Intro Stuff

Definitions:

Comodity: mass produced unspecialized product

run-time system: program that provides services for running a program but is not considered to be part of an operating system

heuristic: problem solving by experimental and especially trial-an-error methods

pragmatics: dealing with facts and actual occurances; practical

short-shrift: little or no attention to consideration

Parts of Compiler:

Scanner/Lexical Analyzer

• 1st stage of compiling
• takes as input a stream of characters
• outputs a stream of words along with their syntactic categories
• collects symbols to form words
• applies rules to determine if each word is legal in source language

Parser

• primary responsibility recognize syntax
• check if a program is a valid sentence in the syntactic programming model

Preface:

• Compiler Front Ends are commodity these days.
• processors becoming performance sensitive
• performance of compiled code depends on compiler’s ability to optimize for a specific processor and features
• the changes above affect the way compiler is constructed

Compilers development focuses on 2 items:

• • optimization
  • code generation

New hires in a compiler co. far more likely to work on a code generator on a new processor or modify an optimization pass than to work on a scanner or parser

Motivation:

• a compiler is a program that takes source language and translates into assembly for execution on a target architecture
• part of this translation a compiler must:
  • determine if the program is valid
  • map an input program onto the finite resources of a target computer

  manipulate several environments

  • allocates resources
  • orchestrate behavior of run-time data structures
• for an ouput program to have a reasnoble performance a compiler must
  • manage hardware latencies in functional units
  • predict the flow of execution and demand for memory
  • reason about the independence and dependence of different machine-level operations in the program
• a modern compiler contains:
  • greedy heuristic searches
  • deterministic finite automata that recoginze words in input
  • fixed point algorithms that help reason about program behavior
  • simple theorem provers
  • algebraic simplifiers that try to predict the values of expressions
  • solvers for diophontine equations, Pressburger arithmetic – used to analyze: array subscripts, classic algorithsm, data stuctures such as hash tables, graph algorithms and sparse set implementations

Balance

• Engineering a Compiler(EAC), for use in an intro course on design and implementation of compilers
• EAC:
  • discusses many of the problems faced by compiler people and teqniques used to solve these problems
  • material rebalanced for more coverage on optimization and code generation and less on front end, material students will need in the job market
  • focuses on best-practices techniques( used for modern commercial or research compiler):
    • static single assignment form
    • list scheduling
    • graph-coloring register allocation
  • contains info for the advance student or practicing professional
  • Advance Topics contains issues and techniques beyond the undergrad course
  • chapter 9 & 10 are more in depth than typical undergrad course

Approach

• Intermediate representation, a representation done without any consideration, for compiler has a deep impact on the rest of the compiler:
  • time and space
  • the ease with which different algorithms can be applied