docs/DependenceGraphs/index.rst

   1 =========================
   2 Dependence Graphs in LLVM
   3 =========================
   4
   5 .. contents::
   6    :local:
   7
   8 Introduction
   9 ============
  10 Dependence graphs are useful tools in compilers for analyzing relationships
  11 between various program elements to help guide optimizations. The ideas
  12 behind these graphs are described in papers [1]_ and [2]_.
  13
  14 The implementation of these ideas in LLVM may be slightly different than
  15 what is mentioned in the papers. These differences are documented in
  16 the `implementation details <implementation-details_>`_.
  17
  18 .. _DataDependenceGraph:
  19
  20 Data Dependence Graph
  21 =====================
  22 In its simplest form the Data Dependence Graph (or DDG) represents data
  23 dependencies between individual instructions. Each node in such a graph
  24 represents a single instruction and is referred to as an "atomic" node.
  25 It is also possible to combine some atomic nodes that have a simple
  26 def-use dependency between them into larger nodes that contain multiple-
  27 instructions.
  28
  29 As described in [1]_ the DDG uses graph abstraction to group nodes
  30 that are part of a strongly connected component of the graph
  31 into special nodes called pi-blocks. pi-blocks represent cycles of data
  32 dependency that prevent reordering transformations. Since any strongly
  33 connected component of the graph is a maximal subgraph of all the nodes
  34 that form a cycle, pi-blocks are at most one level deep. In other words,
  35 no pi-blocks are nested inside another pi-block, resulting in a
  36 hierarchical representation that is at most one level deep.
  37
  38
  39 For example, consider the following:
  40
  41 .. code-block:: c++
  42
  43   for (int i = 1; i < n; i++) {
  44     b[i] = c[i] + b[i-1];
  45   }
  46
  47 This code contains a statement that has a loop carried dependence on
  48 itself creating a cycle in the DDG. The figure bellow illustrates
  49 how the cycle of dependency is carried through multiple def-use relations
  50 and a memory access dependency.
  51
  52 .. image:: cycle.png
  53
  54 The DDG corresponding to this example would have a pi-block that contains
  55 all the nodes participating in the cycle, as shown bellow:
  56
  57 .. image:: cycle_pi.png
  58
  59 Program Dependence Graph
  60 ========================
  61
  62 The Program Dependence Graph (or PDG) has a similar structure as the
  63 DDG, but it is capable of representing both data dependencies and
  64 control-flow dependencies between program elements such as
  65 instructions, groups of instructions, basic blocks or groups of
  66 basic blocks.
  67
  68 High-Level Design
  69 =================
  70
  71 The DDG and the PDG are both directed graphs and they extend the
  72 ``DirectedGraph`` class. Each implementation extends its corresponding
  73 node and edge types resulting in the inheritance relationship depicted
  74 in the UML diagram bellow:
  75
  76 .. image:: uml_nodes_and_edges.png
  77
  78 Graph Construction
  79 ------------------
  80
  81 The graph build algorithm considers dependencies between elements of
  82 a given set of instructions or basic blocks. Any dependencies coming
  83 into or going out of instructions that do not belong to that range
  84 are ignored. The steps in the build algorithm for the DDG are very
  85 similar to the steps in the build algorithm for the PDG. As such,
  86 one of the design goals is to reuse the build algorithm code to
  87 allow creation of both DDG and PDG representations while allowing
  88 the two implementations to define their own distinct and independent
  89 node and edge types. This is achieved by using the well-known builder
  90 design pattern to isolate the construction of the dependence graph
  91 from its concrete representation.
  92
  93 The following UML diagram depicts the overall structure of the design
  94 pattern as it applies to the dependence graph implementation.
  95
  96 .. image:: uml_builder_pattern.png
  97
  98 Notice that the common code for building the two types of graphs are
  99 provided in the ``DependenceGraphBuilder`` class, while the ``DDGBuilder``
 100 and ``PDGBuilder`` control some aspects of how the graph is constructed
 101 by the way of overriding virtual methods defined in ``DependenceGraphBuilder``.
 102
 103 Note also that the steps and the names used in this diagram are for
 104 illustrative purposes and may be different from those in the actual
 105 implementation.
 106
 107 Design Trade-offs
 108 -----------------
 109
 110 Advantages:
 111 ^^^^^^^^^^^
 112   - Builder allows graph construction code to be reused for DDG and PDG.
 113   - Builder allows us to create DDG and PDG as separate graphs.
 114   - DDG nodes and edges are completely disjoint from PDG nodes and edges allowing them to change easily and independently.
 115
 116 Disadvantages:
 117 ^^^^^^^^^^^^^^
 118   - Builder may be perceived as over-engineering at first.
 119   - There are some similarities between DDG nodes and edges compared to PDG nodes and edges, but there is little reuse of the class definitions.
 120
 121     - This is tolerable given that the node and edge types are fairly simple and there is little code reuse opportunity anyway.
 122
 123
 124 .. _implementation-details:
 125
 126 Implementation Details
 127 ======================
 128
 129 The current implementation of DDG differs slightly from the dependence
 130 graph described in [1]_ in the following ways:
 131
 132   1. The graph nodes in the paper represent three main program components, namely *assignment statements*, *for loop headers* and *while loop headers*. In this implementation, DDG nodes naturally represent LLVM IR instructions. An assignment statement in this implementation typically involves a node representing the ``store`` instruction along with a number of individual nodes computing the right-hand-side of the assignment that connect to the ``store`` node via a def-use edge.  The loop header instructions are not represented as special nodes in this implementation because they have limited uses and can be easily identified, for example, through ``LoopAnalysis``.
 133   2. The paper describes five types of dependency edges between nodes namely *loop dependency*, *flow-*, *anti-*, *output-*, and *input-* dependencies. In this implementation *memory* edges represent the *flow-*, *anti-*, *output-*, and *input-* dependencies. However, *loop dependencies* are not made explicit, because they mainly represent association between a loop structure and the program elements inside the loop and this association is fairly obvious in LLVM IR itself.
 134   3. The paper describes two types of pi-blocks; *recurrences* whose bodies are SCCs and *IN* nodes whose bodies are not part of any SCC. In this impelmentation, pi-blocks are only created for *recurrences*. *IN* nodes remain as simple DDG nodes in the graph.
 135
 136
 137 References
 138 ----------
 139 .. [1] "D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe (1981). DEPENDENCE GRAPHS AND COMPILER OPTIMIZATIONS."
 140 .. [2] "J. FERRANTE (IBM), K. J. OTTENSTEIN (Michigan Technological University) and JOE D. WARREN (Rice University), 1987. The Program Dependence Graph and Its Use in Optimization."