1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
|
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Dependence Graphs in LLVM — LLVM 13 documentation</title>
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../_static/llvm-theme.css" type="text/css" />
<script id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
<script src="../_static/jquery.js"></script>
<script src="../_static/underscore.js"></script>
<script src="../_static/doctools.js"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="Exception Handling in LLVM" href="../ExceptionHandling.html" />
<link rel="prev" title="Coroutines in LLVM" href="../Coroutines.html" />
<style type="text/css">
table.right { float: right; margin-left: 20px; }
table.right td { border: 1px solid #ccc; }
</style>
</head><body>
<div class="logo">
<a href="../index.html">
<img src="../_static/logo.png"
alt="LLVM Logo" width="250" height="88"/></a>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="../ExceptionHandling.html" title="Exception Handling in LLVM"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="../Coroutines.html" title="Coroutines in LLVM"
accesskey="P">previous</a> |</li>
<li><a href="https://llvm.org/">LLVM Home</a> | </li>
<li><a href="../index.html">Documentation</a>»</li>
<li class="nav-item nav-item-1"><a href="../Reference.html" accesskey="U">Reference</a> »</li>
<li class="nav-item nav-item-this"><a href="">Dependence Graphs in LLVM</a></li>
</ul>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3>Documentation</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/GettingStartedTutorials.html">Getting Started/Tutorials</a></li>
<li><a href="https://llvm.org/docs/UserGuides.html">User Guides</a></li>
<li><a href="https://llvm.org/docs/Reference.html">Reference</a></li>
</ul>
<h3>Getting Involved</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/Contributing.html">Contributing to LLVM</a></li>
<li><a href="https://llvm.org/docs/HowToSubmitABug.html">Submitting Bug Reports</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#mailing-lists">Mailing Lists</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#irc">IRC</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#meetups-and-social-events">Meetups and Social Events</a></li>
</ul>
<h3>Additional Links</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/FAQ.html">FAQ</a></li>
<li><a href="https://llvm.org/docs/Lexicon.html">Glossary</a></li>
<li><a href="https://llvm.org/pubs">Publications</a></li>
<li><a href="https://github.com/llvm/llvm-project//">Github Repository</a></li>
</ul>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/DependenceGraphs/index.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="../search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" />
<input type="submit" value="Go" />
</form>
</div>
</div>
<script>$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="section" id="dependence-graphs-in-llvm">
<h1>Dependence Graphs in LLVM<a class="headerlink" href="#dependence-graphs-in-llvm" title="Permalink to this headline">¶</a></h1>
<div class="contents local topic" id="contents">
<ul class="simple">
<li><p><a class="reference internal" href="#introduction" id="id8">Introduction</a></p></li>
<li><p><a class="reference internal" href="#data-dependence-graph" id="id9">Data Dependence Graph</a></p></li>
<li><p><a class="reference internal" href="#program-dependence-graph" id="id10">Program Dependence Graph</a></p></li>
<li><p><a class="reference internal" href="#high-level-design" id="id11">High-Level Design</a></p>
<ul>
<li><p><a class="reference internal" href="#graph-construction" id="id12">Graph Construction</a></p></li>
<li><p><a class="reference internal" href="#design-trade-offs" id="id13">Design Trade-offs</a></p>
<ul>
<li><p><a class="reference internal" href="#advantages" id="id14">Advantages:</a></p></li>
<li><p><a class="reference internal" href="#disadvantages" id="id15">Disadvantages:</a></p></li>
</ul>
</li>
</ul>
</li>
<li><p><a class="reference internal" href="#implementation-details" id="id16">Implementation Details</a></p>
<ul>
<li><p><a class="reference internal" href="#references" id="id17">References</a></p></li>
</ul>
</li>
</ul>
</div>
<div class="section" id="introduction">
<h2><a class="toc-backref" href="#id8">Introduction</a><a class="headerlink" href="#introduction" title="Permalink to this headline">¶</a></h2>
<p>Dependence graphs are useful tools in compilers for analyzing relationships
between various program elements to help guide optimizations. The ideas
behind these graphs are described in papers <a class="footnote-reference brackets" href="#id6" id="id1">1</a> and <a class="footnote-reference brackets" href="#id7" id="id2">2</a>.</p>
<p>The implementation of these ideas in LLVM may be slightly different than
what is mentioned in the papers. These differences are documented in
the <a class="reference internal" href="#implementation-details">implementation details</a>.</p>
</div>
<div class="section" id="data-dependence-graph">
<span id="datadependencegraph"></span><h2><a class="toc-backref" href="#id9">Data Dependence Graph</a><a class="headerlink" href="#data-dependence-graph" title="Permalink to this headline">¶</a></h2>
<p>In its simplest form the Data Dependence Graph (or DDG) represents data
dependencies between individual instructions. Each node in such a graph
represents a single instruction and is referred to as an “atomic” node.
It is also possible to combine some atomic nodes that have a simple
def-use dependency between them into larger nodes that contain multiple-
instructions.</p>
<p>As described in <a class="footnote-reference brackets" href="#id6" id="id3">1</a> the DDG uses graph abstraction to group nodes
that are part of a strongly connected component of the graph
into special nodes called pi-blocks. pi-blocks represent cycles of data
dependency that prevent reordering transformations. Since any strongly
connected component of the graph is a maximal subgraph of all the nodes
that form a cycle, pi-blocks are at most one level deep. In other words,
no pi-blocks are nested inside another pi-block, resulting in a
hierarchical representation that is at most one level deep.</p>
<p>For example, consider the following:</p>
<div class="highlight-c++ notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
<span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="mi">-1</span><span class="p">];</span>
<span class="p">}</span>
</pre></div>
</div>
<p>This code contains a statement that has a loop carried dependence on
itself creating a cycle in the DDG. The figure below illustrates
how the cycle of dependency is carried through multiple def-use relations
and a memory access dependency.</p>
<img alt="../_images/cycle.png" src="../_images/cycle.png" />
<p>The DDG corresponding to this example would have a pi-block that contains
all the nodes participating in the cycle, as shown below:</p>
<img alt="../_images/cycle_pi.png" src="../_images/cycle_pi.png" />
</div>
<div class="section" id="program-dependence-graph">
<h2><a class="toc-backref" href="#id10">Program Dependence Graph</a><a class="headerlink" href="#program-dependence-graph" title="Permalink to this headline">¶</a></h2>
<p>The Program Dependence Graph (or PDG) has a similar structure as the
DDG, but it is capable of representing both data dependencies and
control-flow dependencies between program elements such as
instructions, groups of instructions, basic blocks or groups of
basic blocks.</p>
</div>
<div class="section" id="high-level-design">
<h2><a class="toc-backref" href="#id11">High-Level Design</a><a class="headerlink" href="#high-level-design" title="Permalink to this headline">¶</a></h2>
<p>The DDG and the PDG are both directed graphs and they extend the
<code class="docutils literal notranslate"><span class="pre">DirectedGraph</span></code> class. Each implementation extends its corresponding
node and edge types resulting in the inheritance relationship depicted
in the UML diagram below:</p>
<img alt="../_images/uml_nodes_and_edges.png" src="../_images/uml_nodes_and_edges.png" />
<div class="section" id="graph-construction">
<h3><a class="toc-backref" href="#id12">Graph Construction</a><a class="headerlink" href="#graph-construction" title="Permalink to this headline">¶</a></h3>
<p>The graph build algorithm considers dependencies between elements of
a given set of instructions or basic blocks. Any dependencies coming
into or going out of instructions that do not belong to that range
are ignored. The steps in the build algorithm for the DDG are very
similar to the steps in the build algorithm for the PDG. As such,
one of the design goals is to reuse the build algorithm code to
allow creation of both DDG and PDG representations while allowing
the two implementations to define their own distinct and independent
node and edge types. This is achieved by using the well-known builder
design pattern to isolate the construction of the dependence graph
from its concrete representation.</p>
<p>The following UML diagram depicts the overall structure of the design
pattern as it applies to the dependence graph implementation.</p>
<img alt="../_images/uml_builder_pattern.png" src="../_images/uml_builder_pattern.png" />
<p>Notice that the common code for building the two types of graphs are
provided in the <code class="docutils literal notranslate"><span class="pre">DependenceGraphBuilder</span></code> class, while the <code class="docutils literal notranslate"><span class="pre">DDGBuilder</span></code>
and <code class="docutils literal notranslate"><span class="pre">PDGBuilder</span></code> control some aspects of how the graph is constructed
by the way of overriding virtual methods defined in <code class="docutils literal notranslate"><span class="pre">DependenceGraphBuilder</span></code>.</p>
<p>Note also that the steps and the names used in this diagram are for
illustrative purposes and may be different from those in the actual
implementation.</p>
</div>
<div class="section" id="design-trade-offs">
<h3><a class="toc-backref" href="#id13">Design Trade-offs</a><a class="headerlink" href="#design-trade-offs" title="Permalink to this headline">¶</a></h3>
<div class="section" id="advantages">
<h4><a class="toc-backref" href="#id14">Advantages:</a><a class="headerlink" href="#advantages" title="Permalink to this headline">¶</a></h4>
<blockquote>
<div><ul class="simple">
<li><p>Builder allows graph construction code to be reused for DDG and PDG.</p></li>
<li><p>Builder allows us to create DDG and PDG as separate graphs.</p></li>
<li><p>DDG nodes and edges are completely disjoint from PDG nodes and edges allowing them to change easily and independently.</p></li>
</ul>
</div></blockquote>
</div>
<div class="section" id="disadvantages">
<h4><a class="toc-backref" href="#id15">Disadvantages:</a><a class="headerlink" href="#disadvantages" title="Permalink to this headline">¶</a></h4>
<blockquote>
<div><ul class="simple">
<li><p>Builder may be perceived as over-engineering at first.</p></li>
<li><p>There are some similarities between DDG nodes and edges compared to PDG nodes and edges, but there is little reuse of the class definitions.</p>
<ul>
<li><p>This is tolerable given that the node and edge types are fairly simple and there is little code reuse opportunity anyway.</p></li>
</ul>
</li>
</ul>
</div></blockquote>
</div>
</div>
</div>
<div class="section" id="implementation-details">
<span id="id4"></span><h2><a class="toc-backref" href="#id16">Implementation Details</a><a class="headerlink" href="#implementation-details" title="Permalink to this headline">¶</a></h2>
<p>The current implementation of DDG differs slightly from the dependence
graph described in <a class="footnote-reference brackets" href="#id6" id="id5">1</a> in the following ways:</p>
<blockquote>
<div><ol class="arabic simple">
<li><p>The graph nodes in the paper represent three main program components, namely <em>assignment statements</em>, <em>for loop headers</em> and <em>while loop headers</em>. In this implementation, DDG nodes naturally represent LLVM IR instructions. An assignment statement in this implementation typically involves a node representing the <code class="docutils literal notranslate"><span class="pre">store</span></code> instruction along with a number of individual nodes computing the right-hand-side of the assignment that connect to the <code class="docutils literal notranslate"><span class="pre">store</span></code> 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 <code class="docutils literal notranslate"><span class="pre">LoopAnalysis</span></code>.</p></li>
<li><p>The paper describes five types of dependency edges between nodes namely <em>loop dependency</em>, <em>flow-</em>, <em>anti-</em>, <em>output-</em>, and <em>input-</em> dependencies. In this implementation <em>memory</em> edges represent the <em>flow-</em>, <em>anti-</em>, <em>output-</em>, and <em>input-</em> dependencies. However, <em>loop dependencies</em> 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.</p></li>
<li><p>The paper describes two types of pi-blocks; <em>recurrences</em> whose bodies are SCCs and <em>IN</em> nodes whose bodies are not part of any SCC. In this implementation, pi-blocks are only created for <em>recurrences</em>. <em>IN</em> nodes remain as simple DDG nodes in the graph.</p></li>
</ol>
</div></blockquote>
<div class="section" id="references">
<h3><a class="toc-backref" href="#id17">References</a><a class="headerlink" href="#references" title="Permalink to this headline">¶</a></h3>
<dl class="footnote brackets">
<dt class="label" id="id6"><span class="brackets">1</span><span class="fn-backref">(<a href="#id1">1</a>,<a href="#id3">2</a>,<a href="#id5">3</a>)</span></dt>
<dd><p>“D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe (1981). DEPENDENCE GRAPHS AND COMPILER OPTIMIZATIONS.”</p>
</dd>
<dt class="label" id="id7"><span class="brackets"><a class="fn-backref" href="#id2">2</a></span></dt>
<dd><p>“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.”</p>
</dd>
</dl>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="../ExceptionHandling.html" title="Exception Handling in LLVM"
>next</a> |</li>
<li class="right" >
<a href="../Coroutines.html" title="Coroutines in LLVM"
>previous</a> |</li>
<li><a href="https://llvm.org/">LLVM Home</a> | </li>
<li><a href="../index.html">Documentation</a>»</li>
<li class="nav-item nav-item-1"><a href="../Reference.html" >Reference</a> »</li>
<li class="nav-item nav-item-this"><a href="">Dependence Graphs in LLVM</a></li>
</ul>
</div>
<div class="footer" role="contentinfo">
© Copyright 2003-2021, LLVM Project.
Last updated on 2021-09-18.
Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 3.5.4.
</div>
</body>
</html>
|
