Source

youtube

Program Representation

Basic Block

flow -> “Basic block” -> out

• a basic block has only one entry point and one exit point.
• no inside jump
• never jump to middle
• control can always leaves successfully, only exception is last instruction

leader

first instruction

• first instruction of program
• target of a jump
• instruction immediately run after a jump

Directed Acyclic Graphs

DAG-Based Optimization. <- Local optimization.

• Node = input value of basic block, associated with instruction inside basic block
• instruction S uses var defined in S1,…Sn -> edge of Si to S
• var defined but not used inside its def-basic-block, mark it to output value

1
2
3
4

1: a = b + c
2: b = a - d
3: c = b + c
4: d = a - d

DAG:

1
2
3

in b,c -> out (+,a)
in a,d -> out (-,b)
...

Optimize

• Hashmap<Pair<Function,Node>>.existed -> v’ = alias of v
• to Value-Number table
  Pair<Instruction, Pair<Function, List<Node>>>

  1 2 3 4 5

  1 (b) to (in,_) ... 4 (b = d - a) to (-, 3, 4) // 3 is nodeId ... 7 (d = d - a) to (-, 3, 4)

  • same number(4,7) = dup!

Dead code elimination can be made!

Peephole Optimization

• analyze a sliding window of instructions
• observe patter in windows, and optimize

Can be used for optimizing branches, eg: fall through

1
2
3
4
5
6

if (a < b) 
  goto L1
  ...
L1: // Fall through here
  goto L2
  ...

equals to

1
2
3

if (a < b)
  goto L2
  ... // Contents still be here

'Cause:

• no other branch might jmp to L1
• L1 is proceeded by unconditioned jmp

Strength Reduction

make program fit computer architecture eg:

• x*2 -> x<<1
• addl $1, %rax -> inc %rax

Local Register Allocation

• if first use of variable, load to reg
• on use:
  • in reg: do nothing
  • not in reg: load from memory, and if needed, store the not used values to memory
• free register once the variable never used

To allocate, if regs have different sizes, it’s NP-complete
minimizing cost is also NP-Complete

Data flow analysis

flow sensitive: dependencies between data & control flow
CFG Example:

Image

Image End