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 30 using namespace llvm; 31 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; 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 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 72 public: 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. 84 void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) { 85 SmallVector<VPBlockBase *, 8> VPBBPreds; 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. 94 void 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. 114 VPBasicBlock *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. 146 bool 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'. 181 VPValue *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). 207 void 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( 224 new VPInstruction(VPInstruction::BranchOnCond, {Cond})); 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. 257 VPBasicBlock *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); 365 VPBlockUtils::connectBlocks(Region, ExitVPBB); 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 378 VPBasicBlock *VPlanHCFGBuilder::buildPlainCFG() { 379 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan); 380 return PCFGBuilder.buildPlainCFG(); 381 } 382 383 // Public interface to build a H-CFG. 384 void VPlanHCFGBuilder::buildHierarchicalCFG() { 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 } 398