Skip to content

Commit 8b9d1f3

Browse files
aniragilaniragil
committedNov 20, 2017
[LV] Model masking in VPlan, introducing VPInstructions
This patch adds a new abstraction layer to VPlan and leverages it to model the planned instructions that manipulate masks (AND, OR, NOT), introduced during predication. The new VPValue and VPUser classes model how data flows into, through and out of a VPlan, forming the vertices of a planned Def-Use graph. The new VPInstruction class is a generic single-instruction Recipe that models a planned instruction along with its opcode, operands and users. See VectorizationPlan.rst for more details. Differential Revision: https://reviews.llvm.org/D38676 llvm-svn: 318645
1 parent fa03a6a commit 8b9d1f3

File tree

7 files changed

+709
-129
lines changed

7 files changed

+709
-129
lines changed
 

‎llvm/docs/Proposals/VectorizationPlan.rst

+67-2
Original file line numberDiff line numberDiff line change
@@ -82,8 +82,14 @@ The design of VPlan follows several high-level guidelines:
8282
replicated VF*UF times to handle scalarized and predicated instructions.
8383
Innerloops are also modelled as SESE regions.
8484

85-
Low-level Design
86-
================
85+
7. Support instruction-level analysis and transformation, as part of Planning
86+
Step 2.b: During vectorization instructions may need to be traversed, moved,
87+
replaced by other instructions or be created. For example, vector idiom
88+
detection and formation involves searching for and optimizing instruction
89+
patterns.
90+
91+
Definitions
92+
===========
8793
The low-level design of VPlan comprises of the following classes.
8894

8995
:LoopVectorizationPlanner:
@@ -139,11 +145,64 @@ The low-level design of VPlan comprises of the following classes.
139145
instructions; e.g., cloned once, replicated multiple times or widened
140146
according to selected VF.
141147

148+
:VPValue:
149+
The base of VPlan's def-use relations class hierarchy. When instantiated, it
150+
models a constant or a live-in Value in VPlan. It has users, which are of type
151+
VPUser, but no operands.
152+
153+
:VPUser:
154+
A VPValue representing a general vertex in the def-use graph of VPlan. It has
155+
operands which are of type VPValue. When instantiated, it represents a
156+
live-out Instruction that exists outside VPlan. VPUser is similar in some
157+
aspects to LLVM's User class.
158+
159+
:VPInstruction:
160+
A VPInstruction is both a VPRecipe and a VPUser. It models a single
161+
VPlan-level instruction to be generated if the VPlan is executed, including
162+
its opcode and possibly additional characteristics. It is the basis for
163+
writing instruction-level analyses and optimizations in VPlan as creating,
164+
replacing or moving VPInstructions record both def-use and scheduling
165+
decisions. VPInstructions also extend LLVM IR's opcodes with idiomatic
166+
operations that enrich the Vectorizer's semantics.
167+
142168
:VPTransformState:
143169
Stores information used for generating output IR, passed from
144170
LoopVectorizationPlanner to its selected VPlan for execution, and used to pass
145171
additional information down to VPBlocks and VPRecipes.
146172

173+
The Planning Process and VPlan Roadmap
174+
======================================
175+
176+
Transforming the Loop Vectorizer to use VPlan follows a staged approach. First,
177+
VPlan is used to record the final vectorization decisions, and to execute them:
178+
the Hierarchical CFG models the planned control-flow, and Recipes capture
179+
decisions taken inside basic-blocks. Next, VPlan will be used also as the basis
180+
for taking these decisions, effectively turning them into a series of
181+
VPlan-to-VPlan algorithms. Finally, VPlan will support the planning process
182+
itself including cost-based analyses for making these decisions, to fully
183+
support compositional and iterative decision making.
184+
185+
Some decisions are local to an instruction in the loop, such as whether to widen
186+
it into a vector instruction or replicate it, keeping the generated instructions
187+
in place. Other decisions, however, involve moving instructions, replacing them
188+
with other instructions, and/or introducing new instructions. For example, a
189+
cast may sink past a later instruction and be widened to handle first-order
190+
recurrence; an interleave group of strided gathers or scatters may effectively
191+
move to one place where they are replaced with shuffles and a common wide vector
192+
load or store; new instructions may be introduced to compute masks, shuffle the
193+
elements of vectors, and pack scalar values into vectors or vice-versa.
194+
195+
In order for VPlan to support making instruction-level decisions and analyses,
196+
it needs to model the relevant instructions along with their def/use relations.
197+
This too follows a staged approach: first, the new instructions that compute
198+
masks are modeled as VPInstructions, along with their induced def/use subgraph.
199+
This effectively models masks in VPlan, facilitating VPlan-based predication.
200+
Next, the logic embedded within each Recipe for generating its instructions at
201+
VPlan execution time, will instead take part in the planning process by modeling
202+
them as VPInstructions. Finally, only logic that applies to instructions as a
203+
group will remain in Recipes, such as interleave groups and potentially other
204+
idiom groups having synergistic cost.
205+
147206
Related LLVM components
148207
-----------------------
149208
1. SLP Vectorizer: one can compare the VPlan model with LLVM's existing SLP
@@ -152,6 +211,9 @@ Related LLVM components
152211
2. RegionInfo: one can compare VPlan's H-CFG with the Region Analysis as used by
153212
Polly [7]_.
154213

