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
|
|
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
|
|
|
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
|
|
|
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
|
|
|
