LLVM 18.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 setRegionPredsFromBB(VPRegionBlock *VPBB, BasicBlock *BB);
65 void fixPhiNodes();
66 VPBasicBlock *getOrCreateVPBB(BasicBlock *BB);
67#ifndef NDEBUG
68 bool isExternalDef(Value *Val);
69#endif
70 VPValue *getOrCreateVPOperand(Value *IRVal);
71 void createVPInstructionsForVPBB(VPBasicBlock *VPBB, BasicBlock *BB);
72
73public:
74 PlainCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
75 : TheLoop(Lp), LI(LI), Plan(P) {}
76
77 /// Build plain CFG for TheLoop and connects it to Plan's entry.
78 void 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) {
85 auto GetLatchOfExit = [this](BasicBlock *BB) -> BasicBlock * {
86 auto *SinglePred = BB->getSinglePredecessor();
87 Loop *LoopForBB = LI->getLoopFor(BB);
88 if (!SinglePred || LI->getLoopFor(SinglePred) == LoopForBB)
89 return nullptr;
90 // The input IR must be in loop-simplify form, ensuring a single predecessor
91 // for exit blocks.
92 assert(SinglePred == LI->getLoopFor(SinglePred)->getLoopLatch() &&
93 "SinglePred must be the only loop latch");
94 return SinglePred;
95 };
96 if (auto *LatchBB = GetLatchOfExit(BB)) {
97 auto *PredRegion = getOrCreateVPBB(LatchBB)->getParent();
98 assert(VPBB == cast<VPBasicBlock>(PredRegion->getSingleSuccessor()) &&
99 "successor must already be set for PredRegion; it must have VPBB "
100 "as single successor");
101 VPBB->setPredecessors({PredRegion});
102 return;
103 }
104 // Collect VPBB predecessors.
106 for (BasicBlock *Pred : predecessors(BB))
107 VPBBPreds.push_back(getOrCreateVPBB(Pred));
108 VPBB->setPredecessors(VPBBPreds);
109}
110
111static bool isHeaderBB(BasicBlock *BB, Loop *L) {
112 return L && BB == L->getHeader();
113}
114
115void PlainCFGBuilder::setRegionPredsFromBB(VPRegionBlock *Region,
116 BasicBlock *BB) {
117 // BB is a loop header block. Connect the region to the loop preheader.
118 Loop *LoopOfBB = LI->getLoopFor(BB);
119 Region->setPredecessors({getOrCreateVPBB(LoopOfBB->getLoopPredecessor())});
120}
121
122// Add operands to VPInstructions representing phi nodes from the input IR.
123void PlainCFGBuilder::fixPhiNodes() {
124 for (auto *Phi : PhisToFix) {
125 assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
126 VPValue *VPVal = IRDef2VPValue[Phi];
127 assert(isa<VPWidenPHIRecipe>(VPVal) &&
128 "Expected WidenPHIRecipe for phi node.");
129 auto *VPPhi = cast<VPWidenPHIRecipe>(VPVal);
130 assert(VPPhi->getNumOperands() == 0 &&
131 "Expected VPInstruction with no operands.");
132
133 Loop *L = LI->getLoopFor(Phi->getParent());
134 if (isHeaderBB(Phi->getParent(), L)) {
135 // For header phis, make sure the incoming value from the loop
136 // predecessor is the first operand of the recipe.
137 assert(Phi->getNumOperands() == 2);
138 BasicBlock *LoopPred = L->getLoopPredecessor();
139 VPPhi->addIncoming(
140 getOrCreateVPOperand(Phi->getIncomingValueForBlock(LoopPred)),
141 BB2VPBB[LoopPred]);
142 BasicBlock *LoopLatch = L->getLoopLatch();
143 VPPhi->addIncoming(
144 getOrCreateVPOperand(Phi->getIncomingValueForBlock(LoopLatch)),
145 BB2VPBB[LoopLatch]);
146 continue;
147 }
148
149 for (unsigned I = 0; I != Phi->getNumOperands(); ++I)
150 VPPhi->addIncoming(getOrCreateVPOperand(Phi->getIncomingValue(I)),
151 BB2VPBB[Phi->getIncomingBlock(I)]);
152 }
153}
154
155static bool isHeaderVPBB(VPBasicBlock *VPBB) {
156 return VPBB->getParent() && VPBB->getParent()->getEntry() == VPBB;
157}
158
159// Create a new empty VPBasicBlock for an incoming BasicBlock in the region
160// corresponding to the containing loop or retrieve an existing one if it was
161// already created. If no region exists yet for the loop containing \p BB, a new
162// one is created.
163VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
164 if (auto *VPBB = BB2VPBB.lookup(BB)) {
165 // Retrieve existing VPBB.
166 return VPBB;
167 }
168
169 // Create new VPBB.
170 LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << BB->getName() << "\n");
171 VPBasicBlock *VPBB = new VPBasicBlock(BB->getName());
172 BB2VPBB[BB] = VPBB;
173
174 // Get or create a region for the loop containing BB.
175 Loop *LoopOfBB = LI->getLoopFor(BB);
176 if (!LoopOfBB)
177 return VPBB;
178
179 VPRegionBlock *RegionOfBB = Loop2Region.lookup(LoopOfBB);
180 assert((RegionOfBB != nullptr) ^ isHeaderBB(BB, LoopOfBB) &&
181 "region must exist or BB must be a loop header");
182 if (RegionOfBB) {
183 VPBB->setParent(RegionOfBB);
184 } else {
185 // If BB's loop is nested inside another loop within VPlan's scope, the
186 // header of that enclosing loop was already visited and its region
187 // constructed and recorded in Loop2Region. That region is now set as the
188 // parent of VPBB's region. Otherwise it is set to null.
189 auto *RegionOfVPBB = new VPRegionBlock(
190 LoopOfBB->getHeader()->getName().str(), false /*isReplicator*/);
191 RegionOfVPBB->setParent(Loop2Region[LoopOfBB->getParentLoop()]);
192 RegionOfVPBB->setEntry(VPBB);
193 Loop2Region[LoopOfBB] = RegionOfVPBB;
194 }
195 return VPBB;
196}
197
198#ifndef NDEBUG
199// Return true if \p Val is considered an external definition. An external
200// definition is either:
201// 1. A Value that is not an Instruction. This will be refined in the future.
202// 2. An Instruction that is outside of the CFG snippet represented in VPlan,
203// i.e., is not part of: a) the loop nest, b) outermost loop PH and, c)
204// outermost loop exits.
205bool PlainCFGBuilder::isExternalDef(Value *Val) {
206 // All the Values that are not Instructions are considered external
207 // definitions for now.
208 Instruction *Inst = dyn_cast<Instruction>(Val);
209 if (!Inst)
210 return true;
211
212 BasicBlock *InstParent = Inst->getParent();
213 assert(InstParent && "Expected instruction parent.");
214
215 // Check whether Instruction definition is in loop PH.
216 BasicBlock *PH = TheLoop->getLoopPreheader();
217 assert(PH && "Expected loop pre-header.");
218
219 if (InstParent == PH)
220 // Instruction definition is in outermost loop PH.
221 return false;
222
223 // Check whether Instruction definition is in the loop exit.
224 BasicBlock *Exit = TheLoop->getUniqueExitBlock();
225 assert(Exit && "Expected loop with single exit.");
226 if (InstParent == Exit) {
227 // Instruction definition is in outermost loop exit.
228 return false;
229 }
230
231 // Check whether Instruction definition is in loop body.
232 return !TheLoop->contains(Inst);
233}
234#endif
235
236// Create a new VPValue or retrieve an existing one for the Instruction's
237// operand \p IRVal. This function must only be used to create/retrieve VPValues
238// for *Instruction's operands* and not to create regular VPInstruction's. For
239// the latter, please, look at 'createVPInstructionsForVPBB'.
240VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
241 auto VPValIt = IRDef2VPValue.find(IRVal);
242 if (VPValIt != IRDef2VPValue.end())
243 // Operand has an associated VPInstruction or VPValue that was previously
244 // created.
245 return VPValIt->second;
246
247 // Operand doesn't have a previously created VPInstruction/VPValue. This
248 // means that operand is:
249 // A) a definition external to VPlan,
250 // B) any other Value without specific representation in VPlan.
251 // For now, we use VPValue to represent A and B and classify both as external
252 // definitions. We may introduce specific VPValue subclasses for them in the
253 // future.
254 assert(isExternalDef(IRVal) && "Expected external definition as operand.");
255
256 // A and B: Create VPValue and add it to the pool of external definitions and
257 // to the Value->VPValue map.
258 VPValue *NewVPVal = Plan.getVPValueOrAddLiveIn(IRVal);
259 IRDef2VPValue[IRVal] = NewVPVal;
260 return NewVPVal;
261}
262
263// Create new VPInstructions in a VPBasicBlock, given its BasicBlock
264// counterpart. This function must be invoked in RPO so that the operands of a
265// VPInstruction in \p BB have been visited before (except for Phi nodes).
266void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
267 BasicBlock *BB) {
268 VPIRBuilder.setInsertPoint(VPBB);
269 for (Instruction &InstRef : *BB) {
270 Instruction *Inst = &InstRef;
271
272 // There shouldn't be any VPValue for Inst at this point. Otherwise, we
273 // visited Inst when we shouldn't, breaking the RPO traversal order.
274 assert(!IRDef2VPValue.count(Inst) &&
275 "Instruction shouldn't have been visited.");
276
277 if (auto *Br = dyn_cast<BranchInst>(Inst)) {
278 // Conditional branch instruction are represented using BranchOnCond
279 // recipes.
280 if (Br->isConditional()) {
281 VPValue *Cond = getOrCreateVPOperand(Br->getCondition());
282 VPBB->appendRecipe(
284 }
285
286 // Skip the rest of the Instruction processing for Branch instructions.
287 continue;
288 }
289
290 VPValue *NewVPV;
291 if (auto *Phi = dyn_cast<PHINode>(Inst)) {
292 // Phi node's operands may have not been visited at this point. We create
293 // an empty VPInstruction that we will fix once the whole plain CFG has
294 // been built.
295 NewVPV = new VPWidenPHIRecipe(Phi);
296 VPBB->appendRecipe(cast<VPWidenPHIRecipe>(NewVPV));
297 PhisToFix.push_back(Phi);
298 } else {
299 // Translate LLVM-IR operands into VPValue operands and set them in the
300 // new VPInstruction.
301 SmallVector<VPValue *, 4> VPOperands;
302 for (Value *Op : Inst->operands())
303 VPOperands.push_back(getOrCreateVPOperand(Op));
304
305 // Build VPInstruction for any arbitrary Instruction without specific
306 // representation in VPlan.
307 NewVPV = cast<VPInstruction>(
308 VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst));
309 }
310
311 IRDef2VPValue[Inst] = NewVPV;
312 }
313}
314
315// Main interface to build the plain CFG.
316void PlainCFGBuilder::buildPlainCFG() {
317 // 1. Scan the body of the loop in a topological order to visit each basic
318 // block after having visited its predecessor basic blocks. Create a VPBB for
319 // each BB and link it to its successor and predecessor VPBBs. Note that
320 // predecessors must be set in the same order as they are in the incomming IR.
321 // Otherwise, there might be problems with existing phi nodes and algorithm
322 // based on predecessors traversal.
323
324 // Loop PH needs to be explicitly visited since it's not taken into account by
325 // LoopBlocksDFS.
326 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
327 assert((ThePreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
328 "Unexpected loop preheader");
329 // buildPlainCFG needs to be called after createInitialVPlan, which creates
330 // the initial skeleton (including the preheader VPBB). buildPlainCFG builds
331 // the CFG for the loop nest and hooks it up to the initial skeleton.
332 VPBasicBlock *ThePreheaderVPBB = Plan.getEntry();
333 BB2VPBB[ThePreheaderBB] = ThePreheaderVPBB;
334 ThePreheaderVPBB->setName("vector.ph");
335 for (auto &I : *ThePreheaderBB) {
336 if (I.getType()->isVoidTy())
337 continue;
338 IRDef2VPValue[&I] = Plan.getVPValueOrAddLiveIn(&I);
339 }
340 // Create region (and header block) for the outer loop, so that we can link
341 // PH->Region.
342 VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
343 HeaderVPBB->setName("vector.body");
344 ThePreheaderVPBB->setOneSuccessor(HeaderVPBB->getParent());
345
346 LoopBlocksRPO RPO(TheLoop);
347 RPO.perform(LI);
348
349 for (BasicBlock *BB : RPO) {
350 // Create or retrieve the VPBasicBlock for this BB and create its
351 // VPInstructions.
352 VPBasicBlock *VPBB = getOrCreateVPBB(BB);
353 VPRegionBlock *Region = VPBB->getParent();
354 createVPInstructionsForVPBB(VPBB, BB);
355 Loop *LoopForBB = LI->getLoopFor(BB);
356 // Set VPBB predecessors in the same order as they are in the incoming BB.
357 if (!isHeaderBB(BB, LoopForBB))
358 setVPBBPredsFromBB(VPBB, BB);
359 else {
360 // BB is a loop header, set the predecessor for the region.
361 assert(isHeaderVPBB(VPBB) && "isHeaderBB and isHeaderVPBB disagree");
362 setRegionPredsFromBB(Region, BB);
363 }
364
365 // Set VPBB successors. We create empty VPBBs for successors if they don't
366 // exist already. Recipes will be created when the successor is visited
367 // during the RPO traversal.
368 auto *BI = cast<BranchInst>(BB->getTerminator());
369 unsigned NumSuccs = succ_size(BB);
370 if (NumSuccs == 1) {
371 auto *Successor = getOrCreateVPBB(BB->getSingleSuccessor());
373 ? Successor->getParent()
374 : static_cast<VPBlockBase *>(Successor));
375 continue;
376 }
377 assert(BI->isConditional() && NumSuccs == 2 && BI->isConditional() &&
378 "block must have conditional branch with 2 successors");
379 // Look up the branch condition to get the corresponding VPValue
380 // representing the condition bit in VPlan (which may be in another VPBB).
381 assert(IRDef2VPValue.contains(BI->getCondition()) &&
382 "Missing condition bit in IRDef2VPValue!");
383 VPBasicBlock *Successor0 = getOrCreateVPBB(BI->getSuccessor(0));
384 VPBasicBlock *Successor1 = getOrCreateVPBB(BI->getSuccessor(1));
385 if (!LoopForBB || BB != LoopForBB->getLoopLatch()) {
386 VPBB->setTwoSuccessors(Successor0, Successor1);
387 continue;
388 }
389 // For a latch we need to set the successor of the region rather than that
390 // of VPBB and it should be set to the exit, i.e., non-header successor.
391 Region->setOneSuccessor(isHeaderVPBB(Successor0) ? Successor1 : Successor0);
392 Region->setExiting(VPBB);
393 }
394
395 // 2. Process outermost loop exit. We created an empty VPBB for the loop
396 // single exit BB during the RPO traversal of the loop body but Instructions
397 // weren't visited because it's not part of the loop.
398 BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
399 assert(LoopExitBB && "Loops with multiple exits are not supported.");
400 VPBasicBlock *LoopExitVPBB = BB2VPBB[LoopExitBB];
401 // Loop exit was already set as successor of the loop exiting BB.
402 // We only set its predecessor VPBB now.
403 setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB);
404
405 // 3. The whole CFG has been built at this point so all the input Values must
406 // have a VPlan couterpart. Fix VPlan phi nodes by adding their corresponding
407 // VPlan operands.
408 fixPhiNodes();
409}
410
411void VPlanHCFGBuilder::buildPlainCFG() {
412 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
413 PCFGBuilder.buildPlainCFG();
414}
415
416// Public interface to build a H-CFG.
418 // Build Top Region enclosing the plain CFG.
419 buildPlainCFG();
420 LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
421
422 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
423 Verifier.verifyHierarchicalCFG(TopRegion);
424
425 // Compute plain CFG dom tree for VPLInfo.
426 VPDomTree.recalculate(Plan);
427 LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
428 VPDomTree.print(dbgs()));
429}
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file provides a LoopVectorizationPlanner class.
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isHeaderBB(BasicBlock *BB, Loop *L)
static bool isHeaderVPBB(VPBasicBlock *VPBB)
This file defines the VPlanHCFGBuilder class which contains the public interface (buildHierarchicalCF...
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:296
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
This class represents an Operation in the Expression.
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
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:195
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
BlockT * getHeader() const
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
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:47
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:2253
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2321
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:420
VPRegionBlock * getParent()
Definition: VPlan.h:492
void setName(const Twine &newName)
Definition: VPlan.h:485
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:606
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition: VPlan.h:597
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
Definition: VPlan.h:586
void setParent(VPRegionBlock *P)
Definition: VPlan.h:503
VPlan-based builder utility analogous to IRBuilder.
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:1018
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2377
const VPBlockBase * getEntry() const
Definition: VPlan.h:2416
A recipe for handling header phis that are widened in the vector loop.
Definition: VPlan.h:1507
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:2474
void setName(const Twine &newName)
Definition: VPlan.h:2612
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:2668
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
NodeAddr< PhiNode * > Phi
Definition: RDFGraph.h:390
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)
unsigned succ_size(const MachineBasicBlock *BB)
void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const
Verify the invariants of the H-CFG starting from TopRegion.