214+
3. Loop Vectorizer: the Vectorization Plan aims to upgrade the infrastructure of
215+
the Loop Vectorizer and extend it to handle outer loops [8,9]_.
216+
155217
References
156218
----------
157219
.. [1] "Outer-loop vectorization: revisited for short SIMD architectures", Dorit
@@ -180,3 +242,6 @@ References
180242
181243
.. [8] "Introducing VPlan to the Loop Vectorizer", Gil Rapaport and Ayal Zaks,
182244
European LLVM Developers' Meeting 2017.
245+
246+
.. [9] "Extending LoopVectorizer: OpenMP4.5 SIMD and Outer Loop
247+
Auto-Vectorization", Intel Vectorizer Team, LLVM Developers' Meeting 2016.

‎llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

+226-117
Large diffs are not rendered by default.

‎llvm/lib/Transforms/Vectorize/VPlan.cpp

+74
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,14 @@ using namespace llvm;
4646

4747
#define DEBUG_TYPE "vplan"
4848

49+
raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
50+
if (const VPInstruction *Instr = dyn_cast<VPInstruction>(&V))
51+
Instr->print(OS);
52+
else
53+
V.printAsOperand(OS);
54+
return OS;
55+
}
56+
4957
/// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
5058
const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
5159
const VPBlockBase *Block = this;
@@ -212,10 +220,68 @@ void VPRegionBlock::execute(VPTransformState *State) {
212220
State->Instance.reset();
213221
}
214222

