# Shared Flashcard Set

## Details

Comp2010 - Flashcard Set 9 - Code Generation 2: Instruction
Comp2010 - Flashcard Set 9 - Code Generation 2: Instruction Emission and Code Optimization
13
Computer Science
05/28/2013

Term
 What are the principles of Instruction Selection?
Definition
 Generating real machine instructions from IR tree (or intermediate code) Followed by register allocation Not a 1:1 correspondence between tree nodes and instructions
Term
 What are some instruction tree patterns?
Definition
 [image][image][image]
Term
 What are the principles of tiling an IR tree?
Definition
 Cover IR tree with set of non-overlapping tiles Tile=tree pattern corresponding to a legal machine instruction E.g. a[i] = x; i held in a register a and x escape (stored in current stack frame)
Term
 What are some characteristics of Optimal Tilings?
Definition
 Best tiling --> least cost instruction sequence Smallest number of instructions Lowest execution time Optimum tiling: minimizes sum of costs of tiles Optimal tiling: cannot combine adjecent tiles into a tile of lower cost Optimum may be significantly better than optimal CISC processors: large tiles, variable cost RISC processors: small tiles, uniform cost Not much difference
Term
 What is an Optimal Tiling Algorithm?
Definition
 Maximal Munch Start at root, find largest tile that fits Use to cover that part of tree, leaving several subtrees Repeat for each subtree Largest = covers most nodes Arbitrary choice where more than one NB: Order in which instructions are emitted is different from the "munch order"
Term
 What are the principles of register allocation?
Definition
 Result of instruction selection still uses (mainly) "indeterminate" registers Need to allocate to real registers Allocate multiple temporaries to same real register When not alive (i.e. in use) at the same time Spill into memory if necessary Involves modifying instruction sequence
Term
 What are the principles of liveness analysis?
Definition
 A variable is live if it holds a value that may be needed in the future
Term
 What does an interference graph tell us?
Definition
 An interference graph expresses constraints Nodes represent temporaries Two nodes connected by an edge if they cannot be allocated to the same register Use graph colouring algorithm to allocate available registers to nodes
Term
 What are the principles of code optimization?
Definition
 Techniques for improving quality of generated code Law of diminishing result applies Most important is good register allocation Peephole optimization applied locally to generated redundant code: remove redundant code
Term
 What are some common subexpressions that can be removed for optimization?
Definition
 Eliminate repeated evaluation of expressions whose value does not change Usually done by transformations on AST (or IR tree) e.g. a[i+j] = a[i+j] + 1; calculates  [[ (baseaddress of a) + (i + j)*elementSize ]] twice
Term
 What is constant folding in code optimization?
Definition
 Evaluate expressions as much as possible during compile time Obvious: 2+5 less obvious: ((2*x)+1)*3 Constant propagation double pi = 3.1415; double twopi = 2*pi; Copy propagation a=x+z; b=y; c=b+z;
Term
 What is dead code elimination in code optimization?
Definition
 Remove code that is unreachable or has no effect But be careful as optimization must preserve program behaviour.
Term
 What are some common loop optimizations?
Definition
 High proportion of execution time spent in (inner) loops Move invariant computations outside loop
Supporting users have an ad free experience!