Propagating Information Using SSA

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.