CSC 355 Notes
Tuesday Dec 6, 2005
 

Topics:

• Updates & reminders
  • Final Project
    • Thursday December 8 - date for completion
    • In-class demo of your project accomplishments
      • Build & run; show samples; what phases are complete
      • Key accomplishments & challenges
      • Less than 10 minutes per group; be prepared to demo to minimize set-up time
      • Don't provide line by line commentary; this is a chance to share with you classmates
    • Report submission
      • Written report summarizing your accomplishments on the project
      • Include representative/key parts of the specification files - it is note necessary to include the complete files
      • Some expected elements of your document would include
        • Project goals & background
        • Successes
        • Challenges
        • Narrative of your design philosophy with some real examples sprinkled in
  • Final Exam
    • Take Home - distributed 12/8 - due 12/13
    • In Class - Tuesday 12/13 8:00am
   
• Type rules
• Code generation
• Optimization
  • data-flow analysis
  • simulated execution
  • program statistics
  • loop structure analysis
  • code elimination
  • code motion
  • code selection
  • constant value analysis
  • constant folding
  • common subexpression detection
  • loop optimizations
    • range analysis
    • loop unrolling
    • register and memory allocation

AST

• intermediate form
• represent the essential information from the program
• internal nodes represent constructs
• branches represent the components that collectively form the construct

Examine structure of AST

• work with tree to try to "improve" the structure
• better code, better organization, ...
• constant subtrees
  • constant expression can be evaluated at compile time
  • replace the expression evaluation with the result
• remove constant computations (produce same value each time) from a loop

Why other representations may be used

• such as 3-address code or ...
• more program-like nature
• goto's (and other unstructured components)

Code optimization by transformation

• flow analysis or data flow analysis (DFA)
• trace flow of data though a compilation unit (usually a procedure)
• forward information flow
  • constant propagation
    • reference to a variable known to be constant can be replaced by constant
• backward information flow
  • eliminate assignments to variables that will never be used again

Sample Program

Module Dataflow;

From IO import ReadInt, WriteInt;

Var a,b,c : integer;

begin

 a := 5 ;

 ReadInt(b);

 if b=3 then

   c := a - b;

 else

   a := b;

   b := 3;

 end

 writeInt(c+b);

end dataflow;

Forward data-flow analysis

• track variables known to have a constant value
• need to handle each branch separately, then combine at joins
• in our set , assign numbers to variables ( a=0, b=1, c=2 )

Module Dataflow;

From IO import ReadInt, WriteInt;

Var a,b,c : integer;

begin

 a := 5 ;

 ReadInt(b);

 if b=3 then

   c := a - b;

 else

   a := b;

   b := 3;

 end

 writeInt(c+b);

end dataflow;

Backward data-flow analysis

• track live variables
• live variables have values that may be used again
• need to start at the end of the program, only time we know the answer
• assignment to a variable "kills" that variable
• using the variable in an expression brings is back into the set
• previous value of variable will be used after this line

Module Dataflow;

From IO import ReadInt, WriteInt;

Var a,b,c : integer;

begin

 a := 5 ;

 ReadInt(b);

 if b=3 then

   c := a - b;

 else

   a := b;

   b := 3;

 end

 writeInt(c+b);

end dataflow;

So what types of information does this provide?

Other types of optimizations

• Simulated execution - partial evaluation
  • evaluate as much as possible at compile time
  • look for constants
  • keep track of what variables, registers are used
  • look for similarities for common sub-expressions
• Program statistics
  • determine or gather statistics
  • how many time is variable used, how many lines of code, etc
• Loop structure analysis
  • what variables control the loop
  • nesting structure
• Code elimination
  • prune off code that does not need to be executed
  • code that does not contribute to the result
• Code motion
  • move code
  • move code out of a loop body
  • move code closer to other accesses (cache)

Code Generation

• Must produce correct code
• only then should efficiency and optimization be a concern
  • register allocation
• understand the target
• only with thorough understanding of the source and target languages can you hope to make this endeavor successful
• formal specifications are very important

Register allocation

• generate code with "infinite" registers or temp memory locations
• but that does not lead to realistic code
• need to fit into the finite confines of a real system
• registers will probably need to be "spilled" into memory
• but want to make the most efficient use possible
• register operation are faster than those involving memory operands
• need to decide what should be in registers
• need to decide which register it should be in

Register allocation by graph coloring (only one of many approaches)

• Pass 1: generate code with infinite registers
• Pass 2 : construct graph representation
  • nodes are registers
  • edge connects nodes if register is "live" at time other is defined
• Color graph using K colors (where K is number of registers available)
• each color represents a register
  • by coloring, it ensures that 2 symbolic registers can be assigned to the same physical register with no interference
• if "k-colorable", then assign to registers
• if not, then must spill some registers 
  • pick registers not in inner loops ...

Code Optimization

• create efficient target programs
• most bang for the buck
• must preserve meaning and will hopefully speed-up the program by a noticeable amount
• many times, the best improvements can be found at the source language or algorithm level

Basic blocks

• sequence of consecutive statements
• flow of control enters at the beginning
• flow of control leaves at the end
• within block, will not halt and no branching
• given a sequence of 3-address  statements, partition into basic blocks
  • divide based on statements involved in flow of control changes/choices
  • first statement
  • any target of a jump
  • any statement following a jump
• a name in a basic block is "live" at a given point if its value is used after that point in the program
• perform transformations on basic blocks - maintain equivalence
  • values that are live at the end of the block are the same

Transformations

• common subexpression elimination
• dead-code elimination
• renaming of temporary variables
• interchange of statements (independent, adjacent)

Common subexpressions

• value of E has been computed
• E is needed again (and the values of the variables used in E have not changed)
• can simply access the previously "computed" result

An example

• a := b + c
  b := a - d
  c := b + c
  d := a - d

• are there any common subexpressions
• can they be removed (combined)

Dead-code elimination

• dead code = statements that compute values that are not used
• given statement:   d := b + c
• if d is not used again after this line, the assignment statement itself is not needed.
• the code can be removed from the generated code
• while it may be unlikely that a programmer would intentionally insert dead code, there may be some conditions which can be deduced at compile time that affect if-statements or loops

Renaming and code movement

• temporary variables can be renamed (if done consistently)
  • t4 = a + b
  • can replace all "t4" occurrences by v and things will still be fine
• interchanging independent and adjacent statements
  • a := b + c
    d := e + f
  • d := e + f
    a := b + c

Loop optimizations

• much time is spent in loops
• inner-loops can play a large part in the run-time of a program
• code motion : moves code outside of loop
  • loop invariant computation : produces same result no matter how many times the instruction is executed
  • place the expression before the loop
  • while ( i <= limit - 2 )
  • t = limit - 2; while ( i <= t )
• induction-variable elimination :
• reduction in strength : replace an expensive operations by a cheaper one