Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Analysis/IVDescriptors.cpp
Warning:line 1232, column 8
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 IVDescriptors.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/Analysis -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Analysis -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/Analysis/IVDescriptors.cpp
1//===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===//
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// This file "describes" induction and recurrence variables.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/IVDescriptors.h"
14#include "llvm/Analysis/DemandedBits.h"
15#include "llvm/Analysis/LoopInfo.h"
16#include "llvm/Analysis/ScalarEvolution.h"
17#include "llvm/Analysis/ScalarEvolutionExpressions.h"
18#include "llvm/Analysis/ValueTracking.h"
19#include "llvm/IR/Dominators.h"
20#include "llvm/IR/Instructions.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/PatternMatch.h"
23#include "llvm/IR/ValueHandle.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/KnownBits.h"
26
27#include <set>
28
29using namespace llvm;
30using namespace llvm::PatternMatch;
31
32#define DEBUG_TYPE"iv-descriptors" "iv-descriptors"
33
34bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
35 SmallPtrSetImpl<Instruction *> &Set) {
36 for (const Use &Use : I->operands())
37 if (!Set.count(dyn_cast<Instruction>(Use)))
38 return false;
39 return true;
40}
41
42bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) {
43 switch (Kind) {
44 default:
45 break;
46 case RecurKind::Add:
47 case RecurKind::Mul:
48 case RecurKind::Or:
49 case RecurKind::And:
50 case RecurKind::Xor:
51 case RecurKind::SMax:
52 case RecurKind::SMin:
53 case RecurKind::UMax:
54 case RecurKind::UMin:
55 case RecurKind::SelectICmp:
56 case RecurKind::SelectFCmp:
57 return true;
58 }
59 return false;
60}
61
62bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) {
63 return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
64}
65
66/// Determines if Phi may have been type-promoted. If Phi has a single user
67/// that ANDs the Phi with a type mask, return the user. RT is updated to
68/// account for the narrower bit width represented by the mask, and the AND
69/// instruction is added to CI.
70static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
71 SmallPtrSetImpl<Instruction *> &Visited,
72 SmallPtrSetImpl<Instruction *> &CI) {
73 if (!Phi->hasOneUse())
74 return Phi;
75
76 const APInt *M = nullptr;
77 Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
78
79 // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
80 // with a new integer type of the corresponding bit width.
81 if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
82 int32_t Bits = (*M + 1).exactLogBase2();
83 if (Bits > 0) {
84 RT = IntegerType::get(Phi->getContext(), Bits);
85 Visited.insert(Phi);
86 CI.insert(J);
87 return J;
88 }
89 }
90 return Phi;
91}
92
93/// Compute the minimal bit width needed to represent a reduction whose exit
94/// instruction is given by Exit.
95static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
96 DemandedBits *DB,
97 AssumptionCache *AC,
98 DominatorTree *DT) {
99 bool IsSigned = false;
100 const DataLayout &DL = Exit->getModule()->getDataLayout();
101 uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
102
103 if (DB) {
104 // Use the demanded bits analysis to determine the bits that are live out
105 // of the exit instruction, rounding up to the nearest power of two. If the
106 // use of demanded bits results in a smaller bit width, we know the value
107 // must be positive (i.e., IsSigned = false), because if this were not the
108 // case, the sign bit would have been demanded.
109 auto Mask = DB->getDemandedBits(Exit);
110 MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
111 }
112
113 if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
114 // If demanded bits wasn't able to limit the bit width, we can try to use
115 // value tracking instead. This can be the case, for example, if the value
116 // may be negative.
117 auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
118 auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
119 MaxBitWidth = NumTypeBits - NumSignBits;
120 KnownBits Bits = computeKnownBits(Exit, DL);
121 if (!Bits.isNonNegative()) {
122 // If the value is not known to be non-negative, we set IsSigned to true,
123 // meaning that we will use sext instructions instead of zext
124 // instructions to restore the original type.
125 IsSigned = true;
126 // Make sure at at least one sign bit is included in the result, so it
127 // will get properly sign-extended.
128 ++MaxBitWidth;
129 }
130 }
131 if (!isPowerOf2_64(MaxBitWidth))
132 MaxBitWidth = NextPowerOf2(MaxBitWidth);
133
134 return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
135 IsSigned);
136}
137
138/// Collect cast instructions that can be ignored in the vectorizer's cost
139/// model, given a reduction exit value and the minimal type in which the
140// reduction can be represented. Also search casts to the recurrence type
141// to find the minimum width used by the recurrence.
142static void collectCastInstrs(Loop *TheLoop, Instruction *Exit,
143 Type *RecurrenceType,
144 SmallPtrSetImpl<Instruction *> &Casts,
145 unsigned &MinWidthCastToRecurTy) {
146
147 SmallVector<Instruction *, 8> Worklist;
148 SmallPtrSet<Instruction *, 8> Visited;
149 Worklist.push_back(Exit);
150 MinWidthCastToRecurTy = -1U;
151
152 while (!Worklist.empty()) {
153 Instruction *Val = Worklist.pop_back_val();
154 Visited.insert(Val);
155 if (auto *Cast = dyn_cast<CastInst>(Val)) {
156 if (Cast->getSrcTy() == RecurrenceType) {
157 // If the source type of a cast instruction is equal to the recurrence
158 // type, it will be eliminated, and should be ignored in the vectorizer
159 // cost model.
160 Casts.insert(Cast);
161 continue;
162 }
163 if (Cast->getDestTy() == RecurrenceType) {
164 // The minimum width used by the recurrence is found by checking for
165 // casts on its operands. The minimum width is used by the vectorizer
166 // when finding the widest type for in-loop reductions without any
167 // loads/stores.
168 MinWidthCastToRecurTy = std::min<unsigned>(
169 MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits());
170 continue;
171 }
172 }
173 // Add all operands to the work list if they are loop-varying values that
174 // we haven't yet visited.
175 for (Value *O : cast<User>(Val)->operands())
176 if (auto *I = dyn_cast<Instruction>(O))
177 if (TheLoop->contains(I) && !Visited.count(I))
178 Worklist.push_back(I);
179 }
180}
181
182// Check if a given Phi node can be recognized as an ordered reduction for
183// vectorizing floating point operations without unsafe math.
184static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst,
185 Instruction *Exit, PHINode *Phi) {
186 // Currently only FAdd and FMulAdd are supported.
187 if (Kind != RecurKind::FAdd && Kind != RecurKind::FMulAdd)
188 return false;
189
190 if (Kind == RecurKind::FAdd && Exit->getOpcode() != Instruction::FAdd)
191 return false;
192
193 if (Kind == RecurKind::FMulAdd &&
194 !RecurrenceDescriptor::isFMulAddIntrinsic(Exit))
195 return false;
196
197 // Ensure the exit instruction has only one user other than the reduction PHI
198 if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3))
199 return false;
200
201 // The only pattern accepted is the one in which the reduction PHI
202 // is used as one of the operands of the exit instruction
203 auto *Op0 = Exit->getOperand(0);
204 auto *Op1 = Exit->getOperand(1);
205 if (Kind == RecurKind::FAdd && Op0 != Phi && Op1 != Phi)
206 return false;
207 if (Kind == RecurKind::FMulAdd && Exit->getOperand(2) != Phi)
208 return false;
209
210 LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: Found an ordered reduction: Phi: "
<< *Phi << ", ExitInst: " << *Exit <<
"\n"; } } while (false)
211 << ", ExitInst: " << *Exit << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: Found an ordered reduction: Phi: "
<< *Phi << ", ExitInst: " << *Exit <<
"\n"; } } while (false)
;
212
213 return true;
214}
215
216bool RecurrenceDescriptor::AddReductionVar(
217 PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF,
218 RecurrenceDescriptor &RedDes, DemandedBits *DB, AssumptionCache *AC,
219 DominatorTree *DT, ScalarEvolution *SE) {
220 if (Phi->getNumIncomingValues() != 2)
221 return false;
222
223 // Reduction variables are only found in the loop header block.
224 if (Phi->getParent() != TheLoop->getHeader())
225 return false;
226
227 // Obtain the reduction start value from the value that comes from the loop
228 // preheader.
229 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
230
231 // ExitInstruction is the single value which is used outside the loop.
232 // We only allow for a single reduction value to be used outside the loop.
233 // This includes users of the reduction, variables (which form a cycle
234 // which ends in the phi node).
235 Instruction *ExitInstruction = nullptr;
236
237 // Variable to keep last visited store instruction. By the end of the
238 // algorithm this variable will be either empty or having intermediate
239 // reduction value stored in invariant address.
240 StoreInst *IntermediateStore = nullptr;
241
242 // Indicates that we found a reduction operation in our scan.
243 bool FoundReduxOp = false;
244
245 // We start with the PHI node and scan for all of the users of this
246 // instruction. All users must be instructions that can be used as reduction
247 // variables (such as ADD). We must have a single out-of-block user. The cycle
248 // must include the original PHI.
249 bool FoundStartPHI = false;
250
251 // To recognize min/max patterns formed by a icmp select sequence, we store
252 // the number of instruction we saw from the recognized min/max pattern,
253 // to make sure we only see exactly the two instructions.
254 unsigned NumCmpSelectPatternInst = 0;
255 InstDesc ReduxDesc(false, nullptr);
256
257 // Data used for determining if the recurrence has been type-promoted.
258 Type *RecurrenceType = Phi->getType();
259 SmallPtrSet<Instruction *, 4> CastInsts;
260 unsigned MinWidthCastToRecurrenceType;
261 Instruction *Start = Phi;
262 bool IsSigned = false;
263
264 SmallPtrSet<Instruction *, 8> VisitedInsts;
265 SmallVector<Instruction *, 8> Worklist;
266
267 // Return early if the recurrence kind does not match the type of Phi. If the
268 // recurrence kind is arithmetic, we attempt to look through AND operations
269 // resulting from the type promotion performed by InstCombine. Vector
270 // operations are not limited to the legal integer widths, so we may be able
271 // to evaluate the reduction in the narrower width.
272 if (RecurrenceType->isFloatingPointTy()) {
273 if (!isFloatingPointRecurrenceKind(Kind))
274 return false;
275 } else if (RecurrenceType->isIntegerTy()) {
276 if (!isIntegerRecurrenceKind(Kind))
277 return false;
278 if (!isMinMaxRecurrenceKind(Kind))
279 Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
280 } else {
281 // Pointer min/max may exist, but it is not supported as a reduction op.
282 return false;
283 }
284
285 Worklist.push_back(Start);
286 VisitedInsts.insert(Start);
287
288 // Start with all flags set because we will intersect this with the reduction
289 // flags from all the reduction operations.
290 FastMathFlags FMF = FastMathFlags::getFast();
291
292 // The first instruction in the use-def chain of the Phi node that requires
293 // exact floating point operations.
294 Instruction *ExactFPMathInst = nullptr;
295
296 // A value in the reduction can be used:
297 // - By the reduction:
298 // - Reduction operation:
299 // - One use of reduction value (safe).
300 // - Multiple use of reduction value (not safe).
301 // - PHI:
302 // - All uses of the PHI must be the reduction (safe).
303 // - Otherwise, not safe.
304 // - By instructions outside of the loop (safe).
305 // * One value may have several outside users, but all outside
306 // uses must be of the same value.
307 // - By store instructions with a loop invariant address (safe with
308 // the following restrictions):
309 // * If there are several stores, all must have the same address.
310 // * Final value should be stored in that loop invariant address.
311 // - By an instruction that is not part of the reduction (not safe).
312 // This is either:
313 // * An instruction type other than PHI or the reduction operation.
314 // * A PHI in the header other than the initial PHI.
315 while (!Worklist.empty()) {
316 Instruction *Cur = Worklist.pop_back_val();
317
318 // Store instructions are allowed iff it is the store of the reduction
319 // value to the same loop invariant memory location.
320 if (auto *SI = dyn_cast<StoreInst>(Cur)) {
321 if (!SE) {
322 LLVM_DEBUG(dbgs() << "Store instructions are not processed without "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Store instructions are not processed without "
<< "Scalar Evolution Analysis\n"; } } while (false)
323 << "Scalar Evolution Analysis\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Store instructions are not processed without "
<< "Scalar Evolution Analysis\n"; } } while (false)
;
324 return false;
325 }
326
327 const SCEV *PtrScev = SE->getSCEV(SI->getPointerOperand());
328 // Check it is the same address as previous stores
329 if (IntermediateStore) {
330 const SCEV *OtherScev =
331 SE->getSCEV(IntermediateStore->getPointerOperand());
332
333 if (OtherScev != PtrScev) {
334 LLVM_DEBUG(dbgs() << "Storing reduction value to different addresses "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses "
<< "inside the loop: " << *SI->getPointerOperand
() << " and " << *IntermediateStore->getPointerOperand
() << '\n'; } } while (false)
335 << "inside the loop: " << *SI->getPointerOperand()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses "
<< "inside the loop: " << *SI->getPointerOperand
() << " and " << *IntermediateStore->getPointerOperand
() << '\n'; } } while (false)
336 << " and "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses "
<< "inside the loop: " << *SI->getPointerOperand
() << " and " << *IntermediateStore->getPointerOperand
() << '\n'; } } while (false)
337 << *IntermediateStore->getPointerOperand() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses "
<< "inside the loop: " << *SI->getPointerOperand
() << " and " << *IntermediateStore->getPointerOperand
() << '\n'; } } while (false)
;
338 return false;
339 }
340 }
341
342 // Check the pointer is loop invariant
343 if (!SE->isLoopInvariant(PtrScev, TheLoop)) {
344 LLVM_DEBUG(dbgs() << "Storing reduction value to non-uniform address "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address "
<< "inside the loop: " << *SI->getPointerOperand
() << '\n'; } } while (false)
345 << "inside the loop: " << *SI->getPointerOperand()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address "
<< "inside the loop: " << *SI->getPointerOperand
() << '\n'; } } while (false)
346 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address "
<< "inside the loop: " << *SI->getPointerOperand
() << '\n'; } } while (false)
;
347 return false;
348 }
349
350 // IntermediateStore is always the last store in the loop.
351 IntermediateStore = SI;
352 continue;
353 }
354
355 // No Users.
356 // If the instruction has no users then this is a broken chain and can't be
357 // a reduction variable.
358 if (Cur->use_empty())
359 return false;
360
361 bool IsAPhi = isa<PHINode>(Cur);
362
363 // A header PHI use other than the original PHI.
364 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
365 return false;
366
367 // Reductions of instructions such as Div, and Sub is only possible if the
368 // LHS is the reduction variable.
369 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
370 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
371 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
372 return false;
373
374 // Any reduction instruction must be of one of the allowed kinds. We ignore
375 // the starting value (the Phi or an AND instruction if the Phi has been
376 // type-promoted).
377 if (Cur != Start) {
378 ReduxDesc =
379 isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF);
380 ExactFPMathInst = ExactFPMathInst == nullptr
381 ? ReduxDesc.getExactFPMathInst()
382 : ExactFPMathInst;
383 if (!ReduxDesc.isRecurrence())
384 return false;
385 // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
386 if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi) {
387 FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags();
388 if (auto *Sel = dyn_cast<SelectInst>(ReduxDesc.getPatternInst())) {
389 // Accept FMF on either fcmp or select of a min/max idiom.
390 // TODO: This is a hack to work-around the fact that FMF may not be
391 // assigned/propagated correctly. If that problem is fixed or we
392 // standardize on fmin/fmax via intrinsics, this can be removed.
393 if (auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
394 CurFMF |= FCmp->getFastMathFlags();
395 }
396 FMF &= CurFMF;
397 }
398 // Update this reduction kind if we matched a new instruction.
399 // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind'
400 // state accurate while processing the worklist?
401 if (ReduxDesc.getRecKind() != RecurKind::None)
402 Kind = ReduxDesc.getRecKind();
403 }
404
405 bool IsASelect = isa<SelectInst>(Cur);
406
407 // A conditional reduction operation must only have 2 or less uses in
408 // VisitedInsts.
409 if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) &&
410 hasMultipleUsesOf(Cur, VisitedInsts, 2))
411 return false;
412
413 // A reduction operation must only have one use of the reduction value.
414 if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) &&
415 !isSelectCmpRecurrenceKind(Kind) &&
416 hasMultipleUsesOf(Cur, VisitedInsts, 1))
417 return false;
418
419 // All inputs to a PHI node must be a reduction value.
420 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
421 return false;
422
423 if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectICmp) &&
424 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
425 ++NumCmpSelectPatternInst;
426 if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectFCmp) &&
427 (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
428 ++NumCmpSelectPatternInst;
429
430 // Check whether we found a reduction operator.
431 FoundReduxOp |= !IsAPhi && Cur != Start;
432
433 // Process users of current instruction. Push non-PHI nodes after PHI nodes
434 // onto the stack. This way we are going to have seen all inputs to PHI
435 // nodes once we get to them.
436 SmallVector<Instruction *, 8> NonPHIs;
437 SmallVector<Instruction *, 8> PHIs;
438 for (User *U : Cur->users()) {
439 Instruction *UI = cast<Instruction>(U);
440
441 // If the user is a call to llvm.fmuladd then the instruction can only be
442 // the final operand.
443 if (isFMulAddIntrinsic(UI))
444 if (Cur == UI->getOperand(0) || Cur == UI->getOperand(1))
445 return false;
446
447 // Check if we found the exit user.
448 BasicBlock *Parent = UI->getParent();
449 if (!TheLoop->contains(Parent)) {
450 // If we already know this instruction is used externally, move on to
451 // the next user.
452 if (ExitInstruction == Cur)
453 continue;
454
455 // Exit if you find multiple values used outside or if the header phi
456 // node is being used. In this case the user uses the value of the
457 // previous iteration, in which case we would loose "VF-1" iterations of
458 // the reduction operation if we vectorize.
459 if (ExitInstruction != nullptr || Cur == Phi)
460 return false;
461
462 // The instruction used by an outside user must be the last instruction
463 // before we feed back to the reduction phi. Otherwise, we loose VF-1
464 // operations on the value.
465 if (!is_contained(Phi->operands(), Cur))
466 return false;
467
468 ExitInstruction = Cur;
469 continue;
470 }
471
472 // Process instructions only once (termination). Each reduction cycle
473 // value must only be used once, except by phi nodes and min/max
474 // reductions which are represented as a cmp followed by a select.
475 InstDesc IgnoredVal(false, nullptr);
476 if (VisitedInsts.insert(UI).second) {
477 if (isa<PHINode>(UI)) {
478 PHIs.push_back(UI);
479 } else {
480 StoreInst *SI = dyn_cast<StoreInst>(UI);
481 if (SI && SI->getPointerOperand() == Cur) {
482 // Reduction variable chain can only be stored somewhere but it
483 // can't be used as an address.
484 return false;
485 }
486 NonPHIs.push_back(UI);
487 }
488 } else if (!isa<PHINode>(UI) &&
489 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
490 !isa<SelectInst>(UI)) ||
491 (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
492 !isSelectCmpPattern(TheLoop, Phi, UI, IgnoredVal)
493 .isRecurrence() &&
494 !isMinMaxPattern(UI, Kind, IgnoredVal).isRecurrence())))
495 return false;
496
497 // Remember that we completed the cycle.
498 if (UI == Phi)
499 FoundStartPHI = true;
500 }
501 Worklist.append(PHIs.begin(), PHIs.end());
502 Worklist.append(NonPHIs.begin(), NonPHIs.end());
503 }
504
505 // This means we have seen one but not the other instruction of the
506 // pattern or more than just a select and cmp. Zero implies that we saw a
507 // llvm.min/max intrinsic, which is always OK.
508 if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2 &&
509 NumCmpSelectPatternInst != 0)
510 return false;
511
512 if (isSelectCmpRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1)
513 return false;
514
515 if (IntermediateStore) {
516 // Check that stored value goes to the phi node again. This way we make sure
517 // that the value stored in IntermediateStore is indeed the final reduction
518 // value.
519 if (!is_contained(Phi->operands(), IntermediateStore->getValueOperand())) {
520 LLVM_DEBUG(dbgs() << "Not a final reduction value stored: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Not a final reduction value stored: "
<< *IntermediateStore << '\n'; } } while (false)
521 << *IntermediateStore << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Not a final reduction value stored: "
<< *IntermediateStore << '\n'; } } while (false)
;
522 return false;
523 }
524
525 // If there is an exit instruction it's value should be stored in
526 // IntermediateStore
527 if (ExitInstruction &&
528 IntermediateStore->getValueOperand() != ExitInstruction) {
529 LLVM_DEBUG(dbgs() << "Last store Instruction of reduction value does not "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not "
"store last calculated value of the reduction: " << *IntermediateStore
<< '\n'; } } while (false)
530 "store last calculated value of the reduction: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not "
"store last calculated value of the reduction: " << *IntermediateStore
<< '\n'; } } while (false)
531 << *IntermediateStore << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not "
"store last calculated value of the reduction: " << *IntermediateStore
<< '\n'; } } while (false)
;
532 return false;
533 }
534
535 // If all uses are inside the loop (intermediate stores), then the
536 // reduction value after the loop will be the one used in the last store.
537 if (!ExitInstruction)
538 ExitInstruction = cast<Instruction>(IntermediateStore->getValueOperand());
539 }
540
541 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
542 return false;
543
544 const bool IsOrdered =
545 checkOrderedReduction(Kind, ExactFPMathInst, ExitInstruction, Phi);
546
547 if (Start != Phi) {
548 // If the starting value is not the same as the phi node, we speculatively
549 // looked through an 'and' instruction when evaluating a potential
550 // arithmetic reduction to determine if it may have been type-promoted.
551 //
552 // We now compute the minimal bit width that is required to represent the
553 // reduction. If this is the same width that was indicated by the 'and', we
554 // can represent the reduction in the smaller type. The 'and' instruction
555 // will be eliminated since it will essentially be a cast instruction that
556 // can be ignore in the cost model. If we compute a different type than we
557 // did when evaluating the 'and', the 'and' will not be eliminated, and we
558 // will end up with different kinds of operations in the recurrence
559 // expression (e.g., IntegerAND, IntegerADD). We give up if this is
560 // the case.
561 //
562 // The vectorizer relies on InstCombine to perform the actual
563 // type-shrinking. It does this by inserting instructions to truncate the
564 // exit value of the reduction to the width indicated by RecurrenceType and
565 // then extend this value back to the original width. If IsSigned is false,
566 // a 'zext' instruction will be generated; otherwise, a 'sext' will be
567 // used.
568 //
569 // TODO: We should not rely on InstCombine to rewrite the reduction in the
570 // smaller type. We should just generate a correctly typed expression
571 // to begin with.
572 Type *ComputedType;
573 std::tie(ComputedType, IsSigned) =
574 computeRecurrenceType(ExitInstruction, DB, AC, DT);
575 if (ComputedType != RecurrenceType)
576 return false;
577 }
578
579 // Collect cast instructions and the minimum width used by the recurrence.
580 // If the starting value is not the same as the phi node and the computed
581 // recurrence type is equal to the recurrence type, the recurrence expression
582 // will be represented in a narrower or wider type. If there are any cast
583 // instructions that will be unnecessary, collect them in CastsFromRecurTy.
584 // Note that the 'and' instruction was already included in this list.
585 //
586 // TODO: A better way to represent this may be to tag in some way all the
587 // instructions that are a part of the reduction. The vectorizer cost
588 // model could then apply the recurrence type to these instructions,
589 // without needing a white list of instructions to ignore.
590 // This may also be useful for the inloop reductions, if it can be
591 // kept simple enough.
592 collectCastInstrs(TheLoop, ExitInstruction, RecurrenceType, CastInsts,
593 MinWidthCastToRecurrenceType);
594
595 // We found a reduction var if we have reached the original phi node and we
596 // only have a single instruction with out-of-loop users.
597
598 // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
599 // is saved as part of the RecurrenceDescriptor.
600
601 // Save the description of this reduction variable.
602 RecurrenceDescriptor RD(RdxStart, ExitInstruction, IntermediateStore, Kind,
603 FMF, ExactFPMathInst, RecurrenceType, IsSigned,
604 IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
605 RedDes = RD;
606
607 return true;
608}
609
610// We are looking for loops that do something like this:
611// int r = 0;
612// for (int i = 0; i < n; i++) {
613// if (src[i] > 3)
614// r = 3;
615// }
616// where the reduction value (r) only has two states, in this example 0 or 3.
617// The generated LLVM IR for this type of loop will be like this:
618// for.body:
619// %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
620// ...
621// %cmp = icmp sgt i32 %5, 3
622// %spec.select = select i1 %cmp, i32 3, i32 %r
623// ...
624// In general we can support vectorization of loops where 'r' flips between
625// any two non-constants, provided they are loop invariant. The only thing
626// we actually care about at the end of the loop is whether or not any lane
627// in the selected vector is different from the start value. The final
628// across-vector reduction after the loop simply involves choosing the start
629// value if nothing changed (0 in the example above) or the other selected
630// value (3 in the example above).
631RecurrenceDescriptor::InstDesc
632RecurrenceDescriptor::isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
633 Instruction *I, InstDesc &Prev) {
634 // We must handle the select(cmp(),x,y) as a single instruction. Advance to
635 // the select.
636 CmpInst::Predicate Pred;
637 if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
638 if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
639 return InstDesc(Select, Prev.getRecKind());
640 }
641
642 // Only match select with single use cmp condition.
643 if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
644 m_Value())))
645 return InstDesc(false, I);
646
647 SelectInst *SI = cast<SelectInst>(I);
648 Value *NonPhi = nullptr;
649
650 if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))
651 NonPhi = SI->getFalseValue();
652 else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))
653 NonPhi = SI->getTrueValue();
654 else
655 return InstDesc(false, I);
656
657 // We are looking for selects of the form:
658 // select(cmp(), phi, loop_invariant) or
659 // select(cmp(), loop_invariant, phi)
660 if (!Loop->isLoopInvariant(NonPhi))
661 return InstDesc(false, I);
662
663 return InstDesc(I, isa<ICmpInst>(I->getOperand(0)) ? RecurKind::SelectICmp
664 : RecurKind::SelectFCmp);
665}
666
667RecurrenceDescriptor::InstDesc
668RecurrenceDescriptor::isMinMaxPattern(Instruction *I, RecurKind Kind,
669 const InstDesc &Prev) {
670 assert((isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) &&(static_cast <bool> ((isa<CmpInst>(I) || isa<SelectInst
>(I) || isa<CallInst>(I)) && "Expected a cmp or select or call instruction"
) ? void (0) : __assert_fail ("(isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) && \"Expected a cmp or select or call instruction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 671, __extension__ __PRETTY_FUNCTION__
))
671 "Expected a cmp or select or call instruction")(static_cast <bool> ((isa<CmpInst>(I) || isa<SelectInst
>(I) || isa<CallInst>(I)) && "Expected a cmp or select or call instruction"
) ? void (0) : __assert_fail ("(isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) && \"Expected a cmp or select or call instruction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 671, __extension__ __PRETTY_FUNCTION__
))
;
672 if (!isMinMaxRecurrenceKind(Kind))
673 return InstDesc(false, I);
674
675 // We must handle the select(cmp()) as a single instruction. Advance to the
676 // select.
677 CmpInst::Predicate Pred;
678 if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
679 if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
680 return InstDesc(Select, Prev.getRecKind());
681 }
682
683 // Only match select with single use cmp condition, or a min/max intrinsic.
684 if (!isa<IntrinsicInst>(I) &&
685 !match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
686 m_Value())))
687 return InstDesc(false, I);
688
689 // Look for a min/max pattern.
690 if (match(I, m_UMin(m_Value(), m_Value())))
691 return InstDesc(Kind == RecurKind::UMin, I);
692 if (match(I, m_UMax(m_Value(), m_Value())))
693 return InstDesc(Kind == RecurKind::UMax, I);
694 if (match(I, m_SMax(m_Value(), m_Value())))
695 return InstDesc(Kind == RecurKind::SMax, I);
696 if (match(I, m_SMin(m_Value(), m_Value())))
697 return InstDesc(Kind == RecurKind::SMin, I);
698 if (match(I, m_OrdFMin(m_Value(), m_Value())))
699 return InstDesc(Kind == RecurKind::FMin, I);
700 if (match(I, m_OrdFMax(m_Value(), m_Value())))
701 return InstDesc(Kind == RecurKind::FMax, I);
702 if (match(I, m_UnordFMin(m_Value(), m_Value())))
703 return InstDesc(Kind == RecurKind::FMin, I);
704 if (match(I, m_UnordFMax(m_Value(), m_Value())))
705 return InstDesc(Kind == RecurKind::FMax, I);
706 if (match(I, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_Value())))
707 return InstDesc(Kind == RecurKind::FMin, I);
708 if (match(I, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_Value())))
709 return InstDesc(Kind == RecurKind::FMax, I);
710
711 return InstDesc(false, I);
712}
713
714/// Returns true if the select instruction has users in the compare-and-add
715/// reduction pattern below. The select instruction argument is the last one
716/// in the sequence.
717///
718/// %sum.1 = phi ...
719/// ...
720/// %cmp = fcmp pred %0, %CFP
721/// %add = fadd %0, %sum.1
722/// %sum.2 = select %cmp, %add, %sum.1
723RecurrenceDescriptor::InstDesc
724RecurrenceDescriptor::isConditionalRdxPattern(RecurKind Kind, Instruction *I) {
725 SelectInst *SI = dyn_cast<SelectInst>(I);
726 if (!SI)
727 return InstDesc(false, I);
728
729 CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
730 // Only handle single use cases for now.
731 if (!CI || !CI->hasOneUse())
732 return InstDesc(false, I);
733
734 Value *TrueVal = SI->getTrueValue();
735 Value *FalseVal = SI->getFalseValue();
736 // Handle only when either of operands of select instruction is a PHI
737 // node for now.
738 if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
739 (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
740 return InstDesc(false, I);
741
742 Instruction *I1 =
743 isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
744 : dyn_cast<Instruction>(TrueVal);
745 if (!I1 || !I1->isBinaryOp())
746 return InstDesc(false, I);
747
748 Value *Op1, *Op2;
749 if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
750 m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
751 I1->isFast())
752 return InstDesc(Kind == RecurKind::FAdd, SI);
753
754 if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
755 return InstDesc(Kind == RecurKind::FMul, SI);
756
757 return InstDesc(false, I);
758}
759
760RecurrenceDescriptor::InstDesc
761RecurrenceDescriptor::isRecurrenceInstr(Loop *L, PHINode *OrigPhi,
762 Instruction *I, RecurKind Kind,
763 InstDesc &Prev, FastMathFlags FuncFMF) {
764 assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind)(static_cast <bool> (Prev.getRecKind() == RecurKind::None
|| Prev.getRecKind() == Kind) ? void (0) : __assert_fail ("Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind"
, "llvm/lib/Analysis/IVDescriptors.cpp", 764, __extension__ __PRETTY_FUNCTION__
))
;
765 switch (I->getOpcode()) {
766 default:
767 return InstDesc(false, I);
768 case Instruction::PHI:
769 return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
770 case Instruction::Sub:
771 case Instruction::Add:
772 return InstDesc(Kind == RecurKind::Add, I);
773 case Instruction::Mul:
774 return InstDesc(Kind == RecurKind::Mul, I);
775 case Instruction::And:
776 return InstDesc(Kind == RecurKind::And, I);
777 case Instruction::Or:
778 return InstDesc(Kind == RecurKind::Or, I);
779 case Instruction::Xor:
780 return InstDesc(Kind == RecurKind::Xor, I);
781 case Instruction::FDiv:
782 case Instruction::FMul:
783 return InstDesc(Kind == RecurKind::FMul, I,
784 I->hasAllowReassoc() ? nullptr : I);
785 case Instruction::FSub:
786 case Instruction::FAdd:
787 return InstDesc(Kind == RecurKind::FAdd, I,
788 I->hasAllowReassoc() ? nullptr : I);
789 case Instruction::Select:
790 if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul)
791 return isConditionalRdxPattern(Kind, I);
792 [[fallthrough]];
793 case Instruction::FCmp:
794 case Instruction::ICmp:
795 case Instruction::Call:
796 if (isSelectCmpRecurrenceKind(Kind))
797 return isSelectCmpPattern(L, OrigPhi, I, Prev);
798 if (isIntMinMaxRecurrenceKind(Kind) ||
799 (((FuncFMF.noNaNs() && FuncFMF.noSignedZeros()) ||
800 (isa<FPMathOperator>(I) && I->hasNoNaNs() &&
801 I->hasNoSignedZeros())) &&
802 isFPMinMaxRecurrenceKind(Kind)))
803 return isMinMaxPattern(I, Kind, Prev);
804 else if (isFMulAddIntrinsic(I))
805 return InstDesc(Kind == RecurKind::FMulAdd, I,
806 I->hasAllowReassoc() ? nullptr : I);
807 return InstDesc(false, I);
808 }
809}
810
811bool RecurrenceDescriptor::hasMultipleUsesOf(
812 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
813 unsigned MaxNumUses) {
814 unsigned NumUses = 0;
815 for (const Use &U : I->operands()) {
816 if (Insts.count(dyn_cast<Instruction>(U)))
817 ++NumUses;
818 if (NumUses > MaxNumUses)
819 return true;
820 }
821
822 return false;
823}
824
825bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
826 RecurrenceDescriptor &RedDes,
827 DemandedBits *DB, AssumptionCache *AC,
828 DominatorTree *DT,
829 ScalarEvolution *SE) {
830 BasicBlock *Header = TheLoop->getHeader();
831 Function &F = *Header->getParent();
832 FastMathFlags FMF;
833 FMF.setNoNaNs(
834 F.getFnAttribute("no-nans-fp-math").getValueAsBool());
835 FMF.setNoSignedZeros(
836 F.getFnAttribute("no-signed-zeros-fp-math").getValueAsBool());
837
838 if (AddReductionVar(Phi, RecurKind::Add, TheLoop, FMF, RedDes, DB, AC, DT,
839 SE)) {
840 LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an ADD reduction PHI."
<< *Phi << "\n"; } } while (false)
;
841 return true;
842 }
843 if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, FMF, RedDes, DB, AC, DT,
844 SE)) {
845 LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a MUL reduction PHI."
<< *Phi << "\n"; } } while (false)
;
846 return true;
847 }
848 if (AddReductionVar(Phi, RecurKind::Or, TheLoop, FMF, RedDes, DB, AC, DT,
849 SE)) {
850 LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an OR reduction PHI."
<< *Phi << "\n"; } } while (false)
;
851 return true;
852 }
853 if (AddReductionVar(Phi, RecurKind::And, TheLoop, FMF, RedDes, DB, AC, DT,
854 SE)) {
855 LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an AND reduction PHI."
<< *Phi << "\n"; } } while (false)
;
856 return true;
857 }
858 if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, FMF, RedDes, DB, AC, DT,
859 SE)) {
860 LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a XOR reduction PHI."
<< *Phi << "\n"; } } while (false)
;
861 return true;
862 }
863 if (AddReductionVar(Phi, RecurKind::SMax, TheLoop, FMF, RedDes, DB, AC, DT,
864 SE)) {
865 LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a SMAX reduction PHI."
<< *Phi << "\n"; } } while (false)
;
866 return true;
867 }
868 if (AddReductionVar(Phi, RecurKind::SMin, TheLoop, FMF, RedDes, DB, AC, DT,
869 SE)) {
870 LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a SMIN reduction PHI."
<< *Phi << "\n"; } } while (false)
;
871 return true;
872 }
873 if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, FMF, RedDes, DB, AC, DT,
874 SE)) {
875 LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a UMAX reduction PHI."
<< *Phi << "\n"; } } while (false)
;
876 return true;
877 }
878 if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, FMF, RedDes, DB, AC, DT,
879 SE)) {
880 LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a UMIN reduction PHI."
<< *Phi << "\n"; } } while (false)
;
881 return true;
882 }
883 if (AddReductionVar(Phi, RecurKind::SelectICmp, TheLoop, FMF, RedDes, DB, AC,
884 DT, SE)) {
885 LLVM_DEBUG(dbgs() << "Found an integer conditional select reduction PHI."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an integer conditional select reduction PHI."
<< *Phi << "\n"; } } while (false)
886 << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an integer conditional select reduction PHI."
<< *Phi << "\n"; } } while (false)
;
887 return true;
888 }
889 if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, FMF, RedDes, DB, AC, DT,
890 SE)) {
891 LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an FMult reduction PHI."
<< *Phi << "\n"; } } while (false)
;
892 return true;
893 }
894 if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, FMF, RedDes, DB, AC, DT,
895 SE)) {
896 LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an FAdd reduction PHI."
<< *Phi << "\n"; } } while (false)
;
897 return true;
898 }
899 if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, FMF, RedDes, DB, AC, DT,
900 SE)) {
901 LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a float MAX reduction PHI."
<< *Phi << "\n"; } } while (false)
;
902 return true;
903 }
904 if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, FMF, RedDes, DB, AC, DT,
905 SE)) {
906 LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a float MIN reduction PHI."
<< *Phi << "\n"; } } while (false)
;
907 return true;
908 }
909 if (AddReductionVar(Phi, RecurKind::SelectFCmp, TheLoop, FMF, RedDes, DB, AC,
910 DT, SE)) {
911 LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a float conditional select reduction PHI."
<< " PHI." << *Phi << "\n"; } } while (false
)
912 << " PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a float conditional select reduction PHI."
<< " PHI." << *Phi << "\n"; } } while (false
)
;
913 return true;
914 }
915 if (AddReductionVar(Phi, RecurKind::FMulAdd, TheLoop, FMF, RedDes, DB, AC, DT,
916 SE)) {
917 LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an FMulAdd reduction PHI."
<< *Phi << "\n"; } } while (false)
;
918 return true;
919 }
920 // Not a reduction of known type.
921 return false;
922}
923
924bool RecurrenceDescriptor::isFixedOrderRecurrence(
925 PHINode *Phi, Loop *TheLoop,
926 MapVector<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
927
928 // Ensure the phi node is in the loop header and has two incoming values.
929 if (Phi->getParent() != TheLoop->getHeader() ||
930 Phi->getNumIncomingValues() != 2)
931 return false;
932
933 // Ensure the loop has a preheader and a single latch block. The loop
934 // vectorizer will need the latch to set up the next iteration of the loop.
935 auto *Preheader = TheLoop->getLoopPreheader();
936 auto *Latch = TheLoop->getLoopLatch();
937 if (!Preheader || !Latch)
938 return false;
939
940 // Ensure the phi node's incoming blocks are the loop preheader and latch.
941 if (Phi->getBasicBlockIndex(Preheader) < 0 ||
942 Phi->getBasicBlockIndex(Latch) < 0)
943 return false;
944
945 // Get the previous value. The previous value comes from the latch edge while
946 // the initial value comes form the preheader edge.
947 auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
948
949 // If Previous is a phi in the header, go through incoming values from the
950 // latch until we find a non-phi value. Use this as the new Previous, all uses
951 // in the header will be dominated by the original phi, but need to be moved
952 // after the non-phi previous value.
953 SmallPtrSet<PHINode *, 4> SeenPhis;
954 while (auto *PrevPhi = dyn_cast_or_null<PHINode>(Previous)) {
955 if (PrevPhi->getParent() != Phi->getParent())
956 return false;
957 if (!SeenPhis.insert(PrevPhi).second)
958 return false;
959 Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch));
960 }
961
962 if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
963 SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
964 return false;
965
966 // Ensure every user of the phi node (recursively) is dominated by the
967 // previous value. The dominance requirement ensures the loop vectorizer will
968 // not need to vectorize the initial value prior to the first iteration of the
969 // loop.
970 // TODO: Consider extending this sinking to handle memory instructions.
971
972 // We optimistically assume we can sink all users after Previous. Keep a set
973 // of instructions to sink after Previous ordered by dominance in the common
974 // basic block. It will be applied to SinkAfter if all users can be sunk.
975 auto CompareByComesBefore = [](const Instruction *A, const Instruction *B) {
976 return A->comesBefore(B);
977 };
978 std::set<Instruction *, decltype(CompareByComesBefore)> InstrsToSink(
979 CompareByComesBefore);
980
981 BasicBlock *PhiBB = Phi->getParent();
982 SmallVector<Instruction *, 8> WorkList;
983 auto TryToPushSinkCandidate = [&](Instruction *SinkCandidate) {
984 // Already sunk SinkCandidate.
985 if (SinkCandidate->getParent() == PhiBB &&
986 InstrsToSink.find(SinkCandidate) != InstrsToSink.end())
987 return true;
988
989 // Cyclic dependence.
990 if (Previous == SinkCandidate)
991 return false;
992
993 if (DT->dominates(Previous,
994 SinkCandidate)) // We already are good w/o sinking.
995 return true;
996
997 if (SinkCandidate->getParent() != PhiBB ||
998 SinkCandidate->mayHaveSideEffects() ||
999 SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
1000 return false;
1001
1002 // Avoid sinking an instruction multiple times (if multiple operands are
1003 // fixed order recurrences) by sinking once - after the latest 'previous'
1004 // instruction.
1005 auto It = SinkAfter.find(SinkCandidate);
1006 if (It != SinkAfter.end()) {
1007 auto *OtherPrev = It->second;
1008 // Find the earliest entry in the 'sink-after' chain. The last entry in
1009 // the chain is the original 'Previous' for a recurrence handled earlier.
1010 auto EarlierIt = SinkAfter.find(OtherPrev);
1011 while (EarlierIt != SinkAfter.end()) {
1012 Instruction *EarlierInst = EarlierIt->second;
1013 EarlierIt = SinkAfter.find(EarlierInst);
1014 // Bail out if order has not been preserved.
1015 if (EarlierIt != SinkAfter.end() &&
1016 !DT->dominates(EarlierInst, OtherPrev))
1017 return false;
1018 OtherPrev = EarlierInst;
1019 }
1020 // Bail out if order has not been preserved.
1021 if (OtherPrev != It->second && !DT->dominates(It->second, OtherPrev))
1022 return false;
1023
1024 // SinkCandidate is already being sunk after an instruction after
1025 // Previous. Nothing left to do.
1026 if (DT->dominates(Previous, OtherPrev) || Previous == OtherPrev)
1027 return true;
1028 // Otherwise, Previous comes after OtherPrev and SinkCandidate needs to be
1029 // re-sunk to Previous, instead of sinking to OtherPrev. Remove
1030 // SinkCandidate from SinkAfter to ensure it's insert position is updated.
1031 SinkAfter.erase(SinkCandidate);
1032 }
1033
1034 // If we reach a PHI node that is not dominated by Previous, we reached a
1035 // header PHI. No need for sinking.
1036 if (isa<PHINode>(SinkCandidate))
1037 return true;
1038
1039 // Sink User tentatively and check its users
1040 InstrsToSink.insert(SinkCandidate);
1041 WorkList.push_back(SinkCandidate);
1042 return true;
1043 };
1044
1045 WorkList.push_back(Phi);
1046 // Try to recursively sink instructions and their users after Previous.
1047 while (!WorkList.empty()) {
1048 Instruction *Current = WorkList.pop_back_val();
1049 for (User *User : Current->users()) {
1050 if (!TryToPushSinkCandidate(cast<Instruction>(User)))
1051 return false;
1052 }
1053 }
1054
1055 // We can sink all users of Phi. Update the mapping.
1056 for (Instruction *I : InstrsToSink) {
1057 SinkAfter[I] = Previous;
1058 Previous = I;
1059 }
1060 return true;
1061}
1062
1063/// This function returns the identity element (or neutral element) for
1064/// the operation K.
1065Value *RecurrenceDescriptor::getRecurrenceIdentity(RecurKind K, Type *Tp,
1066 FastMathFlags FMF) const {
1067 switch (K) {
1068 case RecurKind::Xor:
1069 case RecurKind::Add:
1070 case RecurKind::Or:
1071 // Adding, Xoring, Oring zero to a number does not change it.
1072 return ConstantInt::get(Tp, 0);
1073 case RecurKind::Mul:
1074 // Multiplying a number by 1 does not change it.
1075 return ConstantInt::get(Tp, 1);
1076 case RecurKind::And:
1077 // AND-ing a number with an all-1 value does not change it.
1078 return ConstantInt::get(Tp, -1, true);
1079 case RecurKind::FMul:
1080 // Multiplying a number by 1 does not change it.
1081 return ConstantFP::get(Tp, 1.0L);
1082 case RecurKind::FMulAdd:
1083 case RecurKind::FAdd:
1084 // Adding zero to a number does not change it.
1085 // FIXME: Ideally we should not need to check FMF for FAdd and should always
1086 // use -0.0. However, this will currently result in mixed vectors of 0.0/-0.0.
1087 // Instead, we should ensure that 1) the FMF from FAdd are propagated to the PHI
1088 // nodes where possible, and 2) PHIs with the nsz flag + -0.0 use 0.0. This would
1089 // mean we can then remove the check for noSignedZeros() below (see D98963).
1090 if (FMF.noSignedZeros())
1091 return ConstantFP::get(Tp, 0.0L);
1092 return ConstantFP::get(Tp, -0.0L);
1093 case RecurKind::UMin:
1094 return ConstantInt::get(Tp, -1);
1095 case RecurKind::UMax:
1096 return ConstantInt::get(Tp, 0);
1097 case RecurKind::SMin:
1098 return ConstantInt::get(Tp,
1099 APInt::getSignedMaxValue(Tp->getIntegerBitWidth()));
1100 case RecurKind::SMax:
1101 return ConstantInt::get(Tp,
1102 APInt::getSignedMinValue(Tp->getIntegerBitWidth()));
1103 case RecurKind::FMin:
1104 return ConstantFP::getInfinity(Tp, true);
1105 case RecurKind::FMax:
1106 return ConstantFP::getInfinity(Tp, false);
1107 case RecurKind::SelectICmp:
1108 case RecurKind::SelectFCmp:
1109 return getRecurrenceStartValue();
1110 break;
1111 default:
1112 llvm_unreachable("Unknown recurrence kind")::llvm::llvm_unreachable_internal("Unknown recurrence kind", "llvm/lib/Analysis/IVDescriptors.cpp"
, 1112)
;
1113 }
1114}
1115
1116unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
1117 switch (Kind) {
1118 case RecurKind::Add:
1119 return Instruction::Add;
1120 case RecurKind::Mul:
1121 return Instruction::Mul;
1122 case RecurKind::Or:
1123 return Instruction::Or;
1124 case RecurKind::And:
1125 return Instruction::And;
1126 case RecurKind::Xor:
1127 return Instruction::Xor;
1128 case RecurKind::FMul:
1129 return Instruction::FMul;
1130 case RecurKind::FMulAdd:
1131 case RecurKind::FAdd:
1132 return Instruction::FAdd;
1133 case RecurKind::SMax:
1134 case RecurKind::SMin:
1135 case RecurKind::UMax:
1136 case RecurKind::UMin:
1137 case RecurKind::SelectICmp:
1138 return Instruction::ICmp;
1139 case RecurKind::FMax:
1140 case RecurKind::FMin:
1141 case RecurKind::SelectFCmp:
1142 return Instruction::FCmp;
1143 default:
1144 llvm_unreachable("Unknown recurrence operation")::llvm::llvm_unreachable_internal("Unknown recurrence operation"
, "llvm/lib/Analysis/IVDescriptors.cpp", 1144)
;
1145 }
1146}
1147
1148SmallVector<Instruction *, 4>
1149RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {
1150 SmallVector<Instruction *, 4> ReductionOperations;
1151 unsigned RedOp = getOpcode(Kind);
1152
1153 // Search down from the Phi to the LoopExitInstr, looking for instructions
1154 // with a single user of the correct type for the reduction.
1155
1156 // Note that we check that the type of the operand is correct for each item in
1157 // the chain, including the last (the loop exit value). This can come up from
1158 // sub, which would otherwise be treated as an add reduction. MinMax also need
1159 // to check for a pair of icmp/select, for which we use getNextInstruction and
1160 // isCorrectOpcode functions to step the right number of instruction, and
1161 // check the icmp/select pair.
1162 // FIXME: We also do not attempt to look through Select's yet, which might
1163 // be part of the reduction chain, or attempt to looks through And's to find a
1164 // smaller bitwidth. Subs are also currently not allowed (which are usually
1165 // treated as part of a add reduction) as they are expected to generally be
1166 // more expensive than out-of-loop reductions, and need to be costed more
1167 // carefully.
1168 unsigned ExpectedUses = 1;
1169 if (RedOp
0.1
'RedOp' is equal to ICmp
== Instruction::ICmp || RedOp == Instruction::FCmp)
1170 ExpectedUses = 2;
1171
1172 auto getNextInstruction = [&](Instruction *Cur) -> Instruction * {
1173 for (auto *User : Cur->users()) {
1174 Instruction *UI = cast<Instruction>(User);
1175 if (isa<PHINode>(UI))
1176 continue;
1177 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1178 // We are expecting a icmp/select pair, which we go to the next select
1179 // instruction if we can. We already know that Cur has 2 uses.
1180 if (isa<SelectInst>(UI))
1181 return UI;
1182 continue;
1183 }
1184 return UI;
1185 }
1186 return nullptr;
1187 };
1188 auto isCorrectOpcode = [&](Instruction *Cur) {
1189 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1190 Value *LHS, *RHS;
1191 return SelectPatternResult::isMinOrMax(
1192 matchSelectPattern(Cur, LHS, RHS).Flavor);
1193 }
1194 // Recognize a call to the llvm.fmuladd intrinsic.
1195 if (isFMulAddIntrinsic(Cur))
1196 return true;
1197
1198 return Cur->getOpcode() == RedOp;
1199 };
1200
1201 // Attempt to look through Phis which are part of the reduction chain
1202 unsigned ExtraPhiUses = 0;
1203 Instruction *RdxInstr = LoopExitInstr;
1204 if (auto ExitPhi
1.1
'ExitPhi' is non-null
= dyn_cast<PHINode>(LoopExitInstr)) {
1
Assuming field 'LoopExitInstr' is a 'CastReturnType'
2
Taking true branch
1205 if (ExitPhi->getNumIncomingValues() != 2)
3
Assuming the condition is false
4
Taking false branch
1206 return {};
1207
1208 Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0));
5
Assuming the object is not a 'CastReturnType'
1209 Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1));
1210
1211 Instruction *Chain = nullptr;
1212 if (Inc0 == Phi)
6
Assuming 'Inc0' is equal to 'Phi'
7
Taking true branch
1213 Chain = Inc1;
1214 else if (Inc1 == Phi)
1215 Chain = Inc0;
1216 else
1217 return {};
1218
1219 RdxInstr = Chain;
1220 ExtraPhiUses = 1;
1221 }
1222
1223 // The loop exit instruction we check first (as a quick test) but add last. We
1224 // check the opcode is correct (and dont allow them to be Subs) and that they
1225 // have expected to have the expected number of uses. They will have one use
1226 // from the phi and one from a LCSSA value, no matter the type.
1227 if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->hasNUses(2))
8
Assuming the condition is false
9
Taking false branch
1228 return {};
1229
1230 // Check that the Phi has one (or two for min/max) uses, plus an extra use
1231 // for conditional reductions.
1232 if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses))
10
Called C++ object pointer is null
1233 return {};
1234
1235 Instruction *Cur = getNextInstruction(Phi);
1236
1237 // Each other instruction in the chain should have the expected number of uses
1238 // and be the correct opcode.
1239 while (Cur != RdxInstr) {
1240 if (!Cur || !isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses))
1241 return {};
1242
1243 ReductionOperations.push_back(Cur);
1244 Cur = getNextInstruction(Cur);
1245 }
1246
1247 ReductionOperations.push_back(Cur);
1248 return ReductionOperations;
1249}
1250
1251InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
1252 const SCEV *Step, BinaryOperator *BOp,
1253 Type *ElementType,
1254 SmallVectorImpl<Instruction *> *Casts)
1255 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp),
1256 ElementType(ElementType) {
1257 assert(IK != IK_NoInduction && "Not an induction")(static_cast <bool> (IK != IK_NoInduction && "Not an induction"
) ? void (0) : __assert_fail ("IK != IK_NoInduction && \"Not an induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1257, __extension__ __PRETTY_FUNCTION__
))
;
1258
1259 // Start value type should match the induction kind and the value
1260 // itself should not be null.
1261 assert(StartValue && "StartValue is null")(static_cast <bool> (StartValue && "StartValue is null"
) ? void (0) : __assert_fail ("StartValue && \"StartValue is null\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1261, __extension__ __PRETTY_FUNCTION__
))
;
1262 assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&(static_cast <bool> ((IK != IK_PtrInduction || StartValue
->getType()->isPointerTy()) && "StartValue is not a pointer for pointer induction"
) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && \"StartValue is not a pointer for pointer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1263, __extension__ __PRETTY_FUNCTION__
))
1263 "StartValue is not a pointer for pointer induction")(static_cast <bool> ((IK != IK_PtrInduction || StartValue
->getType()->isPointerTy()) && "StartValue is not a pointer for pointer induction"
) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && \"StartValue is not a pointer for pointer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1263, __extension__ __PRETTY_FUNCTION__
))
;
1264 assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&(static_cast <bool> ((IK != IK_IntInduction || StartValue
->getType()->isIntegerTy()) && "StartValue is not an integer for integer induction"
) ? void (0) : __assert_fail ("(IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && \"StartValue is not an integer for integer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1265, __extension__ __PRETTY_FUNCTION__
))
1265 "StartValue is not an integer for integer induction")(static_cast <bool> ((IK != IK_IntInduction || StartValue
->getType()->isIntegerTy()) && "StartValue is not an integer for integer induction"
) ? void (0) : __assert_fail ("(IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && \"StartValue is not an integer for integer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1265, __extension__ __PRETTY_FUNCTION__
))
;
1266
1267 // Check the Step Value. It should be non-zero integer value.
1268 assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&(static_cast <bool> ((!getConstIntStepValue() || !getConstIntStepValue
()->isZero()) && "Step value is zero") ? void (0) :
__assert_fail ("(!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && \"Step value is zero\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1269, __extension__ __PRETTY_FUNCTION__
))
1269 "Step value is zero")(static_cast <bool> ((!getConstIntStepValue() || !getConstIntStepValue
()->isZero()) && "Step value is zero") ? void (0) :
__assert_fail ("(!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && \"Step value is zero\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1269, __extension__ __PRETTY_FUNCTION__
))
;
1270
1271 assert((IK != IK_PtrInduction || getConstIntStepValue()) &&(static_cast <bool> ((IK != IK_PtrInduction || getConstIntStepValue
()) && "Step value should be constant for pointer induction"
) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || getConstIntStepValue()) && \"Step value should be constant for pointer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1272, __extension__ __PRETTY_FUNCTION__
))
1272 "Step value should be constant for pointer induction")(static_cast <bool> ((IK != IK_PtrInduction || getConstIntStepValue
()) && "Step value should be constant for pointer induction"
) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || getConstIntStepValue()) && \"Step value should be constant for pointer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1272, __extension__ __PRETTY_FUNCTION__
))
;
1273 assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&(static_cast <bool> ((IK == IK_FpInduction || Step->
getType()->isIntegerTy()) && "StepValue is not an integer"
) ? void (0) : __assert_fail ("(IK == IK_FpInduction || Step->getType()->isIntegerTy()) && \"StepValue is not an integer\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1274, __extension__ __PRETTY_FUNCTION__
))
1274 "StepValue is not an integer")(static_cast <bool> ((IK == IK_FpInduction || Step->
getType()->isIntegerTy()) && "StepValue is not an integer"
) ? void (0) : __assert_fail ("(IK == IK_FpInduction || Step->getType()->isIntegerTy()) && \"StepValue is not an integer\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1274, __extension__ __PRETTY_FUNCTION__
))
;
1275
1276 assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&(static_cast <bool> ((IK != IK_FpInduction || Step->
getType()->isFloatingPointTy()) && "StepValue is not FP for FpInduction"
) ? void (0) : __assert_fail ("(IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && \"StepValue is not FP for FpInduction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1277, __extension__ __PRETTY_FUNCTION__
))
1277 "StepValue is not FP for FpInduction")(static_cast <bool> ((IK != IK_FpInduction || Step->
getType()->isFloatingPointTy()) && "StepValue is not FP for FpInduction"
) ? void (0) : __assert_fail ("(IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && \"StepValue is not FP for FpInduction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1277, __extension__ __PRETTY_FUNCTION__
))
;
1278 assert((IK != IK_FpInduction ||(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
&& (InductionBinOp->getOpcode() == Instruction::FAdd
|| InductionBinOp->getOpcode() == Instruction::FSub))) &&
"Binary opcode should be specified for FP induction") ? void
(0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1282, __extension__ __PRETTY_FUNCTION__
))
1279 (InductionBinOp &&(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
&& (InductionBinOp->getOpcode() == Instruction::FAdd
|| InductionBinOp->getOpcode() == Instruction::FSub))) &&
"Binary opcode should be specified for FP induction") ? void
(0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1282, __extension__ __PRETTY_FUNCTION__
))
1280 (InductionBinOp->getOpcode() == Instruction::FAdd ||(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
&& (InductionBinOp->getOpcode() == Instruction::FAdd
|| InductionBinOp->getOpcode() == Instruction::FSub))) &&
"Binary opcode should be specified for FP induction") ? void
(0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1282, __extension__ __PRETTY_FUNCTION__
))
1281 InductionBinOp->getOpcode() == Instruction::FSub))) &&(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
&& (InductionBinOp->getOpcode() == Instruction::FAdd
|| InductionBinOp->getOpcode() == Instruction::FSub))) &&
"Binary opcode should be specified for FP induction") ? void
(0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1282, __extension__ __PRETTY_FUNCTION__
))
1282 "Binary opcode should be specified for FP induction")(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
&& (InductionBinOp->getOpcode() == Instruction::FAdd
|| InductionBinOp->getOpcode() == Instruction::FSub))) &&
"Binary opcode should be specified for FP induction") ? void
(0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1282, __extension__ __PRETTY_FUNCTION__
))
;
1283
1284 if (IK == IK_PtrInduction)
1285 assert(ElementType && "Pointer induction must have element type")(static_cast <bool> (ElementType && "Pointer induction must have element type"
) ? void (0) : __assert_fail ("ElementType && \"Pointer induction must have element type\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1285, __extension__ __PRETTY_FUNCTION__
))
;
1286 else
1287 assert(!ElementType && "Non-pointer induction cannot have element type")(static_cast <bool> (!ElementType && "Non-pointer induction cannot have element type"
) ? void (0) : __assert_fail ("!ElementType && \"Non-pointer induction cannot have element type\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1287, __extension__ __PRETTY_FUNCTION__
))
;
1288
1289 if (Casts) {
1290 for (auto &Inst : *Casts) {
1291 RedundantCasts.push_back(Inst);
1292 }
1293 }
1294}
1295
1296ConstantInt *InductionDescriptor::getConstIntStepValue() const {
1297 if (isa<SCEVConstant>(Step))
1298 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
1299 return nullptr;
1300}
1301
1302bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
1303 ScalarEvolution *SE,
1304 InductionDescriptor &D) {
1305
1306 // Here we only handle FP induction variables.
1307 assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type")(static_cast <bool> (Phi->getType()->isFloatingPointTy
() && "Unexpected Phi type") ? void (0) : __assert_fail
("Phi->getType()->isFloatingPointTy() && \"Unexpected Phi type\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1307, __extension__ __PRETTY_FUNCTION__
))
;
1308
1309 if (TheLoop->getHeader() != Phi->getParent())
1310 return false;
1311
1312 // The loop may have multiple entrances or multiple exits; we can analyze
1313 // this phi if it has a unique entry value and a unique backedge value.
1314 if (Phi->getNumIncomingValues() != 2)
1315 return false;
1316 Value *BEValue = nullptr, *StartValue = nullptr;
1317 if (TheLoop->contains(Phi->getIncomingBlock(0))) {
1318 BEValue = Phi->getIncomingValue(0);
1319 StartValue = Phi->getIncomingValue(1);
1320 } else {
1321 assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&(static_cast <bool> (TheLoop->contains(Phi->getIncomingBlock
(1)) && "Unexpected Phi node in the loop") ? void (0)
: __assert_fail ("TheLoop->contains(Phi->getIncomingBlock(1)) && \"Unexpected Phi node in the loop\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1322, __extension__ __PRETTY_FUNCTION__
))
1322 "Unexpected Phi node in the loop")(static_cast <bool> (TheLoop->contains(Phi->getIncomingBlock
(1)) && "Unexpected Phi node in the loop") ? void (0)
: __assert_fail ("TheLoop->contains(Phi->getIncomingBlock(1)) && \"Unexpected Phi node in the loop\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1322, __extension__ __PRETTY_FUNCTION__
))
;
1323 BEValue = Phi->getIncomingValue(1);
1324 StartValue = Phi->getIncomingValue(0);
1325 }
1326
1327 BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
1328 if (!BOp)
1329 return false;
1330
1331 Value *Addend = nullptr;
1332 if (BOp->getOpcode() == Instruction::FAdd) {
1333 if (BOp->getOperand(0) == Phi)
1334 Addend = BOp->getOperand(1);
1335 else if (BOp->getOperand(1) == Phi)
1336 Addend = BOp->getOperand(0);
1337 } else if (BOp->getOpcode() == Instruction::FSub)
1338 if (BOp->getOperand(0) == Phi)
1339 Addend = BOp->getOperand(1);
1340
1341 if (!Addend)
1342 return false;
1343
1344 // The addend should be loop invariant
1345 if (auto *I = dyn_cast<Instruction>(Addend))
1346 if (TheLoop->contains(I))
1347 return false;
1348
1349 // FP Step has unknown SCEV
1350 const SCEV *Step = SE->getUnknown(Addend);
1351 D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
1352 return true;
1353}
1354
1355/// This function is called when we suspect that the update-chain of a phi node
1356/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
1357/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
1358/// predicate P under which the SCEV expression for the phi can be the
1359/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
1360/// cast instructions that are involved in the update-chain of this induction.
1361/// A caller that adds the required runtime predicate can be free to drop these
1362/// cast instructions, and compute the phi using \p AR (instead of some scev
1363/// expression with casts).
1364///
1365/// For example, without a predicate the scev expression can take the following
1366/// form:
1367/// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
1368///
1369/// It corresponds to the following IR sequence:
1370/// %for.body:
1371/// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
1372/// %casted_phi = "ExtTrunc i64 %x"
1373/// %add = add i64 %casted_phi, %step
1374///
1375/// where %x is given in \p PN,
1376/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
1377/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
1378/// several forms, for example, such as:
1379/// ExtTrunc1: %casted_phi = and %x, 2^n-1
1380/// or:
1381/// ExtTrunc2: %t = shl %x, m
1382/// %casted_phi = ashr %t, m
1383///
1384/// If we are able to find such sequence, we return the instructions
1385/// we found, namely %casted_phi and the instructions on its use-def chain up
1386/// to the phi (not including the phi).
1387static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
1388 const SCEVUnknown *PhiScev,
1389 const SCEVAddRecExpr *AR,
1390 SmallVectorImpl<Instruction *> &CastInsts) {
1391
1392 assert(CastInsts.empty() && "CastInsts is expected to be empty.")(static_cast <bool> (CastInsts.empty() && "CastInsts is expected to be empty."
) ? void (0) : __assert_fail ("CastInsts.empty() && \"CastInsts is expected to be empty.\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1392, __extension__ __PRETTY_FUNCTION__
))
;
1393 auto *PN = cast<PHINode>(PhiScev->getValue());
1394 assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression")(static_cast <bool> (PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression"
) ? void (0) : __assert_fail ("PSE.getSCEV(PN) == AR && \"Unexpected phi node SCEV expression\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1394, __extension__ __PRETTY_FUNCTION__
))
;
1395 const Loop *L = AR->getLoop();
1396
1397 // Find any cast instructions that participate in the def-use chain of
1398 // PhiScev in the loop.
1399 // FORNOW/TODO: We currently expect the def-use chain to include only
1400 // two-operand instructions, where one of the operands is an invariant.
1401 // createAddRecFromPHIWithCasts() currently does not support anything more
1402 // involved than that, so we keep the search simple. This can be
1403 // extended/generalized as needed.
1404
1405 auto getDef = [&](const Value *Val) -> Value * {
1406 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
1407 if (!BinOp)
1408 return nullptr;
1409 Value *Op0 = BinOp->getOperand(0);
1410 Value *Op1 = BinOp->getOperand(1);
1411 Value *Def = nullptr;
1412 if (L->isLoopInvariant(Op0))
1413 Def = Op1;
1414 else if (L->isLoopInvariant(Op1))
1415 Def = Op0;
1416 return Def;
1417 };
1418
1419 // Look for the instruction that defines the induction via the
1420 // loop backedge.
1421 BasicBlock *Latch = L->getLoopLatch();
1422 if (!Latch)
1423 return false;
1424 Value *Val = PN->getIncomingValueForBlock(Latch);
1425 if (!Val)
1426 return false;
1427
1428 // Follow the def-use chain until the induction phi is reached.
1429 // If on the way we encounter a Value that has the same SCEV Expr as the
1430 // phi node, we can consider the instructions we visit from that point
1431 // as part of the cast-sequence that can be ignored.
1432 bool InCastSequence = false;
1433 auto *Inst = dyn_cast<Instruction>(Val);
1434 while (Val != PN) {
1435 // If we encountered a phi node other than PN, or if we left the loop,
1436 // we bail out.
1437 if (!Inst || !L->contains(Inst)) {
1438 return false;
1439 }
1440 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
1441 if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
1442 InCastSequence = true;
1443 if (InCastSequence) {
1444 // Only the last instruction in the cast sequence is expected to have
1445 // uses outside the induction def-use chain.
1446 if (!CastInsts.empty())
1447 if (!Inst->hasOneUse())
1448 return false;
1449 CastInsts.push_back(Inst);
1450 }
1451 Val = getDef(Val);
1452 if (!Val)
1453 return false;
1454 Inst = dyn_cast<Instruction>(Val);
1455 }
1456
1457 return InCastSequence;
1458}
1459
1460bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
1461 PredicatedScalarEvolution &PSE,
1462 InductionDescriptor &D, bool Assume) {
1463 Type *PhiTy = Phi->getType();
1464
1465 // Handle integer and pointer inductions variables.
1466 // Now we handle also FP induction but not trying to make a
1467 // recurrent expression from the PHI node in-place.
1468
1469 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
1470 !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
1471 return false;
1472
1473 if (PhiTy->isFloatingPointTy())
1474 return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
1475
1476 const SCEV *PhiScev = PSE.getSCEV(Phi);
1477 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1478
1479 // We need this expression to be an AddRecExpr.
1480 if (Assume && !AR)
1481 AR = PSE.getAsAddRec(Phi);
1482
1483 if (!AR) {
1484 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: PHI is not a poly recurrence.\n"
; } } while (false)
;
1485 return false;
1486 }
1487
1488 // Record any Cast instructions that participate in the induction update
1489 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1490 // If we started from an UnknownSCEV, and managed to build an addRecurrence
1491 // only after enabling Assume with PSCEV, this means we may have encountered
1492 // cast instructions that required adding a runtime check in order to
1493 // guarantee the correctness of the AddRecurrence respresentation of the
1494 // induction.
1495 if (PhiScev != AR && SymbolicPhi) {
1496 SmallVector<Instruction *, 2> Casts;
1497 if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1498 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1499 }
1500
1501 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1502}
1503
1504bool InductionDescriptor::isInductionPHI(
1505 PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1506 InductionDescriptor &D, const SCEV *Expr,
1507 SmallVectorImpl<Instruction *> *CastsToIgnore) {
1508 Type *PhiTy = Phi->getType();
1509 // We only handle integer and pointer inductions variables.
1510 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1511 return false;
1512
1513 // Check that the PHI is consecutive.
1514 const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1515 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1516
1517 if (!AR) {
1518 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: PHI is not a poly recurrence.\n"
; } } while (false)
;
1519 return false;
1520 }
1521
1522 if (AR->getLoop() != TheLoop) {
1523 // FIXME: We should treat this as a uniform. Unfortunately, we
1524 // don't currently know how to handled uniform PHIs.
1525 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n"
; } } while (false)
1526 dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n"
; } } while (false)
;
1527 return false;
1528 }
1529
1530 Value *StartValue =
1531 Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
1532
1533 BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1534 if (!Latch)
1535 return false;
1536
1537 const SCEV *Step = AR->getStepRecurrence(*SE);
1538 // Calculate the pointer stride and check if it is consecutive.
1539 // The stride may be a constant or a loop invariant integer value.
1540 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1541 if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1542 return false;
1543
1544 if (PhiTy->isIntegerTy()) {
1545 BinaryOperator *BOp =
1546 dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
1547 D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1548 /* ElementType */ nullptr, CastsToIgnore);
1549 return true;
1550 }
1551
1552 assert(PhiTy->isPointerTy() && "The PHI must be a pointer")(static_cast <bool> (PhiTy->isPointerTy() &&
"The PHI must be a pointer") ? void (0) : __assert_fail ("PhiTy->isPointerTy() && \"The PHI must be a pointer\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1552, __extension__ __PRETTY_FUNCTION__
))
;
1553 // Pointer induction should be a constant.
1554 if (!ConstStep)
1555 return false;
1556
1557 // Always use i8 element type for opaque pointer inductions.
1558 PointerType *PtrTy = cast<PointerType>(PhiTy);
1559 Type *ElementType = PtrTy->isOpaque()
1560 ? Type::getInt8Ty(PtrTy->getContext())
1561 : PtrTy->getNonOpaquePointerElementType();
1562 if (!ElementType->isSized())
1563 return false;
1564
1565 ConstantInt *CV = ConstStep->getValue();
1566 const DataLayout &DL = Phi->getModule()->getDataLayout();
1567 TypeSize TySize = DL.getTypeAllocSize(ElementType);
1568 // TODO: We could potentially support this for scalable vectors if we can
1569 // prove at compile time that the constant step is always a multiple of
1570 // the scalable type.
1571 if (TySize.isZero() || TySize.isScalable())
1572 return false;
1573
1574 int64_t Size = static_cast<int64_t>(TySize.getFixedSize());
1575 int64_t CVSize = CV->getSExtValue();
1576 if (CVSize % Size)
1577 return false;
1578 auto *StepValue =
1579 SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1580 D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue,
1581 /* BinOp */ nullptr, ElementType);
1582 return true;
1583}