Dominator DAGs: Generalizing Single Static Assignment

Event Sponsor: 
Argonne Leadership Computing Facility Seminar
Start Date: 
Jul 25 2019 - 10:00am
Building/Room: 
Building 240/Room 4301
Location: 
Argonne National Laboratory
Speaker(s): 
George Stelle
Speaker(s) Title: 
Los Alamos National Laboratory

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.