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
53 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
operator <<(raw_ostream & OS,const VPValue & V)54 raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
55 const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
56 VPSlotTracker SlotTracker(
57 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
58 V.print(OS, SlotTracker);
59 return OS;
60 }
61 #endif
62
getAsRuntimeExpr(IRBuilder<> & Builder,const ElementCount & VF) const63 Value *VPLane::getAsRuntimeExpr(IRBuilder<> &Builder,
64 const ElementCount &VF) const {
65 switch (LaneKind) {
66 case VPLane::Kind::ScalableLast:
67 // Lane = RuntimeVF - VF.getKnownMinValue() + Lane
68 return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),
69 Builder.getInt32(VF.getKnownMinValue() - Lane));
70 case VPLane::Kind::First:
71 return Builder.getInt32(Lane);
72 }
73 llvm_unreachable("Unknown lane kind");
74 }
75
VPValue(const unsigned char SC,Value * UV,VPDef * Def)76 VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
77 : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
78 if (Def)
79 Def->addDefinedValue(this);
80 }
81
~VPValue()82 VPValue::~VPValue() {
83 assert(Users.empty() && "trying to delete a VPValue with remaining users");
84 if (Def)
85 Def->removeDefinedValue(this);
86 }
87
88 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & OS,VPSlotTracker & SlotTracker) const89 void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const {
90 if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def))
91 R->print(OS, "", SlotTracker);
92 else
93 printAsOperand(OS, SlotTracker);
94 }
95
dump() const96 void VPValue::dump() const {
97 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def);
98 VPSlotTracker SlotTracker(
99 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
100 print(dbgs(), SlotTracker);
101 dbgs() << "\n";
102 }
103
dump() const104 void VPDef::dump() const {
105 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);
106 VPSlotTracker SlotTracker(
107 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
108 print(dbgs(), "", SlotTracker);
109 dbgs() << "\n";
110 }
111 #endif
112
113 // Get the top-most entry block of \p Start. This is the entry block of the
114 // containing VPlan. This function is templated to support both const and non-const blocks
getPlanEntry(T * Start)115 template <typename T> static T *getPlanEntry(T *Start) {
116 T *Next = Start;
117 T *Current = Start;
118 while ((Next = Next->getParent()))
119 Current = Next;
120
121 SmallSetVector<T *, 8> WorkList;
122 WorkList.insert(Current);
123
124 for (unsigned i = 0; i < WorkList.size(); i++) {
125 T *Current = WorkList[i];
126 if (Current->getNumPredecessors() == 0)
127 return Current;
128 auto &Predecessors = Current->getPredecessors();
129 WorkList.insert(Predecessors.begin(), Predecessors.end());
130 }
131
132 llvm_unreachable("VPlan without any entry node without predecessors");
133 }
134
getPlan()135 VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
136
getPlan() const137 const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
138
139 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
getEntryBasicBlock() const140 const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
141 const VPBlockBase *Block = this;
142 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
143 Block = Region->getEntry();
144 return cast<VPBasicBlock>(Block);
145 }
146
getEntryBasicBlock()147 VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
148 VPBlockBase *Block = this;
149 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
150 Block = Region->getEntry();
151 return cast<VPBasicBlock>(Block);
152 }
153
setPlan(VPlan * ParentPlan)154 void VPBlockBase::setPlan(VPlan *ParentPlan) {
155 assert(ParentPlan->getEntry() == this &&
156 "Can only set plan on its entry block.");
157 Plan = ParentPlan;
158 }
159
160 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
getExitBasicBlock() const161 const VPBasicBlock *VPBlockBase::getExitBasicBlock() const {
162 const VPBlockBase *Block = this;
163 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
164 Block = Region->getExit();
165 return cast<VPBasicBlock>(Block);
166 }
167
getExitBasicBlock()168 VPBasicBlock *VPBlockBase::getExitBasicBlock() {
169 VPBlockBase *Block = this;
170 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
171 Block = Region->getExit();
172 return cast<VPBasicBlock>(Block);
173 }
174
getEnclosingBlockWithSuccessors()175 VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
176 if (!Successors.empty() || !Parent)
177 return this;
178 assert(Parent->getExit() == this &&
179 "Block w/o successors not the exit of its parent.");
180 return Parent->getEnclosingBlockWithSuccessors();
181 }
182
getEnclosingBlockWithPredecessors()183 VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
184 if (!Predecessors.empty() || !Parent)
185 return this;
186 assert(Parent->getEntry() == this &&
187 "Block w/o predecessors not the entry of its parent.");
188 return Parent->getEnclosingBlockWithPredecessors();
189 }
190
getCondBit()191 VPValue *VPBlockBase::getCondBit() {
192 return CondBitUser.getSingleOperandOrNull();
193 }
194
getCondBit() const195 const VPValue *VPBlockBase::getCondBit() const {
196 return CondBitUser.getSingleOperandOrNull();
197 }
198
setCondBit(VPValue * CV)199 void VPBlockBase::setCondBit(VPValue *CV) { CondBitUser.resetSingleOpUser(CV); }
200
getPredicate()201 VPValue *VPBlockBase::getPredicate() {
202 return PredicateUser.getSingleOperandOrNull();
203 }
204
getPredicate() const205 const VPValue *VPBlockBase::getPredicate() const {
206 return PredicateUser.getSingleOperandOrNull();
207 }
208
setPredicate(VPValue * CV)209 void VPBlockBase::setPredicate(VPValue *CV) {
210 PredicateUser.resetSingleOpUser(CV);
211 }
212
deleteCFG(VPBlockBase * Entry)213 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
214 SmallVector<VPBlockBase *, 8> Blocks(depth_first(Entry));
215
216 for (VPBlockBase *Block : Blocks)
217 delete Block;
218 }
219
getFirstNonPhi()220 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
221 iterator It = begin();
222 while (It != end() && It->isPhi())
223 It++;
224 return It;
225 }
226
get(VPValue * Def,const VPIteration & Instance)227 Value *VPTransformState::get(VPValue *Def, const VPIteration &Instance) {
228 if (!Def->getDef())
229 return Def->getLiveInIRValue();
230
231 if (hasScalarValue(Def, Instance)) {
232 return Data
233 .PerPartScalars[Def][Instance.Part][Instance.Lane.mapToCacheIndex(VF)];
234 }
235
236 assert(hasVectorValue(Def, Instance.Part));
237 auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
238 if (!VecPart->getType()->isVectorTy()) {
239 assert(Instance.Lane.isFirstLane() && "cannot get lane > 0 for scalar");
240 return VecPart;
241 }
242 // TODO: Cache created scalar values.
243 Value *Lane = Instance.Lane.getAsRuntimeExpr(Builder, VF);
244 auto *Extract = Builder.CreateExtractElement(VecPart, Lane);
245 // set(Def, Extract, Instance);
246 return Extract;
247 }
248
249 BasicBlock *
createEmptyBasicBlock(VPTransformState::CFGState & CFG)250 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
251 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
252 // Pred stands for Predessor. Prev stands for Previous - last visited/created.
253 BasicBlock *PrevBB = CFG.PrevBB;
254 BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
255 PrevBB->getParent(), CFG.LastBB);
256 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
257
258 // Hook up the new basic block to its predecessors.
259 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
260 VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
261 auto &PredVPSuccessors = PredVPBB->getSuccessors();
262 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
263
264 // In outer loop vectorization scenario, the predecessor BBlock may not yet
265 // be visited(backedge). Mark the VPBasicBlock for fixup at the end of
266 // vectorization. We do not encounter this case in inner loop vectorization
267 // as we start out by building a loop skeleton with the vector loop header
268 // and latch blocks. As a result, we never enter this function for the
269 // header block in the non VPlan-native path.
270 if (!PredBB) {
271 assert(EnableVPlanNativePath &&
272 "Unexpected null predecessor in non VPlan-native path");
273 CFG.VPBBsToFix.push_back(PredVPBB);
274 continue;
275 }
276
277 assert(PredBB && "Predecessor basic-block not found building successor.");
278 auto *PredBBTerminator = PredBB->getTerminator();
279 LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
280 if (isa<UnreachableInst>(PredBBTerminator)) {
281 assert(PredVPSuccessors.size() == 1 &&
282 "Predecessor ending w/o branch must have single successor.");
283 PredBBTerminator->eraseFromParent();
284 BranchInst::Create(NewBB, PredBB);
285 } else {
286 assert(PredVPSuccessors.size() == 2 &&
287 "Predecessor ending with branch must have two successors.");
288 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
289 assert(!PredBBTerminator->getSuccessor(idx) &&
290 "Trying to reset an existing successor block.");
291 PredBBTerminator->setSuccessor(idx, NewBB);
292 }
293 }
294 return NewBB;
295 }
296
execute(VPTransformState * State)297 void VPBasicBlock::execute(VPTransformState *State) {
298 bool Replica = State->Instance && !State->Instance->isFirstIteration();
299 VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
300 VPBlockBase *SingleHPred = nullptr;
301 BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
302
303 // 1. Create an IR basic block, or reuse the last one if possible.
304 // The last IR basic block is reused, as an optimization, in three cases:
305 // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
306 // B. when the current VPBB has a single (hierarchical) predecessor which
307 // is PrevVPBB and the latter has a single (hierarchical) successor; and
308 // C. when the current VPBB is an entry of a region replica - where PrevVPBB
309 // is the exit of this region from a previous instance, or the predecessor
310 // of this region.
311 if (PrevVPBB && /* A */
312 !((SingleHPred = getSingleHierarchicalPredecessor()) &&
313 SingleHPred->getExitBasicBlock() == PrevVPBB &&
314 PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
315 !(Replica && getPredecessors().empty())) { /* C */
316 NewBB = createEmptyBasicBlock(State->CFG);
317 State->Builder.SetInsertPoint(NewBB);
318 // Temporarily terminate with unreachable until CFG is rewired.
319 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
320 State->Builder.SetInsertPoint(Terminator);
321 // Register NewBB in its loop. In innermost loops its the same for all BB's.
322 Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
323 L->addBasicBlockToLoop(NewBB, *State->LI);
324 State->CFG.PrevBB = NewBB;
325 }
326
327 // 2. Fill the IR basic block with IR instructions.
328 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
329 << " in BB:" << NewBB->getName() << '\n');
330
331 State->CFG.VPBB2IRBB[this] = NewBB;
332 State->CFG.PrevVPBB = this;
333
334 for (VPRecipeBase &Recipe : Recipes)
335 Recipe.execute(*State);
336
337 VPValue *CBV;
338 if (EnableVPlanNativePath && (CBV = getCondBit())) {
339 assert(CBV->getUnderlyingValue() &&
340 "Unexpected null underlying value for condition bit");
341
342 // Condition bit value in a VPBasicBlock is used as the branch selector. In
343 // the VPlan-native path case, since all branches are uniform we generate a
344 // branch instruction using the condition value from vector lane 0 and dummy
345 // successors. The successors are fixed later when the successor blocks are
346 // visited.
347 Value *NewCond = State->get(CBV, {0, 0});
348
349 // Replace the temporary unreachable terminator with the new conditional
350 // branch.
351 auto *CurrentTerminator = NewBB->getTerminator();
352 assert(isa<UnreachableInst>(CurrentTerminator) &&
353 "Expected to replace unreachable terminator with conditional "
354 "branch.");
355 auto *CondBr = BranchInst::Create(NewBB, nullptr, NewCond);
356 CondBr->setSuccessor(0, nullptr);
357 ReplaceInstWithInst(CurrentTerminator, CondBr);
358 }
359
360 LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
361 }
362
dropAllReferences(VPValue * NewValue)363 void VPBasicBlock::dropAllReferences(VPValue *NewValue) {
364 for (VPRecipeBase &R : Recipes) {
365 for (auto *Def : R.definedValues())
366 Def->replaceAllUsesWith(NewValue);
367
368 for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
369 R.setOperand(I, NewValue);
370 }
371 }
372
splitAt(iterator SplitAt)373 VPBasicBlock *VPBasicBlock::splitAt(iterator SplitAt) {
374 assert((SplitAt == end() || SplitAt->getParent() == this) &&
375 "can only split at a position in the same block");
376
377 SmallVector<VPBlockBase *, 2> Succs(getSuccessors().begin(),
378 getSuccessors().end());
379 // First, disconnect the current block from its successors.
380 for (VPBlockBase *Succ : Succs)
381 VPBlockUtils::disconnectBlocks(this, Succ);
382
383 // Create new empty block after the block to split.
384 auto *SplitBlock = new VPBasicBlock(getName() + ".split");
385 VPBlockUtils::insertBlockAfter(SplitBlock, this);
386
387 // Add successors for block to split to new block.
388 for (VPBlockBase *Succ : Succs)
389 VPBlockUtils::connectBlocks(SplitBlock, Succ);
390
391 // Finally, move the recipes starting at SplitAt to new block.
392 for (VPRecipeBase &ToMove :
393 make_early_inc_range(make_range(SplitAt, this->end())))
394 ToMove.moveBefore(*SplitBlock, SplitBlock->end());
395
396 return SplitBlock;
397 }
398
399 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
printSuccessors(raw_ostream & O,const Twine & Indent) const400 void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
401 if (getSuccessors().empty()) {
402 O << Indent << "No successors\n";
403 } else {
404 O << Indent << "Successor(s): ";
405 ListSeparator LS;
406 for (auto *Succ : getSuccessors())
407 O << LS << Succ->getName();
408 O << '\n';
409 }
410 }
411
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const412 void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
413 VPSlotTracker &SlotTracker) const {
414 O << Indent << getName() << ":\n";
415 if (const VPValue *Pred = getPredicate()) {
416 O << Indent << "BlockPredicate:";
417 Pred->printAsOperand(O, SlotTracker);
418 if (const auto *PredInst = dyn_cast<VPInstruction>(Pred))
419 O << " (" << PredInst->getParent()->getName() << ")";
420 O << '\n';
421 }
422
423 auto RecipeIndent = Indent + " ";
424 for (const VPRecipeBase &Recipe : *this) {
425 Recipe.print(O, RecipeIndent, SlotTracker);
426 O << '\n';
427 }
428
429 printSuccessors(O, Indent);
430
431 if (const VPValue *CBV = getCondBit()) {
432 O << Indent << "CondBit: ";
433 CBV->printAsOperand(O, SlotTracker);
434 if (const auto *CBI = dyn_cast<VPInstruction>(CBV))
435 O << " (" << CBI->getParent()->getName() << ")";
436 O << '\n';
437 }
438 }
439 #endif
440
dropAllReferences(VPValue * NewValue)441 void VPRegionBlock::dropAllReferences(VPValue *NewValue) {
442 for (VPBlockBase *Block : depth_first(Entry))
443 // Drop all references in VPBasicBlocks and replace all uses with
444 // DummyValue.
445 Block->dropAllReferences(NewValue);
446 }
447
execute(VPTransformState * State)448 void VPRegionBlock::execute(VPTransformState *State) {
449 ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
450
451 if (!isReplicator()) {
452 // Visit the VPBlocks connected to "this", starting from it.
453 for (VPBlockBase *Block : RPOT) {
454 if (EnableVPlanNativePath) {
455 // The inner loop vectorization path does not represent loop preheader
456 // and exit blocks as part of the VPlan. In the VPlan-native path, skip
457 // vectorizing loop preheader block. In future, we may replace this
458 // check with the check for loop preheader.
459 if (Block->getNumPredecessors() == 0)
460 continue;
461
462 // Skip vectorizing loop exit block. In future, we may replace this
463 // check with the check for loop exit.
464 if (Block->getNumSuccessors() == 0)
465 continue;
466 }
467
468 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
469 Block->execute(State);
470 }
471 return;
472 }
473
474 assert(!State->Instance && "Replicating a Region with non-null instance.");
475
476 // Enter replicating mode.
477 State->Instance = VPIteration(0, 0);
478
479 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
480 State->Instance->Part = Part;
481 assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
482 for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
483 ++Lane) {
484 State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
485 // Visit the VPBlocks connected to \p this, starting from it.
486 for (VPBlockBase *Block : RPOT) {
487 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
488 Block->execute(State);
489 }
490 }
491 }
492
493 // Exit replicating mode.
494 State->Instance.reset();
495 }
496
497 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const498 void VPRegionBlock::print(raw_ostream &O, const Twine &Indent,
499 VPSlotTracker &SlotTracker) const {
500 O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
501 auto NewIndent = Indent + " ";
502 for (auto *BlockBase : depth_first(Entry)) {
503 O << '\n';
504 BlockBase->print(O, NewIndent, SlotTracker);
505 }
506 O << Indent << "}\n";
507
508 printSuccessors(O, Indent);
509 }
510 #endif
511
mayWriteToMemory() const512 bool VPRecipeBase::mayWriteToMemory() const {
513 switch (getVPDefID()) {
514 case VPWidenMemoryInstructionSC: {
515 return cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
516 }
517 case VPReplicateSC:
518 case VPWidenCallSC:
519 return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
520 ->mayWriteToMemory();
521 case VPBranchOnMaskSC:
522 return false;
523 case VPWidenIntOrFpInductionSC:
524 case VPWidenCanonicalIVSC:
525 case VPWidenPHISC:
526 case VPBlendSC:
527 case VPWidenSC:
528 case VPWidenGEPSC:
529 case VPReductionSC:
530 case VPWidenSelectSC: {
531 const Instruction *I =
532 dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
533 (void)I;
534 assert((!I || !I->mayWriteToMemory()) &&
535 "underlying instruction may write to memory");
536 return false;
537 }
538 default:
539 return true;
540 }
541 }
542
mayReadFromMemory() const543 bool VPRecipeBase::mayReadFromMemory() const {
544 switch (getVPDefID()) {
545 case VPWidenMemoryInstructionSC: {
546 return !cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
547 }
548 case VPReplicateSC:
549 case VPWidenCallSC:
550 return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
551 ->mayReadFromMemory();
552 case VPBranchOnMaskSC:
553 return false;
554 case VPWidenIntOrFpInductionSC:
555 case VPWidenCanonicalIVSC:
556 case VPWidenPHISC:
557 case VPBlendSC:
558 case VPWidenSC:
559 case VPWidenGEPSC:
560 case VPReductionSC:
561 case VPWidenSelectSC: {
562 const Instruction *I =
563 dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
564 (void)I;
565 assert((!I || !I->mayReadFromMemory()) &&
566 "underlying instruction may read from memory");
567 return false;
568 }
569 default:
570 return true;
571 }
572 }
573
mayHaveSideEffects() const574 bool VPRecipeBase::mayHaveSideEffects() const {
575 switch (getVPDefID()) {
576 case VPBranchOnMaskSC:
577 return false;
578 case VPWidenIntOrFpInductionSC:
579 case VPWidenCanonicalIVSC:
580 case VPWidenPHISC:
581 case VPBlendSC:
582 case VPWidenSC:
583 case VPWidenGEPSC:
584 case VPReductionSC:
585 case VPWidenSelectSC: {
586 const Instruction *I =
587 dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
588 (void)I;
589 assert((!I || !I->mayHaveSideEffects()) &&
590 "underlying instruction has side-effects");
591 return false;
592 }
593 case VPReplicateSC: {
594 auto *R = cast<VPReplicateRecipe>(this);
595 return R->getUnderlyingInstr()->mayHaveSideEffects();
596 }
597 default:
598 return true;
599 }
600 }
601
insertBefore(VPRecipeBase * InsertPos)602 void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
603 assert(!Parent && "Recipe already in some VPBasicBlock");
604 assert(InsertPos->getParent() &&
605 "Insertion position not in any VPBasicBlock");
606 Parent = InsertPos->getParent();
607 Parent->getRecipeList().insert(InsertPos->getIterator(), this);
608 }
609
insertAfter(VPRecipeBase * InsertPos)610 void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {
611 assert(!Parent && "Recipe already in some VPBasicBlock");
612 assert(InsertPos->getParent() &&
613 "Insertion position not in any VPBasicBlock");
614 Parent = InsertPos->getParent();
615 Parent->getRecipeList().insertAfter(InsertPos->getIterator(), this);
616 }
617
removeFromParent()618 void VPRecipeBase::removeFromParent() {
619 assert(getParent() && "Recipe not in any VPBasicBlock");
620 getParent()->getRecipeList().remove(getIterator());
621 Parent = nullptr;
622 }
623
eraseFromParent()624 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
625 assert(getParent() && "Recipe not in any VPBasicBlock");
626 return getParent()->getRecipeList().erase(getIterator());
627 }
628
moveAfter(VPRecipeBase * InsertPos)629 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
630 removeFromParent();
631 insertAfter(InsertPos);
632 }
633
moveBefore(VPBasicBlock & BB,iplist<VPRecipeBase>::iterator I)634 void VPRecipeBase::moveBefore(VPBasicBlock &BB,
635 iplist<VPRecipeBase>::iterator I) {
636 assert(I == BB.end() || I->getParent() == &BB);
637 removeFromParent();
638 Parent = &BB;
639 BB.getRecipeList().insert(I, this);
640 }
641
generateInstruction(VPTransformState & State,unsigned Part)642 void VPInstruction::generateInstruction(VPTransformState &State,
643 unsigned Part) {
644 IRBuilder<> &Builder = State.Builder;
645
646 if (Instruction::isBinaryOp(getOpcode())) {
647 Value *A = State.get(getOperand(0), Part);
648 Value *B = State.get(getOperand(1), Part);
649 Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
650 State.set(this, V, Part);
651 return;
652 }
653
654 switch (getOpcode()) {
655 case VPInstruction::Not: {
656 Value *A = State.get(getOperand(0), Part);
657 Value *V = Builder.CreateNot(A);
658 State.set(this, V, Part);
659 break;
660 }
661 case VPInstruction::ICmpULE: {
662 Value *IV = State.get(getOperand(0), Part);
663 Value *TC = State.get(getOperand(1), Part);
664 Value *V = Builder.CreateICmpULE(IV, TC);
665 State.set(this, V, Part);
666 break;
667 }
668 case Instruction::Select: {
669 Value *Cond = State.get(getOperand(0), Part);
670 Value *Op1 = State.get(getOperand(1), Part);
671 Value *Op2 = State.get(getOperand(2), Part);
672 Value *V = Builder.CreateSelect(Cond, Op1, Op2);
673 State.set(this, V, Part);
674 break;
675 }
676 case VPInstruction::ActiveLaneMask: {
677 // Get first lane of vector induction variable.
678 Value *VIVElem0 = State.get(getOperand(0), VPIteration(Part, 0));
679 // Get the original loop tripcount.
680 Value *ScalarTC = State.TripCount;
681
682 auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
683 auto *PredTy = FixedVectorType::get(Int1Ty, State.VF.getKnownMinValue());
684 Instruction *Call = Builder.CreateIntrinsic(
685 Intrinsic::get_active_lane_mask, {PredTy, ScalarTC->getType()},
686 {VIVElem0, ScalarTC}, nullptr, "active.lane.mask");
687 State.set(this, Call, Part);
688 break;
689 }
690 case VPInstruction::FirstOrderRecurrenceSplice: {
691 // Generate code to combine the previous and current values in vector v3.
692 //
693 // vector.ph:
694 // v_init = vector(..., ..., ..., a[-1])
695 // br vector.body
696 //
697 // vector.body
698 // i = phi [0, vector.ph], [i+4, vector.body]
699 // v1 = phi [v_init, vector.ph], [v2, vector.body]
700 // v2 = a[i, i+1, i+2, i+3];
701 // v3 = vector(v1(3), v2(0, 1, 2))
702
703 // For the first part, use the recurrence phi (v1), otherwise v2.
704 auto *V1 = State.get(getOperand(0), 0);
705 Value *PartMinus1 = Part == 0 ? V1 : State.get(getOperand(1), Part - 1);
706 if (!PartMinus1->getType()->isVectorTy()) {
707 State.set(this, PartMinus1, Part);
708 } else {
709 Value *V2 = State.get(getOperand(1), Part);
710 State.set(this, Builder.CreateVectorSplice(PartMinus1, V2, -1), Part);
711 }
712 break;
713 }
714 default:
715 llvm_unreachable("Unsupported opcode for instruction");
716 }
717 }
718
execute(VPTransformState & State)719 void VPInstruction::execute(VPTransformState &State) {
720 assert(!State.Instance && "VPInstruction executing an Instance");
721 for (unsigned Part = 0; Part < State.UF; ++Part)
722 generateInstruction(State, Part);
723 }
724
725 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const726 void VPInstruction::dump() const {
727 VPSlotTracker SlotTracker(getParent()->getPlan());
728 print(dbgs(), "", SlotTracker);
729 }
730
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const731 void VPInstruction::print(raw_ostream &O, const Twine &Indent,
732 VPSlotTracker &SlotTracker) const {
733 O << Indent << "EMIT ";
734
735 if (hasResult()) {
736 printAsOperand(O, SlotTracker);
737 O << " = ";
738 }
739
740 switch (getOpcode()) {
741 case VPInstruction::Not:
742 O << "not";
743 break;
744 case VPInstruction::ICmpULE:
745 O << "icmp ule";
746 break;
747 case VPInstruction::SLPLoad:
748 O << "combined load";
749 break;
750 case VPInstruction::SLPStore:
751 O << "combined store";
752 break;
753 case VPInstruction::ActiveLaneMask:
754 O << "active lane mask";
755 break;
756 case VPInstruction::FirstOrderRecurrenceSplice:
757 O << "first-order splice";
758 break;
759 default:
760 O << Instruction::getOpcodeName(getOpcode());
761 }
762
763 for (const VPValue *Operand : operands()) {
764 O << " ";
765 Operand->printAsOperand(O, SlotTracker);
766 }
767 }
768 #endif
769
770 /// Generate the code inside the body of the vectorized loop. Assumes a single
771 /// LoopVectorBody basic-block was created for this. Introduce additional
772 /// basic-blocks as needed, and fill them all.
execute(VPTransformState * State)773 void VPlan::execute(VPTransformState *State) {
774 // -1. Check if the backedge taken count is needed, and if so build it.
775 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
776 Value *TC = State->TripCount;
777 IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
778 auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
779 "trip.count.minus.1");
780 auto VF = State->VF;
781 Value *VTCMO =
782 VF.isScalar() ? TCMO : Builder.CreateVectorSplat(VF, TCMO, "broadcast");
783 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part)
784 State->set(BackedgeTakenCount, VTCMO, Part);
785 }
786
787 // 0. Set the reverse mapping from VPValues to Values for code generation.
788 for (auto &Entry : Value2VPValue)
789 State->VPValue2Value[Entry.second] = Entry.first;
790
791 BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
792 State->CFG.VectorPreHeader = VectorPreHeaderBB;
793 BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
794 assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
795
796 // 1. Make room to generate basic-blocks inside loop body if needed.
797 BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
798 VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
799 Loop *L = State->LI->getLoopFor(VectorHeaderBB);
800 L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
801 // Remove the edge between Header and Latch to allow other connections.
802 // Temporarily terminate with unreachable until CFG is rewired.
803 // Note: this asserts the generated code's assumption that
804 // getFirstInsertionPt() can be dereferenced into an Instruction.
805 VectorHeaderBB->getTerminator()->eraseFromParent();
806 State->Builder.SetInsertPoint(VectorHeaderBB);
807 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
808 State->Builder.SetInsertPoint(Terminator);
809
810 // 2. Generate code in loop body.
811 State->CFG.PrevVPBB = nullptr;
812 State->CFG.PrevBB = VectorHeaderBB;
813 State->CFG.LastBB = VectorLatchBB;
814
815 for (VPBlockBase *Block : depth_first(Entry))
816 Block->execute(State);
817
818 // Setup branch terminator successors for VPBBs in VPBBsToFix based on
819 // VPBB's successors.
820 for (auto VPBB : State->CFG.VPBBsToFix) {
821 assert(EnableVPlanNativePath &&
822 "Unexpected VPBBsToFix in non VPlan-native path");
823 BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
824 assert(BB && "Unexpected null basic block for VPBB");
825
826 unsigned Idx = 0;
827 auto *BBTerminator = BB->getTerminator();
828
829 for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
830 VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
831 BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
832 ++Idx;
833 }
834 }
835
836 // 3. Merge the temporary latch created with the last basic-block filled.
837 BasicBlock *LastBB = State->CFG.PrevBB;
838 // Connect LastBB to VectorLatchBB to facilitate their merge.
839 assert((EnableVPlanNativePath ||
840 isa<UnreachableInst>(LastBB->getTerminator())) &&
841 "Expected InnerLoop VPlan CFG to terminate with unreachable");
842 assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
843 "Expected VPlan CFG to terminate with branch in NativePath");
844 LastBB->getTerminator()->eraseFromParent();
845 BranchInst::Create(VectorLatchBB, LastBB);
846
847 // Merge LastBB with Latch.
848 bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
849 (void)Merged;
850 assert(Merged && "Could not merge last basic block with latch.");
851 VectorLatchBB = LastBB;
852
853 // We do not attempt to preserve DT for outer loop vectorization currently.
854 if (!EnableVPlanNativePath)
855 updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB,
856 L->getExitBlock());
857 }
858
859 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
860 LLVM_DUMP_METHOD
print(raw_ostream & O) const861 void VPlan::print(raw_ostream &O) const {
862 VPSlotTracker SlotTracker(this);
863
864 O << "VPlan '" << Name << "' {";
865 for (const VPBlockBase *Block : depth_first(getEntry())) {
866 O << '\n';
867 Block->print(O, "", SlotTracker);
868 }
869 O << "}\n";
870 }
871
872 LLVM_DUMP_METHOD
printDOT(raw_ostream & O) const873 void VPlan::printDOT(raw_ostream &O) const {
874 VPlanPrinter Printer(O, *this);
875 Printer.dump();
876 }
877
878 LLVM_DUMP_METHOD
dump() const879 void VPlan::dump() const { print(dbgs()); }
880 #endif
881
updateDominatorTree(DominatorTree * DT,BasicBlock * LoopPreHeaderBB,BasicBlock * LoopLatchBB,BasicBlock * LoopExitBB)882 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
883 BasicBlock *LoopLatchBB,
884 BasicBlock *LoopExitBB) {
885 BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
886 assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
887 // The vector body may be more than a single basic-block by this point.
888 // Update the dominator tree information inside the vector body by propagating
889 // it from header to latch, expecting only triangular control-flow, if any.
890 BasicBlock *PostDomSucc = nullptr;
891 for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
892 // Get the list of successors of this block.
893 std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
894 assert(Succs.size() <= 2 &&
895 "Basic block in vector loop has more than 2 successors.");
896 PostDomSucc = Succs[0];
897 if (Succs.size() == 1) {
898 assert(PostDomSucc->getSinglePredecessor() &&
899 "PostDom successor has more than one predecessor.");
900 DT->addNewBlock(PostDomSucc, BB);
901 continue;
902 }
903 BasicBlock *InterimSucc = Succs[1];
904 if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
905 PostDomSucc = Succs[1];
906 InterimSucc = Succs[0];
907 }
908 assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
909 "One successor of a basic block does not lead to the other.");
910 assert(InterimSucc->getSinglePredecessor() &&
911 "Interim successor has more than one predecessor.");
912 assert(PostDomSucc->hasNPredecessors(2) &&
913 "PostDom successor has more than two predecessors.");
914 DT->addNewBlock(InterimSucc, BB);
915 DT->addNewBlock(PostDomSucc, BB);
916 }
917 // Latch block is a new dominator for the loop exit.
918 DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
919 assert(DT->verify(DominatorTree::VerificationLevel::Fast));
920 }
921
922 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
getUID(const VPBlockBase * Block)923 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
924 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
925 Twine(getOrCreateBID(Block));
926 }
927
getOrCreateName(const VPBlockBase * Block)928 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
929 const std::string &Name = Block->getName();
930 if (!Name.empty())
931 return Name;
932 return "VPB" + Twine(getOrCreateBID(Block));
933 }
934
dump()935 void VPlanPrinter::dump() {
936 Depth = 1;
937 bumpIndent(0);
938 OS << "digraph VPlan {\n";
939 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
940 if (!Plan.getName().empty())
941 OS << "\\n" << DOT::EscapeString(Plan.getName());
942 if (Plan.BackedgeTakenCount) {
943 OS << ", where:\\n";
944 Plan.BackedgeTakenCount->print(OS, SlotTracker);
945 OS << " := BackedgeTakenCount";
946 }
947 OS << "\"]\n";
948 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
949 OS << "edge [fontname=Courier, fontsize=30]\n";
950 OS << "compound=true\n";
951
952 for (const VPBlockBase *Block : depth_first(Plan.getEntry()))
953 dumpBlock(Block);
954
955 OS << "}\n";
956 }
957
dumpBlock(const VPBlockBase * Block)958 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
959 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
960 dumpBasicBlock(BasicBlock);
961 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
962 dumpRegion(Region);
963 else
964 llvm_unreachable("Unsupported kind of VPBlock.");
965 }
966
drawEdge(const VPBlockBase * From,const VPBlockBase * To,bool Hidden,const Twine & Label)967 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
968 bool Hidden, const Twine &Label) {
969 // Due to "dot" we print an edge between two regions as an edge between the
970 // exit basic block and the entry basic of the respective regions.
971 const VPBlockBase *Tail = From->getExitBasicBlock();
972 const VPBlockBase *Head = To->getEntryBasicBlock();
973 OS << Indent << getUID(Tail) << " -> " << getUID(Head);
974 OS << " [ label=\"" << Label << '\"';
975 if (Tail != From)
976 OS << " ltail=" << getUID(From);
977 if (Head != To)
978 OS << " lhead=" << getUID(To);
979 if (Hidden)
980 OS << "; splines=none";
981 OS << "]\n";
982 }
983
dumpEdges(const VPBlockBase * Block)984 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
985 auto &Successors = Block->getSuccessors();
986 if (Successors.size() == 1)
987 drawEdge(Block, Successors.front(), false, "");
988 else if (Successors.size() == 2) {
989 drawEdge(Block, Successors.front(), false, "T");
990 drawEdge(Block, Successors.back(), false, "F");
991 } else {
992 unsigned SuccessorNumber = 0;
993 for (auto *Successor : Successors)
994 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
995 }
996 }
997
dumpBasicBlock(const VPBasicBlock * BasicBlock)998 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
999 // Implement dot-formatted dump by performing plain-text dump into the
1000 // temporary storage followed by some post-processing.
1001 OS << Indent << getUID(BasicBlock) << " [label =\n";
1002 bumpIndent(1);
1003 std::string Str;
1004 raw_string_ostream SS(Str);
1005 // Use no indentation as we need to wrap the lines into quotes ourselves.
1006 BasicBlock->print(SS, "", SlotTracker);
1007
1008 // We need to process each line of the output separately, so split
1009 // single-string plain-text dump.
1010 SmallVector<StringRef, 0> Lines;
1011 StringRef(Str).rtrim('\n').split(Lines, "\n");
1012
1013 auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1014 OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1015 };
1016
1017 // Don't need the "+" after the last line.
1018 for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1019 EmitLine(Line, " +\n");
1020 EmitLine(Lines.back(), "\n");
1021
1022 bumpIndent(-1);
1023 OS << Indent << "]\n";
1024
1025 dumpEdges(BasicBlock);
1026 }
1027
dumpRegion(const VPRegionBlock * Region)1028 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1029 OS << Indent << "subgraph " << getUID(Region) << " {\n";
1030 bumpIndent(1);
1031 OS << Indent << "fontname=Courier\n"
1032 << Indent << "label=\""
1033 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1034 << DOT::EscapeString(Region->getName()) << "\"\n";
1035 // Dump the blocks of the region.
1036 assert(Region->getEntry() && "Region contains no inner blocks.");
1037 for (const VPBlockBase *Block : depth_first(Region->getEntry()))
1038 dumpBlock(Block);
1039 bumpIndent(-1);
1040 OS << Indent << "}\n";
1041 dumpEdges(Region);
1042 }
1043
print(raw_ostream & O) const1044 void VPlanIngredient::print(raw_ostream &O) const {
1045 if (auto *Inst = dyn_cast<Instruction>(V)) {
1046 if (!Inst->getType()->isVoidTy()) {
1047 Inst->printAsOperand(O, false);
1048 O << " = ";
1049 }
1050 O << Inst->getOpcodeName() << " ";
1051 unsigned E = Inst->getNumOperands();
1052 if (E > 0) {
1053 Inst->getOperand(0)->printAsOperand(O, false);
1054 for (unsigned I = 1; I < E; ++I)
1055 Inst->getOperand(I)->printAsOperand(O << ", ", false);
1056 }
1057 } else // !Inst
1058 V->printAsOperand(O, false);
1059 }
1060
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1061 void VPWidenCallRecipe::print(raw_ostream &O, const Twine &Indent,
1062 VPSlotTracker &SlotTracker) const {
1063 O << Indent << "WIDEN-CALL ";
1064
1065 auto *CI = cast<CallInst>(getUnderlyingInstr());
1066 if (CI->getType()->isVoidTy())
1067 O << "void ";
1068 else {
1069 printAsOperand(O, SlotTracker);
1070 O << " = ";
1071 }
1072
1073 O << "call @" << CI->getCalledFunction()->getName() << "(";
1074 printOperands(O, SlotTracker);
1075 O << ")";
1076 }
1077
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1078 void VPWidenSelectRecipe::print(raw_ostream &O, const Twine &Indent,
1079 VPSlotTracker &SlotTracker) const {
1080 O << Indent << "WIDEN-SELECT ";
1081 printAsOperand(O, SlotTracker);
1082 O << " = select ";
1083 getOperand(0)->printAsOperand(O, SlotTracker);
1084 O << ", ";
1085 getOperand(1)->printAsOperand(O, SlotTracker);
1086 O << ", ";
1087 getOperand(2)->printAsOperand(O, SlotTracker);
1088 O << (InvariantCond ? " (condition is loop invariant)" : "");
1089 }
1090
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1091 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent,
1092 VPSlotTracker &SlotTracker) const {
1093 O << Indent << "WIDEN ";
1094 printAsOperand(O, SlotTracker);
1095 O << " = " << getUnderlyingInstr()->getOpcodeName() << " ";
1096 printOperands(O, SlotTracker);
1097 }
1098
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1099 void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, const Twine &Indent,
1100 VPSlotTracker &SlotTracker) const {
1101 O << Indent << "WIDEN-INDUCTION";
1102 if (getTruncInst()) {
1103 O << "\\l\"";
1104 O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
1105 O << " +\n" << Indent << "\" ";
1106 getVPValue(0)->printAsOperand(O, SlotTracker);
1107 } else
1108 O << " " << VPlanIngredient(IV);
1109 }
1110
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1111 void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent,
1112 VPSlotTracker &SlotTracker) const {
1113 O << Indent << "WIDEN-GEP ";
1114 O << (IsPtrLoopInvariant ? "Inv" : "Var");
1115 size_t IndicesNumber = IsIndexLoopInvariant.size();
1116 for (size_t I = 0; I < IndicesNumber; ++I)
1117 O << "[" << (IsIndexLoopInvariant[I] ? "Inv" : "Var") << "]";
1118
1119 O << " ";
1120 printAsOperand(O, SlotTracker);
1121 O << " = getelementptr ";
1122 printOperands(O, SlotTracker);
1123 }
1124
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1125 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent,
1126 VPSlotTracker &SlotTracker) const {
1127 O << Indent << "WIDEN-PHI ";
1128
1129 auto *OriginalPhi = cast<PHINode>(getUnderlyingValue());
1130 // Unless all incoming values are modeled in VPlan print the original PHI
1131 // directly.
1132 // TODO: Remove once all VPWidenPHIRecipe instances keep all relevant incoming
1133 // values as VPValues.
1134 if (getNumOperands() != OriginalPhi->getNumOperands()) {
1135 O << VPlanIngredient(OriginalPhi);
1136 return;
1137 }
1138
1139 printAsOperand(O, SlotTracker);
1140 O << " = phi ";
1141 printOperands(O, SlotTracker);
1142 }
1143
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1144 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent,
1145 VPSlotTracker &SlotTracker) const {
1146 O << Indent << "BLEND ";
1147 Phi->printAsOperand(O, false);
1148 O << " =";
1149 if (getNumIncomingValues() == 1) {
1150 // Not a User of any mask: not really blending, this is a
1151 // single-predecessor phi.
1152 O << " ";
1153 getIncomingValue(0)->printAsOperand(O, SlotTracker);
1154 } else {
1155 for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
1156 O << " ";
1157 getIncomingValue(I)->printAsOperand(O, SlotTracker);
1158 O << "/";
1159 getMask(I)->printAsOperand(O, SlotTracker);
1160 }
1161 }
1162 }
1163
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1164 void VPReductionRecipe::print(raw_ostream &O, const Twine &Indent,
1165 VPSlotTracker &SlotTracker) const {
1166 O << Indent << "REDUCE ";
1167 printAsOperand(O, SlotTracker);
1168 O << " = ";
1169 getChainOp()->printAsOperand(O, SlotTracker);
1170 O << " + reduce." << Instruction::getOpcodeName(RdxDesc->getOpcode())
1171 << " (";
1172 getVecOp()->printAsOperand(O, SlotTracker);
1173 if (getCondOp()) {
1174 O << ", ";
1175 getCondOp()->printAsOperand(O, SlotTracker);
1176 }
1177 O << ")";
1178 }
1179
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1180 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent,
1181 VPSlotTracker &SlotTracker) const {
1182 O << Indent << (IsUniform ? "CLONE " : "REPLICATE ");
1183
1184 if (!getUnderlyingInstr()->getType()->isVoidTy()) {
1185 printAsOperand(O, SlotTracker);
1186 O << " = ";
1187 }
1188 O << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode()) << " ";
1189 printOperands(O, SlotTracker);
1190
1191 if (AlsoPack)
1192 O << " (S->V)";
1193 }
1194
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1195 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent,
1196 VPSlotTracker &SlotTracker) const {
1197 O << Indent << "PHI-PREDICATED-INSTRUCTION ";
1198 printAsOperand(O, SlotTracker);
1199 O << " = ";
1200 printOperands(O, SlotTracker);
1201 }
1202
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1203 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent,
1204 VPSlotTracker &SlotTracker) const {
1205 O << Indent << "WIDEN ";
1206
1207 if (!isStore()) {
1208 getVPSingleValue()->printAsOperand(O, SlotTracker);
1209 O << " = ";
1210 }
1211 O << Instruction::getOpcodeName(Ingredient.getOpcode()) << " ";
1212
1213 printOperands(O, SlotTracker);
1214 }
1215 #endif
1216
execute(VPTransformState & State)1217 void VPWidenCanonicalIVRecipe::execute(VPTransformState &State) {
1218 Value *CanonicalIV = State.CanonicalIV;
1219 Type *STy = CanonicalIV->getType();
1220 IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
1221 ElementCount VF = State.VF;
1222 assert(!VF.isScalable() && "the code following assumes non scalables ECs");
1223 Value *VStart = VF.isScalar()
1224 ? CanonicalIV
1225 : Builder.CreateVectorSplat(VF.getKnownMinValue(),
1226 CanonicalIV, "broadcast");
1227 for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
1228 SmallVector<Constant *, 8> Indices;
1229 for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
1230 Indices.push_back(
1231 ConstantInt::get(STy, Part * VF.getKnownMinValue() + Lane));
1232 // If VF == 1, there is only one iteration in the loop above, thus the
1233 // element pushed back into Indices is ConstantInt::get(STy, Part)
1234 Constant *VStep =
1235 VF.isScalar() ? Indices.back() : ConstantVector::get(Indices);
1236 // Add the consecutive indices to the vector value.
1237 Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
1238 State.set(getVPSingleValue(), CanonicalVectorIV, Part);
1239 }
1240 }
1241
1242 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1243 void VPWidenCanonicalIVRecipe::print(raw_ostream &O, const Twine &Indent,
1244 VPSlotTracker &SlotTracker) const {
1245 O << Indent << "EMIT ";
1246 getVPSingleValue()->printAsOperand(O, SlotTracker);
1247 O << " = WIDEN-CANONICAL-INDUCTION";
1248 }
1249 #endif
1250
execute(VPTransformState & State)1251 void VPFirstOrderRecurrencePHIRecipe::execute(VPTransformState &State) {
1252 auto &Builder = State.Builder;
1253 // Create a vector from the initial value.
1254 auto *VectorInit = getStartValue()->getLiveInIRValue();
1255
1256 Type *VecTy = State.VF.isScalar()
1257 ? VectorInit->getType()
1258 : VectorType::get(VectorInit->getType(), State.VF);
1259
1260 if (State.VF.isVector()) {
1261 auto *IdxTy = Builder.getInt32Ty();
1262 auto *One = ConstantInt::get(IdxTy, 1);
1263 IRBuilder<>::InsertPointGuard Guard(Builder);
1264 Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1265 auto *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);
1266 auto *LastIdx = Builder.CreateSub(RuntimeVF, One);
1267 VectorInit = Builder.CreateInsertElement(
1268 PoisonValue::get(VecTy), VectorInit, LastIdx, "vector.recur.init");
1269 }
1270
1271 // Create a phi node for the new recurrence.
1272 PHINode *EntryPart = PHINode::Create(
1273 VecTy, 2, "vector.recur", &*State.CFG.PrevBB->getFirstInsertionPt());
1274 EntryPart->addIncoming(VectorInit, State.CFG.VectorPreHeader);
1275 State.set(this, EntryPart, 0);
1276 }
1277
1278 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1279 void VPFirstOrderRecurrencePHIRecipe::print(raw_ostream &O, const Twine &Indent,
1280 VPSlotTracker &SlotTracker) const {
1281 O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
1282 printAsOperand(O, SlotTracker);
1283 O << " = phi ";
1284 printOperands(O, SlotTracker);
1285 }
1286 #endif
1287
execute(VPTransformState & State)1288 void VPReductionPHIRecipe::execute(VPTransformState &State) {
1289 PHINode *PN = cast<PHINode>(getUnderlyingValue());
1290 auto &Builder = State.Builder;
1291
1292 // In order to support recurrences we need to be able to vectorize Phi nodes.
1293 // Phi nodes have cycles, so we need to vectorize them in two stages. This is
1294 // stage #1: We create a new vector PHI node with no incoming edges. We'll use
1295 // this value when we vectorize all of the instructions that use the PHI.
1296 bool ScalarPHI = State.VF.isScalar() || IsInLoop;
1297 Type *VecTy =
1298 ScalarPHI ? PN->getType() : VectorType::get(PN->getType(), State.VF);
1299
1300 BasicBlock *HeaderBB = State.CFG.PrevBB;
1301 assert(State.LI->getLoopFor(HeaderBB)->getHeader() == HeaderBB &&
1302 "recipe must be in the vector loop header");
1303 unsigned LastPartForNewPhi = isOrdered() ? 1 : State.UF;
1304 for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1305 Value *EntryPart =
1306 PHINode::Create(VecTy, 2, "vec.phi", &*HeaderBB->getFirstInsertionPt());
1307 State.set(this, EntryPart, Part);
1308 }
1309 VPValue *StartVPV = getStartValue();
1310 Value *StartV = StartVPV->getLiveInIRValue();
1311
1312 Value *Iden = nullptr;
1313 RecurKind RK = RdxDesc.getRecurrenceKind();
1314 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK)) {
1315 // MinMax reduction have the start value as their identify.
1316 if (ScalarPHI) {
1317 Iden = StartV;
1318 } else {
1319 IRBuilderBase::InsertPointGuard IPBuilder(Builder);
1320 Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1321 StartV = Iden =
1322 Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
1323 }
1324 } else {
1325 Constant *IdenC = RecurrenceDescriptor::getRecurrenceIdentity(
1326 RK, VecTy->getScalarType(), RdxDesc.getFastMathFlags());
1327 Iden = IdenC;
1328
1329 if (!ScalarPHI) {
1330 Iden = ConstantVector::getSplat(State.VF, IdenC);
1331 IRBuilderBase::InsertPointGuard IPBuilder(Builder);
1332 Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1333 Constant *Zero = Builder.getInt32(0);
1334 StartV = Builder.CreateInsertElement(Iden, StartV, Zero);
1335 }
1336 }
1337
1338 for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1339 Value *EntryPart = State.get(this, Part);
1340 // Make sure to add the reduction start value only to the
1341 // first unroll part.
1342 Value *StartVal = (Part == 0) ? StartV : Iden;
1343 cast<PHINode>(EntryPart)->addIncoming(StartVal, State.CFG.VectorPreHeader);
1344 }
1345 }
1346
1347 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker) const1348 void VPReductionPHIRecipe::print(raw_ostream &O, const Twine &Indent,
1349 VPSlotTracker &SlotTracker) const {
1350 O << Indent << "WIDEN-REDUCTION-PHI ";
1351
1352 printAsOperand(O, SlotTracker);
1353 O << " = phi ";
1354 printOperands(O, SlotTracker);
1355 }
1356 #endif
1357
1358 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1359
replaceAllUsesWith(VPValue * New)1360 void VPValue::replaceAllUsesWith(VPValue *New) {
1361 for (unsigned J = 0; J < getNumUsers();) {
1362 VPUser *User = Users[J];
1363 unsigned NumUsers = getNumUsers();
1364 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
1365 if (User->getOperand(I) == this)
1366 User->setOperand(I, New);
1367 // If a user got removed after updating the current user, the next user to
1368 // update will be moved to the current position, so we only need to
1369 // increment the index if the number of users did not change.
1370 if (NumUsers == getNumUsers())
1371 J++;
1372 }
1373 }
1374
1375 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
printAsOperand(raw_ostream & OS,VPSlotTracker & Tracker) const1376 void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const {
1377 if (const Value *UV = getUnderlyingValue()) {
1378 OS << "ir<";
1379 UV->printAsOperand(OS, false);
1380 OS << ">";
1381 return;
1382 }
1383
1384 unsigned Slot = Tracker.getSlot(this);
1385 if (Slot == unsigned(-1))
1386 OS << "<badref>";
1387 else
1388 OS << "vp<%" << Tracker.getSlot(this) << ">";
1389 }
1390
printOperands(raw_ostream & O,VPSlotTracker & SlotTracker) const1391 void VPUser::printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const {
1392 interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
1393 Op->printAsOperand(O, SlotTracker);
1394 });
1395 }
1396 #endif
1397
visitRegion(VPRegionBlock * Region,Old2NewTy & Old2New,InterleavedAccessInfo & IAI)1398 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1399 Old2NewTy &Old2New,
1400 InterleavedAccessInfo &IAI) {
1401 ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
1402 for (VPBlockBase *Base : RPOT) {
1403 visitBlock(Base, Old2New, IAI);
1404 }
1405 }
1406
visitBlock(VPBlockBase * Block,Old2NewTy & Old2New,InterleavedAccessInfo & IAI)1407 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1408 InterleavedAccessInfo &IAI) {
1409 if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1410 for (VPRecipeBase &VPI : *VPBB) {
1411 if (isa<VPWidenPHIRecipe>(&VPI))
1412 continue;
1413 assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1414 auto *VPInst = cast<VPInstruction>(&VPI);
1415 auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
1416 auto *IG = IAI.getInterleaveGroup(Inst);
1417 if (!IG)
1418 continue;
1419
1420 auto NewIGIter = Old2New.find(IG);
1421 if (NewIGIter == Old2New.end())
1422 Old2New[IG] = new InterleaveGroup<VPInstruction>(
1423 IG->getFactor(), IG->isReverse(), IG->getAlign());
1424
1425 if (Inst == IG->getInsertPos())
1426 Old2New[IG]->setInsertPos(VPInst);
1427
1428 InterleaveGroupMap[VPInst] = Old2New[IG];
1429 InterleaveGroupMap[VPInst]->insertMember(
1430 VPInst, IG->getIndex(Inst),
1431 Align(IG->isReverse() ? (-1) * int(IG->getFactor())
1432 : IG->getFactor()));
1433 }
1434 } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1435 visitRegion(Region, Old2New, IAI);
1436 else
1437 llvm_unreachable("Unsupported kind of VPBlock.");
1438 }
1439
VPInterleavedAccessInfo(VPlan & Plan,InterleavedAccessInfo & IAI)1440 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
1441 InterleavedAccessInfo &IAI) {
1442 Old2NewTy Old2New;
1443 visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
1444 }
1445
assignSlot(const VPValue * V)1446 void VPSlotTracker::assignSlot(const VPValue *V) {
1447 assert(Slots.find(V) == Slots.end() && "VPValue already has a slot!");
1448 Slots[V] = NextSlot++;
1449 }
1450
assignSlots(const VPlan & Plan)1451 void VPSlotTracker::assignSlots(const VPlan &Plan) {
1452
1453 for (const VPValue *V : Plan.VPExternalDefs)
1454 assignSlot(V);
1455
1456 if (Plan.BackedgeTakenCount)
1457 assignSlot(Plan.BackedgeTakenCount);
1458
1459 ReversePostOrderTraversal<
1460 VPBlockRecursiveTraversalWrapper<const VPBlockBase *>>
1461 RPOT(VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(
1462 Plan.getEntry()));
1463 for (const VPBasicBlock *VPBB :
1464 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1465 for (const VPRecipeBase &Recipe : *VPBB)
1466 for (VPValue *Def : Recipe.definedValues())
1467 assignSlot(Def);
1468 }
1469