1 //===- VPlan.cpp - Vectorizer Plan ----------------------------------------===// 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 is the LLVM vectorization plan. It represents a candidate for 11 /// vectorization, allowing to plan and optimize how to vectorize a given loop 12 /// before generating LLVM-IR. 13 /// The vectorizer uses vectorization plans to estimate the costs of potential 14 /// candidates and if profitable to execute the desired plan, generating vector 15 /// LLVM-IR code. 16 /// 17 //===----------------------------------------------------------------------===// 18 19 #include "VPlan.h" 20 #include "VPlanCFG.h" 21 #include "VPlanDominatorTree.h" 22 #include "VPlanPatternMatch.h" 23 #include "llvm/ADT/PostOrderIterator.h" 24 #include "llvm/ADT/STLExtras.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/StringExtras.h" 27 #include "llvm/ADT/Twine.h" 28 #include "llvm/Analysis/LoopInfo.h" 29 #include "llvm/IR/BasicBlock.h" 30 #include "llvm/IR/CFG.h" 31 #include "llvm/IR/IRBuilder.h" 32 #include "llvm/IR/Instruction.h" 33 #include "llvm/IR/Instructions.h" 34 #include "llvm/IR/Type.h" 35 #include "llvm/IR/Value.h" 36 #include "llvm/Support/Casting.h" 37 #include "llvm/Support/CommandLine.h" 38 #include "llvm/Support/Debug.h" 39 #include "llvm/Support/GenericDomTreeConstruction.h" 40 #include "llvm/Support/GraphWriter.h" 41 #include "llvm/Support/raw_ostream.h" 42 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 43 #include "llvm/Transforms/Utils/LoopVersioning.h" 44 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 45 #include <cassert> 46 #include <string> 47 #include <vector> 48 49 using namespace llvm; 50 using namespace llvm::VPlanPatternMatch; 51 52 namespace llvm { 53 extern cl::opt<bool> EnableVPlanNativePath; 54 } 55 56 #define DEBUG_TYPE "vplan" 57 58 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 59 raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) { 60 const VPInstruction *Instr = dyn_cast<VPInstruction>(&V); 61 VPSlotTracker SlotTracker( 62 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr); 63 V.print(OS, SlotTracker); 64 return OS; 65 } 66 #endif 67 68 Value *VPLane::getAsRuntimeExpr(IRBuilderBase &Builder, 69 const ElementCount &VF) const { 70 switch (LaneKind) { 71 case VPLane::Kind::ScalableLast: 72 // Lane = RuntimeVF - VF.getKnownMinValue() + Lane 73 return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF), 74 Builder.getInt32(VF.getKnownMinValue() - Lane)); 75 case VPLane::Kind::First: 76 return Builder.getInt32(Lane); 77 } 78 llvm_unreachable("Unknown lane kind"); 79 } 80 81 VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def) 82 : SubclassID(SC), UnderlyingVal(UV), Def(Def) { 83 if (Def) 84 Def->addDefinedValue(this); 85 } 86 87 VPValue::~VPValue() { 88 assert(Users.empty() && "trying to delete a VPValue with remaining users"); 89 if (Def) 90 Def->removeDefinedValue(this); 91 } 92 93 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 94 void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const { 95 if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def)) 96 R->print(OS, "", SlotTracker); 97 else 98 printAsOperand(OS, SlotTracker); 99 } 100 101 void VPValue::dump() const { 102 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def); 103 VPSlotTracker SlotTracker( 104 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr); 105 print(dbgs(), SlotTracker); 106 dbgs() << "\n"; 107 } 108 109 void VPDef::dump() const { 110 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this); 111 VPSlotTracker SlotTracker( 112 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr); 113 print(dbgs(), "", SlotTracker); 114 dbgs() << "\n"; 115 } 116 #endif 117 118 VPRecipeBase *VPValue::getDefiningRecipe() { 119 return cast_or_null<VPRecipeBase>(Def); 120 } 121 122 const VPRecipeBase *VPValue::getDefiningRecipe() const { 123 return cast_or_null<VPRecipeBase>(Def); 124 } 125 126 // Get the top-most entry block of \p Start. This is the entry block of the 127 // containing VPlan. This function is templated to support both const and non-const blocks 128 template <typename T> static T *getPlanEntry(T *Start) { 129 T *Next = Start; 130 T *Current = Start; 131 while ((Next = Next->getParent())) 132 Current = Next; 133 134 SmallSetVector<T *, 8> WorkList; 135 WorkList.insert(Current); 136 137 for (unsigned i = 0; i < WorkList.size(); i++) { 138 T *Current = WorkList[i]; 139 if (Current->getNumPredecessors() == 0) 140 return Current; 141 auto &Predecessors = Current->getPredecessors(); 142 WorkList.insert(Predecessors.begin(), Predecessors.end()); 143 } 144 145 llvm_unreachable("VPlan without any entry node without predecessors"); 146 } 147 148 VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; } 149 150 const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; } 151 152 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly. 153 const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const { 154 const VPBlockBase *Block = this; 155 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 156 Block = Region->getEntry(); 157 return cast<VPBasicBlock>(Block); 158 } 159 160 VPBasicBlock *VPBlockBase::getEntryBasicBlock() { 161 VPBlockBase *Block = this; 162 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 163 Block = Region->getEntry(); 164 return cast<VPBasicBlock>(Block); 165 } 166 167 void VPBlockBase::setPlan(VPlan *ParentPlan) { 168 assert( 169 (ParentPlan->getEntry() == this || ParentPlan->getPreheader() == this) && 170 "Can only set plan on its entry or preheader block."); 171 Plan = ParentPlan; 172 } 173 174 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly. 175 const VPBasicBlock *VPBlockBase::getExitingBasicBlock() const { 176 const VPBlockBase *Block = this; 177 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 178 Block = Region->getExiting(); 179 return cast<VPBasicBlock>(Block); 180 } 181 182 VPBasicBlock *VPBlockBase::getExitingBasicBlock() { 183 VPBlockBase *Block = this; 184 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 185 Block = Region->getExiting(); 186 return cast<VPBasicBlock>(Block); 187 } 188 189 VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() { 190 if (!Successors.empty() || !Parent) 191 return this; 192 assert(Parent->getExiting() == this && 193 "Block w/o successors not the exiting block of its parent."); 194 return Parent->getEnclosingBlockWithSuccessors(); 195 } 196 197 VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() { 198 if (!Predecessors.empty() || !Parent) 199 return this; 200 assert(Parent->getEntry() == this && 201 "Block w/o predecessors not the entry of its parent."); 202 return Parent->getEnclosingBlockWithPredecessors(); 203 } 204 205 void VPBlockBase::deleteCFG(VPBlockBase *Entry) { 206 for (VPBlockBase *Block : to_vector(vp_depth_first_shallow(Entry))) 207 delete Block; 208 } 209 210 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() { 211 iterator It = begin(); 212 while (It != end() && It->isPhi()) 213 It++; 214 return It; 215 } 216 217 VPTransformState::VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, 218 DominatorTree *DT, IRBuilderBase &Builder, 219 InnerLoopVectorizer *ILV, VPlan *Plan, 220 LLVMContext &Ctx) 221 : VF(VF), UF(UF), LI(LI), DT(DT), Builder(Builder), ILV(ILV), Plan(Plan), 222 LVer(nullptr), 223 TypeAnalysis(Plan->getCanonicalIV()->getScalarType(), Ctx) {} 224 225 Value *VPTransformState::get(VPValue *Def, const VPIteration &Instance) { 226 if (Def->isLiveIn()) 227 return Def->getLiveInIRValue(); 228 229 if (hasScalarValue(Def, Instance)) { 230 return Data 231 .PerPartScalars[Def][Instance.Part][Instance.Lane.mapToCacheIndex(VF)]; 232 } 233 234 assert(hasVectorValue(Def, Instance.Part)); 235 auto *VecPart = Data.PerPartOutput[Def][Instance.Part]; 236 if (!VecPart->getType()->isVectorTy()) { 237 assert(Instance.Lane.isFirstLane() && "cannot get lane > 0 for scalar"); 238 return VecPart; 239 } 240 // TODO: Cache created scalar values. 241 Value *Lane = Instance.Lane.getAsRuntimeExpr(Builder, VF); 242 auto *Extract = Builder.CreateExtractElement(VecPart, Lane); 243 // set(Def, Extract, Instance); 244 return Extract; 245 } 246 247 Value *VPTransformState::get(VPValue *Def, unsigned Part, bool NeedsScalar) { 248 if (NeedsScalar) { 249 assert((VF.isScalar() || Def->isLiveIn() || 250 (hasScalarValue(Def, VPIteration(Part, 0)) && 251 Data.PerPartScalars[Def][Part].size() == 1)) && 252 "Trying to access a single scalar per part but has multiple scalars " 253 "per part."); 254 return get(Def, VPIteration(Part, 0)); 255 } 256 257 // If Values have been set for this Def return the one relevant for \p Part. 258 if (hasVectorValue(Def, Part)) 259 return Data.PerPartOutput[Def][Part]; 260 261 auto GetBroadcastInstrs = [this, Def](Value *V) { 262 bool SafeToHoist = Def->isDefinedOutsideVectorRegions(); 263 if (VF.isScalar()) 264 return V; 265 // Place the code for broadcasting invariant variables in the new preheader. 266 IRBuilder<>::InsertPointGuard Guard(Builder); 267 if (SafeToHoist) { 268 BasicBlock *LoopVectorPreHeader = CFG.VPBB2IRBB[cast<VPBasicBlock>( 269 Plan->getVectorLoopRegion()->getSinglePredecessor())]; 270 if (LoopVectorPreHeader) 271 Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator()); 272 } 273 274 // Place the code for broadcasting invariant variables in the new preheader. 275 // Broadcast the scalar into all locations in the vector. 276 Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast"); 277 278 return Shuf; 279 }; 280 281 if (!hasScalarValue(Def, {Part, 0})) { 282 assert(Def->isLiveIn() && "expected a live-in"); 283 if (Part != 0) 284 return get(Def, 0); 285 Value *IRV = Def->getLiveInIRValue(); 286 Value *B = GetBroadcastInstrs(IRV); 287 set(Def, B, Part); 288 return B; 289 } 290 291 Value *ScalarValue = get(Def, {Part, 0}); 292 // If we aren't vectorizing, we can just copy the scalar map values over 293 // to the vector map. 294 if (VF.isScalar()) { 295 set(Def, ScalarValue, Part); 296 return ScalarValue; 297 } 298 299 bool IsUniform = vputils::isUniformAfterVectorization(Def); 300 301 unsigned LastLane = IsUniform ? 0 : VF.getKnownMinValue() - 1; 302 // Check if there is a scalar value for the selected lane. 303 if (!hasScalarValue(Def, {Part, LastLane})) { 304 // At the moment, VPWidenIntOrFpInductionRecipes, VPScalarIVStepsRecipes and 305 // VPExpandSCEVRecipes can also be uniform. 306 assert((isa<VPWidenIntOrFpInductionRecipe>(Def->getDefiningRecipe()) || 307 isa<VPScalarIVStepsRecipe>(Def->getDefiningRecipe()) || 308 isa<VPExpandSCEVRecipe>(Def->getDefiningRecipe())) && 309 "unexpected recipe found to be invariant"); 310 IsUniform = true; 311 LastLane = 0; 312 } 313 314 auto *LastInst = cast<Instruction>(get(Def, {Part, LastLane})); 315 // Set the insert point after the last scalarized instruction or after the 316 // last PHI, if LastInst is a PHI. This ensures the insertelement sequence 317 // will directly follow the scalar definitions. 318 auto OldIP = Builder.saveIP(); 319 auto NewIP = 320 isa<PHINode>(LastInst) 321 ? BasicBlock::iterator(LastInst->getParent()->getFirstNonPHI()) 322 : std::next(BasicBlock::iterator(LastInst)); 323 Builder.SetInsertPoint(&*NewIP); 324 325 // However, if we are vectorizing, we need to construct the vector values. 326 // If the value is known to be uniform after vectorization, we can just 327 // broadcast the scalar value corresponding to lane zero for each unroll 328 // iteration. Otherwise, we construct the vector values using 329 // insertelement instructions. Since the resulting vectors are stored in 330 // State, we will only generate the insertelements once. 331 Value *VectorValue = nullptr; 332 if (IsUniform) { 333 VectorValue = GetBroadcastInstrs(ScalarValue); 334 set(Def, VectorValue, Part); 335 } else { 336 // Initialize packing with insertelements to start from undef. 337 assert(!VF.isScalable() && "VF is assumed to be non scalable."); 338 Value *Undef = PoisonValue::get(VectorType::get(LastInst->getType(), VF)); 339 set(Def, Undef, Part); 340 for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane) 341 packScalarIntoVectorValue(Def, {Part, Lane}); 342 VectorValue = get(Def, Part); 343 } 344 Builder.restoreIP(OldIP); 345 return VectorValue; 346 } 347 348 BasicBlock *VPTransformState::CFGState::getPreheaderBBFor(VPRecipeBase *R) { 349 VPRegionBlock *LoopRegion = R->getParent()->getEnclosingLoopRegion(); 350 return VPBB2IRBB[LoopRegion->getPreheaderVPBB()]; 351 } 352 353 void VPTransformState::addNewMetadata(Instruction *To, 354 const Instruction *Orig) { 355 // If the loop was versioned with memchecks, add the corresponding no-alias 356 // metadata. 357 if (LVer && (isa<LoadInst>(Orig) || isa<StoreInst>(Orig))) 358 LVer->annotateInstWithNoAlias(To, Orig); 359 } 360 361 void VPTransformState::addMetadata(Instruction *To, Instruction *From) { 362 // No source instruction to transfer metadata from? 363 if (!From) 364 return; 365 366 propagateMetadata(To, From); 367 addNewMetadata(To, From); 368 } 369 370 void VPTransformState::addMetadata(ArrayRef<Value *> To, Instruction *From) { 371 // No source instruction to transfer metadata from? 372 if (!From) 373 return; 374 375 for (Value *V : To) { 376 if (Instruction *I = dyn_cast<Instruction>(V)) 377 addMetadata(I, From); 378 } 379 } 380 381 void VPTransformState::setDebugLocFrom(DebugLoc DL) { 382 const DILocation *DIL = DL; 383 // When a FSDiscriminator is enabled, we don't need to add the multiply 384 // factors to the discriminators. 385 if (DIL && 386 Builder.GetInsertBlock() 387 ->getParent() 388 ->shouldEmitDebugInfoForProfiling() && 389 !EnableFSDiscriminator) { 390 // FIXME: For scalable vectors, assume vscale=1. 391 auto NewDIL = 392 DIL->cloneByMultiplyingDuplicationFactor(UF * VF.getKnownMinValue()); 393 if (NewDIL) 394 Builder.SetCurrentDebugLocation(*NewDIL); 395 else 396 LLVM_DEBUG(dbgs() << "Failed to create new discriminator: " 397 << DIL->getFilename() << " Line: " << DIL->getLine()); 398 } else 399 Builder.SetCurrentDebugLocation(DIL); 400 } 401 402 void VPTransformState::packScalarIntoVectorValue(VPValue *Def, 403 const VPIteration &Instance) { 404 Value *ScalarInst = get(Def, Instance); 405 Value *VectorValue = get(Def, Instance.Part); 406 VectorValue = Builder.CreateInsertElement( 407 VectorValue, ScalarInst, Instance.Lane.getAsRuntimeExpr(Builder, VF)); 408 set(Def, VectorValue, Instance.Part); 409 } 410 411 BasicBlock * 412 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) { 413 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks. 414 // Pred stands for Predessor. Prev stands for Previous - last visited/created. 415 BasicBlock *PrevBB = CFG.PrevBB; 416 BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(), 417 PrevBB->getParent(), CFG.ExitBB); 418 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n'); 419 420 // Hook up the new basic block to its predecessors. 421 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) { 422 VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock(); 423 auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors(); 424 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB]; 425 426 assert(PredBB && "Predecessor basic-block not found building successor."); 427 auto *PredBBTerminator = PredBB->getTerminator(); 428 LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n'); 429 430 auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator); 431 if (isa<UnreachableInst>(PredBBTerminator)) { 432 assert(PredVPSuccessors.size() == 1 && 433 "Predecessor ending w/o branch must have single successor."); 434 DebugLoc DL = PredBBTerminator->getDebugLoc(); 435 PredBBTerminator->eraseFromParent(); 436 auto *Br = BranchInst::Create(NewBB, PredBB); 437 Br->setDebugLoc(DL); 438 } else if (TermBr && !TermBr->isConditional()) { 439 TermBr->setSuccessor(0, NewBB); 440 } else { 441 // Set each forward successor here when it is created, excluding 442 // backedges. A backward successor is set when the branch is created. 443 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1; 444 assert(!TermBr->getSuccessor(idx) && 445 "Trying to reset an existing successor block."); 446 TermBr->setSuccessor(idx, NewBB); 447 } 448 } 449 return NewBB; 450 } 451 452 void VPBasicBlock::execute(VPTransformState *State) { 453 bool Replica = State->Instance && !State->Instance->isFirstIteration(); 454 VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB; 455 VPBlockBase *SingleHPred = nullptr; 456 BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible. 457 458 auto IsLoopRegion = [](VPBlockBase *BB) { 459 auto *R = dyn_cast<VPRegionBlock>(BB); 460 return R && !R->isReplicator(); 461 }; 462 463 // 1. Create an IR basic block, or reuse the last one or ExitBB if possible. 464 if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() == this) { 465 // ExitBB can be re-used for the exit block of the Plan. 466 NewBB = State->CFG.ExitBB; 467 State->CFG.PrevBB = NewBB; 468 State->Builder.SetInsertPoint(NewBB->getFirstNonPHI()); 469 470 // Update the branch instruction in the predecessor to branch to ExitBB. 471 VPBlockBase *PredVPB = getSingleHierarchicalPredecessor(); 472 VPBasicBlock *ExitingVPBB = PredVPB->getExitingBasicBlock(); 473 assert(PredVPB->getSingleSuccessor() == this && 474 "predecessor must have the current block as only successor"); 475 BasicBlock *ExitingBB = State->CFG.VPBB2IRBB[ExitingVPBB]; 476 // The Exit block of a loop is always set to be successor 0 of the Exiting 477 // block. 478 cast<BranchInst>(ExitingBB->getTerminator())->setSuccessor(0, NewBB); 479 } else if (PrevVPBB && /* A */ 480 !((SingleHPred = getSingleHierarchicalPredecessor()) && 481 SingleHPred->getExitingBasicBlock() == PrevVPBB && 482 PrevVPBB->getSingleHierarchicalSuccessor() && 483 (SingleHPred->getParent() == getEnclosingLoopRegion() && 484 !IsLoopRegion(SingleHPred))) && /* B */ 485 !(Replica && getPredecessors().empty())) { /* C */ 486 // The last IR basic block is reused, as an optimization, in three cases: 487 // A. the first VPBB reuses the loop pre-header BB - when PrevVPBB is null; 488 // B. when the current VPBB has a single (hierarchical) predecessor which 489 // is PrevVPBB and the latter has a single (hierarchical) successor which 490 // both are in the same non-replicator region; and 491 // C. when the current VPBB is an entry of a region replica - where PrevVPBB 492 // is the exiting VPBB of this region from a previous instance, or the 493 // predecessor of this region. 494 495 NewBB = createEmptyBasicBlock(State->CFG); 496 State->Builder.SetInsertPoint(NewBB); 497 // Temporarily terminate with unreachable until CFG is rewired. 498 UnreachableInst *Terminator = State->Builder.CreateUnreachable(); 499 // Register NewBB in its loop. In innermost loops its the same for all 500 // BB's. 501 if (State->CurrentVectorLoop) 502 State->CurrentVectorLoop->addBasicBlockToLoop(NewBB, *State->LI); 503 State->Builder.SetInsertPoint(Terminator); 504 State->CFG.PrevBB = NewBB; 505 } 506 507 // 2. Fill the IR basic block with IR instructions. 508 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName() 509 << " in BB:" << NewBB->getName() << '\n'); 510 511 State->CFG.VPBB2IRBB[this] = NewBB; 512 State->CFG.PrevVPBB = this; 513 514 for (VPRecipeBase &Recipe : Recipes) 515 Recipe.execute(*State); 516 517 LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB); 518 } 519 520 void VPBasicBlock::dropAllReferences(VPValue *NewValue) { 521 for (VPRecipeBase &R : Recipes) { 522 for (auto *Def : R.definedValues()) 523 Def->replaceAllUsesWith(NewValue); 524 525 for (unsigned I = 0, E = R.getNumOperands(); I != E; I++) 526 R.setOperand(I, NewValue); 527 } 528 } 529 530 VPBasicBlock *VPBasicBlock::splitAt(iterator SplitAt) { 531 assert((SplitAt == end() || SplitAt->getParent() == this) && 532 "can only split at a position in the same block"); 533 534 SmallVector<VPBlockBase *, 2> Succs(successors()); 535 // First, disconnect the current block from its successors. 536 for (VPBlockBase *Succ : Succs) 537 VPBlockUtils::disconnectBlocks(this, Succ); 538 539 // Create new empty block after the block to split. 540 auto *SplitBlock = new VPBasicBlock(getName() + ".split"); 541 VPBlockUtils::insertBlockAfter(SplitBlock, this); 542 543 // Add successors for block to split to new block. 544 for (VPBlockBase *Succ : Succs) 545 VPBlockUtils::connectBlocks(SplitBlock, Succ); 546 547 // Finally, move the recipes starting at SplitAt to new block. 548 for (VPRecipeBase &ToMove : 549 make_early_inc_range(make_range(SplitAt, this->end()))) 550 ToMove.moveBefore(*SplitBlock, SplitBlock->end()); 551 552 return SplitBlock; 553 } 554 555 VPRegionBlock *VPBasicBlock::getEnclosingLoopRegion() { 556 VPRegionBlock *P = getParent(); 557 if (P && P->isReplicator()) { 558 P = P->getParent(); 559 assert(!cast<VPRegionBlock>(P)->isReplicator() && 560 "unexpected nested replicate regions"); 561 } 562 return P; 563 } 564 565 static bool hasConditionalTerminator(const VPBasicBlock *VPBB) { 566 if (VPBB->empty()) { 567 assert( 568 VPBB->getNumSuccessors() < 2 && 569 "block with multiple successors doesn't have a recipe as terminator"); 570 return false; 571 } 572 573 const VPRecipeBase *R = &VPBB->back(); 574 bool IsCondBranch = isa<VPBranchOnMaskRecipe>(R) || 575 match(R, m_BranchOnCond(m_VPValue())) || 576 match(R, m_BranchOnCount(m_VPValue(), m_VPValue())); 577 (void)IsCondBranch; 578 579 if (VPBB->getNumSuccessors() >= 2 || 580 (VPBB->isExiting() && !VPBB->getParent()->isReplicator())) { 581 assert(IsCondBranch && "block with multiple successors not terminated by " 582 "conditional branch recipe"); 583 584 return true; 585 } 586 587 assert( 588 !IsCondBranch && 589 "block with 0 or 1 successors terminated by conditional branch recipe"); 590 return false; 591 } 592 593 VPRecipeBase *VPBasicBlock::getTerminator() { 594 if (hasConditionalTerminator(this)) 595 return &back(); 596 return nullptr; 597 } 598 599 const VPRecipeBase *VPBasicBlock::getTerminator() const { 600 if (hasConditionalTerminator(this)) 601 return &back(); 602 return nullptr; 603 } 604 605 bool VPBasicBlock::isExiting() const { 606 return getParent() && getParent()->getExitingBasicBlock() == this; 607 } 608 609 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 610 void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const { 611 if (getSuccessors().empty()) { 612 O << Indent << "No successors\n"; 613 } else { 614 O << Indent << "Successor(s): "; 615 ListSeparator LS; 616 for (auto *Succ : getSuccessors()) 617 O << LS << Succ->getName(); 618 O << '\n'; 619 } 620 } 621 622 void VPBasicBlock::print(raw_ostream &O, const Twine &Indent, 623 VPSlotTracker &SlotTracker) const { 624 O << Indent << getName() << ":\n"; 625 626 auto RecipeIndent = Indent + " "; 627 for (const VPRecipeBase &Recipe : *this) { 628 Recipe.print(O, RecipeIndent, SlotTracker); 629 O << '\n'; 630 } 631 632 printSuccessors(O, Indent); 633 } 634 #endif 635 636 static std::pair<VPBlockBase *, VPBlockBase *> cloneSESE(VPBlockBase *Entry); 637 638 // Clone the CFG for all nodes in the single-entry-single-exit region reachable 639 // from \p Entry, this includes cloning the blocks and their recipes. Operands 640 // of cloned recipes will NOT be updated. Remapping of operands must be done 641 // separately. Returns a pair with the the new entry and exiting blocks of the 642 // cloned region. 643 static std::pair<VPBlockBase *, VPBlockBase *> cloneSESE(VPBlockBase *Entry) { 644 DenseMap<VPBlockBase *, VPBlockBase *> Old2NewVPBlocks; 645 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT( 646 Entry); 647 for (VPBlockBase *BB : RPOT) { 648 VPBlockBase *NewBB = BB->clone(); 649 for (VPBlockBase *Pred : BB->getPredecessors()) 650 VPBlockUtils::connectBlocks(Old2NewVPBlocks[Pred], NewBB); 651 652 Old2NewVPBlocks[BB] = NewBB; 653 } 654 655 #if !defined(NDEBUG) 656 // Verify that the order of predecessors and successors matches in the cloned 657 // version. 658 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> 659 NewRPOT(Old2NewVPBlocks[Entry]); 660 for (const auto &[OldBB, NewBB] : zip(RPOT, NewRPOT)) { 661 for (const auto &[OldPred, NewPred] : 662 zip(OldBB->getPredecessors(), NewBB->getPredecessors())) 663 assert(NewPred == Old2NewVPBlocks[OldPred] && "Different predecessors"); 664 665 for (const auto &[OldSucc, NewSucc] : 666 zip(OldBB->successors(), NewBB->successors())) 667 assert(NewSucc == Old2NewVPBlocks[OldSucc] && "Different successors"); 668 } 669 #endif 670 671 return std::make_pair(Old2NewVPBlocks[Entry], 672 Old2NewVPBlocks[*reverse(RPOT).begin()]); 673 } 674 675 VPRegionBlock *VPRegionBlock::clone() { 676 const auto &[NewEntry, NewExiting] = cloneSESE(getEntry()); 677 auto *NewRegion = 678 new VPRegionBlock(NewEntry, NewExiting, getName(), isReplicator()); 679 for (VPBlockBase *Block : vp_depth_first_shallow(NewEntry)) 680 Block->setParent(NewRegion); 681 return NewRegion; 682 } 683 684 void VPRegionBlock::dropAllReferences(VPValue *NewValue) { 685 for (VPBlockBase *Block : vp_depth_first_shallow(Entry)) 686 // Drop all references in VPBasicBlocks and replace all uses with 687 // DummyValue. 688 Block->dropAllReferences(NewValue); 689 } 690 691 void VPRegionBlock::execute(VPTransformState *State) { 692 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> 693 RPOT(Entry); 694 695 if (!isReplicator()) { 696 // Create and register the new vector loop. 697 Loop *PrevLoop = State->CurrentVectorLoop; 698 State->CurrentVectorLoop = State->LI->AllocateLoop(); 699 BasicBlock *VectorPH = State->CFG.VPBB2IRBB[getPreheaderVPBB()]; 700 Loop *ParentLoop = State->LI->getLoopFor(VectorPH); 701 702 // Insert the new loop into the loop nest and register the new basic blocks 703 // before calling any utilities such as SCEV that require valid LoopInfo. 704 if (ParentLoop) 705 ParentLoop->addChildLoop(State->CurrentVectorLoop); 706 else 707 State->LI->addTopLevelLoop(State->CurrentVectorLoop); 708 709 // Visit the VPBlocks connected to "this", starting from it. 710 for (VPBlockBase *Block : RPOT) { 711 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n'); 712 Block->execute(State); 713 } 714 715 State->CurrentVectorLoop = PrevLoop; 716 return; 717 } 718 719 assert(!State->Instance && "Replicating a Region with non-null instance."); 720 721 // Enter replicating mode. 722 State->Instance = VPIteration(0, 0); 723 724 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) { 725 State->Instance->Part = Part; 726 assert(!State->VF.isScalable() && "VF is assumed to be non scalable."); 727 for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF; 728 ++Lane) { 729 State->Instance->Lane = VPLane(Lane, VPLane::Kind::First); 730 // Visit the VPBlocks connected to \p this, starting from it. 731 for (VPBlockBase *Block : RPOT) { 732 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n'); 733 Block->execute(State); 734 } 735 } 736 } 737 738 // Exit replicating mode. 739 State->Instance.reset(); 740 } 741 742 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 743 void VPRegionBlock::print(raw_ostream &O, const Twine &Indent, 744 VPSlotTracker &SlotTracker) const { 745 O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {"; 746 auto NewIndent = Indent + " "; 747 for (auto *BlockBase : vp_depth_first_shallow(Entry)) { 748 O << '\n'; 749 BlockBase->print(O, NewIndent, SlotTracker); 750 } 751 O << Indent << "}\n"; 752 753 printSuccessors(O, Indent); 754 } 755 #endif 756 757 VPlan::~VPlan() { 758 for (auto &KV : LiveOuts) 759 delete KV.second; 760 LiveOuts.clear(); 761 762 if (Entry) { 763 VPValue DummyValue; 764 for (VPBlockBase *Block : vp_depth_first_shallow(Entry)) 765 Block->dropAllReferences(&DummyValue); 766 767 VPBlockBase::deleteCFG(Entry); 768 769 Preheader->dropAllReferences(&DummyValue); 770 delete Preheader; 771 } 772 for (VPValue *VPV : VPLiveInsToFree) 773 delete VPV; 774 if (BackedgeTakenCount) 775 delete BackedgeTakenCount; 776 } 777 778 VPlanPtr VPlan::createInitialVPlan(const SCEV *TripCount, ScalarEvolution &SE) { 779 VPBasicBlock *Preheader = new VPBasicBlock("ph"); 780 VPBasicBlock *VecPreheader = new VPBasicBlock("vector.ph"); 781 auto Plan = std::make_unique<VPlan>(Preheader, VecPreheader); 782 Plan->TripCount = 783 vputils::getOrCreateVPValueForSCEVExpr(*Plan, TripCount, SE); 784 // Create empty VPRegionBlock, to be filled during processing later. 785 auto *TopRegion = new VPRegionBlock("vector loop", false /*isReplicator*/); 786 VPBlockUtils::insertBlockAfter(TopRegion, VecPreheader); 787 VPBasicBlock *MiddleVPBB = new VPBasicBlock("middle.block"); 788 VPBlockUtils::insertBlockAfter(MiddleVPBB, TopRegion); 789 return Plan; 790 } 791 792 void VPlan::prepareToExecute(Value *TripCountV, Value *VectorTripCountV, 793 Value *CanonicalIVStartValue, 794 VPTransformState &State) { 795 // Check if the backedge taken count is needed, and if so build it. 796 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) { 797 IRBuilder<> Builder(State.CFG.PrevBB->getTerminator()); 798 auto *TCMO = Builder.CreateSub(TripCountV, 799 ConstantInt::get(TripCountV->getType(), 1), 800 "trip.count.minus.1"); 801 BackedgeTakenCount->setUnderlyingValue(TCMO); 802 } 803 804 VectorTripCount.setUnderlyingValue(VectorTripCountV); 805 806 IRBuilder<> Builder(State.CFG.PrevBB->getTerminator()); 807 // FIXME: Model VF * UF computation completely in VPlan. 808 VFxUF.setUnderlyingValue( 809 createStepForVF(Builder, TripCountV->getType(), State.VF, State.UF)); 810 811 // When vectorizing the epilogue loop, the canonical induction start value 812 // needs to be changed from zero to the value after the main vector loop. 813 // FIXME: Improve modeling for canonical IV start values in the epilogue loop. 814 if (CanonicalIVStartValue) { 815 VPValue *VPV = getVPValueOrAddLiveIn(CanonicalIVStartValue); 816 auto *IV = getCanonicalIV(); 817 assert(all_of(IV->users(), 818 [](const VPUser *U) { 819 return isa<VPScalarIVStepsRecipe>(U) || 820 isa<VPScalarCastRecipe>(U) || 821 isa<VPDerivedIVRecipe>(U) || 822 cast<VPInstruction>(U)->getOpcode() == 823 Instruction::Add; 824 }) && 825 "the canonical IV should only be used by its increment or " 826 "ScalarIVSteps when resetting the start value"); 827 IV->setOperand(0, VPV); 828 } 829 } 830 831 /// Generate the code inside the preheader and body of the vectorized loop. 832 /// Assumes a single pre-header basic-block was created for this. Introduce 833 /// additional basic-blocks as needed, and fill them all. 834 void VPlan::execute(VPTransformState *State) { 835 // Initialize CFG state. 836 State->CFG.PrevVPBB = nullptr; 837 State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor(); 838 BasicBlock *VectorPreHeader = State->CFG.PrevBB; 839 State->Builder.SetInsertPoint(VectorPreHeader->getTerminator()); 840 841 // Generate code in the loop pre-header and body. 842 for (VPBlockBase *Block : vp_depth_first_shallow(Entry)) 843 Block->execute(State); 844 845 VPBasicBlock *LatchVPBB = getVectorLoopRegion()->getExitingBasicBlock(); 846 BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB]; 847 848 // Fix the latch value of canonical, reduction and first-order recurrences 849 // phis in the vector loop. 850 VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock(); 851 for (VPRecipeBase &R : Header->phis()) { 852 // Skip phi-like recipes that generate their backedege values themselves. 853 if (isa<VPWidenPHIRecipe>(&R)) 854 continue; 855 856 if (isa<VPWidenPointerInductionRecipe>(&R) || 857 isa<VPWidenIntOrFpInductionRecipe>(&R)) { 858 PHINode *Phi = nullptr; 859 if (isa<VPWidenIntOrFpInductionRecipe>(&R)) { 860 Phi = cast<PHINode>(State->get(R.getVPSingleValue(), 0)); 861 } else { 862 auto *WidenPhi = cast<VPWidenPointerInductionRecipe>(&R); 863 // TODO: Split off the case that all users of a pointer phi are scalar 864 // from the VPWidenPointerInductionRecipe. 865 if (WidenPhi->onlyScalarsGenerated(State->VF.isScalable())) 866 continue; 867 868 auto *GEP = cast<GetElementPtrInst>(State->get(WidenPhi, 0)); 869 Phi = cast<PHINode>(GEP->getPointerOperand()); 870 } 871 872 Phi->setIncomingBlock(1, VectorLatchBB); 873 874 // Move the last step to the end of the latch block. This ensures 875 // consistent placement of all induction updates. 876 Instruction *Inc = cast<Instruction>(Phi->getIncomingValue(1)); 877 Inc->moveBefore(VectorLatchBB->getTerminator()->getPrevNode()); 878 continue; 879 } 880 881 auto *PhiR = cast<VPHeaderPHIRecipe>(&R); 882 // For canonical IV, first-order recurrences and in-order reduction phis, 883 // only a single part is generated, which provides the last part from the 884 // previous iteration. For non-ordered reductions all UF parts are 885 // generated. 886 bool SinglePartNeeded = isa<VPCanonicalIVPHIRecipe>(PhiR) || 887 isa<VPFirstOrderRecurrencePHIRecipe>(PhiR) || 888 (isa<VPReductionPHIRecipe>(PhiR) && 889 cast<VPReductionPHIRecipe>(PhiR)->isOrdered()); 890 bool NeedsScalar = isa<VPCanonicalIVPHIRecipe>(PhiR) || 891 (isa<VPReductionPHIRecipe>(PhiR) && 892 cast<VPReductionPHIRecipe>(PhiR)->isInLoop()); 893 unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF; 894 895 for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) { 896 Value *Phi = State->get(PhiR, Part, NeedsScalar); 897 Value *Val = 898 State->get(PhiR->getBackedgeValue(), 899 SinglePartNeeded ? State->UF - 1 : Part, NeedsScalar); 900 cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB); 901 } 902 } 903 904 // We do not attempt to preserve DT for outer loop vectorization currently. 905 if (!EnableVPlanNativePath) { 906 BasicBlock *VectorHeaderBB = State->CFG.VPBB2IRBB[Header]; 907 State->DT->addNewBlock(VectorHeaderBB, VectorPreHeader); 908 updateDominatorTree(State->DT, VectorHeaderBB, VectorLatchBB, 909 State->CFG.ExitBB); 910 } 911 } 912 913 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 914 void VPlan::printLiveIns(raw_ostream &O) const { 915 VPSlotTracker SlotTracker(this); 916 917 if (VFxUF.getNumUsers() > 0) { 918 O << "\nLive-in "; 919 VFxUF.printAsOperand(O, SlotTracker); 920 O << " = VF * UF"; 921 } 922 923 if (VectorTripCount.getNumUsers() > 0) { 924 O << "\nLive-in "; 925 VectorTripCount.printAsOperand(O, SlotTracker); 926 O << " = vector-trip-count"; 927 } 928 929 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) { 930 O << "\nLive-in "; 931 BackedgeTakenCount->printAsOperand(O, SlotTracker); 932 O << " = backedge-taken count"; 933 } 934 935 O << "\n"; 936 if (TripCount->isLiveIn()) 937 O << "Live-in "; 938 TripCount->printAsOperand(O, SlotTracker); 939 O << " = original trip-count"; 940 O << "\n"; 941 } 942 943 LLVM_DUMP_METHOD 944 void VPlan::print(raw_ostream &O) const { 945 VPSlotTracker SlotTracker(this); 946 947 O << "VPlan '" << getName() << "' {"; 948 949 printLiveIns(O); 950 951 if (!getPreheader()->empty()) { 952 O << "\n"; 953 getPreheader()->print(O, "", SlotTracker); 954 } 955 956 for (const VPBlockBase *Block : vp_depth_first_shallow(getEntry())) { 957 O << '\n'; 958 Block->print(O, "", SlotTracker); 959 } 960 961 if (!LiveOuts.empty()) 962 O << "\n"; 963 for (const auto &KV : LiveOuts) { 964 KV.second->print(O, SlotTracker); 965 } 966 967 O << "}\n"; 968 } 969 970 std::string VPlan::getName() const { 971 std::string Out; 972 raw_string_ostream RSO(Out); 973 RSO << Name << " for "; 974 if (!VFs.empty()) { 975 RSO << "VF={" << VFs[0]; 976 for (ElementCount VF : drop_begin(VFs)) 977 RSO << "," << VF; 978 RSO << "},"; 979 } 980 981 if (UFs.empty()) { 982 RSO << "UF>=1"; 983 } else { 984 RSO << "UF={" << UFs[0]; 985 for (unsigned UF : drop_begin(UFs)) 986 RSO << "," << UF; 987 RSO << "}"; 988 } 989 990 return Out; 991 } 992 993 LLVM_DUMP_METHOD 994 void VPlan::printDOT(raw_ostream &O) const { 995 VPlanPrinter Printer(O, *this); 996 Printer.dump(); 997 } 998 999 LLVM_DUMP_METHOD 1000 void VPlan::dump() const { print(dbgs()); } 1001 #endif 1002 1003 void VPlan::addLiveOut(PHINode *PN, VPValue *V) { 1004 assert(LiveOuts.count(PN) == 0 && "an exit value for PN already exists"); 1005 LiveOuts.insert({PN, new VPLiveOut(PN, V)}); 1006 } 1007 1008 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopHeaderBB, 1009 BasicBlock *LoopLatchBB, 1010 BasicBlock *LoopExitBB) { 1011 // The vector body may be more than a single basic-block by this point. 1012 // Update the dominator tree information inside the vector body by propagating 1013 // it from header to latch, expecting only triangular control-flow, if any. 1014 BasicBlock *PostDomSucc = nullptr; 1015 for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) { 1016 // Get the list of successors of this block. 1017 std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB)); 1018 assert(Succs.size() <= 2 && 1019 "Basic block in vector loop has more than 2 successors."); 1020 PostDomSucc = Succs[0]; 1021 if (Succs.size() == 1) { 1022 assert(PostDomSucc->getSinglePredecessor() && 1023 "PostDom successor has more than one predecessor."); 1024 DT->addNewBlock(PostDomSucc, BB); 1025 continue; 1026 } 1027 BasicBlock *InterimSucc = Succs[1]; 1028 if (PostDomSucc->getSingleSuccessor() == InterimSucc) { 1029 PostDomSucc = Succs[1]; 1030 InterimSucc = Succs[0]; 1031 } 1032 assert(InterimSucc->getSingleSuccessor() == PostDomSucc && 1033 "One successor of a basic block does not lead to the other."); 1034 assert(InterimSucc->getSinglePredecessor() && 1035 "Interim successor has more than one predecessor."); 1036 assert(PostDomSucc->hasNPredecessors(2) && 1037 "PostDom successor has more than two predecessors."); 1038 DT->addNewBlock(InterimSucc, BB); 1039 DT->addNewBlock(PostDomSucc, BB); 1040 } 1041 // Latch block is a new dominator for the loop exit. 1042 DT->changeImmediateDominator(LoopExitBB, LoopLatchBB); 1043 assert(DT->verify(DominatorTree::VerificationLevel::Fast)); 1044 } 1045 1046 static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry, 1047 DenseMap<VPValue *, VPValue *> &Old2NewVPValues) { 1048 // Update the operands of all cloned recipes starting at NewEntry. This 1049 // traverses all reachable blocks. This is done in two steps, to handle cycles 1050 // in PHI recipes. 1051 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> 1052 OldDeepRPOT(Entry); 1053 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> 1054 NewDeepRPOT(NewEntry); 1055 // First, collect all mappings from old to new VPValues defined by cloned 1056 // recipes. 1057 for (const auto &[OldBB, NewBB] : 1058 zip(VPBlockUtils::blocksOnly<VPBasicBlock>(OldDeepRPOT), 1059 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT))) { 1060 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().size() && 1061 "blocks must have the same number of recipes"); 1062 for (const auto &[OldR, NewR] : zip(*OldBB, *NewBB)) { 1063 assert(OldR.getNumOperands() == NewR.getNumOperands() && 1064 "recipes must have the same number of operands"); 1065 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() && 1066 "recipes must define the same number of operands"); 1067 for (const auto &[OldV, NewV] : 1068 zip(OldR.definedValues(), NewR.definedValues())) 1069 Old2NewVPValues[OldV] = NewV; 1070 } 1071 } 1072 1073 // Update all operands to use cloned VPValues. 1074 for (VPBasicBlock *NewBB : 1075 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) { 1076 for (VPRecipeBase &NewR : *NewBB) 1077 for (unsigned I = 0, E = NewR.getNumOperands(); I != E; ++I) { 1078 VPValue *NewOp = Old2NewVPValues.lookup(NewR.getOperand(I)); 1079 NewR.setOperand(I, NewOp); 1080 } 1081 } 1082 } 1083 1084 VPlan *VPlan::duplicate() { 1085 // Clone blocks. 1086 VPBasicBlock *NewPreheader = Preheader->clone(); 1087 const auto &[NewEntry, __] = cloneSESE(Entry); 1088 1089 // Create VPlan, clone live-ins and remap operands in the cloned blocks. 1090 auto *NewPlan = new VPlan(NewPreheader, cast<VPBasicBlock>(NewEntry)); 1091 DenseMap<VPValue *, VPValue *> Old2NewVPValues; 1092 for (VPValue *OldLiveIn : VPLiveInsToFree) { 1093 Old2NewVPValues[OldLiveIn] = 1094 NewPlan->getVPValueOrAddLiveIn(OldLiveIn->getLiveInIRValue()); 1095 } 1096 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount; 1097 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF; 1098 if (BackedgeTakenCount) { 1099 NewPlan->BackedgeTakenCount = new VPValue(); 1100 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount; 1101 } 1102 assert(TripCount && "trip count must be set"); 1103 if (TripCount->isLiveIn()) 1104 Old2NewVPValues[TripCount] = 1105 NewPlan->getVPValueOrAddLiveIn(TripCount->getLiveInIRValue()); 1106 // else NewTripCount will be created and inserted into Old2NewVPValues when 1107 // TripCount is cloned. In any case NewPlan->TripCount is updated below. 1108 1109 remapOperands(Preheader, NewPreheader, Old2NewVPValues); 1110 remapOperands(Entry, NewEntry, Old2NewVPValues); 1111 1112 // Clone live-outs. 1113 for (const auto &[_, LO] : LiveOuts) 1114 NewPlan->addLiveOut(LO->getPhi(), Old2NewVPValues[LO->getOperand(0)]); 1115 1116 // Initialize remaining fields of cloned VPlan. 1117 NewPlan->VFs = VFs; 1118 NewPlan->UFs = UFs; 1119 // TODO: Adjust names. 1120 NewPlan->Name = Name; 1121 assert(Old2NewVPValues.contains(TripCount) && 1122 "TripCount must have been added to Old2NewVPValues"); 1123 NewPlan->TripCount = Old2NewVPValues[TripCount]; 1124 return NewPlan; 1125 } 1126 1127 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1128 1129 Twine VPlanPrinter::getUID(const VPBlockBase *Block) { 1130 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") + 1131 Twine(getOrCreateBID(Block)); 1132 } 1133 1134 Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) { 1135 const std::string &Name = Block->getName(); 1136 if (!Name.empty()) 1137 return Name; 1138 return "VPB" + Twine(getOrCreateBID(Block)); 1139 } 1140 1141 void VPlanPrinter::dump() { 1142 Depth = 1; 1143 bumpIndent(0); 1144 OS << "digraph VPlan {\n"; 1145 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan"; 1146 if (!Plan.getName().empty()) 1147 OS << "\\n" << DOT::EscapeString(Plan.getName()); 1148 1149 { 1150 // Print live-ins. 1151 std::string Str; 1152 raw_string_ostream SS(Str); 1153 Plan.printLiveIns(SS); 1154 SmallVector<StringRef, 0> Lines; 1155 StringRef(Str).rtrim('\n').split(Lines, "\n"); 1156 for (auto Line : Lines) 1157 OS << DOT::EscapeString(Line.str()) << "\\n"; 1158 } 1159 1160 OS << "\"]\n"; 1161 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n"; 1162 OS << "edge [fontname=Courier, fontsize=30]\n"; 1163 OS << "compound=true\n"; 1164 1165 dumpBlock(Plan.getPreheader()); 1166 1167 for (const VPBlockBase *Block : vp_depth_first_shallow(Plan.getEntry())) 1168 dumpBlock(Block); 1169 1170 OS << "}\n"; 1171 } 1172 1173 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) { 1174 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block)) 1175 dumpBasicBlock(BasicBlock); 1176 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 1177 dumpRegion(Region); 1178 else 1179 llvm_unreachable("Unsupported kind of VPBlock."); 1180 } 1181 1182 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To, 1183 bool Hidden, const Twine &Label) { 1184 // Due to "dot" we print an edge between two regions as an edge between the 1185 // exiting basic block and the entry basic of the respective regions. 1186 const VPBlockBase *Tail = From->getExitingBasicBlock(); 1187 const VPBlockBase *Head = To->getEntryBasicBlock(); 1188 OS << Indent << getUID(Tail) << " -> " << getUID(Head); 1189 OS << " [ label=\"" << Label << '\"'; 1190 if (Tail != From) 1191 OS << " ltail=" << getUID(From); 1192 if (Head != To) 1193 OS << " lhead=" << getUID(To); 1194 if (Hidden) 1195 OS << "; splines=none"; 1196 OS << "]\n"; 1197 } 1198 1199 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) { 1200 auto &Successors = Block->getSuccessors(); 1201 if (Successors.size() == 1) 1202 drawEdge(Block, Successors.front(), false, ""); 1203 else if (Successors.size() == 2) { 1204 drawEdge(Block, Successors.front(), false, "T"); 1205 drawEdge(Block, Successors.back(), false, "F"); 1206 } else { 1207 unsigned SuccessorNumber = 0; 1208 for (auto *Successor : Successors) 1209 drawEdge(Block, Successor, false, Twine(SuccessorNumber++)); 1210 } 1211 } 1212 1213 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) { 1214 // Implement dot-formatted dump by performing plain-text dump into the 1215 // temporary storage followed by some post-processing. 1216 OS << Indent << getUID(BasicBlock) << " [label =\n"; 1217 bumpIndent(1); 1218 std::string Str; 1219 raw_string_ostream SS(Str); 1220 // Use no indentation as we need to wrap the lines into quotes ourselves. 1221 BasicBlock->print(SS, "", SlotTracker); 1222 1223 // We need to process each line of the output separately, so split 1224 // single-string plain-text dump. 1225 SmallVector<StringRef, 0> Lines; 1226 StringRef(Str).rtrim('\n').split(Lines, "\n"); 1227 1228 auto EmitLine = [&](StringRef Line, StringRef Suffix) { 1229 OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix; 1230 }; 1231 1232 // Don't need the "+" after the last line. 1233 for (auto Line : make_range(Lines.begin(), Lines.end() - 1)) 1234 EmitLine(Line, " +\n"); 1235 EmitLine(Lines.back(), "\n"); 1236 1237 bumpIndent(-1); 1238 OS << Indent << "]\n"; 1239 1240 dumpEdges(BasicBlock); 1241 } 1242 1243 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) { 1244 OS << Indent << "subgraph " << getUID(Region) << " {\n"; 1245 bumpIndent(1); 1246 OS << Indent << "fontname=Courier\n" 1247 << Indent << "label=\"" 1248 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ") 1249 << DOT::EscapeString(Region->getName()) << "\"\n"; 1250 // Dump the blocks of the region. 1251 assert(Region->getEntry() && "Region contains no inner blocks."); 1252 for (const VPBlockBase *Block : vp_depth_first_shallow(Region->getEntry())) 1253 dumpBlock(Block); 1254 bumpIndent(-1); 1255 OS << Indent << "}\n"; 1256 dumpEdges(Region); 1257 } 1258 1259 void VPlanIngredient::print(raw_ostream &O) const { 1260 if (auto *Inst = dyn_cast<Instruction>(V)) { 1261 if (!Inst->getType()->isVoidTy()) { 1262 Inst->printAsOperand(O, false); 1263 O << " = "; 1264 } 1265 O << Inst->getOpcodeName() << " "; 1266 unsigned E = Inst->getNumOperands(); 1267 if (E > 0) { 1268 Inst->getOperand(0)->printAsOperand(O, false); 1269 for (unsigned I = 1; I < E; ++I) 1270 Inst->getOperand(I)->printAsOperand(O << ", ", false); 1271 } 1272 } else // !Inst 1273 V->printAsOperand(O, false); 1274 } 1275 1276 #endif 1277 1278 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT); 1279 1280 void VPValue::replaceAllUsesWith(VPValue *New) { 1281 replaceUsesWithIf(New, [](VPUser &, unsigned) { return true; }); 1282 } 1283 1284 void VPValue::replaceUsesWithIf( 1285 VPValue *New, 1286 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace) { 1287 // Note that this early exit is required for correctness; the implementation 1288 // below relies on the number of users for this VPValue to decrease, which 1289 // isn't the case if this == New. 1290 if (this == New) 1291 return; 1292 1293 for (unsigned J = 0; J < getNumUsers();) { 1294 VPUser *User = Users[J]; 1295 bool RemovedUser = false; 1296 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) { 1297 if (User->getOperand(I) != this || !ShouldReplace(*User, I)) 1298 continue; 1299 1300 RemovedUser = true; 1301 User->setOperand(I, New); 1302 } 1303 // If a user got removed after updating the current user, the next user to 1304 // update will be moved to the current position, so we only need to 1305 // increment the index if the number of users did not change. 1306 if (!RemovedUser) 1307 J++; 1308 } 1309 } 1310 1311 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1312 void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const { 1313 if (const Value *UV = getUnderlyingValue()) { 1314 OS << "ir<"; 1315 UV->printAsOperand(OS, false); 1316 OS << ">"; 1317 return; 1318 } 1319 1320 unsigned Slot = Tracker.getSlot(this); 1321 if (Slot == unsigned(-1)) 1322 OS << "<badref>"; 1323 else 1324 OS << "vp<%" << Tracker.getSlot(this) << ">"; 1325 } 1326 1327 void VPUser::printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const { 1328 interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) { 1329 Op->printAsOperand(O, SlotTracker); 1330 }); 1331 } 1332 #endif 1333 1334 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region, 1335 Old2NewTy &Old2New, 1336 InterleavedAccessInfo &IAI) { 1337 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> 1338 RPOT(Region->getEntry()); 1339 for (VPBlockBase *Base : RPOT) { 1340 visitBlock(Base, Old2New, IAI); 1341 } 1342 } 1343 1344 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New, 1345 InterleavedAccessInfo &IAI) { 1346 if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) { 1347 for (VPRecipeBase &VPI : *VPBB) { 1348 if (isa<VPWidenPHIRecipe>(&VPI)) 1349 continue; 1350 assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions"); 1351 auto *VPInst = cast<VPInstruction>(&VPI); 1352 1353 auto *Inst = dyn_cast_or_null<Instruction>(VPInst->getUnderlyingValue()); 1354 if (!Inst) 1355 continue; 1356 auto *IG = IAI.getInterleaveGroup(Inst); 1357 if (!IG) 1358 continue; 1359 1360 auto NewIGIter = Old2New.find(IG); 1361 if (NewIGIter == Old2New.end()) 1362 Old2New[IG] = new InterleaveGroup<VPInstruction>( 1363 IG->getFactor(), IG->isReverse(), IG->getAlign()); 1364 1365 if (Inst == IG->getInsertPos()) 1366 Old2New[IG]->setInsertPos(VPInst); 1367 1368 InterleaveGroupMap[VPInst] = Old2New[IG]; 1369 InterleaveGroupMap[VPInst]->insertMember( 1370 VPInst, IG->getIndex(Inst), 1371 Align(IG->isReverse() ? (-1) * int(IG->getFactor()) 1372 : IG->getFactor())); 1373 } 1374 } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 1375 visitRegion(Region, Old2New, IAI); 1376 else 1377 llvm_unreachable("Unsupported kind of VPBlock."); 1378 } 1379 1380 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan, 1381 InterleavedAccessInfo &IAI) { 1382 Old2NewTy Old2New; 1383 visitRegion(Plan.getVectorLoopRegion(), Old2New, IAI); 1384 } 1385 1386 void VPSlotTracker::assignSlot(const VPValue *V) { 1387 assert(!Slots.contains(V) && "VPValue already has a slot!"); 1388 Slots[V] = NextSlot++; 1389 } 1390 1391 void VPSlotTracker::assignSlots(const VPlan &Plan) { 1392 if (Plan.VFxUF.getNumUsers() > 0) 1393 assignSlot(&Plan.VFxUF); 1394 assignSlot(&Plan.VectorTripCount); 1395 if (Plan.BackedgeTakenCount) 1396 assignSlot(Plan.BackedgeTakenCount); 1397 assignSlots(Plan.getPreheader()); 1398 1399 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<const VPBlockBase *>> 1400 RPOT(VPBlockDeepTraversalWrapper<const VPBlockBase *>(Plan.getEntry())); 1401 for (const VPBasicBlock *VPBB : 1402 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT)) 1403 assignSlots(VPBB); 1404 } 1405 1406 void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) { 1407 for (const VPRecipeBase &Recipe : *VPBB) 1408 for (VPValue *Def : Recipe.definedValues()) 1409 assignSlot(Def); 1410 } 1411 1412 bool vputils::onlyFirstLaneUsed(const VPValue *Def) { 1413 return all_of(Def->users(), 1414 [Def](const VPUser *U) { return U->onlyFirstLaneUsed(Def); }); 1415 } 1416 1417 bool vputils::onlyFirstPartUsed(const VPValue *Def) { 1418 return all_of(Def->users(), 1419 [Def](const VPUser *U) { return U->onlyFirstPartUsed(Def); }); 1420 } 1421 1422 VPValue *vputils::getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, 1423 ScalarEvolution &SE) { 1424 if (auto *Expanded = Plan.getSCEVExpansion(Expr)) 1425 return Expanded; 1426 VPValue *Expanded = nullptr; 1427 if (auto *E = dyn_cast<SCEVConstant>(Expr)) 1428 Expanded = Plan.getVPValueOrAddLiveIn(E->getValue()); 1429 else if (auto *E = dyn_cast<SCEVUnknown>(Expr)) 1430 Expanded = Plan.getVPValueOrAddLiveIn(E->getValue()); 1431 else { 1432 Expanded = new VPExpandSCEVRecipe(Expr, SE); 1433 Plan.getPreheader()->appendRecipe(Expanded->getDefiningRecipe()); 1434 } 1435 Plan.addSCEVExpansion(Expr, Expanded); 1436 return Expanded; 1437 } 1438