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 "VPlanDominatorTree.h" 21 #include "llvm/ADT/DepthFirstIterator.h" 22 #include "llvm/ADT/PostOrderIterator.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/ADT/Twine.h" 25 #include "llvm/Analysis/LoopInfo.h" 26 #include "llvm/IR/BasicBlock.h" 27 #include "llvm/IR/CFG.h" 28 #include "llvm/IR/InstrTypes.h" 29 #include "llvm/IR/Instruction.h" 30 #include "llvm/IR/Instructions.h" 31 #include "llvm/IR/Type.h" 32 #include "llvm/IR/Value.h" 33 #include "llvm/Support/Casting.h" 34 #include "llvm/Support/Debug.h" 35 #include "llvm/Support/ErrorHandling.h" 36 #include "llvm/Support/GenericDomTreeConstruction.h" 37 #include "llvm/Support/GraphWriter.h" 38 #include "llvm/Support/raw_ostream.h" 39 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 40 #include <cassert> 41 #include <iterator> 42 #include <string> 43 #include <vector> 44 45 using namespace llvm; 46 extern cl::opt<bool> EnableVPlanNativePath; 47 48 #define DEBUG_TYPE "vplan" 49 50 raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) { 51 if (const VPInstruction *Instr = dyn_cast<VPInstruction>(&V)) 52 Instr->print(OS); 53 else 54 V.printAsOperand(OS); 55 return OS; 56 } 57 58 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly. 59 const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const { 60 const VPBlockBase *Block = this; 61 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 62 Block = Region->getEntry(); 63 return cast<VPBasicBlock>(Block); 64 } 65 66 VPBasicBlock *VPBlockBase::getEntryBasicBlock() { 67 VPBlockBase *Block = this; 68 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 69 Block = Region->getEntry(); 70 return cast<VPBasicBlock>(Block); 71 } 72 73 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly. 74 const VPBasicBlock *VPBlockBase::getExitBasicBlock() const { 75 const VPBlockBase *Block = this; 76 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 77 Block = Region->getExit(); 78 return cast<VPBasicBlock>(Block); 79 } 80 81 VPBasicBlock *VPBlockBase::getExitBasicBlock() { 82 VPBlockBase *Block = this; 83 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 84 Block = Region->getExit(); 85 return cast<VPBasicBlock>(Block); 86 } 87 88 VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() { 89 if (!Successors.empty() || !Parent) 90 return this; 91 assert(Parent->getExit() == this && 92 "Block w/o successors not the exit of its parent."); 93 return Parent->getEnclosingBlockWithSuccessors(); 94 } 95 96 VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() { 97 if (!Predecessors.empty() || !Parent) 98 return this; 99 assert(Parent->getEntry() == this && 100 "Block w/o predecessors not the entry of its parent."); 101 return Parent->getEnclosingBlockWithPredecessors(); 102 } 103 104 void VPBlockBase::deleteCFG(VPBlockBase *Entry) { 105 SmallVector<VPBlockBase *, 8> Blocks; 106 for (VPBlockBase *Block : depth_first(Entry)) 107 Blocks.push_back(Block); 108 109 for (VPBlockBase *Block : Blocks) 110 delete Block; 111 } 112 113 BasicBlock * 114 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) { 115 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks. 116 // Pred stands for Predessor. Prev stands for Previous - last visited/created. 117 BasicBlock *PrevBB = CFG.PrevBB; 118 BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(), 119 PrevBB->getParent(), CFG.LastBB); 120 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n'); 121 122 // Hook up the new basic block to its predecessors. 123 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) { 124 VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock(); 125 auto &PredVPSuccessors = PredVPBB->getSuccessors(); 126 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB]; 127 128 // In outer loop vectorization scenario, the predecessor BBlock may not yet 129 // be visited(backedge). Mark the VPBasicBlock for fixup at the end of 130 // vectorization. We do not encounter this case in inner loop vectorization 131 // as we start out by building a loop skeleton with the vector loop header 132 // and latch blocks. As a result, we never enter this function for the 133 // header block in the non VPlan-native path. 134 if (!PredBB) { 135 assert(EnableVPlanNativePath && 136 "Unexpected null predecessor in non VPlan-native path"); 137 CFG.VPBBsToFix.push_back(PredVPBB); 138 continue; 139 } 140 141 assert(PredBB && "Predecessor basic-block not found building successor."); 142 auto *PredBBTerminator = PredBB->getTerminator(); 143 LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n'); 144 if (isa<UnreachableInst>(PredBBTerminator)) { 145 assert(PredVPSuccessors.size() == 1 && 146 "Predecessor ending w/o branch must have single successor."); 147 PredBBTerminator->eraseFromParent(); 148 BranchInst::Create(NewBB, PredBB); 149 } else { 150 assert(PredVPSuccessors.size() == 2 && 151 "Predecessor ending with branch must have two successors."); 152 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1; 153 assert(!PredBBTerminator->getSuccessor(idx) && 154 "Trying to reset an existing successor block."); 155 PredBBTerminator->setSuccessor(idx, NewBB); 156 } 157 } 158 return NewBB; 159 } 160 161 void VPBasicBlock::execute(VPTransformState *State) { 162 bool Replica = State->Instance && 163 !(State->Instance->Part == 0 && State->Instance->Lane == 0); 164 VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB; 165 VPBlockBase *SingleHPred = nullptr; 166 BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible. 167 168 // 1. Create an IR basic block, or reuse the last one if possible. 169 // The last IR basic block is reused, as an optimization, in three cases: 170 // A. the first VPBB reuses the loop header BB - when PrevVPBB is null; 171 // B. when the current VPBB has a single (hierarchical) predecessor which 172 // is PrevVPBB and the latter has a single (hierarchical) successor; and 173 // C. when the current VPBB is an entry of a region replica - where PrevVPBB 174 // is the exit of this region from a previous instance, or the predecessor 175 // of this region. 176 if (PrevVPBB && /* A */ 177 !((SingleHPred = getSingleHierarchicalPredecessor()) && 178 SingleHPred->getExitBasicBlock() == PrevVPBB && 179 PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */ 180 !(Replica && getPredecessors().empty())) { /* C */ 181 NewBB = createEmptyBasicBlock(State->CFG); 182 State->Builder.SetInsertPoint(NewBB); 183 // Temporarily terminate with unreachable until CFG is rewired. 184 UnreachableInst *Terminator = State->Builder.CreateUnreachable(); 185 State->Builder.SetInsertPoint(Terminator); 186 // Register NewBB in its loop. In innermost loops its the same for all BB's. 187 Loop *L = State->LI->getLoopFor(State->CFG.LastBB); 188 L->addBasicBlockToLoop(NewBB, *State->LI); 189 State->CFG.PrevBB = NewBB; 190 } 191 192 // 2. Fill the IR basic block with IR instructions. 193 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName() 194 << " in BB:" << NewBB->getName() << '\n'); 195 196 State->CFG.VPBB2IRBB[this] = NewBB; 197 State->CFG.PrevVPBB = this; 198 199 for (VPRecipeBase &Recipe : Recipes) 200 Recipe.execute(*State); 201 202 VPValue *CBV; 203 if (EnableVPlanNativePath && (CBV = getCondBit())) { 204 Value *IRCBV = CBV->getUnderlyingValue(); 205 assert(IRCBV && "Unexpected null underlying value for condition bit"); 206 207 // Condition bit value in a VPBasicBlock is used as the branch selector. In 208 // the VPlan-native path case, since all branches are uniform we generate a 209 // branch instruction using the condition value from vector lane 0 and dummy 210 // successors. The successors are fixed later when the successor blocks are 211 // visited. 212 Value *NewCond = State->Callback.getOrCreateVectorValues(IRCBV, 0); 213 NewCond = State->Builder.CreateExtractElement(NewCond, 214 State->Builder.getInt32(0)); 215 216 // Replace the temporary unreachable terminator with the new conditional 217 // branch. 218 auto *CurrentTerminator = NewBB->getTerminator(); 219 assert(isa<UnreachableInst>(CurrentTerminator) && 220 "Expected to replace unreachable terminator with conditional " 221 "branch."); 222 auto *CondBr = BranchInst::Create(NewBB, nullptr, NewCond); 223 CondBr->setSuccessor(0, nullptr); 224 ReplaceInstWithInst(CurrentTerminator, CondBr); 225 } 226 227 LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB); 228 } 229 230 void VPRegionBlock::execute(VPTransformState *State) { 231 ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry); 232 233 if (!isReplicator()) { 234 // Visit the VPBlocks connected to "this", starting from it. 235 for (VPBlockBase *Block : RPOT) { 236 if (EnableVPlanNativePath) { 237 // The inner loop vectorization path does not represent loop preheader 238 // and exit blocks as part of the VPlan. In the VPlan-native path, skip 239 // vectorizing loop preheader block. In future, we may replace this 240 // check with the check for loop preheader. 241 if (Block->getNumPredecessors() == 0) 242 continue; 243 244 // Skip vectorizing loop exit block. In future, we may replace this 245 // check with the check for loop exit. 246 if (Block->getNumSuccessors() == 0) 247 continue; 248 } 249 250 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n'); 251 Block->execute(State); 252 } 253 return; 254 } 255 256 assert(!State->Instance && "Replicating a Region with non-null instance."); 257 258 // Enter replicating mode. 259 State->Instance = {0, 0}; 260 261 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) { 262 State->Instance->Part = Part; 263 for (unsigned Lane = 0, VF = State->VF; Lane < VF; ++Lane) { 264 State->Instance->Lane = Lane; 265 // Visit the VPBlocks connected to \p this, starting from it. 266 for (VPBlockBase *Block : RPOT) { 267 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n'); 268 Block->execute(State); 269 } 270 } 271 } 272 273 // Exit replicating mode. 274 State->Instance.reset(); 275 } 276 277 void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) { 278 Parent = InsertPos->getParent(); 279 Parent->getRecipeList().insert(InsertPos->getIterator(), this); 280 } 281 282 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() { 283 return getParent()->getRecipeList().erase(getIterator()); 284 } 285 286 void VPInstruction::generateInstruction(VPTransformState &State, 287 unsigned Part) { 288 IRBuilder<> &Builder = State.Builder; 289 290 if (Instruction::isBinaryOp(getOpcode())) { 291 Value *A = State.get(getOperand(0), Part); 292 Value *B = State.get(getOperand(1), Part); 293 Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B); 294 State.set(this, V, Part); 295 return; 296 } 297 298 switch (getOpcode()) { 299 case VPInstruction::Not: { 300 Value *A = State.get(getOperand(0), Part); 301 Value *V = Builder.CreateNot(A); 302 State.set(this, V, Part); 303 break; 304 } 305 case VPInstruction::ICmpULE: { 306 Value *IV = State.get(getOperand(0), Part); 307 Value *TC = State.get(getOperand(1), Part); 308 Value *V = Builder.CreateICmpULE(IV, TC); 309 State.set(this, V, Part); 310 break; 311 } 312 default: 313 llvm_unreachable("Unsupported opcode for instruction"); 314 } 315 } 316 317 void VPInstruction::execute(VPTransformState &State) { 318 assert(!State.Instance && "VPInstruction executing an Instance"); 319 for (unsigned Part = 0; Part < State.UF; ++Part) 320 generateInstruction(State, Part); 321 } 322 323 void VPInstruction::print(raw_ostream &O, const Twine &Indent) const { 324 O << " +\n" << Indent << "\"EMIT "; 325 print(O); 326 O << "\\l\""; 327 } 328 329 void VPInstruction::print(raw_ostream &O) const { 330 printAsOperand(O); 331 O << " = "; 332 333 switch (getOpcode()) { 334 case VPInstruction::Not: 335 O << "not"; 336 break; 337 case VPInstruction::ICmpULE: 338 O << "icmp ule"; 339 break; 340 case VPInstruction::SLPLoad: 341 O << "combined load"; 342 break; 343 case VPInstruction::SLPStore: 344 O << "combined store"; 345 break; 346 default: 347 O << Instruction::getOpcodeName(getOpcode()); 348 } 349 350 for (const VPValue *Operand : operands()) { 351 O << " "; 352 Operand->printAsOperand(O); 353 } 354 } 355 356 /// Generate the code inside the body of the vectorized loop. Assumes a single 357 /// LoopVectorBody basic-block was created for this. Introduce additional 358 /// basic-blocks as needed, and fill them all. 359 void VPlan::execute(VPTransformState *State) { 360 // -1. Check if the backedge taken count is needed, and if so build it. 361 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) { 362 Value *TC = State->TripCount; 363 IRBuilder<> Builder(State->CFG.PrevBB->getTerminator()); 364 auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1), 365 "trip.count.minus.1"); 366 Value2VPValue[TCMO] = BackedgeTakenCount; 367 } 368 369 // 0. Set the reverse mapping from VPValues to Values for code generation. 370 for (auto &Entry : Value2VPValue) 371 State->VPValue2Value[Entry.second] = Entry.first; 372 373 BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB; 374 BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor(); 375 assert(VectorHeaderBB && "Loop preheader does not have a single successor."); 376 377 // 1. Make room to generate basic-blocks inside loop body if needed. 378 BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock( 379 VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch"); 380 Loop *L = State->LI->getLoopFor(VectorHeaderBB); 381 L->addBasicBlockToLoop(VectorLatchBB, *State->LI); 382 // Remove the edge between Header and Latch to allow other connections. 383 // Temporarily terminate with unreachable until CFG is rewired. 384 // Note: this asserts the generated code's assumption that 385 // getFirstInsertionPt() can be dereferenced into an Instruction. 386 VectorHeaderBB->getTerminator()->eraseFromParent(); 387 State->Builder.SetInsertPoint(VectorHeaderBB); 388 UnreachableInst *Terminator = State->Builder.CreateUnreachable(); 389 State->Builder.SetInsertPoint(Terminator); 390 391 // 2. Generate code in loop body. 392 State->CFG.PrevVPBB = nullptr; 393 State->CFG.PrevBB = VectorHeaderBB; 394 State->CFG.LastBB = VectorLatchBB; 395 396 for (VPBlockBase *Block : depth_first(Entry)) 397 Block->execute(State); 398 399 // Setup branch terminator successors for VPBBs in VPBBsToFix based on 400 // VPBB's successors. 401 for (auto VPBB : State->CFG.VPBBsToFix) { 402 assert(EnableVPlanNativePath && 403 "Unexpected VPBBsToFix in non VPlan-native path"); 404 BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB]; 405 assert(BB && "Unexpected null basic block for VPBB"); 406 407 unsigned Idx = 0; 408 auto *BBTerminator = BB->getTerminator(); 409 410 for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) { 411 VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock(); 412 BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]); 413 ++Idx; 414 } 415 } 416 417 // 3. Merge the temporary latch created with the last basic-block filled. 418 BasicBlock *LastBB = State->CFG.PrevBB; 419 // Connect LastBB to VectorLatchBB to facilitate their merge. 420 assert((EnableVPlanNativePath || 421 isa<UnreachableInst>(LastBB->getTerminator())) && 422 "Expected InnerLoop VPlan CFG to terminate with unreachable"); 423 assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) && 424 "Expected VPlan CFG to terminate with branch in NativePath"); 425 LastBB->getTerminator()->eraseFromParent(); 426 BranchInst::Create(VectorLatchBB, LastBB); 427 428 // Merge LastBB with Latch. 429 bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI); 430 (void)Merged; 431 assert(Merged && "Could not merge last basic block with latch."); 432 VectorLatchBB = LastBB; 433 434 // We do not attempt to preserve DT for outer loop vectorization currently. 435 if (!EnableVPlanNativePath) 436 updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB); 437 } 438 439 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB, 440 BasicBlock *LoopLatchBB) { 441 BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor(); 442 assert(LoopHeaderBB && "Loop preheader does not have a single successor."); 443 DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB); 444 // The vector body may be more than a single basic-block by this point. 445 // Update the dominator tree information inside the vector body by propagating 446 // it from header to latch, expecting only triangular control-flow, if any. 447 BasicBlock *PostDomSucc = nullptr; 448 for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) { 449 // Get the list of successors of this block. 450 std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB)); 451 assert(Succs.size() <= 2 && 452 "Basic block in vector loop has more than 2 successors."); 453 PostDomSucc = Succs[0]; 454 if (Succs.size() == 1) { 455 assert(PostDomSucc->getSinglePredecessor() && 456 "PostDom successor has more than one predecessor."); 457 DT->addNewBlock(PostDomSucc, BB); 458 continue; 459 } 460 BasicBlock *InterimSucc = Succs[1]; 461 if (PostDomSucc->getSingleSuccessor() == InterimSucc) { 462 PostDomSucc = Succs[1]; 463 InterimSucc = Succs[0]; 464 } 465 assert(InterimSucc->getSingleSuccessor() == PostDomSucc && 466 "One successor of a basic block does not lead to the other."); 467 assert(InterimSucc->getSinglePredecessor() && 468 "Interim successor has more than one predecessor."); 469 assert(PostDomSucc->hasNPredecessors(2) && 470 "PostDom successor has more than two predecessors."); 471 DT->addNewBlock(InterimSucc, BB); 472 DT->addNewBlock(PostDomSucc, BB); 473 } 474 } 475 476 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) { 477 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") + 478 Twine(getOrCreateBID(Block)); 479 } 480 481 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) { 482 const std::string &Name = Block->getName(); 483 if (!Name.empty()) 484 return Name; 485 return "VPB" + Twine(getOrCreateBID(Block)); 486 } 487 488 void VPlanPrinter::dump() { 489 Depth = 1; 490 bumpIndent(0); 491 OS << "digraph VPlan {\n"; 492 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan"; 493 if (!Plan.getName().empty()) 494 OS << "\\n" << DOT::EscapeString(Plan.getName()); 495 if (!Plan.Value2VPValue.empty() || Plan.BackedgeTakenCount) { 496 OS << ", where:"; 497 if (Plan.BackedgeTakenCount) 498 OS << "\\n" 499 << *Plan.getOrCreateBackedgeTakenCount() << " := BackedgeTakenCount"; 500 for (auto Entry : Plan.Value2VPValue) { 501 OS << "\\n" << *Entry.second; 502 OS << DOT::EscapeString(" := "); 503 Entry.first->printAsOperand(OS, false); 504 } 505 } 506 OS << "\"]\n"; 507 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n"; 508 OS << "edge [fontname=Courier, fontsize=30]\n"; 509 OS << "compound=true\n"; 510 511 for (VPBlockBase *Block : depth_first(Plan.getEntry())) 512 dumpBlock(Block); 513 514 OS << "}\n"; 515 } 516 517 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) { 518 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block)) 519 dumpBasicBlock(BasicBlock); 520 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 521 dumpRegion(Region); 522 else 523 llvm_unreachable("Unsupported kind of VPBlock."); 524 } 525 526 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To, 527 bool Hidden, const Twine &Label) { 528 // Due to "dot" we print an edge between two regions as an edge between the 529 // exit basic block and the entry basic of the respective regions. 530 const VPBlockBase *Tail = From->getExitBasicBlock(); 531 const VPBlockBase *Head = To->getEntryBasicBlock(); 532 OS << Indent << getUID(Tail) << " -> " << getUID(Head); 533 OS << " [ label=\"" << Label << '\"'; 534 if (Tail != From) 535 OS << " ltail=" << getUID(From); 536 if (Head != To) 537 OS << " lhead=" << getUID(To); 538 if (Hidden) 539 OS << "; splines=none"; 540 OS << "]\n"; 541 } 542 543 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) { 544 auto &Successors = Block->getSuccessors(); 545 if (Successors.size() == 1) 546 drawEdge(Block, Successors.front(), false, ""); 547 else if (Successors.size() == 2) { 548 drawEdge(Block, Successors.front(), false, "T"); 549 drawEdge(Block, Successors.back(), false, "F"); 550 } else { 551 unsigned SuccessorNumber = 0; 552 for (auto *Successor : Successors) 553 drawEdge(Block, Successor, false, Twine(SuccessorNumber++)); 554 } 555 } 556 557 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) { 558 OS << Indent << getUID(BasicBlock) << " [label =\n"; 559 bumpIndent(1); 560 OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\""; 561 bumpIndent(1); 562 563 // Dump the block predicate. 564 const VPValue *Pred = BasicBlock->getPredicate(); 565 if (Pred) { 566 OS << " +\n" << Indent << " \"BlockPredicate: "; 567 if (const VPInstruction *PredI = dyn_cast<VPInstruction>(Pred)) { 568 PredI->printAsOperand(OS); 569 OS << " (" << DOT::EscapeString(PredI->getParent()->getName()) 570 << ")\\l\""; 571 } else 572 Pred->printAsOperand(OS); 573 } 574 575 for (const VPRecipeBase &Recipe : *BasicBlock) 576 Recipe.print(OS, Indent); 577 578 // Dump the condition bit. 579 const VPValue *CBV = BasicBlock->getCondBit(); 580 if (CBV) { 581 OS << " +\n" << Indent << " \"CondBit: "; 582 if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) { 583 CBI->printAsOperand(OS); 584 OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\""; 585 } else { 586 CBV->printAsOperand(OS); 587 OS << "\""; 588 } 589 } 590 591 bumpIndent(-2); 592 OS << "\n" << Indent << "]\n"; 593 dumpEdges(BasicBlock); 594 } 595 596 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) { 597 OS << Indent << "subgraph " << getUID(Region) << " {\n"; 598 bumpIndent(1); 599 OS << Indent << "fontname=Courier\n" 600 << Indent << "label=\"" 601 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ") 602 << DOT::EscapeString(Region->getName()) << "\"\n"; 603 // Dump the blocks of the region. 604 assert(Region->getEntry() && "Region contains no inner blocks."); 605 for (const VPBlockBase *Block : depth_first(Region->getEntry())) 606 dumpBlock(Block); 607 bumpIndent(-1); 608 OS << Indent << "}\n"; 609 dumpEdges(Region); 610 } 611 612 void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) { 613 std::string IngredientString; 614 raw_string_ostream RSO(IngredientString); 615 if (auto *Inst = dyn_cast<Instruction>(V)) { 616 if (!Inst->getType()->isVoidTy()) { 617 Inst->printAsOperand(RSO, false); 618 RSO << " = "; 619 } 620 RSO << Inst->getOpcodeName() << " "; 621 unsigned E = Inst->getNumOperands(); 622 if (E > 0) { 623 Inst->getOperand(0)->printAsOperand(RSO, false); 624 for (unsigned I = 1; I < E; ++I) 625 Inst->getOperand(I)->printAsOperand(RSO << ", ", false); 626 } 627 } else // !Inst 628 V->printAsOperand(RSO, false); 629 RSO.flush(); 630 O << DOT::EscapeString(IngredientString); 631 } 632 633 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const { 634 O << " +\n" << Indent << "\"WIDEN\\l\""; 635 for (auto &Instr : make_range(Begin, End)) 636 O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\""; 637 } 638 639 void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, 640 const Twine &Indent) const { 641 O << " +\n" << Indent << "\"WIDEN-INDUCTION"; 642 if (Trunc) { 643 O << "\\l\""; 644 O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\""; 645 O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\""; 646 } else 647 O << " " << VPlanIngredient(IV) << "\\l\""; 648 } 649 650 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const { 651 O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\""; 652 } 653 654 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const { 655 O << " +\n" << Indent << "\"BLEND "; 656 Phi->printAsOperand(O, false); 657 O << " ="; 658 if (!User) { 659 // Not a User of any mask: not really blending, this is a 660 // single-predecessor phi. 661 O << " "; 662 Phi->getIncomingValue(0)->printAsOperand(O, false); 663 } else { 664 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) { 665 O << " "; 666 Phi->getIncomingValue(I)->printAsOperand(O, false); 667 O << "/"; 668 User->getOperand(I)->printAsOperand(O); 669 } 670 } 671 O << "\\l\""; 672 } 673 674 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const { 675 O << " +\n" 676 << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ") 677 << VPlanIngredient(Ingredient); 678 if (AlsoPack) 679 O << " (S->V)"; 680 O << "\\l\""; 681 } 682 683 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const { 684 O << " +\n" 685 << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst) 686 << "\\l\""; 687 } 688 689 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, 690 const Twine &Indent) const { 691 O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr); 692 if (User) { 693 O << ", "; 694 User->getOperand(0)->printAsOperand(O); 695 } 696 O << "\\l\""; 697 } 698 699 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT); 700 701 void VPValue::replaceAllUsesWith(VPValue *New) { 702 for (VPUser *User : users()) 703 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) 704 if (User->getOperand(I) == this) 705 User->setOperand(I, New); 706 } 707 708 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region, 709 Old2NewTy &Old2New, 710 InterleavedAccessInfo &IAI) { 711 ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry()); 712 for (VPBlockBase *Base : RPOT) { 713 visitBlock(Base, Old2New, IAI); 714 } 715 } 716 717 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New, 718 InterleavedAccessInfo &IAI) { 719 if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) { 720 for (VPRecipeBase &VPI : *VPBB) { 721 assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions"); 722 auto *VPInst = cast<VPInstruction>(&VPI); 723 auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue()); 724 auto *IG = IAI.getInterleaveGroup(Inst); 725 if (!IG) 726 continue; 727 728 auto NewIGIter = Old2New.find(IG); 729 if (NewIGIter == Old2New.end()) 730 Old2New[IG] = new InterleaveGroup<VPInstruction>( 731 IG->getFactor(), IG->isReverse(), IG->getAlignment()); 732 733 if (Inst == IG->getInsertPos()) 734 Old2New[IG]->setInsertPos(VPInst); 735 736 InterleaveGroupMap[VPInst] = Old2New[IG]; 737 InterleaveGroupMap[VPInst]->insertMember( 738 VPInst, IG->getIndex(Inst), 739 IG->isReverse() ? (-1) * int(IG->getFactor()) : IG->getFactor()); 740 } 741 } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block)) 742 visitRegion(Region, Old2New, IAI); 743 else 744 llvm_unreachable("Unsupported kind of VPBlock."); 745 } 746 747 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan, 748 InterleavedAccessInfo &IAI) { 749 Old2NewTy Old2New; 750 visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI); 751 } 752