1336809Sdim//===-- VPlanHCFGBuilder.cpp ----------------------------------------------===// 2336809Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6336809Sdim// 7336809Sdim//===----------------------------------------------------------------------===// 8336809Sdim/// 9336809Sdim/// \file 10336809Sdim/// This file implements the construction of a VPlan-based Hierarchical CFG 11336809Sdim/// (H-CFG) for an incoming IR. This construction comprises the following 12336809Sdim/// components and steps: 13336809Sdim// 14336809Sdim/// 1. PlainCFGBuilder class: builds a plain VPBasicBlock-based CFG that 15336809Sdim/// faithfully represents the CFG in the incoming IR. A VPRegionBlock (Top 16336809Sdim/// Region) is created to enclose and serve as parent of all the VPBasicBlocks 17336809Sdim/// in the plain CFG. 18336809Sdim/// NOTE: At this point, there is a direct correspondence between all the 19336809Sdim/// VPBasicBlocks created for the initial plain CFG and the incoming 20336809Sdim/// BasicBlocks. However, this might change in the future. 21336809Sdim/// 22336809Sdim//===----------------------------------------------------------------------===// 23336809Sdim 24336809Sdim#include "VPlanHCFGBuilder.h" 25336809Sdim#include "LoopVectorizationPlanner.h" 26336809Sdim#include "llvm/Analysis/LoopIterator.h" 27336809Sdim 28336809Sdim#define DEBUG_TYPE "loop-vectorize" 29336809Sdim 30336809Sdimusing namespace llvm; 31336809Sdim 32336809Sdimnamespace { 33336809Sdim// Class that is used to build the plain CFG for the incoming IR. 34336809Sdimclass PlainCFGBuilder { 35336809Sdimprivate: 36336809Sdim // The outermost loop of the input loop nest considered for vectorization. 37336809Sdim Loop *TheLoop; 38336809Sdim 39336809Sdim // Loop Info analysis. 40336809Sdim LoopInfo *LI; 41336809Sdim 42336809Sdim // Vectorization plan that we are working on. 43336809Sdim VPlan &Plan; 44336809Sdim 45336809Sdim // Output Top Region. 46336809Sdim VPRegionBlock *TopRegion = nullptr; 47336809Sdim 48336809Sdim // Builder of the VPlan instruction-level representation. 49336809Sdim VPBuilder VPIRBuilder; 50336809Sdim 51336809Sdim // NOTE: The following maps are intentionally destroyed after the plain CFG 52336809Sdim // construction because subsequent VPlan-to-VPlan transformation may 53336809Sdim // invalidate them. 54336809Sdim // Map incoming BasicBlocks to their newly-created VPBasicBlocks. 55336809Sdim DenseMap<BasicBlock *, VPBasicBlock *> BB2VPBB; 56336809Sdim // Map incoming Value definitions to their newly-created VPValues. 57336809Sdim DenseMap<Value *, VPValue *> IRDef2VPValue; 58336809Sdim 59336809Sdim // Hold phi node's that need to be fixed once the plain CFG has been built. 60336809Sdim SmallVector<PHINode *, 8> PhisToFix; 61336809Sdim 62336809Sdim // Utility functions. 63336809Sdim void setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB); 64336809Sdim void fixPhiNodes(); 65336809Sdim VPBasicBlock *getOrCreateVPBB(BasicBlock *BB); 66353358Sdim#ifndef NDEBUG 67336809Sdim bool isExternalDef(Value *Val); 68353358Sdim#endif 69336809Sdim VPValue *getOrCreateVPOperand(Value *IRVal); 70336809Sdim void createVPInstructionsForVPBB(VPBasicBlock *VPBB, BasicBlock *BB); 71336809Sdim 72336809Sdimpublic: 73336809Sdim PlainCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P) 74336809Sdim : TheLoop(Lp), LI(LI), Plan(P) {} 75336809Sdim 76336809Sdim // Build the plain CFG and return its Top Region. 77336809Sdim VPRegionBlock *buildPlainCFG(); 78336809Sdim}; 79336809Sdim} // anonymous namespace 80336809Sdim 81336809Sdim// Set predecessors of \p VPBB in the same order as they are in \p BB. \p VPBB 82336809Sdim// must have no predecessors. 83336809Sdimvoid PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) { 84336809Sdim SmallVector<VPBlockBase *, 8> VPBBPreds; 85336809Sdim // Collect VPBB predecessors. 86336809Sdim for (BasicBlock *Pred : predecessors(BB)) 87336809Sdim VPBBPreds.push_back(getOrCreateVPBB(Pred)); 88336809Sdim 89336809Sdim VPBB->setPredecessors(VPBBPreds); 90336809Sdim} 91336809Sdim 92336809Sdim// Add operands to VPInstructions representing phi nodes from the input IR. 93336809Sdimvoid PlainCFGBuilder::fixPhiNodes() { 94336809Sdim for (auto *Phi : PhisToFix) { 95336809Sdim assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode."); 96336809Sdim VPValue *VPVal = IRDef2VPValue[Phi]; 97336809Sdim assert(isa<VPInstruction>(VPVal) && "Expected VPInstruction for phi node."); 98336809Sdim auto *VPPhi = cast<VPInstruction>(VPVal); 99336809Sdim assert(VPPhi->getNumOperands() == 0 && 100336809Sdim "Expected VPInstruction with no operands."); 101336809Sdim 102336809Sdim for (Value *Op : Phi->operands()) 103336809Sdim VPPhi->addOperand(getOrCreateVPOperand(Op)); 104336809Sdim } 105336809Sdim} 106336809Sdim 107336809Sdim// Create a new empty VPBasicBlock for an incoming BasicBlock or retrieve an 108336809Sdim// existing one if it was already created. 109336809SdimVPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) { 110336809Sdim auto BlockIt = BB2VPBB.find(BB); 111336809Sdim if (BlockIt != BB2VPBB.end()) 112336809Sdim // Retrieve existing VPBB. 113336809Sdim return BlockIt->second; 114336809Sdim 115336809Sdim // Create new VPBB. 116336809Sdim LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << BB->getName() << "\n"); 117336809Sdim VPBasicBlock *VPBB = new VPBasicBlock(BB->getName()); 118336809Sdim BB2VPBB[BB] = VPBB; 119336809Sdim VPBB->setParent(TopRegion); 120336809Sdim return VPBB; 121336809Sdim} 122336809Sdim 123353358Sdim#ifndef NDEBUG 124336809Sdim// Return true if \p Val is considered an external definition. An external 125336809Sdim// definition is either: 126336809Sdim// 1. A Value that is not an Instruction. This will be refined in the future. 127336809Sdim// 2. An Instruction that is outside of the CFG snippet represented in VPlan, 128336809Sdim// i.e., is not part of: a) the loop nest, b) outermost loop PH and, c) 129336809Sdim// outermost loop exits. 130336809Sdimbool PlainCFGBuilder::isExternalDef(Value *Val) { 131336809Sdim // All the Values that are not Instructions are considered external 132336809Sdim // definitions for now. 133336809Sdim Instruction *Inst = dyn_cast<Instruction>(Val); 134336809Sdim if (!Inst) 135336809Sdim return true; 136336809Sdim 137336809Sdim BasicBlock *InstParent = Inst->getParent(); 138336809Sdim assert(InstParent && "Expected instruction parent."); 139336809Sdim 140336809Sdim // Check whether Instruction definition is in loop PH. 141336809Sdim BasicBlock *PH = TheLoop->getLoopPreheader(); 142336809Sdim assert(PH && "Expected loop pre-header."); 143336809Sdim 144336809Sdim if (InstParent == PH) 145336809Sdim // Instruction definition is in outermost loop PH. 146336809Sdim return false; 147336809Sdim 148336809Sdim // Check whether Instruction definition is in the loop exit. 149336809Sdim BasicBlock *Exit = TheLoop->getUniqueExitBlock(); 150336809Sdim assert(Exit && "Expected loop with single exit."); 151336809Sdim if (InstParent == Exit) { 152336809Sdim // Instruction definition is in outermost loop exit. 153336809Sdim return false; 154336809Sdim } 155336809Sdim 156336809Sdim // Check whether Instruction definition is in loop body. 157336809Sdim return !TheLoop->contains(Inst); 158336809Sdim} 159353358Sdim#endif 160336809Sdim 161336809Sdim// Create a new VPValue or retrieve an existing one for the Instruction's 162336809Sdim// operand \p IRVal. This function must only be used to create/retrieve VPValues 163336809Sdim// for *Instruction's operands* and not to create regular VPInstruction's. For 164336809Sdim// the latter, please, look at 'createVPInstructionsForVPBB'. 165336809SdimVPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) { 166336809Sdim auto VPValIt = IRDef2VPValue.find(IRVal); 167336809Sdim if (VPValIt != IRDef2VPValue.end()) 168336809Sdim // Operand has an associated VPInstruction or VPValue that was previously 169336809Sdim // created. 170336809Sdim return VPValIt->second; 171336809Sdim 172336809Sdim // Operand doesn't have a previously created VPInstruction/VPValue. This 173336809Sdim // means that operand is: 174336809Sdim // A) a definition external to VPlan, 175336809Sdim // B) any other Value without specific representation in VPlan. 176336809Sdim // For now, we use VPValue to represent A and B and classify both as external 177336809Sdim // definitions. We may introduce specific VPValue subclasses for them in the 178336809Sdim // future. 179336809Sdim assert(isExternalDef(IRVal) && "Expected external definition as operand."); 180336809Sdim 181336809Sdim // A and B: Create VPValue and add it to the pool of external definitions and 182336809Sdim // to the Value->VPValue map. 183336809Sdim VPValue *NewVPVal = new VPValue(IRVal); 184336809Sdim Plan.addExternalDef(NewVPVal); 185336809Sdim IRDef2VPValue[IRVal] = NewVPVal; 186336809Sdim return NewVPVal; 187336809Sdim} 188336809Sdim 189336809Sdim// Create new VPInstructions in a VPBasicBlock, given its BasicBlock 190336809Sdim// counterpart. This function must be invoked in RPO so that the operands of a 191336809Sdim// VPInstruction in \p BB have been visited before (except for Phi nodes). 192336809Sdimvoid PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB, 193336809Sdim BasicBlock *BB) { 194336809Sdim VPIRBuilder.setInsertPoint(VPBB); 195336809Sdim for (Instruction &InstRef : *BB) { 196336809Sdim Instruction *Inst = &InstRef; 197336809Sdim 198336809Sdim // There shouldn't be any VPValue for Inst at this point. Otherwise, we 199336809Sdim // visited Inst when we shouldn't, breaking the RPO traversal order. 200336809Sdim assert(!IRDef2VPValue.count(Inst) && 201336809Sdim "Instruction shouldn't have been visited."); 202336809Sdim 203336809Sdim if (auto *Br = dyn_cast<BranchInst>(Inst)) { 204336809Sdim // Branch instruction is not explicitly represented in VPlan but we need 205336809Sdim // to represent its condition bit when it's conditional. 206336809Sdim if (Br->isConditional()) 207336809Sdim getOrCreateVPOperand(Br->getCondition()); 208336809Sdim 209336809Sdim // Skip the rest of the Instruction processing for Branch instructions. 210336809Sdim continue; 211336809Sdim } 212336809Sdim 213336809Sdim VPInstruction *NewVPInst; 214336809Sdim if (auto *Phi = dyn_cast<PHINode>(Inst)) { 215336809Sdim // Phi node's operands may have not been visited at this point. We create 216336809Sdim // an empty VPInstruction that we will fix once the whole plain CFG has 217336809Sdim // been built. 218336809Sdim NewVPInst = cast<VPInstruction>(VPIRBuilder.createNaryOp( 219336809Sdim Inst->getOpcode(), {} /*No operands*/, Inst)); 220336809Sdim PhisToFix.push_back(Phi); 221336809Sdim } else { 222336809Sdim // Translate LLVM-IR operands into VPValue operands and set them in the 223336809Sdim // new VPInstruction. 224336809Sdim SmallVector<VPValue *, 4> VPOperands; 225336809Sdim for (Value *Op : Inst->operands()) 226336809Sdim VPOperands.push_back(getOrCreateVPOperand(Op)); 227336809Sdim 228336809Sdim // Build VPInstruction for any arbitraty Instruction without specific 229336809Sdim // representation in VPlan. 230336809Sdim NewVPInst = cast<VPInstruction>( 231336809Sdim VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst)); 232336809Sdim } 233336809Sdim 234336809Sdim IRDef2VPValue[Inst] = NewVPInst; 235336809Sdim } 236336809Sdim} 237336809Sdim 238336809Sdim// Main interface to build the plain CFG. 239336809SdimVPRegionBlock *PlainCFGBuilder::buildPlainCFG() { 240336809Sdim // 1. Create the Top Region. It will be the parent of all VPBBs. 241336809Sdim TopRegion = new VPRegionBlock("TopRegion", false /*isReplicator*/); 242336809Sdim 243336809Sdim // 2. Scan the body of the loop in a topological order to visit each basic 244336809Sdim // block after having visited its predecessor basic blocks. Create a VPBB for 245336809Sdim // each BB and link it to its successor and predecessor VPBBs. Note that 246336809Sdim // predecessors must be set in the same order as they are in the incomming IR. 247336809Sdim // Otherwise, there might be problems with existing phi nodes and algorithm 248336809Sdim // based on predecessors traversal. 249336809Sdim 250336809Sdim // Loop PH needs to be explicitly visited since it's not taken into account by 251336809Sdim // LoopBlocksDFS. 252336809Sdim BasicBlock *PreheaderBB = TheLoop->getLoopPreheader(); 253336809Sdim assert((PreheaderBB->getTerminator()->getNumSuccessors() == 1) && 254336809Sdim "Unexpected loop preheader"); 255336809Sdim VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(PreheaderBB); 256336809Sdim createVPInstructionsForVPBB(PreheaderVPBB, PreheaderBB); 257336809Sdim // Create empty VPBB for Loop H so that we can link PH->H. 258336809Sdim VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader()); 259336809Sdim // Preheader's predecessors will be set during the loop RPO traversal below. 260336809Sdim PreheaderVPBB->setOneSuccessor(HeaderVPBB); 261336809Sdim 262336809Sdim LoopBlocksRPO RPO(TheLoop); 263336809Sdim RPO.perform(LI); 264336809Sdim 265336809Sdim for (BasicBlock *BB : RPO) { 266336809Sdim // Create or retrieve the VPBasicBlock for this BB and create its 267336809Sdim // VPInstructions. 268336809Sdim VPBasicBlock *VPBB = getOrCreateVPBB(BB); 269336809Sdim createVPInstructionsForVPBB(VPBB, BB); 270336809Sdim 271336809Sdim // Set VPBB successors. We create empty VPBBs for successors if they don't 272336809Sdim // exist already. Recipes will be created when the successor is visited 273336809Sdim // during the RPO traversal. 274344779Sdim Instruction *TI = BB->getTerminator(); 275336809Sdim assert(TI && "Terminator expected."); 276336809Sdim unsigned NumSuccs = TI->getNumSuccessors(); 277336809Sdim 278336809Sdim if (NumSuccs == 1) { 279336809Sdim VPBasicBlock *SuccVPBB = getOrCreateVPBB(TI->getSuccessor(0)); 280336809Sdim assert(SuccVPBB && "VPBB Successor not found."); 281336809Sdim VPBB->setOneSuccessor(SuccVPBB); 282336809Sdim } else if (NumSuccs == 2) { 283336809Sdim VPBasicBlock *SuccVPBB0 = getOrCreateVPBB(TI->getSuccessor(0)); 284336809Sdim assert(SuccVPBB0 && "Successor 0 not found."); 285336809Sdim VPBasicBlock *SuccVPBB1 = getOrCreateVPBB(TI->getSuccessor(1)); 286336809Sdim assert(SuccVPBB1 && "Successor 1 not found."); 287336809Sdim 288336809Sdim // Get VPBB's condition bit. 289336809Sdim assert(isa<BranchInst>(TI) && "Unsupported terminator!"); 290336809Sdim auto *Br = cast<BranchInst>(TI); 291336809Sdim Value *BrCond = Br->getCondition(); 292336809Sdim // Look up the branch condition to get the corresponding VPValue 293336809Sdim // representing the condition bit in VPlan (which may be in another VPBB). 294336809Sdim assert(IRDef2VPValue.count(BrCond) && 295336809Sdim "Missing condition bit in IRDef2VPValue!"); 296336809Sdim VPValue *VPCondBit = IRDef2VPValue[BrCond]; 297336809Sdim 298336809Sdim // Link successors using condition bit. 299336809Sdim VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1, VPCondBit); 300336809Sdim } else 301336809Sdim llvm_unreachable("Number of successors not supported."); 302336809Sdim 303336809Sdim // Set VPBB predecessors in the same order as they are in the incoming BB. 304336809Sdim setVPBBPredsFromBB(VPBB, BB); 305336809Sdim } 306336809Sdim 307336809Sdim // 3. Process outermost loop exit. We created an empty VPBB for the loop 308336809Sdim // single exit BB during the RPO traversal of the loop body but Instructions 309336809Sdim // weren't visited because it's not part of the the loop. 310336809Sdim BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock(); 311336809Sdim assert(LoopExitBB && "Loops with multiple exits are not supported."); 312336809Sdim VPBasicBlock *LoopExitVPBB = BB2VPBB[LoopExitBB]; 313336809Sdim createVPInstructionsForVPBB(LoopExitVPBB, LoopExitBB); 314336809Sdim // Loop exit was already set as successor of the loop exiting BB. 315336809Sdim // We only set its predecessor VPBB now. 316336809Sdim setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB); 317336809Sdim 318336809Sdim // 4. The whole CFG has been built at this point so all the input Values must 319336809Sdim // have a VPlan couterpart. Fix VPlan phi nodes by adding their corresponding 320336809Sdim // VPlan operands. 321336809Sdim fixPhiNodes(); 322336809Sdim 323336809Sdim // 5. Final Top Region setup. Set outermost loop pre-header and single exit as 324336809Sdim // Top Region entry and exit. 325336809Sdim TopRegion->setEntry(PreheaderVPBB); 326336809Sdim TopRegion->setExit(LoopExitVPBB); 327336809Sdim return TopRegion; 328336809Sdim} 329336809Sdim 330337149SdimVPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() { 331337149Sdim PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan); 332337149Sdim return PCFGBuilder.buildPlainCFG(); 333337149Sdim} 334337149Sdim 335336809Sdim// Public interface to build a H-CFG. 336337149Sdimvoid VPlanHCFGBuilder::buildHierarchicalCFG() { 337336809Sdim // Build Top Region enclosing the plain CFG and set it as VPlan entry. 338337149Sdim VPRegionBlock *TopRegion = buildPlainCFG(); 339336809Sdim Plan.setEntry(TopRegion); 340336809Sdim LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan); 341336809Sdim 342336809Sdim Verifier.verifyHierarchicalCFG(TopRegion); 343337149Sdim 344337149Sdim // Compute plain CFG dom tree for VPLInfo. 345337149Sdim VPDomTree.recalculate(*TopRegion); 346337149Sdim LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n"; 347337149Sdim VPDomTree.print(dbgs())); 348337149Sdim 349337149Sdim // Compute VPLInfo and keep it in Plan. 350337149Sdim VPLoopInfo &VPLInfo = Plan.getVPLoopInfo(); 351337149Sdim VPLInfo.analyze(VPDomTree); 352337149Sdim LLVM_DEBUG(dbgs() << "VPLoop Info After buildPlainCFG:\n"; 353337149Sdim VPLInfo.print(dbgs())); 354336809Sdim} 355