Line data Source code
1 : //===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file "describes" induction and recurrence variables.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "llvm/Analysis/IVDescriptors.h"
15 : #include "llvm/ADT/ScopeExit.h"
16 : #include "llvm/Analysis/AliasAnalysis.h"
17 : #include "llvm/Analysis/BasicAliasAnalysis.h"
18 : #include "llvm/Analysis/GlobalsModRef.h"
19 : #include "llvm/Analysis/InstructionSimplify.h"
20 : #include "llvm/Analysis/LoopInfo.h"
21 : #include "llvm/Analysis/LoopPass.h"
22 : #include "llvm/Analysis/MustExecute.h"
23 : #include "llvm/Analysis/ScalarEvolution.h"
24 : #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
25 : #include "llvm/Analysis/ScalarEvolutionExpander.h"
26 : #include "llvm/Analysis/ScalarEvolutionExpressions.h"
27 : #include "llvm/Analysis/TargetTransformInfo.h"
28 : #include "llvm/Analysis/ValueTracking.h"
29 : #include "llvm/IR/DomTreeUpdater.h"
30 : #include "llvm/IR/Dominators.h"
31 : #include "llvm/IR/Instructions.h"
32 : #include "llvm/IR/Module.h"
33 : #include "llvm/IR/PatternMatch.h"
34 : #include "llvm/IR/ValueHandle.h"
35 : #include "llvm/Pass.h"
36 : #include "llvm/Support/Debug.h"
37 : #include "llvm/Support/KnownBits.h"
38 :
39 : using namespace llvm;
40 : using namespace llvm::PatternMatch;
41 :
42 : #define DEBUG_TYPE "iv-descriptors"
43 :
44 119 : bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
45 : SmallPtrSetImpl<Instruction *> &Set) {
46 355 : for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
47 209 : if (!Set.count(dyn_cast<Instruction>(*Use)))
48 : return false;
49 : return true;
50 : }
51 :
52 27552 : bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
53 27552 : switch (Kind) {
54 : default:
55 : break;
56 : case RK_IntegerAdd:
57 : case RK_IntegerMult:
58 : case RK_IntegerOr:
59 : case RK_IntegerAnd:
60 : case RK_IntegerXor:
61 : case RK_IntegerMinMax:
62 : return true;
63 : }
64 8876 : return false;
65 : }
66 :
67 953 : bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
68 953 : return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
69 : }
70 :
71 18004 : bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
72 : switch (Kind) {
73 : default:
74 : break;
75 : case RK_IntegerAdd:
76 : case RK_IntegerMult:
77 : case RK_FloatAdd:
78 : case RK_FloatMult:
79 : return true;
80 : }
81 : return false;
82 : }
83 :
84 : /// Determines if Phi may have been type-promoted. If Phi has a single user
85 : /// that ANDs the Phi with a type mask, return the user. RT is updated to
86 : /// account for the narrower bit width represented by the mask, and the AND
87 : /// instruction is added to CI.
88 6362 : static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
89 : SmallPtrSetImpl<Instruction *> &Visited,
90 : SmallPtrSetImpl<Instruction *> &CI) {
91 6332 : if (!Phi->hasOneUse())
92 : return Phi;
93 :
94 2327 : const APInt *M = nullptr;
95 2327 : Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
96 :
97 : // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
98 : // with a new integer type of the corresponding bit width.
99 2327 : if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
100 130 : int32_t Bits = (*M + 1).exactLogBase2();
101 65 : if (Bits > 0) {
102 18 : RT = IntegerType::get(Phi->getContext(), Bits);
103 18 : Visited.insert(Phi);
104 18 : CI.insert(J);
105 18 : return J;
106 : }
107 : }
108 : return Phi;
109 : }
110 :
111 : /// Compute the minimal bit width needed to represent a reduction whose exit
112 : /// instruction is given by Exit.
113 9 : static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
114 : DemandedBits *DB,
115 : AssumptionCache *AC,
116 : DominatorTree *DT) {
117 : bool IsSigned = false;
118 9 : const DataLayout &DL = Exit->getModule()->getDataLayout();
119 9 : uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
120 :
121 9 : if (DB) {
122 : // Use the demanded bits analysis to determine the bits that are live out
123 : // of the exit instruction, rounding up to the nearest power of two. If the
124 : // use of demanded bits results in a smaller bit width, we know the value
125 : // must be positive (i.e., IsSigned = false), because if this were not the
126 : // case, the sign bit would have been demanded.
127 9 : auto Mask = DB->getDemandedBits(Exit);
128 9 : MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
129 : }
130 :
131 9 : if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
132 : // If demanded bits wasn't able to limit the bit width, we can try to use
133 : // value tracking instead. This can be the case, for example, if the value
134 : // may be negative.
135 3 : auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
136 3 : auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
137 3 : MaxBitWidth = NumTypeBits - NumSignBits;
138 6 : KnownBits Bits = computeKnownBits(Exit, DL);
139 3 : if (!Bits.isNonNegative()) {
140 : // If the value is not known to be non-negative, we set IsSigned to true,
141 : // meaning that we will use sext instructions instead of zext
142 : // instructions to restore the original type.
143 : IsSigned = true;
144 1 : if (!Bits.isNegative())
145 : // If the value is not known to be negative, we don't known what the
146 : // upper bit is, and therefore, we don't know what kind of extend we
147 : // will need. In this case, just increase the bit width by one bit and
148 : // use sext.
149 1 : ++MaxBitWidth;
150 : }
151 : }
152 : if (!isPowerOf2_64(MaxBitWidth))
153 : MaxBitWidth = NextPowerOf2(MaxBitWidth);
154 :
155 9 : return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
156 9 : IsSigned);
157 : }
158 :
159 : /// Collect cast instructions that can be ignored in the vectorizer's cost
160 : /// model, given a reduction exit value and the minimal type in which the
161 : /// reduction can be represented.
162 6 : static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
163 : Type *RecurrenceType,
164 : SmallPtrSetImpl<Instruction *> &Casts) {
165 :
166 : SmallVector<Instruction *, 8> Worklist;
167 : SmallPtrSet<Instruction *, 8> Visited;
168 6 : Worklist.push_back(Exit);
169 :
170 39 : while (!Worklist.empty()) {
171 : Instruction *Val = Worklist.pop_back_val();
172 33 : Visited.insert(Val);
173 : if (auto *Cast = dyn_cast<CastInst>(Val))
174 6 : if (Cast->getSrcTy() == RecurrenceType) {
175 : // If the source type of a cast instruction is equal to the recurrence
176 : // type, it will be eliminated, and should be ignored in the vectorizer
177 : // cost model.
178 4 : Casts.insert(Cast);
179 4 : continue;
180 : }
181 :
182 : // Add all operands to the work list if they are loop-varying values that
183 : // we haven't yet visited.
184 83 : for (Value *O : cast<User>(Val)->operands())
185 54 : if (auto *I = dyn_cast<Instruction>(O))
186 35 : if (TheLoop->contains(I) && !Visited.count(I))
187 27 : Worklist.push_back(I);
188 : }
189 6 : }
190 :
191 27552 : bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
192 : Loop *TheLoop, bool HasFunNoNaNAttr,
193 : RecurrenceDescriptor &RedDes,
194 : DemandedBits *DB,
195 : AssumptionCache *AC,
196 : DominatorTree *DT) {
197 27552 : if (Phi->getNumIncomingValues() != 2)
198 : return false;
199 :
200 : // Reduction variables are only found in the loop header block.
201 55104 : if (Phi->getParent() != TheLoop->getHeader())
202 : return false;
203 :
204 : // Obtain the reduction start value from the value that comes from the loop
205 : // preheader.
206 27552 : Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
207 :
208 : // ExitInstruction is the single value which is used outside the loop.
209 : // We only allow for a single reduction value to be used outside the loop.
210 : // This includes users of the reduction, variables (which form a cycle
211 : // which ends in the phi node).
212 : Instruction *ExitInstruction = nullptr;
213 : // Indicates that we found a reduction operation in our scan.
214 : bool FoundReduxOp = false;
215 :
216 : // We start with the PHI node and scan for all of the users of this
217 : // instruction. All users must be instructions that can be used as reduction
218 : // variables (such as ADD). We must have a single out-of-block user. The cycle
219 : // must include the original PHI.
220 : bool FoundStartPHI = false;
221 :
222 : // To recognize min/max patterns formed by a icmp select sequence, we store
223 : // the number of instruction we saw from the recognized min/max pattern,
224 : // to make sure we only see exactly the two instructions.
225 : unsigned NumCmpSelectPatternInst = 0;
226 : InstDesc ReduxDesc(false, nullptr);
227 :
228 : // Data used for determining if the recurrence has been type-promoted.
229 27552 : Type *RecurrenceType = Phi->getType();
230 : SmallPtrSet<Instruction *, 4> CastInsts;
231 27552 : Instruction *Start = Phi;
232 27552 : bool IsSigned = false;
233 :
234 : SmallPtrSet<Instruction *, 8> VisitedInsts;
235 : SmallVector<Instruction *, 8> Worklist;
236 :
237 : // Return early if the recurrence kind does not match the type of Phi. If the
238 : // recurrence kind is arithmetic, we attempt to look through AND operations
239 : // resulting from the type promotion performed by InstCombine. Vector
240 : // operations are not limited to the legal integer widths, so we may be able
241 : // to evaluate the reduction in the narrower width.
242 : if (RecurrenceType->isFloatingPointTy()) {
243 953 : if (!isFloatingPointRecurrenceKind(Kind))
244 : return false;
245 : } else {
246 26599 : if (!isIntegerRecurrenceKind(Kind))
247 : return false;
248 18004 : if (isArithmeticRecurrenceKind(Kind))
249 6362 : Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
250 : }
251 :
252 18285 : Worklist.push_back(Start);
253 18285 : VisitedInsts.insert(Start);
254 :
255 : // A value in the reduction can be used:
256 : // - By the reduction:
257 : // - Reduction operation:
258 : // - One use of reduction value (safe).
259 : // - Multiple use of reduction value (not safe).
260 : // - PHI:
261 : // - All uses of the PHI must be the reduction (safe).
262 : // - Otherwise, not safe.
263 : // - By instructions outside of the loop (safe).
264 : // * One value may have several outside users, but all outside
265 : // uses must be of the same value.
266 : // - By an instruction that is not part of the reduction (not safe).
267 : // This is either:
268 : // * An instruction type other than PHI or the reduction operation.
269 : // * A PHI in the header other than the initial PHI.
270 37727 : while (!Worklist.empty()) {
271 37255 : Instruction *Cur = Worklist.back();
272 : Worklist.pop_back();
273 :
274 : // No Users.
275 : // If the instruction has no users then this is a broken chain and can't be
276 : // a reduction variable.
277 37255 : if (Cur->use_empty())
278 17813 : return false;
279 :
280 : bool IsAPhi = isa<PHINode>(Cur);
281 :
282 : // A header PHI use other than the original PHI.
283 35444 : if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
284 : return false;
285 :
286 : // Reductions of instructions such as Div, and Sub is only possible if the
287 : // LHS is the reduction variable.
288 28224 : if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
289 18361 : !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
290 18300 : !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
291 : return false;
292 :
293 : // Any reduction instruction must be of one of the allowed kinds. We ignore
294 : // the starting value (the Phi or an AND instruction if the Phi has been
295 : // type-promoted).
296 30422 : if (Cur != Start) {
297 12227 : ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
298 12227 : if (!ReduxDesc.isRecurrence())
299 : return false;
300 : }
301 :
302 : bool IsASelect = isa<SelectInst>(Cur);
303 :
304 : // A conditional reduction operation must only have 2 or less uses in
305 : // VisitedInsts.
306 20145 : if (IsASelect && (Kind == RK_FloatAdd || Kind == RK_FloatMult) &&
307 10 : hasMultipleUsesOf(Cur, VisitedInsts, 2))
308 : return false;
309 :
310 : // A reduction operation must only have one use of the reduction value.
311 23709 : if (!IsAPhi && !IsASelect && Kind != RK_IntegerMinMax &&
312 20135 : Kind != RK_FloatMinMax && hasMultipleUsesOf(Cur, VisitedInsts, 1))
313 : return false;
314 :
315 : // All inputs to a PHI node must be a reduction value.
316 20135 : if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
317 : return false;
318 :
319 20043 : if (Kind == RK_IntegerMinMax &&
320 2900 : (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
321 52 : ++NumCmpSelectPatternInst;
322 20043 : if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
323 34 : ++NumCmpSelectPatternInst;
324 :
325 : // Check whether we found a reduction operator.
326 38265 : FoundReduxOp |= !IsAPhi && Cur != Start;
327 :
328 : // Process users of current instruction. Push non-PHI nodes after PHI nodes
329 : // onto the stack. This way we are going to have seen all inputs to PHI
330 : // nodes once we get to them.
331 : SmallVector<Instruction *, 8> NonPHIs;
332 : SmallVector<Instruction *, 8> PHIs;
333 62621 : for (User *U : Cur->users()) {
334 43179 : Instruction *UI = cast<Instruction>(U);
335 :
336 : // Check if we found the exit user.
337 43179 : BasicBlock *Parent = UI->getParent();
338 43179 : if (!TheLoop->contains(Parent)) {
339 : // If we already know this instruction is used externally, move on to
340 : // the next user.
341 1114 : if (ExitInstruction == Cur)
342 522 : continue;
343 :
344 : // Exit if you find multiple values used outside or if the header phi
345 : // node is being used. In this case the user uses the value of the
346 : // previous iteration, in which case we would loose "VF-1" iterations of
347 : // the reduction operation if we vectorize.
348 1102 : if (ExitInstruction != nullptr || Cur == Phi)
349 601 : return false;
350 :
351 : // The instruction used by an outside user must be the last instruction
352 : // before we feed back to the reduction phi. Otherwise, we loose VF-1
353 : // operations on the value.
354 1038 : if (!is_contained(Phi->operands(), Cur))
355 : return false;
356 :
357 : ExitInstruction = Cur;
358 : continue;
359 : }
360 :
361 : // Process instructions only once (termination). Each reduction cycle
362 : // value must only be used once, except by phi nodes and min/max
363 : // reductions which are represented as a cmp followed by a select.
364 : InstDesc IgnoredVal(false, nullptr);
365 42065 : if (VisitedInsts.insert(UI).second) {
366 80924 : if (isa<PHINode>(UI))
367 448 : PHIs.push_back(UI);
368 : else
369 40014 : NonPHIs.push_back(UI);
370 3206 : } else if (!isa<PHINode>(UI) &&
371 61 : ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
372 52 : !isa<SelectInst>(UI)) ||
373 52 : (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
374 1594 : !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())))
375 9 : return false;
376 :
377 : // Remember that we completed the cycle.
378 42056 : if (UI == Phi)
379 : FoundStartPHI = true;
380 : }
381 19442 : Worklist.append(PHIs.begin(), PHIs.end());
382 19442 : Worklist.append(NonPHIs.begin(), NonPHIs.end());
383 : }
384 :
385 : // This means we have seen one but not the other instruction of the
386 : // pattern or more than just a select and cmp.
387 472 : if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
388 : NumCmpSelectPatternInst != 2)
389 : return false;
390 :
391 472 : if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
392 : return false;
393 :
394 469 : if (Start != Phi) {
395 : // If the starting value is not the same as the phi node, we speculatively
396 : // looked through an 'and' instruction when evaluating a potential
397 : // arithmetic reduction to determine if it may have been type-promoted.
398 : //
399 : // We now compute the minimal bit width that is required to represent the
400 : // reduction. If this is the same width that was indicated by the 'and', we
401 : // can represent the reduction in the smaller type. The 'and' instruction
402 : // will be eliminated since it will essentially be a cast instruction that
403 : // can be ignore in the cost model. If we compute a different type than we
404 : // did when evaluating the 'and', the 'and' will not be eliminated, and we
405 : // will end up with different kinds of operations in the recurrence
406 : // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is
407 : // the case.
408 : //
409 : // The vectorizer relies on InstCombine to perform the actual
410 : // type-shrinking. It does this by inserting instructions to truncate the
411 : // exit value of the reduction to the width indicated by RecurrenceType and
412 : // then extend this value back to the original width. If IsSigned is false,
413 : // a 'zext' instruction will be generated; otherwise, a 'sext' will be
414 : // used.
415 : //
416 : // TODO: We should not rely on InstCombine to rewrite the reduction in the
417 : // smaller type. We should just generate a correctly typed expression
418 : // to begin with.
419 : Type *ComputedType;
420 : std::tie(ComputedType, IsSigned) =
421 9 : computeRecurrenceType(ExitInstruction, DB, AC, DT);
422 9 : if (ComputedType != RecurrenceType)
423 3 : return false;
424 :
425 : // The recurrence expression will be represented in a narrower type. If
426 : // there are any cast instructions that will be unnecessary, collect them
427 : // in CastInsts. Note that the 'and' instruction was already included in
428 : // this list.
429 : //
430 : // TODO: A better way to represent this may be to tag in some way all the
431 : // instructions that are a part of the reduction. The vectorizer cost
432 : // model could then apply the recurrence type to these instructions,
433 : // without needing a white list of instructions to ignore.
434 6 : collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
435 : }
436 :
437 : // We found a reduction var if we have reached the original phi node and we
438 : // only have a single instruction with out-of-loop users.
439 :
440 : // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
441 : // is saved as part of the RecurrenceDescriptor.
442 :
443 : // Save the description of this reduction variable.
444 : RecurrenceDescriptor RD(
445 : RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
446 932 : ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
447 466 : RedDes = RD;
448 :
449 : return true;
450 : }
451 :
452 : /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
453 : /// pattern corresponding to a min(X, Y) or max(X, Y).
454 : RecurrenceDescriptor::InstDesc
455 147 : RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
456 :
457 : assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
458 : "Expect a select instruction");
459 : Instruction *Cmp = nullptr;
460 : SelectInst *Select = nullptr;
461 :
462 : // We must handle the select(cmp()) as a single instruction. Advance to the
463 : // select.
464 : if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
465 60 : if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
466 : return InstDesc(false, I);
467 44 : return InstDesc(Select, Prev.getMinMaxKind());
468 : }
469 :
470 : // Only handle single use cases for now.
471 : if (!(Select = dyn_cast<SelectInst>(I)))
472 : return InstDesc(false, I);
473 87 : if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
474 : !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
475 : return InstDesc(false, I);
476 87 : if (!Cmp->hasOneUse())
477 : return InstDesc(false, I);
478 :
479 : Value *CmpLeft;
480 : Value *CmpRight;
481 :
482 : // Look for a min/max pattern.
483 87 : if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
484 : return InstDesc(Select, MRK_UIntMin);
485 79 : else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
486 : return InstDesc(Select, MRK_UIntMax);
487 65 : else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
488 : return InstDesc(Select, MRK_SIntMax);
489 57 : else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
490 : return InstDesc(Select, MRK_SIntMin);
491 37 : else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
492 : return InstDesc(Select, MRK_FloatMin);
493 27 : else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
494 : return InstDesc(Select, MRK_FloatMax);
495 19 : else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
496 : return InstDesc(Select, MRK_FloatMin);
497 11 : else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
498 : return InstDesc(Select, MRK_FloatMax);
499 :
500 : return InstDesc(false, I);
501 : }
502 :
503 : /// Returns true if the select instruction has users in the compare-and-add
504 : /// reduction pattern below. The select instruction argument is the last one
505 : /// in the sequence.
506 : ///
507 : /// %sum.1 = phi ...
508 : /// ...
509 : /// %cmp = fcmp pred %0, %CFP
510 : /// %add = fadd %0, %sum.1
511 : /// %sum.2 = select %cmp, %add, %sum.1
512 : RecurrenceDescriptor::InstDesc
513 62 : RecurrenceDescriptor::isConditionalRdxPattern(
514 : RecurrenceKind Kind, Instruction *I) {
515 : SelectInst *SI = dyn_cast<SelectInst>(I);
516 : if (!SI)
517 : return InstDesc(false, I);
518 :
519 : CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
520 : // Only handle single use cases for now.
521 62 : if (!CI || !CI->hasOneUse())
522 : return InstDesc(false, I);
523 :
524 : Value *TrueVal = SI->getTrueValue();
525 : Value *FalseVal = SI->getFalseValue();
526 : // Handle only when either of operands of select instruction is a PHI
527 : // node for now.
528 : if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
529 : (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
530 : return InstDesc(false, I);
531 :
532 : Instruction *I1 =
533 : isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
534 : : dyn_cast<Instruction>(TrueVal);
535 62 : if (!I1 || !I1->isBinaryOp())
536 : return InstDesc(false, I);
537 :
538 : Value *Op1, *Op2;
539 32 : if (m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
540 10 : m_FSub(m_Value(Op1), m_Value(Op2)).match(I1))
541 16 : return InstDesc(Kind == RK_FloatAdd, SI);
542 :
543 6 : if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1))
544 4 : return InstDesc(Kind == RK_FloatMult, SI);
545 :
546 : return InstDesc(false, I);
547 : }
548 :
549 : RecurrenceDescriptor::InstDesc
550 12227 : RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
551 : InstDesc &Prev, bool HasFunNoNaNAttr) {
552 12227 : bool FP = I->getType()->isFloatingPointTy();
553 12227 : Instruction *UAI = Prev.getUnsafeAlgebraInst();
554 12227 : if (!UAI && FP && !I->isFast())
555 : UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
556 :
557 12227 : switch (I->getOpcode()) {
558 : default:
559 : return InstDesc(false, I);
560 119 : case Instruction::PHI:
561 119 : return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
562 6586 : case Instruction::Sub:
563 : case Instruction::Add:
564 6586 : return InstDesc(Kind == RK_IntegerAdd, I);
565 118 : case Instruction::Mul:
566 118 : return InstDesc(Kind == RK_IntegerMult, I);
567 245 : case Instruction::And:
568 245 : return InstDesc(Kind == RK_IntegerAnd, I);
569 78 : case Instruction::Or:
570 78 : return InstDesc(Kind == RK_IntegerOr, I);
571 57 : case Instruction::Xor:
572 57 : return InstDesc(Kind == RK_IntegerXor, I);
573 25 : case Instruction::FMul:
574 25 : return InstDesc(Kind == RK_FloatMult, I, UAI);
575 150 : case Instruction::FSub:
576 : case Instruction::FAdd:
577 150 : return InstDesc(Kind == RK_FloatAdd, I, UAI);
578 70 : case Instruction::Select:
579 70 : if (Kind == RK_FloatAdd || Kind == RK_FloatMult)
580 10 : return isConditionalRdxPattern(Kind, I);
581 : LLVM_FALLTHROUGH;
582 : case Instruction::FCmp:
583 : case Instruction::ICmp:
584 768 : if (Kind != RK_IntegerMinMax &&
585 697 : (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
586 : return InstDesc(false, I);
587 105 : return isMinMaxSelectCmpPattern(I, Prev);
588 : }
589 : }
590 :
591 1753 : bool RecurrenceDescriptor::hasMultipleUsesOf(
592 : Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
593 : unsigned MaxNumUses) {
594 : unsigned NumUses = 0;
595 7022 : for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
596 : ++Use) {
597 3516 : if (Insts.count(dyn_cast<Instruction>(*Use)))
598 1763 : ++NumUses;
599 3516 : if (NumUses > MaxNumUses)
600 : return true;
601 : }
602 :
603 : return false;
604 : }
605 3322 : bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
606 : RecurrenceDescriptor &RedDes,
607 : DemandedBits *DB, AssumptionCache *AC,
608 : DominatorTree *DT) {
609 :
610 : BasicBlock *Header = TheLoop->getHeader();
611 3322 : Function &F = *Header->getParent();
612 : bool HasFunNoNaNAttr =
613 3322 : F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
614 :
615 3322 : if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
616 : AC, DT)) {
617 : LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
618 : return true;
619 : }
620 3056 : if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
621 : AC, DT)) {
622 : LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
623 : return true;
624 : }
625 3051 : if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
626 : AC, DT)) {
627 : LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
628 : return true;
629 : }
630 3032 : if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
631 : AC, DT)) {
632 : LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
633 : return true;
634 : }
635 3005 : if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
636 : AC, DT)) {
637 : LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
638 : return true;
639 : }
640 3002 : if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
641 : DB, AC, DT)) {
642 : LLVM_DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
643 : return true;
644 : }
645 2977 : if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
646 : AC, DT)) {
647 : LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
648 : return true;
649 : }
650 2974 : if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
651 : AC, DT)) {
652 : LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
653 : return true;
654 : }
655 2925 : if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
656 : AC, DT)) {
657 : LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
658 : << "\n");
659 17 : return true;
660 : }
661 : // Not a reduction of known type.
662 : return false;
663 : }
664 :
665 391 : bool RecurrenceDescriptor::isFirstOrderRecurrence(
666 : PHINode *Phi, Loop *TheLoop,
667 : DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
668 :
669 : // Ensure the phi node is in the loop header and has two incoming values.
670 782 : if (Phi->getParent() != TheLoop->getHeader() ||
671 : Phi->getNumIncomingValues() != 2)
672 : return false;
673 :
674 : // Ensure the loop has a preheader and a single latch block. The loop
675 : // vectorizer will need the latch to set up the next iteration of the loop.
676 391 : auto *Preheader = TheLoop->getLoopPreheader();
677 391 : auto *Latch = TheLoop->getLoopLatch();
678 391 : if (!Preheader || !Latch)
679 : return false;
680 :
681 : // Ensure the phi node's incoming blocks are the loop preheader and latch.
682 391 : if (Phi->getBasicBlockIndex(Preheader) < 0 ||
683 391 : Phi->getBasicBlockIndex(Latch) < 0)
684 : return false;
685 :
686 : // Get the previous value. The previous value comes from the latch edge while
687 : // the initial value comes form the preheader edge.
688 391 : auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
689 385 : if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
690 304 : SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
691 87 : return false;
692 :
693 : // Ensure every user of the phi node is dominated by the previous value.
694 : // The dominance requirement ensures the loop vectorizer will not need to
695 : // vectorize the initial value prior to the first iteration of the loop.
696 : // TODO: Consider extending this sinking to handle other kinds of instructions
697 : // and expressions, beyond sinking a single cast past Previous.
698 291 : if (Phi->hasOneUse()) {
699 161 : auto *I = Phi->user_back();
700 263 : if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() &&
701 51 : DT->dominates(Previous, I->user_back())) {
702 19 : if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
703 13 : SinkAfter[I] = Previous;
704 19 : return true;
705 : }
706 : }
707 :
708 391 : for (User *U : Phi->users())
709 : if (auto *I = dyn_cast<Instruction>(U)) {
710 347 : if (!DT->dominates(Previous, I))
711 : return false;
712 : }
713 :
714 : return true;
715 : }
716 :
717 : /// This function returns the identity element (or neutral element) for
718 : /// the operation K.
719 175 : Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
720 : Type *Tp) {
721 175 : switch (K) {
722 117 : case RK_IntegerXor:
723 : case RK_IntegerAdd:
724 : case RK_IntegerOr:
725 : // Adding, Xoring, Oring zero to a number does not change it.
726 117 : return ConstantInt::get(Tp, 0);
727 4 : case RK_IntegerMult:
728 : // Multiplying a number by 1 does not change it.
729 4 : return ConstantInt::get(Tp, 1);
730 21 : case RK_IntegerAnd:
731 : // AND-ing a number with an all-1 value does not change it.
732 21 : return ConstantInt::get(Tp, -1, true);
733 3 : case RK_FloatMult:
734 : // Multiplying a number by 1 does not change it.
735 3 : return ConstantFP::get(Tp, 1.0L);
736 30 : case RK_FloatAdd:
737 : // Adding zero to a number does not change it.
738 30 : return ConstantFP::get(Tp, 0.0L);
739 0 : default:
740 0 : llvm_unreachable("Unknown recurrence kind");
741 : }
742 : }
743 :
744 : /// This function translates the recurrence kind to an LLVM binary operator.
745 212 : unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
746 : switch (Kind) {
747 : case RK_IntegerAdd:
748 : return Instruction::Add;
749 : case RK_IntegerMult:
750 : return Instruction::Mul;
751 : case RK_IntegerOr:
752 : return Instruction::Or;
753 : case RK_IntegerAnd:
754 : return Instruction::And;
755 : case RK_IntegerXor:
756 : return Instruction::Xor;
757 : case RK_FloatMult:
758 : return Instruction::FMul;
759 : case RK_FloatAdd:
760 : return Instruction::FAdd;
761 : case RK_IntegerMinMax:
762 : return Instruction::ICmp;
763 : case RK_FloatMinMax:
764 : return Instruction::FCmp;
765 0 : default:
766 0 : llvm_unreachable("Unknown recurrence operation");
767 : }
768 : }
769 :
770 2573 : InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
771 : const SCEV *Step, BinaryOperator *BOp,
772 2573 : SmallVectorImpl<Instruction *> *Casts)
773 2573 : : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
774 : assert(IK != IK_NoInduction && "Not an induction");
775 :
776 : // Start value type should match the induction kind and the value
777 : // itself should not be null.
778 : assert(StartValue && "StartValue is null");
779 : assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
780 : "StartValue is not a pointer for pointer induction");
781 : assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
782 : "StartValue is not an integer for integer induction");
783 :
784 : // Check the Step Value. It should be non-zero integer value.
785 : assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
786 : "Step value is zero");
787 :
788 : assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
789 : "Step value should be constant for pointer induction");
790 : assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
791 : "StepValue is not an integer");
792 :
793 : assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
794 : "StepValue is not FP for FpInduction");
795 : assert((IK != IK_FpInduction ||
796 : (InductionBinOp &&
797 : (InductionBinOp->getOpcode() == Instruction::FAdd ||
798 : InductionBinOp->getOpcode() == Instruction::FSub))) &&
799 : "Binary opcode should be specified for FP induction");
800 :
801 2573 : if (Casts) {
802 28 : for (auto &Inst : *Casts) {
803 17 : RedundantCasts.push_back(Inst);
804 : }
805 : }
806 2573 : }
807 :
808 0 : int InductionDescriptor::getConsecutiveDirection() const {
809 0 : ConstantInt *ConstStep = getConstIntStepValue();
810 0 : if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
811 0 : return ConstStep->getSExtValue();
812 : return 0;
813 : }
814 :
815 4727 : ConstantInt *InductionDescriptor::getConstIntStepValue() const {
816 9454 : if (isa<SCEVConstant>(Step))
817 4686 : return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
818 : return nullptr;
819 : }
820 :
821 48 : bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
822 : ScalarEvolution *SE,
823 : InductionDescriptor &D) {
824 :
825 : // Here we only handle FP induction variables.
826 : assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
827 :
828 48 : if (TheLoop->getHeader() != Phi->getParent())
829 : return false;
830 :
831 : // The loop may have multiple entrances or multiple exits; we can analyze
832 : // this phi if it has a unique entry value and a unique backedge value.
833 48 : if (Phi->getNumIncomingValues() != 2)
834 : return false;
835 : Value *BEValue = nullptr, *StartValue = nullptr;
836 48 : if (TheLoop->contains(Phi->getIncomingBlock(0))) {
837 : BEValue = Phi->getIncomingValue(0);
838 : StartValue = Phi->getIncomingValue(1);
839 : } else {
840 : assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
841 : "Unexpected Phi node in the loop");
842 : BEValue = Phi->getIncomingValue(1);
843 : StartValue = Phi->getIncomingValue(0);
844 : }
845 :
846 : BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
847 : if (!BOp)
848 : return false;
849 :
850 : Value *Addend = nullptr;
851 34 : if (BOp->getOpcode() == Instruction::FAdd) {
852 30 : if (BOp->getOperand(0) == Phi)
853 : Addend = BOp->getOperand(1);
854 2 : else if (BOp->getOperand(1) == Phi)
855 : Addend = BOp->getOperand(0);
856 4 : } else if (BOp->getOpcode() == Instruction::FSub)
857 4 : if (BOp->getOperand(0) == Phi)
858 : Addend = BOp->getOperand(1);
859 :
860 34 : if (!Addend)
861 : return false;
862 :
863 : // The addend should be loop invariant
864 : if (auto *I = dyn_cast<Instruction>(Addend))
865 12 : if (TheLoop->contains(I))
866 : return false;
867 :
868 : // FP Step has unknown SCEV
869 30 : const SCEV *Step = SE->getUnknown(Addend);
870 30 : D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
871 30 : return true;
872 : }
873 :
874 : /// This function is called when we suspect that the update-chain of a phi node
875 : /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
876 : /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
877 : /// predicate P under which the SCEV expression for the phi can be the
878 : /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
879 : /// cast instructions that are involved in the update-chain of this induction.
880 : /// A caller that adds the required runtime predicate can be free to drop these
881 : /// cast instructions, and compute the phi using \p AR (instead of some scev
882 : /// expression with casts).
883 : ///
884 : /// For example, without a predicate the scev expression can take the following
885 : /// form:
886 : /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
887 : ///
888 : /// It corresponds to the following IR sequence:
889 : /// %for.body:
890 : /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
891 : /// %casted_phi = "ExtTrunc i64 %x"
892 : /// %add = add i64 %casted_phi, %step
893 : ///
894 : /// where %x is given in \p PN,
895 : /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
896 : /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
897 : /// several forms, for example, such as:
898 : /// ExtTrunc1: %casted_phi = and %x, 2^n-1
899 : /// or:
900 : /// ExtTrunc2: %t = shl %x, m
901 : /// %casted_phi = ashr %t, m
902 : ///
903 : /// If we are able to find such sequence, we return the instructions
904 : /// we found, namely %casted_phi and the instructions on its use-def chain up
905 : /// to the phi (not including the phi).
906 11 : static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
907 : const SCEVUnknown *PhiScev,
908 : const SCEVAddRecExpr *AR,
909 : SmallVectorImpl<Instruction *> &CastInsts) {
910 :
911 : assert(CastInsts.empty() && "CastInsts is expected to be empty.");
912 : auto *PN = cast<PHINode>(PhiScev->getValue());
913 : assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
914 11 : const Loop *L = AR->getLoop();
915 :
916 : // Find any cast instructions that participate in the def-use chain of
917 : // PhiScev in the loop.
918 : // FORNOW/TODO: We currently expect the def-use chain to include only
919 : // two-operand instructions, where one of the operands is an invariant.
920 : // createAddRecFromPHIWithCasts() currently does not support anything more
921 : // involved than that, so we keep the search simple. This can be
922 : // extended/generalized as needed.
923 :
924 : auto getDef = [&](const Value *Val) -> Value * {
925 : const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
926 : if (!BinOp)
927 : return nullptr;
928 : Value *Op0 = BinOp->getOperand(0);
929 : Value *Op1 = BinOp->getOperand(1);
930 : Value *Def = nullptr;
931 : if (L->isLoopInvariant(Op0))
932 : Def = Op1;
933 : else if (L->isLoopInvariant(Op1))
934 : Def = Op0;
935 : return Def;
936 11 : };
937 :
938 : // Look for the instruction that defines the induction via the
939 : // loop backedge.
940 11 : BasicBlock *Latch = L->getLoopLatch();
941 11 : if (!Latch)
942 : return false;
943 11 : Value *Val = PN->getIncomingValueForBlock(Latch);
944 11 : if (!Val)
945 : return false;
946 :
947 : // Follow the def-use chain until the induction phi is reached.
948 : // If on the way we encounter a Value that has the same SCEV Expr as the
949 : // phi node, we can consider the instructions we visit from that point
950 : // as part of the cast-sequence that can be ignored.
951 : bool InCastSequence = false;
952 11 : auto *Inst = dyn_cast<Instruction>(Val);
953 39 : while (Val != PN) {
954 : // If we encountered a phi node other than PN, or if we left the loop,
955 : // we bail out.
956 28 : if (!Inst || !L->contains(Inst)) {
957 0 : return false;
958 : }
959 28 : auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
960 28 : if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
961 : InCastSequence = true;
962 17 : if (InCastSequence) {
963 : // Only the last instruction in the cast sequence is expected to have
964 : // uses outside the induction def-use chain.
965 17 : if (!CastInsts.empty())
966 6 : if (!Inst->hasOneUse())
967 : return false;
968 17 : CastInsts.push_back(Inst);
969 : }
970 28 : Val = getDef(Val);
971 28 : if (!Val)
972 : return false;
973 28 : Inst = dyn_cast<Instruction>(Val);
974 : }
975 :
976 : return InCastSequence;
977 : }
978 :
979 3237 : bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
980 : PredicatedScalarEvolution &PSE,
981 : InductionDescriptor &D, bool Assume) {
982 3237 : Type *PhiTy = Phi->getType();
983 :
984 : // Handle integer and pointer inductions variables.
985 : // Now we handle also FP induction but not trying to make a
986 : // recurrent expression from the PHI node in-place.
987 :
988 774 : if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
989 3237 : !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
990 : return false;
991 :
992 : if (PhiTy->isFloatingPointTy())
993 48 : return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
994 :
995 3189 : const SCEV *PhiScev = PSE.getSCEV(Phi);
996 : const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
997 :
998 : // We need this expression to be an AddRecExpr.
999 3189 : if (Assume && !AR)
1000 316 : AR = PSE.getAsAddRec(Phi);
1001 :
1002 3189 : if (!AR) {
1003 : LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1004 : return false;
1005 : }
1006 :
1007 : // Record any Cast instructions that participate in the induction update
1008 : const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1009 : // If we started from an UnknownSCEV, and managed to build an addRecurrence
1010 : // only after enabling Assume with PSCEV, this means we may have encountered
1011 : // cast instructions that required adding a runtime check in order to
1012 : // guarantee the correctness of the AddRecurence respresentation of the
1013 : // induction.
1014 2523 : if (PhiScev != AR && SymbolicPhi) {
1015 : SmallVector<Instruction *, 2> Casts;
1016 11 : if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1017 11 : return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1018 : }
1019 :
1020 2512 : return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1021 : }
1022 :
1023 2557 : bool InductionDescriptor::isInductionPHI(
1024 : PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1025 : InductionDescriptor &D, const SCEV *Expr,
1026 : SmallVectorImpl<Instruction *> *CastsToIgnore) {
1027 2557 : Type *PhiTy = Phi->getType();
1028 : // We only handle integer and pointer inductions variables.
1029 2557 : if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1030 : return false;
1031 :
1032 : // Check that the PHI is consecutive.
1033 2556 : const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1034 : const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1035 :
1036 : if (!AR) {
1037 : LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1038 : return false;
1039 : }
1040 :
1041 2555 : if (AR->getLoop() != TheLoop) {
1042 : // FIXME: We should treat this as a uniform. Unfortunately, we
1043 : // don't currently know how to handled uniform PHIs.
1044 : LLVM_DEBUG(
1045 : dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1046 : return false;
1047 : }
1048 :
1049 : Value *StartValue =
1050 2555 : Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
1051 2555 : const SCEV *Step = AR->getStepRecurrence(*SE);
1052 : // Calculate the pointer stride and check if it is consecutive.
1053 : // The stride may be a constant or a loop invariant integer value.
1054 : const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1055 34 : if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1056 : return false;
1057 :
1058 2555 : if (PhiTy->isIntegerTy()) {
1059 4014 : D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/nullptr,
1060 2007 : CastsToIgnore);
1061 2007 : return true;
1062 : }
1063 :
1064 : assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1065 : // Pointer induction should be a constant.
1066 548 : if (!ConstStep)
1067 : return false;
1068 :
1069 540 : ConstantInt *CV = ConstStep->getValue();
1070 540 : Type *PointerElementType = PhiTy->getPointerElementType();
1071 : // The pointer stride cannot be determined if the pointer element type is not
1072 : // sized.
1073 540 : if (!PointerElementType->isSized())
1074 : return false;
1075 :
1076 538 : const DataLayout &DL = Phi->getModule()->getDataLayout();
1077 538 : int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1078 538 : if (!Size)
1079 : return false;
1080 :
1081 : int64_t CVSize = CV->getSExtValue();
1082 536 : if (CVSize % Size)
1083 : return false;
1084 : auto *StepValue =
1085 1072 : SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1086 536 : D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
1087 536 : return true;
1088 : }
|
