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: 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. 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. 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. 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. 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'. 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). 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. 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 327 VPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() { 328 PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan); 329 return PCFGBuilder.buildPlainCFG(); 330 } 331 332 // Public interface to build a H-CFG. 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