Make dataflow visible in an intermediate representation

Prerequisites: Control-flow graphs, variables, and sets.

Learning objectives

• Explain the purpose of basic blocks and an intermediate representation.
• Interpret an SSA phi at a control-flow join.
• Calculate backward liveness for a small block.

Give transformations an explicit structure

An intermediate representation, or IR, sits between source syntax and final machine code. It exposes operations and control flow in a form suitable for analysis and transformation. A basic block is a straight-line sequence with one entry and control transfer at its end. A control-flow graph connects blocks by possible successor edges.

Three-address-style IR gives intermediate results names, separating a compound expression into simpler operations. For example, y=(a+b)c can become t1=a+b followed by y=t1c. The representation does not itself prove that every reordering is legal; side effects and dependencies still constrain transformations.

A join must explain which definition arrives

Static single assignment, SSA, gives each defined value a distinct name. Consider a branch that assigns x=1 on the left path and x=2 on the right. SSA can name these x_left and x_right, then introduce x_join=phi(left:x_left,right:x_right) in the joining block. The phi selects the value associated with the edge actually taken. It does not add both values or execute both predecessor blocks.

SSA makes many dependencies explicit, but memory still needs a model because two addresses can alias. A compiler may use additional memory representations or conservative analysis rather than pretending every load reads an independent variable.

Compute what remains needed

A variable is live at a point if its current value may be used along some future path before being overwritten. For a block, let USE contain values read before being defined in that block, and DEF contain values defined there. The backward equations are OUT[B]=union of IN over successors, and IN[B]=USE[B] union (OUT[B] minus DEF[B]).

Take a block containing t=a+b followed by c=t*2, with a successor that needs c and d. OUT is {c,d}. USE is {a,b}; the read of t is satisfied by its earlier definition in this block. DEF is {t,c}. Therefore IN is {a,b,d}. The old value of c is not needed at entry because the block overwrites it before the successor uses it.

Loops make the equations mutually dependent. Start with conservative initialization appropriate to the analysis and repeatedly propagate sets until they stop changing. For this finite liveness analysis, starting with empty sets and monotonically adding facts reaches the least fixed point. A single pass can miss information traveling around a loop.

Liveness supports register allocation and dead-value reasoning, but an unused result does not automatically make its instruction removable. A call may perform I/O, a store changes memory, and an operation may trap. Analysis facts justify transformations only when combined with the IR’s effect and semantic rules.

Primary reading

• LLVM Language Reference (LLVM Project).
• Live Variable Analysis and Worklist Algorithms (Cornell University, CS4120).

Practice problem

For a block containing p=u+v followed by u=p+1, assume the successor needs u and w. Compute USE, DEF, OUT, and IN under the stated equations. Then explain why an instruction whose result is not live might still need to remain if it calls an output routine.

Worked solution

USE is {u,v}, because the first instruction reads the incoming values of u and v before either is defined in the block. DEF is {p,u}. OUT is {u,w}, as supplied by the successor requirement. Subtracting DEF from OUT leaves {w}; union with USE gives IN={u,v,w}. The incoming value of u is live despite u also appearing in DEF because it is read before being overwritten. An output routine can have an observable side effect even when its return value is unused. Removing that call would change the program’s visible behavior. Liveness of result values is therefore only one input to dead-code elimination; effect and exception behavior must also be considered.

Check your understanding

What does an SSA phi choose?

• The sum of all predecessor values.
• The value corresponding to the control-flow edge used to enter the block.
• A random register each run.
• Always the first source variable alphabetically.

Explanation

A phi expresses the merge of path-specific definitions.

Why can liveness analysis need repeated propagation?

• Loops make block equations depend on one another.
• Set union can never be computed.
• Every block must execute twice.
• The source program has no variables.

Explanation

Facts discovered on one pass may flow around a cycle and affect earlier blocks.

Primary reading

• LLVM Language Reference: LLVM Project
• Live Variable Analysis and Worklist Algorithms: Cornell University, CS4120

Open the study and save your work →