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
Undergraduate 2
05/28/2013

Additional Computer Science Flashcards

 


 

Cards

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!