Center for Embedded Computer Systems	Computer Science and Engineering
Microelectronic Embedded Systems Laboratory	University Of California, San Diego

3-Layered Intermediate Representation

Spark employs a 3-layered intermediate representation that consists of control flow graphs (CFGs), data flow graphs (DFGs) and hierarchical task graphs (HTGs). Whereas the data flow graphs are useful for capturing data dependencies between operations, the CFGs and HTGs capture the control flow between the basic blocks and hierarchical nodes (if-then-else, loop nodes) respectively. Thus, whereas CFGs are useful for traversing the design during scheduling, the HTGs are used for moving operations hierarchicall across large pieces of code without visiting each intermediate node.

Hierarchical Task Graphs

Traditionally, control-data flow graphs (CDFGs) have been the most popular intermediate representation for high-level synthesis. CDFGs consist of operation and control nodes with edges for both data flow and control flow. CDFGs work very well for the traditional high-level synthesis tasks of scheduling and binding. However, we found the abstraction level offered by CDFGs is too thin for the range of coarse-grain and fine-grain parallelizing compiler transformations that we proposed.

In order to enable the range of optimizations explored by our work, the Spark framework uses an intermediate representation that maintains the hierarchical structuring of the design such as if-then-else blocks and for and while loops. This intermediate representation consists of basic blocks encapsulated in Hierarchical Task Graphs (HTGs).

Since HTGs maintain a hierarchy of nodes, they are able to retain coarse, high level information about program structure, in addition to operation level and basic block level information. This aids in coarse-grain code restructuring (such as that done by loop transformations) and also, in operation movement by reducing the amount of compensation code required. Furthermore, non-incremental moves of operations across large blocks of code are possible without visiting each intermediate node.

Consider the sample ``C'' code in Figure 1(a). The HTG representation for this code is given in Figure 1(b). The HTG representation consists of a compound design HTG (htg_0) that encapsulates the HTG nodes, htg_1 to htg_7, and the control flow edges between the HTG nodes (shown by dashed arrows). The if-then-else control construct from the source code is encapsulated in the compound If-HTG node, htg_2. The If-HTG node consists of a single node for the conditional check, a compound node for the true/then branch, a compound node for the false/else branch and a single node for the Join node (containing only an empty basic block as explained below).

In Figure 1(c), we show how the control flow graph (CFG) and data flow graph (DFG) can be overlaid onto the HTG graph. Basic blocks are denoted by shaded boxes within the HTG nodes (bb_0 to bb_5) and operations are denoted by circular nodes with the operator sign within (operations 1 to 8). Dashed lines denote control flow between HTG nodes and solid lines denote data flow between operations. A fork in the control flow (i.e. a Boolean condition check) is denoted by a triangle and a merge by an inverted triangle.