223+
void VPInstruction::generateInstruction(VPTransformState &State,
224+
unsigned Part) {
225+
IRBuilder<> &Builder = State.Builder;
226+
227+
if (Instruction::isBinaryOp(getOpcode())) {
228+
Value *A = State.get(getOperand(0), Part);
229+
Value *B = State.get(getOperand(1), Part);
230+
Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
231+
State.set(this, V, Part);
232+
return;
233+
}
234+
235+
switch (getOpcode()) {
236+
case VPInstruction::Not: {
237+
Value *A = State.get(getOperand(0), Part);
238+
Value *V = Builder.CreateNot(A);
239+
State.set(this, V, Part);
240+
break;
241+
}
242+
default:
243+
llvm_unreachable("Unsupported opcode for instruction");
244+
}
245+
}
246+
247+
void VPInstruction::execute(VPTransformState &State) {
248+
assert(!State.Instance && "VPInstruction executing an Instance");
249+
for (unsigned Part = 0; Part < State.UF; ++Part)
250+
generateInstruction(State, Part);
251+
}
252+
253+
void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
254+
O << " +\n" << Indent << "\"EMIT ";
255+
print(O);
256+
O << "\\l\"";
257+
}
258+
259+
void VPInstruction::print(raw_ostream &O) const {
260+
printAsOperand(O);
261+
O << " = ";
262+
263+
switch (getOpcode()) {
264+
case VPInstruction::Not:
265+
O << "not";
266+
break;
267+
default:
268+
O << Instruction::getOpcodeName(getOpcode());
269+
}
270+
271+
for (const VPValue *Operand : operands()) {
272+
O << " ";
273+
Operand->printAsOperand(O);
274+
}
275+
}
276+
215277
/// Generate the code inside the body of the vectorized loop. Assumes a single
216278
/// LoopVectorBody basic-block was created for this. Introduce additional
217279
/// basic-blocks as needed, and fill them all.
218280
void VPlan::execute(VPTransformState *State) {
281+
// 0. Set the reverse mapping from VPValues to Values for code generation.
282+
for (auto &Entry : Value2VPValue)
283+
State->VPValue2Value[Entry.second] = Entry.first;
284+
219285
BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
220286
BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
221287
assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
@@ -316,6 +382,14 @@ void VPlanPrinter::dump() {
316382
OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
317383
if (!Plan.getName().empty())
318384
OS << "\\n" << DOT::EscapeString(Plan.getName());
385+
if (!Plan.Value2VPValue.empty()) {
386+
OS << ", where:";
387+
for (auto Entry : Plan.Value2VPValue) {
388+
OS << "\\n" << *Entry.second;
389+
OS << DOT::EscapeString(" := ");
390+
Entry.first->printAsOperand(OS, false);
391+
}
392+
}
319393
OS << "\"]\n";
320394
OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
321395
OS << "edge [fontname=Courier, fontsize=30]\n";

‎llvm/lib/Transforms/Vectorize/VPlan.h

+134-9
Original file line numberDiff line numberDiff line change
@@ -15,15 +15,18 @@
1515
/// treated as proper graphs for generic algorithms;
1616
/// 3. Pure virtual VPRecipeBase serving as the base class for recipes contained
1717
/// within VPBasicBlocks;
18-
/// 4. The VPlan class holding a candidate for vectorization;
19-
/// 5. The VPlanPrinter class providing a way to print a plan in dot format.
18+
/// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned
19+
/// instruction;
20+
/// 5. The VPlan class holding a candidate for vectorization;
21+
/// 6. The VPlanPrinter class providing a way to print a plan in dot format;
2022
/// These are documented in docs/VectorizationPlan.rst.
2123
//
2224
//===----------------------------------------------------------------------===//
2325

2426
#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
2527
#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
2628

29+
#include "VPlanValue.h"
2730
#include "llvm/ADT/DenseMap.h"
2831
#include "llvm/ADT/GraphTraits.h"
2932
#include "llvm/ADT/Optional.h"
@@ -39,6 +42,13 @@
3942
#include <map>
4043
#include <string>
4144

45+
// The (re)use of existing LoopVectorize classes is subject to future VPlan
46+
// refactoring.
47+
namespace {
48+
class LoopVectorizationLegality;
49+
class LoopVectorizationCostModel;
50+
} // namespace
51+
4252
namespace llvm {
4353

4454
class BasicBlock;
@@ -82,6 +92,8 @@ struct VPIteration {
8292
/// Entries from either map can be retrieved using the getVectorValue and
8393
/// getScalarValue functions, which assert that the desired value exists.
8494
struct VectorizerValueMap {
95+
friend struct VPTransformState;
96+
8597
private:
8698
/// The unroll factor. Each entry in the vector map contains UF vector values.
8799
unsigned UF;
@@ -195,14 +207,21 @@ struct VectorizerValueMap {
195207
}
196208
};
197209

210+
/// This class is used to enable the VPlan to invoke a method of ILV. This is
211+
/// needed until the method is refactored out of ILV and becomes reusable.
212+
struct VPCallback {
213+
virtual ~VPCallback() {}
214+
virtual Value *getOrCreateVectorValues(Value *V, unsigned Part) = 0;
215+
};
216+
198217
/// VPTransformState holds information passed down when "executing" a VPlan,
199218
/// needed for generating the output IR.
200219
struct VPTransformState {
201220
VPTransformState(unsigned VF, unsigned UF, LoopInfo *LI, DominatorTree *DT,
202221
IRBuilder<> &Builder, VectorizerValueMap &ValueMap,
203-
InnerLoopVectorizer *ILV)
204-
: VF(VF), UF(UF), LI(LI), DT(DT), Builder(Builder), ValueMap(ValueMap),
205-
ILV(ILV) {}
222+
InnerLoopVectorizer *ILV, VPCallback &Callback)
223+
: VF(VF), UF(UF), Instance(), LI(LI), DT(DT), Builder(Builder),
224+
ValueMap(ValueMap), ILV(ILV), Callback(Callback) {}
206225

207226
/// The chosen Vectorization and Unroll Factors of the loop being vectorized.
208227
unsigned VF;
@@ -213,6 +232,37 @@ struct VPTransformState {
213232
/// instructions.
214233
Optional<VPIteration> Instance;
215234

235+
struct DataState {
236+
/// A type for vectorized values in the new loop. Each value from the
237+
/// original loop, when vectorized, is represented by UF vector values in
238+
/// the new unrolled loop, where UF is the unroll factor.
239+
typedef SmallVector<Value *, 2> PerPartValuesTy;
240+
241+
DenseMap<VPValue *, PerPartValuesTy> PerPartOutput;
242+
} Data;
243+
244+
/// Get the generated Value for a given VPValue and a given Part. Note that
245+
/// as some Defs are still created by ILV and managed in its ValueMap, this
246+
/// method will delegate the call to ILV in such cases in order to provide
247+
/// callers a consistent API.
248+
/// \see set.
249+
Value *get(VPValue *Def, unsigned Part) {
250+
// If Values have been set for this Def return the one relevant for \p Part.
251+
if (Data.PerPartOutput.count(Def))
252+
return Data.PerPartOutput[Def][Part];
253+
// Def is managed by ILV: bring the Values from ValueMap.
254+
return Callback.getOrCreateVectorValues(VPValue2Value[Def], Part);
255+
}
256+
257+
/// Set the generated Value for a given VPValue and a given Part.
258+
void set(VPValue *Def, Value *V, unsigned Part) {
259+
if (!Data.PerPartOutput.count(Def)) {
260+
DataState::PerPartValuesTy Entry(UF);
261+
Data.PerPartOutput[Def] = Entry;
262+
}
263+
Data.PerPartOutput[Def][Part] = V;
264+
}
265+
216266
/// Hold state information used when constructing the CFG of the output IR,
217267
/// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
218268
struct CFGState {
@@ -247,8 +297,14 @@ struct VPTransformState {
247297
/// Values of the output IR.
248298
VectorizerValueMap &ValueMap;
249299

300+
/// Hold a reference to a mapping between VPValues in VPlan and original
301+
/// Values they correspond to.
302+
VPValue2ValueTy VPValue2Value;
303+
250304
/// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
251305
InnerLoopVectorizer *ILV;
306+
307+
VPCallback &Callback;
252308
};
253309

254310
/// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
@@ -454,6 +510,7 @@ class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
454510
using VPRecipeTy = enum {
455511
VPBlendSC,
456512
VPBranchOnMaskSC,
513+
VPInstructionSC,
457514
VPInterleaveSC,
458515
VPPredInstPHISC,
459516
VPReplicateSC,
@@ -483,6 +540,52 @@ class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
483540
virtual void print(raw_ostream &O, const Twine &Indent) const = 0;
484541
};
485542

543+
/// This is a concrete Recipe that models a single VPlan-level instruction.
544+
/// While as any Recipe it may generate a sequence of IR instructions when
545+
/// executed, these instructions would always form a single-def expression as
546+
/// the VPInstruction is also a single def-use vertex.
547+
class VPInstruction : public VPUser, public VPRecipeBase {
548+
public:
549+
/// VPlan opcodes, extending LLVM IR with idiomatics instructions.
550+
enum { Not = Instruction::OtherOpsEnd + 1 };
551+
552+
private:
553+
typedef unsigned char OpcodeTy;
554+
OpcodeTy Opcode;
555+
556+
/// Utility method serving execute(): generates a single instance of the
557+
/// modeled instruction.
558+
void generateInstruction(VPTransformState &State, unsigned Part);
559+
560+
public:
561+
VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)
562+
: VPUser(VPValue::VPInstructionSC, Operands),
563+
VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {}
564+
565+
/// Method to support type inquiry through isa, cast, and dyn_cast.
566+
static inline bool classof(const VPValue *V) {
567+
return V->getVPValueID() == VPValue::VPInstructionSC;
568+
}
569+
570+
/// Method to support type inquiry through isa, cast, and dyn_cast.
571+
static inline bool classof(const VPRecipeBase *R) {
572+
return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC;
573+
}
574+
575+
unsigned getOpcode() const { return Opcode; }
576+
577+
/// Generate the instruction.
578+
/// TODO: We currently execute only per-part unless a specific instance is
579+
/// provided.
580+
void execute(VPTransformState &State) override;
581+
582+
/// Print the Recipe.
583+
void print(raw_ostream &O, const Twine &Indent) const override;
584+
585+
/// Print the VPInstruction.
586+
void print(raw_ostream &O) const;
587+
};
588+
486589
/// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
487590
/// holds a sequence of zero or more VPRecipe's each representing a sequence of
488591
/// output IR instructions.
@@ -539,15 +642,17 @@ class VPBasicBlock : public VPBlockBase {
539642
return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
540643
}
541644

542-
/// Augment the existing recipes of a VPBasicBlock with an additional
543-
/// \p Recipe as the last recipe.
544-
void appendRecipe(VPRecipeBase *Recipe) {
645+
void insert(VPRecipeBase *Recipe, iterator InsertPt) {
545646
assert(Recipe && "No recipe to append.");
546647
assert(!Recipe->Parent && "Recipe already in VPlan");
547648
Recipe->Parent = this;
548-
return Recipes.push_back(Recipe);
649+
Recipes.insert(InsertPt, Recipe);
549650
}
550651

652+
/// Augment the existing recipes of a VPBasicBlock with an additional
653+
/// \p Recipe as the last recipe.
654+
void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
655+
551656
/// The method which generates the output IR instructions that correspond to
552657
/// this VPBasicBlock, thereby "executing" the VPlan.
553658
void execute(struct VPTransformState *State) override;
@@ -620,6 +725,8 @@ class VPRegionBlock : public VPBlockBase {
620725
/// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
621726
/// VPBlock.
622727
class VPlan {
728+
friend class VPlanPrinter;
729+
623730
private:
624731
/// Hold the single entry to the Hierarchical CFG of the VPlan.
625732
VPBlockBase *Entry;
@@ -630,12 +737,18 @@ class VPlan {
630737
/// Holds the name of the VPlan, for printing.
631738
std::string Name;
632739

740+
/// Holds a mapping between Values and their corresponding VPValue inside
741+
/// VPlan.
742+
Value2VPValueTy Value2VPValue;
743+
633744
public:
634745
VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {}
635746

636747
~VPlan() {
637748
if (Entry)
638749
VPBlockBase::deleteCFG(Entry);
750+
for (auto &MapEntry : Value2VPValue)
751+
delete MapEntry.second;
639752
}
640753

641754
/// Generate the IR code for this VPlan.
@@ -654,6 +767,18 @@ class VPlan {
654767

655768
void setName(const Twine &newName) { Name = newName.str(); }
656769

770+
void addVPValue(Value *V) {
771+
assert(V && "Trying to add a null Value to VPlan");
772+
assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
773+
Value2VPValue[V] = new VPValue();
774+
}
775+
776+
VPValue *getVPValue(Value *V) {
777+
assert(V && "Trying to get the VPValue of a null Value");
778+
assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
779+
return Value2VPValue[V];
780+
}
781+
657782
private:
658783
/// Add to the given dominator tree the header block and every new basic block
659784
/// that was created between it and the latch block, inclusive.

‎llvm/lib/Transforms/Vectorize/VPlanBuilder.h

+61
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
//===- VPlanBuilder.h - A VPlan utility for constructing VPInstructions ---===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
///
10+
/// \file
11+
/// This file provides a VPlan-based builder utility analogous to IRBuilder.
12+
/// It provides an instruction-level API for generating VPInstructions while
13+
/// abstracting away the Recipe manipulation details.
14+
//===----------------------------------------------------------------------===//
15+
16+
#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_BUILDER_H
17+
#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_BUILDER_H
18+
19+
#include "VPlan.h"
20+
21+
namespace llvm {
22+
23+
class VPBuilder {
24+
private:
25+
VPBasicBlock *BB = nullptr;
26+
VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator();
27+
28+
VPInstruction *createInstruction(unsigned Opcode,
29+
std::initializer_list<VPValue *> Operands) {
30+
VPInstruction *Instr = new VPInstruction(Opcode, Operands);
31+
BB->insert(Instr, InsertPt);
32+
return Instr;
33+
}
34+
35+
public:
36+
VPBuilder() {}
37+
38+
/// \brief This specifies that created VPInstructions should be appended to
39+
/// the end of the specified block.
40+
void setInsertPoint(VPBasicBlock *TheBB) {
41+
assert(TheBB && "Attempting to set a null insert point");
42+
BB = TheBB;
43+
InsertPt = BB->end();
44+
}
45+
46+
VPValue *createNot(VPValue *Operand) {
47+
return createInstruction(VPInstruction::Not, {Operand});
48+
}
49+
50+
VPValue *createAnd(VPValue *LHS, VPValue *RHS) {
51+
return createInstruction(Instruction::BinaryOps::And, {LHS, RHS});
52+
}
53+
54+
VPValue *createOr(VPValue *LHS, VPValue *RHS) {
55+
return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS});
56+
}
57+
};
58+
59+
} // namespace llvm
60+
61+
#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_BUILDER_H

‎llvm/lib/Transforms/Vectorize/VPlanValue.h

+146
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
//===- VPlanValue.h - Represent Values in Vectorizer Plan -----------------===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
///
10+
/// \file
11+
/// This file contains the declarations of the entities induced by Vectorization
12+
/// Plans, e.g. the instructions the VPlan intends to generate if executed.
13+
/// VPlan models the following entities:
14+
/// VPValue
15+
/// |-- VPUser
16+
/// | |-- VPInstruction
17+
/// These are documented in docs/VectorizationPlan.rst.
18+
///
19+
//===----------------------------------------------------------------------===//
20+
21+
#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
22+
#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
23+
24+
#include "llvm/ADT/DenseMap.h"
25+
#include "llvm/ADT/SmallVector.h"
26+
#include "llvm/IR/Value.h"
27+
#include "llvm/Support/Debug.h"
28+
#include "llvm/Support/raw_ostream.h"
29+
30+
namespace llvm {
31+
32+
// Forward declarations.
33+
class VPUser;
34+
35+
// This is the base class of the VPlan Def/Use graph, used for modeling the data
36+
// flow into, within and out of the VPlan. VPValues can stand for live-ins
37+
// coming from the input IR, instructions which VPlan will generate if executed
38+
// and live-outs which the VPlan will need to fix accordingly.
39+
class VPValue {
40+
private:
41+
const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
42+
43+
SmallVector<VPUser *, 1> Users;
44+
45+
protected:
46+
VPValue(const unsigned char SC) : SubclassID(SC) {}
47+
48+
public:
49+
/// An enumeration for keeping track of the concrete subclass of VPValue that
50+
/// are actually instantiated. Values of this enumeration are kept in the
51+
/// SubclassID field of the VPValue objects. They are used for concrete
52+
/// type identification.
53+
enum { VPValueSC, VPUserSC, VPInstructionSC };
54+
55+
VPValue() : SubclassID(VPValueSC) {}
56+
VPValue(const VPValue &) = delete;
57+
VPValue &operator=(const VPValue &) = delete;
58+
59+
/// \return an ID for the concrete type of this object.
60+
/// This is used to implement the classof checks. This should not be used
61+
/// for any other purpose, as the values may change as LLVM evolves.
62+
unsigned getVPValueID() const { return SubclassID; }
63+
64+
void printAsOperand(raw_ostream &OS) const {
65+
OS << "%vp" << (unsigned short)(unsigned long long)this;
66+
}
67+
68+
unsigned getNumUsers() const { return Users.size(); }
69+
void addUser(VPUser &User) { Users.push_back(&User); }
70+
71+
typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
72+
typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
73+
typedef iterator_range<user_iterator> user_range;
74+
typedef iterator_range<const_user_iterator> const_user_range;
75+
76+
user_iterator user_begin() { return Users.begin(); }
77+
const_user_iterator user_begin() const { return Users.begin(); }
78+
user_iterator user_end() { return Users.end(); }
79+
const_user_iterator user_end() const { return Users.end(); }
80+
user_range users() { return user_range(user_begin(), user_end()); }
81+
const_user_range users() const {
82+
return const_user_range(user_begin(), user_end());
83+
}
84+
};
85+
86+
typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
87+
typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
88+
89+
raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
90+
91+
/// This class augments VPValue with operands which provide the inverse def-use
92+
/// edges from VPValue's users to their defs.
93+
class VPUser : public VPValue {
94+
private:
95+
SmallVector<VPValue *, 2> Operands;
96+
97+
void addOperand(VPValue *Operand) {
98+
Operands.push_back(Operand);
99+
Operand->addUser(*this);
100+
}
101+
102+
protected:
103+
VPUser(const unsigned char SC) : VPValue(SC) {}
104+
VPUser(const unsigned char SC, ArrayRef<VPValue *> Operands) : VPValue(SC) {
105+
for (VPValue *Operand : Operands)
106+
addOperand(Operand);
107+
}
108+
109+
public:
110+
VPUser() : VPValue(VPValue::VPUserSC) {}
111+
VPUser(ArrayRef<VPValue *> Operands) : VPUser(VPValue::VPUserSC, Operands) {}
112+
VPUser(std::initializer_list<VPValue *> Operands)
113+
: VPUser(ArrayRef<VPValue *>(Operands)) {}
114+
VPUser(const VPUser &) = delete;
115+
VPUser &operator=(const VPUser &) = delete;
116+
117+
/// Method to support type inquiry through isa, cast, and dyn_cast.
118+
static inline bool classof(const VPValue *V) {
119+
return V->getVPValueID() >= VPUserSC &&
120+
V->getVPValueID() <= VPInstructionSC;
121+
}
122+
123+
unsigned getNumOperands() const { return Operands.size(); }
124+
inline VPValue *getOperand(unsigned N) const {
125+
assert(N < Operands.size() && "Operand index out of bounds");
126+
return Operands[N];
127+
}
128+
129+
typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
130+
typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
131+
typedef iterator_range<operand_iterator> operand_range;
132+
typedef iterator_range<const_operand_iterator> const_operand_range;
133+
134+
operand_iterator op_begin() { return Operands.begin(); }
135+
const_operand_iterator op_begin() const { return Operands.begin(); }
136+
operand_iterator op_end() { return Operands.end(); }
137+
const_operand_iterator op_end() const { return Operands.end(); }
138+
operand_range operands() { return operand_range(op_begin(), op_end()); }
139+
const_operand_range operands() const {
140+
return const_operand_range(op_begin(), op_end());
141+
}
142+
};
143+
144+
} // namespace llvm
145+
146+
#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H

‎llvm/test/Transforms/LoopVectorize/if-conversion-nest.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -42,9 +42,9 @@ define i32 @foo(i32* nocapture %A, i32* nocapture %B, i32 %n) {
4242
; CHECK-NEXT: [[TMP13:%.*]] = icmp slt <4 x i32> [[WIDE_LOAD6]], <i32 4, i32 4, i32 4, i32 4>
4343
; CHECK-NEXT: [[TMP14:%.*]] = select <4 x i1> [[TMP13]], <4 x i32> <i32 4, i32 4, i32 4, i32 4>, <4 x i32> <i32 5, i32 5, i32 5, i32 5>
4444
; CHECK-NEXT: [[TMP15:%.*]] = and <4 x i1> [[TMP12]], [[TMP11]]
45-
; CHECK-NEXT: [[PREDPHI:%.*]] = select <4 x i1> [[TMP15]], <4 x i32> <i32 3, i32 3, i32 3, i32 3>, <4 x i32> <i32 9, i32 9, i32 9, i32 9>
4645
; CHECK-NEXT: [[TMP16:%.*]] = xor <4 x i1> [[TMP12]], <i1 true, i1 true, i1 true, i1 true>
4746
; CHECK-NEXT: [[TMP17:%.*]] = and <4 x i1> [[TMP11]], [[TMP16]]
47+
; CHECK-NEXT: [[PREDPHI:%.*]] = select <4 x i1> [[TMP15]], <4 x i32> <i32 3, i32 3, i32 3, i32 3>, <4 x i32> <i32 9, i32 9, i32 9, i32 9>
4848
; CHECK-NEXT: [[PREDPHI7:%.*]] = select <4 x i1> [[TMP17]], <4 x i32> [[TMP14]], <4 x i32> [[PREDPHI]]
4949
; CHECK-NEXT: [[TMP18:%.*]] = bitcast i32* [[TMP7]] to <4 x i32>*
5050
; CHECK-NEXT: store <4 x i32> [[PREDPHI7]], <4 x i32>* [[TMP18]], align 4, !alias.scope !0, !noalias !3

0 commit comments

Comments
 (0)
Please sign in to comment.