Seonglae ChoStatic Single Assignment
An IR form where every variable (register) is assigned exactly once. It transforms imperative programs into a graph (circuit) structure, making analysis and optimization easier. The reason for its creation is that imperative code with frequent variable reassignments is difficult to analyze for data flow. Converting to SSA transforms the program into a Pure Function purely functional circuit (DAG) form, enabling optimization through graph algorithms.
- Programs are divided into Basic Blocks (non-branching code), (Extended basic block (EBB)
- These blocks form a Control Flow Graph (CFG).
- In SSA, variable connections between blocks are represented by phi nodes (or block arguments).
Dominance Concept
- If a block is included in all paths to another block, it has a dominates relationship.
- This relationship defines the Dominance Tree and Dominance Frontier, allowing precise placement of phi nodes at merge points.
- Lifting Memory
- Analyzes
store→loadpatterns to eliminate memory access and replace with pure register operations. - Tracks
storeinstructions that aloadcan reference by following the Dataflow Graph.
- Optimization Process
- Dependency Analysis to track load-store relationships
- Remove unnecessary memory access (lift)
- Clean up with Dead Code Elimination / CFG Simplification
- Result: SSA transforms programs into a graph-theoretically interpretable circuit form, serving as the foundation for various optimizations including constant propagation, CSE, and loop optimization.
