Optimising Compilers

 

Optimising Compilers

Basic blocks: Have one predecessor and one successor. They reduce time and space requirements for analysis algorithms by calculating and storing data flow into once per per block rather than once per instruction. Normal form uses a new temporary variable on each occasion.

Local/peeophole analysis: Within a basic block.

Interprocedural: Over the whole program.

Simple Analysis: Unreachable nodes are deleted. Delete procedures which aren't callable.

Live variable analysis: Used to warn of dataflow errors, and to perform register allocation by colouring.

Semantically live: A variable x is semantically live at node n if there is an execution sequence starting at n, whose I/O behavior can be affected by changing the value of x.

Syntactically live: A variable x is syntactically live at node n if a later node may use the current value of x.

AVAIL: An expression e is available at node n if e is available (evaluated and not invalidated).

Graph coloring heuristic:

  • Choose a virtual register with the least number of clashes

  • If this is less than the number of colours, then push it on a LIFO stack since we can guarantee to colour it. Remove the register from the clash graph.

  • If all virtual registers have more clashes than colors then split the one with the least number of accesses.

  • When the clash graph is empty, pop all the virtual registers and color them.

Common subexpression elimination: Use a variable to store e rather than recomputing.

Partial redundancy elimination: Remove doubles in loops.

Phase optimisation problem: Different order of optimisation for different programs.

Higher level optimizations: Algebraic identities eg; e+0->e

Strength reduction: Replacing expensive operations with cheaper ones, eg; 2xe->e+e.

Can eliminate variables, eg; if j = x (+) y, then j(x)->x(x)y(x)x.

And replacing variables in loops eg V[i] with addresses. Becomes less human readable, and less optimisable.

Abstract interpretation: Eg; can know that negative x positive = negative.

Strictness analysis: A function in a lazy functional language that is strict is evaluated whenever the function returns. Hence we can use call by value, which is faster (as closer to hardware, can be done in parallel).

Strictness function: Eg; if x then y else z – x is strict.

Constraint based analysis: Walk through program, emitting constraints. Eg; if X is constrained to be odd then X+1 is constrained to be even.

Control flow analysis: Given a program, what values can result from e.

Inference based program analysis: Finds types.

Effect systems: Finds which channels can be read or written to in P.

Instruction Scheduling: Aims to minimize the number of NOPs in a pipeline.

Decomplimation: EU 1991 software directive says you can reproduce and translate for interoperability. Need to match flow graph from assembler with higher level control structures.