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"
25#include "LoopVectorizationPlanner.h"
26#include "llvm/Analysis/LoopIterator.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.
52 DenseMap<BasicBlock *, VPBasicBlock *> BB2VPBB;
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.
57 SmallVector<PHINode *, 8> PhisToFix;
58
59 /// Maps loops in the original IR to their corresponding region.
60 DenseMap<Loop *, VPRegionBlock *> Loop2Region;
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(BB: 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(BB: 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.
105 SmallVector<VPBlockBase *, 2> VPBBPreds;
106 for (BasicBlock *Pred : predecessors(BB))
107 VPBBPreds.push_back(Elt: getOrCreateVPBB(BB: 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(BB: 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>(Val: VPVal);
130 assert(VPPhi->getNumOperands() == 0 &&
131 "Expected VPInstruction with no operands.");
132
133 Loop *L = LI->getLoopFor(BB: Phi->getParent());
134 if (isHeaderBB(BB: 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 IncomingV: getOrCreateVPOperand(IRVal: Phi->getIncomingValueForBlock(BB: LoopPred)),
141 IncomingBlock: BB2VPBB[LoopPred]);
142 BasicBlock *LoopLatch = L->getLoopLatch();
143 VPPhi->addIncoming(
144 IncomingV: getOrCreateVPOperand(IRVal: Phi->getIncomingValueForBlock(BB: LoopLatch)),
145 IncomingBlock: BB2VPBB[LoopLatch]);
146 continue;
147 }
148
149 for (unsigned I = 0; I != Phi->getNumOperands(); ++I)
150 VPPhi->addIncoming(IncomingV: getOrCreateVPOperand(IRVal: Phi->getIncomingValue(i: I)),
151 IncomingBlock: BB2VPBB[Phi->getIncomingBlock(i: I)]);
152 }
153}
154
155static bool isHeaderVPBB(VPBasicBlock *VPBB) {
156 return VPBB->getParent() && VPBB->getParent()->getEntry() == VPBB;
157}
158
159/// Return true of \p L loop is contained within \p OuterLoop.
160static bool doesContainLoop(const Loop *L, const Loop *OuterLoop) {
161 if (L->getLoopDepth() < OuterLoop->getLoopDepth())
162 return false;
163 const Loop *P = L;
164 while (P) {
165 if (P == OuterLoop)
166 return true;
167 P = P->getParentLoop();
168 }
169 return false;
170}
171
172// Create a new empty VPBasicBlock for an incoming BasicBlock in the region
173// corresponding to the containing loop or retrieve an existing one if it was
174// already created. If no region exists yet for the loop containing \p BB, a new
175// one is created.
176VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
177 if (auto *VPBB = BB2VPBB.lookup(Val: BB)) {
178 // Retrieve existing VPBB.
179 return VPBB;
180 }
181
182 // Create new VPBB.
183 StringRef Name = isHeaderBB(BB, L: TheLoop) ? "vector.body" : BB->getName();
184 LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << Name << "\n");
185 VPBasicBlock *VPBB = new VPBasicBlock(Name);
186 BB2VPBB[BB] = VPBB;
187
188 // Get or create a region for the loop containing BB.
189 Loop *LoopOfBB = LI->getLoopFor(BB);
190 if (!LoopOfBB || !doesContainLoop(L: LoopOfBB, OuterLoop: TheLoop))
191 return VPBB;
192
193 auto *RegionOfVPBB = Loop2Region.lookup(Val: LoopOfBB);
194 if (!isHeaderBB(BB, L: LoopOfBB)) {
195 assert(RegionOfVPBB &&
196 "Region should have been created by visiting header earlier");
197 VPBB->setParent(RegionOfVPBB);
198 return VPBB;
199 }
200
201 assert(!RegionOfVPBB &&
202 "First visit of a header basic block expects to register its region.");
203 // Handle a header - take care of its Region.
204 if (LoopOfBB == TheLoop) {
205 RegionOfVPBB = Plan.getVectorLoopRegion();
206 } else {
207 RegionOfVPBB = new VPRegionBlock(Name.str(), false /*isReplicator*/);
208 RegionOfVPBB->setParent(Loop2Region[LoopOfBB->getParentLoop()]);
209 }
210 RegionOfVPBB->setEntry(VPBB);
211 Loop2Region[LoopOfBB] = RegionOfVPBB;
212 return VPBB;
213}
214
215#ifndef NDEBUG
216// Return true if \p Val is considered an external definition. An external
217// definition is either:
218// 1. A Value that is not an Instruction. This will be refined in the future.
219// 2. An Instruction that is outside of the CFG snippet represented in VPlan,
220// i.e., is not part of: a) the loop nest, b) outermost loop PH and, c)
221// outermost loop exits.
222bool PlainCFGBuilder::isExternalDef(Value *Val) {
223 // All the Values that are not Instructions are considered external
224 // definitions for now.
225 Instruction *Inst = dyn_cast<Instruction>(Val);
226 if (!Inst)
227 return true;
228
229 BasicBlock *InstParent = Inst->getParent();
230 assert(InstParent && "Expected instruction parent.");
231
232 // Check whether Instruction definition is in loop PH.
233 BasicBlock *PH = TheLoop->getLoopPreheader();
234 assert(PH && "Expected loop pre-header.");
235
236 if (InstParent == PH)
237 // Instruction definition is in outermost loop PH.
238 return false;
239
240 // Check whether Instruction definition is in the loop exit.
241 BasicBlock *Exit = TheLoop->getUniqueExitBlock();
242 assert(Exit && "Expected loop with single exit.");
243 if (InstParent == Exit) {
244 // Instruction definition is in outermost loop exit.
245 return false;
246 }
247
248 // Check whether Instruction definition is in loop body.
249 return !TheLoop->contains(Inst);
250}
251#endif
252
253// Create a new VPValue or retrieve an existing one for the Instruction's
254// operand \p IRVal. This function must only be used to create/retrieve VPValues
255// for *Instruction's operands* and not to create regular VPInstruction's. For
256// the latter, please, look at 'createVPInstructionsForVPBB'.
257VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
258 auto VPValIt = IRDef2VPValue.find(Val: IRVal);
259 if (VPValIt != IRDef2VPValue.end())
260 // Operand has an associated VPInstruction or VPValue that was previously
261 // created.
262 return VPValIt->second;
263
264 // Operand doesn't have a previously created VPInstruction/VPValue. This
265 // means that operand is:
266 // A) a definition external to VPlan,
267 // B) any other Value without specific representation in VPlan.
268 // For now, we use VPValue to represent A and B and classify both as external
269 // definitions. We may introduce specific VPValue subclasses for them in the
270 // future.
271 assert(isExternalDef(IRVal) && "Expected external definition as operand.");
272
273 // A and B: Create VPValue and add it to the pool of external definitions and
274 // to the Value->VPValue map.
275 VPValue *NewVPVal = Plan.getOrAddLiveIn(V: IRVal);
276 IRDef2VPValue[IRVal] = NewVPVal;
277 return NewVPVal;
278}
279
280// Create new VPInstructions in a VPBasicBlock, given its BasicBlock
281// counterpart. This function must be invoked in RPO so that the operands of a
282// VPInstruction in \p BB have been visited before (except for Phi nodes).
283void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
284 BasicBlock *BB) {
285 VPIRBuilder.setInsertPoint(VPBB);
286 for (Instruction &InstRef : BB->instructionsWithoutDebug(SkipPseudoOp: false)) {
287 Instruction *Inst = &InstRef;
288
289 // There shouldn't be any VPValue for Inst at this point. Otherwise, we
290 // visited Inst when we shouldn't, breaking the RPO traversal order.
291 assert(!IRDef2VPValue.count(Inst) &&
292 "Instruction shouldn't have been visited.");
293
294 if (auto *Br = dyn_cast<BranchInst>(Val: Inst)) {
295 // Conditional branch instruction are represented using BranchOnCond
296 // recipes.
297 if (Br->isConditional()) {
298 VPValue *Cond = getOrCreateVPOperand(IRVal: Br->getCondition());
299 VPIRBuilder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cond}, Inst);
300 }
301
302 // Skip the rest of the Instruction processing for Branch instructions.
303 continue;
304 }
305
306 VPValue *NewVPV;
307 if (auto *Phi = dyn_cast<PHINode>(Val: Inst)) {
308 // Phi node's operands may have not been visited at this point. We create
309 // an empty VPInstruction that we will fix once the whole plain CFG has
310 // been built.
311 NewVPV = new VPWidenPHIRecipe(Phi);
312 VPBB->appendRecipe(Recipe: cast<VPWidenPHIRecipe>(Val: NewVPV));
313 PhisToFix.push_back(Elt: Phi);
314 } else {
315 // Translate LLVM-IR operands into VPValue operands and set them in the
316 // new VPInstruction.
317 SmallVector<VPValue *, 4> VPOperands;
318 for (Value *Op : Inst->operands())
319 VPOperands.push_back(Elt: getOrCreateVPOperand(IRVal: Op));
320
321 // Build VPInstruction for any arbitrary Instruction without specific
322 // representation in VPlan.
323 NewVPV = cast<VPInstruction>(
324 Val: VPIRBuilder.createNaryOp(Opcode: Inst->getOpcode(), Operands: VPOperands, Inst));
325 }
326
327 IRDef2VPValue[Inst] = NewVPV;
328 }
329}
330
331// Main interface to build the plain CFG.
332void PlainCFGBuilder::buildPlainCFG() {
333 // 0. Reuse the top-level region, vector-preheader and exit VPBBs from the
334 // skeleton. These were created directly rather than via getOrCreateVPBB(),
335 // revisit them now to update BB2VPBB. Note that header/entry and
336 // latch/exiting VPBB's of top-level region have yet to be created.
337 VPRegionBlock *TheRegion = Plan.getVectorLoopRegion();
338 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
339 assert((ThePreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
340 "Unexpected loop preheader");
341 auto *VectorPreheaderVPBB =
342 cast<VPBasicBlock>(Val: TheRegion->getSinglePredecessor());
343 // ThePreheaderBB conceptually corresponds to both Plan.getPreheader() (which
344 // wraps the original preheader BB) and Plan.getEntry() (which represents the
345 // new vector preheader); here we're interested in setting BB2VPBB to the
346 // latter.
347 BB2VPBB[ThePreheaderBB] = VectorPreheaderVPBB;
348 BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
349 Loop2Region[LI->getLoopFor(BB: TheLoop->getHeader())] = TheRegion;
350 assert(LoopExitBB && "Loops with multiple exits are not supported.");
351 BB2VPBB[LoopExitBB] = cast<VPBasicBlock>(Val: TheRegion->getSingleSuccessor());
352
353 // The existing vector region's entry and exiting VPBBs correspond to the loop
354 // header and latch.
355 VPBasicBlock *VectorHeaderVPBB = TheRegion->getEntryBasicBlock();
356 VPBasicBlock *VectorLatchVPBB = TheRegion->getExitingBasicBlock();
357 BB2VPBB[TheLoop->getHeader()] = VectorHeaderVPBB;
358 VectorHeaderVPBB->clearSuccessors();
359 VectorLatchVPBB->clearPredecessors();
360 if (TheLoop->getHeader() != TheLoop->getLoopLatch()) {
361 BB2VPBB[TheLoop->getLoopLatch()] = VectorLatchVPBB;
362 } else {
363 TheRegion->setExiting(VectorHeaderVPBB);
364 delete VectorLatchVPBB;
365 }
366
367 // 1. Scan the body of the loop in a topological order to visit each basic
368 // block after having visited its predecessor basic blocks. Create a VPBB for
369 // each BB and link it to its successor and predecessor VPBBs. Note that
370 // predecessors must be set in the same order as they are in the incomming IR.
371 // Otherwise, there might be problems with existing phi nodes and algorithm
372 // based on predecessors traversal.
373
374 // Loop PH needs to be explicitly visited since it's not taken into account by
375 // LoopBlocksDFS.
376 for (auto &I : *ThePreheaderBB) {
377 if (I.getType()->isVoidTy())
378 continue;
379 IRDef2VPValue[&I] = Plan.getOrAddLiveIn(V: &I);
380 }
381
382 LoopBlocksRPO RPO(TheLoop);
383 RPO.perform(LI);
384
385 for (BasicBlock *BB : RPO) {
386 // Create or retrieve the VPBasicBlock for this BB and create its
387 // VPInstructions.
388 VPBasicBlock *VPBB = getOrCreateVPBB(BB);
389 VPRegionBlock *Region = VPBB->getParent();
390 createVPInstructionsForVPBB(VPBB, BB);
391 Loop *LoopForBB = LI->getLoopFor(BB);
392 // Set VPBB predecessors in the same order as they are in the incoming BB.
393 if (!isHeaderBB(BB, L: LoopForBB)) {
394 setVPBBPredsFromBB(VPBB, BB);
395 } else {
396 // BB is a loop header, set the predecessor for the region, except for the
397 // top region, whose predecessor was set when creating VPlan's skeleton.
398 assert(isHeaderVPBB(VPBB) && "isHeaderBB and isHeaderVPBB disagree");
399 if (TheRegion != Region)
400 setRegionPredsFromBB(Region, BB);
401 }
402
403 // Set VPBB successors. We create empty VPBBs for successors if they don't
404 // exist already. Recipes will be created when the successor is visited
405 // during the RPO traversal.
406 auto *BI = cast<BranchInst>(Val: BB->getTerminator());
407 unsigned NumSuccs = succ_size(BB);
408 if (NumSuccs == 1) {
409 auto *Successor = getOrCreateVPBB(BB: BB->getSingleSuccessor());
410 VPBB->setOneSuccessor(isHeaderVPBB(VPBB: Successor)
411 ? Successor->getParent()
412 : static_cast<VPBlockBase *>(Successor));
413 continue;
414 }
415 assert(BI->isConditional() && NumSuccs == 2 && BI->isConditional() &&
416 "block must have conditional branch with 2 successors");
417 // Look up the branch condition to get the corresponding VPValue
418 // representing the condition bit in VPlan (which may be in another VPBB).
419 assert(IRDef2VPValue.contains(BI->getCondition()) &&
420 "Missing condition bit in IRDef2VPValue!");
421 VPBasicBlock *Successor0 = getOrCreateVPBB(BB: BI->getSuccessor(i: 0));
422 VPBasicBlock *Successor1 = getOrCreateVPBB(BB: BI->getSuccessor(i: 1));
423 if (!LoopForBB || BB != LoopForBB->getLoopLatch()) {
424 VPBB->setTwoSuccessors(IfTrue: Successor0, IfFalse: Successor1);
425 continue;
426 }
427 // For a latch we need to set the successor of the region rather than that
428 // of VPBB and it should be set to the exit, i.e., non-header successor,
429 // except for the top region, whose successor was set when creating VPlan's
430 // skeleton.
431 if (TheRegion != Region) {
432 Region->setOneSuccessor(isHeaderVPBB(VPBB: Successor0) ? Successor1
433 : Successor0);
434 Region->setExiting(VPBB);
435 }
436 }
437
438 // 2. The whole CFG has been built at this point so all the input Values must
439 // have a VPlan couterpart. Fix VPlan phi nodes by adding their corresponding
440 // VPlan operands.
441 fixPhiNodes();
442}
443
444void VPlanHCFGBuilder::buildPlainCFG() {
445 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
446 PCFGBuilder.buildPlainCFG();
447}
448
449// Public interface to build a H-CFG.
450void VPlanHCFGBuilder::buildHierarchicalCFG() {
451 // Build Top Region enclosing the plain CFG.
452 buildPlainCFG();
453 LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
454
455 // Compute plain CFG dom tree for VPLInfo.
456 VPDomTree.recalculate(Func&: Plan);
457 LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
458 VPDomTree.print(dbgs()));
459}
460