Dominator DAGs: Generalizing Single Static Assignment

George Stelle, Los Alamos National Laboratory
Seminar

Single static assignment (SSA) has become a standard semantics for internal representations in modern compilers. A fundamental part of SSA is calculating and using domination relations, which determine where variables can be referenced. Dominator trees, used for calculating domination relations, have historically been an efficient and accurate approximation of the true domination relation. Unfortunately, there are programs for which dominator trees fail to capture precise domination relations, preventing a large class of optimizations. In this talk, we discuss examples of these kinds of programs, and show how generalizing the dominator tree to a directed acyclic graph (DAG) computes more precise domination relations, enabling more optimizations.  In addition, we discuss how this this generalization is essential for reasoning about concurrent programs, and outline how we hope to use it as a basis for a concurrent SSA theory.