Abstract
This chapter provides a gentle introduction to classical data-flow analysis and explains how SSA form improves both performance and expressiveness. In the first part, classical data-flow analysis is discussed by introducing the fundamentals of monotone frameworks on control-flow graphs. In the following part, the chapter introduces a simple and elegant data-flow engine that exploits SSA form. The engine relies on SSA form in order to efficiently propagate information on the values of variables on a so-called SSA graph, while at the same time taking into account control dependencies that emerge from the classical control-flow graph. The engine’s operation is explained through several examples based on constant and copy propagation, which illustrate the advantages of jointly processing the program’s data and control flow.
| Original language | English |
|---|---|
| Title of host publication | SSA-based Compiler Design |
| Publisher | Springer International Publishing |
| Pages | 95-106 |
| Number of pages | 12 |
| ISBN (Electronic) | 9783030805159 |
| ISBN (Print) | 9783030805142 |
| DOIs | |
| Publication status | Published - 1 Jan 2022 |
Keywords
- Compact evaluation graph (CEG)
- Compiler design
- Constant propagation
- Control dependence
- Copy propagation
- Data dependence
- Data-flow analysis
- Forward analysis
- Lattice
- Liveness analysis
- Maximal fixed point (MFP)
- Meet over all path (MOP)
- Monotone analysis
- Propagation
- Range propagation
- SSA graph
- Single-entry/single-exit region (SESE)
- Sparse data-flow analysis
- Sparse evaluation graph (SEG)
- Static analysis
- Static single assignment form (SSA form)
- Transfer function