1 //===-- VPlanHCFGBuilder.cpp ----------------------------------------------===//
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 implements the construction of a VPlan-based Hierarchical CFG
12 /// (H-CFG) for an incoming IR. This construction comprises the following
13 /// components and steps:
14 //
15 /// 1. PlainCFGBuilder class: builds a plain VPBasicBlock-based CFG that
16 /// faithfully represents the CFG in the incoming IR. A VPRegionBlock (Top
17 /// Region) is created to enclose and serve as parent of all the VPBasicBlocks
18 /// in the plain CFG.
19 /// NOTE: At this point, there is a direct correspondence between all the
20 /// VPBasicBlocks created for the initial plain CFG and the incoming
21 /// BasicBlocks. However, this might change in the future.
22 ///
23 //===----------------------------------------------------------------------===//
24
25 #include "VPlanHCFGBuilder.h"
26 #include "LoopVectorizationPlanner.h"
27 #include "llvm/Analysis/LoopIterator.h"
28
29 #define DEBUG_TYPE "loop-vectorize"
30
31 using namespace llvm;
32
33 namespace {
34 // Class that is used to build the plain CFG for the incoming IR.
35 class PlainCFGBuilder {
36 private:
37 // The outermost loop of the input loop nest considered for vectorization.
38 Loop *TheLoop;
39
40 // Loop Info analysis.
41 LoopInfo *LI;
42
43 // Vectorization plan that we are working on.
44 VPlan &Plan;
45
46 // Output Top Region.
47 VPRegionBlock *TopRegion = nullptr;
48
49 // Builder of the VPlan instruction-level representation.
50 VPBuilder VPIRBuilder;
51
52 // NOTE: The following maps are intentionally destroyed after the plain CFG
53 // construction because subsequent VPlan-to-VPlan transformation may
54 // invalidate them.
55 // Map incoming BasicBlocks to their newly-created VPBasicBlocks.
56 DenseMap<BasicBlock *, VPBasicBlock *> BB2VPBB;
57 // Map incoming Value definitions to their newly-created VPValues.
58 DenseMap<Value *, VPValue *> IRDef2VPValue;
59
60 // Hold phi node's that need to be fixed once the plain CFG has been built.
61 SmallVector<PHINode *, 8> PhisToFix;
62
63 // Utility functions.
64 void setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB);
65 void fixPhiNodes();
66 VPBasicBlock *getOrCreateVPBB(BasicBlock *BB);
67 bool isExternalDef(Value *Val);
68 VPValue *getOrCreateVPOperand(Value *IRVal);
69 void createVPInstructionsForVPBB(VPBasicBlock *VPBB, BasicBlock *BB);
70
71 public:
PlainCFGBuilder(Loop * Lp,LoopInfo * LI,VPlan & P)72 PlainCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
73 : TheLoop(Lp), LI(LI), Plan(P) {}
74
75 // Build the plain CFG and return its Top Region.
76 VPRegionBlock *buildPlainCFG();
77 };
78 } // anonymous namespace
79
80 // Set predecessors of \p VPBB in the same order as they are in \p BB. \p VPBB
81 // must have no predecessors.
setVPBBPredsFromBB(VPBasicBlock * VPBB,BasicBlock * BB)82 void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) {
83 SmallVector<VPBlockBase *, 8> VPBBPreds;
84 // Collect VPBB predecessors.
85 for (BasicBlock *Pred : predecessors(BB))
86 VPBBPreds.push_back(getOrCreateVPBB(Pred));
87
88 VPBB->setPredecessors(VPBBPreds);
89 }
90
91 // Add operands to VPInstructions representing phi nodes from the input IR.
fixPhiNodes()92 void PlainCFGBuilder::fixPhiNodes() {
93 for (auto *Phi : PhisToFix) {
94 assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
95 VPValue *VPVal = IRDef2VPValue[Phi];
96 assert(isa<VPInstruction>(VPVal) && "Expected VPInstruction for phi node.");
97 auto *VPPhi = cast<VPInstruction>(VPVal);
98 assert(VPPhi->getNumOperands() == 0 &&
99 "Expected VPInstruction with no operands.");
100
101 for (Value *Op : Phi->operands())
102 VPPhi->addOperand(getOrCreateVPOperand(Op));
103 }
104 }
105
106 // Create a new empty VPBasicBlock for an incoming BasicBlock or retrieve an
107 // existing one if it was already created.
getOrCreateVPBB(BasicBlock * BB)108 VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
109 auto BlockIt = BB2VPBB.find(BB);
110 if (BlockIt != BB2VPBB.end())
111 // Retrieve existing VPBB.
112 return BlockIt->second;
113
114 // Create new VPBB.
115 LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << BB->getName() << "\n");
116 VPBasicBlock *VPBB = new VPBasicBlock(BB->getName());
117 BB2VPBB[BB] = VPBB;
118 VPBB->setParent(TopRegion);
119 return VPBB;
120 }
121
122 // Return true if \p Val is considered an external definition. An external
123 // definition is either:
124 // 1. A Value that is not an Instruction. This will be refined in the future.
125 // 2. An Instruction that is outside of the CFG snippet represented in VPlan,
126 // i.e., is not part of: a) the loop nest, b) outermost loop PH and, c)
127 // outermost loop exits.
isExternalDef(Value * Val)128 bool PlainCFGBuilder::isExternalDef(Value *Val) {
129 // All the Values that are not Instructions are considered external
130 // definitions for now.
131 Instruction *Inst = dyn_cast<Instruction>(Val);
132 if (!Inst)
133 return true;
134
135 BasicBlock *InstParent = Inst->getParent();
136 assert(InstParent && "Expected instruction parent.");
137
138 // Check whether Instruction definition is in loop PH.
139 BasicBlock *PH = TheLoop->getLoopPreheader();
140 assert(PH && "Expected loop pre-header.");
141
142 if (InstParent == PH)
143 // Instruction definition is in outermost loop PH.
144 return false;
145
146 // Check whether Instruction definition is in the loop exit.
147 BasicBlock *Exit = TheLoop->getUniqueExitBlock();
148 assert(Exit && "Expected loop with single exit.");
149 if (InstParent == Exit) {
150 // Instruction definition is in outermost loop exit.
151 return false;
152 }
153
154 // Check whether Instruction definition is in loop body.
155 return !TheLoop->contains(Inst);
156 }
157
158 // Create a new VPValue or retrieve an existing one for the Instruction's
159 // operand \p IRVal. This function must only be used to create/retrieve VPValues
160 // for *Instruction's operands* and not to create regular VPInstruction's. For
161 // the latter, please, look at 'createVPInstructionsForVPBB'.
getOrCreateVPOperand(Value * IRVal)162 VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
163 auto VPValIt = IRDef2VPValue.find(IRVal);
164 if (VPValIt != IRDef2VPValue.end())
165 // Operand has an associated VPInstruction or VPValue that was previously
166 // created.
167 return VPValIt->second;
168
169 // Operand doesn't have a previously created VPInstruction/VPValue. This
170 // means that operand is:
171 // A) a definition external to VPlan,
172 // B) any other Value without specific representation in VPlan.
173 // For now, we use VPValue to represent A and B and classify both as external
174 // definitions. We may introduce specific VPValue subclasses for them in the
175 // future.
176 assert(isExternalDef(IRVal) && "Expected external definition as operand.");
177
178 // A and B: Create VPValue and add it to the pool of external definitions and
179 // to the Value->VPValue map.
180 VPValue *NewVPVal = new VPValue(IRVal);
181 Plan.addExternalDef(NewVPVal);
182 IRDef2VPValue[IRVal] = NewVPVal;
183 return NewVPVal;
184 }
185
186 // Create new VPInstructions in a VPBasicBlock, given its BasicBlock
187 // counterpart. This function must be invoked in RPO so that the operands of a
188 // VPInstruction in \p BB have been visited before (except for Phi nodes).
createVPInstructionsForVPBB(VPBasicBlock * VPBB,BasicBlock * BB)189 void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
190 BasicBlock *BB) {
191 VPIRBuilder.setInsertPoint(VPBB);
192 for (Instruction &InstRef : *BB) {
193 Instruction *Inst = &InstRef;
194
195 // There shouldn't be any VPValue for Inst at this point. Otherwise, we
196 // visited Inst when we shouldn't, breaking the RPO traversal order.
197 assert(!IRDef2VPValue.count(Inst) &&
198 "Instruction shouldn't have been visited.");
199
200 if (auto *Br = dyn_cast<BranchInst>(Inst)) {
201 // Branch instruction is not explicitly represented in VPlan but we need
202 // to represent its condition bit when it's conditional.
203 if (Br->isConditional())
204 getOrCreateVPOperand(Br->getCondition());
205
206 // Skip the rest of the Instruction processing for Branch instructions.
207 continue;
208 }
209
210 VPInstruction *NewVPInst;
211 if (auto *Phi = dyn_cast<PHINode>(Inst)) {
212 // Phi node's operands may have not been visited at this point. We create
213 // an empty VPInstruction that we will fix once the whole plain CFG has
214 // been built.
215 NewVPInst = cast<VPInstruction>(VPIRBuilder.createNaryOp(
216 Inst->getOpcode(), {} /*No operands*/, Inst));
217 PhisToFix.push_back(Phi);
218 } else {
219 // Translate LLVM-IR operands into VPValue operands and set them in the
220 // new VPInstruction.
221 SmallVector<VPValue *, 4> VPOperands;
222 for (Value *Op : Inst->operands())
223 VPOperands.push_back(getOrCreateVPOperand(Op));
224
225 // Build VPInstruction for any arbitraty Instruction without specific
226 // representation in VPlan.
227 NewVPInst = cast<VPInstruction>(
228 VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst));
229 }
230
231 IRDef2VPValue[Inst] = NewVPInst;
232 }
233 }
234
235 // Main interface to build the plain CFG.
buildPlainCFG()236 VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
237 // 1. Create the Top Region. It will be the parent of all VPBBs.
238 TopRegion = new VPRegionBlock("TopRegion", false /*isReplicator*/);
239
240 // 2. Scan the body of the loop in a topological order to visit each basic
241 // block after having visited its predecessor basic blocks. Create a VPBB for
242 // each BB and link it to its successor and predecessor VPBBs. Note that
243 // predecessors must be set in the same order as they are in the incomming IR.
244 // Otherwise, there might be problems with existing phi nodes and algorithm
245 // based on predecessors traversal.
246
247 // Loop PH needs to be explicitly visited since it's not taken into account by
248 // LoopBlocksDFS.
249 BasicBlock *PreheaderBB = TheLoop->getLoopPreheader();
250 assert((PreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
251 "Unexpected loop preheader");
252 VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(PreheaderBB);
253 createVPInstructionsForVPBB(PreheaderVPBB, PreheaderBB);
254 // Create empty VPBB for Loop H so that we can link PH->H.
255 VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
256 // Preheader's predecessors will be set during the loop RPO traversal below.
257 PreheaderVPBB->setOneSuccessor(HeaderVPBB);
258
259 LoopBlocksRPO RPO(TheLoop);
260 RPO.perform(LI);
261
262 for (BasicBlock *BB : RPO) {
263 // Create or retrieve the VPBasicBlock for this BB and create its
264 // VPInstructions.
265 VPBasicBlock *VPBB = getOrCreateVPBB(BB);
266 createVPInstructionsForVPBB(VPBB, BB);
267
268 // Set VPBB successors. We create empty VPBBs for successors if they don't
269 // exist already. Recipes will be created when the successor is visited
270 // during the RPO traversal.
271 TerminatorInst *TI = BB->getTerminator();
272 assert(TI && "Terminator expected.");
273 unsigned NumSuccs = TI->getNumSuccessors();
274
275 if (NumSuccs == 1) {
276 VPBasicBlock *SuccVPBB = getOrCreateVPBB(TI->getSuccessor(0));
277 assert(SuccVPBB && "VPBB Successor not found.");
278 VPBB->setOneSuccessor(SuccVPBB);
279 } else if (NumSuccs == 2) {
280 VPBasicBlock *SuccVPBB0 = getOrCreateVPBB(TI->getSuccessor(0));
281 assert(SuccVPBB0 && "Successor 0 not found.");
282 VPBasicBlock *SuccVPBB1 = getOrCreateVPBB(TI->getSuccessor(1));
283 assert(SuccVPBB1 && "Successor 1 not found.");
284
285 // Get VPBB's condition bit.
286 assert(isa<BranchInst>(TI) && "Unsupported terminator!");
287 auto *Br = cast<BranchInst>(TI);
288 Value *BrCond = Br->getCondition();
289 // Look up the branch condition to get the corresponding VPValue
290 // representing the condition bit in VPlan (which may be in another VPBB).
291 assert(IRDef2VPValue.count(BrCond) &&
292 "Missing condition bit in IRDef2VPValue!");
293 VPValue *VPCondBit = IRDef2VPValue[BrCond];
294
295 // Link successors using condition bit.
296 VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1, VPCondBit);
297 } else
298 llvm_unreachable("Number of successors not supported.");
299
300 // Set VPBB predecessors in the same order as they are in the incoming BB.
301 setVPBBPredsFromBB(VPBB, BB);
302 }
303
304 // 3. Process outermost loop exit. We created an empty VPBB for the loop
305 // single exit BB during the RPO traversal of the loop body but Instructions
306 // weren't visited because it's not part of the the loop.
307 BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
308 assert(LoopExitBB && "Loops with multiple exits are not supported.");
309 VPBasicBlock *LoopExitVPBB = BB2VPBB[LoopExitBB];
310 createVPInstructionsForVPBB(LoopExitVPBB, LoopExitBB);
311 // Loop exit was already set as successor of the loop exiting BB.
312 // We only set its predecessor VPBB now.
313 setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB);
314
315 // 4. The whole CFG has been built at this point so all the input Values must
316 // have a VPlan couterpart. Fix VPlan phi nodes by adding their corresponding
317 // VPlan operands.
318 fixPhiNodes();
319
320 // 5. Final Top Region setup. Set outermost loop pre-header and single exit as
321 // Top Region entry and exit.
322 TopRegion->setEntry(PreheaderVPBB);
323 TopRegion->setExit(LoopExitVPBB);
324 return TopRegion;
325 }
326
buildPlainCFG()327 VPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() {
328 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
329 return PCFGBuilder.buildPlainCFG();
330 }
331
332 // Public interface to build a H-CFG.
buildHierarchicalCFG()333 void VPlanHCFGBuilder::buildHierarchicalCFG() {
334 // Build Top Region enclosing the plain CFG and set it as VPlan entry.
335 VPRegionBlock *TopRegion = buildPlainCFG();
336 Plan.setEntry(TopRegion);
337 LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
338
339 Verifier.verifyHierarchicalCFG(TopRegion);
340
341 // Compute plain CFG dom tree for VPLInfo.
342 VPDomTree.recalculate(*TopRegion);
343 LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
344 VPDomTree.print(dbgs()));
345
346 // Compute VPLInfo and keep it in Plan.
347 VPLoopInfo &VPLInfo = Plan.getVPLoopInfo();
348 VPLInfo.analyze(VPDomTree);
349 LLVM_DEBUG(dbgs() << "VPLoop Info After buildPlainCFG:\n";
350 VPLInfo.print(dbgs()));
351 }
352