1 //===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file "describes" induction and recurrence variables.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/Analysis/IVDescriptors.h"
14 #include "llvm/ADT/ScopeExit.h"
15 #include "llvm/Analysis/AliasAnalysis.h"
16 #include "llvm/Analysis/BasicAliasAnalysis.h"
17 #include "llvm/Analysis/DomTreeUpdater.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/ScalarEvolutionExpressions.h"
26 #include "llvm/Analysis/TargetTransformInfo.h"
27 #include "llvm/Analysis/ValueTracking.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/IR/ValueHandle.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/KnownBits.h"
38 using namespace llvm::PatternMatch;
40 #define DEBUG_TYPE "iv-descriptors"
42 bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
43 SmallPtrSetImpl<Instruction *> &Set) {
44 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
45 if (!Set.count(dyn_cast<Instruction>(*Use)))
50 bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
59 case RK_IntegerMinMax:
65 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
66 return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
69 bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
82 /// Determines if Phi may have been type-promoted. If Phi has a single user
83 /// that ANDs the Phi with a type mask, return the user. RT is updated to
84 /// account for the narrower bit width represented by the mask, and the AND
85 /// instruction is added to CI.
86 static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
87 SmallPtrSetImpl<Instruction *> &Visited,
88 SmallPtrSetImpl<Instruction *> &CI) {
89 if (!Phi->hasOneUse())
92 const APInt *M = nullptr;
93 Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
95 // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
96 // with a new integer type of the corresponding bit width.
97 if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
98 int32_t Bits = (*M + 1).exactLogBase2();
100 RT = IntegerType::get(Phi->getContext(), Bits);
109 /// Compute the minimal bit width needed to represent a reduction whose exit
110 /// instruction is given by Exit.
111 static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
115 bool IsSigned = false;
116 const DataLayout &DL = Exit->getModule()->getDataLayout();
117 uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
120 // Use the demanded bits analysis to determine the bits that are live out
121 // of the exit instruction, rounding up to the nearest power of two. If the
122 // use of demanded bits results in a smaller bit width, we know the value
123 // must be positive (i.e., IsSigned = false), because if this were not the
124 // case, the sign bit would have been demanded.
125 auto Mask = DB->getDemandedBits(Exit);
126 MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
129 if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
130 // If demanded bits wasn't able to limit the bit width, we can try to use
131 // value tracking instead. This can be the case, for example, if the value
133 auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
134 auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
135 MaxBitWidth = NumTypeBits - NumSignBits;
136 KnownBits Bits = computeKnownBits(Exit, DL);
137 if (!Bits.isNonNegative()) {
138 // If the value is not known to be non-negative, we set IsSigned to true,
139 // meaning that we will use sext instructions instead of zext
140 // instructions to restore the original type.
142 if (!Bits.isNegative())
143 // If the value is not known to be negative, we don't known what the
144 // upper bit is, and therefore, we don't know what kind of extend we
145 // will need. In this case, just increase the bit width by one bit and
150 if (!isPowerOf2_64(MaxBitWidth))
151 MaxBitWidth = NextPowerOf2(MaxBitWidth);
153 return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
157 /// Collect cast instructions that can be ignored in the vectorizer's cost
158 /// model, given a reduction exit value and the minimal type in which the
159 /// reduction can be represented.
160 static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
161 Type *RecurrenceType,
162 SmallPtrSetImpl<Instruction *> &Casts) {
164 SmallVector<Instruction *, 8> Worklist;
165 SmallPtrSet<Instruction *, 8> Visited;
166 Worklist.push_back(Exit);
168 while (!Worklist.empty()) {
169 Instruction *Val = Worklist.pop_back_val();
171 if (auto *Cast = dyn_cast<CastInst>(Val))
172 if (Cast->getSrcTy() == RecurrenceType) {
173 // If the source type of a cast instruction is equal to the recurrence
174 // type, it will be eliminated, and should be ignored in the vectorizer
180 // Add all operands to the work list if they are loop-varying values that
181 // we haven't yet visited.
182 for (Value *O : cast<User>(Val)->operands())
183 if (auto *I = dyn_cast<Instruction>(O))
184 if (TheLoop->contains(I) && !Visited.count(I))
185 Worklist.push_back(I);
189 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
190 Loop *TheLoop, bool HasFunNoNaNAttr,
191 RecurrenceDescriptor &RedDes,
195 if (Phi->getNumIncomingValues() != 2)
198 // Reduction variables are only found in the loop header block.
199 if (Phi->getParent() != TheLoop->getHeader())
202 // Obtain the reduction start value from the value that comes from the loop
204 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
206 // ExitInstruction is the single value which is used outside the loop.
207 // We only allow for a single reduction value to be used outside the loop.
208 // This includes users of the reduction, variables (which form a cycle
209 // which ends in the phi node).
210 Instruction *ExitInstruction = nullptr;
211 // Indicates that we found a reduction operation in our scan.
212 bool FoundReduxOp = false;
214 // We start with the PHI node and scan for all of the users of this
215 // instruction. All users must be instructions that can be used as reduction
216 // variables (such as ADD). We must have a single out-of-block user. The cycle
217 // must include the original PHI.
218 bool FoundStartPHI = false;
220 // To recognize min/max patterns formed by a icmp select sequence, we store
221 // the number of instruction we saw from the recognized min/max pattern,
222 // to make sure we only see exactly the two instructions.
223 unsigned NumCmpSelectPatternInst = 0;
224 InstDesc ReduxDesc(false, nullptr);
226 // Data used for determining if the recurrence has been type-promoted.
227 Type *RecurrenceType = Phi->getType();
228 SmallPtrSet<Instruction *, 4> CastInsts;
229 Instruction *Start = Phi;
230 bool IsSigned = false;
232 SmallPtrSet<Instruction *, 8> VisitedInsts;
233 SmallVector<Instruction *, 8> Worklist;
235 // Return early if the recurrence kind does not match the type of Phi. If the
236 // recurrence kind is arithmetic, we attempt to look through AND operations
237 // resulting from the type promotion performed by InstCombine. Vector
238 // operations are not limited to the legal integer widths, so we may be able
239 // to evaluate the reduction in the narrower width.
240 if (RecurrenceType->isFloatingPointTy()) {
241 if (!isFloatingPointRecurrenceKind(Kind))
244 if (!isIntegerRecurrenceKind(Kind))
246 if (isArithmeticRecurrenceKind(Kind))
247 Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
250 Worklist.push_back(Start);
251 VisitedInsts.insert(Start);
253 // Start with all flags set because we will intersect this with the reduction
254 // flags from all the reduction operations.
255 FastMathFlags FMF = FastMathFlags::getFast();
257 // A value in the reduction can be used:
258 // - By the reduction:
259 // - Reduction operation:
260 // - One use of reduction value (safe).
261 // - Multiple use of reduction value (not safe).
263 // - All uses of the PHI must be the reduction (safe).
264 // - Otherwise, not safe.
265 // - By instructions outside of the loop (safe).
266 // * One value may have several outside users, but all outside
267 // uses must be of the same value.
268 // - By an instruction that is not part of the reduction (not safe).
270 // * An instruction type other than PHI or the reduction operation.
271 // * A PHI in the header other than the initial PHI.
272 while (!Worklist.empty()) {
273 Instruction *Cur = Worklist.back();
277 // If the instruction has no users then this is a broken chain and can't be
278 // a reduction variable.
279 if (Cur->use_empty())
282 bool IsAPhi = isa<PHINode>(Cur);
284 // A header PHI use other than the original PHI.
285 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
288 // Reductions of instructions such as Div, and Sub is only possible if the
289 // LHS is the reduction variable.
290 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
291 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
292 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
295 // Any reduction instruction must be of one of the allowed kinds. We ignore
296 // the starting value (the Phi or an AND instruction if the Phi has been
299 ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
300 if (!ReduxDesc.isRecurrence())
302 // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
303 if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi)
304 FMF &= ReduxDesc.getPatternInst()->getFastMathFlags();
307 bool IsASelect = isa<SelectInst>(Cur);
309 // A conditional reduction operation must only have 2 or less uses in
311 if (IsASelect && (Kind == RK_FloatAdd || Kind == RK_FloatMult) &&
312 hasMultipleUsesOf(Cur, VisitedInsts, 2))
315 // A reduction operation must only have one use of the reduction value.
316 if (!IsAPhi && !IsASelect && Kind != RK_IntegerMinMax &&
317 Kind != RK_FloatMinMax && hasMultipleUsesOf(Cur, VisitedInsts, 1))
320 // All inputs to a PHI node must be a reduction value.
321 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
324 if (Kind == RK_IntegerMinMax &&
325 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
326 ++NumCmpSelectPatternInst;
327 if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
328 ++NumCmpSelectPatternInst;
330 // Check whether we found a reduction operator.
331 FoundReduxOp |= !IsAPhi && Cur != Start;
333 // Process users of current instruction. Push non-PHI nodes after PHI nodes
334 // onto the stack. This way we are going to have seen all inputs to PHI
335 // nodes once we get to them.
336 SmallVector<Instruction *, 8> NonPHIs;
337 SmallVector<Instruction *, 8> PHIs;
338 for (User *U : Cur->users()) {
339 Instruction *UI = cast<Instruction>(U);
341 // Check if we found the exit user.
342 BasicBlock *Parent = UI->getParent();
343 if (!TheLoop->contains(Parent)) {
344 // If we already know this instruction is used externally, move on to
346 if (ExitInstruction == Cur)
349 // Exit if you find multiple values used outside or if the header phi
350 // node is being used. In this case the user uses the value of the
351 // previous iteration, in which case we would loose "VF-1" iterations of
352 // the reduction operation if we vectorize.
353 if (ExitInstruction != nullptr || Cur == Phi)
356 // The instruction used by an outside user must be the last instruction
357 // before we feed back to the reduction phi. Otherwise, we loose VF-1
358 // operations on the value.
359 if (!is_contained(Phi->operands(), Cur))
362 ExitInstruction = Cur;
366 // Process instructions only once (termination). Each reduction cycle
367 // value must only be used once, except by phi nodes and min/max
368 // reductions which are represented as a cmp followed by a select.
369 InstDesc IgnoredVal(false, nullptr);
370 if (VisitedInsts.insert(UI).second) {
371 if (isa<PHINode>(UI))
374 NonPHIs.push_back(UI);
375 } else if (!isa<PHINode>(UI) &&
376 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
377 !isa<SelectInst>(UI)) ||
378 (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
379 !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())))
382 // Remember that we completed the cycle.
384 FoundStartPHI = true;
386 Worklist.append(PHIs.begin(), PHIs.end());
387 Worklist.append(NonPHIs.begin(), NonPHIs.end());
390 // This means we have seen one but not the other instruction of the
391 // pattern or more than just a select and cmp.
392 if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
393 NumCmpSelectPatternInst != 2)
396 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
400 // If the starting value is not the same as the phi node, we speculatively
401 // looked through an 'and' instruction when evaluating a potential
402 // arithmetic reduction to determine if it may have been type-promoted.
404 // We now compute the minimal bit width that is required to represent the
405 // reduction. If this is the same width that was indicated by the 'and', we
406 // can represent the reduction in the smaller type. The 'and' instruction
407 // will be eliminated since it will essentially be a cast instruction that
408 // can be ignore in the cost model. If we compute a different type than we
409 // did when evaluating the 'and', the 'and' will not be eliminated, and we
410 // will end up with different kinds of operations in the recurrence
411 // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is
414 // The vectorizer relies on InstCombine to perform the actual
415 // type-shrinking. It does this by inserting instructions to truncate the
416 // exit value of the reduction to the width indicated by RecurrenceType and
417 // then extend this value back to the original width. If IsSigned is false,
418 // a 'zext' instruction will be generated; otherwise, a 'sext' will be
421 // TODO: We should not rely on InstCombine to rewrite the reduction in the
422 // smaller type. We should just generate a correctly typed expression
425 std::tie(ComputedType, IsSigned) =
426 computeRecurrenceType(ExitInstruction, DB, AC, DT);
427 if (ComputedType != RecurrenceType)
430 // The recurrence expression will be represented in a narrower type. If
431 // there are any cast instructions that will be unnecessary, collect them
432 // in CastInsts. Note that the 'and' instruction was already included in
435 // TODO: A better way to represent this may be to tag in some way all the
436 // instructions that are a part of the reduction. The vectorizer cost
437 // model could then apply the recurrence type to these instructions,
438 // without needing a white list of instructions to ignore.
439 collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
442 // We found a reduction var if we have reached the original phi node and we
443 // only have a single instruction with out-of-loop users.
445 // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
446 // is saved as part of the RecurrenceDescriptor.
448 // Save the description of this reduction variable.
449 RecurrenceDescriptor RD(
450 RdxStart, ExitInstruction, Kind, FMF, ReduxDesc.getMinMaxKind(),
451 ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
457 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
458 /// pattern corresponding to a min(X, Y) or max(X, Y).
459 RecurrenceDescriptor::InstDesc
460 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
462 assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
463 "Expect a select instruction");
464 Instruction *Cmp = nullptr;
465 SelectInst *Select = nullptr;
467 // We must handle the select(cmp()) as a single instruction. Advance to the
469 if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
470 if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
471 return InstDesc(false, I);
472 return InstDesc(Select, Prev.getMinMaxKind());
475 // Only handle single use cases for now.
476 if (!(Select = dyn_cast<SelectInst>(I)))
477 return InstDesc(false, I);
478 if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
479 !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
480 return InstDesc(false, I);
481 if (!Cmp->hasOneUse())
482 return InstDesc(false, I);
487 // Look for a min/max pattern.
488 if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
489 return InstDesc(Select, MRK_UIntMin);
490 else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
491 return InstDesc(Select, MRK_UIntMax);
492 else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
493 return InstDesc(Select, MRK_SIntMax);
494 else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
495 return InstDesc(Select, MRK_SIntMin);
496 else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
497 return InstDesc(Select, MRK_FloatMin);
498 else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
499 return InstDesc(Select, MRK_FloatMax);
500 else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
501 return InstDesc(Select, MRK_FloatMin);
502 else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
503 return InstDesc(Select, MRK_FloatMax);
505 return InstDesc(false, I);
508 /// Returns true if the select instruction has users in the compare-and-add
509 /// reduction pattern below. The select instruction argument is the last one
514 /// %cmp = fcmp pred %0, %CFP
515 /// %add = fadd %0, %sum.1
516 /// %sum.2 = select %cmp, %add, %sum.1
517 RecurrenceDescriptor::InstDesc
518 RecurrenceDescriptor::isConditionalRdxPattern(
519 RecurrenceKind Kind, Instruction *I) {
520 SelectInst *SI = dyn_cast<SelectInst>(I);
522 return InstDesc(false, I);
524 CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
525 // Only handle single use cases for now.
526 if (!CI || !CI->hasOneUse())
527 return InstDesc(false, I);
529 Value *TrueVal = SI->getTrueValue();
530 Value *FalseVal = SI->getFalseValue();
531 // Handle only when either of operands of select instruction is a PHI
533 if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
534 (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
535 return InstDesc(false, I);
538 isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
539 : dyn_cast<Instruction>(TrueVal);
540 if (!I1 || !I1->isBinaryOp())
541 return InstDesc(false, I);
544 if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
545 m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
547 return InstDesc(Kind == RK_FloatAdd, SI);
549 if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
550 return InstDesc(Kind == RK_FloatMult, SI);
552 return InstDesc(false, I);
555 RecurrenceDescriptor::InstDesc
556 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
557 InstDesc &Prev, bool HasFunNoNaNAttr) {
558 Instruction *UAI = Prev.getUnsafeAlgebraInst();
559 if (!UAI && isa<FPMathOperator>(I) && !I->hasAllowReassoc())
560 UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
562 switch (I->getOpcode()) {
564 return InstDesc(false, I);
565 case Instruction::PHI:
566 return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
567 case Instruction::Sub:
568 case Instruction::Add:
569 return InstDesc(Kind == RK_IntegerAdd, I);
570 case Instruction::Mul:
571 return InstDesc(Kind == RK_IntegerMult, I);
572 case Instruction::And:
573 return InstDesc(Kind == RK_IntegerAnd, I);
574 case Instruction::Or:
575 return InstDesc(Kind == RK_IntegerOr, I);
576 case Instruction::Xor:
577 return InstDesc(Kind == RK_IntegerXor, I);
578 case Instruction::FMul:
579 return InstDesc(Kind == RK_FloatMult, I, UAI);
580 case Instruction::FSub:
581 case Instruction::FAdd:
582 return InstDesc(Kind == RK_FloatAdd, I, UAI);
583 case Instruction::Select:
584 if (Kind == RK_FloatAdd || Kind == RK_FloatMult)
585 return isConditionalRdxPattern(Kind, I);
587 case Instruction::FCmp:
588 case Instruction::ICmp:
589 if (Kind != RK_IntegerMinMax &&
590 (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
591 return InstDesc(false, I);
592 return isMinMaxSelectCmpPattern(I, Prev);
596 bool RecurrenceDescriptor::hasMultipleUsesOf(
597 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
598 unsigned MaxNumUses) {
599 unsigned NumUses = 0;
600 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
602 if (Insts.count(dyn_cast<Instruction>(*Use)))
604 if (NumUses > MaxNumUses)
610 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
611 RecurrenceDescriptor &RedDes,
612 DemandedBits *DB, AssumptionCache *AC,
615 BasicBlock *Header = TheLoop->getHeader();
616 Function &F = *Header->getParent();
617 bool HasFunNoNaNAttr =
618 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
620 if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
622 LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
625 if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
627 LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
630 if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
632 LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
635 if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
637 LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
640 if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
642 LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
645 if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
647 LLVM_DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
650 if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
652 LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
655 if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
657 LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
660 if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
662 LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
666 // Not a reduction of known type.
670 bool RecurrenceDescriptor::isFirstOrderRecurrence(
671 PHINode *Phi, Loop *TheLoop,
672 DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
674 // Ensure the phi node is in the loop header and has two incoming values.
675 if (Phi->getParent() != TheLoop->getHeader() ||
676 Phi->getNumIncomingValues() != 2)
679 // Ensure the loop has a preheader and a single latch block. The loop
680 // vectorizer will need the latch to set up the next iteration of the loop.
681 auto *Preheader = TheLoop->getLoopPreheader();
682 auto *Latch = TheLoop->getLoopLatch();
683 if (!Preheader || !Latch)
686 // Ensure the phi node's incoming blocks are the loop preheader and latch.
687 if (Phi->getBasicBlockIndex(Preheader) < 0 ||
688 Phi->getBasicBlockIndex(Latch) < 0)
691 // Get the previous value. The previous value comes from the latch edge while
692 // the initial value comes form the preheader edge.
693 auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
694 if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
695 SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
698 // Ensure every user of the phi node is dominated by the previous value.
699 // The dominance requirement ensures the loop vectorizer will not need to
700 // vectorize the initial value prior to the first iteration of the loop.
701 // TODO: Consider extending this sinking to handle memory instructions and
702 // phis with multiple users.
704 // Returns true, if all users of I are dominated by DominatedBy.
705 auto allUsesDominatedBy = [DT](Instruction *I, Instruction *DominatedBy) {
706 return all_of(I->uses(), [DT, DominatedBy](Use &U) {
707 return DT->dominates(DominatedBy, U);
711 if (Phi->hasOneUse()) {
712 Instruction *I = Phi->user_back();
714 // If the user of the PHI is also the incoming value, we potentially have a
715 // reduction and which cannot be handled by sinking.
719 // We cannot sink terminator instructions.
720 if (I->getParent()->getTerminator() == I)
723 // Do not try to sink an instruction multiple times (if multiple operands
724 // are first order recurrences).
725 // TODO: We can support this case, by sinking the instruction after the
726 // 'deepest' previous instruction.
727 if (SinkAfter.find(I) != SinkAfter.end())
730 if (DT->dominates(Previous, I)) // We already are good w/o sinking.
733 // We can sink any instruction without side effects, as long as all users
734 // are dominated by the instruction we are sinking after.
735 if (I->getParent() == Phi->getParent() && !I->mayHaveSideEffects() &&
736 allUsesDominatedBy(I, Previous)) {
737 SinkAfter[I] = Previous;
742 return allUsesDominatedBy(Phi, Previous);
745 /// This function returns the identity element (or neutral element) for
747 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
753 // Adding, Xoring, Oring zero to a number does not change it.
754 return ConstantInt::get(Tp, 0);
756 // Multiplying a number by 1 does not change it.
757 return ConstantInt::get(Tp, 1);
759 // AND-ing a number with an all-1 value does not change it.
760 return ConstantInt::get(Tp, -1, true);
762 // Multiplying a number by 1 does not change it.
763 return ConstantFP::get(Tp, 1.0L);
765 // Adding zero to a number does not change it.
766 return ConstantFP::get(Tp, 0.0L);
768 llvm_unreachable("Unknown recurrence kind");
772 /// This function translates the recurrence kind to an LLVM binary operator.
773 unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
776 return Instruction::Add;
778 return Instruction::Mul;
780 return Instruction::Or;
782 return Instruction::And;
784 return Instruction::Xor;
786 return Instruction::FMul;
788 return Instruction::FAdd;
789 case RK_IntegerMinMax:
790 return Instruction::ICmp;
792 return Instruction::FCmp;
794 llvm_unreachable("Unknown recurrence operation");
798 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
799 const SCEV *Step, BinaryOperator *BOp,
800 SmallVectorImpl<Instruction *> *Casts)
801 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
802 assert(IK != IK_NoInduction && "Not an induction");
804 // Start value type should match the induction kind and the value
805 // itself should not be null.
806 assert(StartValue && "StartValue is null");
807 assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
808 "StartValue is not a pointer for pointer induction");
809 assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
810 "StartValue is not an integer for integer induction");
812 // Check the Step Value. It should be non-zero integer value.
813 assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
814 "Step value is zero");
816 assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
817 "Step value should be constant for pointer induction");
818 assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
819 "StepValue is not an integer");
821 assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
822 "StepValue is not FP for FpInduction");
823 assert((IK != IK_FpInduction ||
825 (InductionBinOp->getOpcode() == Instruction::FAdd ||
826 InductionBinOp->getOpcode() == Instruction::FSub))) &&
827 "Binary opcode should be specified for FP induction");
830 for (auto &Inst : *Casts) {
831 RedundantCasts.push_back(Inst);
836 int InductionDescriptor::getConsecutiveDirection() const {
837 ConstantInt *ConstStep = getConstIntStepValue();
838 if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
839 return ConstStep->getSExtValue();
843 ConstantInt *InductionDescriptor::getConstIntStepValue() const {
844 if (isa<SCEVConstant>(Step))
845 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
849 bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
851 InductionDescriptor &D) {
853 // Here we only handle FP induction variables.
854 assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
856 if (TheLoop->getHeader() != Phi->getParent())
859 // The loop may have multiple entrances or multiple exits; we can analyze
860 // this phi if it has a unique entry value and a unique backedge value.
861 if (Phi->getNumIncomingValues() != 2)
863 Value *BEValue = nullptr, *StartValue = nullptr;
864 if (TheLoop->contains(Phi->getIncomingBlock(0))) {
865 BEValue = Phi->getIncomingValue(0);
866 StartValue = Phi->getIncomingValue(1);
868 assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
869 "Unexpected Phi node in the loop");
870 BEValue = Phi->getIncomingValue(1);
871 StartValue = Phi->getIncomingValue(0);
874 BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
878 Value *Addend = nullptr;
879 if (BOp->getOpcode() == Instruction::FAdd) {
880 if (BOp->getOperand(0) == Phi)
881 Addend = BOp->getOperand(1);
882 else if (BOp->getOperand(1) == Phi)
883 Addend = BOp->getOperand(0);
884 } else if (BOp->getOpcode() == Instruction::FSub)
885 if (BOp->getOperand(0) == Phi)
886 Addend = BOp->getOperand(1);
891 // The addend should be loop invariant
892 if (auto *I = dyn_cast<Instruction>(Addend))
893 if (TheLoop->contains(I))
896 // FP Step has unknown SCEV
897 const SCEV *Step = SE->getUnknown(Addend);
898 D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
902 /// This function is called when we suspect that the update-chain of a phi node
903 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
904 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
905 /// predicate P under which the SCEV expression for the phi can be the
906 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
907 /// cast instructions that are involved in the update-chain of this induction.
908 /// A caller that adds the required runtime predicate can be free to drop these
909 /// cast instructions, and compute the phi using \p AR (instead of some scev
910 /// expression with casts).
912 /// For example, without a predicate the scev expression can take the following
914 /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
916 /// It corresponds to the following IR sequence:
918 /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
919 /// %casted_phi = "ExtTrunc i64 %x"
920 /// %add = add i64 %casted_phi, %step
922 /// where %x is given in \p PN,
923 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
924 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
925 /// several forms, for example, such as:
926 /// ExtTrunc1: %casted_phi = and %x, 2^n-1
928 /// ExtTrunc2: %t = shl %x, m
929 /// %casted_phi = ashr %t, m
931 /// If we are able to find such sequence, we return the instructions
932 /// we found, namely %casted_phi and the instructions on its use-def chain up
933 /// to the phi (not including the phi).
934 static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
935 const SCEVUnknown *PhiScev,
936 const SCEVAddRecExpr *AR,
937 SmallVectorImpl<Instruction *> &CastInsts) {
939 assert(CastInsts.empty() && "CastInsts is expected to be empty.");
940 auto *PN = cast<PHINode>(PhiScev->getValue());
941 assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
942 const Loop *L = AR->getLoop();
944 // Find any cast instructions that participate in the def-use chain of
945 // PhiScev in the loop.
946 // FORNOW/TODO: We currently expect the def-use chain to include only
947 // two-operand instructions, where one of the operands is an invariant.
948 // createAddRecFromPHIWithCasts() currently does not support anything more
949 // involved than that, so we keep the search simple. This can be
950 // extended/generalized as needed.
952 auto getDef = [&](const Value *Val) -> Value * {
953 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
956 Value *Op0 = BinOp->getOperand(0);
957 Value *Op1 = BinOp->getOperand(1);
958 Value *Def = nullptr;
959 if (L->isLoopInvariant(Op0))
961 else if (L->isLoopInvariant(Op1))
966 // Look for the instruction that defines the induction via the
968 BasicBlock *Latch = L->getLoopLatch();
971 Value *Val = PN->getIncomingValueForBlock(Latch);
975 // Follow the def-use chain until the induction phi is reached.
976 // If on the way we encounter a Value that has the same SCEV Expr as the
977 // phi node, we can consider the instructions we visit from that point
978 // as part of the cast-sequence that can be ignored.
979 bool InCastSequence = false;
980 auto *Inst = dyn_cast<Instruction>(Val);
982 // If we encountered a phi node other than PN, or if we left the loop,
984 if (!Inst || !L->contains(Inst)) {
987 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
988 if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
989 InCastSequence = true;
990 if (InCastSequence) {
991 // Only the last instruction in the cast sequence is expected to have
992 // uses outside the induction def-use chain.
993 if (!CastInsts.empty())
994 if (!Inst->hasOneUse())
996 CastInsts.push_back(Inst);
1001 Inst = dyn_cast<Instruction>(Val);
1004 return InCastSequence;
1007 bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
1008 PredicatedScalarEvolution &PSE,
1009 InductionDescriptor &D, bool Assume) {
1010 Type *PhiTy = Phi->getType();
1012 // Handle integer and pointer inductions variables.
1013 // Now we handle also FP induction but not trying to make a
1014 // recurrent expression from the PHI node in-place.
1016 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
1017 !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
1020 if (PhiTy->isFloatingPointTy())
1021 return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
1023 const SCEV *PhiScev = PSE.getSCEV(Phi);
1024 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1026 // We need this expression to be an AddRecExpr.
1028 AR = PSE.getAsAddRec(Phi);
1031 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1035 // Record any Cast instructions that participate in the induction update
1036 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1037 // If we started from an UnknownSCEV, and managed to build an addRecurrence
1038 // only after enabling Assume with PSCEV, this means we may have encountered
1039 // cast instructions that required adding a runtime check in order to
1040 // guarantee the correctness of the AddRecurrence respresentation of the
1042 if (PhiScev != AR && SymbolicPhi) {
1043 SmallVector<Instruction *, 2> Casts;
1044 if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1045 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1048 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1051 bool InductionDescriptor::isInductionPHI(
1052 PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1053 InductionDescriptor &D, const SCEV *Expr,
1054 SmallVectorImpl<Instruction *> *CastsToIgnore) {
1055 Type *PhiTy = Phi->getType();
1056 // We only handle integer and pointer inductions variables.
1057 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1060 // Check that the PHI is consecutive.
1061 const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1062 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1065 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1069 if (AR->getLoop() != TheLoop) {
1070 // FIXME: We should treat this as a uniform. Unfortunately, we
1071 // don't currently know how to handled uniform PHIs.
1073 dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1078 Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
1080 BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1083 BinaryOperator *BOp =
1084 dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
1086 const SCEV *Step = AR->getStepRecurrence(*SE);
1087 // Calculate the pointer stride and check if it is consecutive.
1088 // The stride may be a constant or a loop invariant integer value.
1089 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1090 if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1093 if (PhiTy->isIntegerTy()) {
1094 D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1099 assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1100 // Pointer induction should be a constant.
1104 ConstantInt *CV = ConstStep->getValue();
1105 Type *PointerElementType = PhiTy->getPointerElementType();
1106 // The pointer stride cannot be determined if the pointer element type is not
1108 if (!PointerElementType->isSized())
1111 const DataLayout &DL = Phi->getModule()->getDataLayout();
1112 int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1116 int64_t CVSize = CV->getSExtValue();
1120 SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1121 D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);