Optimization: control-flow analysis
COP-5621
Control-Flow Analysis
What is a Control-Flow Graph (CFG)?
Starting with each instruction as its own block
Why Would We Need a CFG?
Elements of a CFG
Examples
Using SimpleIR
Conditional statement from While
Conditional statement from SimpleIR
Loops
Nested control statements
An algorithm for CFG construction
- Create entry and exit nodes (used for optimization later)
- Collect the leaders of the basic blocks, i.e., each line that starts a basic block, and creating a new node for each
- create edges between basic blocks, looking at each basic block's ending goto/ifgoto and create an edge to the target leader
How do we know when something is a leader, i.e., the first line of a basic block?
- First line of the program
- Target of a goto/ifgoto
- Line after a goto/ifgoto