Compilers and Translators:

Software Verification Tools

Lecture 4: Flow Graphs

September 13, 2007

- Review
- Flow graphs and their representation
- Loops
- Introduction to code optimization
- Exercise
- Reading

- Mathematical logic and proofs
- Compiler phases
- Reading

- Basic blocks
- We can partition the IR into basic blocks, which are maximal sequences of
consecutive three-address instructions such that
- The flow of control can only enter the basic block through the first instruction of the block.
- Control will leave the block without halting or branching, except possibly at the last instruction in the block.

- Algorithm 8.5: partitioning a sequence of three-address instructions into basic blocks.
- Flow graphs and their representation
- The basic blocks become the nodes of a
*flow graph*, whose edges indicate which blocks can follow which other blocks. - There is an edge from block B to block C iff the first instruction in C
can immediately follow the last instruction in B.
- Representation of flow graphs
- Flow graphs can be represented by standard data structures for graphs. Linked lists are a common representation.
- Basic blocks can be represented by DAGs (see Section 8.5 of ALSU).

- A set of nodes L in a flow graph is a
*loop*if - There is a node in L called the loop entry with the property that no other node in L has a predecessor outside L.
- Every node in L has a nonempty path completely within L to the entry of L.

- Causes of redundancy
- Semantics-preserving transformations
- Common subexpression elimination
- Copy propagation
- Dead-code elimination
- Code motion
- Induction variables and reduction in strength

```
do {
KeAcquireSpinLock();
nPacketsOld = nPackets;
if(request){
request = request->Next;
KeReleaseSpinLock();
nPackets++;
}
} while (nPackets != nPacketsOld);
KeReleaseSpinLock();
```

- ALSU: sections 8.4, 8.5, 9.1
- Ball and Rajamani: The SLAM project: Debugging system software via static analysis
- Ball et al.: Thorough static analysis of device drivers

aho@cs.columbia.edu