LLVM 17.0.0git
VPlanHCFGBuilder.cpp
Go to the documentation of this file.
1//===-- VPlanHCFGBuilder.cpp ----------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements the construction of a VPlan-based Hierarchical CFG
11/// (H-CFG) for an incoming IR. This construction comprises the following
12/// components and steps:
13//
14/// 1. PlainCFGBuilder class: builds a plain VPBasicBlock-based CFG that
15/// faithfully represents the CFG in the incoming IR. A VPRegionBlock (Top
16/// Region) is created to enclose and serve as parent of all the VPBasicBlocks
17/// in the plain CFG.
18/// NOTE: At this point, there is a direct correspondence between all the
19/// VPBasicBlocks created for the initial plain CFG and the incoming
20/// BasicBlocks. However, this might change in the future.
21///
22//===----------------------------------------------------------------------===//
23
24#include "VPlanHCFGBuilder.h"
27
28#define DEBUG_TYPE "loop-vectorize"
29
30using namespace llvm;
31
32namespace {
33// Class that is used to build the plain CFG for the incoming IR.
34class PlainCFGBuilder {
35private:
36 // The outermost loop of the input loop nest considered for vectorization.
37 Loop *TheLoop;
38
39 // Loop Info analysis.
40 LoopInfo *LI;
41
42 // Vectorization plan that we are working on.
43 VPlan &Plan;
44
45 // Builder of the VPlan instruction-level representation.
46 VPBuilder VPIRBuilder;
47
48 // NOTE: The following maps are intentionally destroyed after the plain CFG
49 // construction because subsequent VPlan-to-VPlan transformation may
50 // invalidate them.
51 // Map incoming BasicBlocks to their newly-created VPBasicBlocks.
53 // Map incoming Value definitions to their newly-created VPValues.
54 DenseMap<Value *, VPValue *> IRDef2VPValue;
55
56 // Hold phi node's that need to be fixed once the plain CFG has been built.
58
59 /// Maps loops in the original IR to their corresponding region.
61
62 // Utility functions.
63 void setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB);
64 void fixPhiNodes();
65 VPBasicBlock *getOrCreateVPBB(BasicBlock *BB);
66#ifndef NDEBUG
67 bool isExternalDef(Value *Val);
68#endif
69 VPValue *getOrCreateVPOperand(Value *IRVal);
70 void createVPInstructionsForVPBB(VPBasicBlock *VPBB, BasicBlock *BB);
71
72public:
73 PlainCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
74 : TheLoop(Lp), LI(LI), Plan(P) {}
75
76 /// Build plain CFG for TheLoop. Return the pre-header VPBasicBlock connected
77 /// to a new VPRegionBlock (TopRegion) enclosing the plain CFG.
78 VPBasicBlock *buildPlainCFG();
79};
80} // anonymous namespace
81
82// Set predecessors of \p VPBB in the same order as they are in \p BB. \p VPBB
83// must have no predecessors.
84void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) {
86 // Collect VPBB predecessors.
87 for (BasicBlock *Pred : predecessors(BB))
88 VPBBPreds.push_back(getOrCreateVPBB(Pred));
89
90 VPBB->setPredecessors(VPBBPreds);
91}
92
93// Add operands to VPInstructions representing phi nodes from the input IR.
94void PlainCFGBuilder::fixPhiNodes() {
95 for (auto *Phi : PhisToFix) {
96 assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
97 VPValue *VPVal = IRDef2VPValue[Phi];
98 assert(isa<VPWidenPHIRecipe>(VPVal) &&
99 "Expected WidenPHIRecipe for phi node.");
100 auto *VPPhi = cast<VPWidenPHIRecipe>(VPVal);
101 assert(VPPhi->getNumOperands() == 0 &&
102 "Expected VPInstruction with no operands.");
103
104 for (unsigned I = 0; I != Phi->getNumOperands(); ++I)
105 VPPhi->addIncoming(getOrCreateVPOperand(Phi->getIncomingValue(I)),
106 BB2VPBB[Phi->getIncomingBlock(I)]);
107 }
108}
109
110// Create a new empty VPBasicBlock for an incoming BasicBlock in the region
111// corresponding to the containing loop or retrieve an existing one if it was
112// already created. If no region exists yet for the loop containing \p BB, a new
113// one is created.
114VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
115 auto BlockIt = BB2VPBB.find(BB);
116 if (BlockIt != BB2VPBB.end())
117 // Retrieve existing VPBB.
118 return BlockIt->second;
119
120 // Get or create a region for the loop containing BB.
121 Loop *CurrentLoop = LI->getLoopFor(BB);
122 VPRegionBlock *ParentR = nullptr;
123 if (CurrentLoop) {
124 auto Iter = Loop2Region.insert({CurrentLoop, nullptr});
125 if (Iter.second)
126 Iter.first->second = new VPRegionBlock(
127 CurrentLoop->getHeader()->getName().str(), false /*isReplicator*/);
128 ParentR = Iter.first->second;
129 }
130
131 // Create new VPBB.
132 LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << BB->getName() << "\n");
133 VPBasicBlock *VPBB = new VPBasicBlock(BB->getName());
134 BB2VPBB[BB] = VPBB;
135 VPBB->setParent(ParentR);
136 return VPBB;
137}
138
139#ifndef NDEBUG
140// Return true if \p Val is considered an external definition. An external
141// definition is either:
142// 1. A Value that is not an Instruction. This will be refined in the future.
143// 2. An Instruction that is outside of the CFG snippet represented in VPlan,
144// i.e., is not part of: a) the loop nest, b) outermost loop PH and, c)
145// outermost loop exits.
146bool PlainCFGBuilder::isExternalDef(Value *Val) {
147 // All the Values that are not Instructions are considered external
148 // definitions for now.
149 Instruction *Inst = dyn_cast<Instruction>(Val);
150 if (!Inst)
151 return true;
152
153 BasicBlock *InstParent = Inst->getParent();
154 assert(InstParent && "Expected instruction parent.");
155
156 // Check whether Instruction definition is in loop PH.
157 BasicBlock *PH = TheLoop->getLoopPreheader();
158 assert(PH && "Expected loop pre-header.");
159
160 if (InstParent == PH)
161 // Instruction definition is in outermost loop PH.
162 return false;
163
164 // Check whether Instruction definition is in the loop exit.
165 BasicBlock *Exit = TheLoop->getUniqueExitBlock();
166 assert(Exit && "Expected loop with single exit.");
167 if (InstParent == Exit) {
168 // Instruction definition is in outermost loop exit.
169 return false;
170 }
171
172 // Check whether Instruction definition is in loop body.
173 return !TheLoop->contains(Inst);
174}
175#endif
176
177// Create a new VPValue or retrieve an existing one for the Instruction's
178// operand \p IRVal. This function must only be used to create/retrieve VPValues
179// for *Instruction's operands* and not to create regular VPInstruction's. For
180// the latter, please, look at 'createVPInstructionsForVPBB'.
181VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
182 auto VPValIt = IRDef2VPValue.find(IRVal);
183 if (VPValIt != IRDef2VPValue.end())
184 // Operand has an associated VPInstruction or VPValue that was previously
185 // created.
186 return VPValIt->second;
187
188 // Operand doesn't have a previously created VPInstruction/VPValue. This
189 // means that operand is:
190 // A) a definition external to VPlan,
191 // B) any other Value without specific representation in VPlan.
192 // For now, we use VPValue to represent A and B and classify both as external
193 // definitions. We may introduce specific VPValue subclasses for them in the
194 // future.
195 assert(isExternalDef(IRVal) && "Expected external definition as operand.");
196
197 // A and B: Create VPValue and add it to the pool of external definitions and
198 // to the Value->VPValue map.
199 VPValue *NewVPVal = Plan.getOrAddExternalDef(IRVal);
200 IRDef2VPValue[IRVal] = NewVPVal;
201 return NewVPVal;
202}
203
204// Create new VPInstructions in a VPBasicBlock, given its BasicBlock
205// counterpart. This function must be invoked in RPO so that the operands of a
206// VPInstruction in \p BB have been visited before (except for Phi nodes).
207void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
208 BasicBlock *BB) {
209 VPIRBuilder.setInsertPoint(VPBB);
210 for (Instruction &InstRef : *BB) {
211 Instruction *Inst = &InstRef;
212
213 // There shouldn't be any VPValue for Inst at this point. Otherwise, we
214 // visited Inst when we shouldn't, breaking the RPO traversal order.
215 assert(!IRDef2VPValue.count(Inst) &&
216 "Instruction shouldn't have been visited.");
217
218 if (auto *Br = dyn_cast<BranchInst>(Inst)) {
219 // Conditional branch instruction are represented using BranchOnCond
220 // recipes.
221 if (Br->isConditional()) {
222 VPValue *Cond = getOrCreateVPOperand(Br->getCondition());
223 VPBB->appendRecipe(
225 }
226
227 // Skip the rest of the Instruction processing for Branch instructions.
228 continue;
229 }
230
231 VPValue *NewVPV;
232 if (auto *Phi = dyn_cast<PHINode>(Inst)) {
233 // Phi node's operands may have not been visited at this point. We create
234 // an empty VPInstruction that we will fix once the whole plain CFG has
235 // been built.
236 NewVPV = new VPWidenPHIRecipe(Phi);
237 VPBB->appendRecipe(cast<VPWidenPHIRecipe>(NewVPV));
238 PhisToFix.push_back(Phi);
239 } else {
240 // Translate LLVM-IR operands into VPValue operands and set them in the
241 // new VPInstruction.
242 SmallVector<VPValue *, 4> VPOperands;
243 for (Value *Op : Inst->operands())
244 VPOperands.push_back(getOrCreateVPOperand(Op));
245
246 // Build VPInstruction for any arbitrary Instruction without specific
247 // representation in VPlan.
248 NewVPV = cast<VPInstruction>(
249 VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst));
250 }
251
252 IRDef2VPValue[Inst] = NewVPV;
253 }
254}
255
256// Main interface to build the plain CFG.
257VPBasicBlock *PlainCFGBuilder::buildPlainCFG() {
258 // 1. Scan the body of the loop in a topological order to visit each basic
259 // block after having visited its predecessor basic blocks. Create a VPBB for
260 // each BB and link it to its successor and predecessor VPBBs. Note that
261 // predecessors must be set in the same order as they are in the incomming IR.
262 // Otherwise, there might be problems with existing phi nodes and algorithm
263 // based on predecessors traversal.
264
265 // Loop PH needs to be explicitly visited since it's not taken into account by
266 // LoopBlocksDFS.
267 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
268 assert((ThePreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
269 "Unexpected loop preheader");
270 VPBasicBlock *ThePreheaderVPBB = getOrCreateVPBB(ThePreheaderBB);
271 ThePreheaderVPBB->setName("vector.ph");
272 for (auto &I : *ThePreheaderBB) {
273 if (I.getType()->isVoidTy())
274 continue;
275 IRDef2VPValue[&I] = Plan.getOrAddExternalDef(&I);
276 }
277 // Create empty VPBB for Loop H so that we can link PH->H.
278 VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
279 HeaderVPBB->setName("vector.body");
280 ThePreheaderVPBB->setOneSuccessor(HeaderVPBB);
281
282 LoopBlocksRPO RPO(TheLoop);
283 RPO.perform(LI);
284
285 for (BasicBlock *BB : RPO) {
286 // Create or retrieve the VPBasicBlock for this BB and create its
287 // VPInstructions.
288 VPBasicBlock *VPBB = getOrCreateVPBB(BB);
289 createVPInstructionsForVPBB(VPBB, BB);
290
291 // Set VPBB successors. We create empty VPBBs for successors if they don't
292 // exist already. Recipes will be created when the successor is visited
293 // during the RPO traversal.
294 Instruction *TI = BB->getTerminator();
295 assert(TI && "Terminator expected.");
296 unsigned NumSuccs = TI->getNumSuccessors();
297
298 if (NumSuccs == 1) {
299 VPBasicBlock *SuccVPBB = getOrCreateVPBB(TI->getSuccessor(0));
300 assert(SuccVPBB && "VPBB Successor not found.");
301 VPBB->setOneSuccessor(SuccVPBB);
302 } else if (NumSuccs == 2) {
303 VPBasicBlock *SuccVPBB0 = getOrCreateVPBB(TI->getSuccessor(0));
304 assert(SuccVPBB0 && "Successor 0 not found.");
305 VPBasicBlock *SuccVPBB1 = getOrCreateVPBB(TI->getSuccessor(1));
306 assert(SuccVPBB1 && "Successor 1 not found.");
307
308 // Get VPBB's condition bit.
309 assert(isa<BranchInst>(TI) && "Unsupported terminator!");
310 // Look up the branch condition to get the corresponding VPValue
311 // representing the condition bit in VPlan (which may be in another VPBB).
312 assert(IRDef2VPValue.count(cast<BranchInst>(TI)->getCondition()) &&
313 "Missing condition bit in IRDef2VPValue!");
314
315 // Link successors.
316 VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1);
317 } else
318 llvm_unreachable("Number of successors not supported.");
319
320 // Set VPBB predecessors in the same order as they are in the incoming BB.
321 setVPBBPredsFromBB(VPBB, BB);
322 }
323
324 // 2. Process outermost loop exit. We created an empty VPBB for the loop
325 // single exit BB during the RPO traversal of the loop body but Instructions
326 // weren't visited because it's not part of the the loop.
327 BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
328 assert(LoopExitBB && "Loops with multiple exits are not supported.");
329 VPBasicBlock *LoopExitVPBB = BB2VPBB[LoopExitBB];
330 // Loop exit was already set as successor of the loop exiting BB.
331 // We only set its predecessor VPBB now.
332 setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB);
333
334 // 3. Fix up region blocks for loops. For each loop,
335 // * use the header block as entry to the corresponding region,
336 // * use the latch block as exit of the corresponding region,
337 // * set the region as successor of the loop pre-header, and
338 // * set the exit block as successor to the region.
339 SmallVector<Loop *> LoopWorkList;
340 LoopWorkList.push_back(TheLoop);
341 while (!LoopWorkList.empty()) {
342 Loop *L = LoopWorkList.pop_back_val();
343 BasicBlock *Header = L->getHeader();
344 BasicBlock *Exiting = L->getLoopLatch();
345 assert(Exiting == L->getExitingBlock() &&
346 "Latch must be the only exiting block");
347 VPRegionBlock *Region = Loop2Region[L];
348 VPBasicBlock *HeaderVPBB = getOrCreateVPBB(Header);
349 VPBasicBlock *ExitingVPBB = getOrCreateVPBB(Exiting);
350
351 // Disconnect backedge and pre-header from header.
352 VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(L->getLoopPreheader());
353 VPBlockUtils::disconnectBlocks(PreheaderVPBB, HeaderVPBB);
354 VPBlockUtils::disconnectBlocks(ExitingVPBB, HeaderVPBB);
355
356 Region->setParent(PreheaderVPBB->getParent());
357 Region->setEntry(HeaderVPBB);
358 VPBlockUtils::connectBlocks(PreheaderVPBB, Region);
359
360 // Disconnect exit block from exiting (=latch) block, set exiting block and
361 // connect region to exit block.
362 VPBasicBlock *ExitVPBB = getOrCreateVPBB(L->getExitBlock());
363 VPBlockUtils::disconnectBlocks(ExitingVPBB, ExitVPBB);
364 Region->setExiting(ExitingVPBB);
366
367 // Queue sub-loops for processing.
368 LoopWorkList.append(L->begin(), L->end());
369 }
370 // 4. The whole CFG has been built at this point so all the input Values must
371 // have a VPlan couterpart. Fix VPlan phi nodes by adding their corresponding
372 // VPlan operands.
373 fixPhiNodes();
374
375 return ThePreheaderVPBB;
376}
377
378VPBasicBlock *VPlanHCFGBuilder::buildPlainCFG() {
379 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
380 return PCFGBuilder.buildPlainCFG();
381}
382
383// Public interface to build a H-CFG.
385 // Build Top Region enclosing the plain CFG and set it as VPlan entry.
386 VPBasicBlock *EntryVPBB = buildPlainCFG();
387 Plan.setEntry(EntryVPBB);
388 LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
389
390 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
391 Verifier.verifyHierarchicalCFG(TopRegion);
392
393 // Compute plain CFG dom tree for VPLInfo.
394 VPDomTree.recalculate(Plan);
395 LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
396 VPDomTree.print(dbgs()));
397}
SmallVector< MachineOperand, 4 > Cond
#define LLVM_DEBUG(X)
Definition: Debug.h:101
rpo function Deduce function attributes in RPO
This file provides a LoopVectorizationPlanner class.
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the VPlanHCFGBuilder class which contains the public interface (buildHierarchicalCF...
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
void print(raw_ostream &O) const
print - Convert to human readable form
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const BasicBlock * getParent() const
Definition: Instruction.h:90
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
BlockT * getHeader() const
Definition: LoopInfo.h:105
iterator end() const
Definition: LoopInfo.h:172
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:107
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
iterator begin() const
Definition: LoopInfo.h:171
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
bool empty() const
Definition: SmallVector.h:94
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:222
op_range operands()
Definition: User.h:242
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1939
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2007
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:390
VPRegionBlock * getParent()
Definition: VPlan.h:462
void setName(const Twine &newName)
Definition: VPlan.h:455
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:574
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition: VPlan.h:565
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
Definition: VPlan.h:556
void setParent(VPRegionBlock *P)
Definition: VPlan.h:473
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2529
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2518
VPlan-based builder utility analogous to IRBuilder.
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:779
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2063
A recipe for handling header phis that are widened in the vector loop.
Definition: VPlan.h:1209
void buildHierarchicalCFG()
Build H-CFG for TheLoop and update Plan accordingly.
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2160
void setName(const Twine &newName)
Definition: VPlan.h:2276
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:2353
VPBlockBase * setEntry(VPBlockBase *Block)
Definition: VPlan.h:2226
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
auto predecessors(const MachineBasicBlock *BB)
void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const
Verify the invariants of the H-CFG starting from TopRegion.