Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
Warning:line 329, column 20
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name VPlanTransforms.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Transforms/Vectorize -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Transforms/Vectorize -I include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-10-03-140002-15933-1 -x c++ /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
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 "llvm/ADT/PostOrderIterator.h"
16#include "llvm/ADT/SetVector.h"
17#include "llvm/Analysis/IVDescriptors.h"
18#include "llvm/Analysis/VectorUtils.h"
19#include "llvm/IR/Intrinsics.h"
20
21using namespace llvm;
22
23void VPlanTransforms::VPInstructionsToVPRecipes(
24 Loop *OrigLoop, VPlanPtr &Plan,
25 function_ref<const InductionDescriptor *(PHINode *)>
26 GetIntOrFpInductionDescriptor,
27 SmallPtrSetImpl<Instruction *> &DeadInstructions, ScalarEvolution &SE,
28 const TargetLibraryInfo &TLI) {
29
30 ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>>
31 RPOT(Plan->getEntry());
32 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
33 VPRecipeBase *Term = VPBB->getTerminator();
34 auto EndIter = Term ? Term->getIterator() : VPBB->end();
35 // Introduce each ingredient into VPlan.
36 for (VPRecipeBase &Ingredient :
37 make_early_inc_range(make_range(VPBB->begin(), EndIter))) {
38
39 VPValue *VPV = Ingredient.getVPSingleValue();
40 Instruction *Inst = cast<Instruction>(VPV->getUnderlyingValue());
41 if (DeadInstructions.count(Inst)) {
42 VPValue DummyValue;
43 VPV->replaceAllUsesWith(&DummyValue);
44 Ingredient.eraseFromParent();
45 continue;
46 }
47
48 VPRecipeBase *NewRecipe = nullptr;
49 if (auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
50 auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
51 if (const auto *II = GetIntOrFpInductionDescriptor(Phi)) {
52 VPValue *Start = Plan->getOrAddVPValue(II->getStartValue());
53 VPValue *Step =
54 vputils::getOrCreateVPValueForSCEVExpr(*Plan, II->getStep(), SE);
55 NewRecipe =
56 new VPWidenIntOrFpInductionRecipe(Phi, Start, Step, *II, true);
57 } else {
58 Plan->addVPValue(Phi, VPPhi);
59 continue;
60 }
61 } else {
62 assert(isa<VPInstruction>(&Ingredient) &&(static_cast <bool> (isa<VPInstruction>(&Ingredient
) && "only VPInstructions expected here") ? void (0) :
__assert_fail ("isa<VPInstruction>(&Ingredient) && \"only VPInstructions expected here\""
, "llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp", 63, __extension__
__PRETTY_FUNCTION__))
63 "only VPInstructions expected here")(static_cast <bool> (isa<VPInstruction>(&Ingredient
) && "only VPInstructions expected here") ? void (0) :
__assert_fail ("isa<VPInstruction>(&Ingredient) && \"only VPInstructions expected here\""
, "llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp", 63, __extension__
__PRETTY_FUNCTION__))
;
64 assert(!isa<PHINode>(Inst) && "phis should be handled above")(static_cast <bool> (!isa<PHINode>(Inst) &&
"phis should be handled above") ? void (0) : __assert_fail (
"!isa<PHINode>(Inst) && \"phis should be handled above\""
, "llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp", 64, __extension__
__PRETTY_FUNCTION__))
;
65 // Create VPWidenMemoryInstructionRecipe for loads and stores.
66 if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
67 NewRecipe = new VPWidenMemoryInstructionRecipe(
68 *Load, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)),
69 nullptr /*Mask*/, false /*Consecutive*/, false /*Reverse*/);
70 } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
71 NewRecipe = new VPWidenMemoryInstructionRecipe(
72 *Store, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)),
73 Plan->getOrAddVPValue(Store->getValueOperand()), nullptr /*Mask*/,
74 false /*Consecutive*/, false /*Reverse*/);
75 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
76 NewRecipe = new VPWidenGEPRecipe(
77 GEP, Plan->mapToVPValues(GEP->operands()), OrigLoop);
78 } else if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
79 NewRecipe =
80 new VPWidenCallRecipe(*CI, Plan->mapToVPValues(CI->args()),
81 getVectorIntrinsicIDForCall(CI, &TLI));
82 } else if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
83 bool InvariantCond =
84 SE.isLoopInvariant(SE.getSCEV(SI->getOperand(0)), OrigLoop);
85 NewRecipe = new VPWidenSelectRecipe(
86 *SI, Plan->mapToVPValues(SI->operands()), InvariantCond);
87 } else {
88 NewRecipe =
89 new VPWidenRecipe(*Inst, Plan->mapToVPValues(Inst->operands()));
90 }
91 }
92
93 NewRecipe->insertBefore(&Ingredient);
94 if (NewRecipe->getNumDefinedValues() == 1)
95 VPV->replaceAllUsesWith(NewRecipe->getVPSingleValue());
96 else
97 assert(NewRecipe->getNumDefinedValues() == 0 &&(static_cast <bool> (NewRecipe->getNumDefinedValues(
) == 0 && "Only recpies with zero or one defined values expected"
) ? void (0) : __assert_fail ("NewRecipe->getNumDefinedValues() == 0 && \"Only recpies with zero or one defined values expected\""
, "llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp", 98, __extension__
__PRETTY_FUNCTION__))
98 "Only recpies with zero or one defined values expected")(static_cast <bool> (NewRecipe->getNumDefinedValues(
) == 0 && "Only recpies with zero or one defined values expected"
) ? void (0) : __assert_fail ("NewRecipe->getNumDefinedValues() == 0 && \"Only recpies with zero or one defined values expected\""
, "llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp", 98, __extension__
__PRETTY_FUNCTION__))
;
99 Ingredient.eraseFromParent();
100 Plan->removeVPValueFor(Inst);
101 for (auto *Def : NewRecipe->definedValues()) {
102 Plan->addVPValue(Inst, Def);
103 }
104 }
105 }
106}
107
108bool VPlanTransforms::sinkScalarOperands(VPlan &Plan) {
109 auto Iter = depth_first(
110 VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry()));
111 bool Changed = false;
112 // First, collect the operands of all predicated replicate recipes as seeds
113 // for sinking.
114 SetVector<std::pair<VPBasicBlock *, VPValue *>> WorkList;
115 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
116 for (auto &Recipe : *VPBB) {
117 auto *RepR = dyn_cast<VPReplicateRecipe>(&Recipe);
118 if (!RepR || !RepR->isPredicated())
119 continue;
120 for (VPValue *Op : RepR->operands())
121 WorkList.insert(std::make_pair(RepR->getParent(), Op));
122 }
123 }
124
125 // Try to sink each replicate recipe in the worklist.
126 while (!WorkList.empty()) {
127 VPBasicBlock *SinkTo;
128 VPValue *C;
129 std::tie(SinkTo, C) = WorkList.pop_back_val();
130 auto *SinkCandidate = dyn_cast_or_null<VPReplicateRecipe>(C->Def);
131 if (!SinkCandidate || SinkCandidate->isUniform() ||
132 SinkCandidate->getParent() == SinkTo ||
133 SinkCandidate->mayHaveSideEffects() ||
134 SinkCandidate->mayReadOrWriteMemory())
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. At the moment, we identify such UAV's by looking for the
142 // address operands of widened memory recipes.
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 auto *WidenI = dyn_cast<VPWidenMemoryInstructionRecipe>(UI);
151 if (WidenI && WidenI->getAddr() == SinkCandidate) {
152 NeedsDuplicating = true;
153 return true;
154 }
155 return false;
156 };
157 if (!all_of(SinkCandidate->users(), CanSinkWithUser))
158 continue;
159
160 if (NeedsDuplicating) {
161 Instruction *I = cast<Instruction>(SinkCandidate->getUnderlyingValue());
162 auto *Clone =
163 new VPReplicateRecipe(I, SinkCandidate->operands(), true, false);
164 // TODO: add ".cloned" suffix to name of Clone's VPValue.
165
166 Clone->insertBefore(SinkCandidate);
167 SmallVector<VPUser *, 4> Users(SinkCandidate->users());
168 for (auto *U : Users) {
169 auto *UI = cast<VPRecipeBase>(U);
170 if (UI->getParent() == SinkTo)
171 continue;
172
173 for (unsigned Idx = 0; Idx != UI->getNumOperands(); Idx++) {
174 if (UI->getOperand(Idx) != SinkCandidate)
175 continue;
176 UI->setOperand(Idx, Clone);
177 }
178 }
179 }
180 SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi());
181 for (VPValue *Op : SinkCandidate->operands())
182 WorkList.insert(std::make_pair(SinkTo, Op));
183 Changed = true;
184 }
185 return Changed;
186}
187
188/// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return
189/// the mask.
190VPValue *getPredicatedMask(VPRegionBlock *R) {
191 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
192 if (!EntryBB || EntryBB->size() != 1 ||
193 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
194 return nullptr;
195
196 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
197}
198
199/// If \p R is a triangle region, return the 'then' block of the triangle.
200static VPBasicBlock *getPredicatedThenBlock(VPRegionBlock *R) {
201 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
202 if (EntryBB->getNumSuccessors() != 2)
203 return nullptr;
204
205 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
206 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
207 if (!Succ0 || !Succ1)
208 return nullptr;
209
210 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
211 return nullptr;
212 if (Succ0->getSingleSuccessor() == Succ1)
213 return Succ0;
214 if (Succ1->getSingleSuccessor() == Succ0)
215 return Succ1;
216 return nullptr;
217}
218
219bool VPlanTransforms::mergeReplicateRegions(VPlan &Plan) {
220 SetVector<VPRegionBlock *> DeletedRegions;
221 bool Changed = false;
222
223 // Collect region blocks to process up-front, to avoid iterator invalidation
224 // issues while merging regions.
225 SmallVector<VPRegionBlock *, 8> CandidateRegions(
226 VPBlockUtils::blocksOnly<VPRegionBlock>(depth_first(
227 VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry()))));
228
229 // Check if Base is a predicated triangle, followed by an empty block,
230 // followed by another predicate triangle. If that's the case, move the
231 // recipes from the first to the second triangle.
232 for (VPRegionBlock *Region1 : CandidateRegions) {
233 if (DeletedRegions.contains(Region1))
234 continue;
235 auto *MiddleBasicBlock =
236 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
237 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
238 continue;
239
240 auto *Region2 =
241 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
242 if (!Region2)
243 continue;
244
245 VPValue *Mask1 = getPredicatedMask(Region1);
246 VPValue *Mask2 = getPredicatedMask(Region2);
247 if (!Mask1 || Mask1 != Mask2)
248 continue;
249 VPBasicBlock *Then1 = getPredicatedThenBlock(Region1);
250 VPBasicBlock *Then2 = getPredicatedThenBlock(Region2);
251 if (!Then1 || !Then2)
252 continue;
253
254 assert(Mask1 && Mask2 && "both region must have conditions")(static_cast <bool> (Mask1 && Mask2 && "both region must have conditions"
) ? void (0) : __assert_fail ("Mask1 && Mask2 && \"both region must have conditions\""
, "llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp", 254, __extension__
__PRETTY_FUNCTION__))
;
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 SmallVector<VPUser *> Users(Phi1ToMoveV->users());
275 for (VPUser *U : Users) {
276 auto *UI = dyn_cast<VPRecipeBase>(U);
277 if (!UI || UI->getParent() != Then2)
278 continue;
279 for (unsigned I = 0, E = U->getNumOperands(); I != E; ++I) {
280 if (Phi1ToMoveV != U->getOperand(I))
281 continue;
282 U->setOperand(I, PredInst1);
283 }
284 }
285
286 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
287 }
288
289 // Finally, remove the first region.
290 for (VPBlockBase *Pred : make_early_inc_range(Region1->getPredecessors())) {
291 VPBlockUtils::disconnectBlocks(Pred, Region1);
292 VPBlockUtils::connectBlocks(Pred, MiddleBasicBlock);
293 }
294 VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock);
295 DeletedRegions.insert(Region1);
296 }
297
298 for (VPRegionBlock *ToDelete : DeletedRegions)
299 delete ToDelete;
300 return Changed;
301}
302
303void VPlanTransforms::removeRedundantInductionCasts(VPlan &Plan) {
304 for (auto &Phi : Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
305 auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
1
Assuming the object is a 'CastReturnType'
306 if (!IV
1.1
'IV' is non-null
|| IV->getTruncInst())
2
Taking false branch
307 continue;
308
309 // A sequence of IR Casts has potentially been recorded for IV, which
310 // *must be bypassed* when the IV is vectorized, because the vectorized IV
311 // will produce the desired casted value. This sequence forms a def-use
312 // chain and is provided in reverse order, ending with the cast that uses
313 // the IV phi. Search for the recipe of the last cast in the chain and
314 // replace it with the original IV. Note that only the final cast is
315 // expected to have users outside the cast-chain and the dead casts left
316 // over will be cleaned up later.
317 auto &Casts = IV->getInductionDescriptor().getCastInsts();
318 VPValue *FindMyCast = IV;
319 for (Instruction *IRCast : reverse(Casts)) {
320 VPRecipeBase *FoundUserCast = nullptr;
3
'FoundUserCast' initialized to a null pointer value
321 for (auto *U : FindMyCast->users()) {
4
Assuming '__begin3' is equal to '__end3'
322 auto *UserCast = cast<VPRecipeBase>(U);
323 if (UserCast->getNumDefinedValues() == 1 &&
324 UserCast->getVPSingleValue()->getUnderlyingValue() == IRCast) {
325 FoundUserCast = UserCast;
326 break;
327 }
328 }
329 FindMyCast = FoundUserCast->getVPSingleValue();
5
Called C++ object pointer is null
330 }
331 FindMyCast->replaceAllUsesWith(IV);
332 }
333}
334
335void VPlanTransforms::removeRedundantCanonicalIVs(VPlan &Plan) {
336 VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
337 VPWidenCanonicalIVRecipe *WidenNewIV = nullptr;
338 for (VPUser *U : CanonicalIV->users()) {
339 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
340 if (WidenNewIV)
341 break;
342 }
343
344 if (!WidenNewIV)
345 return;
346
347 VPBasicBlock *HeaderVPBB = Plan.getVectorLoopRegion()->getEntryBasicBlock();
348 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
349 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
350
351 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() ||
352 WidenOriginalIV->getScalarType() != WidenNewIV->getScalarType())
353 continue;
354
355 // Replace WidenNewIV with WidenOriginalIV if WidenOriginalIV provides
356 // everything WidenNewIV's users need. That is, WidenOriginalIV will
357 // generate a vector phi or all users of WidenNewIV demand the first lane
358 // only.
359 if (WidenOriginalIV->needsVectorIV() ||
360 vputils::onlyFirstLaneUsed(WidenNewIV)) {
361 WidenNewIV->replaceAllUsesWith(WidenOriginalIV);
362 WidenNewIV->eraseFromParent();
363 return;
364 }
365 }
366}
367
368void VPlanTransforms::removeDeadRecipes(VPlan &Plan) {
369 ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>>
370 RPOT(Plan.getEntry());
371
372 for (VPBasicBlock *VPBB : reverse(VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT))) {
373 // The recipes in the block are processed in reverse order, to catch chains
374 // of dead recipes.
375 for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) {
376 if (R.mayHaveSideEffects() || any_of(R.definedValues(), [](VPValue *V) {
377 return V->getNumUsers() > 0;
378 }))
379 continue;
380 R.eraseFromParent();
381 }
382 }
383}
384
385void VPlanTransforms::optimizeInductions(VPlan &Plan, ScalarEvolution &SE) {
386 SmallVector<VPRecipeBase *> ToRemove;
387 VPBasicBlock *HeaderVPBB = Plan.getVectorLoopRegion()->getEntryBasicBlock();
388 bool HasOnlyVectorVFs = !Plan.hasVF(ElementCount::getFixed(1));
389 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
390 auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
391 if (!IV)
392 continue;
393 if (HasOnlyVectorVFs &&
394 none_of(IV->users(), [IV](VPUser *U) { return U->usesScalars(IV); }))
395 continue;
396
397 const InductionDescriptor &ID = IV->getInductionDescriptor();
398 VPValue *Step =
399 vputils::getOrCreateVPValueForSCEVExpr(Plan, ID.getStep(), SE);
400 Instruction *TruncI = IV->getTruncInst();
401 VPScalarIVStepsRecipe *Steps = new VPScalarIVStepsRecipe(
402 IV->getPHINode()->getType(), ID, Plan.getCanonicalIV(),
403 IV->getStartValue(), Step, TruncI ? TruncI->getType() : nullptr);
404 HeaderVPBB->insert(Steps, HeaderVPBB->getFirstNonPhi());
405
406 // Update scalar users of IV to use Step instead. Use SetVector to ensure
407 // the list of users doesn't contain duplicates.
408 SetVector<VPUser *> Users(IV->user_begin(), IV->user_end());
409 for (VPUser *U : Users) {
410 if (HasOnlyVectorVFs && !U->usesScalars(IV))
411 continue;
412 for (unsigned I = 0, E = U->getNumOperands(); I != E; I++) {
413 if (U->getOperand(I) != IV)
414 continue;
415 U->setOperand(I, Steps);
416 }
417 }
418 }
419}
420
421void VPlanTransforms::removeRedundantExpandSCEVRecipes(VPlan &Plan) {
422 DenseMap<const SCEV *, VPValue *> SCEV2VPV;
423
424 for (VPRecipeBase &R :
425 make_early_inc_range(*Plan.getEntry()->getEntryBasicBlock())) {
426 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
427 if (!ExpR)
428 continue;
429
430 auto I = SCEV2VPV.insert({ExpR->getSCEV(), ExpR});
431 if (I.second)
432 continue;
433 ExpR->replaceAllUsesWith(I.first->second);
434 ExpR->eraseFromParent();
435 }
436}