Utilizing the Value State Dependence Graph for Haskell

Abstract

Modern compilers use control flow based intermediate representations for representing programs during code optimization and generation. However, many optimizations tend to rely not on the explicit representation of control paths, but on the flow of data between operations. One such intermediate representation that makes this flow explicit is the Value State Dependence Graph (VSDG). It abandoned explicit control flow and only models the data flow between operations. The flow of control is at a later point recovered from these data flow properties. The goal of this thesis is to make the Value State Dependence Graph applicable for Haskell. This is accomplished by equipping the GHC compiler with a proof-of-concept back-end that facilitates the use of it. The new back-end allows for a simplified compilation process by translating a program at an early stage into a VSDG and expressing all further transformations down to assembly code in it. Also, the back-end is theoretically evaluated and a comparison is drawn between it and the already present ones.