Technical reports

Optimizing compilation with the Value State Dependence Graph

Alan C. Lawrence

December 2007, 183 pages

This technical report is based on a dissertation submitted May 2007 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Churchill College.

Some figures in this document are best viewed in colour. If you received a black-and-white copy, please consult the online version if necessary.

DOI: 10.48456/tr-705

Abstract

Most modern compilers are based on variants of the Control Flow Graph. Developments on this representation—specifically, SSA form and the Program Dependence Graph (PDG)—have focused on adding and refining data dependence information, and these suggest the next step is to use a purely data-dependence-based representation such as the VDG (Ernst et al.) or VSDG (Johnson et al.).

This thesis studies such representations, identifying key differences in the information carried by the VSDG and several restricted forms of PDG, which relate to functional programming and continuations. We unify these representations in a new framework for specifying the sharing of resources across a computation.

We study the problems posed by using the VSDG, and argue that existing techniques have not solved the sequentialization problem of mapping VSDGs back to CFGs. We propose a new compiler architecture breaking sequentialization into several stages which focus on different characteristics of the input VSDG, and tend to be concerned with different properties of the output and target machine. The stages integrate a wide variety of important optimizations, exploit opportunities offered by the VSDG to address many common phase-order problems, and unify many operations previously considered distinct.

Focusing on branch-intensive code, we demonstrate how effective control flow—sometimes superior to that of the original source code, and comparable to the best CFG optimization techniques—can be reconstructed from just the dataflow information comprising the VSDG. Further, a wide variety of more invasive optimizations involving the duplication and specialization of program elements are eased because the VSDG relaxes the CFG’s overspecification of instruction and branch ordering. Specifically we identify the optimization of nested branches as generalizing the problem of minimizing boolean expressions.

We conclude that it is now practical to discard the control flow information rather than maintain it in parallel as is done in many previous approaches (e.g. the PDG).

Full text

PDF (3.8 MB)

BibTeX record

@TechReport{UCAM-CL-TR-705,
  author =	 {Lawrence, Alan C.},
  title = 	 {{Optimizing compilation with the Value State Dependence
         	   Graph}},
  year = 	 2007,
  month = 	 dec,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-705.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-705},
  number = 	 {UCAM-CL-TR-705}
}