LLVM 18.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"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SetVector.h"
24#include "llvm/IR/Intrinsics.h"
26
27using namespace llvm;
28
29using namespace llvm::PatternMatch;
30
32 VPlanPtr &Plan,
34 GetIntOrFpInductionDescriptor,
35 ScalarEvolution &SE, const TargetLibraryInfo &TLI) {
36
38 Plan->getEntry());
39 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
40 VPRecipeBase *Term = VPBB->getTerminator();
41 auto EndIter = Term ? Term->getIterator() : VPBB->end();
42 // Introduce each ingredient into VPlan.
43 for (VPRecipeBase &Ingredient :
44 make_early_inc_range(make_range(VPBB->begin(), EndIter))) {
45
46 VPValue *VPV = Ingredient.getVPSingleValue();
47 Instruction *Inst = cast<Instruction>(VPV->getUnderlyingValue());
48
49 VPRecipeBase *NewRecipe = nullptr;
50 if (auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
51 auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
52 if (const auto *II = GetIntOrFpInductionDescriptor(Phi)) {
53 VPValue *Start = Plan->getVPValueOrAddLiveIn(II->getStartValue());
54 VPValue *Step =
55 vputils::getOrCreateVPValueForSCEVExpr(*Plan, II->getStep(), SE);
56 NewRecipe = new VPWidenIntOrFpInductionRecipe(Phi, Start, Step, *II);
57 } else {
58 Plan->addVPValue(Phi, VPPhi);
59 continue;
60 }
61 } else {
62 assert(isa<VPInstruction>(&Ingredient) &&
63 "only VPInstructions expected here");
64 assert(!isa<PHINode>(Inst) && "phis should be handled above");
65 // Create VPWidenMemoryInstructionRecipe for loads and stores.
66 if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
67 NewRecipe = new VPWidenMemoryInstructionRecipe(
68 *Load, Ingredient.getOperand(0), nullptr /*Mask*/,
69 false /*Consecutive*/, false /*Reverse*/);
70 } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
71 NewRecipe = new VPWidenMemoryInstructionRecipe(
72 *Store, Ingredient.getOperand(1), Ingredient.getOperand(0),
73 nullptr /*Mask*/, false /*Consecutive*/, false /*Reverse*/);
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 =
78 new VPWidenCallRecipe(*CI, drop_end(Ingredient.operands()),
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 = Op->getDefiningRecipe())
117 WorkList.insert(std::make_pair(VPBB, Def));
118 }
119 }
120
121 bool ScalarVFOnly = Plan.hasScalarVFOnly();
122 // Try to sink each replicate or scalar IV steps recipe in the worklist.
123 for (unsigned I = 0; I != WorkList.size(); ++I) {
124 VPBasicBlock *SinkTo;
125 VPRecipeBase *SinkCandidate;
126 std::tie(SinkTo, SinkCandidate) = WorkList[I];
127 if (SinkCandidate->getParent() == SinkTo ||
128 SinkCandidate->mayHaveSideEffects() ||
129 SinkCandidate->mayReadOrWriteMemory())
130 continue;
131 if (auto *RepR = dyn_cast<VPReplicateRecipe>(SinkCandidate)) {
132 if (!ScalarVFOnly && RepR->isUniform())
133 continue;
134 } else if (!isa<VPScalarIVStepsRecipe>(SinkCandidate))
135 continue;
136
137 bool NeedsDuplicating = false;
138 // All recipe users of the sink candidate must be in the same block SinkTo
139 // or all users outside of SinkTo must be uniform-after-vectorization (
140 // i.e., only first lane is used) . In the latter case, we need to duplicate
141 // SinkCandidate.
142 auto CanSinkWithUser = [SinkTo, &NeedsDuplicating,
143 SinkCandidate](VPUser *U) {
144 auto *UI = dyn_cast<VPRecipeBase>(U);
145 if (!UI)
146 return false;
147 if (UI->getParent() == SinkTo)
148 return true;
149 NeedsDuplicating =
150 UI->onlyFirstLaneUsed(SinkCandidate->getVPSingleValue());
151 // We only know how to duplicate VPRecipeRecipes for now.
152 return NeedsDuplicating && isa<VPReplicateRecipe>(SinkCandidate);
153 };
154 if (!all_of(SinkCandidate->getVPSingleValue()->users(), CanSinkWithUser))
155 continue;
156
157 if (NeedsDuplicating) {
158 if (ScalarVFOnly)
159 continue;
160 Instruction *I = cast<Instruction>(
161 cast<VPReplicateRecipe>(SinkCandidate)->getUnderlyingValue());
162 auto *Clone = new VPReplicateRecipe(I, SinkCandidate->operands(), true);
163 // TODO: add ".cloned" suffix to name of Clone's VPValue.
164
165 Clone->insertBefore(SinkCandidate);
166 SinkCandidate->getVPSingleValue()->replaceUsesWithIf(
167 Clone, [SinkTo](VPUser &U, unsigned) {
168 return cast<VPRecipeBase>(&U)->getParent() != SinkTo;
169 });
170 }
171 SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi());
172 for (VPValue *Op : SinkCandidate->operands())
173 if (auto *Def = Op->getDefiningRecipe())
174 WorkList.insert(std::make_pair(SinkTo, Def));
175 Changed = true;
176 }
177 return Changed;
178}
179
180/// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return
181/// the mask.
183 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
184 if (!EntryBB || EntryBB->size() != 1 ||
185 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
186 return nullptr;
187
188 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
189}
190
191/// If \p R is a triangle region, return the 'then' block of the triangle.
193 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
194 if (EntryBB->getNumSuccessors() != 2)
195 return nullptr;
196
197 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
198 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
199 if (!Succ0 || !Succ1)
200 return nullptr;
201
202 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
203 return nullptr;
204 if (Succ0->getSingleSuccessor() == Succ1)
205 return Succ0;
206 if (Succ1->getSingleSuccessor() == Succ0)
207 return Succ1;
208 return nullptr;
209}
210
211// Merge replicate regions in their successor region, if a replicate region
212// is connected to a successor replicate region with the same predicate by a
213// single, empty VPBasicBlock.
215 SetVector<VPRegionBlock *> DeletedRegions;
216
217 // Collect replicate regions followed by an empty block, followed by another
218 // replicate region with matching masks to process front. This is to avoid
219 // iterator invalidation issues while merging regions.
221 for (VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
222 vp_depth_first_deep(Plan.getEntry()))) {
223 if (!Region1->isReplicator())
224 continue;
225 auto *MiddleBasicBlock =
226 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
227 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
228 continue;
229
230 auto *Region2 =
231 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
232 if (!Region2 || !Region2->isReplicator())
233 continue;
234
235 VPValue *Mask1 = getPredicatedMask(Region1);
236 VPValue *Mask2 = getPredicatedMask(Region2);
237 if (!Mask1 || Mask1 != Mask2)
238 continue;
239
240 assert(Mask1 && Mask2 && "both region must have conditions");
241 WorkList.push_back(Region1);
242 }
243
244 // Move recipes from Region1 to its successor region, if both are triangles.
245 for (VPRegionBlock *Region1 : WorkList) {
246 if (DeletedRegions.contains(Region1))
247 continue;
248 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());
249 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
250
251 VPBasicBlock *Then1 = getPredicatedThenBlock(Region1);
252 VPBasicBlock *Then2 = getPredicatedThenBlock(Region2);
253 if (!Then1 || !Then2)
254 continue;
255
256 // Note: No fusion-preventing memory dependencies are expected in either
257 // region. Such dependencies should be rejected during earlier dependence
258 // checks, which guarantee accesses can be re-ordered for vectorization.
259 //
260 // Move recipes to the successor region.
261 for (VPRecipeBase &ToMove : make_early_inc_range(reverse(*Then1)))
262 ToMove.moveBefore(*Then2, Then2->getFirstNonPhi());
263
264 auto *Merge1 = cast<VPBasicBlock>(Then1->getSingleSuccessor());
265 auto *Merge2 = cast<VPBasicBlock>(Then2->getSingleSuccessor());
266
267 // Move VPPredInstPHIRecipes from the merge block to the successor region's
268 // merge block. Update all users inside the successor region to use the
269 // original values.
270 for (VPRecipeBase &Phi1ToMove : make_early_inc_range(reverse(*Merge1))) {
271 VPValue *PredInst1 =
272 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
273 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
274 Phi1ToMoveV->replaceUsesWithIf(PredInst1, [Then2](VPUser &U, unsigned) {
275 auto *UI = dyn_cast<VPRecipeBase>(&U);
276 return UI && UI->getParent() == Then2;
277 });
278
279 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
280 }
281
282 // Finally, remove the first region.
283 for (VPBlockBase *Pred : make_early_inc_range(Region1->getPredecessors())) {
284 VPBlockUtils::disconnectBlocks(Pred, Region1);
285 VPBlockUtils::connectBlocks(Pred, MiddleBasicBlock);
286 }
287 VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock);
288 DeletedRegions.insert(Region1);
289 }
290
291 for (VPRegionBlock *ToDelete : DeletedRegions)
292 delete ToDelete;
293 return !DeletedRegions.empty();
294}
295
297 VPlan &Plan) {
298 Instruction *Instr = PredRecipe->getUnderlyingInstr();
299 // Build the triangular if-then region.
300 std::string RegionName = (Twine("pred.") + Instr->getOpcodeName()).str();
301 assert(Instr->getParent() && "Predicated instruction not in any basic block");
302 auto *BlockInMask = PredRecipe->getMask();
303 auto *BOMRecipe = new VPBranchOnMaskRecipe(BlockInMask);
304 auto *Entry = new VPBasicBlock(Twine(RegionName) + ".entry", BOMRecipe);
305
306 // Replace predicated replicate recipe with a replicate recipe without a
307 // mask but in the replicate region.
308 auto *RecipeWithoutMask = new VPReplicateRecipe(
309 PredRecipe->getUnderlyingInstr(),
310 make_range(PredRecipe->op_begin(), std::prev(PredRecipe->op_end())),
311 PredRecipe->isUniform());
312 auto *Pred = new VPBasicBlock(Twine(RegionName) + ".if", RecipeWithoutMask);
313
314 VPPredInstPHIRecipe *PHIRecipe = nullptr;
315 if (PredRecipe->getNumUsers() != 0) {
316 PHIRecipe = new VPPredInstPHIRecipe(RecipeWithoutMask);
317 PredRecipe->replaceAllUsesWith(PHIRecipe);
318 PHIRecipe->setOperand(0, RecipeWithoutMask);
319 }
320 PredRecipe->eraseFromParent();
321 auto *Exiting = new VPBasicBlock(Twine(RegionName) + ".continue", PHIRecipe);
322 VPRegionBlock *Region = new VPRegionBlock(Entry, Exiting, RegionName, true);
323
324 // Note: first set Entry as region entry and then connect successors starting
325 // from it in order, to propagate the "parent" of each VPBasicBlock.
326 VPBlockUtils::insertTwoBlocksAfter(Pred, Exiting, Entry);
327 VPBlockUtils::connectBlocks(Pred, Exiting);
328
329 return Region;
330}
331
332static void addReplicateRegions(VPlan &Plan) {
334 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
335 vp_depth_first_deep(Plan.getEntry()))) {
336 for (VPRecipeBase &R : *VPBB)
337 if (auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
338 if (RepR->isPredicated())
339 WorkList.push_back(RepR);
340 }
341 }
342
343 unsigned BBNum = 0;
344 for (VPReplicateRecipe *RepR : WorkList) {
345 VPBasicBlock *CurrentBlock = RepR->getParent();
346 VPBasicBlock *SplitBlock = CurrentBlock->splitAt(RepR->getIterator());
347
348 BasicBlock *OrigBB = RepR->getUnderlyingInstr()->getParent();
350 OrigBB->hasName() ? OrigBB->getName() + "." + Twine(BBNum++) : "");
351 // Record predicated instructions for above packing optimizations.
353 Region->setParent(CurrentBlock->getParent());
355 VPBlockUtils::connectBlocks(CurrentBlock, Region);
357 }
358}
359
361 // Convert masked VPReplicateRecipes to if-then region blocks.
363
364 bool ShouldSimplify = true;
365 while (ShouldSimplify) {
366 ShouldSimplify = sinkScalarOperands(Plan);
367 ShouldSimplify |= mergeReplicateRegionsIntoSuccessors(Plan);
368 ShouldSimplify |= VPlanTransforms::mergeBlocksIntoPredecessors(Plan);
369 }
370}
371bool VPlanTransforms::mergeBlocksIntoPredecessors(VPlan &Plan) {
373 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
374 vp_depth_first_deep(Plan.getEntry()))) {
375 auto *PredVPBB =
376 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
377 if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
378 WorkList.push_back(VPBB);
379 }
380
381 for (VPBasicBlock *VPBB : WorkList) {
382 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
383 for (VPRecipeBase &R : make_early_inc_range(*VPBB))
384 R.moveBefore(*PredVPBB, PredVPBB->end());
385 VPBlockUtils::disconnectBlocks(PredVPBB, VPBB);
386 auto *ParentRegion = cast_or_null<VPRegionBlock>(VPBB->getParent());
387 if (ParentRegion && ParentRegion->getExiting() == VPBB)
388 ParentRegion->setExiting(PredVPBB);
389 for (auto *Succ : to_vector(VPBB->successors())) {
391 VPBlockUtils::connectBlocks(PredVPBB, Succ);
392 }
393 delete VPBB;
394 }
395 return !WorkList.empty();
396}
397
398void VPlanTransforms::removeRedundantInductionCasts(VPlan &Plan) {
399 for (auto &Phi : Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
400 auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
401 if (!IV || IV->getTruncInst())
402 continue;
403
404 // A sequence of IR Casts has potentially been recorded for IV, which
405 // *must be bypassed* when the IV is vectorized, because the vectorized IV
406 // will produce the desired casted value. This sequence forms a def-use
407 // chain and is provided in reverse order, ending with the cast that uses
408 // the IV phi. Search for the recipe of the last cast in the chain and
409 // replace it with the original IV. Note that only the final cast is
410 // expected to have users outside the cast-chain and the dead casts left
411 // over will be cleaned up later.
412 auto &Casts = IV->getInductionDescriptor().getCastInsts();
413 VPValue *FindMyCast = IV;
414 for (Instruction *IRCast : reverse(Casts)) {
415 VPRecipeBase *FoundUserCast = nullptr;
416 for (auto *U : FindMyCast->users()) {
417 auto *UserCast = cast<VPRecipeBase>(U);
418 if (UserCast->getNumDefinedValues() == 1 &&
419 UserCast->getVPSingleValue()->getUnderlyingValue() == IRCast) {
420 FoundUserCast = UserCast;
421 break;
422 }
423 }
424 FindMyCast = FoundUserCast->getVPSingleValue();
425 }
426 FindMyCast->replaceAllUsesWith(IV);
427 }
428}
429
430void VPlanTransforms::removeRedundantCanonicalIVs(VPlan &Plan) {
431 VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
432 VPWidenCanonicalIVRecipe *WidenNewIV = nullptr;
433 for (VPUser *U : CanonicalIV->users()) {
434 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
435 if (WidenNewIV)
436 break;
437 }
438
439 if (!WidenNewIV)
440 return;
441
443 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
444 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
445
446 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() ||
447 WidenOriginalIV->getScalarType() != WidenNewIV->getScalarType())
448 continue;
449
450 // Replace WidenNewIV with WidenOriginalIV if WidenOriginalIV provides
451 // everything WidenNewIV's users need. That is, WidenOriginalIV will
452 // generate a vector phi or all users of WidenNewIV demand the first lane
453 // only.
454 if (any_of(WidenOriginalIV->users(),
455 [WidenOriginalIV](VPUser *U) {
456 return !U->usesScalars(WidenOriginalIV);
457 }) ||
458 vputils::onlyFirstLaneUsed(WidenNewIV)) {
459 WidenNewIV->replaceAllUsesWith(WidenOriginalIV);
460 WidenNewIV->eraseFromParent();
461 return;
462 }
463 }
464}
465
466void VPlanTransforms::removeDeadRecipes(VPlan &Plan) {
468 Plan.getEntry());
469
470 for (VPBasicBlock *VPBB : reverse(VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT))) {
471 // The recipes in the block are processed in reverse order, to catch chains
472 // of dead recipes.
473 for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) {
474 // A user keeps R alive:
475 if (any_of(R.definedValues(),
476 [](VPValue *V) { return V->getNumUsers(); }))
477 continue;
478
479 // Having side effects keeps R alive, but do remove conditional assume
480 // instructions as their conditions may be flattened.
481 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);
482 bool IsConditionalAssume =
483 RepR && RepR->isPredicated() &&
484 match(RepR->getUnderlyingInstr(), m_Intrinsic<Intrinsic::assume>());
485 if (R.mayHaveSideEffects() && !IsConditionalAssume)
486 continue;
487
488 R.eraseFromParent();
489 }
490 }
491}
492
494 ScalarEvolution &SE, Instruction *TruncI,
495 Type *IVTy, VPValue *StartV,
496 VPValue *Step) {
498 auto IP = HeaderVPBB->getFirstNonPhi();
499 VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
500 Type *TruncTy = TruncI ? TruncI->getType() : IVTy;
501 VPValue *BaseIV = CanonicalIV;
502 if (!CanonicalIV->isCanonical(ID.getKind(), StartV, Step, TruncTy)) {
503 BaseIV = new VPDerivedIVRecipe(ID, StartV, CanonicalIV, Step,
504 TruncI ? TruncI->getType() : nullptr);
505 HeaderVPBB->insert(BaseIV->getDefiningRecipe(), IP);
506 }
507
508 VPScalarIVStepsRecipe *Steps = new VPScalarIVStepsRecipe(ID, BaseIV, Step);
509 HeaderVPBB->insert(Steps, IP);
510 return Steps;
511}
512
513void VPlanTransforms::optimizeInductions(VPlan &Plan, ScalarEvolution &SE) {
516 bool HasOnlyVectorVFs = !Plan.hasVF(ElementCount::getFixed(1));
517 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
518 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
519 if (!WideIV)
520 continue;
521 if (HasOnlyVectorVFs && none_of(WideIV->users(), [WideIV](VPUser *U) {
522 return U->usesScalars(WideIV);
523 }))
524 continue;
525
526 const InductionDescriptor &ID = WideIV->getInductionDescriptor();
528 Plan, ID, SE, WideIV->getTruncInst(), WideIV->getPHINode()->getType(),
529 WideIV->getStartValue(), WideIV->getStepValue());
530
531 // Update scalar users of IV to use Step instead. Use SetVector to ensure
532 // the list of users doesn't contain duplicates.
533 WideIV->replaceUsesWithIf(
534 Steps, [HasOnlyVectorVFs, WideIV](VPUser &U, unsigned) {
535 return !HasOnlyVectorVFs || U.usesScalars(WideIV);
536 });
537 }
538}
539
540void VPlanTransforms::removeRedundantExpandSCEVRecipes(VPlan &Plan) {
542
543 for (VPRecipeBase &R :
545 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
546 if (!ExpR)
547 continue;
548
549 auto I = SCEV2VPV.insert({ExpR->getSCEV(), ExpR});
550 if (I.second)
551 continue;
552 ExpR->replaceAllUsesWith(I.first->second);
553 ExpR->eraseFromParent();
554 }
555}
556
558 VPInstruction *Not = dyn_cast<VPInstruction>(Term->getOperand(0));
559 if (!Not || Not->getOpcode() != VPInstruction::Not)
560 return false;
561
562 VPInstruction *ALM = dyn_cast<VPInstruction>(Not->getOperand(0));
563 return ALM && ALM->getOpcode() == VPInstruction::ActiveLaneMask;
564}
565
567 unsigned BestUF,
569 assert(Plan.hasVF(BestVF) && "BestVF is not available in Plan");
570 assert(Plan.hasUF(BestUF) && "BestUF is not available in Plan");
571 VPBasicBlock *ExitingVPBB =
573 auto *Term = dyn_cast<VPInstruction>(&ExitingVPBB->back());
574 // Try to simplify the branch condition if TC <= VF * UF when preparing to
575 // execute the plan for the main vector loop. We only do this if the
576 // terminator is:
577 // 1. BranchOnCount, or
578 // 2. BranchOnCond where the input is Not(ActiveLaneMask).
579 if (!Term || (Term->getOpcode() != VPInstruction::BranchOnCount &&
580 (Term->getOpcode() != VPInstruction::BranchOnCond ||
582 return;
583
584 Type *IdxTy =
586 const SCEV *TripCount = createTripCountSCEV(IdxTy, PSE);
587 ScalarEvolution &SE = *PSE.getSE();
588 const SCEV *C =
589 SE.getConstant(TripCount->getType(), BestVF.getKnownMinValue() * BestUF);
590 if (TripCount->isZero() ||
591 !SE.isKnownPredicate(CmpInst::ICMP_ULE, TripCount, C))
592 return;
593
594 LLVMContext &Ctx = SE.getContext();
595 auto *BOC = new VPInstruction(
598 Term->eraseFromParent();
599 ExitingVPBB->appendRecipe(BOC);
600 Plan.setVF(BestVF);
601 Plan.setUF(BestUF);
602 // TODO: Further simplifications are possible
603 // 1. Replace inductions with constants.
604 // 2. Replace vector loop region with VPBasicBlock.
605}
606
607#ifndef NDEBUG
609 auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
610 if (Region && Region->isReplicator()) {
611 assert(Region->getNumSuccessors() == 1 &&
612 Region->getNumPredecessors() == 1 && "Expected SESE region!");
613 assert(R->getParent()->size() == 1 &&
614 "A recipe in an original replicator region must be the only "
615 "recipe in its block");
616 return Region;
617 }
618 return nullptr;
619}
620#endif
621
622static bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B,
623 VPDominatorTree &VPDT) {
624 if (A == B)
625 return false;
626
627 auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {
628 for (auto &R : *A->getParent()) {
629 if (&R == A)
630 return true;
631 if (&R == B)
632 return false;
633 }
634 llvm_unreachable("recipe not found");
635 };
636 const VPBlockBase *ParentA = A->getParent();
637 const VPBlockBase *ParentB = B->getParent();
638 if (ParentA == ParentB)
639 return LocalComesBefore(A, B);
640
641 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(A)) &&
642 "No replicate regions expected at this point");
643 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(B)) &&
644 "No replicate regions expected at this point");
645 return VPDT.properlyDominates(ParentA, ParentB);
646}
647
648/// Sink users of \p FOR after the recipe defining the previous value \p
649/// Previous of the recurrence. \returns true if all users of \p FOR could be
650/// re-arranged as needed or false if it is not possible.
651static bool
653 VPRecipeBase *Previous,
654 VPDominatorTree &VPDT) {
655 // Collect recipes that need sinking.
658 Seen.insert(Previous);
659 auto TryToPushSinkCandidate = [&](VPRecipeBase *SinkCandidate) {
660 // The previous value must not depend on the users of the recurrence phi. In
661 // that case, FOR is not a fixed order recurrence.
662 if (SinkCandidate == Previous)
663 return false;
664
665 if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||
666 !Seen.insert(SinkCandidate).second ||
667 properlyDominates(Previous, SinkCandidate, VPDT))
668 return true;
669
670 if (SinkCandidate->mayHaveSideEffects())
671 return false;
672
673 WorkList.push_back(SinkCandidate);
674 return true;
675 };
676
677 // Recursively sink users of FOR after Previous.
678 WorkList.push_back(FOR);
679 for (unsigned I = 0; I != WorkList.size(); ++I) {
680 VPRecipeBase *Current = WorkList[I];
681 assert(Current->getNumDefinedValues() == 1 &&
682 "only recipes with a single defined value expected");
683
684 for (VPUser *User : Current->getVPSingleValue()->users()) {
685 if (auto *R = dyn_cast<VPRecipeBase>(User))
686 if (!TryToPushSinkCandidate(R))
687 return false;
688 }
689 }
690
691 // Keep recipes to sink ordered by dominance so earlier instructions are
692 // processed first.
693 sort(WorkList, [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
694 return properlyDominates(A, B, VPDT);
695 });
696
697 for (VPRecipeBase *SinkCandidate : WorkList) {
698 if (SinkCandidate == FOR)
699 continue;
700
701 SinkCandidate->moveAfter(Previous);
702 Previous = SinkCandidate;
703 }
704 return true;
705}
706
708 VPBuilder &Builder) {
709 VPDominatorTree VPDT;
710 VPDT.recalculate(Plan);
711
713 for (VPRecipeBase &R :
715 if (auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R))
716 RecurrencePhis.push_back(FOR);
717
718 for (VPFirstOrderRecurrencePHIRecipe *FOR : RecurrencePhis) {
720 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
721 // Fixed-order recurrences do not contain cycles, so this loop is guaranteed
722 // to terminate.
723 while (auto *PrevPhi =
724 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {
725 assert(PrevPhi->getParent() == FOR->getParent());
726 assert(SeenPhis.insert(PrevPhi).second);
727 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
728 }
729
730 if (!sinkRecurrenceUsersAfterPrevious(FOR, Previous, VPDT))
731 return false;
732
733 // Introduce a recipe to combine the incoming and previous values of a
734 // fixed-order recurrence.
735 VPBasicBlock *InsertBlock = Previous->getParent();
736 if (isa<VPHeaderPHIRecipe>(Previous))
737 Builder.setInsertPoint(InsertBlock, InsertBlock->getFirstNonPhi());
738 else
739 Builder.setInsertPoint(InsertBlock, std::next(Previous->getIterator()));
740
741 auto *RecurSplice = cast<VPInstruction>(
743 {FOR, FOR->getBackedgeValue()}));
744
745 FOR->replaceAllUsesWith(RecurSplice);
746 // Set the first operand of RecurSplice to FOR again, after replacing
747 // all users.
748 RecurSplice->setOperand(0, FOR);
749 }
750 return true;
751}
752
754 for (VPRecipeBase &R :
756 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(&R);
757 if (!PhiR)
758 continue;
759 const RecurrenceDescriptor &RdxDesc = PhiR->getRecurrenceDescriptor();
760 RecurKind RK = RdxDesc.getRecurrenceKind();
761 if (RK != RecurKind::Add && RK != RecurKind::Mul)
762 continue;
763
765 Worklist.insert(PhiR);
766
767 for (unsigned I = 0; I != Worklist.size(); ++I) {
768 VPValue *Cur = Worklist[I];
769 if (auto *RecWithFlags =
770 dyn_cast<VPRecipeWithIRFlags>(Cur->getDefiningRecipe())) {
771 RecWithFlags->dropPoisonGeneratingFlags();
772 }
773
774 for (VPUser *U : Cur->users()) {
775 auto *UserRecipe = dyn_cast<VPRecipeBase>(U);
776 if (!UserRecipe)
777 continue;
778 for (VPValue *V : UserRecipe->definedValues())
779 Worklist.insert(V);
780 }
781 }
782 }
783}
784
785/// Returns true is \p V is constant one.
786static bool isConstantOne(VPValue *V) {
787 if (!V->isLiveIn())
788 return false;
789 auto *C = dyn_cast<ConstantInt>(V->getLiveInIRValue());
790 return C && C->isOne();
791}
792
793/// Returns the llvm::Instruction opcode for \p R.
794static unsigned getOpcodeForRecipe(VPRecipeBase &R) {
795 if (auto *WidenR = dyn_cast<VPWidenRecipe>(&R))
796 return WidenR->getUnderlyingInstr()->getOpcode();
797 if (auto *WidenC = dyn_cast<VPWidenCastRecipe>(&R))
798 return WidenC->getOpcode();
799 if (auto *RepR = dyn_cast<VPReplicateRecipe>(&R))
800 return RepR->getUnderlyingInstr()->getOpcode();
801 if (auto *VPI = dyn_cast<VPInstruction>(&R))
802 return VPI->getOpcode();
803 return 0;
804}
805
806/// Try to simplify recipe \p R.
807static void simplifyRecipe(VPRecipeBase &R, VPTypeAnalysis &TypeInfo) {
808 switch (getOpcodeForRecipe(R)) {
809 case Instruction::Mul: {
810 VPValue *A = R.getOperand(0);
811 VPValue *B = R.getOperand(1);
812 if (isConstantOne(A))
813 return R.getVPSingleValue()->replaceAllUsesWith(B);
814 if (isConstantOne(B))
815 return R.getVPSingleValue()->replaceAllUsesWith(A);
816 break;
817 }
818 case Instruction::Trunc: {
819 VPRecipeBase *Ext = R.getOperand(0)->getDefiningRecipe();
820 if (!Ext)
821 break;
822 unsigned ExtOpcode = getOpcodeForRecipe(*Ext);
823 if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)
824 break;
825 VPValue *A = Ext->getOperand(0);
826 VPValue *Trunc = R.getVPSingleValue();
827 Type *TruncTy = TypeInfo.inferScalarType(Trunc);
828 Type *ATy = TypeInfo.inferScalarType(A);
829 if (TruncTy == ATy) {
830 Trunc->replaceAllUsesWith(A);
831 } else if (ATy->getScalarSizeInBits() < TruncTy->getScalarSizeInBits()) {
832 auto *VPC =
833 new VPWidenCastRecipe(Instruction::CastOps(ExtOpcode), A, TruncTy);
834 VPC->insertBefore(&R);
835 Trunc->replaceAllUsesWith(VPC);
836 } else if (ATy->getScalarSizeInBits() > TruncTy->getScalarSizeInBits()) {
837 auto *VPC = new VPWidenCastRecipe(Instruction::Trunc, A, TruncTy);
838 VPC->insertBefore(&R);
839 Trunc->replaceAllUsesWith(VPC);
840 }
841#ifndef NDEBUG
842 // Verify that the cached type info is for both A and its users is still
843 // accurate by comparing it to freshly computed types.
844 VPTypeAnalysis TypeInfo2(TypeInfo.getContext());
845 assert(TypeInfo.inferScalarType(A) == TypeInfo2.inferScalarType(A));
846 for (VPUser *U : A->users()) {
847 auto *R = dyn_cast<VPRecipeBase>(U);
848 if (!R)
849 continue;
850 for (VPValue *VPV : R->definedValues())
851 assert(TypeInfo.inferScalarType(VPV) == TypeInfo2.inferScalarType(VPV));
852 }
853#endif
854 break;
855 }
856 default:
857 break;
858 }
859}
860
861/// Try to simplify the recipes in \p Plan.
862static void simplifyRecipes(VPlan &Plan, LLVMContext &Ctx) {
864 Plan.getEntry());
865 VPTypeAnalysis TypeInfo(Ctx);
866 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
867 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
868 simplifyRecipe(R, TypeInfo);
869 }
870 }
871}
872
874 VPlan &Plan, const MapVector<Instruction *, uint64_t> &MinBWs,
875 LLVMContext &Ctx) {
876#ifndef NDEBUG
877 // Count the processed recipes and cross check the count later with MinBWs
878 // size, to make sure all entries in MinBWs have been handled.
879 unsigned NumProcessedRecipes = 0;
880#endif
881 // Keep track of created truncates, so they can be re-used. Note that we
882 // cannot use RAUW after creating a new truncate, as this would could make
883 // other uses have different types for their operands, making them invalidly
884 // typed.
886 VPTypeAnalysis TypeInfo(Ctx);
887 VPBasicBlock *PH = Plan.getEntry();
888 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
890 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
893 continue;
894
895 VPValue *ResultVPV = R.getVPSingleValue();
896 auto *UI = cast_or_null<Instruction>(ResultVPV->getUnderlyingValue());
897 unsigned NewResSizeInBits = MinBWs.lookup(UI);
898 if (!NewResSizeInBits)
899 continue;
900
901#ifndef NDEBUG
902 NumProcessedRecipes++;
903#endif
904 // If the value wasn't vectorized, we must maintain the original scalar
905 // type. Skip those here, after incrementing NumProcessedRecipes. Also
906 // skip casts which do not need to be handled explicitly here, as
907 // redundant casts will be removed during recipe simplification.
908 if (isa<VPReplicateRecipe, VPWidenCastRecipe>(&R)) {
909#ifndef NDEBUG
910 // If any of the operands is a live-in and not used by VPWidenRecipe or
911 // VPWidenSelectRecipe, but in MinBWs, make sure it is counted as
912 // processed as well. When MinBWs is currently constructed, there is no
913 // information about whether recipes are widened or replicated and in
914 // case they are reciplicated the operands are not truncated. Counting
915 // them them here ensures we do not miss any recipes in MinBWs.
916 // TODO: Remove once the analysis is done on VPlan.
917 for (VPValue *Op : R.operands()) {
918 if (!Op->isLiveIn())
919 continue;
920 auto *UV = dyn_cast_or_null<Instruction>(Op->getUnderlyingValue());
921 if (UV && MinBWs.contains(UV) && !ProcessedTruncs.contains(Op) &&
922 all_of(Op->users(), [](VPUser *U) {
923 return !isa<VPWidenRecipe, VPWidenSelectRecipe>(U);
924 })) {
925 // Add an entry to ProcessedTruncs to avoid counting the same
926 // operand multiple times.
927 ProcessedTruncs[Op] = nullptr;
928 NumProcessedRecipes += 1;
929 }
930 }
931#endif
932 continue;
933 }
934
935 Type *OldResTy = TypeInfo.inferScalarType(ResultVPV);
936 unsigned OldResSizeInBits = OldResTy->getScalarSizeInBits();
937 assert(OldResTy->isIntegerTy() && "only integer types supported");
938 if (OldResSizeInBits == NewResSizeInBits)
939 continue;
940 assert(OldResSizeInBits > NewResSizeInBits && "Nothing to shrink?");
941 (void)OldResSizeInBits;
942
943 auto *NewResTy = IntegerType::get(Ctx, NewResSizeInBits);
944
945 // Shrink operands by introducing truncates as needed.
946 unsigned StartIdx = isa<VPWidenSelectRecipe>(&R) ? 1 : 0;
947 for (unsigned Idx = StartIdx; Idx != R.getNumOperands(); ++Idx) {
948 auto *Op = R.getOperand(Idx);
949 unsigned OpSizeInBits =
951 if (OpSizeInBits == NewResSizeInBits)
952 continue;
953 assert(OpSizeInBits > NewResSizeInBits && "nothing to truncate");
954 auto [ProcessedIter, IterIsEmpty] =
955 ProcessedTruncs.insert({Op, nullptr});
956 VPWidenCastRecipe *NewOp =
957 IterIsEmpty
958 ? new VPWidenCastRecipe(Instruction::Trunc, Op, NewResTy)
959 : ProcessedIter->second;
960 R.setOperand(Idx, NewOp);
961 if (!IterIsEmpty)
962 continue;
963 ProcessedIter->second = NewOp;
964 if (!Op->isLiveIn()) {
965 NewOp->insertBefore(&R);
966 } else {
967 PH->appendRecipe(NewOp);
968#ifndef NDEBUG
969 auto *OpInst = dyn_cast<Instruction>(Op->getLiveInIRValue());
970 bool IsContained = MinBWs.contains(OpInst);
971 NumProcessedRecipes += IsContained;
972#endif
973 }
974 }
975
976 // Any wrapping introduced by shrinking this operation shouldn't be
977 // considered undefined behavior. So, we can't unconditionally copy
978 // arithmetic wrapping flags to VPW.
979 if (auto *VPW = dyn_cast<VPRecipeWithIRFlags>(&R))
980 VPW->dropPoisonGeneratingFlags();
981
982 // Extend result to original width.
983 auto *Ext = new VPWidenCastRecipe(Instruction::ZExt, ResultVPV, OldResTy);
984 Ext->insertAfter(&R);
985 ResultVPV->replaceAllUsesWith(Ext);
986 Ext->setOperand(0, ResultVPV);
987 }
988 }
989
990 assert(MinBWs.size() == NumProcessedRecipes &&
991 "some entries in MinBWs haven't been processed");
992}
993
995 removeRedundantCanonicalIVs(Plan);
996 removeRedundantInductionCasts(Plan);
997
998 optimizeInductions(Plan, SE);
999 simplifyRecipes(Plan, SE.getContext());
1000 removeDeadRecipes(Plan);
1001
1003
1004 removeRedundantExpandSCEVRecipes(Plan);
1005 mergeBlocksIntoPredecessors(Plan);
1006}
1007
1008// Add a VPActiveLaneMaskPHIRecipe and related recipes to \p Plan and replace
1009// the loop terminator with a branch-on-cond recipe with the negated
1010// active-lane-mask as operand. Note that this turns the loop into an
1011// uncountable one. Only the existing terminator is replaced, all other existing
1012// recipes/users remain unchanged, except for poison-generating flags being
1013// dropped from the canonical IV increment. Return the created
1014// VPActiveLaneMaskPHIRecipe.
1015//
1016// The function uses the following definitions:
1017//
1018// %TripCount = DataWithControlFlowWithoutRuntimeCheck ?
1019// calculate-trip-count-minus-VF (original TC) : original TC
1020// %IncrementValue = DataWithControlFlowWithoutRuntimeCheck ?
1021// CanonicalIVPhi : CanonicalIVIncrement
1022// %StartV is the canonical induction start value.
1023//
1024// The function adds the following recipes:
1025//
1026// vector.ph:
1027// %TripCount = calculate-trip-count-minus-VF (original TC)
1028// [if DataWithControlFlowWithoutRuntimeCheck]
1029// %EntryInc = canonical-iv-increment-for-part %StartV
1030// %EntryALM = active-lane-mask %EntryInc, %TripCount
1031//
1032// vector.body:
1033// ...
1034// %P = active-lane-mask-phi [ %EntryALM, %vector.ph ], [ %ALM, %vector.body ]
1035// ...
1036// %InLoopInc = canonical-iv-increment-for-part %IncrementValue
1037// %ALM = active-lane-mask %InLoopInc, TripCount
1038// %Negated = Not %ALM
1039// branch-on-cond %Negated
1040//
1043 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
1044 VPBasicBlock *EB = TopRegion->getExitingBasicBlock();
1045 auto *CanonicalIVPHI = Plan.getCanonicalIV();
1046 VPValue *StartV = CanonicalIVPHI->getStartValue();
1047
1048 auto *CanonicalIVIncrement =
1049 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());
1050 // TODO: Check if dropping the flags is needed if
1051 // !DataAndControlFlowWithoutRuntimeCheck.
1052 CanonicalIVIncrement->dropPoisonGeneratingFlags();
1053 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
1054 // We can't use StartV directly in the ActiveLaneMask VPInstruction, since
1055 // we have to take unrolling into account. Each part needs to start at
1056 // Part * VF
1057 auto *VecPreheader = cast<VPBasicBlock>(TopRegion->getSinglePredecessor());
1058 VPBuilder Builder(VecPreheader);
1059
1060 // Create the ActiveLaneMask instruction using the correct start values.
1061 VPValue *TC = Plan.getTripCount();
1062
1063 VPValue *TripCount, *IncrementValue;
1065 // When the loop is guarded by a runtime overflow check for the loop
1066 // induction variable increment by VF, we can increment the value before
1067 // the get.active.lane mask and use the unmodified tripcount.
1068 IncrementValue = CanonicalIVIncrement;
1069 TripCount = TC;
1070 } else {
1071 // When avoiding a runtime check, the active.lane.mask inside the loop
1072 // uses a modified trip count and the induction variable increment is
1073 // done after the active.lane.mask intrinsic is called.
1074 IncrementValue = CanonicalIVPHI;
1076 {TC}, DL);
1077 }
1078 auto *EntryIncrement = Builder.createOverflowingOp(
1079 VPInstruction::CanonicalIVIncrementForPart, {StartV}, {false, false}, DL,
1080 "index.part.next");
1081
1082 // Create the active lane mask instruction in the VPlan preheader.
1083 auto *EntryALM =
1084 Builder.createNaryOp(VPInstruction::ActiveLaneMask, {EntryIncrement, TC},
1085 DL, "active.lane.mask.entry");
1086
1087 // Now create the ActiveLaneMaskPhi recipe in the main loop using the
1088 // preheader ActiveLaneMask instruction.
1089 auto LaneMaskPhi = new VPActiveLaneMaskPHIRecipe(EntryALM, DebugLoc());
1090 LaneMaskPhi->insertAfter(CanonicalIVPHI);
1091
1092 // Create the active lane mask for the next iteration of the loop before the
1093 // original terminator.
1094 VPRecipeBase *OriginalTerminator = EB->getTerminator();
1095 Builder.setInsertPoint(OriginalTerminator);
1096 auto *InLoopIncrement =
1098 {IncrementValue}, {false, false}, DL);
1099 auto *ALM = Builder.createNaryOp(VPInstruction::ActiveLaneMask,
1100 {InLoopIncrement, TripCount}, DL,
1101 "active.lane.mask.next");
1102 LaneMaskPhi->addOperand(ALM);
1103
1104 // Replace the original terminator with BranchOnCond. We have to invert the
1105 // mask here because a true condition means jumping to the exit block.
1106 auto *NotMask = Builder.createNot(ALM, DL);
1107 Builder.createNaryOp(VPInstruction::BranchOnCond, {NotMask}, DL);
1108 OriginalTerminator->eraseFromParent();
1109 return LaneMaskPhi;
1110}
1111
1113 VPlan &Plan, bool UseActiveLaneMaskForControlFlow,
1116 UseActiveLaneMaskForControlFlow) &&
1117 "DataAndControlFlowWithoutRuntimeCheck implies "
1118 "UseActiveLaneMaskForControlFlow");
1119
1120 auto FoundWidenCanonicalIVUser =
1121 find_if(Plan.getCanonicalIV()->users(),
1122 [](VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); });
1123 assert(FoundWidenCanonicalIVUser &&
1124 "Must have widened canonical IV when tail folding!");
1125 auto *WideCanonicalIV =
1126 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);
1127 VPRecipeBase *LaneMask;
1128 if (UseActiveLaneMaskForControlFlow) {
1131 } else {
1133 {WideCanonicalIV, Plan.getTripCount()},
1134 nullptr, "active.lane.mask");
1135 LaneMask->insertAfter(WideCanonicalIV);
1136 }
1137
1138 // Walk users of WideCanonicalIV and replace all compares of the form
1139 // (ICMP_ULE, WideCanonicalIV, backedge-taken-count) with an
1140 // active-lane-mask.
1142 for (VPUser *U : SmallVector<VPUser *>(WideCanonicalIV->users())) {
1143 auto *CompareToReplace = dyn_cast<VPInstruction>(U);
1144 if (!CompareToReplace ||
1145 CompareToReplace->getOpcode() != Instruction::ICmp ||
1146 CompareToReplace->getPredicate() != CmpInst::ICMP_ULE ||
1147 CompareToReplace->getOperand(1) != BTC)
1148 continue;
1149
1150 assert(CompareToReplace->getOperand(0) == WideCanonicalIV &&
1151 "WidenCanonicalIV must be the first operand of the compare");
1152 CompareToReplace->replaceAllUsesWith(LaneMask->getVPSingleValue());
1153 CompareToReplace->eraseFromParent();
1154 }
1155}
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
Hexagon Common GEP
static bool isConstantOne(const Value *Val)
isConstantOne - Return true only if val is constant int 1
Definition: IRBuilder.cpp:295
#define I(x, y, z)
Definition: MD5.cpp:58
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 canSimplifyBranchOnCond(VPInstruction *Term)
static bool sinkScalarOperands(VPlan &Plan)
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 simplifyRecipe(VPRecipeBase &R, VPTypeAnalysis &TypeInfo)
Try to simplify recipe R.
static VPRegionBlock * GetReplicateRegion(VPRecipeBase *R)
static bool properlyDominates(const VPRecipeBase *A, const VPRecipeBase *B, VPDominatorTree &VPDT)
static unsigned getOpcodeForRecipe(VPRecipeBase &R)
Returns the llvm::Instruction opcode for R.
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 VPValue * createScalarIVSteps(VPlan &Plan, const InductionDescriptor &ID, ScalarEvolution &SE, Instruction *TruncI, Type *IVTy, VPValue *StartV, VPValue *Step)
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:213
This class represents a function call, abstracting a target machine's calling convention.
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:774
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
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:297
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:948
A struct for saving information about induction variables.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:285
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:177
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.
const SCEV * getConstant(ConstantInt *V)
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,...
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
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:2107
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2260
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2328
iterator end()
Definition: VPlan.h:2291
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
Definition: VPlan.h:2338
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:208
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:510
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition: VPlan.cpp:574
const VPRecipeBase & back() const
Definition: VPlan.h:2303
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:2319
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:420
VPRegionBlock * getParent()
Definition: VPlan.h:492
const VPBasicBlock * getExitingBasicBlock() const
Definition: VPlan.cpp:173
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:533
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:151
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:527
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:517
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition: VPlan.h:2831
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2859
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2848
A recipe for generating conditional branches on the bits of a mask.
Definition: VPlan.h:1860
VPlan-based builder utility analogous to IRBuilder.
VPInstruction * createOverflowingOp(unsigned Opcode, std::initializer_list< VPValue * > Operands, VPRecipeWithIRFlags::WrapFlagsTy WrapFlags, DebugLoc DL, const Twine &Name="")
VPValue * createNot(VPValue *Operand, DebugLoc DL, const Twine &Name="")
VPValue * 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.
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:2062
bool isCanonical(InductionDescriptor::InductionKind Kind, VPValue *Start, VPValue *Step, Type *Ty) 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
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:395
A recipe for converting the canonical IV value to the corresponding value of an IV with different sta...
Definition: VPlan.h:2163
VPValue * getStartValue()
Returns the start value of the phi, if one is set.
Definition: VPlan.h:1371
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:1018
unsigned getOpcode() const
Definition: VPlan.h:1085
@ FirstOrderRecurrenceSplice
Definition: VPlan.h:1024
@ CanonicalIVIncrementForPart
Definition: VPlan.h:1035
@ CalculateTripCountMinusVF
Definition: VPlan.h:1031
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
Definition: VPlan.h:1907
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:707
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.
Instruction * getUnderlyingInstr()
Returns the underlying instruction, if the recipe is a VPValue or nullptr otherwise.
Definition: VPlan.h:767
VPBasicBlock * getParent()
Definition: VPlan.h:729
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.
void insertAfter(VPRecipeBase *InsertPos)
Insert an unlinked Recipe into a basic block immediately after 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:2384
const VPBlockBase * getEntry() const
Definition: VPlan.h:2423
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:1797
bool isUniform() const
Definition: VPlan.h:1829
VPValue * getMask()
Return the mask of a predicated VPReplicateRecipe.
Definition: VPlan.h:1853
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition: VPlan.h:2216
An analysis for type-inference for VPValues.
Definition: VPlanAnalysis.h:39
LLVMContext & getContext()
Return the LLVMContext used by the analysis.
Definition: VPlanAnalysis.h:59
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:211
operand_range operands()
Definition: VPlanValue.h:286
void setOperand(unsigned I, VPValue *New)
Definition: VPlanValue.h:266
operand_iterator op_end()
Definition: VPlanValue.h:284
operand_iterator op_begin()
Definition: VPlanValue.h:282
VPValue * getOperand(unsigned N) const
Definition: VPlanValue.h:261
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
Definition: VPlanValue.h:84
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition: VPlan.cpp:116
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:1124
unsigned getNumUsers() const
Definition: VPlanValue.h:119
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
Definition: VPlanValue.h:187
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:1139
user_range users()
Definition: VPlanValue.h:147
A recipe for widening Call instructions.
Definition: VPlan.h:1218
A Recipe for widening the canonical induction variable of the vector loop.
Definition: VPlan.h:2132
const Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:2154
VPWidenCastRecipe is a recipe to create vector cast instructions.
Definition: VPlan.h:1180
A recipe for handling GEP instructions.
Definition: VPlan.h:1280
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
Definition: VPlan.h:1395
A Recipe for widening load/store operations.
Definition: VPlan.h:1940
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:1154
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2481
VPBasicBlock * getEntry()
Definition: VPlan.h:2575
VPValue * getTripCount() const
The trip count of the original loop.
Definition: VPlan.h:2579
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition: VPlan.h:2585
VPValue * getVPValueOrAddLiveIn(Value *V)
Gets the VPValue for V or adds a new live-in (if none exists yet) for V.
Definition: VPlan.h:2644
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:2680
bool hasVF(ElementCount VF)
Definition: VPlan.h:2606
bool hasUF(unsigned UF) const
Definition: VPlan.h:2610
void setVF(ElementCount VF)
Definition: VPlan.h:2600
bool hasScalarVFOnly() const
Definition: VPlan.h:2608
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
Definition: VPlan.h:2688
void setUF(unsigned UF)
Definition: VPlan.h:2612
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 ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition: TypeSize.h:169
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
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
Definition: VPlan.cpp:1263
bool onlyFirstLaneUsed(VPValue *Def)
Returns true if only the first lane of Def is used.
Definition: VPlan.cpp:1258
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:1726
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:1733
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1651
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:132
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:1740
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:1303
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:1753
@ 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:1550
A recipe for widening select instructions.
Definition: VPlan.h:1251
static void createAndOptimizeReplicateRegions(VPlan &Plan)
Wrap predicated VPReplicateRecipes with a mask operand in an if-then region block and remove the mask...
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.