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->getOrAddLiveIn(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 VPWidenMemoryRecipe for loads and stores.
64 if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
65 NewRecipe = new VPWidenLoadRecipe(
66 *Load, Ingredient.getOperand(0), nullptr /*Mask*/,
67 false /*Consecutive*/, false /*Reverse*/,
68 Ingredient.getDebugLoc());
69 } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
70 NewRecipe = new VPWidenStoreRecipe(
71 *Store, Ingredient.getOperand(1), Ingredient.getOperand(0),
72 nullptr /*Mask*/, false /*Consecutive*/, false /*Reverse*/,
73 Ingredient.getDebugLoc());
74 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
75 NewRecipe = new VPWidenGEPRecipe(GEP, Ingredient.operands());
76 } else if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
77 NewRecipe = new VPWidenCallRecipe(
78 CI, Ingredient.operands(), getVectorIntrinsicIDForCall(CI, &TLI),
79 CI->getDebugLoc());
80 } else if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
81 NewRecipe = new VPWidenSelectRecipe(*SI, Ingredient.operands());
82 } else if (auto *CI = dyn_cast<CastInst>(Inst)) {
83 NewRecipe = new VPWidenCastRecipe(
84 CI->getOpcode(), Ingredient.getOperand(0), CI->getType(), *CI);
85 } else {
86 NewRecipe = new VPWidenRecipe(*Inst, Ingredient.operands());
87 }
88 }
89
90 NewRecipe->insertBefore(&Ingredient);
91 if (NewRecipe->getNumDefinedValues() == 1)
92 VPV->replaceAllUsesWith(NewRecipe->getVPSingleValue());
93 else
94 assert(NewRecipe->getNumDefinedValues() == 0 &&
95 "Only recpies with zero or one defined values expected");
96 Ingredient.eraseFromParent();
97 }
98 }
99}
100
101static bool sinkScalarOperands(VPlan &Plan) {
102 auto Iter = vp_depth_first_deep(Plan.getEntry());
103 bool Changed = false;
104 // First, collect the operands of all recipes in replicate blocks as seeds for
105 // sinking.
107 for (VPRegionBlock *VPR : VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)) {
108 VPBasicBlock *EntryVPBB = VPR->getEntryBasicBlock();
109 if (!VPR->isReplicator() || EntryVPBB->getSuccessors().size() != 2)
110 continue;
111 VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(EntryVPBB->getSuccessors()[0]);
112 if (!VPBB || VPBB->getSingleSuccessor() != VPR->getExitingBasicBlock())
113 continue;
114 for (auto &Recipe : *VPBB) {
115 for (VPValue *Op : Recipe.operands())
116 if (auto *Def =
117 dyn_cast_or_null<VPSingleDefRecipe>(Op->getDefiningRecipe()))
118 WorkList.insert(std::make_pair(VPBB, Def));
119 }
120 }
121
122 bool ScalarVFOnly = Plan.hasScalarVFOnly();
123 // Try to sink each replicate or scalar IV steps recipe in the worklist.
124 for (unsigned I = 0; I != WorkList.size(); ++I) {
125 VPBasicBlock *SinkTo;
126 VPSingleDefRecipe *SinkCandidate;
127 std::tie(SinkTo, SinkCandidate) = WorkList[I];
128 if (SinkCandidate->getParent() == SinkTo ||
129 SinkCandidate->mayHaveSideEffects() ||
130 SinkCandidate->mayReadOrWriteMemory())
131 continue;
132 if (auto *RepR = dyn_cast<VPReplicateRecipe>(SinkCandidate)) {
133 if (!ScalarVFOnly && RepR->isUniform())
134 continue;
135 } else if (!isa<VPScalarIVStepsRecipe>(SinkCandidate))
136 continue;
137
138 bool NeedsDuplicating = false;
139 // All recipe users of the sink candidate must be in the same block SinkTo
140 // or all users outside of SinkTo must be uniform-after-vectorization (
141 // i.e., only first lane is used) . In the latter case, we need to duplicate
142 // SinkCandidate.
143 auto CanSinkWithUser = [SinkTo, &NeedsDuplicating,
144 SinkCandidate](VPUser *U) {
145 auto *UI = dyn_cast<VPRecipeBase>(U);
146 if (!UI)
147 return false;
148 if (UI->getParent() == SinkTo)
149 return true;
150 NeedsDuplicating = UI->onlyFirstLaneUsed(SinkCandidate);
151 // We only know how to duplicate VPRecipeRecipes for now.
152 return NeedsDuplicating && isa<VPReplicateRecipe>(SinkCandidate);
153 };
154 if (!all_of(SinkCandidate->users(), CanSinkWithUser))
155 continue;
156
157 if (NeedsDuplicating) {
158 if (ScalarVFOnly)
159 continue;
160 Instruction *I = SinkCandidate->getUnderlyingInstr();
161 auto *Clone = new VPReplicateRecipe(I, SinkCandidate->operands(), true);
162 // TODO: add ".cloned" suffix to name of Clone's VPValue.
163
164 Clone->insertBefore(SinkCandidate);
165 SinkCandidate->replaceUsesWithIf(Clone, [SinkTo](VPUser &U, unsigned) {
166 return cast<VPRecipeBase>(&U)->getParent() != SinkTo;
167 });
168 }
169 SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi());
170 for (VPValue *Op : SinkCandidate->operands())
171 if (auto *Def =
172 dyn_cast_or_null<VPSingleDefRecipe>(Op->getDefiningRecipe()))
173 WorkList.insert(std::make_pair(SinkTo, Def));
174 Changed = true;
175 }
176 return Changed;
177}
178
179/// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return
180/// the mask.
182 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
183 if (!EntryBB || EntryBB->size() != 1 ||
184 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
185 return nullptr;
186
187 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
188}
189
190/// If \p R is a triangle region, return the 'then' block of the triangle.
192 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
193 if (EntryBB->getNumSuccessors() != 2)
194 return nullptr;
195
196 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
197 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
198 if (!Succ0 || !Succ1)
199 return nullptr;
200
201 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
202 return nullptr;
203 if (Succ0->getSingleSuccessor() == Succ1)
204 return Succ0;
205 if (Succ1->getSingleSuccessor() == Succ0)
206 return Succ1;
207 return nullptr;
208}
209
210// Merge replicate regions in their successor region, if a replicate region
211// is connected to a successor replicate region with the same predicate by a
212// single, empty VPBasicBlock.
214 SetVector<VPRegionBlock *> DeletedRegions;
215
216 // Collect replicate regions followed by an empty block, followed by another
217 // replicate region with matching masks to process front. This is to avoid
218 // iterator invalidation issues while merging regions.
220 for (VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
221 vp_depth_first_deep(Plan.getEntry()))) {
222 if (!Region1->isReplicator())
223 continue;
224 auto *MiddleBasicBlock =
225 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
226 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
227 continue;
228
229 auto *Region2 =
230 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
231 if (!Region2 || !Region2->isReplicator())
232 continue;
233
234 VPValue *Mask1 = getPredicatedMask(Region1);
235 VPValue *Mask2 = getPredicatedMask(Region2);
236 if (!Mask1 || Mask1 != Mask2)
237 continue;
238
239 assert(Mask1 && Mask2 && "both region must have conditions");
240 WorkList.push_back(Region1);
241 }
242
243 // Move recipes from Region1 to its successor region, if both are triangles.
244 for (VPRegionBlock *Region1 : WorkList) {
245 if (DeletedRegions.contains(Region1))
246 continue;
247 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());
248 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
249
250 VPBasicBlock *Then1 = getPredicatedThenBlock(Region1);
251 VPBasicBlock *Then2 = getPredicatedThenBlock(Region2);
252 if (!Then1 || !Then2)
253 continue;
254
255 // Note: No fusion-preventing memory dependencies are expected in either
256 // region. Such dependencies should be rejected during earlier dependence
257 // checks, which guarantee accesses can be re-ordered for vectorization.
258 //
259 // Move recipes to the successor region.
260 for (VPRecipeBase &ToMove : make_early_inc_range(reverse(*Then1)))
261 ToMove.moveBefore(*Then2, Then2->getFirstNonPhi());
262
263 auto *Merge1 = cast<VPBasicBlock>(Then1->getSingleSuccessor());
264 auto *Merge2 = cast<VPBasicBlock>(Then2->getSingleSuccessor());
265
266 // Move VPPredInstPHIRecipes from the merge block to the successor region's
267 // merge block. Update all users inside the successor region to use the
268 // original values.
269 for (VPRecipeBase &Phi1ToMove : make_early_inc_range(reverse(*Merge1))) {
270 VPValue *PredInst1 =
271 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
272 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
273 Phi1ToMoveV->replaceUsesWithIf(PredInst1, [Then2](VPUser &U, unsigned) {
274 auto *UI = dyn_cast<VPRecipeBase>(&U);
275 return UI && UI->getParent() == Then2;
276 });
277
278 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
279 }
280
281 // Finally, remove the first region.
282 for (VPBlockBase *Pred : make_early_inc_range(Region1->getPredecessors())) {
283 VPBlockUtils::disconnectBlocks(Pred, Region1);
284 VPBlockUtils::connectBlocks(Pred, MiddleBasicBlock);
285 }
286 VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock);
287 DeletedRegions.insert(Region1);
288 }
289
290 for (VPRegionBlock *ToDelete : DeletedRegions)
291 delete ToDelete;
292 return !DeletedRegions.empty();
293}
294
296 VPlan &Plan) {
297 Instruction *Instr = PredRecipe->getUnderlyingInstr();
298 // Build the triangular if-then region.
299 std::string RegionName = (Twine("pred.") + Instr->getOpcodeName()).str();
300 assert(Instr->getParent() && "Predicated instruction not in any basic block");
301 auto *BlockInMask = PredRecipe->getMask();
302 auto *BOMRecipe = new VPBranchOnMaskRecipe(BlockInMask);
303 auto *Entry = new VPBasicBlock(Twine(RegionName) + ".entry", BOMRecipe);
304
305 // Replace predicated replicate recipe with a replicate recipe without a
306 // mask but in the replicate region.
307 auto *RecipeWithoutMask = new VPReplicateRecipe(
308 PredRecipe->getUnderlyingInstr(),
309 make_range(PredRecipe->op_begin(), std::prev(PredRecipe->op_end())),
310 PredRecipe->isUniform());
311 auto *Pred = new VPBasicBlock(Twine(RegionName) + ".if", RecipeWithoutMask);
312
313 VPPredInstPHIRecipe *PHIRecipe = nullptr;
314 if (PredRecipe->getNumUsers() != 0) {
315 PHIRecipe = new VPPredInstPHIRecipe(RecipeWithoutMask);
316 PredRecipe->replaceAllUsesWith(PHIRecipe);
317 PHIRecipe->setOperand(0, RecipeWithoutMask);
318 }
319 PredRecipe->eraseFromParent();
320 auto *Exiting = new VPBasicBlock(Twine(RegionName) + ".continue", PHIRecipe);
321 VPRegionBlock *Region = new VPRegionBlock(Entry, Exiting, RegionName, true);
322
323 // Note: first set Entry as region entry and then connect successors starting
324 // from it in order, to propagate the "parent" of each VPBasicBlock.
325 VPBlockUtils::insertTwoBlocksAfter(Pred, Exiting, Entry);
326 VPBlockUtils::connectBlocks(Pred, Exiting);
327
328 return Region;
329}
330
331static void addReplicateRegions(VPlan &Plan) {
333 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
334 vp_depth_first_deep(Plan.getEntry()))) {
335 for (VPRecipeBase &R : *VPBB)
336 if (auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
337 if (RepR->isPredicated())
338 WorkList.push_back(RepR);
339 }
340 }
341
342 unsigned BBNum = 0;
343 for (VPReplicateRecipe *RepR : WorkList) {
344 VPBasicBlock *CurrentBlock = RepR->getParent();
345 VPBasicBlock *SplitBlock = CurrentBlock->splitAt(RepR->getIterator());
346
347 BasicBlock *OrigBB = RepR->getUnderlyingInstr()->getParent();
349 OrigBB->hasName() ? OrigBB->getName() + "." + Twine(BBNum++) : "");
350 // Record predicated instructions for above packing optimizations.
352 Region->setParent(CurrentBlock->getParent());
354 VPBlockUtils::connectBlocks(CurrentBlock, Region);
356 }
357}
358
359/// Remove redundant VPBasicBlocks by merging them into their predecessor if
360/// the predecessor has a single successor.
363 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
364 vp_depth_first_deep(Plan.getEntry()))) {
365 auto *PredVPBB =
366 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
367 if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
368 WorkList.push_back(VPBB);
369 }
370
371 for (VPBasicBlock *VPBB : WorkList) {
372 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
373 for (VPRecipeBase &R : make_early_inc_range(*VPBB))
374 R.moveBefore(*PredVPBB, PredVPBB->end());
375 VPBlockUtils::disconnectBlocks(PredVPBB, VPBB);
376 auto *ParentRegion = cast_or_null<VPRegionBlock>(VPBB->getParent());
377 if (ParentRegion && ParentRegion->getExiting() == VPBB)
378 ParentRegion->setExiting(PredVPBB);
379 for (auto *Succ : to_vector(VPBB->successors())) {
381 VPBlockUtils::connectBlocks(PredVPBB, Succ);
382 }
383 delete VPBB;
384 }
385 return !WorkList.empty();
386}
387
389 // Convert masked VPReplicateRecipes to if-then region blocks.
391
392 bool ShouldSimplify = true;
393 while (ShouldSimplify) {
394 ShouldSimplify = sinkScalarOperands(Plan);
395 ShouldSimplify |= mergeReplicateRegionsIntoSuccessors(Plan);
396 ShouldSimplify |= mergeBlocksIntoPredecessors(Plan);
397 }
398}
399
400/// Remove redundant casts of inductions.
401///
402/// Such redundant casts are casts of induction variables that can be ignored,
403/// because we already proved that the casted phi is equal to the uncasted phi
404/// in the vectorized loop. There is no need to vectorize the cast - the same
405/// value can be used for both the phi and casts in the vector loop.
407 for (auto &Phi : Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
408 auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
409 if (!IV || IV->getTruncInst())
410 continue;
411
412 // A sequence of IR Casts has potentially been recorded for IV, which
413 // *must be bypassed* when the IV is vectorized, because the vectorized IV
414 // will produce the desired casted value. This sequence forms a def-use
415 // chain and is provided in reverse order, ending with the cast that uses
416 // the IV phi. Search for the recipe of the last cast in the chain and
417 // replace it with the original IV. Note that only the final cast is
418 // expected to have users outside the cast-chain and the dead casts left
419 // over will be cleaned up later.
420 auto &Casts = IV->getInductionDescriptor().getCastInsts();
421 VPValue *FindMyCast = IV;
422 for (Instruction *IRCast : reverse(Casts)) {
423 VPSingleDefRecipe *FoundUserCast = nullptr;
424 for (auto *U : FindMyCast->users()) {
425 auto *UserCast = dyn_cast<VPSingleDefRecipe>(U);
426 if (UserCast && UserCast->getUnderlyingValue() == IRCast) {
427 FoundUserCast = UserCast;
428 break;
429 }
430 }
431 FindMyCast = FoundUserCast;
432 }
433 FindMyCast->replaceAllUsesWith(IV);
434 }
435}
436
437/// Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV
438/// recipe, if it exists.
440 VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
441 VPWidenCanonicalIVRecipe *WidenNewIV = nullptr;
442 for (VPUser *U : CanonicalIV->users()) {
443 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
444 if (WidenNewIV)
445 break;
446 }
447
448 if (!WidenNewIV)
449 return;
450
452 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
453 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
454
455 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical())
456 continue;
457
458 // Replace WidenNewIV with WidenOriginalIV if WidenOriginalIV provides
459 // everything WidenNewIV's users need. That is, WidenOriginalIV will
460 // generate a vector phi or all users of WidenNewIV demand the first lane
461 // only.
462 if (any_of(WidenOriginalIV->users(),
463 [WidenOriginalIV](VPUser *U) {
464 return !U->usesScalars(WidenOriginalIV);
465 }) ||
466 vputils::onlyFirstLaneUsed(WidenNewIV)) {
467 WidenNewIV->replaceAllUsesWith(WidenOriginalIV);
468 WidenNewIV->eraseFromParent();
469 return;
470 }
471 }
472}
473
474/// Returns true if \p R is dead and can be removed.
475static bool isDeadRecipe(VPRecipeBase &R) {
476 using namespace llvm::PatternMatch;
477 // Do remove conditional assume instructions as their conditions may be
478 // flattened.
479 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);
480 bool IsConditionalAssume =
481 RepR && RepR->isPredicated() &&
482 match(RepR->getUnderlyingInstr(), m_Intrinsic<Intrinsic::assume>());
483 if (IsConditionalAssume)
484 return true;
485
486 if (R.mayHaveSideEffects())
487 return false;
488
489 // Recipe is dead if no user keeps the recipe alive.
490 return all_of(R.definedValues(),
491 [](VPValue *V) { return V->getNumUsers() == 0; });
492}
493
494static void removeDeadRecipes(VPlan &Plan) {
496 Plan.getEntry());
497
498 for (VPBasicBlock *VPBB : reverse(VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT))) {
499 // The recipes in the block are processed in reverse order, to catch chains
500 // of dead recipes.
501 for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) {
502 if (isDeadRecipe(R))
503 R.eraseFromParent();
504 }
505 }
506}
507
510 Instruction::BinaryOps InductionOpcode,
511 FPMathOperator *FPBinOp, ScalarEvolution &SE,
512 Instruction *TruncI, VPValue *StartV, VPValue *Step,
515 VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
516 VPSingleDefRecipe *BaseIV = CanonicalIV;
517 if (!CanonicalIV->isCanonical(Kind, StartV, Step)) {
518 BaseIV = new VPDerivedIVRecipe(Kind, FPBinOp, StartV, CanonicalIV, Step);
519 HeaderVPBB->insert(BaseIV, IP);
520 }
521
522 // Truncate base induction if needed.
524 SE.getContext());
525 Type *ResultTy = TypeInfo.inferScalarType(BaseIV);
526 if (TruncI) {
527 Type *TruncTy = TruncI->getType();
528 assert(ResultTy->getScalarSizeInBits() > TruncTy->getScalarSizeInBits() &&
529 "Not truncating.");
530 assert(ResultTy->isIntegerTy() && "Truncation requires an integer type");
531 BaseIV = new VPScalarCastRecipe(Instruction::Trunc, BaseIV, TruncTy);
532 HeaderVPBB->insert(BaseIV, IP);
533 ResultTy = TruncTy;
534 }
535
536 // Truncate step if needed.
537 Type *StepTy = TypeInfo.inferScalarType(Step);
538 if (ResultTy != StepTy) {
539 assert(StepTy->getScalarSizeInBits() > ResultTy->getScalarSizeInBits() &&
540 "Not truncating.");
541 assert(StepTy->isIntegerTy() && "Truncation requires an integer type");
542 Step = new VPScalarCastRecipe(Instruction::Trunc, Step, ResultTy);
543 auto *VecPreheader =
544 cast<VPBasicBlock>(HeaderVPBB->getSingleHierarchicalPredecessor());
545 VecPreheader->appendRecipe(Step->getDefiningRecipe());
546 }
547
549 BaseIV, Step, InductionOpcode,
550 FPBinOp ? FPBinOp->getFastMathFlags() : FastMathFlags());
551 HeaderVPBB->insert(Steps, IP);
552 return Steps;
553}
554
555/// Legalize VPWidenPointerInductionRecipe, by replacing it with a PtrAdd
556/// (IndStart, ScalarIVSteps (0, Step)) if only its scalar values are used, as
557/// VPWidenPointerInductionRecipe will generate vectors only. If some users
558/// require vectors while other require scalars, the scalar uses need to extract
559/// the scalars from the generated vectors (Note that this is different to how
560/// int/fp inductions are handled). Also optimize VPWidenIntOrFpInductionRecipe,
561/// if any of its users needs scalar values, by providing them scalar steps
562/// built on the canonical scalar IV and update the original IV's users. This is
563/// an optional optimization to reduce the needs of vector extracts.
567 bool HasOnlyVectorVFs = !Plan.hasVF(ElementCount::getFixed(1));
568 VPBasicBlock::iterator InsertPt = HeaderVPBB->getFirstNonPhi();
569 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
570 // Replace wide pointer inductions which have only their scalars used by
571 // PtrAdd(IndStart, ScalarIVSteps (0, Step)).
572 if (auto *PtrIV = dyn_cast<VPWidenPointerInductionRecipe>(&Phi)) {
573 if (!PtrIV->onlyScalarsGenerated(Plan.hasScalableVF()))
574 continue;
575
576 const InductionDescriptor &ID = PtrIV->getInductionDescriptor();
577 VPValue *StartV =
578 Plan.getOrAddLiveIn(ConstantInt::get(ID.getStep()->getType(), 0));
579 VPValue *StepV = PtrIV->getOperand(1);
581 Plan, InductionDescriptor::IK_IntInduction, Instruction::Add, nullptr,
582 SE, nullptr, StartV, StepV, InsertPt);
583
584 auto *Recipe = new VPInstruction(VPInstruction::PtrAdd,
585 {PtrIV->getStartValue(), Steps},
586 PtrIV->getDebugLoc(), "next.gep");
587
588 Recipe->insertAfter(Steps);
589 PtrIV->replaceAllUsesWith(Recipe);
590 continue;
591 }
592
593 // Replace widened induction with scalar steps for users that only use
594 // scalars.
595 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
596 if (!WideIV)
597 continue;
598 if (HasOnlyVectorVFs && none_of(WideIV->users(), [WideIV](VPUser *U) {
599 return U->usesScalars(WideIV);
600 }))
601 continue;
602
603 const InductionDescriptor &ID = WideIV->getInductionDescriptor();
605 Plan, ID.getKind(), ID.getInductionOpcode(),
606 dyn_cast_or_null<FPMathOperator>(ID.getInductionBinOp()), SE,
607 WideIV->getTruncInst(), WideIV->getStartValue(), WideIV->getStepValue(),
608 InsertPt);
609
610 // Update scalar users of IV to use Step instead.
611 if (!HasOnlyVectorVFs)
612 WideIV->replaceAllUsesWith(Steps);
613 else
614 WideIV->replaceUsesWithIf(Steps, [WideIV](VPUser &U, unsigned) {
615 return U.usesScalars(WideIV);
616 });
617 }
618}
619
620/// Remove redundant EpxandSCEVRecipes in \p Plan's entry block by replacing
621/// them with already existing recipes expanding the same SCEV expression.
624
625 for (VPRecipeBase &R :
627 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
628 if (!ExpR)
629 continue;
630
631 auto I = SCEV2VPV.insert({ExpR->getSCEV(), ExpR});
632 if (I.second)
633 continue;
634 ExpR->replaceAllUsesWith(I.first->second);
635 ExpR->eraseFromParent();
636 }
637}
638
640 SmallVector<VPValue *> WorkList;
642 WorkList.push_back(V);
643
644 while (!WorkList.empty()) {
645 VPValue *Cur = WorkList.pop_back_val();
646 if (!Seen.insert(Cur).second)
647 continue;
649 if (!R)
650 continue;
651 if (!isDeadRecipe(*R))
652 continue;
653 WorkList.append(R->op_begin(), R->op_end());
654 R->eraseFromParent();
655 }
656}
657
659 unsigned BestUF,
661 assert(Plan.hasVF(BestVF) && "BestVF is not available in Plan");
662 assert(Plan.hasUF(BestUF) && "BestUF is not available in Plan");
663 VPBasicBlock *ExitingVPBB =
665 auto *Term = &ExitingVPBB->back();
666 // Try to simplify the branch condition if TC <= VF * UF when preparing to
667 // execute the plan for the main vector loop. We only do this if the
668 // terminator is:
669 // 1. BranchOnCount, or
670 // 2. BranchOnCond where the input is Not(ActiveLaneMask).
671 using namespace llvm::VPlanPatternMatch;
672 if (!match(Term, m_BranchOnCount(m_VPValue(), m_VPValue())) &&
673 !match(Term,
674 m_BranchOnCond(m_Not(m_ActiveLaneMask(m_VPValue(), m_VPValue())))))
675 return;
676
677 Type *IdxTy =
679 const SCEV *TripCount = createTripCountSCEV(IdxTy, PSE);
680 ScalarEvolution &SE = *PSE.getSE();
681 ElementCount NumElements = BestVF.multiplyCoefficientBy(BestUF);
682 const SCEV *C = SE.getElementCount(TripCount->getType(), NumElements);
683 if (TripCount->isZero() ||
684 !SE.isKnownPredicate(CmpInst::ICMP_ULE, TripCount, C))
685 return;
686
687 LLVMContext &Ctx = SE.getContext();
688 auto *BOC =
691
692 SmallVector<VPValue *> PossiblyDead(Term->operands());
693 Term->eraseFromParent();
694 for (VPValue *Op : PossiblyDead)
696 ExitingVPBB->appendRecipe(BOC);
697 Plan.setVF(BestVF);
698 Plan.setUF(BestUF);
699 // TODO: Further simplifications are possible
700 // 1. Replace inductions with constants.
701 // 2. Replace vector loop region with VPBasicBlock.
702}
703
704#ifndef NDEBUG
706 auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
707 if (Region && Region->isReplicator()) {
708 assert(Region->getNumSuccessors() == 1 &&
709 Region->getNumPredecessors() == 1 && "Expected SESE region!");
710 assert(R->getParent()->size() == 1 &&
711 "A recipe in an original replicator region must be the only "
712 "recipe in its block");
713 return Region;
714 }
715 return nullptr;
716}
717#endif
718
719static bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B,
720 VPDominatorTree &VPDT) {
721 if (A == B)
722 return false;
723
724 auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {
725 for (auto &R : *A->getParent()) {
726 if (&R == A)
727 return true;
728 if (&R == B)
729 return false;
730 }
731 llvm_unreachable("recipe not found");
732 };
733 const VPBlockBase *ParentA = A->getParent();
734 const VPBlockBase *ParentB = B->getParent();
735 if (ParentA == ParentB)
736 return LocalComesBefore(A, B);
737
738 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(A)) &&
739 "No replicate regions expected at this point");
740 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(B)) &&
741 "No replicate regions expected at this point");
742 return VPDT.properlyDominates(ParentA, ParentB);
743}
744
745/// Sink users of \p FOR after the recipe defining the previous value \p
746/// Previous of the recurrence. \returns true if all users of \p FOR could be
747/// re-arranged as needed or false if it is not possible.
748static bool
750 VPRecipeBase *Previous,
751 VPDominatorTree &VPDT) {
752 // Collect recipes that need sinking.
755 Seen.insert(Previous);
756 auto TryToPushSinkCandidate = [&](VPRecipeBase *SinkCandidate) {
757 // The previous value must not depend on the users of the recurrence phi. In
758 // that case, FOR is not a fixed order recurrence.
759 if (SinkCandidate == Previous)
760 return false;
761
762 if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||
763 !Seen.insert(SinkCandidate).second ||
764 properlyDominates(Previous, SinkCandidate, VPDT))
765 return true;
766
767 if (SinkCandidate->mayHaveSideEffects())
768 return false;
769
770 WorkList.push_back(SinkCandidate);
771 return true;
772 };
773
774 // Recursively sink users of FOR after Previous.
775 WorkList.push_back(FOR);
776 for (unsigned I = 0; I != WorkList.size(); ++I) {
777 VPRecipeBase *Current = WorkList[I];
778 assert(Current->getNumDefinedValues() == 1 &&
779 "only recipes with a single defined value expected");
780
781 for (VPUser *User : Current->getVPSingleValue()->users()) {
782 if (auto *R = dyn_cast<VPRecipeBase>(User))
783 if (!TryToPushSinkCandidate(R))
784 return false;
785 }
786 }
787
788 // Keep recipes to sink ordered by dominance so earlier instructions are
789 // processed first.
790 sort(WorkList, [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
791 return properlyDominates(A, B, VPDT);
792 });
793
794 for (VPRecipeBase *SinkCandidate : WorkList) {
795 if (SinkCandidate == FOR)
796 continue;
797
798 SinkCandidate->moveAfter(Previous);
799 Previous = SinkCandidate;
800 }
801 return true;
802}
803
805 VPBuilder &LoopBuilder) {
806 VPDominatorTree VPDT;
807 VPDT.recalculate(Plan);
808
810 for (VPRecipeBase &R :
812 if (auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R))
813 RecurrencePhis.push_back(FOR);
814
815 VPBuilder MiddleBuilder(
816 cast<VPBasicBlock>(Plan.getVectorLoopRegion()->getSingleSuccessor()));
817 for (VPFirstOrderRecurrencePHIRecipe *FOR : RecurrencePhis) {
819 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
820 // Fixed-order recurrences do not contain cycles, so this loop is guaranteed
821 // to terminate.
822 while (auto *PrevPhi =
823 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {
824 assert(PrevPhi->getParent() == FOR->getParent());
825 assert(SeenPhis.insert(PrevPhi).second);
826 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
827 }
828
829 if (!sinkRecurrenceUsersAfterPrevious(FOR, Previous, VPDT))
830 return false;
831
832 // Introduce a recipe to combine the incoming and previous values of a
833 // fixed-order recurrence.
834 VPBasicBlock *InsertBlock = Previous->getParent();
835 if (isa<VPHeaderPHIRecipe>(Previous))
836 LoopBuilder.setInsertPoint(InsertBlock, InsertBlock->getFirstNonPhi());
837 else
838 LoopBuilder.setInsertPoint(InsertBlock,
839 std::next(Previous->getIterator()));
840
841 auto *RecurSplice = cast<VPInstruction>(
843 {FOR, FOR->getBackedgeValue()}));
844
845 FOR->replaceAllUsesWith(RecurSplice);
846 // Set the first operand of RecurSplice to FOR again, after replacing
847 // all users.
848 RecurSplice->setOperand(0, FOR);
849
850 // This is the second phase of vectorizing first-order recurrences. An
851 // overview of the transformation is described below. Suppose we have the
852 // following loop with some use after the loop of the last a[i-1],
853 //
854 // for (int i = 0; i < n; ++i) {
855 // t = a[i - 1];
856 // b[i] = a[i] - t;
857 // }
858 // use t;
859 //
860 // There is a first-order recurrence on "a". For this loop, the shorthand
861 // scalar IR looks like:
862 //
863 // scalar.ph:
864 // s_init = a[-1]
865 // br scalar.body
866 //
867 // scalar.body:
868 // i = phi [0, scalar.ph], [i+1, scalar.body]
869 // s1 = phi [s_init, scalar.ph], [s2, scalar.body]
870 // s2 = a[i]
871 // b[i] = s2 - s1
872 // br cond, scalar.body, exit.block
873 //
874 // exit.block:
875 // use = lcssa.phi [s1, scalar.body]
876 //
877 // In this example, s1 is a recurrence because it's value depends on the
878 // previous iteration. In the first phase of vectorization, we created a
879 // vector phi v1 for s1. We now complete the vectorization and produce the
880 // shorthand vector IR shown below (for VF = 4, UF = 1).
881 //
882 // vector.ph:
883 // v_init = vector(..., ..., ..., a[-1])
884 // br vector.body
885 //
886 // vector.body
887 // i = phi [0, vector.ph], [i+4, vector.body]
888 // v1 = phi [v_init, vector.ph], [v2, vector.body]
889 // v2 = a[i, i+1, i+2, i+3];
890 // v3 = vector(v1(3), v2(0, 1, 2))
891 // b[i, i+1, i+2, i+3] = v2 - v3
892 // br cond, vector.body, middle.block
893 //
894 // middle.block:
895 // s_penultimate = v2(2) = v3(3)
896 // s_resume = v2(3)
897 // br cond, scalar.ph, exit.block
898 //
899 // scalar.ph:
900 // s_init' = phi [s_resume, middle.block], [s_init, otherwise]
901 // br scalar.body
902 //
903 // scalar.body:
904 // i = phi [0, scalar.ph], [i+1, scalar.body]
905 // s1 = phi [s_init', scalar.ph], [s2, scalar.body]
906 // s2 = a[i]
907 // b[i] = s2 - s1
908 // br cond, scalar.body, exit.block
909 //
910 // exit.block:
911 // lo = lcssa.phi [s1, scalar.body], [s.penultimate, middle.block]
912 //
913 // After execution completes the vector loop, we extract the next value of
914 // the recurrence (x) to use as the initial value in the scalar loop. This
915 // is modeled by ExtractFromEnd.
916 Type *IntTy = Plan.getCanonicalIV()->getScalarType();
917
918 // Extract the penultimate value of the recurrence and update VPLiveOut
919 // users of the recurrence splice.
920 auto *Penultimate = cast<VPInstruction>(MiddleBuilder.createNaryOp(
922 {FOR->getBackedgeValue(),
923 Plan.getOrAddLiveIn(ConstantInt::get(IntTy, 2))},
924 {}, "vector.recur.extract.for.phi"));
925 RecurSplice->replaceUsesWithIf(
926 Penultimate, [](VPUser &U, unsigned) { return isa<VPLiveOut>(&U); });
927
928 // Extract the resume value and create a new VPLiveOut for it.
929 auto *Resume = MiddleBuilder.createNaryOp(
931 {FOR->getBackedgeValue(),
932 Plan.getOrAddLiveIn(ConstantInt::get(IntTy, 1))},
933 {}, "vector.recur.extract");
934 Plan.addLiveOut(cast<PHINode>(FOR->getUnderlyingInstr()), Resume);
935 }
936 return true;
937}
938
940 SetVector<VPUser *> Users(V->user_begin(), V->user_end());
941 for (unsigned I = 0; I != Users.size(); ++I) {
942 VPRecipeBase *Cur = dyn_cast<VPRecipeBase>(Users[I]);
943 if (!Cur || isa<VPHeaderPHIRecipe>(Cur))
944 continue;
945 for (VPValue *V : Cur->definedValues())
946 Users.insert(V->user_begin(), V->user_end());
947 }
948 return Users.takeVector();
949}
950
952 for (VPRecipeBase &R :
954 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(&R);
955 if (!PhiR)
956 continue;
957 const RecurrenceDescriptor &RdxDesc = PhiR->getRecurrenceDescriptor();
958 RecurKind RK = RdxDesc.getRecurrenceKind();
959 if (RK != RecurKind::Add && RK != RecurKind::Mul)
960 continue;
961
962 for (VPUser *U : collectUsersRecursively(PhiR))
963 if (auto *RecWithFlags = dyn_cast<VPRecipeWithIRFlags>(U)) {
964 RecWithFlags->dropPoisonGeneratingFlags();
965 }
966 }
967}
968
969/// Try to simplify recipe \p R.
970static void simplifyRecipe(VPRecipeBase &R, VPTypeAnalysis &TypeInfo) {
971 using namespace llvm::VPlanPatternMatch;
972 // Try to remove redundant blend recipes.
973 if (auto *Blend = dyn_cast<VPBlendRecipe>(&R)) {
974 VPValue *Inc0 = Blend->getIncomingValue(0);
975 for (unsigned I = 1; I != Blend->getNumIncomingValues(); ++I)
976 if (Inc0 != Blend->getIncomingValue(I) &&
977 !match(Blend->getMask(I), m_False()))
978 return;
979 Blend->replaceAllUsesWith(Inc0);
980 Blend->eraseFromParent();
981 return;
982 }
983
984 VPValue *A;
985 if (match(&R, m_Trunc(m_ZExtOrSExt(m_VPValue(A))))) {
986 VPValue *Trunc = R.getVPSingleValue();
987 Type *TruncTy = TypeInfo.inferScalarType(Trunc);
988 Type *ATy = TypeInfo.inferScalarType(A);
989 if (TruncTy == ATy) {
990 Trunc->replaceAllUsesWith(A);
991 } else {
992 // Don't replace a scalarizing recipe with a widened cast.
993 if (isa<VPReplicateRecipe>(&R))
994 return;
995 if (ATy->getScalarSizeInBits() < TruncTy->getScalarSizeInBits()) {
996
997 unsigned ExtOpcode = match(R.getOperand(0), m_SExt(m_VPValue()))
998 ? Instruction::SExt
999 : Instruction::ZExt;
1000 auto *VPC =
1001 new VPWidenCastRecipe(Instruction::CastOps(ExtOpcode), A, TruncTy);
1002 if (auto *UnderlyingExt = R.getOperand(0)->getUnderlyingValue()) {
1003 // UnderlyingExt has distinct return type, used to retain legacy cost.
1004 VPC->setUnderlyingValue(UnderlyingExt);
1005 }
1006 VPC->insertBefore(&R);
1007 Trunc->replaceAllUsesWith(VPC);
1008 } else if (ATy->getScalarSizeInBits() > TruncTy->getScalarSizeInBits()) {
1009 auto *VPC = new VPWidenCastRecipe(Instruction::Trunc, A, TruncTy);
1010 VPC->insertBefore(&R);
1011 Trunc->replaceAllUsesWith(VPC);
1012 }
1013 }
1014#ifndef NDEBUG
1015 // Verify that the cached type info is for both A and its users is still
1016 // accurate by comparing it to freshly computed types.
1017 VPTypeAnalysis TypeInfo2(
1018 R.getParent()->getPlan()->getCanonicalIV()->getScalarType(),
1019 TypeInfo.getContext());
1020 assert(TypeInfo.inferScalarType(A) == TypeInfo2.inferScalarType(A));
1021 for (VPUser *U : A->users()) {
1022 auto *R = dyn_cast<VPRecipeBase>(U);
1023 if (!R)
1024 continue;
1025 for (VPValue *VPV : R->definedValues())
1026 assert(TypeInfo.inferScalarType(VPV) == TypeInfo2.inferScalarType(VPV));
1027 }
1028#endif
1029 }
1030
1031 // Simplify (X && Y) || (X && !Y) -> X.
1032 // TODO: Split up into simpler, modular combines: (X && Y) || (X && Z) into X
1033 // && (Y || Z) and (X || !X) into true. This requires queuing newly created
1034 // recipes to be visited during simplification.
1035 VPValue *X, *Y, *X1, *Y1;
1036 if (match(&R,
1037 m_c_BinaryOr(m_LogicalAnd(m_VPValue(X), m_VPValue(Y)),
1038 m_LogicalAnd(m_VPValue(X1), m_Not(m_VPValue(Y1))))) &&
1039 X == X1 && Y == Y1) {
1040 R.getVPSingleValue()->replaceAllUsesWith(X);
1041 return;
1042 }
1043
1044 if (match(&R, m_c_Mul(m_VPValue(A), m_SpecificInt(1))))
1045 return R.getVPSingleValue()->replaceAllUsesWith(A);
1046}
1047
1048/// Try to simplify the recipes in \p Plan.
1049static void simplifyRecipes(VPlan &Plan, LLVMContext &Ctx) {
1051 Plan.getEntry());
1052 VPTypeAnalysis TypeInfo(Plan.getCanonicalIV()->getScalarType(), Ctx);
1053 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
1054 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
1055 simplifyRecipe(R, TypeInfo);
1056 }
1057 }
1058}
1059
1061 VPlan &Plan, const MapVector<Instruction *, uint64_t> &MinBWs,
1062 LLVMContext &Ctx) {
1063#ifndef NDEBUG
1064 // Count the processed recipes and cross check the count later with MinBWs
1065 // size, to make sure all entries in MinBWs have been handled.
1066 unsigned NumProcessedRecipes = 0;
1067#endif
1068 // Keep track of created truncates, so they can be re-used. Note that we
1069 // cannot use RAUW after creating a new truncate, as this would could make
1070 // other uses have different types for their operands, making them invalidly
1071 // typed.
1073 VPTypeAnalysis TypeInfo(Plan.getCanonicalIV()->getScalarType(), Ctx);
1074 VPBasicBlock *PH = Plan.getEntry();
1075 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
1077 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
1080 continue;
1081
1082 VPValue *ResultVPV = R.getVPSingleValue();
1083 auto *UI = cast_or_null<Instruction>(ResultVPV->getUnderlyingValue());
1084 unsigned NewResSizeInBits = MinBWs.lookup(UI);
1085 if (!NewResSizeInBits)
1086 continue;
1087
1088#ifndef NDEBUG
1089 NumProcessedRecipes++;
1090#endif
1091 // If the value wasn't vectorized, we must maintain the original scalar
1092 // type. Skip those here, after incrementing NumProcessedRecipes. Also
1093 // skip casts which do not need to be handled explicitly here, as
1094 // redundant casts will be removed during recipe simplification.
1095 if (isa<VPReplicateRecipe, VPWidenCastRecipe>(&R)) {
1096#ifndef NDEBUG
1097 // If any of the operands is a live-in and not used by VPWidenRecipe or
1098 // VPWidenSelectRecipe, but in MinBWs, make sure it is counted as
1099 // processed as well. When MinBWs is currently constructed, there is no
1100 // information about whether recipes are widened or replicated and in
1101 // case they are reciplicated the operands are not truncated. Counting
1102 // them them here ensures we do not miss any recipes in MinBWs.
1103 // TODO: Remove once the analysis is done on VPlan.
1104 for (VPValue *Op : R.operands()) {
1105 if (!Op->isLiveIn())
1106 continue;
1107 auto *UV = dyn_cast_or_null<Instruction>(Op->getUnderlyingValue());
1108 if (UV && MinBWs.contains(UV) && !ProcessedTruncs.contains(Op) &&
1109 all_of(Op->users(), [](VPUser *U) {
1110 return !isa<VPWidenRecipe, VPWidenSelectRecipe>(U);
1111 })) {
1112 // Add an entry to ProcessedTruncs to avoid counting the same
1113 // operand multiple times.
1114 ProcessedTruncs[Op] = nullptr;
1115 NumProcessedRecipes += 1;
1116 }
1117 }
1118#endif
1119 continue;
1120 }
1121
1122 Type *OldResTy = TypeInfo.inferScalarType(ResultVPV);
1123 unsigned OldResSizeInBits = OldResTy->getScalarSizeInBits();
1124 assert(OldResTy->isIntegerTy() && "only integer types supported");
1125 (void)OldResSizeInBits;
1126
1127 auto *NewResTy = IntegerType::get(Ctx, NewResSizeInBits);
1128
1129 // Any wrapping introduced by shrinking this operation shouldn't be
1130 // considered undefined behavior. So, we can't unconditionally copy
1131 // arithmetic wrapping flags to VPW.
1132 if (auto *VPW = dyn_cast<VPRecipeWithIRFlags>(&R))
1133 VPW->dropPoisonGeneratingFlags();
1134
1135 using namespace llvm::VPlanPatternMatch;
1136 if (OldResSizeInBits != NewResSizeInBits &&
1137 !match(&R, m_Binary<Instruction::ICmp>(m_VPValue(), m_VPValue()))) {
1138 // Extend result to original width.
1139 auto *Ext =
1140 new VPWidenCastRecipe(Instruction::ZExt, ResultVPV, OldResTy);
1141 Ext->insertAfter(&R);
1142 ResultVPV->replaceAllUsesWith(Ext);
1143 Ext->setOperand(0, ResultVPV);
1144 assert(OldResSizeInBits > NewResSizeInBits && "Nothing to shrink?");
1145 } else
1146 assert(
1147 match(&R, m_Binary<Instruction::ICmp>(m_VPValue(), m_VPValue())) &&
1148 "Only ICmps should not need extending the result.");
1149
1150 assert(!isa<VPWidenStoreRecipe>(&R) && "stores cannot be narrowed");
1151 if (isa<VPWidenLoadRecipe>(&R))
1152 continue;
1153
1154 // Shrink operands by introducing truncates as needed.
1155 unsigned StartIdx = isa<VPWidenSelectRecipe>(&R) ? 1 : 0;
1156 for (unsigned Idx = StartIdx; Idx != R.getNumOperands(); ++Idx) {
1157 auto *Op = R.getOperand(Idx);
1158 unsigned OpSizeInBits =
1160 if (OpSizeInBits == NewResSizeInBits)
1161 continue;
1162 assert(OpSizeInBits > NewResSizeInBits && "nothing to truncate");
1163 auto [ProcessedIter, IterIsEmpty] =
1164 ProcessedTruncs.insert({Op, nullptr});
1165 VPWidenCastRecipe *NewOp =
1166 IterIsEmpty
1167 ? new VPWidenCastRecipe(Instruction::Trunc, Op, NewResTy)
1168 : ProcessedIter->second;
1169 R.setOperand(Idx, NewOp);
1170 if (!IterIsEmpty)
1171 continue;
1172 ProcessedIter->second = NewOp;
1173 if (!Op->isLiveIn()) {
1174 NewOp->insertBefore(&R);
1175 } else {
1176 PH->appendRecipe(NewOp);
1177#ifndef NDEBUG
1178 auto *OpInst = dyn_cast<Instruction>(Op->getLiveInIRValue());
1179 bool IsContained = MinBWs.contains(OpInst);
1180 NumProcessedRecipes += IsContained;
1181#endif
1182 }
1183 }
1184
1185 }
1186 }
1187
1188 assert(MinBWs.size() == NumProcessedRecipes &&
1189 "some entries in MinBWs haven't been processed");
1190}
1191
1195
1196 simplifyRecipes(Plan, SE.getContext());
1198 removeDeadRecipes(Plan);
1199
1201
1204}
1205
1206// Add a VPActiveLaneMaskPHIRecipe and related recipes to \p Plan and replace
1207// the loop terminator with a branch-on-cond recipe with the negated
1208// active-lane-mask as operand. Note that this turns the loop into an
1209// uncountable one. Only the existing terminator is replaced, all other existing
1210// recipes/users remain unchanged, except for poison-generating flags being
1211// dropped from the canonical IV increment. Return the created
1212// VPActiveLaneMaskPHIRecipe.
1213//
1214// The function uses the following definitions:
1215//
1216// %TripCount = DataWithControlFlowWithoutRuntimeCheck ?
1217// calculate-trip-count-minus-VF (original TC) : original TC
1218// %IncrementValue = DataWithControlFlowWithoutRuntimeCheck ?
1219// CanonicalIVPhi : CanonicalIVIncrement
1220// %StartV is the canonical induction start value.
1221//
1222// The function adds the following recipes:
1223//
1224// vector.ph:
1225// %TripCount = calculate-trip-count-minus-VF (original TC)
1226// [if DataWithControlFlowWithoutRuntimeCheck]
1227// %EntryInc = canonical-iv-increment-for-part %StartV
1228// %EntryALM = active-lane-mask %EntryInc, %TripCount
1229//
1230// vector.body:
1231// ...
1232// %P = active-lane-mask-phi [ %EntryALM, %vector.ph ], [ %ALM, %vector.body ]
1233// ...
1234// %InLoopInc = canonical-iv-increment-for-part %IncrementValue
1235// %ALM = active-lane-mask %InLoopInc, TripCount
1236// %Negated = Not %ALM
1237// branch-on-cond %Negated
1238//
1241 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
1242 VPBasicBlock *EB = TopRegion->getExitingBasicBlock();
1243 auto *CanonicalIVPHI = Plan.getCanonicalIV();
1244 VPValue *StartV = CanonicalIVPHI->getStartValue();
1245
1246 auto *CanonicalIVIncrement =
1247 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());
1248 // TODO: Check if dropping the flags is needed if
1249 // !DataAndControlFlowWithoutRuntimeCheck.
1250 CanonicalIVIncrement->dropPoisonGeneratingFlags();
1251 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
1252 // We can't use StartV directly in the ActiveLaneMask VPInstruction, since
1253 // we have to take unrolling into account. Each part needs to start at
1254 // Part * VF
1255 auto *VecPreheader = cast<VPBasicBlock>(TopRegion->getSinglePredecessor());
1256 VPBuilder Builder(VecPreheader);
1257
1258 // Create the ActiveLaneMask instruction using the correct start values.
1259 VPValue *TC = Plan.getTripCount();
1260
1261 VPValue *TripCount, *IncrementValue;
1263 // When the loop is guarded by a runtime overflow check for the loop
1264 // induction variable increment by VF, we can increment the value before
1265 // the get.active.lane mask and use the unmodified tripcount.
1266 IncrementValue = CanonicalIVIncrement;
1267 TripCount = TC;
1268 } else {
1269 // When avoiding a runtime check, the active.lane.mask inside the loop
1270 // uses a modified trip count and the induction variable increment is
1271 // done after the active.lane.mask intrinsic is called.
1272 IncrementValue = CanonicalIVPHI;
1274 {TC}, DL);
1275 }
1276 auto *EntryIncrement = Builder.createOverflowingOp(
1277 VPInstruction::CanonicalIVIncrementForPart, {StartV}, {false, false}, DL,
1278 "index.part.next");
1279
1280 // Create the active lane mask instruction in the VPlan preheader.
1281 auto *EntryALM =
1282 Builder.createNaryOp(VPInstruction::ActiveLaneMask, {EntryIncrement, TC},
1283 DL, "active.lane.mask.entry");
1284
1285 // Now create the ActiveLaneMaskPhi recipe in the main loop using the
1286 // preheader ActiveLaneMask instruction.
1287 auto LaneMaskPhi = new VPActiveLaneMaskPHIRecipe(EntryALM, DebugLoc());
1288 LaneMaskPhi->insertAfter(CanonicalIVPHI);
1289
1290 // Create the active lane mask for the next iteration of the loop before the
1291 // original terminator.
1292 VPRecipeBase *OriginalTerminator = EB->getTerminator();
1293 Builder.setInsertPoint(OriginalTerminator);
1294 auto *InLoopIncrement =
1296 {IncrementValue}, {false, false}, DL);
1297 auto *ALM = Builder.createNaryOp(VPInstruction::ActiveLaneMask,
1298 {InLoopIncrement, TripCount}, DL,
1299 "active.lane.mask.next");
1300 LaneMaskPhi->addOperand(ALM);
1301
1302 // Replace the original terminator with BranchOnCond. We have to invert the
1303 // mask here because a true condition means jumping to the exit block.
1304 auto *NotMask = Builder.createNot(ALM, DL);
1305 Builder.createNaryOp(VPInstruction::BranchOnCond, {NotMask}, DL);
1306 OriginalTerminator->eraseFromParent();
1307 return LaneMaskPhi;
1308}
1309
1310/// Collect all VPValues representing a header mask through the (ICMP_ULE,
1311/// WideCanonicalIV, backedge-taken-count) pattern.
1312/// TODO: Introduce explicit recipe for header-mask instead of searching
1313/// for the header-mask pattern manually.
1315 SmallVector<VPValue *> WideCanonicalIVs;
1316 auto *FoundWidenCanonicalIVUser =
1317 find_if(Plan.getCanonicalIV()->users(),
1318 [](VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); });
1320 [](VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); }) <=
1321 1 &&
1322 "Must have at most one VPWideCanonicalIVRecipe");
1323 if (FoundWidenCanonicalIVUser != Plan.getCanonicalIV()->users().end()) {
1324 auto *WideCanonicalIV =
1325 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);
1326 WideCanonicalIVs.push_back(WideCanonicalIV);
1327 }
1328
1329 // Also include VPWidenIntOrFpInductionRecipes that represent a widened
1330 // version of the canonical induction.
1331 VPBasicBlock *HeaderVPBB = Plan.getVectorLoopRegion()->getEntryBasicBlock();
1332 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
1333 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
1334 if (WidenOriginalIV && WidenOriginalIV->isCanonical())
1335 WideCanonicalIVs.push_back(WidenOriginalIV);
1336 }
1337
1338 // Walk users of wide canonical IVs and collect to all compares of the form
1339 // (ICMP_ULE, WideCanonicalIV, backedge-taken-count).
1340 SmallVector<VPValue *> HeaderMasks;
1342 for (auto *Wide : WideCanonicalIVs) {
1343 for (VPUser *U : SmallVector<VPUser *>(Wide->users())) {
1344 auto *HeaderMask = dyn_cast<VPInstruction>(U);
1345 if (!HeaderMask || HeaderMask->getOpcode() != Instruction::ICmp ||
1346 HeaderMask->getPredicate() != CmpInst::ICMP_ULE ||
1347 HeaderMask->getOperand(1) != BTC)
1348 continue;
1349
1350 assert(HeaderMask->getOperand(0) == Wide &&
1351 "WidenCanonicalIV must be the first operand of the compare");
1352 HeaderMasks.push_back(HeaderMask);
1353 }
1354 }
1355 return HeaderMasks;
1356}
1357
1359 VPlan &Plan, bool UseActiveLaneMaskForControlFlow,
1362 UseActiveLaneMaskForControlFlow) &&
1363 "DataAndControlFlowWithoutRuntimeCheck implies "
1364 "UseActiveLaneMaskForControlFlow");
1365
1366 auto FoundWidenCanonicalIVUser =
1367 find_if(Plan.getCanonicalIV()->users(),
1368 [](VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); });
1369 assert(FoundWidenCanonicalIVUser &&
1370 "Must have widened canonical IV when tail folding!");
1371 auto *WideCanonicalIV =
1372 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);
1373 VPSingleDefRecipe *LaneMask;
1374 if (UseActiveLaneMaskForControlFlow) {
1377 } else {
1378 VPBuilder B = VPBuilder::getToInsertAfter(WideCanonicalIV);
1379 LaneMask = B.createNaryOp(VPInstruction::ActiveLaneMask,
1380 {WideCanonicalIV, Plan.getTripCount()}, nullptr,
1381 "active.lane.mask");
1382 }
1383
1384 // Walk users of WideCanonicalIV and replace all compares of the form
1385 // (ICMP_ULE, WideCanonicalIV, backedge-taken-count) with an
1386 // active-lane-mask.
1387 for (VPValue *HeaderMask : collectAllHeaderMasks(Plan))
1388 HeaderMask->replaceAllUsesWith(LaneMask);
1389}
1390
1391/// Add a VPEVLBasedIVPHIRecipe and related recipes to \p Plan and
1392/// replaces all uses except the canonical IV increment of
1393/// VPCanonicalIVPHIRecipe with a VPEVLBasedIVPHIRecipe. VPCanonicalIVPHIRecipe
1394/// is used only for loop iterations counting after this transformation.
1395///
1396/// The function uses the following definitions:
1397/// %StartV is the canonical induction start value.
1398///
1399/// The function adds the following recipes:
1400///
1401/// vector.ph:
1402/// ...
1403///
1404/// vector.body:
1405/// ...
1406/// %EVLPhi = EXPLICIT-VECTOR-LENGTH-BASED-IV-PHI [ %StartV, %vector.ph ],
1407/// [ %NextEVLIV, %vector.body ]
1408/// %VPEVL = EXPLICIT-VECTOR-LENGTH %EVLPhi, original TC
1409/// ...
1410/// %NextEVLIV = add IVSize (cast i32 %VPEVVL to IVSize), %EVLPhi
1411/// ...
1412///
1415 // The transform updates all users of inductions to work based on EVL, instead
1416 // of the VF directly. At the moment, widened inductions cannot be updated, so
1417 // bail out if the plan contains any.
1418 if (any_of(Header->phis(), [](VPRecipeBase &Phi) {
1419 return (isa<VPWidenIntOrFpInductionRecipe>(&Phi) ||
1420 isa<VPWidenPointerInductionRecipe>(&Phi));
1421 }))
1422 return false;
1423 auto *CanonicalIVPHI = Plan.getCanonicalIV();
1424 VPValue *StartV = CanonicalIVPHI->getStartValue();
1425
1426 // Create the ExplicitVectorLengthPhi recipe in the main loop.
1427 auto *EVLPhi = new VPEVLBasedIVPHIRecipe(StartV, DebugLoc());
1428 EVLPhi->insertAfter(CanonicalIVPHI);
1430 {EVLPhi, Plan.getTripCount()});
1431 VPEVL->insertBefore(*Header, Header->getFirstNonPhi());
1432
1433 auto *CanonicalIVIncrement =
1434 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());
1435 VPSingleDefRecipe *OpVPEVL = VPEVL;
1436 if (unsigned IVSize = CanonicalIVPHI->getScalarType()->getScalarSizeInBits();
1437 IVSize != 32) {
1438 OpVPEVL = new VPScalarCastRecipe(IVSize < 32 ? Instruction::Trunc
1439 : Instruction::ZExt,
1440 OpVPEVL, CanonicalIVPHI->getScalarType());
1441 OpVPEVL->insertBefore(CanonicalIVIncrement);
1442 }
1443 auto *NextEVLIV =
1444 new VPInstruction(Instruction::Add, {OpVPEVL, EVLPhi},
1445 {CanonicalIVIncrement->hasNoUnsignedWrap(),
1446 CanonicalIVIncrement->hasNoSignedWrap()},
1447 CanonicalIVIncrement->getDebugLoc(), "index.evl.next");
1448 NextEVLIV->insertBefore(CanonicalIVIncrement);
1449 EVLPhi->addOperand(NextEVLIV);
1450
1451 for (VPValue *HeaderMask : collectAllHeaderMasks(Plan)) {
1452 for (VPUser *U : collectUsersRecursively(HeaderMask)) {
1453 auto *MemR = dyn_cast<VPWidenMemoryRecipe>(U);
1454 if (!MemR)
1455 continue;
1456 VPValue *OrigMask = MemR->getMask();
1457 assert(OrigMask && "Unmasked widen memory recipe when folding tail");
1458 VPValue *NewMask = HeaderMask == OrigMask ? nullptr : OrigMask;
1459 if (auto *L = dyn_cast<VPWidenLoadRecipe>(MemR)) {
1460 auto *N = new VPWidenLoadEVLRecipe(L, VPEVL, NewMask);
1461 N->insertBefore(L);
1462 L->replaceAllUsesWith(N);
1463 L->eraseFromParent();
1464 } else if (auto *S = dyn_cast<VPWidenStoreRecipe>(MemR)) {
1465 auto *N = new VPWidenStoreEVLRecipe(S, VPEVL, NewMask);
1466 N->insertBefore(S);
1467 S->eraseFromParent();
1468 } else {
1469 llvm_unreachable("unsupported recipe");
1470 }
1471 }
1472 recursivelyDeleteDeadRecipes(HeaderMask);
1473 }
1474 // Replace all uses of VPCanonicalIVPHIRecipe by
1475 // VPEVLBasedIVPHIRecipe except for the canonical IV increment.
1476 CanonicalIVPHI->replaceAllUsesWith(EVLPhi);
1477 CanonicalIVIncrement->setOperand(0, CanonicalIVPHI);
1478 // TODO: support unroll factor > 1.
1479 Plan.setUF(1);
1480 return true;
1481}
1482
1484 VPlan &Plan, function_ref<bool(BasicBlock *)> BlockNeedsPredication) {
1485 // Collect recipes in the backward slice of `Root` that may generate a poison
1486 // value that is used after vectorization.
1488 auto collectPoisonGeneratingInstrsInBackwardSlice([&](VPRecipeBase *Root) {
1490 Worklist.push_back(Root);
1491
1492 // Traverse the backward slice of Root through its use-def chain.
1493 while (!Worklist.empty()) {
1494 VPRecipeBase *CurRec = Worklist.back();
1495 Worklist.pop_back();
1496
1497 if (!Visited.insert(CurRec).second)
1498 continue;
1499
1500 // Prune search if we find another recipe generating a widen memory
1501 // instruction. Widen memory instructions involved in address computation
1502 // will lead to gather/scatter instructions, which don't need to be
1503 // handled.
1504 if (isa<VPWidenMemoryRecipe>(CurRec) || isa<VPInterleaveRecipe>(CurRec) ||
1505 isa<VPScalarIVStepsRecipe>(CurRec) || isa<VPHeaderPHIRecipe>(CurRec))
1506 continue;
1507
1508 // This recipe contributes to the address computation of a widen
1509 // load/store. If the underlying instruction has poison-generating flags,
1510 // drop them directly.
1511 if (auto *RecWithFlags = dyn_cast<VPRecipeWithIRFlags>(CurRec)) {
1512 VPValue *A, *B;
1513 using namespace llvm::VPlanPatternMatch;
1514 // Dropping disjoint from an OR may yield incorrect results, as some
1515 // analysis may have converted it to an Add implicitly (e.g. SCEV used
1516 // for dependence analysis). Instead, replace it with an equivalent Add.
1517 // This is possible as all users of the disjoint OR only access lanes
1518 // where the operands are disjoint or poison otherwise.
1519 if (match(RecWithFlags, m_BinaryOr(m_VPValue(A), m_VPValue(B))) &&
1520 RecWithFlags->isDisjoint()) {
1521 VPBuilder Builder(RecWithFlags);
1522 VPInstruction *New = Builder.createOverflowingOp(
1523 Instruction::Add, {A, B}, {false, false},
1524 RecWithFlags->getDebugLoc());
1525 New->setUnderlyingValue(RecWithFlags->getUnderlyingValue());
1526 RecWithFlags->replaceAllUsesWith(New);
1527 RecWithFlags->eraseFromParent();
1528 CurRec = New;
1529 } else
1530 RecWithFlags->dropPoisonGeneratingFlags();
1531 } else {
1532 Instruction *Instr = dyn_cast_or_null<Instruction>(
1533 CurRec->getVPSingleValue()->getUnderlyingValue());
1534 (void)Instr;
1535 assert((!Instr || !Instr->hasPoisonGeneratingFlags()) &&
1536 "found instruction with poison generating flags not covered by "
1537 "VPRecipeWithIRFlags");
1538 }
1539
1540 // Add new definitions to the worklist.
1541 for (VPValue *operand : CurRec->operands())
1542 if (VPRecipeBase *OpDef = operand->getDefiningRecipe())
1543 Worklist.push_back(OpDef);
1544 }
1545 });
1546
1547 // Traverse all the recipes in the VPlan and collect the poison-generating
1548 // recipes in the backward slice starting at the address of a VPWidenRecipe or
1549 // VPInterleaveRecipe.
1550 auto Iter = vp_depth_first_deep(Plan.getEntry());
1551 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
1552 for (VPRecipeBase &Recipe : *VPBB) {
1553 if (auto *WidenRec = dyn_cast<VPWidenMemoryRecipe>(&Recipe)) {
1554 Instruction &UnderlyingInstr = WidenRec->getIngredient();
1555 VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();
1556 if (AddrDef && WidenRec->isConsecutive() &&
1557 BlockNeedsPredication(UnderlyingInstr.getParent()))
1558 collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
1559 } else if (auto *InterleaveRec = dyn_cast<VPInterleaveRecipe>(&Recipe)) {
1560 VPRecipeBase *AddrDef = InterleaveRec->getAddr()->getDefiningRecipe();
1561 if (AddrDef) {
1562 // Check if any member of the interleave group needs predication.
1563 const InterleaveGroup<Instruction> *InterGroup =
1564 InterleaveRec->getInterleaveGroup();
1565 bool NeedPredication = false;
1566 for (int I = 0, NumMembers = InterGroup->getNumMembers();
1567 I < NumMembers; ++I) {
1568 Instruction *Member = InterGroup->getMember(I);
1569 if (Member)
1570 NeedPredication |= BlockNeedsPredication(Member->getParent());
1571 }
1572
1573 if (NeedPredication)
1574 collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
1575 }
1576 }
1577 }
1578 }
1579}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Hexagon Common GEP
iv Induction Variable Users
Definition: IVUsers.cpp:48
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution &SE)
#define I(x, y, z)
Definition: MD5.cpp:58
uint64_t IntrinsicInst * II
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
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 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 bool isDeadRecipe(VPRecipeBase &R)
Returns true if R is dead and can be removed.
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 SmallVector< VPValue * > collectAllHeaderMasks(VPlan &Plan)
Collect all VPValues representing a header mask through the (ICMP_ULE, WideCanonicalIV,...
static VPScalarIVStepsRecipe * createScalarIVSteps(VPlan &Plan, InductionDescriptor::InductionKind Kind, Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp, ScalarEvolution &SE, Instruction *TruncI, VPValue *StartV, VPValue *Step, VPBasicBlock::iterator IP)
static bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B, VPDominatorTree &VPDT)
static SmallVector< VPUser * > collectUsersRecursively(VPValue *V)
static void recursivelyDeleteDeadRecipes(VPValue *V)
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:206
This class represents a function call, abstracting a target machine's calling convention.
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:1019
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:850
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:308
Utility class for floating point operations which can have information about relaxed accuracy require...
Definition: Operator.h:202
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags.
Definition: Operator.h:320
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:974
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:445
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
Definition: VectorUtils.h:515
uint32_t getNumMembers() const
Definition: VectorUtils.h:463
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:185
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
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
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:318
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:2677
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2881
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2953
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:2905
iterator end()
Definition: VPlan.h:2915
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
Definition: VPlan.h:2966
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:211
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:538
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition: VPlan.cpp:601
const VPRecipeBase & back() const
Definition: VPlan.h:2927
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:2944
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:437
VPRegionBlock * getParent()
Definition: VPlan.h:509
const VPBasicBlock * getExitingBasicBlock() const
Definition: VPlan.cpp:176
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:550
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:154
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:596
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:544
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:534
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition: VPlan.h:3508
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3536
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3525
A recipe for generating conditional branches on the bits of a mask.
Definition: VPlan.h:2271
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:2620
Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:2649
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:422
ArrayRef< VPValue * > definedValues()
Returns an ArrayRef of the values defined by the VPDef.
Definition: VPlanValue.h:417
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:395
A recipe for converting the input value IV value to the corresponding value of an IV with different s...
Definition: VPlan.h:2774
A recipe for generating the phi node for the current index of elements, adjusted in accordance with E...
Definition: VPlan.h:2709
VPValue * getStartValue()
Returns the start value of the phi, if one is set.
Definition: VPlan.h:1721
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:1217
@ FirstOrderRecurrenceSplice
Definition: VPlan.h:1223
@ CanonicalIVIncrementForPart
Definition: VPlan.h:1233
@ CalculateTripCountMinusVF
Definition: VPlan.h:1231
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
Definition: VPlan.h:2322
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:753
bool mayReadOrWriteMemory() const
Returns true if the recipe may read from or write to memory.
Definition: VPlan.h:844
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
VPBasicBlock * getParent()
Definition: VPlan.h:778
DebugLoc getDebugLoc() const
Returns the debug location of the recipe.
Definition: VPlan.h:849
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:3059
const VPBlockBase * getEntry() const
Definition: VPlan.h:3098
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:2198
bool isUniform() const
Definition: VPlan.h:2238
VPValue * getMask()
Return the mask of a predicated VPReplicateRecipe.
Definition: VPlan.h:2262
VPScalarCastRecipe is a recipe to create scalar cast instructions.
Definition: VPlan.h:1464
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition: VPlan.h:2831
VPSingleDef is a base class for recipes for modeling a sequence of one or more output IR that define ...
Definition: VPlan.h:880
Instruction * getUnderlyingInstr()
Returns the underlying instruction.
Definition: VPlan.h:943
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:202
operand_range operands()
Definition: VPlanValue.h:272
void setOperand(unsigned I, VPValue *New)
Definition: VPlanValue.h:257
operand_iterator op_end()
Definition: VPlanValue.h:270
operand_iterator op_begin()
Definition: VPlanValue.h:268
void addOperand(VPValue *Operand)
Definition: VPlanValue.h:246
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition: VPlan.cpp:119
Value * getUnderlyingValue() const
Return the underlying Value attached to this VPValue.
Definition: VPlanValue.h:77
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:1316
unsigned getNumUsers() const
Definition: VPlanValue.h:111
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
Definition: VPlanValue.h:172
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:1320
user_range users()
Definition: VPlanValue.h:132
A recipe for widening Call instructions.
Definition: VPlan.h:1503
A Recipe for widening the canonical induction variable of the vector loop.
Definition: VPlan.h:2745
VPWidenCastRecipe is a recipe to create vector cast instructions.
Definition: VPlan.h:1416
A recipe for handling GEP instructions.
Definition: VPlan.h:1590
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
Definition: VPlan.h:1745
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:1384
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:3163
bool hasScalableVF()
Definition: VPlan.h:3300
VPBasicBlock * getEntry()
Definition: VPlan.h:3261
VPValue * getTripCount() const
The trip count of the original loop.
Definition: VPlan.h:3265
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition: VPlan.h:3279
void addLiveOut(PHINode *PN, VPValue *V)
Definition: VPlan.cpp:1077
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:3360
bool hasVF(ElementCount VF)
Definition: VPlan.h:3299
bool hasUF(unsigned UF) const
Definition: VPlan.h:3311
void setVF(ElementCount VF)
Definition: VPlan.h:3293
VPValue * getOrAddLiveIn(Value *V)
Gets the live-in VPValue for V or adds a new live-in (if none exists yet) for V.
Definition: VPlan.h:3326
bool hasScalarVFOnly() const
Definition: VPlan.h:3309
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
Definition: VPlan.h:3368
void setUF(unsigned UF)
Definition: VPlan.h:3313
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:255
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
Definition: ilist_node.h:109
IteratorT end() const
#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
CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)
Matches Trunc.
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:972
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
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.
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
Definition: VPlan.cpp:1505
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used.
Definition: VPlan.cpp:1495
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:1722
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:656
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:1729
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:147
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:1736
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
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
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1921
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:1749
@ DataAndControlFlowWithoutRuntimeCheck
Use predicate to control both data and control flow, but modify the trip count so that a runtime over...
#define N
A recipe for handling first-order recurrence phis.
Definition: VPlan.h:1916
A recipe for widening load operations with vector-predication intrinsics, using the address to load f...
Definition: VPlan.h:2470
A recipe for widening load operations, using the address to load from and an optional mask.
Definition: VPlan.h:2431
A recipe for widening select instructions.
Definition: VPlan.h:1556
A recipe for widening store operations with vector-predication intrinsics, using the value to store,...
Definition: VPlan.h:2546
A recipe for widening store operations, using the stored value, the address to store to and an option...
Definition: VPlan.h:2505
static bool tryAddExplicitVectorLength(VPlan &Plan)
Add a VPEVLBasedIVPHIRecipe and related recipes to Plan and replaces all uses except the canonical IV...
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.