LLVM 19.0.0git
VPlanTransforms.cpp
Go to the documentation of this file.
1//===-- VPlanTransforms.cpp - Utility VPlan to VPlan transforms -----------===//
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 file implements a set of utility VPlan to VPlan transformations.
11///
12//===----------------------------------------------------------------------===//
13
14#include "VPlanTransforms.h"
15#include "VPRecipeBuilder.h"
16#include "VPlanAnalysis.h"
17#include "VPlanCFG.h"
18#include "VPlanDominatorTree.h"
19#include "VPlanPatternMatch.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SetVector.h"
25#include "llvm/IR/Intrinsics.h"
27
28using namespace llvm;
29
31 VPlanPtr &Plan,
33 GetIntOrFpInductionDescriptor,
34 ScalarEvolution &SE, const TargetLibraryInfo &TLI) {
35
37 Plan->getEntry());
38 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
39 VPRecipeBase *Term = VPBB->getTerminator();
40 auto EndIter = Term ? Term->getIterator() : VPBB->end();
41 // Introduce each ingredient into VPlan.
42 for (VPRecipeBase &Ingredient :
43 make_early_inc_range(make_range(VPBB->begin(), EndIter))) {
44
45 VPValue *VPV = Ingredient.getVPSingleValue();
46 Instruction *Inst = cast<Instruction>(VPV->getUnderlyingValue());
47
48 VPRecipeBase *NewRecipe = nullptr;
49 if (auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
50 auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
51 const auto *II = GetIntOrFpInductionDescriptor(Phi);
52 if (!II)
53 continue;
54
55 VPValue *Start = Plan->getVPValueOrAddLiveIn(II->getStartValue());
56 VPValue *Step =
57 vputils::getOrCreateVPValueForSCEVExpr(*Plan, II->getStep(), SE);
58 NewRecipe = new VPWidenIntOrFpInductionRecipe(Phi, Start, Step, *II);
59 } else {
60 assert(isa<VPInstruction>(&Ingredient) &&
61 "only VPInstructions expected here");
62 assert(!isa<PHINode>(Inst) && "phis should be handled above");
63 // Create VPWidenMemoryInstructionRecipe for loads and stores.
64 if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
65 NewRecipe = new VPWidenMemoryInstructionRecipe(
66 *Load, Ingredient.getOperand(0), nullptr /*Mask*/,
67 false /*Consecutive*/, false /*Reverse*/);
68 } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
69 NewRecipe = new VPWidenMemoryInstructionRecipe(
70 *Store, Ingredient.getOperand(1), Ingredient.getOperand(0),
71 nullptr /*Mask*/, false /*Consecutive*/, false /*Reverse*/);
72 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
73 NewRecipe = new VPWidenGEPRecipe(GEP, Ingredient.operands());
74 } else if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
75 NewRecipe = new VPWidenCallRecipe(
76 *CI, drop_end(Ingredient.operands()),
77 getVectorIntrinsicIDForCall(CI, &TLI), CI->getDebugLoc());
78 } else if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
79 NewRecipe = new VPWidenSelectRecipe(*SI, Ingredient.operands());
80 } else if (auto *CI = dyn_cast<CastInst>(Inst)) {
81 NewRecipe = new VPWidenCastRecipe(
82 CI->getOpcode(), Ingredient.getOperand(0), CI->getType(), *CI);
83 } else {
84 NewRecipe = new VPWidenRecipe(*Inst, Ingredient.operands());
85 }
86 }
87
88 NewRecipe->insertBefore(&Ingredient);
89 if (NewRecipe->getNumDefinedValues() == 1)
90 VPV->replaceAllUsesWith(NewRecipe->getVPSingleValue());
91 else
92 assert(NewRecipe->getNumDefinedValues() == 0 &&
93 "Only recpies with zero or one defined values expected");
94 Ingredient.eraseFromParent();
95 }
96 }
97}
98
99static bool sinkScalarOperands(VPlan &Plan) {
100 auto Iter = vp_depth_first_deep(Plan.getEntry());
101 bool Changed = false;
102 // First, collect the operands of all recipes in replicate blocks as seeds for
103 // sinking.
105 for (VPRegionBlock *VPR : VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)) {
106 VPBasicBlock *EntryVPBB = VPR->getEntryBasicBlock();
107 if (!VPR->isReplicator() || EntryVPBB->getSuccessors().size() != 2)
108 continue;
109 VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(EntryVPBB->getSuccessors()[0]);
110 if (!VPBB || VPBB->getSingleSuccessor() != VPR->getExitingBasicBlock())
111 continue;
112 for (auto &Recipe : *VPBB) {
113 for (VPValue *Op : Recipe.operands())
114 if (auto *Def =
115 dyn_cast_or_null<VPSingleDefRecipe>(Op->getDefiningRecipe()))
116 WorkList.insert(std::make_pair(VPBB, Def));
117 }
118 }
119
120 bool ScalarVFOnly = Plan.hasScalarVFOnly();
121 // Try to sink each replicate or scalar IV steps recipe in the worklist.
122 for (unsigned I = 0; I != WorkList.size(); ++I) {
123 VPBasicBlock *SinkTo;
124 VPSingleDefRecipe *SinkCandidate;
125 std::tie(SinkTo, SinkCandidate) = WorkList[I];
126 if (SinkCandidate->getParent() == SinkTo ||
127 SinkCandidate->mayHaveSideEffects() ||
128 SinkCandidate->mayReadOrWriteMemory())
129 continue;
130 if (auto *RepR = dyn_cast<VPReplicateRecipe>(SinkCandidate)) {
131 if (!ScalarVFOnly && RepR->isUniform())
132 continue;
133 } else if (!isa<VPScalarIVStepsRecipe>(SinkCandidate))
134 continue;
135
136 bool NeedsDuplicating = false;
137 // All recipe users of the sink candidate must be in the same block SinkTo
138 // or all users outside of SinkTo must be uniform-after-vectorization (
139 // i.e., only first lane is used) . In the latter case, we need to duplicate
140 // SinkCandidate.
141 auto CanSinkWithUser = [SinkTo, &NeedsDuplicating,
142 SinkCandidate](VPUser *U) {
143 auto *UI = dyn_cast<VPRecipeBase>(U);
144 if (!UI)
145 return false;
146 if (UI->getParent() == SinkTo)
147 return true;
148 NeedsDuplicating = UI->onlyFirstLaneUsed(SinkCandidate);
149 // We only know how to duplicate VPRecipeRecipes for now.
150 return NeedsDuplicating && isa<VPReplicateRecipe>(SinkCandidate);
151 };
152 if (!all_of(SinkCandidate->users(), CanSinkWithUser))
153 continue;
154
155 if (NeedsDuplicating) {
156 if (ScalarVFOnly)
157 continue;
158 Instruction *I = SinkCandidate->getUnderlyingInstr();
159 auto *Clone = new VPReplicateRecipe(I, SinkCandidate->operands(), true);
160 // TODO: add ".cloned" suffix to name of Clone's VPValue.
161
162 Clone->insertBefore(SinkCandidate);
163 SinkCandidate->replaceUsesWithIf(Clone, [SinkTo](VPUser &U, unsigned) {
164 return cast<VPRecipeBase>(&U)->getParent() != SinkTo;
165 });
166 }
167 SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi());
168 for (VPValue *Op : SinkCandidate->operands())
169 if (auto *Def =
170 dyn_cast_or_null<VPSingleDefRecipe>(Op->getDefiningRecipe()))
171 WorkList.insert(std::make_pair(SinkTo, Def));
172 Changed = true;
173 }
174 return Changed;
175}
176
177/// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return
178/// the mask.
180 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
181 if (!EntryBB || EntryBB->size() != 1 ||
182 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
183 return nullptr;
184
185 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
186}
187
188/// If \p R is a triangle region, return the 'then' block of the triangle.
190 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
191 if (EntryBB->getNumSuccessors() != 2)
192 return nullptr;
193
194 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
195 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
196 if (!Succ0 || !Succ1)
197 return nullptr;
198
199 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
200 return nullptr;
201 if (Succ0->getSingleSuccessor() == Succ1)
202 return Succ0;
203 if (Succ1->getSingleSuccessor() == Succ0)
204 return Succ1;
205 return nullptr;
206}
207
208// Merge replicate regions in their successor region, if a replicate region
209// is connected to a successor replicate region with the same predicate by a
210// single, empty VPBasicBlock.
212 SetVector<VPRegionBlock *> DeletedRegions;
213
214 // Collect replicate regions followed by an empty block, followed by another
215 // replicate region with matching masks to process front. This is to avoid
216 // iterator invalidation issues while merging regions.
218 for (VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
219 vp_depth_first_deep(Plan.getEntry()))) {
220 if (!Region1->isReplicator())
221 continue;
222 auto *MiddleBasicBlock =
223 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
224 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
225 continue;
226
227 auto *Region2 =
228 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
229 if (!Region2 || !Region2->isReplicator())
230 continue;
231
232 VPValue *Mask1 = getPredicatedMask(Region1);
233 VPValue *Mask2 = getPredicatedMask(Region2);
234 if (!Mask1 || Mask1 != Mask2)
235 continue;
236
237 assert(Mask1 && Mask2 && "both region must have conditions");
238 WorkList.push_back(Region1);
239 }
240
241 // Move recipes from Region1 to its successor region, if both are triangles.
242 for (VPRegionBlock *Region1 : WorkList) {
243 if (DeletedRegions.contains(Region1))
244 continue;
245 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());
246 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
247
248 VPBasicBlock *Then1 = getPredicatedThenBlock(Region1);
249 VPBasicBlock *Then2 = getPredicatedThenBlock(Region2);
250 if (!Then1 || !Then2)
251 continue;
252
253 // Note: No fusion-preventing memory dependencies are expected in either
254 // region. Such dependencies should be rejected during earlier dependence
255 // checks, which guarantee accesses can be re-ordered for vectorization.
256 //
257 // Move recipes to the successor region.
258 for (VPRecipeBase &ToMove : make_early_inc_range(reverse(*Then1)))
259 ToMove.moveBefore(*Then2, Then2->getFirstNonPhi());
260
261 auto *Merge1 = cast<VPBasicBlock>(Then1->getSingleSuccessor());
262 auto *Merge2 = cast<VPBasicBlock>(Then2->getSingleSuccessor());
263
264 // Move VPPredInstPHIRecipes from the merge block to the successor region's
265 // merge block. Update all users inside the successor region to use the
266 // original values.
267 for (VPRecipeBase &Phi1ToMove : make_early_inc_range(reverse(*Merge1))) {
268 VPValue *PredInst1 =
269 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
270 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
271 Phi1ToMoveV->replaceUsesWithIf(PredInst1, [Then2](VPUser &U, unsigned) {
272 auto *UI = dyn_cast<VPRecipeBase>(&U);
273 return UI && UI->getParent() == Then2;
274 });
275
276 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
277 }
278
279 // Finally, remove the first region.
280 for (VPBlockBase *Pred : make_early_inc_range(Region1->getPredecessors())) {
281 VPBlockUtils::disconnectBlocks(Pred, Region1);
282 VPBlockUtils::connectBlocks(Pred, MiddleBasicBlock);
283 }
284 VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock);
285 DeletedRegions.insert(Region1);
286 }
287
288 for (VPRegionBlock *ToDelete : DeletedRegions)
289 delete ToDelete;
290 return !DeletedRegions.empty();
291}
292
294 VPlan &Plan) {
295 Instruction *Instr = PredRecipe->getUnderlyingInstr();
296 // Build the triangular if-then region.
297 std::string RegionName = (Twine("pred.") + Instr->getOpcodeName()).str();
298 assert(Instr->getParent() && "Predicated instruction not in any basic block");
299 auto *BlockInMask = PredRecipe->getMask();
300 auto *BOMRecipe = new VPBranchOnMaskRecipe(BlockInMask);
301 auto *Entry = new VPBasicBlock(Twine(RegionName) + ".entry", BOMRecipe);
302
303 // Replace predicated replicate recipe with a replicate recipe without a
304 // mask but in the replicate region.
305 auto *RecipeWithoutMask = new VPReplicateRecipe(
306 PredRecipe->getUnderlyingInstr(),
307 make_range(PredRecipe->op_begin(), std::prev(PredRecipe->op_end())),
308 PredRecipe->isUniform());
309 auto *Pred = new VPBasicBlock(Twine(RegionName) + ".if", RecipeWithoutMask);
310
311 VPPredInstPHIRecipe *PHIRecipe = nullptr;
312 if (PredRecipe->getNumUsers() != 0) {
313 PHIRecipe = new VPPredInstPHIRecipe(RecipeWithoutMask);
314 PredRecipe->replaceAllUsesWith(PHIRecipe);
315 PHIRecipe->setOperand(0, RecipeWithoutMask);
316 }
317 PredRecipe->eraseFromParent();
318 auto *Exiting = new VPBasicBlock(Twine(RegionName) + ".continue", PHIRecipe);
319 VPRegionBlock *Region = new VPRegionBlock(Entry, Exiting, RegionName, true);
320
321 // Note: first set Entry as region entry and then connect successors starting
322 // from it in order, to propagate the "parent" of each VPBasicBlock.
323 VPBlockUtils::insertTwoBlocksAfter(Pred, Exiting, Entry);
324 VPBlockUtils::connectBlocks(Pred, Exiting);
325
326 return Region;
327}
328
329static void addReplicateRegions(VPlan &Plan) {
331 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
332 vp_depth_first_deep(Plan.getEntry()))) {
333 for (VPRecipeBase &R : *VPBB)
334 if (auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
335 if (RepR->isPredicated())
336 WorkList.push_back(RepR);
337 }
338 }
339
340 unsigned BBNum = 0;
341 for (VPReplicateRecipe *RepR : WorkList) {
342 VPBasicBlock *CurrentBlock = RepR->getParent();
343 VPBasicBlock *SplitBlock = CurrentBlock->splitAt(RepR->getIterator());
344
345 BasicBlock *OrigBB = RepR->getUnderlyingInstr()->getParent();
347 OrigBB->hasName() ? OrigBB->getName() + "." + Twine(BBNum++) : "");
348 // Record predicated instructions for above packing optimizations.
350 Region->setParent(CurrentBlock->getParent());
352 VPBlockUtils::connectBlocks(CurrentBlock, Region);
354 }
355}
356
357/// Remove redundant VPBasicBlocks by merging them into their predecessor if
358/// the predecessor has a single successor.
361 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
362 vp_depth_first_deep(Plan.getEntry()))) {
363 auto *PredVPBB =
364 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
365 if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
366 WorkList.push_back(VPBB);
367 }
368
369 for (VPBasicBlock *VPBB : WorkList) {
370 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
371 for (VPRecipeBase &R : make_early_inc_range(*VPBB))
372 R.moveBefore(*PredVPBB, PredVPBB->end());
373 VPBlockUtils::disconnectBlocks(PredVPBB, VPBB);
374 auto *ParentRegion = cast_or_null<VPRegionBlock>(VPBB->getParent());
375 if (ParentRegion && ParentRegion->getExiting() == VPBB)
376 ParentRegion->setExiting(PredVPBB);
377 for (auto *Succ : to_vector(VPBB->successors())) {
379 VPBlockUtils::connectBlocks(PredVPBB, Succ);
380 }
381 delete VPBB;
382 }
383 return !WorkList.empty();
384}
385
387 // Convert masked VPReplicateRecipes to if-then region blocks.
389
390 bool ShouldSimplify = true;
391 while (ShouldSimplify) {
392 ShouldSimplify = sinkScalarOperands(Plan);
393 ShouldSimplify |= mergeReplicateRegionsIntoSuccessors(Plan);
394 ShouldSimplify |= mergeBlocksIntoPredecessors(Plan);
395 }
396}
397
398/// Remove redundant casts of inductions.
399///
400/// Such redundant casts are casts of induction variables that can be ignored,
401/// because we already proved that the casted phi is equal to the uncasted phi
402/// in the vectorized loop. There is no need to vectorize the cast - the same
403/// value can be used for both the phi and casts in the vector loop.
405 for (auto &Phi : Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
406 auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
407 if (!IV || IV->getTruncInst())
408 continue;
409
410 // A sequence of IR Casts has potentially been recorded for IV, which
411 // *must be bypassed* when the IV is vectorized, because the vectorized IV
412 // will produce the desired casted value. This sequence forms a def-use
413 // chain and is provided in reverse order, ending with the cast that uses
414 // the IV phi. Search for the recipe of the last cast in the chain and
415 // replace it with the original IV. Note that only the final cast is
416 // expected to have users outside the cast-chain and the dead casts left
417 // over will be cleaned up later.
418 auto &Casts = IV->getInductionDescriptor().getCastInsts();
419 VPValue *FindMyCast = IV;
420 for (Instruction *IRCast : reverse(Casts)) {
421 VPSingleDefRecipe *FoundUserCast = nullptr;
422 for (auto *U : FindMyCast->users()) {
423 auto *UserCast = dyn_cast<VPSingleDefRecipe>(U);
424 if (UserCast && UserCast->getUnderlyingValue() == IRCast) {
425 FoundUserCast = UserCast;
426 break;
427 }
428 }
429 FindMyCast = FoundUserCast;
430 }
431 FindMyCast->replaceAllUsesWith(IV);
432 }
433}
434
435/// Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV
436/// recipe, if it exists.
438 VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
439 VPWidenCanonicalIVRecipe *WidenNewIV = nullptr;
440 for (VPUser *U : CanonicalIV->users()) {
441 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
442 if (WidenNewIV)
443 break;
444 }
445
446 if (!WidenNewIV)
447 return;
448
450 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
451 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
452
453 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() ||
454 WidenOriginalIV->getScalarType() != WidenNewIV->getScalarType())
455 continue;
456
457 // Replace WidenNewIV with WidenOriginalIV if WidenOriginalIV provides
458 // everything WidenNewIV's users need. That is, WidenOriginalIV will
459 // generate a vector phi or all users of WidenNewIV demand the first lane
460 // only.
461 if (any_of(WidenOriginalIV->users(),
462 [WidenOriginalIV](VPUser *U) {
463 return !U->usesScalars(WidenOriginalIV);
464 }) ||
465 vputils::onlyFirstLaneUsed(WidenNewIV)) {
466 WidenNewIV->replaceAllUsesWith(WidenOriginalIV);
467 WidenNewIV->eraseFromParent();
468 return;
469 }
470 }
471}
472
473static void removeDeadRecipes(VPlan &Plan) {
475 Plan.getEntry());
476
477 for (VPBasicBlock *VPBB : reverse(VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT))) {
478 // The recipes in the block are processed in reverse order, to catch chains
479 // of dead recipes.
480 for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) {
481 // A user keeps R alive:
482 if (any_of(R.definedValues(),
483 [](VPValue *V) { return V->getNumUsers(); }))
484 continue;
485
486 using namespace llvm::PatternMatch;
487 // Having side effects keeps R alive, but do remove conditional assume
488 // instructions as their conditions may be flattened.
489 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);
490 bool IsConditionalAssume =
491 RepR && RepR->isPredicated() &&
492 match(RepR->getUnderlyingInstr(), m_Intrinsic<Intrinsic::assume>());
493 if (R.mayHaveSideEffects() && !IsConditionalAssume)
494 continue;
495
496 R.eraseFromParent();
497 }
498 }
499}
500
503 Instruction::BinaryOps InductionOpcode,
504 FPMathOperator *FPBinOp,
505 ScalarEvolution &SE, Instruction *TruncI,
506 VPValue *StartV, VPValue *Step,
509 VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
510 VPSingleDefRecipe *BaseIV = CanonicalIV;
511 if (!CanonicalIV->isCanonical(Kind, StartV, Step)) {
512 BaseIV = new VPDerivedIVRecipe(Kind, FPBinOp, StartV, CanonicalIV, Step);
513 HeaderVPBB->insert(BaseIV, IP);
514 }
515
516 // Truncate base induction if needed.
518 SE.getContext());
519 Type *ResultTy = TypeInfo.inferScalarType(BaseIV);
520 if (TruncI) {
521 Type *TruncTy = TruncI->getType();
522 assert(ResultTy->getScalarSizeInBits() > TruncTy->getScalarSizeInBits() &&
523 "Not truncating.");
524 assert(ResultTy->isIntegerTy() && "Truncation requires an integer type");
525 BaseIV = new VPScalarCastRecipe(Instruction::Trunc, BaseIV, TruncTy);
526 HeaderVPBB->insert(BaseIV, IP);
527 ResultTy = TruncTy;
528 }
529
530 // Truncate step if needed.
531 Type *StepTy = TypeInfo.inferScalarType(Step);
532 if (ResultTy != StepTy) {
533 assert(StepTy->getScalarSizeInBits() > ResultTy->getScalarSizeInBits() &&
534 "Not truncating.");
535 assert(StepTy->isIntegerTy() && "Truncation requires an integer type");
536 Step = new VPScalarCastRecipe(Instruction::Trunc, Step, ResultTy);
537 auto *VecPreheader =
538 cast<VPBasicBlock>(HeaderVPBB->getSingleHierarchicalPredecessor());
539 VecPreheader->appendRecipe(Step->getDefiningRecipe());
540 }
541
543 BaseIV, Step, InductionOpcode,
544 FPBinOp ? FPBinOp->getFastMathFlags() : FastMathFlags());
545 HeaderVPBB->insert(Steps, IP);
546 return Steps;
547}
548
549/// Legalize VPWidenPointerInductionRecipe, by replacing it with a PtrAdd
550/// (IndStart, ScalarIVSteps (0, Step)) if only its scalar values are used, as
551/// VPWidenPointerInductionRecipe will generate vectors only. If some users
552/// require vectors while other require scalars, the scalar uses need to extract
553/// the scalars from the generated vectors (Note that this is different to how
554/// int/fp inductions are handled). Also optimize VPWidenIntOrFpInductionRecipe,
555/// if any of its users needs scalar values, by providing them scalar steps
556/// built on the canonical scalar IV and update the original IV's users. This is
557/// an optional optimization to reduce the needs of vector extracts.
561 bool HasOnlyVectorVFs = !Plan.hasVF(ElementCount::getFixed(1));
562 VPBasicBlock::iterator InsertPt = HeaderVPBB->getFirstNonPhi();
563 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
564 // Replace wide pointer inductions which have only their scalars used by
565 // PtrAdd(IndStart, ScalarIVSteps (0, Step)).
566 if (auto *PtrIV = dyn_cast<VPWidenPointerInductionRecipe>(&Phi)) {
567 if (!PtrIV->onlyScalarsGenerated(Plan.hasScalableVF()))
568 continue;
569
570 const InductionDescriptor &ID = PtrIV->getInductionDescriptor();
571 VPValue *StartV = Plan.getVPValueOrAddLiveIn(
572 ConstantInt::get(ID.getStep()->getType(), 0));
573 VPValue *StepV = PtrIV->getOperand(1);
574 VPRecipeBase *Steps =
576 Instruction::Add, nullptr, SE, nullptr, StartV,
577 StepV, InsertPt)
579
580 auto *Recipe =
582 {PtrIV->getStartValue(), Steps->getVPSingleValue()},
583 PtrIV->getDebugLoc(), "next.gep");
584
585 Recipe->insertAfter(Steps);
586 PtrIV->replaceAllUsesWith(Recipe);
587 continue;
588 }
589
590 // Replace widened induction with scalar steps for users that only use
591 // scalars.
592 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
593 if (!WideIV)
594 continue;
595 if (HasOnlyVectorVFs && none_of(WideIV->users(), [WideIV](VPUser *U) {
596 return U->usesScalars(WideIV);
597 }))
598 continue;
599
600 const InductionDescriptor &ID = WideIV->getInductionDescriptor();
602 Plan, ID.getKind(), ID.getInductionOpcode(),
603 dyn_cast_or_null<FPMathOperator>(ID.getInductionBinOp()), SE,
604 WideIV->getTruncInst(), WideIV->getStartValue(), WideIV->getStepValue(),
605 InsertPt);
606
607 // Update scalar users of IV to use Step instead.
608 if (!HasOnlyVectorVFs)
609 WideIV->replaceAllUsesWith(Steps);
610 else
611 WideIV->replaceUsesWithIf(Steps, [WideIV](VPUser &U, unsigned) {
612 return U.usesScalars(WideIV);
613 });
614 }
615}
616
617/// Remove redundant EpxandSCEVRecipes in \p Plan's entry block by replacing
618/// them with already existing recipes expanding the same SCEV expression.
621
622 for (VPRecipeBase &R :
624 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
625 if (!ExpR)
626 continue;
627
628 auto I = SCEV2VPV.insert({ExpR->getSCEV(), ExpR});
629 if (I.second)
630 continue;
631 ExpR->replaceAllUsesWith(I.first->second);
632 ExpR->eraseFromParent();
633 }
634}
635
637 unsigned BestUF,
639 assert(Plan.hasVF(BestVF) && "BestVF is not available in Plan");
640 assert(Plan.hasUF(BestUF) && "BestUF is not available in Plan");
641 VPBasicBlock *ExitingVPBB =
643 auto *Term = &ExitingVPBB->back();
644 // Try to simplify the branch condition if TC <= VF * UF when preparing to
645 // execute the plan for the main vector loop. We only do this if the
646 // terminator is:
647 // 1. BranchOnCount, or
648 // 2. BranchOnCond where the input is Not(ActiveLaneMask).
649 using namespace llvm::VPlanPatternMatch;
650 if (!match(Term, m_BranchOnCount(m_VPValue(), m_VPValue())) &&
651 !match(Term,
652 m_BranchOnCond(m_Not(m_ActiveLaneMask(m_VPValue(), m_VPValue())))))
653 return;
654
655 Type *IdxTy =
657 const SCEV *TripCount = createTripCountSCEV(IdxTy, PSE);
658 ScalarEvolution &SE = *PSE.getSE();
659 ElementCount NumElements = BestVF.multiplyCoefficientBy(BestUF);
660 const SCEV *C = SE.getElementCount(TripCount->getType(), NumElements);
661 if (TripCount->isZero() ||
662 !SE.isKnownPredicate(CmpInst::ICMP_ULE, TripCount, C))
663 return;
664
665 LLVMContext &Ctx = SE.getContext();
666 auto *BOC = new VPInstruction(
669 Term->eraseFromParent();
670 ExitingVPBB->appendRecipe(BOC);
671 Plan.setVF(BestVF);
672 Plan.setUF(BestUF);
673 // TODO: Further simplifications are possible
674 // 1. Replace inductions with constants.
675 // 2. Replace vector loop region with VPBasicBlock.
676}
677
678#ifndef NDEBUG
680 auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
681 if (Region && Region->isReplicator()) {
682 assert(Region->getNumSuccessors() == 1 &&
683 Region->getNumPredecessors() == 1 && "Expected SESE region!");
684 assert(R->getParent()->size() == 1 &&
685 "A recipe in an original replicator region must be the only "
686 "recipe in its block");
687 return Region;
688 }
689 return nullptr;
690}
691#endif
692
693static bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B,
694 VPDominatorTree &VPDT) {
695 if (A == B)
696 return false;
697
698 auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {
699 for (auto &R : *A->getParent()) {
700 if (&R == A)
701 return true;
702 if (&R == B)
703 return false;
704 }
705 llvm_unreachable("recipe not found");
706 };
707 const VPBlockBase *ParentA = A->getParent();
708 const VPBlockBase *ParentB = B->getParent();
709 if (ParentA == ParentB)
710 return LocalComesBefore(A, B);
711
712 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(A)) &&
713 "No replicate regions expected at this point");
714 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(B)) &&
715 "No replicate regions expected at this point");
716 return VPDT.properlyDominates(ParentA, ParentB);
717}
718
719/// Sink users of \p FOR after the recipe defining the previous value \p
720/// Previous of the recurrence. \returns true if all users of \p FOR could be
721/// re-arranged as needed or false if it is not possible.
722static bool
724 VPRecipeBase *Previous,
725 VPDominatorTree &VPDT) {
726 // Collect recipes that need sinking.
729 Seen.insert(Previous);
730 auto TryToPushSinkCandidate = [&](VPRecipeBase *SinkCandidate) {
731 // The previous value must not depend on the users of the recurrence phi. In
732 // that case, FOR is not a fixed order recurrence.
733 if (SinkCandidate == Previous)
734 return false;
735
736 if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||
737 !Seen.insert(SinkCandidate).second ||
738 properlyDominates(Previous, SinkCandidate, VPDT))
739 return true;
740
741 if (SinkCandidate->mayHaveSideEffects())
742 return false;
743
744 WorkList.push_back(SinkCandidate);
745 return true;
746 };
747
748 // Recursively sink users of FOR after Previous.
749 WorkList.push_back(FOR);
750 for (unsigned I = 0; I != WorkList.size(); ++I) {
751 VPRecipeBase *Current = WorkList[I];
752 assert(Current->getNumDefinedValues() == 1 &&
753 "only recipes with a single defined value expected");
754
755 for (VPUser *User : Current->getVPSingleValue()->users()) {
756 if (auto *R = dyn_cast<VPRecipeBase>(User))
757 if (!TryToPushSinkCandidate(R))
758 return false;
759 }
760 }
761
762 // Keep recipes to sink ordered by dominance so earlier instructions are
763 // processed first.
764 sort(WorkList, [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
765 return properlyDominates(A, B, VPDT);
766 });
767
768 for (VPRecipeBase *SinkCandidate : WorkList) {
769 if (SinkCandidate == FOR)
770 continue;
771
772 SinkCandidate->moveAfter(Previous);
773 Previous = SinkCandidate;
774 }
775 return true;
776}
777
779 VPBuilder &Builder) {
780 VPDominatorTree VPDT;
781 VPDT.recalculate(Plan);
782
784 for (VPRecipeBase &R :
786 if (auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R))
787 RecurrencePhis.push_back(FOR);
788
789 for (VPFirstOrderRecurrencePHIRecipe *FOR : RecurrencePhis) {
791 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
792 // Fixed-order recurrences do not contain cycles, so this loop is guaranteed
793 // to terminate.
794 while (auto *PrevPhi =
795 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {
796 assert(PrevPhi->getParent() == FOR->getParent());
797 assert(SeenPhis.insert(PrevPhi).second);
798 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
799 }
800
801 if (!sinkRecurrenceUsersAfterPrevious(FOR, Previous, VPDT))
802 return false;
803
804 // Introduce a recipe to combine the incoming and previous values of a
805 // fixed-order recurrence.
806 VPBasicBlock *InsertBlock = Previous->getParent();
807 if (isa<VPHeaderPHIRecipe>(Previous))
808 Builder.setInsertPoint(InsertBlock, InsertBlock->getFirstNonPhi());
809 else
810 Builder.setInsertPoint(InsertBlock, std::next(Previous->getIterator()));
811
812 auto *RecurSplice = cast<VPInstruction>(
814 {FOR, FOR->getBackedgeValue()}));
815
816 FOR->replaceAllUsesWith(RecurSplice);
817 // Set the first operand of RecurSplice to FOR again, after replacing
818 // all users.
819 RecurSplice->setOperand(0, FOR);
820 }
821 return true;
822}
823
825 for (VPRecipeBase &R :
827 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(&R);
828 if (!PhiR)
829 continue;
830 const RecurrenceDescriptor &RdxDesc = PhiR->getRecurrenceDescriptor();
831 RecurKind RK = RdxDesc.getRecurrenceKind();
832 if (RK != RecurKind::Add && RK != RecurKind::Mul)
833 continue;
834
836 Worklist.insert(PhiR);
837
838 for (unsigned I = 0; I != Worklist.size(); ++I) {
839 VPValue *Cur = Worklist[I];
840 if (auto *RecWithFlags =
841 dyn_cast<VPRecipeWithIRFlags>(Cur->getDefiningRecipe())) {
842 RecWithFlags->dropPoisonGeneratingFlags();
843 }
844
845 for (VPUser *U : Cur->users()) {
846 auto *UserRecipe = dyn_cast<VPRecipeBase>(U);
847 if (!UserRecipe)
848 continue;
849 for (VPValue *V : UserRecipe->definedValues())
850 Worklist.insert(V);
851 }
852 }
853 }
854}
855
856/// Try to simplify recipe \p R.
857static void simplifyRecipe(VPRecipeBase &R, VPTypeAnalysis &TypeInfo) {
858 // Try to remove redundant blend recipes.
859 if (auto *Blend = dyn_cast<VPBlendRecipe>(&R)) {
860 VPValue *Inc0 = Blend->getIncomingValue(0);
861 for (unsigned I = 1; I != Blend->getNumIncomingValues(); ++I)
862 if (Inc0 != Blend->getIncomingValue(I))
863 return;
864 Blend->replaceAllUsesWith(Inc0);
865 Blend->eraseFromParent();
866 return;
867 }
868
869 using namespace llvm::VPlanPatternMatch;
870 VPValue *A;
871 if (match(&R, m_Trunc(m_ZExtOrSExt(m_VPValue(A))))) {
872 VPValue *Trunc = R.getVPSingleValue();
873 Type *TruncTy = TypeInfo.inferScalarType(Trunc);
874 Type *ATy = TypeInfo.inferScalarType(A);
875 if (TruncTy == ATy) {
876 Trunc->replaceAllUsesWith(A);
877 } else {
878 // Don't replace a scalarizing recipe with a widened cast.
879 if (isa<VPReplicateRecipe>(&R))
880 return;
881 if (ATy->getScalarSizeInBits() < TruncTy->getScalarSizeInBits()) {
882
883 unsigned ExtOpcode = match(R.getOperand(0), m_SExt(m_VPValue()))
884 ? Instruction::SExt
885 : Instruction::ZExt;
886 auto *VPC =
887 new VPWidenCastRecipe(Instruction::CastOps(ExtOpcode), A, TruncTy);
888 VPC->insertBefore(&R);
889 Trunc->replaceAllUsesWith(VPC);
890 } else if (ATy->getScalarSizeInBits() > TruncTy->getScalarSizeInBits()) {
891 auto *VPC = new VPWidenCastRecipe(Instruction::Trunc, A, TruncTy);
892 VPC->insertBefore(&R);
893 Trunc->replaceAllUsesWith(VPC);
894 }
895 }
896#ifndef NDEBUG
897 // Verify that the cached type info is for both A and its users is still
898 // accurate by comparing it to freshly computed types.
899 VPTypeAnalysis TypeInfo2(
900 R.getParent()->getPlan()->getCanonicalIV()->getScalarType(),
901 TypeInfo.getContext());
902 assert(TypeInfo.inferScalarType(A) == TypeInfo2.inferScalarType(A));
903 for (VPUser *U : A->users()) {
904 auto *R = dyn_cast<VPRecipeBase>(U);
905 if (!R)
906 continue;
907 for (VPValue *VPV : R->definedValues())
908 assert(TypeInfo.inferScalarType(VPV) == TypeInfo2.inferScalarType(VPV));
909 }
910#endif
911 }
912
913 if (match(&R, m_CombineOr(m_Mul(m_VPValue(A), m_SpecificInt(1)),
914 m_Mul(m_SpecificInt(1), m_VPValue(A)))))
915 return R.getVPSingleValue()->replaceAllUsesWith(A);
916}
917
918/// Try to simplify the recipes in \p Plan.
919static void simplifyRecipes(VPlan &Plan, LLVMContext &Ctx) {
921 Plan.getEntry());
922 VPTypeAnalysis TypeInfo(Plan.getCanonicalIV()->getScalarType(), Ctx);
923 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
924 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
925 simplifyRecipe(R, TypeInfo);
926 }
927 }
928}
929
931 VPlan &Plan, const MapVector<Instruction *, uint64_t> &MinBWs,
932 LLVMContext &Ctx) {
933#ifndef NDEBUG
934 // Count the processed recipes and cross check the count later with MinBWs
935 // size, to make sure all entries in MinBWs have been handled.
936 unsigned NumProcessedRecipes = 0;
937#endif
938 // Keep track of created truncates, so they can be re-used. Note that we
939 // cannot use RAUW after creating a new truncate, as this would could make
940 // other uses have different types for their operands, making them invalidly
941 // typed.
943 VPTypeAnalysis TypeInfo(Plan.getCanonicalIV()->getScalarType(), Ctx);
944 VPBasicBlock *PH = Plan.getEntry();
945 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
947 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
950 continue;
951 if (isa<VPWidenMemoryInstructionRecipe>(&R) &&
952 cast<VPWidenMemoryInstructionRecipe>(&R)->isStore())
953 continue;
954
955 VPValue *ResultVPV = R.getVPSingleValue();
956 auto *UI = cast_or_null<Instruction>(ResultVPV->getUnderlyingValue());
957 unsigned NewResSizeInBits = MinBWs.lookup(UI);
958 if (!NewResSizeInBits)
959 continue;
960
961#ifndef NDEBUG
962 NumProcessedRecipes++;
963#endif
964 // If the value wasn't vectorized, we must maintain the original scalar
965 // type. Skip those here, after incrementing NumProcessedRecipes. Also
966 // skip casts which do not need to be handled explicitly here, as
967 // redundant casts will be removed during recipe simplification.
968 if (isa<VPReplicateRecipe, VPWidenCastRecipe>(&R)) {
969#ifndef NDEBUG
970 // If any of the operands is a live-in and not used by VPWidenRecipe or
971 // VPWidenSelectRecipe, but in MinBWs, make sure it is counted as
972 // processed as well. When MinBWs is currently constructed, there is no
973 // information about whether recipes are widened or replicated and in
974 // case they are reciplicated the operands are not truncated. Counting
975 // them them here ensures we do not miss any recipes in MinBWs.
976 // TODO: Remove once the analysis is done on VPlan.
977 for (VPValue *Op : R.operands()) {
978 if (!Op->isLiveIn())
979 continue;
980 auto *UV = dyn_cast_or_null<Instruction>(Op->getUnderlyingValue());
981 if (UV && MinBWs.contains(UV) && !ProcessedTruncs.contains(Op) &&
982 all_of(Op->users(), [](VPUser *U) {
983 return !isa<VPWidenRecipe, VPWidenSelectRecipe>(U);
984 })) {
985 // Add an entry to ProcessedTruncs to avoid counting the same
986 // operand multiple times.
987 ProcessedTruncs[Op] = nullptr;
988 NumProcessedRecipes += 1;
989 }
990 }
991#endif
992 continue;
993 }
994
995 Type *OldResTy = TypeInfo.inferScalarType(ResultVPV);
996 unsigned OldResSizeInBits = OldResTy->getScalarSizeInBits();
997 assert(OldResTy->isIntegerTy() && "only integer types supported");
998 (void)OldResSizeInBits;
999
1000 auto *NewResTy = IntegerType::get(Ctx, NewResSizeInBits);
1001
1002 // Any wrapping introduced by shrinking this operation shouldn't be
1003 // considered undefined behavior. So, we can't unconditionally copy
1004 // arithmetic wrapping flags to VPW.
1005 if (auto *VPW = dyn_cast<VPRecipeWithIRFlags>(&R))
1006 VPW->dropPoisonGeneratingFlags();
1007
1008 if (OldResSizeInBits != NewResSizeInBits) {
1009 // Extend result to original width.
1010 auto *Ext =
1011 new VPWidenCastRecipe(Instruction::ZExt, ResultVPV, OldResTy);
1012 Ext->insertAfter(&R);
1013 ResultVPV->replaceAllUsesWith(Ext);
1014 Ext->setOperand(0, ResultVPV);
1015 assert(OldResSizeInBits > NewResSizeInBits && "Nothing to shrink?");
1016 } else
1017 assert(cast<VPWidenRecipe>(&R)->getOpcode() == Instruction::ICmp &&
1018 "Only ICmps should not need extending the result.");
1019
1020 if (isa<VPWidenMemoryInstructionRecipe>(&R)) {
1021 assert(!cast<VPWidenMemoryInstructionRecipe>(&R)->isStore() && "stores cannot be narrowed");
1022 continue;
1023 }
1024
1025 // Shrink operands by introducing truncates as needed.
1026 unsigned StartIdx = isa<VPWidenSelectRecipe>(&R) ? 1 : 0;
1027 for (unsigned Idx = StartIdx; Idx != R.getNumOperands(); ++Idx) {
1028 auto *Op = R.getOperand(Idx);
1029 unsigned OpSizeInBits =
1031 if (OpSizeInBits == NewResSizeInBits)
1032 continue;
1033 assert(OpSizeInBits > NewResSizeInBits && "nothing to truncate");
1034 auto [ProcessedIter, IterIsEmpty] =
1035 ProcessedTruncs.insert({Op, nullptr});
1036 VPWidenCastRecipe *NewOp =
1037 IterIsEmpty
1038 ? new VPWidenCastRecipe(Instruction::Trunc, Op, NewResTy)
1039 : ProcessedIter->second;
1040 R.setOperand(Idx, NewOp);
1041 if (!IterIsEmpty)
1042 continue;
1043 ProcessedIter->second = NewOp;
1044 if (!Op->isLiveIn()) {
1045 NewOp->insertBefore(&R);
1046 } else {
1047 PH->appendRecipe(NewOp);
1048#ifndef NDEBUG
1049 auto *OpInst = dyn_cast<Instruction>(Op->getLiveInIRValue());
1050 bool IsContained = MinBWs.contains(OpInst);
1051 NumProcessedRecipes += IsContained;
1052#endif
1053 }
1054 }
1055
1056 }
1057 }
1058
1059 assert(MinBWs.size() == NumProcessedRecipes &&
1060 "some entries in MinBWs haven't been processed");
1061}
1062
1066
1067 simplifyRecipes(Plan, SE.getContext());
1069 removeDeadRecipes(Plan);
1070
1072
1075}
1076
1077// Add a VPActiveLaneMaskPHIRecipe and related recipes to \p Plan and replace
1078// the loop terminator with a branch-on-cond recipe with the negated
1079// active-lane-mask as operand. Note that this turns the loop into an
1080// uncountable one. Only the existing terminator is replaced, all other existing
1081// recipes/users remain unchanged, except for poison-generating flags being
1082// dropped from the canonical IV increment. Return the created
1083// VPActiveLaneMaskPHIRecipe.
1084//
1085// The function uses the following definitions:
1086//
1087// %TripCount = DataWithControlFlowWithoutRuntimeCheck ?
1088// calculate-trip-count-minus-VF (original TC) : original TC
1089// %IncrementValue = DataWithControlFlowWithoutRuntimeCheck ?
1090// CanonicalIVPhi : CanonicalIVIncrement
1091// %StartV is the canonical induction start value.
1092//
1093// The function adds the following recipes:
1094//
1095// vector.ph:
1096// %TripCount = calculate-trip-count-minus-VF (original TC)
1097// [if DataWithControlFlowWithoutRuntimeCheck]
1098// %EntryInc = canonical-iv-increment-for-part %StartV
1099// %EntryALM = active-lane-mask %EntryInc, %TripCount
1100//
1101// vector.body:
1102// ...
1103// %P = active-lane-mask-phi [ %EntryALM, %vector.ph ], [ %ALM, %vector.body ]
1104// ...
1105// %InLoopInc = canonical-iv-increment-for-part %IncrementValue
1106// %ALM = active-lane-mask %InLoopInc, TripCount
1107// %Negated = Not %ALM
1108// branch-on-cond %Negated
1109//
1112 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
1113 VPBasicBlock *EB = TopRegion->getExitingBasicBlock();
1114 auto *CanonicalIVPHI = Plan.getCanonicalIV();
1115 VPValue *StartV = CanonicalIVPHI->getStartValue();
1116
1117 auto *CanonicalIVIncrement =
1118 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());
1119 // TODO: Check if dropping the flags is needed if
1120 // !DataAndControlFlowWithoutRuntimeCheck.
1121 CanonicalIVIncrement->dropPoisonGeneratingFlags();
1122 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
1123 // We can't use StartV directly in the ActiveLaneMask VPInstruction, since
1124 // we have to take unrolling into account. Each part needs to start at
1125 // Part * VF
1126 auto *VecPreheader = cast<VPBasicBlock>(TopRegion->getSinglePredecessor());
1127 VPBuilder Builder(VecPreheader);
1128
1129 // Create the ActiveLaneMask instruction using the correct start values.
1130 VPValue *TC = Plan.getTripCount();
1131
1132 VPValue *TripCount, *IncrementValue;
1134 // When the loop is guarded by a runtime overflow check for the loop
1135 // induction variable increment by VF, we can increment the value before
1136 // the get.active.lane mask and use the unmodified tripcount.
1137 IncrementValue = CanonicalIVIncrement;
1138 TripCount = TC;
1139 } else {
1140 // When avoiding a runtime check, the active.lane.mask inside the loop
1141 // uses a modified trip count and the induction variable increment is
1142 // done after the active.lane.mask intrinsic is called.
1143 IncrementValue = CanonicalIVPHI;
1145 {TC}, DL);
1146 }
1147 auto *EntryIncrement = Builder.createOverflowingOp(
1148 VPInstruction::CanonicalIVIncrementForPart, {StartV}, {false, false}, DL,
1149 "index.part.next");
1150
1151 // Create the active lane mask instruction in the VPlan preheader.
1152 auto *EntryALM =
1153 Builder.createNaryOp(VPInstruction::ActiveLaneMask, {EntryIncrement, TC},
1154 DL, "active.lane.mask.entry");
1155
1156 // Now create the ActiveLaneMaskPhi recipe in the main loop using the
1157 // preheader ActiveLaneMask instruction.
1158 auto LaneMaskPhi = new VPActiveLaneMaskPHIRecipe(EntryALM, DebugLoc());
1159 LaneMaskPhi->insertAfter(CanonicalIVPHI);
1160
1161 // Create the active lane mask for the next iteration of the loop before the
1162 // original terminator.
1163 VPRecipeBase *OriginalTerminator = EB->getTerminator();
1164 Builder.setInsertPoint(OriginalTerminator);
1165 auto *InLoopIncrement =
1167 {IncrementValue}, {false, false}, DL);
1168 auto *ALM = Builder.createNaryOp(VPInstruction::ActiveLaneMask,
1169 {InLoopIncrement, TripCount}, DL,
1170 "active.lane.mask.next");
1171 LaneMaskPhi->addOperand(ALM);
1172
1173 // Replace the original terminator with BranchOnCond. We have to invert the
1174 // mask here because a true condition means jumping to the exit block.
1175 auto *NotMask = Builder.createNot(ALM, DL);
1176 Builder.createNaryOp(VPInstruction::BranchOnCond, {NotMask}, DL);
1177 OriginalTerminator->eraseFromParent();
1178 return LaneMaskPhi;
1179}
1180
1182 VPlan &Plan, bool UseActiveLaneMaskForControlFlow,
1185 UseActiveLaneMaskForControlFlow) &&
1186 "DataAndControlFlowWithoutRuntimeCheck implies "
1187 "UseActiveLaneMaskForControlFlow");
1188
1189 auto FoundWidenCanonicalIVUser =
1190 find_if(Plan.getCanonicalIV()->users(),
1191 [](VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); });
1192 assert(FoundWidenCanonicalIVUser &&
1193 "Must have widened canonical IV when tail folding!");
1194 auto *WideCanonicalIV =
1195 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);
1196 VPSingleDefRecipe *LaneMask;
1197 if (UseActiveLaneMaskForControlFlow) {
1200 } else {
1201 VPBuilder B = VPBuilder::getToInsertAfter(WideCanonicalIV);
1202 LaneMask = B.createNaryOp(VPInstruction::ActiveLaneMask,
1203 {WideCanonicalIV, Plan.getTripCount()}, nullptr,
1204 "active.lane.mask");
1205 }
1206
1207 // Walk users of WideCanonicalIV and replace all compares of the form
1208 // (ICMP_ULE, WideCanonicalIV, backedge-taken-count) with an
1209 // active-lane-mask.
1211 for (VPUser *U : SmallVector<VPUser *>(WideCanonicalIV->users())) {
1212 auto *CompareToReplace = dyn_cast<VPInstruction>(U);
1213 if (!CompareToReplace ||
1214 CompareToReplace->getOpcode() != Instruction::ICmp ||
1215 CompareToReplace->getPredicate() != CmpInst::ICMP_ULE ||
1216 CompareToReplace->getOperand(1) != BTC)
1217 continue;
1218
1219 assert(CompareToReplace->getOperand(0) == WideCanonicalIV &&
1220 "WidenCanonicalIV must be the first operand of the compare");
1221 CompareToReplace->replaceAllUsesWith(LaneMask);
1222 CompareToReplace->eraseFromParent();
1223 }
1224}
1225
1227 VPlan &Plan, function_ref<bool(BasicBlock *)> BlockNeedsPredication) {
1228 // Collect recipes in the backward slice of `Root` that may generate a poison
1229 // value that is used after vectorization.
1231 auto collectPoisonGeneratingInstrsInBackwardSlice([&](VPRecipeBase *Root) {
1233 Worklist.push_back(Root);
1234
1235 // Traverse the backward slice of Root through its use-def chain.
1236 while (!Worklist.empty()) {
1237 VPRecipeBase *CurRec = Worklist.back();
1238 Worklist.pop_back();
1239
1240 if (!Visited.insert(CurRec).second)
1241 continue;
1242
1243 // Prune search if we find another recipe generating a widen memory
1244 // instruction. Widen memory instructions involved in address computation
1245 // will lead to gather/scatter instructions, which don't need to be
1246 // handled.
1247 if (isa<VPWidenMemoryInstructionRecipe>(CurRec) ||
1248 isa<VPInterleaveRecipe>(CurRec) ||
1249 isa<VPScalarIVStepsRecipe>(CurRec) ||
1250 isa<VPCanonicalIVPHIRecipe>(CurRec) ||
1251 isa<VPActiveLaneMaskPHIRecipe>(CurRec))
1252 continue;
1253
1254 // This recipe contributes to the address computation of a widen
1255 // load/store. If the underlying instruction has poison-generating flags,
1256 // drop them directly.
1257 if (auto *RecWithFlags = dyn_cast<VPRecipeWithIRFlags>(CurRec)) {
1258 RecWithFlags->dropPoisonGeneratingFlags();
1259 } else {
1260 Instruction *Instr = dyn_cast_or_null<Instruction>(
1261 CurRec->getVPSingleValue()->getUnderlyingValue());
1262 (void)Instr;
1263 assert((!Instr || !Instr->hasPoisonGeneratingFlags()) &&
1264 "found instruction with poison generating flags not covered by "
1265 "VPRecipeWithIRFlags");
1266 }
1267
1268 // Add new definitions to the worklist.
1269 for (VPValue *operand : CurRec->operands())
1270 if (VPRecipeBase *OpDef = operand->getDefiningRecipe())
1271 Worklist.push_back(OpDef);
1272 }
1273 });
1274
1275 // Traverse all the recipes in the VPlan and collect the poison-generating
1276 // recipes in the backward slice starting at the address of a VPWidenRecipe or
1277 // VPInterleaveRecipe.
1278 auto Iter = vp_depth_first_deep(Plan.getEntry());
1279 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
1280 for (VPRecipeBase &Recipe : *VPBB) {
1281 if (auto *WidenRec = dyn_cast<VPWidenMemoryInstructionRecipe>(&Recipe)) {
1282 Instruction &UnderlyingInstr = WidenRec->getIngredient();
1283 VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();
1284 if (AddrDef && WidenRec->isConsecutive() &&
1285 BlockNeedsPredication(UnderlyingInstr.getParent()))
1286 collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
1287 } else if (auto *InterleaveRec = dyn_cast<VPInterleaveRecipe>(&Recipe)) {
1288 VPRecipeBase *AddrDef = InterleaveRec->getAddr()->getDefiningRecipe();
1289 if (AddrDef) {
1290 // Check if any member of the interleave group needs predication.
1291 const InterleaveGroup<Instruction> *InterGroup =
1292 InterleaveRec->getInterleaveGroup();
1293 bool NeedPredication = false;
1294 for (int I = 0, NumMembers = InterGroup->getNumMembers();
1295 I < NumMembers; ++I) {
1296 Instruction *Member = InterGroup->getMember(I);
1297 if (Member)
1298 NeedPredication |= BlockNeedsPredication(Member->getParent());
1299 }
1300
1301 if (NeedPredication)
1302 collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
1303 }
1304 }
1305 }
1306 }
1307}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool isStore(int Opcode)
ReachingDefAnalysis InstSet & ToRemove
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Hexagon Common GEP
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution &SE)
#define I(x, y, z)
Definition: MD5.cpp:58
if(VerifyEach)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file implements a set that has insertion order iteration characteristics.
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:191
static bool sinkScalarOperands(VPlan &Plan)
static void removeRedundantInductionCasts(VPlan &Plan)
Remove redundant casts of inductions.
static void simplifyRecipes(VPlan &Plan, LLVMContext &Ctx)
Try to simplify the recipes in Plan.
static bool sinkRecurrenceUsersAfterPrevious(VPFirstOrderRecurrencePHIRecipe *FOR, VPRecipeBase *Previous, VPDominatorTree &VPDT)
Sink users of FOR after the recipe defining the previous value Previous of the recurrence.
static bool mergeReplicateRegionsIntoSuccessors(VPlan &Plan)
static VPActiveLaneMaskPHIRecipe * addVPLaneMaskPhiAndUpdateExitBranch(VPlan &Plan, bool DataAndControlFlowWithoutRuntimeCheck)
static void addReplicateRegions(VPlan &Plan)
static void legalizeAndOptimizeInductions(VPlan &Plan, ScalarEvolution &SE)
Legalize VPWidenPointerInductionRecipe, by replacing it with a PtrAdd (IndStart, ScalarIVSteps (0,...
static void simplifyRecipe(VPRecipeBase &R, VPTypeAnalysis &TypeInfo)
Try to simplify recipe R.
static VPRegionBlock * GetReplicateRegion(VPRecipeBase *R)
static void removeRedundantExpandSCEVRecipes(VPlan &Plan)
Remove redundant EpxandSCEVRecipes in Plan's entry block by replacing them with already existing reci...
static bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B, VPDominatorTree &VPDT)
static VPValue * createScalarIVSteps(VPlan &Plan, InductionDescriptor::InductionKind Kind, Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp, ScalarEvolution &SE, Instruction *TruncI, VPValue *StartV, VPValue *Step, VPBasicBlock::iterator IP)
static void removeDeadRecipes(VPlan &Plan)
static VPRegionBlock * createReplicateRegion(VPReplicateRecipe *PredRecipe, VPlan &Plan)
static VPBasicBlock * getPredicatedThenBlock(VPRegionBlock *R)
If R is a triangle region, return the 'then' block of the triangle.
VPValue * getPredicatedMask(VPRegionBlock *R)
If R is a region with a VPBranchOnMaskRecipe in the entry block, return the mask.
static void removeRedundantCanonicalIVs(VPlan &Plan)
Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV recipe, if it exists.
This file provides utility VPlan to VPlan transformations.
static const uint32_t IV[8]
Definition: blake3_impl.h:78
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
This class represents a function call, abstracting a target machine's calling convention.
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:986
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:849
This class represents an Operation in the Expression.
A debug info location.
Definition: DebugLoc.h:33
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:145
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Core dominator tree base class.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
static constexpr ElementCount getFixed(ScalarTy MinVal)
Definition: TypeSize.h:296
Utility class for floating point operations which can have information about relaxed accuracy require...
Definition: Operator.h:200
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags.
Definition: Operator.h:318
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:20
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:973
A struct for saving information about induction variables.
InductionKind
This enum represents the kinds of inductions that we support.
@ IK_IntInduction
Integer induction variable. Step = C.
const BasicBlock * getParent() const
Definition: Instruction.h:152
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:278
The group of interleaved loads/stores sharing the same stride and close to each other.
Definition: VectorUtils.h:444
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
Definition: VectorUtils.h:514
uint32_t getNumMembers() const
Definition: VectorUtils.h:462
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
An instruction for reading from memory.
Definition: Instructions.h:184
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
bool contains(const KeyT &Key) const
Definition: MapVector.h:163
ValueT lookup(const KeyT &Key) const
Definition: MapVector.h:110
size_type size() const
Definition: MapVector.h:60
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:71
RecurKind getRecurrenceKind() const
This class represents an analyzed expression in the program.
bool isZero() const
Return true if the expression is a constant zero.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getElementCount(Type *Ty, ElementCount EC)
LLVMContext & getContext() const
This class represents the LLVM 'select' instruction.
A vector that has set insertion semantics.
Definition: SetVector.h:57
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:254
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
An instruction for storing to memory.
Definition: Instructions.h:317
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:228
op_range operands()
Definition: User.h:242
A recipe for generating the active lane mask for the vector loop that is used to predicate the vector...
Definition: VPlan.h:2444
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2618
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2686
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:2639
iterator end()
Definition: VPlan.h:2649
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
Definition: VPlan.h:2696
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:210
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:530
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition: VPlan.cpp:593
const VPRecipeBase & back() const
Definition: VPlan.h:2661
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:2677
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:421
VPRegionBlock * getParent()
Definition: VPlan.h:493
const VPBasicBlock * getExitingBasicBlock() const
Definition: VPlan.cpp:175
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:534
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:153
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:580
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:528
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:518
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition: VPlan.h:3202
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3230
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3219
A recipe for generating conditional branches on the bits of a mask.
Definition: VPlan.h:2166
VPlan-based builder utility analogous to IRBuilder.
static VPBuilder getToInsertAfter(VPRecipeBase *R)
Create a VPBuilder to insert after R.
VPInstruction * createOverflowingOp(unsigned Opcode, std::initializer_list< VPValue * > Operands, VPRecipeWithIRFlags::WrapFlagsTy WrapFlags, DebugLoc DL={}, const Twine &Name="")
VPInstruction * createNaryOp(unsigned Opcode, ArrayRef< VPValue * > Operands, Instruction *Inst=nullptr, const Twine &Name="")
Create an N-ary operation with Opcode, Operands and set Inst as its underlying Instruction.
VPValue * createNot(VPValue *Operand, DebugLoc DL={}, const Twine &Name="")
void setInsertPoint(VPBasicBlock *TheBB)
This specifies that created VPInstructions should be appended to the end of the specified block.
Canonical scalar induction phi of the vector loop.
Definition: VPlan.h:2387
Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:2416
bool isCanonical(InductionDescriptor::InductionKind Kind, VPValue *Start, VPValue *Step) const
Check if the induction described by Kind, /p Start and Step is canonical, i.e.
unsigned getNumDefinedValues() const
Returns the number of values defined by the VPDef.
Definition: VPlanValue.h:425
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:398
A recipe for converting the canonical IV value to the corresponding value of an IV with different sta...
Definition: VPlan.h:2508
VPValue * getStartValue()
Returns the start value of the phi, if one is set.
Definition: VPlan.h:1624
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:1139
@ FirstOrderRecurrenceSplice
Definition: VPlan.h:1145
@ CanonicalIVIncrementForPart
Definition: VPlan.h:1154
@ CalculateTripCountMinusVF
Definition: VPlan.h:1152
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
Definition: VPlan.h:2217
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:713
bool mayReadOrWriteMemory() const
Returns true if the recipe may read from or write to memory.
Definition: VPlan.h:799
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
VPBasicBlock * getParent()
Definition: VPlan.h:738
void moveBefore(VPBasicBlock &BB, iplist< VPRecipeBase >::iterator I)
Unlink this recipe and insert into BB before I.
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2751
const VPBlockBase * getEntry() const
Definition: VPlan.h:2790
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:2093
bool isUniform() const
Definition: VPlan.h:2133
VPValue * getMask()
Return the mask of a predicated VPReplicateRecipe.
Definition: VPlan.h:2157
VPScalarCastRecipe is a recipe to create scalar cast instructions.
Definition: VPlan.h:1381
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition: VPlan.h:2568
VPSingleDef is a base class for recipes for modeling a sequence of one or more output IR that define ...
Definition: VPlan.h:830
Instruction * getUnderlyingInstr()
Returns the underlying instruction.
Definition: VPlan.h:887
An analysis for type-inference for VPValues.
Definition: VPlanAnalysis.h:36
LLVMContext & getContext()
Return the LLVMContext used by the analysis.
Definition: VPlanAnalysis.h:61
Type * inferScalarType(const VPValue *V)
Infer the type of V. Returns the scalar type of V.
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:204
operand_range operands()
Definition: VPlanValue.h:279
void setOperand(unsigned I, VPValue *New)
Definition: VPlanValue.h:259
operand_iterator op_end()
Definition: VPlanValue.h:277
operand_iterator op_begin()
Definition: VPlanValue.h:275
void addOperand(VPValue *Operand)
Definition: VPlanValue.h:248
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
Definition: VPlanValue.h:78
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition: VPlan.cpp:118
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:1277
unsigned getNumUsers() const
Definition: VPlanValue.h:113
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
Definition: VPlanValue.h:174
void replaceUsesWithIf(VPValue *New, llvm::function_ref< bool(VPUser &U, unsigned Idx)> ShouldReplace)
Go through the uses list for this VPValue and make each use point to New if the callback ShouldReplac...
Definition: VPlan.cpp:1281
user_range users()
Definition: VPlanValue.h:134
A recipe for widening Call instructions.
Definition: VPlan.h:1420
A Recipe for widening the canonical induction variable of the vector loop.
Definition: VPlan.h:2473
const Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:2499
VPWidenCastRecipe is a recipe to create vector cast instructions.
Definition: VPlan.h:1331
A recipe for handling GEP instructions.
Definition: VPlan.h:1493
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
Definition: VPlan.h:1648
A Recipe for widening load/store operations.
Definition: VPlan.h:2254
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:1299
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2852
bool hasScalableVF()
Definition: VPlan.h:2984
VPBasicBlock * getEntry()
Definition: VPlan.h:2945
VPValue * getTripCount() const
The trip count of the original loop.
Definition: VPlan.h:2949
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition: VPlan.h:2963
VPValue * getVPValueOrAddLiveIn(Value *V)
Gets the VPValue for V or adds a new live-in (if none exists yet) for V.
Definition: VPlan.h:3021
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:3047
bool hasVF(ElementCount VF)
Definition: VPlan.h:2983
bool hasUF(unsigned UF) const
Definition: VPlan.h:2990
void setVF(ElementCount VF)
Definition: VPlan.h:2977
bool hasScalarVFOnly() const
Definition: VPlan.h:2988
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
Definition: VPlan.h:3055
void setUF(unsigned UF)
Definition: VPlan.h:2992
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:377
bool hasName() const
Definition: Value.h:261
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
constexpr LeafTy multiplyCoefficientBy(ScalarTy RHS) const
Definition: TypeSize.h:243
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
Definition: ilist_node.h:109
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:918
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
CastOperator_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:234
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
Definition: VPlan.cpp:1419
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used.
Definition: VPlan.cpp:1409
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1731
Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
const SCEV * createTripCountSCEV(Type *IdxTy, PredicatedScalarEvolution &PSE, Loop *OrigLoop)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
iterator_range< df_iterator< VPBlockDeepTraversalWrapper< VPBlockBase * > > > vp_depth_first_deep(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order while traversing t...
Definition: VPlanCFG.h:226
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1738
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:134
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1745
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
Definition: SmallVector.h:1312
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition: Casting.h:548
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
Definition: STLExtras.h:336
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:34
@ Mul
Product of integers.
@ Add
Sum of integers.
DWARFExpression::Operation Op
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1758
@ DataAndControlFlowWithoutRuntimeCheck
Use predicate to control both data and control flow, but modify the trip count so that a runtime over...
A recipe for handling first-order recurrence phis.
Definition: VPlan.h:1818
A recipe for widening select instructions.
Definition: VPlan.h:1459
static void createAndOptimizeReplicateRegions(VPlan &Plan)
Wrap predicated VPReplicateRecipes with a mask operand in an if-then region block and remove the mask...
static void dropPoisonGeneratingRecipes(VPlan &Plan, function_ref< bool(BasicBlock *)> BlockNeedsPredication)
Drop poison flags from recipes that may generate a poison value that is used after vectorization,...
static void optimize(VPlan &Plan, ScalarEvolution &SE)
Apply VPlan-to-VPlan optimizations to Plan, including induction recipe optimizations,...
static void clearReductionWrapFlags(VPlan &Plan)
Clear NSW/NUW flags from reduction instructions if necessary.
static void VPInstructionsToVPRecipes(VPlanPtr &Plan, function_ref< const InductionDescriptor *(PHINode *)> GetIntOrFpInductionDescriptor, ScalarEvolution &SE, const TargetLibraryInfo &TLI)
Replaces the VPInstructions in Plan with corresponding widen recipes.
static void truncateToMinimalBitwidths(VPlan &Plan, const MapVector< Instruction *, uint64_t > &MinBWs, LLVMContext &Ctx)
Insert truncates and extends for any truncated recipe.
static void addActiveLaneMask(VPlan &Plan, bool UseActiveLaneMaskForControlFlow, bool DataAndControlFlowWithoutRuntimeCheck)
Replace (ICMP_ULE, wide canonical IV, backedge-taken-count) checks with an (active-lane-mask recipe,...
static bool adjustFixedOrderRecurrences(VPlan &Plan, VPBuilder &Builder)
Sink users of fixed-order recurrences after the recipe defining their previous value.
static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF, unsigned BestUF, PredicatedScalarEvolution &PSE)
Optimize Plan based on BestVF and BestUF.