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