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/STLExtras.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/Twine.h"
26 #include "llvm/Analysis/IVDescriptors.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/CFG.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/Support/Casting.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/ErrorHandling.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 <cassert>
44 #include <iterator>
45 #include <string>
46 #include <vector>
47
48 using namespace llvm;
49 extern cl::opt<bool> EnableVPlanNativePath;
50
51 #define DEBUG_TYPE "vplan"
52
operator <<(raw_ostream & OS,const VPValue & V)53 raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
54 const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
55 VPSlotTracker SlotTracker(
56 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
57 V.print(OS, SlotTracker);
58 return OS;
59 }
60
VPValue(const unsigned char SC,Value * UV,VPDef * Def)61 VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
62 : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
63 if (Def)
64 Def->addDefinedValue(this);
65 }
66
~VPValue()67 VPValue::~VPValue() {
68 assert(Users.empty() && "trying to delete a VPValue with remaining users");
69 if (Def)
70 Def->removeDefinedValue(this);
71 }
72
print(raw_ostream & OS,VPSlotTracker & SlotTracker) const73 void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const {
74 if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def))
75 R->print(OS, "", SlotTracker);
76 else
77 printAsOperand(OS, SlotTracker);
78 }
79
dump() const80 void VPValue::dump() const {
81 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def);
82 VPSlotTracker SlotTracker(
83 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
84 print(dbgs(), SlotTracker);
85 dbgs() << "\n";
86 }
87
dump() const88 void VPDef::dump() const {
89 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);
90 VPSlotTracker SlotTracker(
91 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
92 print(dbgs(), "", SlotTracker);
93 dbgs() << "\n";
94 }
95
toVPUser()96 VPUser *VPRecipeBase::toVPUser() {
97 if (auto *U = dyn_cast<VPInstruction>(this))
98 return U;
99 if (auto *U = dyn_cast<VPWidenRecipe>(this))
100 return U;
101 if (auto *U = dyn_cast<VPWidenCallRecipe>(this))
102 return U;
103 if (auto *U = dyn_cast<VPWidenSelectRecipe>(this))
104 return U;
105 if (auto *U = dyn_cast<VPWidenGEPRecipe>(this))
106 return U;
107 if (auto *U = dyn_cast<VPBlendRecipe>(this))
108 return U;
109 if (auto *U = dyn_cast<VPInterleaveRecipe>(this))
110 return U;
111 if (auto *U = dyn_cast<VPReplicateRecipe>(this))
112 return U;
113 if (auto *U = dyn_cast<VPBranchOnMaskRecipe>(this))
114 return U;
115 if (auto *U = dyn_cast<VPWidenMemoryInstructionRecipe>(this))
116 return U;
117 if (auto *U = dyn_cast<VPReductionRecipe>(this))
118 return U;
119 if (auto *U = dyn_cast<VPPredInstPHIRecipe>(this))
120 return U;
121 return nullptr;
122 }
123
124 // Get the top-most entry block of \p Start. This is the entry block of the
125 // containing VPlan. This function is templated to support both const and non-const blocks
getPlanEntry(T * Start)126 template <typename T> static T *getPlanEntry(T *Start) {
127 T *Next = Start;
128 T *Current = Start;
129 while ((Next = Next->getParent()))
130 Current = Next;
131
132 SmallSetVector<T *, 8> WorkList;
133 WorkList.insert(Current);
134
135 for (unsigned i = 0; i < WorkList.size(); i++) {
136 T *Current = WorkList[i];
137 if (Current->getNumPredecessors() == 0)
138 return Current;
139 auto &Predecessors = Current->getPredecessors();
140 WorkList.insert(Predecessors.begin(), Predecessors.end());
141 }
142
143 llvm_unreachable("VPlan without any entry node without predecessors");
144 }
145
getPlan()146 VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
147
getPlan() const148 const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
149
150 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
getEntryBasicBlock() const151 const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
152 const VPBlockBase *Block = this;
153 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
154 Block = Region->getEntry();
155 return cast<VPBasicBlock>(Block);
156 }
157
getEntryBasicBlock()158 VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
159 VPBlockBase *Block = this;
160 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
161 Block = Region->getEntry();
162 return cast<VPBasicBlock>(Block);
163 }
164
setPlan(VPlan * ParentPlan)165 void VPBlockBase::setPlan(VPlan *ParentPlan) {
166 assert(ParentPlan->getEntry() == this &&
167 "Can only set plan on its entry block.");
168 Plan = ParentPlan;
169 }
170
171 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
getExitBasicBlock() const172 const VPBasicBlock *VPBlockBase::getExitBasicBlock() const {
173 const VPBlockBase *Block = this;
174 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
175 Block = Region->getExit();
176 return cast<VPBasicBlock>(Block);
177 }
178
getExitBasicBlock()179 VPBasicBlock *VPBlockBase::getExitBasicBlock() {
180 VPBlockBase *Block = this;
181 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
182 Block = Region->getExit();
183 return cast<VPBasicBlock>(Block);
184 }
185
getEnclosingBlockWithSuccessors()186 VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
187 if (!Successors.empty() || !Parent)
188 return this;
189 assert(Parent->getExit() == this &&
190 "Block w/o successors not the exit of its parent.");
191 return Parent->getEnclosingBlockWithSuccessors();
192 }
193
getEnclosingBlockWithPredecessors()194 VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
195 if (!Predecessors.empty() || !Parent)
196 return this;
197 assert(Parent->getEntry() == this &&
198 "Block w/o predecessors not the entry of its parent.");
199 return Parent->getEnclosingBlockWithPredecessors();
200 }
201
deleteCFG(VPBlockBase * Entry)202 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
203 SmallVector<VPBlockBase *, 8> Blocks(depth_first(Entry));
204
205 for (VPBlockBase *Block : Blocks)
206 delete Block;
207 }
208
getFirstNonPhi()209 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
210 iterator It = begin();
211 while (It != end() && (isa<VPWidenPHIRecipe>(&*It) ||
212 isa<VPWidenIntOrFpInductionRecipe>(&*It) ||
213 isa<VPPredInstPHIRecipe>(&*It) ||
214 isa<VPWidenCanonicalIVRecipe>(&*It)))
215 It++;
216 return It;
217 }
218
get(VPValue * Def,const VPIteration & Instance)219 Value *VPTransformState::get(VPValue *Def, const VPIteration &Instance) {
220 if (!Def->getDef() && OrigLoop->isLoopInvariant(Def->getLiveInIRValue()))
221 return Def->getLiveInIRValue();
222
223 if (hasScalarValue(Def, Instance))
224 return Data.PerPartScalars[Def][Instance.Part][Instance.Lane];
225
226 if (hasVectorValue(Def, Instance.Part)) {
227 assert(Data.PerPartOutput.count(Def));
228 auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
229 if (!VecPart->getType()->isVectorTy()) {
230 assert(Instance.Lane == 0 && "cannot get lane > 0 for scalar");
231 return VecPart;
232 }
233 // TODO: Cache created scalar values.
234 return Builder.CreateExtractElement(VecPart,
235 Builder.getInt32(Instance.Lane));
236 }
237 return Callback.getOrCreateScalarValue(VPValue2Value[Def], Instance);
238 }
239
240 BasicBlock *
createEmptyBasicBlock(VPTransformState::CFGState & CFG)241 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
242 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
243 // Pred stands for Predessor. Prev stands for Previous - last visited/created.
244 BasicBlock *PrevBB = CFG.PrevBB;
245 BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
246 PrevBB->getParent(), CFG.LastBB);
247 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
248
249 // Hook up the new basic block to its predecessors.
250 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
251 VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
252 auto &PredVPSuccessors = PredVPBB->getSuccessors();
253 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
254
255 // In outer loop vectorization scenario, the predecessor BBlock may not yet
256 // be visited(backedge). Mark the VPBasicBlock for fixup at the end of
257 // vectorization. We do not encounter this case in inner loop vectorization
258 // as we start out by building a loop skeleton with the vector loop header
259 // and latch blocks. As a result, we never enter this function for the
260 // header block in the non VPlan-native path.
261 if (!PredBB) {
262 assert(EnableVPlanNativePath &&
263 "Unexpected null predecessor in non VPlan-native path");
264 CFG.VPBBsToFix.push_back(PredVPBB);
265 continue;
266 }
267
268 assert(PredBB && "Predecessor basic-block not found building successor.");
269 auto *PredBBTerminator = PredBB->getTerminator();
270 LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
271 if (isa<UnreachableInst>(PredBBTerminator)) {
272 assert(PredVPSuccessors.size() == 1 &&
273 "Predecessor ending w/o branch must have single successor.");
274 PredBBTerminator->eraseFromParent();
275 BranchInst::Create(NewBB, PredBB);
276 } else {
277 assert(PredVPSuccessors.size() == 2 &&
278 "Predecessor ending with branch must have two successors.");
279 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
280 assert(!PredBBTerminator->getSuccessor(idx) &&
281 "Trying to reset an existing successor block.");
282 PredBBTerminator->setSuccessor(idx, NewBB);
283 }
284 }
285 return NewBB;
286 }
287
execute(VPTransformState * State)288 void VPBasicBlock::execute(VPTransformState *State) {
289 bool Replica = State->Instance &&
290 !(State->Instance->Part == 0 && State->Instance->Lane == 0);
291 VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
292 VPBlockBase *SingleHPred = nullptr;
293 BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
294
295 // 1. Create an IR basic block, or reuse the last one if possible.
296 // The last IR basic block is reused, as an optimization, in three cases:
297 // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
298 // B. when the current VPBB has a single (hierarchical) predecessor which
299 // is PrevVPBB and the latter has a single (hierarchical) successor; and
300 // C. when the current VPBB is an entry of a region replica - where PrevVPBB
301 // is the exit of this region from a previous instance, or the predecessor
302 // of this region.
303 if (PrevVPBB && /* A */
304 !((SingleHPred = getSingleHierarchicalPredecessor()) &&
305 SingleHPred->getExitBasicBlock() == PrevVPBB &&
306 PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
307 !(Replica && getPredecessors().empty())) { /* C */
308 NewBB = createEmptyBasicBlock(State->CFG);
309 State->Builder.SetInsertPoint(NewBB);
310 // Temporarily terminate with unreachable until CFG is rewired.
311 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
312 State->Builder.SetInsertPoint(Terminator);
313 // Register NewBB in its loop. In innermost loops its the same for all BB's.
314 Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
315 L->addBasicBlockToLoop(NewBB, *State->LI);
316 State->CFG.PrevBB = NewBB;
317 }
318
319 // 2. Fill the IR basic block with IR instructions.
320 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
321 << " in BB:" << NewBB->getName() << '\n');
322
323 State->CFG.VPBB2IRBB[this] = NewBB;
324 State->CFG.PrevVPBB = this;
325
326 for (VPRecipeBase &Recipe : Recipes)
327 Recipe.execute(*State);
328
329 VPValue *CBV;
330 if (EnableVPlanNativePath && (CBV = getCondBit())) {
331 Value *IRCBV = CBV->getUnderlyingValue();
332 assert(IRCBV && "Unexpected null underlying value for condition bit");
333
334 // Condition bit value in a VPBasicBlock is used as the branch selector. In
335 // the VPlan-native path case, since all branches are uniform we generate a
336 // branch instruction using the condition value from vector lane 0 and dummy
337 // successors. The successors are fixed later when the successor blocks are
338 // visited.
339 Value *NewCond = State->Callback.getOrCreateVectorValues(IRCBV, 0);
340 NewCond = State->Builder.CreateExtractElement(NewCond,
341 State->Builder.getInt32(0));
342
343 // Replace the temporary unreachable terminator with the new conditional
344 // branch.
345 auto *CurrentTerminator = NewBB->getTerminator();
346 assert(isa<UnreachableInst>(CurrentTerminator) &&
347 "Expected to replace unreachable terminator with conditional "
348 "branch.");
349 auto *CondBr = BranchInst::Create(NewBB, nullptr, NewCond);
350 CondBr->setSuccessor(0, nullptr);
351 ReplaceInstWithInst(CurrentTerminator, CondBr);
352 }
353
354 LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
355 }
356
dropAllReferences(VPValue * NewValue)357 void VPBasicBlock::dropAllReferences(VPValue *NewValue) {
358 for (VPRecipeBase &R : Recipes) {
359 for (auto *Def : R.definedValues())
360 Def->replaceAllUsesWith(NewValue);
361
362 if (auto *User = R.toVPUser())
363 for (unsigned I = 0, E = User->getNumOperands(); I != E; I++)
364 User->setOperand(I, NewValue);
365 }
366 }
367
dropAllReferences(VPValue * NewValue)368 void VPRegionBlock::dropAllReferences(VPValue *NewValue) {
369 for (VPBlockBase *Block : depth_first(Entry))
370 // Drop all references in VPBasicBlocks and replace all uses with
371 // DummyValue.
372 Block->dropAllReferences(NewValue);
373 }
374
execute(VPTransformState * State)375 void VPRegionBlock::execute(VPTransformState *State) {
376 ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
377
378 if (!isReplicator()) {
379 // Visit the VPBlocks connected to "this", starting from it.
380 for (VPBlockBase *Block : RPOT) {
381 if (EnableVPlanNativePath) {
382 // The inner loop vectorization path does not represent loop preheader
383 // and exit blocks as part of the VPlan. In the VPlan-native path, skip
384 // vectorizing loop preheader block. In future, we may replace this
385 // check with the check for loop preheader.
386 if (Block->getNumPredecessors() == 0)
387 continue;
388
389 // Skip vectorizing loop exit block. In future, we may replace this
390 // check with the check for loop exit.
391 if (Block->getNumSuccessors() == 0)
392 continue;
393 }
394
395 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
396 Block->execute(State);
397 }
398 return;
399 }
400
401 assert(!State->Instance && "Replicating a Region with non-null instance.");
402
403 // Enter replicating mode.
404 State->Instance = {0, 0};
405
406 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
407 State->Instance->Part = Part;
408 assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
409 for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
410 ++Lane) {
411 State->Instance->Lane = Lane;
412 // Visit the VPBlocks connected to \p this, starting from it.
413 for (VPBlockBase *Block : RPOT) {
414 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
415 Block->execute(State);
416 }
417 }
418 }
419
420 // Exit replicating mode.
421 State->Instance.reset();
422 }
423
insertBefore(VPRecipeBase * InsertPos)424 void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
425 assert(!Parent && "Recipe already in some VPBasicBlock");
426 assert(InsertPos->getParent() &&
427 "Insertion position not in any VPBasicBlock");
428 Parent = InsertPos->getParent();
429 Parent->getRecipeList().insert(InsertPos->getIterator(), this);
430 }
431
insertAfter(VPRecipeBase * InsertPos)432 void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {
433 assert(!Parent && "Recipe already in some VPBasicBlock");
434 assert(InsertPos->getParent() &&
435 "Insertion position not in any VPBasicBlock");
436 Parent = InsertPos->getParent();
437 Parent->getRecipeList().insertAfter(InsertPos->getIterator(), this);
438 }
439
removeFromParent()440 void VPRecipeBase::removeFromParent() {
441 assert(getParent() && "Recipe not in any VPBasicBlock");
442 getParent()->getRecipeList().remove(getIterator());
443 Parent = nullptr;
444 }
445
eraseFromParent()446 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
447 assert(getParent() && "Recipe not in any VPBasicBlock");
448 return getParent()->getRecipeList().erase(getIterator());
449 }
450
moveAfter(VPRecipeBase * InsertPos)451 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
452 removeFromParent();
453 insertAfter(InsertPos);
454 }
455
moveBefore(VPBasicBlock & BB,iplist<VPRecipeBase>::iterator I)456 void VPRecipeBase::moveBefore(VPBasicBlock &BB,
457 iplist<VPRecipeBase>::iterator I) {
458 assert(I == BB.end() || I->getParent() == &BB);
459 removeFromParent();
460 Parent = &BB;
461 BB.getRecipeList().insert(I, this);
462 }
463
generateInstruction(VPTransformState & State,unsigned Part)464 void VPInstruction::generateInstruction(VPTransformState &State,
465 unsigned Part) {
466 IRBuilder<> &Builder = State.Builder;
467
468 if (Instruction::isBinaryOp(getOpcode())) {
469 Value *A = State.get(getOperand(0), Part);
470 Value *B = State.get(getOperand(1), Part);
471 Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
472 State.set(this, V, Part);
473 return;
474 }
475
476 switch (getOpcode()) {
477 case VPInstruction::Not: {
478 Value *A = State.get(getOperand(0), Part);
479 Value *V = Builder.CreateNot(A);
480 State.set(this, V, Part);
481 break;
482 }
483 case VPInstruction::ICmpULE: {
484 Value *IV = State.get(getOperand(0), Part);
485 Value *TC = State.get(getOperand(1), Part);
486 Value *V = Builder.CreateICmpULE(IV, TC);
487 State.set(this, V, Part);
488 break;
489 }
490 case Instruction::Select: {
491 Value *Cond = State.get(getOperand(0), Part);
492 Value *Op1 = State.get(getOperand(1), Part);
493 Value *Op2 = State.get(getOperand(2), Part);
494 Value *V = Builder.CreateSelect(Cond, Op1, Op2);
495 State.set(this, V, Part);
496 break;
497 }
498 case VPInstruction::ActiveLaneMask: {
499 // Get first lane of vector induction variable.
500 Value *VIVElem0 = State.get(getOperand(0), {Part, 0});
501 // Get the original loop tripcount.
502 Value *ScalarTC = State.TripCount;
503
504 auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
505 auto *PredTy = FixedVectorType::get(Int1Ty, State.VF.getKnownMinValue());
506 Instruction *Call = Builder.CreateIntrinsic(
507 Intrinsic::get_active_lane_mask, {PredTy, ScalarTC->getType()},
508 {VIVElem0, ScalarTC}, nullptr, "active.lane.mask");
509 State.set(this, Call, Part);
510 break;
511 }
512 default:
513 llvm_unreachable("Unsupported opcode for instruction");
514 }
515 }
516
execute(VPTransformState & State)517 void VPInstruction::execute(VPTransformState &State) {
518 assert(!State.Instance && "VPInstruction executing an Instance");
519 for (unsigned Part = 0; Part < State.UF; ++Part)
520 generateInstruction(State, Part);
521 }
522
dump() const523 void VPInstruction::dump() const {
524 VPSlotTracker SlotTracker(getParent()->getPlan());
525 print(dbgs(), "", SlotTracker);
526 }
527
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const528 void VPInstruction::print(raw_ostream &O, const Twine &Indent,
529 VPSlotTracker &SlotTracker) const {
530 O << "EMIT ";
531
532 if (hasResult()) {
533 printAsOperand(O, SlotTracker);
534 O << " = ";
535 }
536
537 switch (getOpcode()) {
538 case VPInstruction::Not:
539 O << "not";
540 break;
541 case VPInstruction::ICmpULE:
542 O << "icmp ule";
543 break;
544 case VPInstruction::SLPLoad:
545 O << "combined load";
546 break;
547 case VPInstruction::SLPStore:
548 O << "combined store";
549 break;
550 case VPInstruction::ActiveLaneMask:
551 O << "active lane mask";
552 break;
553
554 default:
555 O << Instruction::getOpcodeName(getOpcode());
556 }
557
558 for (const VPValue *Operand : operands()) {
559 O << " ";
560 Operand->printAsOperand(O, SlotTracker);
561 }
562 }
563
564 /// Generate the code inside the body of the vectorized loop. Assumes a single
565 /// LoopVectorBody basic-block was created for this. Introduce additional
566 /// basic-blocks as needed, and fill them all.
execute(VPTransformState * State)567 void VPlan::execute(VPTransformState *State) {
568 // -1. Check if the backedge taken count is needed, and if so build it.
569 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
570 Value *TC = State->TripCount;
571 IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
572 auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
573 "trip.count.minus.1");
574 auto VF = State->VF;
575 Value *VTCMO =
576 VF.isScalar() ? TCMO : Builder.CreateVectorSplat(VF, TCMO, "broadcast");
577 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part)
578 State->set(BackedgeTakenCount, VTCMO, Part);
579 }
580
581 // 0. Set the reverse mapping from VPValues to Values for code generation.
582 for (auto &Entry : Value2VPValue)
583 State->VPValue2Value[Entry.second] = Entry.first;
584
585 BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
586 BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
587 assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
588
589 // 1. Make room to generate basic-blocks inside loop body if needed.
590 BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
591 VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
592 Loop *L = State->LI->getLoopFor(VectorHeaderBB);
593 L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
594 // Remove the edge between Header and Latch to allow other connections.
595 // Temporarily terminate with unreachable until CFG is rewired.
596 // Note: this asserts the generated code's assumption that
597 // getFirstInsertionPt() can be dereferenced into an Instruction.
598 VectorHeaderBB->getTerminator()->eraseFromParent();
599 State->Builder.SetInsertPoint(VectorHeaderBB);
600 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
601 State->Builder.SetInsertPoint(Terminator);
602
603 // 2. Generate code in loop body.
604 State->CFG.PrevVPBB = nullptr;
605 State->CFG.PrevBB = VectorHeaderBB;
606 State->CFG.LastBB = VectorLatchBB;
607
608 for (VPBlockBase *Block : depth_first(Entry))
609 Block->execute(State);
610
611 // Setup branch terminator successors for VPBBs in VPBBsToFix based on
612 // VPBB's successors.
613 for (auto VPBB : State->CFG.VPBBsToFix) {
614 assert(EnableVPlanNativePath &&
615 "Unexpected VPBBsToFix in non VPlan-native path");
616 BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
617 assert(BB && "Unexpected null basic block for VPBB");
618
619 unsigned Idx = 0;
620 auto *BBTerminator = BB->getTerminator();
621
622 for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
623 VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
624 BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
625 ++Idx;
626 }
627 }
628
629 // 3. Merge the temporary latch created with the last basic-block filled.
630 BasicBlock *LastBB = State->CFG.PrevBB;
631 // Connect LastBB to VectorLatchBB to facilitate their merge.
632 assert((EnableVPlanNativePath ||
633 isa<UnreachableInst>(LastBB->getTerminator())) &&
634 "Expected InnerLoop VPlan CFG to terminate with unreachable");
635 assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
636 "Expected VPlan CFG to terminate with branch in NativePath");
637 LastBB->getTerminator()->eraseFromParent();
638 BranchInst::Create(VectorLatchBB, LastBB);
639
640 // Merge LastBB with Latch.
641 bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
642 (void)Merged;
643 assert(Merged && "Could not merge last basic block with latch.");
644 VectorLatchBB = LastBB;
645
646 // We do not attempt to preserve DT for outer loop vectorization currently.
647 if (!EnableVPlanNativePath)
648 updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB,
649 L->getExitBlock());
650 }
651
652 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
653 LLVM_DUMP_METHOD
dump() const654 void VPlan::dump() const { dbgs() << *this << '\n'; }
655 #endif
656
updateDominatorTree(DominatorTree * DT,BasicBlock * LoopPreHeaderBB,BasicBlock * LoopLatchBB,BasicBlock * LoopExitBB)657 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
658 BasicBlock *LoopLatchBB,
659 BasicBlock *LoopExitBB) {
660 BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
661 assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
662 // The vector body may be more than a single basic-block by this point.
663 // Update the dominator tree information inside the vector body by propagating
664 // it from header to latch, expecting only triangular control-flow, if any.
665 BasicBlock *PostDomSucc = nullptr;
666 for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
667 // Get the list of successors of this block.
668 std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
669 assert(Succs.size() <= 2 &&
670 "Basic block in vector loop has more than 2 successors.");
671 PostDomSucc = Succs[0];
672 if (Succs.size() == 1) {
673 assert(PostDomSucc->getSinglePredecessor() &&
674 "PostDom successor has more than one predecessor.");
675 DT->addNewBlock(PostDomSucc, BB);
676 continue;
677 }
678 BasicBlock *InterimSucc = Succs[1];
679 if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
680 PostDomSucc = Succs[1];
681 InterimSucc = Succs[0];
682 }
683 assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
684 "One successor of a basic block does not lead to the other.");
685 assert(InterimSucc->getSinglePredecessor() &&
686 "Interim successor has more than one predecessor.");
687 assert(PostDomSucc->hasNPredecessors(2) &&
688 "PostDom successor has more than two predecessors.");
689 DT->addNewBlock(InterimSucc, BB);
690 DT->addNewBlock(PostDomSucc, BB);
691 }
692 // Latch block is a new dominator for the loop exit.
693 DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
694 assert(DT->verify(DominatorTree::VerificationLevel::Fast));
695 }
696
getUID(const VPBlockBase * Block)697 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
698 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
699 Twine(getOrCreateBID(Block));
700 }
701
getOrCreateName(const VPBlockBase * Block)702 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
703 const std::string &Name = Block->getName();
704 if (!Name.empty())
705 return Name;
706 return "VPB" + Twine(getOrCreateBID(Block));
707 }
708
dump()709 void VPlanPrinter::dump() {
710 Depth = 1;
711 bumpIndent(0);
712 OS << "digraph VPlan {\n";
713 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
714 if (!Plan.getName().empty())
715 OS << "\\n" << DOT::EscapeString(Plan.getName());
716 if (Plan.BackedgeTakenCount) {
717 OS << ", where:\\n";
718 Plan.BackedgeTakenCount->print(OS, SlotTracker);
719 OS << " := BackedgeTakenCount";
720 }
721 OS << "\"]\n";
722 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
723 OS << "edge [fontname=Courier, fontsize=30]\n";
724 OS << "compound=true\n";
725
726 for (const VPBlockBase *Block : depth_first(Plan.getEntry()))
727 dumpBlock(Block);
728
729 OS << "}\n";
730 }
731
dumpBlock(const VPBlockBase * Block)732 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
733 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
734 dumpBasicBlock(BasicBlock);
735 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
736 dumpRegion(Region);
737 else
738 llvm_unreachable("Unsupported kind of VPBlock.");
739 }
740
drawEdge(const VPBlockBase * From,const VPBlockBase * To,bool Hidden,const Twine & Label)741 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
742 bool Hidden, const Twine &Label) {
743 // Due to "dot" we print an edge between two regions as an edge between the
744 // exit basic block and the entry basic of the respective regions.
745 const VPBlockBase *Tail = From->getExitBasicBlock();
746 const VPBlockBase *Head = To->getEntryBasicBlock();
747 OS << Indent << getUID(Tail) << " -> " << getUID(Head);
748 OS << " [ label=\"" << Label << '\"';
749 if (Tail != From)
750 OS << " ltail=" << getUID(From);
751 if (Head != To)
752 OS << " lhead=" << getUID(To);
753 if (Hidden)
754 OS << "; splines=none";
755 OS << "]\n";
756 }
757
dumpEdges(const VPBlockBase * Block)758 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
759 auto &Successors = Block->getSuccessors();
760 if (Successors.size() == 1)
761 drawEdge(Block, Successors.front(), false, "");
762 else if (Successors.size() == 2) {
763 drawEdge(Block, Successors.front(), false, "T");
764 drawEdge(Block, Successors.back(), false, "F");
765 } else {
766 unsigned SuccessorNumber = 0;
767 for (auto *Successor : Successors)
768 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
769 }
770 }
771
dumpBasicBlock(const VPBasicBlock * BasicBlock)772 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
773 OS << Indent << getUID(BasicBlock) << " [label =\n";
774 bumpIndent(1);
775 OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
776 bumpIndent(1);
777
778 // Dump the block predicate.
779 const VPValue *Pred = BasicBlock->getPredicate();
780 if (Pred) {
781 OS << " +\n" << Indent << " \"BlockPredicate: \"";
782 if (const VPInstruction *PredI = dyn_cast<VPInstruction>(Pred)) {
783 PredI->printAsOperand(OS, SlotTracker);
784 OS << " (" << DOT::EscapeString(PredI->getParent()->getName())
785 << ")\\l\"";
786 } else
787 Pred->printAsOperand(OS, SlotTracker);
788 }
789
790 for (const VPRecipeBase &Recipe : *BasicBlock) {
791 OS << " +\n" << Indent << "\"";
792 Recipe.print(OS, Indent, SlotTracker);
793 OS << "\\l\"";
794 }
795
796 // Dump the condition bit.
797 const VPValue *CBV = BasicBlock->getCondBit();
798 if (CBV) {
799 OS << " +\n" << Indent << " \"CondBit: ";
800 if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) {
801 CBI->printAsOperand(OS, SlotTracker);
802 OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\"";
803 } else {
804 CBV->printAsOperand(OS, SlotTracker);
805 OS << "\"";
806 }
807 }
808
809 bumpIndent(-2);
810 OS << "\n" << Indent << "]\n";
811 dumpEdges(BasicBlock);
812 }
813
dumpRegion(const VPRegionBlock * Region)814 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
815 OS << Indent << "subgraph " << getUID(Region) << " {\n";
816 bumpIndent(1);
817 OS << Indent << "fontname=Courier\n"
818 << Indent << "label=\""
819 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
820 << DOT::EscapeString(Region->getName()) << "\"\n";
821 // Dump the blocks of the region.
822 assert(Region->getEntry() && "Region contains no inner blocks.");
823 for (const VPBlockBase *Block : depth_first(Region->getEntry()))
824 dumpBlock(Block);
825 bumpIndent(-1);
826 OS << Indent << "}\n";
827 dumpEdges(Region);
828 }
829
printAsIngredient(raw_ostream & O,const Value * V)830 void VPlanPrinter::printAsIngredient(raw_ostream &O, const Value *V) {
831 std::string IngredientString;
832 raw_string_ostream RSO(IngredientString);
833 if (auto *Inst = dyn_cast<Instruction>(V)) {
834 if (!Inst->getType()->isVoidTy()) {
835 Inst->printAsOperand(RSO, false);
836 RSO << " = ";
837 }
838 RSO << Inst->getOpcodeName() << " ";
839 unsigned E = Inst->getNumOperands();
840 if (E > 0) {
841 Inst->getOperand(0)->printAsOperand(RSO, false);
842 for (unsigned I = 1; I < E; ++I)
843 Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
844 }
845 } else // !Inst
846 V->printAsOperand(RSO, false);
847 RSO.flush();
848 O << DOT::EscapeString(IngredientString);
849 }
850
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const851 void VPWidenCallRecipe::print(raw_ostream &O, const Twine &Indent,
852 VPSlotTracker &SlotTracker) const {
853 O << "WIDEN-CALL ";
854
855 auto *CI = cast<CallInst>(getUnderlyingInstr());
856 if (CI->getType()->isVoidTy())
857 O << "void ";
858 else {
859 printAsOperand(O, SlotTracker);
860 O << " = ";
861 }
862
863 O << "call @" << CI->getCalledFunction()->getName() << "(";
864 printOperands(O, SlotTracker);
865 O << ")";
866 }
867
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const868 void VPWidenSelectRecipe::print(raw_ostream &O, const Twine &Indent,
869 VPSlotTracker &SlotTracker) const {
870 O << "WIDEN-SELECT ";
871 printAsOperand(O, SlotTracker);
872 O << " = select ";
873 getOperand(0)->printAsOperand(O, SlotTracker);
874 O << ", ";
875 getOperand(1)->printAsOperand(O, SlotTracker);
876 O << ", ";
877 getOperand(2)->printAsOperand(O, SlotTracker);
878 O << (InvariantCond ? " (condition is loop invariant)" : "");
879 }
880
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const881 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent,
882 VPSlotTracker &SlotTracker) const {
883 O << "WIDEN ";
884 printAsOperand(O, SlotTracker);
885 O << " = " << getUnderlyingInstr()->getOpcodeName() << " ";
886 printOperands(O, SlotTracker);
887 }
888
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const889 void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, const Twine &Indent,
890 VPSlotTracker &SlotTracker) const {
891 O << "WIDEN-INDUCTION";
892 if (Trunc) {
893 O << "\\l\"";
894 O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
895 O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc);
896 } else
897 O << " " << VPlanIngredient(IV);
898 }
899
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const900 void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent,
901 VPSlotTracker &SlotTracker) const {
902 O << "WIDEN-GEP ";
903 O << (IsPtrLoopInvariant ? "Inv" : "Var");
904 size_t IndicesNumber = IsIndexLoopInvariant.size();
905 for (size_t I = 0; I < IndicesNumber; ++I)
906 O << "[" << (IsIndexLoopInvariant[I] ? "Inv" : "Var") << "]";
907
908 O << " ";
909 printAsOperand(O, SlotTracker);
910 O << " = getelementptr ";
911 printOperands(O, SlotTracker);
912 }
913
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const914 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent,
915 VPSlotTracker &SlotTracker) const {
916 O << "WIDEN-PHI " << VPlanIngredient(Phi);
917 }
918
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const919 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent,
920 VPSlotTracker &SlotTracker) const {
921 O << "BLEND ";
922 Phi->printAsOperand(O, false);
923 O << " =";
924 if (getNumIncomingValues() == 1) {
925 // Not a User of any mask: not really blending, this is a
926 // single-predecessor phi.
927 O << " ";
928 getIncomingValue(0)->printAsOperand(O, SlotTracker);
929 } else {
930 for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
931 O << " ";
932 getIncomingValue(I)->printAsOperand(O, SlotTracker);
933 O << "/";
934 getMask(I)->printAsOperand(O, SlotTracker);
935 }
936 }
937 }
938
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const939 void VPReductionRecipe::print(raw_ostream &O, const Twine &Indent,
940 VPSlotTracker &SlotTracker) const {
941 O << "REDUCE ";
942 printAsOperand(O, SlotTracker);
943 O << " = ";
944 getChainOp()->printAsOperand(O, SlotTracker);
945 O << " + reduce." << Instruction::getOpcodeName(RdxDesc->getOpcode())
946 << " (";
947 getVecOp()->printAsOperand(O, SlotTracker);
948 if (getCondOp()) {
949 O << ", ";
950 getCondOp()->printAsOperand(O, SlotTracker);
951 }
952 O << ")";
953 }
954
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const955 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent,
956 VPSlotTracker &SlotTracker) const {
957 O << (IsUniform ? "CLONE " : "REPLICATE ");
958
959 if (!getUnderlyingInstr()->getType()->isVoidTy()) {
960 printAsOperand(O, SlotTracker);
961 O << " = ";
962 }
963 O << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode()) << " ";
964 printOperands(O, SlotTracker);
965
966 if (AlsoPack)
967 O << " (S->V)";
968 }
969
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const970 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent,
971 VPSlotTracker &SlotTracker) const {
972 O << "PHI-PREDICATED-INSTRUCTION ";
973 printOperands(O, SlotTracker);
974 }
975
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const976 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent,
977 VPSlotTracker &SlotTracker) const {
978 O << "WIDEN ";
979
980 if (!isStore()) {
981 getVPValue()->printAsOperand(O, SlotTracker);
982 O << " = ";
983 }
984 O << Instruction::getOpcodeName(Ingredient.getOpcode()) << " ";
985
986 printOperands(O, SlotTracker);
987 }
988
execute(VPTransformState & State)989 void VPWidenCanonicalIVRecipe::execute(VPTransformState &State) {
990 Value *CanonicalIV = State.CanonicalIV;
991 Type *STy = CanonicalIV->getType();
992 IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
993 ElementCount VF = State.VF;
994 assert(!VF.isScalable() && "the code following assumes non scalables ECs");
995 Value *VStart = VF.isScalar()
996 ? CanonicalIV
997 : Builder.CreateVectorSplat(VF.getKnownMinValue(),
998 CanonicalIV, "broadcast");
999 for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
1000 SmallVector<Constant *, 8> Indices;
1001 for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
1002 Indices.push_back(
1003 ConstantInt::get(STy, Part * VF.getKnownMinValue() + Lane));
1004 // If VF == 1, there is only one iteration in the loop above, thus the
1005 // element pushed back into Indices is ConstantInt::get(STy, Part)
1006 Constant *VStep =
1007 VF.isScalar() ? Indices.back() : ConstantVector::get(Indices);
1008 // Add the consecutive indices to the vector value.
1009 Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
1010 State.set(getVPValue(), CanonicalVectorIV, Part);
1011 }
1012 }
1013
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1014 void VPWidenCanonicalIVRecipe::print(raw_ostream &O, const Twine &Indent,
1015 VPSlotTracker &SlotTracker) const {
1016 O << "EMIT ";
1017 getVPValue()->printAsOperand(O, SlotTracker);
1018 O << " = WIDEN-CANONICAL-INDUCTION";
1019 }
1020
1021 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1022
replaceAllUsesWith(VPValue * New)1023 void VPValue::replaceAllUsesWith(VPValue *New) {
1024 for (unsigned J = 0; J < getNumUsers();) {
1025 VPUser *User = Users[J];
1026 unsigned NumUsers = getNumUsers();
1027 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
1028 if (User->getOperand(I) == this)
1029 User->setOperand(I, New);
1030 // If a user got removed after updating the current user, the next user to
1031 // update will be moved to the current position, so we only need to
1032 // increment the index if the number of users did not change.
1033 if (NumUsers == getNumUsers())
1034 J++;
1035 }
1036 }
1037
printAsOperand(raw_ostream & OS,VPSlotTracker & Tracker) const1038 void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const {
1039 if (const Value *UV = getUnderlyingValue()) {
1040 OS << "ir<";
1041 UV->printAsOperand(OS, false);
1042 OS << ">";
1043 return;
1044 }
1045
1046 unsigned Slot = Tracker.getSlot(this);
1047 if (Slot == unsigned(-1))
1048 OS << "<badref>";
1049 else
1050 OS << "vp<%" << Tracker.getSlot(this) << ">";
1051 }
1052
printOperands(raw_ostream & O,VPSlotTracker & SlotTracker) const1053 void VPUser::printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const {
1054 interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
1055 Op->printAsOperand(O, SlotTracker);
1056 });
1057 }
1058
visitRegion(VPRegionBlock * Region,Old2NewTy & Old2New,InterleavedAccessInfo & IAI)1059 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1060 Old2NewTy &Old2New,
1061 InterleavedAccessInfo &IAI) {
1062 ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
1063 for (VPBlockBase *Base : RPOT) {
1064 visitBlock(Base, Old2New, IAI);
1065 }
1066 }
1067
visitBlock(VPBlockBase * Block,Old2NewTy & Old2New,InterleavedAccessInfo & IAI)1068 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1069 InterleavedAccessInfo &IAI) {
1070 if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1071 for (VPRecipeBase &VPI : *VPBB) {
1072 assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1073 auto *VPInst = cast<VPInstruction>(&VPI);
1074 auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
1075 auto *IG = IAI.getInterleaveGroup(Inst);
1076 if (!IG)
1077 continue;
1078
1079 auto NewIGIter = Old2New.find(IG);
1080 if (NewIGIter == Old2New.end())
1081 Old2New[IG] = new InterleaveGroup<VPInstruction>(
1082 IG->getFactor(), IG->isReverse(), IG->getAlign());
1083
1084 if (Inst == IG->getInsertPos())
1085 Old2New[IG]->setInsertPos(VPInst);
1086
1087 InterleaveGroupMap[VPInst] = Old2New[IG];
1088 InterleaveGroupMap[VPInst]->insertMember(
1089 VPInst, IG->getIndex(Inst),
1090 Align(IG->isReverse() ? (-1) * int(IG->getFactor())
1091 : IG->getFactor()));
1092 }
1093 } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1094 visitRegion(Region, Old2New, IAI);
1095 else
1096 llvm_unreachable("Unsupported kind of VPBlock.");
1097 }
1098
VPInterleavedAccessInfo(VPlan & Plan,InterleavedAccessInfo & IAI)1099 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
1100 InterleavedAccessInfo &IAI) {
1101 Old2NewTy Old2New;
1102 visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
1103 }
1104
assignSlot(const VPValue * V)1105 void VPSlotTracker::assignSlot(const VPValue *V) {
1106 assert(Slots.find(V) == Slots.end() && "VPValue already has a slot!");
1107 Slots[V] = NextSlot++;
1108 }
1109
assignSlots(const VPBlockBase * VPBB)1110 void VPSlotTracker::assignSlots(const VPBlockBase *VPBB) {
1111 if (auto *Region = dyn_cast<VPRegionBlock>(VPBB))
1112 assignSlots(Region);
1113 else
1114 assignSlots(cast<VPBasicBlock>(VPBB));
1115 }
1116
assignSlots(const VPRegionBlock * Region)1117 void VPSlotTracker::assignSlots(const VPRegionBlock *Region) {
1118 ReversePostOrderTraversal<const VPBlockBase *> RPOT(Region->getEntry());
1119 for (const VPBlockBase *Block : RPOT)
1120 assignSlots(Block);
1121 }
1122
assignSlots(const VPBasicBlock * VPBB)1123 void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) {
1124 for (const VPRecipeBase &Recipe : *VPBB) {
1125 for (VPValue *Def : Recipe.definedValues())
1126 assignSlot(Def);
1127 }
1128 }
1129
assignSlots(const VPlan & Plan)1130 void VPSlotTracker::assignSlots(const VPlan &Plan) {
1131
1132 for (const VPValue *V : Plan.VPExternalDefs)
1133 assignSlot(V);
1134
1135 for (const VPValue *V : Plan.VPCBVs)
1136 assignSlot(V);
1137
1138 if (Plan.BackedgeTakenCount)
1139 assignSlot(Plan.BackedgeTakenCount);
1140
1141 ReversePostOrderTraversal<const VPBlockBase *> RPOT(Plan.getEntry());
1142 for (const VPBlockBase *Block : RPOT)
1143 assignSlots(Block);
1144 }
1145