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
|
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Vectorization Plan — 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="Writing an LLVM Pass" href="../WritingAnLLVMPass.html" />
<link rel="prev" title="Auto-Vectorization in LLVM" href="../Vectorizers.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="../WritingAnLLVMPass.html" title="Writing an LLVM Pass"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="../Vectorizers.html" title="Auto-Vectorization 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="../UserGuides.html" >User Guides</a> »</li>
<li class="nav-item nav-item-2"><a href="../Vectorizers.html" accesskey="U">Auto-Vectorization in LLVM</a> »</li>
<li class="nav-item nav-item-this"><a href="">Vectorization Plan</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/Proposals/VectorizationPlan.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="vectorization-plan">
<h1>Vectorization Plan<a class="headerlink" href="#vectorization-plan" title="Permalink to this headline">¶</a></h1>
<div class="contents local topic" id="contents">
<ul class="simple">
<li><p><a class="reference internal" href="#abstract" id="id20">Abstract</a></p></li>
<li><p><a class="reference internal" href="#high-level-design" id="id21">High-level Design</a></p>
<ul>
<li><p><a class="reference internal" href="#vectorization-workflow" id="id22">Vectorization Workflow</a></p></li>
<li><p><a class="reference internal" href="#design-guidelines" id="id23">Design Guidelines</a></p></li>
</ul>
</li>
<li><p><a class="reference internal" href="#definitions" id="id24">Definitions</a></p></li>
<li><p><a class="reference internal" href="#the-planning-process-and-vplan-roadmap" id="id25">The Planning Process and VPlan Roadmap</a></p>
<ul>
<li><p><a class="reference internal" href="#related-llvm-components" id="id26">Related LLVM components</a></p></li>
<li><p><a class="reference internal" href="#references" id="id27">References</a></p></li>
</ul>
</li>
</ul>
</div>
<div class="section" id="abstract">
<h2><a class="toc-backref" href="#id20">Abstract</a><a class="headerlink" href="#abstract" title="Permalink to this headline">¶</a></h2>
<p>The vectorization transformation can be rather complicated, involving several
potential alternatives, especially for outer-loops <a class="footnote-reference brackets" href="#id11" id="id1">1</a> but also possibly for
innermost loops. These alternatives may have significant performance impact,
both positive and negative. A cost model is therefore employed to identify the
best alternative, including the alternative of avoiding any transformation
altogether.</p>
<p>The Vectorization Plan is an explicit model for describing vectorization
candidates. It serves for both optimizing candidates including estimating their
cost reliably, and for performing their final translation into IR. This
facilitates dealing with multiple vectorization candidates.</p>
</div>
<div class="section" id="high-level-design">
<h2><a class="toc-backref" href="#id21">High-level Design</a><a class="headerlink" href="#high-level-design" title="Permalink to this headline">¶</a></h2>
<div class="section" id="vectorization-workflow">
<h3><a class="toc-backref" href="#id22">Vectorization Workflow</a><a class="headerlink" href="#vectorization-workflow" title="Permalink to this headline">¶</a></h3>
<p>VPlan-based vectorization involves three major steps, taking a “scenario-based
approach” to vectorization planning:</p>
<ol class="arabic simple">
<li><p>Legal Step: check if a loop can be legally vectorized; encode constraints and
artifacts if so.</p></li>
<li><p>Plan Step:</p>
<ol class="loweralpha simple">
<li><p>Build initial VPlans following the constraints and decisions taken by
Legal Step 1, and compute their cost.</p></li>
<li><p>Apply optimizations to the VPlans, possibly forking additional VPlans.
Prune sub-optimal VPlans having relatively high cost.</p></li>
</ol>
</li>
<li><p>Execute Step: materialize the best VPlan. Note that this is the only step
that modifies the IR.</p></li>
</ol>
</div>
<div class="section" id="design-guidelines">
<h3><a class="toc-backref" href="#id23">Design Guidelines</a><a class="headerlink" href="#design-guidelines" title="Permalink to this headline">¶</a></h3>
<p>In what follows, the term “input IR” refers to code that is fed into the
vectorizer whereas the term “output IR” refers to code that is generated by the
vectorizer. The output IR contains code that has been vectorized or “widened”
according to a loop Vectorization Factor (VF), and/or loop unroll-and-jammed
according to an Unroll Factor (UF).
The design of VPlan follows several high-level guidelines:</p>
<ol class="arabic simple">
<li><p>Analysis-like: building and manipulating VPlans must not modify the input IR.
In particular, if the best option is not to vectorize at all, the
vectorization process terminates before reaching Step 3, and compilation
should proceed as if VPlans had not been built.</p></li>
<li><p>Align Cost & Execute: each VPlan must support both estimating the cost and
generating the output IR code, such that the cost estimation evaluates the
to-be-generated code reliably.</p></li>
<li><p>Support vectorizing additional constructs:</p>
<ol class="loweralpha simple">
<li><p>Outer-loop vectorization. In particular, VPlan must be able to model the
control-flow of the output IR which may include multiple basic-blocks and
nested loops.</p></li>
<li><p>SLP vectorization.</p></li>
<li><p>Combinations of the above, including nested vectorization: vectorizing
both an inner loop and an outer-loop at the same time (each with its own
VF and UF), mixed vectorization: vectorizing a loop with SLP patterns
inside <a class="footnote-reference brackets" href="#id14" id="id2">4</a>, (re)vectorizing input IR containing vector code.</p></li>
<li><p>Function vectorization <a class="footnote-reference brackets" href="#id12" id="id3">2</a>.</p></li>
</ol>
</li>
<li><p>Support multiple candidates efficiently. In particular, similar candidates
related to a range of possible VF’s and UF’s must be represented efficiently.
Potential versioning needs to be supported efficiently.</p></li>
<li><p>Support vectorizing idioms, such as interleaved groups of strided loads or
stores. This is achieved by modeling a sequence of output instructions using
a “Recipe”, which is responsible for computing its cost and generating its
code.</p></li>
<li><p>Encapsulate Single-Entry Single-Exit regions (SESE). During vectorization
such regions may need to be, for example, predicated and linearized, or
replicated VF*UF times to handle scalarized and predicated instructions.
Innerloops are also modelled as SESE regions.</p></li>
<li><p>Support instruction-level analysis and transformation, as part of Planning
Step 2.b: During vectorization instructions may need to be traversed, moved,
replaced by other instructions or be created. For example, vector idiom
detection and formation involves searching for and optimizing instruction
patterns.</p></li>
</ol>
</div>
</div>
<div class="section" id="definitions">
<h2><a class="toc-backref" href="#id24">Definitions</a><a class="headerlink" href="#definitions" title="Permalink to this headline">¶</a></h2>
<p>The low-level design of VPlan comprises of the following classes.</p>
<dl class="field-list simple">
<dt class="field-odd">LoopVectorizationPlanner</dt>
<dd class="field-odd"><p>A LoopVectorizationPlanner is designed to handle the vectorization of a loop
or a loop nest. It can construct, optimize and discard one or more VPlans,
each VPlan modelling a distinct way to vectorize the loop or the loop nest.
Once the best VPlan is determined, including the best VF and UF, this VPlan
drives the generation of output IR.</p>
</dd>
<dt class="field-even">VPlan</dt>
<dd class="field-even"><p>A model of a vectorized candidate for a given input IR loop or loop nest. This
candidate is represented using a Hierarchical CFG. VPlan supports estimating
the cost and driving the generation of the output IR code it represents.</p>
</dd>
<dt class="field-odd">Hierarchical CFG</dt>
<dd class="field-odd"><p>A control-flow graph whose nodes are basic-blocks or Hierarchical CFG’s. The
Hierarchical CFG data structure is similar to the Tile Tree <a class="footnote-reference brackets" href="#id15" id="id4">5</a>, where
cross-Tile edges are lifted to connect Tiles instead of the original
basic-blocks as in Sharir <a class="footnote-reference brackets" href="#id16" id="id5">6</a>, promoting the Tile encapsulation. The terms
Region and Block are used rather than Tile <a class="footnote-reference brackets" href="#id15" id="id6">5</a> to avoid confusion with loop
tiling.</p>
</dd>
<dt class="field-even">VPBlockBase</dt>
<dd class="field-even"><p>The building block of the Hierarchical CFG. A pure-virtual base-class of
VPBasicBlock and VPRegionBlock, see below. VPBlockBase models the hierarchical
control-flow relations with other VPBlocks. Note that in contrast to the IR
BasicBlock, a VPBlockBase models its control-flow successors and predecessors
directly, rather than through a Terminator branch or through predecessor
branches that “use” the VPBlockBase.</p>
</dd>
<dt class="field-odd">VPBasicBlock</dt>
<dd class="field-odd"><p>VPBasicBlock is a subclass of VPBlockBase, and serves as the leaves of the
Hierarchical CFG. It represents a sequence of output IR instructions that will
appear consecutively in an output IR basic-block. The instructions of this
basic-block originate from one or more VPBasicBlocks. VPBasicBlock holds a
sequence of zero or more VPRecipes that model the cost and generation of the
output IR instructions.</p>
</dd>
<dt class="field-even">VPRegionBlock</dt>
<dd class="field-even"><p>VPRegionBlock is a subclass of VPBlockBase. It models a collection of
VPBasicBlocks and VPRegionBlocks which form a SESE subgraph of the output IR
CFG. A VPRegionBlock may indicate that its contents are to be replicated a
constant number of times when output IR is generated, effectively representing
a loop with constant trip-count that will be completely unrolled. This is used
to support scalarized and predicated instructions with a single model for
multiple candidate VF’s and UF’s.</p>
</dd>
<dt class="field-odd">VPRecipeBase</dt>
<dd class="field-odd"><p>A pure-virtual base class modeling a sequence of one or more output IR
instructions, possibly based on one or more input IR instructions. These
input IR instructions are referred to as “Ingredients” of the Recipe. A Recipe
may specify how its ingredients are to be transformed to produce the output IR
instructions; e.g., cloned once, replicated multiple times or widened
according to selected VF.</p>
</dd>
<dt class="field-even">VPValue</dt>
<dd class="field-even"><p>The base of VPlan’s def-use relations class hierarchy. When instantiated, it
models a constant or a live-in Value in VPlan. It has users, which are of type
VPUser, but no operands.</p>
</dd>
<dt class="field-odd">VPUser</dt>
<dd class="field-odd"><p>A VPUser represents an entity that uses a number of VPValues as operands.
VPUser is similar in some aspects to LLVM’s User class.</p>
</dd>
<dt class="field-even">VPDef</dt>
<dd class="field-even"><p>A VPDef represents an entity that defines zero, one or multiple VPValues.
It is used to model the fact that recipes in VPlan can define multiple
VPValues.</p>
</dd>
<dt class="field-odd">VPInstruction</dt>
<dd class="field-odd"><p>A VPInstruction is both a VPRecipe and a VPUser. It models a single
VPlan-level instruction to be generated if the VPlan is executed, including
its opcode and possibly additional characteristics. It is the basis for
writing instruction-level analyses and optimizations in VPlan as creating,
replacing or moving VPInstructions record both def-use and scheduling
decisions. VPInstructions also extend LLVM IR’s opcodes with idiomatic
operations that enrich the Vectorizer’s semantics.</p>
</dd>
<dt class="field-even">VPTransformState</dt>
<dd class="field-even"><p>Stores information used for generating output IR, passed from
LoopVectorizationPlanner to its selected VPlan for execution, and used to pass
additional information down to VPBlocks and VPRecipes.</p>
</dd>
</dl>
</div>
<div class="section" id="the-planning-process-and-vplan-roadmap">
<h2><a class="toc-backref" href="#id25">The Planning Process and VPlan Roadmap</a><a class="headerlink" href="#the-planning-process-and-vplan-roadmap" title="Permalink to this headline">¶</a></h2>
<p>Transforming the Loop Vectorizer to use VPlan follows a staged approach. First,
VPlan is used to record the final vectorization decisions, and to execute them:
the Hierarchical CFG models the planned control-flow, and Recipes capture
decisions taken inside basic-blocks. Next, VPlan will be used also as the basis
for taking these decisions, effectively turning them into a series of
VPlan-to-VPlan algorithms. Finally, VPlan will support the planning process
itself including cost-based analyses for making these decisions, to fully
support compositional and iterative decision making.</p>
<p>Some decisions are local to an instruction in the loop, such as whether to widen
it into a vector instruction or replicate it, keeping the generated instructions
in place. Other decisions, however, involve moving instructions, replacing them
with other instructions, and/or introducing new instructions. For example, a
cast may sink past a later instruction and be widened to handle first-order
recurrence; an interleave group of strided gathers or scatters may effectively
move to one place where they are replaced with shuffles and a common wide vector
load or store; new instructions may be introduced to compute masks, shuffle the
elements of vectors, and pack scalar values into vectors or vice-versa.</p>
<p>In order for VPlan to support making instruction-level decisions and analyses,
it needs to model the relevant instructions along with their def/use relations.
This too follows a staged approach: first, the new instructions that compute
masks are modeled as VPInstructions, along with their induced def/use subgraph.
This effectively models masks in VPlan, facilitating VPlan-based predication.
Next, the logic embedded within each Recipe for generating its instructions at
VPlan execution time, will instead take part in the planning process by modeling
them as VPInstructions. Finally, only logic that applies to instructions as a
group will remain in Recipes, such as interleave groups and potentially other
idiom groups having synergistic cost.</p>
<div class="section" id="related-llvm-components">
<h3><a class="toc-backref" href="#id26">Related LLVM components</a><a class="headerlink" href="#related-llvm-components" title="Permalink to this headline">¶</a></h3>
<ol class="arabic simple">
<li><p>SLP Vectorizer: one can compare the VPlan model with LLVM’s existing SLP
tree, where TSLP <a class="footnote-reference brackets" href="#id13" id="id7">3</a> adds Plan Step 2.b.</p></li>
<li><p>RegionInfo: one can compare VPlan’s H-CFG with the Region Analysis as used by
Polly <a class="footnote-reference brackets" href="#id17" id="id8">7</a>.</p></li>
<li><p>Loop Vectorizer: the Vectorization Plan aims to upgrade the infrastructure of
the Loop Vectorizer and extend it to handle outer loops <a class="footnote-reference brackets" href="#id18" id="id9">8</a>, <a class="footnote-reference brackets" href="#id19" id="id10">9</a>.</p></li>
</ol>
</div>
<div class="section" id="references">
<h3><a class="toc-backref" href="#id27">References</a><a class="headerlink" href="#references" title="Permalink to this headline">¶</a></h3>
<dl class="footnote brackets">
<dt class="label" id="id11"><span class="brackets"><a class="fn-backref" href="#id1">1</a></span></dt>
<dd><p>“Outer-loop vectorization: revisited for short SIMD architectures”, Dorit
Nuzman and Ayal Zaks, PACT 2008.</p>
</dd>
<dt class="label" id="id12"><span class="brackets"><a class="fn-backref" href="#id3">2</a></span></dt>
<dd><p>“Proposal for function vectorization and loop vectorization with function
calls”, Xinmin Tian, [<a class="reference external" href="http://lists.llvm.org/pipermail/cfe-dev/2016-March/047732.html">cfe-dev</a>].,
March 2, 2016.
See also <a class="reference external" href="https://reviews.llvm.org/D22792">review</a>.</p>
</dd>
<dt class="label" id="id13"><span class="brackets"><a class="fn-backref" href="#id7">3</a></span></dt>
<dd><p>“Throttling Automatic Vectorization: When Less is More”, Vasileios
Porpodas and Tim Jones, PACT 2015 and LLVM Developers’ Meeting 2015.</p>
</dd>
<dt class="label" id="id14"><span class="brackets"><a class="fn-backref" href="#id2">4</a></span></dt>
<dd><p>“Exploiting mixed SIMD parallelism by reducing data reorganization
overhead”, Hao Zhou and Jingling Xue, CGO 2016.</p>
</dd>
<dt class="label" id="id15"><span class="brackets">5</span><span class="fn-backref">(<a href="#id4">1</a>,<a href="#id6">2</a>)</span></dt>
<dd><p>“Register Allocation via Hierarchical Graph Coloring”, David Callahan and
Brian Koblenz, PLDI 1991</p>
</dd>
<dt class="label" id="id16"><span class="brackets"><a class="fn-backref" href="#id5">6</a></span></dt>
<dd><p>“Structural analysis: A new approach to flow analysis in optimizing
compilers”, M. Sharir, Journal of Computer Languages, Jan. 1980</p>
</dd>
<dt class="label" id="id17"><span class="brackets"><a class="fn-backref" href="#id8">7</a></span></dt>
<dd><p>“Enabling Polyhedral Optimizations in LLVM”, Tobias Grosser, Diploma
thesis, 2011.</p>
</dd>
<dt class="label" id="id18"><span class="brackets"><a class="fn-backref" href="#id9">8</a></span></dt>
<dd><p>“Introducing VPlan to the Loop Vectorizer”, Gil Rapaport and Ayal Zaks,
European LLVM Developers’ Meeting 2017.</p>
</dd>
<dt class="label" id="id19"><span class="brackets"><a class="fn-backref" href="#id10">9</a></span></dt>
<dd><p>“Extending LoopVectorizer: OpenMP4.5 SIMD and Outer Loop
Auto-Vectorization”, Intel Vectorizer Team, LLVM Developers’ Meeting 2016.</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="../WritingAnLLVMPass.html" title="Writing an LLVM Pass"
>next</a> |</li>
<li class="right" >
<a href="../Vectorizers.html" title="Auto-Vectorization 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="../UserGuides.html" >User Guides</a> »</li>
<li class="nav-item nav-item-2"><a href="../Vectorizers.html" >Auto-Vectorization in LLVM</a> »</li>
<li class="nav-item nav-item-this"><a href="">Vectorization Plan</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>
|
