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
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
|
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Code Transformation Metadata — 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="Type Metadata" href="TypeMetadata.html" />
<link rel="prev" title="test-suite Makefile Guide (deprecated)" href="TestSuiteMakefileGuide.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="TypeMetadata.html" title="Type Metadata"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="TestSuiteMakefileGuide.html" title="test-suite Makefile Guide (deprecated)"
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="">Code Transformation Metadata</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/TransformMetadata.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="code-transformation-metadata">
<span id="transformation-metadata"></span><h1>Code Transformation Metadata<a class="headerlink" href="#code-transformation-metadata" title="Permalink to this headline">¶</a></h1>
<div class="contents local topic" id="contents">
<ul class="simple">
<li><p><a class="reference internal" href="#overview" id="id1">Overview</a></p></li>
<li><p><a class="reference internal" href="#metadata-on-loops" id="id2">Metadata on Loops</a></p></li>
<li><p><a class="reference internal" href="#transformation-metadata-structure" id="id3">Transformation Metadata Structure</a></p></li>
<li><p><a class="reference internal" href="#pass-specific-transformation-metadata" id="id4">Pass-Specific Transformation Metadata</a></p>
<ul>
<li><p><a class="reference internal" href="#loop-vectorization-and-interleaving" id="id5">Loop Vectorization and Interleaving</a></p></li>
<li><p><a class="reference internal" href="#loop-unrolling" id="id6">Loop Unrolling</a></p></li>
<li><p><a class="reference internal" href="#unroll-and-jam" id="id7">Unroll-And-Jam</a></p></li>
<li><p><a class="reference internal" href="#loop-distribution" id="id8">Loop Distribution</a></p></li>
<li><p><a class="reference internal" href="#versioning-licm" id="id9">Versioning LICM</a></p></li>
<li><p><a class="reference internal" href="#loop-interchange" id="id10">Loop Interchange</a></p></li>
</ul>
</li>
<li><p><a class="reference internal" href="#ambiguous-transformation-order" id="id11">Ambiguous Transformation Order</a></p></li>
<li><p><a class="reference internal" href="#leftover-transformations" id="id12">Leftover Transformations</a></p></li>
</ul>
</div>
<div class="section" id="overview">
<h2><a class="toc-backref" href="#id1">Overview</a><a class="headerlink" href="#overview" title="Permalink to this headline">¶</a></h2>
<p>LLVM transformation passes can be controlled by attaching metadata to
the code to transform. By default, transformation passes use heuristics
to determine whether or not to perform transformations, and when doing
so, other details of how the transformations are applied (e.g., which
vectorization factor to select).
Unless the optimizer is otherwise directed, transformations are applied
conservatively. This conservatism generally allows the optimizer to
avoid unprofitable transformations, but in practice, this results in the
optimizer not applying transformations that would be highly profitable.</p>
<p>Frontends can give additional hints to LLVM passes on which
transformations they should apply. This can be additional knowledge that
cannot be derived from the emitted IR, or directives passed from the
user/programmer. OpenMP pragmas are an example of the latter.</p>
<p>If any such metadata is dropped from the program, the code’s semantics
must not change.</p>
</div>
<div class="section" id="metadata-on-loops">
<h2><a class="toc-backref" href="#id2">Metadata on Loops</a><a class="headerlink" href="#metadata-on-loops" title="Permalink to this headline">¶</a></h2>
<p>Attributes can be attached to loops as described in <a class="reference internal" href="LangRef.html#llvm-loop"><span class="std std-ref">‘llvm.loop’</span></a>.
Attributes can describe properties of the loop, disable transformations,
force specific transformations and set transformation options.</p>
<p>Because metadata nodes are immutable (with the exception of
<code class="docutils literal notranslate"><span class="pre">MDNode::replaceOperandWith</span></code> which is dangerous to use on uniqued
metadata), in order to add or remove a loop attributes, a new <code class="docutils literal notranslate"><span class="pre">MDNode</span></code>
must be created and assigned as the new <code class="docutils literal notranslate"><span class="pre">llvm.loop</span></code> metadata. Any
connection between the old <code class="docutils literal notranslate"><span class="pre">MDNode</span></code> and the loop is lost. The
<code class="docutils literal notranslate"><span class="pre">llvm.loop</span></code> node is also used as LoopID (<code class="docutils literal notranslate"><span class="pre">Loop::getLoopID()</span></code>), i.e.
the loop effectively gets a new identifier. For instance,
<code class="docutils literal notranslate"><span class="pre">llvm.mem.parallel_loop_access</span></code> references the LoopID. Therefore, if
the parallel access property is to be preserved after adding/removing
loop attributes, any <code class="docutils literal notranslate"><span class="pre">llvm.mem.parallel_loop_access</span></code> reference must be
updated to the new LoopID.</p>
</div>
<div class="section" id="transformation-metadata-structure">
<h2><a class="toc-backref" href="#id3">Transformation Metadata Structure</a><a class="headerlink" href="#transformation-metadata-structure" title="Permalink to this headline">¶</a></h2>
<p>Some attributes describe code transformations (unrolling, vectorizing,
loop distribution, etc.). They can either be a hint to the optimizer
that a transformation might be beneficial, instruction to use a specific
option, , or convey a specific request from the user (such as
<code class="docutils literal notranslate"><span class="pre">#pragma</span> <span class="pre">clang</span> <span class="pre">loop</span></code> or <code class="docutils literal notranslate"><span class="pre">#pragma</span> <span class="pre">omp</span> <span class="pre">simd</span></code>).</p>
<p>If a transformation is forced but cannot be carried-out for any reason,
an optimization-missed warning must be emitted. Semantic information
such as a transformation being safe (e.g.
<code class="docutils literal notranslate"><span class="pre">llvm.mem.parallel_loop_access</span></code>) can be unused by the optimizer
without generating a warning.</p>
<p>Unless explicitly disabled, any optimization pass may heuristically
determine whether a transformation is beneficial and apply it. If
metadata for another transformation was specified, applying a different
transformation before it might be inadvertent due to being applied on a
different loop or the loop not existing anymore. To avoid having to
explicitly disable an unknown number of passes, the attribute
<code class="docutils literal notranslate"><span class="pre">llvm.loop.disable_nonforced</span></code> disables all optional, high-level,
restructuring transformations.</p>
<p>The following example avoids the loop being altered before being
vectorized, for instance being unrolled.</p>
<div class="highlight-llvm notranslate"><div class="highlight"><pre><span></span> <span class="k">br</span> <span class="k">i1</span> <span class="nv">%exitcond</span><span class="p">,</span> <span class="k">label</span> <span class="nv">%for.exit</span><span class="p">,</span> <span class="k">label</span> <span class="nv">%for.header</span><span class="p">,</span> <span class="nv">!llvm.loop</span> <span class="nv nv-Anonymous">!0</span>
<span class="p">...</span>
<span class="nv nv-Anonymous">!0</span> <span class="p">=</span> <span class="k">distinct</span> <span class="p">!{</span><span class="nv nv-Anonymous">!0</span><span class="p">,</span> <span class="nv nv-Anonymous">!1</span><span class="p">,</span> <span class="nv nv-Anonymous">!2</span><span class="p">}</span>
<span class="nv nv-Anonymous">!1</span> <span class="p">=</span> <span class="p">!{</span><span class="nv">!"llvm.loop.vectorize.enable"</span><span class="p">,</span> <span class="k">i1</span> <span class="k">true</span><span class="p">}</span>
<span class="nv nv-Anonymous">!2</span> <span class="p">=</span> <span class="p">!{</span><span class="nv">!"llvm.loop.disable_nonforced"</span><span class="p">}</span>
</pre></div>
</div>
<p>After a transformation is applied, follow-up attributes are set on the
transformed and/or new loop(s). This allows additional attributes
including followup-transformations to be specified. Specifying multiple
transformations in the same metadata node is possible for compatibility
reasons, but their execution order is undefined. For instance, when
<code class="docutils literal notranslate"><span class="pre">llvm.loop.vectorize.enable</span></code> and <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.enable</span></code> are
specified at the same time, unrolling may occur either before or after
vectorization.</p>
<p>As an example, the following instructs a loop to be vectorized and only
then unrolled.</p>
<div class="highlight-llvm notranslate"><div class="highlight"><pre><span></span><span class="nv nv-Anonymous">!0</span> <span class="p">=</span> <span class="k">distinct</span> <span class="p">!{</span><span class="nv nv-Anonymous">!0</span><span class="p">,</span> <span class="nv nv-Anonymous">!1</span><span class="p">,</span> <span class="nv nv-Anonymous">!2</span><span class="p">,</span> <span class="nv nv-Anonymous">!3</span><span class="p">}</span>
<span class="nv nv-Anonymous">!1</span> <span class="p">=</span> <span class="p">!{</span><span class="nv">!"llvm.loop.vectorize.enable"</span><span class="p">,</span> <span class="k">i1</span> <span class="k">true</span><span class="p">}</span>
<span class="nv nv-Anonymous">!2</span> <span class="p">=</span> <span class="p">!{</span><span class="nv">!"llvm.loop.disable_nonforced"</span><span class="p">}</span>
<span class="nv nv-Anonymous">!3</span> <span class="p">=</span> <span class="p">!{</span><span class="nv">!"llvm.loop.vectorize.followup_vectorized"</span><span class="p">,</span> <span class="p">!{</span><span class="s">"llvm.loop.unroll.enable"</span><span class="p">}}</span>
</pre></div>
</div>
<p>If, and only if, no followup is specified, the pass may add attributes itself.
For instance, the vectorizer adds a <code class="docutils literal notranslate"><span class="pre">llvm.loop.isvectorized</span></code> attribute and
all attributes from the original loop excluding its loop vectorizer
attributes. To avoid this, an empty followup attribute can be used, e.g.</p>
<div class="highlight-llvm notranslate"><div class="highlight"><pre><span></span><span class="nv nv-Anonymous">!3</span> <span class="p">=</span> <span class="p">!{</span><span class="nv">!"llvm.loop.vectorize.followup_vectorized"</span><span class="p">}</span>
</pre></div>
</div>
<p>The followup attributes of a transformation that cannot be applied will
never be added to a loop and are therefore effectively ignored. This means
that any followup-transformation in such attributes requires that its
prior transformations are applied before the followup-transformation.
The user should receive a warning about the first transformation in the
transformation chain that could not be applied if it a forced
transformation. All following transformations are skipped.</p>
</div>
<div class="section" id="pass-specific-transformation-metadata">
<h2><a class="toc-backref" href="#id4">Pass-Specific Transformation Metadata</a><a class="headerlink" href="#pass-specific-transformation-metadata" title="Permalink to this headline">¶</a></h2>
<p>Transformation options are specific to each transformation. In the
following, we present the model for each LLVM loop optimization pass and
the metadata to influence them.</p>
<div class="section" id="loop-vectorization-and-interleaving">
<h3><a class="toc-backref" href="#id5">Loop Vectorization and Interleaving</a><a class="headerlink" href="#loop-vectorization-and-interleaving" title="Permalink to this headline">¶</a></h3>
<p>Loop vectorization and interleaving is interpreted as a single
transformation. It is interpreted as forced if
<code class="docutils literal notranslate"><span class="pre">!{"llvm.loop.vectorize.enable",</span> <span class="pre">i1</span> <span class="pre">true}</span></code> is set.</p>
<p>Assuming the pre-vectorization loop is</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">0</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="mi">1</span><span class="p">)</span> <span class="c1">// original loop</span>
<span class="n">Stmt</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
</pre></div>
</div>
<p>then the code after vectorization will be approximately (assuming an
SIMD width of 4):</p>
<div class="highlight-c notranslate"><div class="highlight"><pre><span></span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="k">if</span> <span class="p">(</span><span class="n">rtc</span><span class="p">)</span> <span class="p">{</span>
<span class="k">for</span> <span class="p">(;</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">3</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="mi">4</span><span class="p">)</span> <span class="c1">// vectorized/interleaved loop</span>
<span class="n">Stmt</span><span class="p">(</span><span class="nl">i</span><span class="p">:</span><span class="n">i</span><span class="o">+</span><span class="mi">3</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">for</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="mi">1</span><span class="p">)</span> <span class="c1">// epilogue loop</span>
<span class="n">Stmt</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
</pre></div>
</div>
<p>where <code class="docutils literal notranslate"><span class="pre">rtc</span></code> is a generated runtime check.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.vectorize.followup_vectorized</span></code> will set the attributes for
the vectorized loop. If not specified, <code class="docutils literal notranslate"><span class="pre">llvm.loop.isvectorized</span></code> is
combined with the original loop’s attributes to avoid it being
vectorized multiple times.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.vectorize.followup_epilogue</span></code> will set the attributes for
the remainder loop. If not specified, it will have the original loop’s
attributes combined with <code class="docutils literal notranslate"><span class="pre">llvm.loop.isvectorized</span></code> and
<code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.runtime.disable</span></code> (unless the original loop already
has unroll metadata).</p>
<p>The attributes specified by <code class="docutils literal notranslate"><span class="pre">llvm.loop.vectorize.followup_all</span></code> are
added to both loops.</p>
<p>When using a follow-up attribute, it replaces any automatically deduced
attributes for the generated loop in question. Therefore it is
recommended to add <code class="docutils literal notranslate"><span class="pre">llvm.loop.isvectorized</span></code> to
<code class="docutils literal notranslate"><span class="pre">llvm.loop.vectorize.followup_all</span></code> which avoids that the loop
vectorizer tries to optimize the loops again.</p>
</div>
<div class="section" id="loop-unrolling">
<h3><a class="toc-backref" href="#id6">Loop Unrolling</a><a class="headerlink" href="#loop-unrolling" title="Permalink to this headline">¶</a></h3>
<p>Unrolling is interpreted as forced any <code class="docutils literal notranslate"><span class="pre">!{!"llvm.loop.unroll.enable"}</span></code>
metadata or option (<code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.count</span></code>, <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.full</span></code>)
is present. Unrolling can be full unrolling, partial unrolling of a loop
with constant trip count or runtime unrolling of a loop with a trip
count unknown at compile-time.</p>
<p>If the loop has been unrolled fully, there is no followup-loop. For
partial/runtime unrolling, the original loop of</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">0</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="mi">1</span><span class="p">)</span> <span class="c1">// original loop</span>
<span class="n">Stmt</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
</pre></div>
</div>
<p>is transformed into (using an unroll factor of 4):</p>
<div class="highlight-c notranslate"><div class="highlight"><pre><span></span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(;</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">3</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="mi">4</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// unrolled loop</span>
<span class="n">Stmt</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
<span class="n">Stmt</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
<span class="n">Stmt</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">2</span><span class="p">);</span>
<span class="n">Stmt</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">3</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">for</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="mi">1</span><span class="p">)</span> <span class="c1">// remainder loop</span>
<span class="n">Stmt</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
</pre></div>
</div>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.followup_unrolled</span></code> will set the loop attributes of
the unrolled loop. If not specified, the attributes of the original loop
without the <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.*</span></code> attributes are copied and
<code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.disable</span></code> added to it.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.followup_remainder</span></code> defines the attributes of the
remainder loop. If not specified the remainder loop will have no
attributes. The remainder loop might not be present due to being fully
unrolled in which case this attribute has no effect.</p>
<p>Attributes defined in <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.followup_all</span></code> are added to the
unrolled and remainder loops.</p>
<p>To avoid that the partially unrolled loop is unrolled again, it is
recommended to add <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.disable</span></code> to
<code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.followup_all</span></code>. If no follow-up attribute specified
for a generated loop, it is added automatically.</p>
</div>
<div class="section" id="unroll-and-jam">
<h3><a class="toc-backref" href="#id7">Unroll-And-Jam</a><a class="headerlink" href="#unroll-and-jam" title="Permalink to this headline">¶</a></h3>
<p>Unroll-and-jam uses the following transformation model (here with an
unroll factor if 2). Currently, it does not support a fallback version
when the transformation is unsafe.</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">0</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="mi">1</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// original outer loop</span>
<span class="n">Fore</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">+=</span><span class="mi">1</span><span class="p">)</span> <span class="c1">// original inner loop</span>
<span class="n">SubLoop</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">);</span>
<span class="n">Aft</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
<span class="p">}</span>
</pre></div>
</div>
<div class="highlight-c notranslate"><div class="highlight"><pre><span></span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(;</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</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="mi">2</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// unrolled outer loop</span>
<span class="n">Fore</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
<span class="n">Fore</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">+=</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// unrolled inner loop</span>
<span class="n">SubLoop</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">);</span>
<span class="n">SubLoop</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="p">);</span>
<span class="p">}</span>
<span class="n">Aft</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
<span class="n">Aft</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">for</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="mi">1</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// remainder outer loop</span>
<span class="n">Fore</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">+=</span><span class="mi">1</span><span class="p">)</span> <span class="c1">// remainder inner loop</span>
<span class="n">SubLoop</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">);</span>
<span class="n">Aft</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
<span class="p">}</span>
</pre></div>
</div>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll_and_jam.followup_outer</span></code> will set the loop attributes
of the unrolled outer loop. If not specified, the attributes of the
original outer loop without the <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.*</span></code> attributes are
copied and <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.disable</span></code> added to it.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll_and_jam.followup_inner</span></code> will set the loop attributes
of the unrolled inner loop. If not specified, the attributes of the
original inner loop are used unchanged.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll_and_jam.followup_remainder_outer</span></code> sets the loop
attributes of the outer remainder loop. If not specified it will not
have any attributes. The remainder loop might not be present due to
being fully unrolled.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll_and_jam.followup_remainder_inner</span></code> sets the loop
attributes of the inner remainder loop. If not specified it will have
the attributes of the original inner loop. It the outer remainder loop
is unrolled, the inner remainder loop might be present multiple times.</p>
<p>Attributes defined in <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll_and_jam.followup_all</span></code> are
added to all of the aforementioned output loops.</p>
<p>To avoid that the unrolled loop is unrolled again, it is
recommended to add <code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll.disable</span></code> to
<code class="docutils literal notranslate"><span class="pre">llvm.loop.unroll_and_jam.followup_all</span></code>. It suppresses unroll-and-jam
as well as an additional inner loop unrolling. If no follow-up
attribute specified for a generated loop, it is added automatically.</p>
</div>
<div class="section" id="loop-distribution">
<h3><a class="toc-backref" href="#id8">Loop Distribution</a><a class="headerlink" href="#loop-distribution" title="Permalink to this headline">¶</a></h3>
<p>The LoopDistribution pass tries to separate vectorizable parts of a loop
from the non-vectorizable part (which otherwise would make the entire
loop non-vectorizable). Conceptually, it transforms a loop such as</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="mi">1</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// original loop</span>
<span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</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="mi">2</span> <span class="o">+</span> <span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">];</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="mi">3</span> <span class="o">+</span> <span class="n">C</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
<span class="p">}</span>
</pre></div>
</div>
<p>into the following code:</p>
<div class="highlight-c notranslate"><div class="highlight"><pre><span></span><span class="k">if</span> <span class="p">(</span><span class="n">rtc</span><span class="p">)</span> <span class="p">{</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="mi">1</span><span class="p">)</span> <span class="c1">// coincident loop</span>
<span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</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="mi">1</span><span class="p">)</span> <span class="c1">// coincident loop</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="mi">2</span> <span class="o">+</span> <span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">];</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="mi">1</span><span class="p">)</span> <span class="c1">// sequential loop</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="mi">3</span> <span class="o">+</span> <span class="n">C</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
<span class="p">}</span> <span class="k">else</span> <span class="p">{</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="mi">1</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// fallback loop</span>
<span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</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="mi">2</span> <span class="o">+</span> <span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">];</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="mi">3</span> <span class="o">+</span> <span class="n">C</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
<span class="p">}</span>
<span class="p">}</span>
</pre></div>
</div>
<p>where <code class="docutils literal notranslate"><span class="pre">rtc</span></code> is a generated runtime check.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.distribute.followup_coincident</span></code> sets the loop attributes of
all loops without loop-carried dependencies (i.e. vectorizable loops).
There might be more than one such loops. If not defined, the loops will
inherit the original loop’s attributes.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.distribute.followup_sequential</span></code> sets the loop attributes of the
loop with potentially unsafe dependencies. There should be at most one
such loop. If not defined, the loop will inherit the original loop’s
attributes.</p>
<p><code class="docutils literal notranslate"><span class="pre">llvm.loop.distribute.followup_fallback</span></code> defines the loop attributes
for the fallback loop, which is a copy of the original loop for when
loop versioning is required. If undefined, the fallback loop inherits
all attributes from the original loop.</p>
<p>Attributes defined in <code class="docutils literal notranslate"><span class="pre">llvm.loop.distribute.followup_all</span></code> are added to
all of the aforementioned output loops.</p>
<p>It is recommended to add <code class="docutils literal notranslate"><span class="pre">llvm.loop.disable_nonforced</span></code> to
<code class="docutils literal notranslate"><span class="pre">llvm.loop.distribute.followup_fallback</span></code>. This avoids that the
fallback version (which is likely never executed) is further optimized
which would increase the code size.</p>
</div>
<div class="section" id="versioning-licm">
<h3><a class="toc-backref" href="#id9">Versioning LICM</a><a class="headerlink" href="#versioning-licm" title="Permalink to this headline">¶</a></h3>
<p>The pass hoists code out of loops that are only loop-invariant when
dynamic conditions apply. For instance, it transforms the loop</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">0</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="mi">1</span><span class="p">)</span> <span class="c1">// original loop</span>
<span class="n">A</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="mi">0</span><span class="p">];</span>
</pre></div>
</div>
<p>into:</p>
<div class="highlight-c notranslate"><div class="highlight"><pre><span></span><span class="k">if</span> <span class="p">(</span><span class="n">rtc</span><span class="p">)</span> <span class="p">{</span>
<span class="k">auto</span> <span class="n">b</span> <span class="o">=</span> <span class="n">B</span><span class="p">[</span><span class="mi">0</span><span class="p">];</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">0</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="mi">1</span><span class="p">)</span> <span class="c1">// versioned loop</span>
<span class="n">A</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="p">}</span> <span class="k">else</span> <span class="p">{</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">0</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="mi">1</span><span class="p">)</span> <span class="c1">// unversioned loop</span>
<span class="n">A</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="mi">0</span><span class="p">];</span>
<span class="p">}</span>
</pre></div>
</div>
<p>The runtime condition (<code class="docutils literal notranslate"><span class="pre">rtc</span></code>) checks that the array <code class="docutils literal notranslate"><span class="pre">A</span></code> and the
element <cite>B[0]</cite> do not alias.</p>
<p>Currently, this transformation does not support followup-attributes.</p>
</div>
<div class="section" id="loop-interchange">
<h3><a class="toc-backref" href="#id10">Loop Interchange</a><a class="headerlink" href="#loop-interchange" title="Permalink to this headline">¶</a></h3>
<p>Currently, the <code class="docutils literal notranslate"><span class="pre">LoopInterchange</span></code> pass does not use any metadata.</p>
</div>
</div>
<div class="section" id="ambiguous-transformation-order">
<h2><a class="toc-backref" href="#id11">Ambiguous Transformation Order</a><a class="headerlink" href="#ambiguous-transformation-order" title="Permalink to this headline">¶</a></h2>
<p>If there multiple transformations defined, the order in which they are
executed depends on the order in LLVM’s pass pipeline, which is subject
to change. The default optimization pipeline (anything higher than
<code class="docutils literal notranslate"><span class="pre">-O0</span></code>) has the following order.</p>
<p>When using the legacy pass manager:</p>
<blockquote>
<div><ul class="simple">
<li><p>LoopInterchange (if enabled)</p></li>
<li><p>SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)</p></li>
<li><p>VersioningLICM (if enabled)</p></li>
<li><p>LoopDistribute</p></li>
<li><p>LoopVectorizer</p></li>
<li><p>LoopUnrollAndJam (if enabled)</p></li>
<li><p>LoopUnroll (partial and runtime unrolling)</p></li>
</ul>
</div></blockquote>
<p>When using the legacy pass manager with LTO:</p>
<blockquote>
<div><ul class="simple">
<li><p>LoopInterchange (if enabled)</p></li>
<li><p>SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)</p></li>
<li><p>LoopVectorizer</p></li>
<li><p>LoopUnroll (partial and runtime unrolling)</p></li>
</ul>
</div></blockquote>
<p>When using the new pass manager:</p>
<blockquote>
<div><ul class="simple">
<li><p>SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)</p></li>
<li><p>LoopDistribute</p></li>
<li><p>LoopVectorizer</p></li>
<li><p>LoopUnrollAndJam (if enabled)</p></li>
<li><p>LoopUnroll (partial and runtime unrolling)</p></li>
</ul>
</div></blockquote>
</div>
<div class="section" id="leftover-transformations">
<h2><a class="toc-backref" href="#id12">Leftover Transformations</a><a class="headerlink" href="#leftover-transformations" title="Permalink to this headline">¶</a></h2>
<p>Forced transformations that have not been applied after the last
transformation pass should be reported to the user. The transformation
passes themselves cannot be responsible for this reporting because they
might not be in the pipeline, there might be multiple passes able to
apply a transformation (e.g. <code class="docutils literal notranslate"><span class="pre">LoopInterchange</span></code> and Polly) or a
transformation attribute may be ‘hidden’ inside another passes’ followup
attribute.</p>
<p>The pass <code class="docutils literal notranslate"><span class="pre">-transform-warning</span></code> (<code class="docutils literal notranslate"><span class="pre">WarnMissedTransformationsPass</span></code>)
emits such warnings. It should be placed after the last transformation
pass.</p>
<p>The current pass pipeline has a fixed order in which transformations
passes are executed. A transformation can be in the followup of a pass
that is executed later and thus leftover. For instance, a loop nest
cannot be distributed and then interchanged with the current pass
pipeline. The loop distribution will execute, but there is no loop
interchange pass following such that any loop interchange metadata will
be ignored. The <code class="docutils literal notranslate"><span class="pre">-transform-warning</span></code> should emit a warning in this
case.</p>
<p>Future versions of LLVM may fix this by executing transformations using
a dynamic ordering.</p>
</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="TypeMetadata.html" title="Type Metadata"
>next</a> |</li>
<li class="right" >
<a href="TestSuiteMakefileGuide.html" title="test-suite Makefile Guide (deprecated)"
>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="">Code Transformation Metadata</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>
|
