30#define DEBUG_TYPE "iv-descriptors"
34 for (
const Use &
Use :
I->operands())
35 if (!Set.
count(dyn_cast<Instruction>(
Use)))
71 if (!Phi->hasOneUse())
74 const APInt *M =
nullptr;
75 Instruction *
I, *J = cast<Instruction>(Phi->use_begin()->getUser());
80 int32_t Bits = (*M + 1).exactLogBase2();
97 bool IsSigned =
false;
98 const DataLayout &
DL = Exit->getModule()->getDataLayout();
99 uint64_t MaxBitWidth =
DL.getTypeSizeInBits(Exit->getType());
107 auto Mask = DB->getDemandedBits(Exit);
108 MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero();
111 if (MaxBitWidth ==
DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
116 auto NumTypeBits =
DL.getTypeSizeInBits(Exit->getType());
117 MaxBitWidth = NumTypeBits - NumSignBits;
119 if (!Bits.isNonNegative()) {
131 return std::make_pair(
Type::getIntNTy(Exit->getContext(), MaxBitWidth),
140 Type *RecurrenceType,
142 unsigned &MinWidthCastToRecurTy) {
147 MinWidthCastToRecurTy = -1U;
149 while (!Worklist.
empty()) {
152 if (
auto *Cast = dyn_cast<CastInst>(Val)) {
153 if (Cast->getSrcTy() == RecurrenceType) {
160 if (Cast->getDestTy() == RecurrenceType) {
165 MinWidthCastToRecurTy = std::min<unsigned>(
166 MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits());
172 for (
Value *O : cast<User>(Val)->operands())
173 if (
auto *
I = dyn_cast<Instruction>(O))
195 if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3))
200 auto *Op0 = Exit->getOperand(0);
201 auto *Op1 = Exit->getOperand(1);
207 LLVM_DEBUG(
dbgs() <<
"LV: Found an ordered reduction: Phi: " << *Phi
208 <<
", ExitInst: " << *Exit <<
"\n");
217 if (Phi->getNumIncomingValues() != 2)
221 if (Phi->getParent() != TheLoop->
getHeader())
240 bool FoundReduxOp =
false;
246 bool FoundStartPHI =
false;
251 unsigned NumCmpSelectPatternInst = 0;
255 Type *RecurrenceType = Phi->getType();
257 unsigned MinWidthCastToRecurrenceType;
259 bool IsSigned =
false;
276 Start =
lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
283 VisitedInsts.
insert(Start);
312 while (!Worklist.
empty()) {
317 if (
auto *SI = dyn_cast<StoreInst>(Cur)) {
319 LLVM_DEBUG(
dbgs() <<
"Store instructions are not processed without "
320 <<
"Scalar Evolution Analysis\n");
324 const SCEV *PtrScev = SE->
getSCEV(SI->getPointerOperand());
327 const SCEV *OtherScev =
330 if (OtherScev != PtrScev) {
331 LLVM_DEBUG(
dbgs() <<
"Storing reduction value to different addresses "
332 <<
"inside the loop: " << *SI->getPointerOperand()
341 LLVM_DEBUG(
dbgs() <<
"Storing reduction value to non-uniform address "
342 <<
"inside the loop: " << *SI->getPointerOperand()
358 bool IsAPhi = isa<PHINode>(Cur);
361 if (Cur != Phi && IsAPhi && Cur->
getParent() == Phi->getParent())
366 if (!Cur->
isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
367 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
377 ExactFPMathInst = ExactFPMathInst ==
nullptr
385 if (
auto *Sel = dyn_cast<SelectInst>(ReduxDesc.
getPatternInst())) {
390 if (
auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
391 CurFMF |= FCmp->getFastMathFlags();
402 bool IsASelect = isa<SelectInst>(Cur);
416 if (IsAPhi && Cur != Phi && !
areAllUsesIn(Cur, VisitedInsts))
420 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
421 ++NumCmpSelectPatternInst;
423 (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
424 ++NumCmpSelectPatternInst;
427 FoundReduxOp |= !IsAPhi && Cur != Start;
448 if (ExitInstruction == Cur)
455 if (ExitInstruction !=
nullptr || Cur == Phi)
464 ExitInstruction = Cur;
471 InstDesc IgnoredVal(
false,
nullptr);
472 if (VisitedInsts.
insert(UI).second) {
473 if (isa<PHINode>(UI)) {
477 if (SI && SI->getPointerOperand() == Cur) {
484 }
else if (!isa<PHINode>(UI) &&
485 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
486 !isa<SelectInst>(UI)) ||
495 FoundStartPHI =
true;
505 NumCmpSelectPatternInst != 0)
523 if (ExitInstruction &&
525 LLVM_DEBUG(
dbgs() <<
"Last store Instruction of reduction value does not "
526 "store last calculated value of the reduction: "
533 if (!ExitInstruction)
537 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
540 const bool IsOrdered =
569 std::tie(ComputedType, IsSigned) =
571 if (ComputedType != RecurrenceType)
589 MinWidthCastToRecurrenceType);
599 FMF, ExactFPMathInst, RecurrenceType, IsSigned,
600 IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
634 if (
auto *
Select = dyn_cast<SelectInst>(*
I->user_begin()))
644 Value *NonPhi =
nullptr;
646 if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))
647 NonPhi = SI->getFalseValue();
648 else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))
649 NonPhi = SI->getTrueValue();
666 assert((isa<CmpInst>(
I) || isa<SelectInst>(
I) || isa<CallInst>(
I)) &&
667 "Expected a cmp or select or call instruction");
675 if (
auto *
Select = dyn_cast<SelectInst>(*
I->user_begin()))
680 if (!isa<IntrinsicInst>(
I) &&
729 CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
734 Value *TrueVal = SI->getTrueValue();
735 Value *FalseVal = SI->getFalseValue();
738 if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
739 (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
743 isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
744 : dyn_cast<Instruction>(TrueVal);
745 if (!I1 || !I1->isBinaryOp())
758 Instruction *IPhi = isa<PHINode>(*Op1) ? dyn_cast<Instruction>(Op1)
759 : dyn_cast<Instruction>(Op2);
760 if (!IPhi || IPhi != FalseVal)
771 switch (
I->getOpcode()) {
774 case Instruction::PHI:
776 case Instruction::Sub:
777 case Instruction::Add:
779 case Instruction::Mul:
781 case Instruction::And:
783 case Instruction::Or:
785 case Instruction::Xor:
787 case Instruction::FDiv:
788 case Instruction::FMul:
790 I->hasAllowReassoc() ?
nullptr :
I);
791 case Instruction::FSub:
792 case Instruction::FAdd:
794 I->hasAllowReassoc() ?
nullptr :
I);
795 case Instruction::Select:
800 case Instruction::FCmp:
801 case Instruction::ICmp:
802 case Instruction::Call:
805 auto HasRequiredFMF = [&]() {
808 if (isa<FPMathOperator>(
I) &&
I->hasNoNaNs() &&
I->hasNoSignedZeros())
820 I->hasAllowReassoc() ?
nullptr :
I);
827 unsigned MaxNumUses) {
828 unsigned NumUses = 0;
829 for (
const Use &U :
I->operands()) {
830 if (Insts.
count(dyn_cast<Instruction>(U)))
832 if (NumUses > MaxNumUses)
848 F.getFnAttribute(
"no-nans-fp-math").getValueAsBool());
850 F.getFnAttribute(
"no-signed-zeros-fp-math").getValueAsBool());
854 LLVM_DEBUG(
dbgs() <<
"Found an ADD reduction PHI." << *Phi <<
"\n");
859 LLVM_DEBUG(
dbgs() <<
"Found a MUL reduction PHI." << *Phi <<
"\n");
864 LLVM_DEBUG(
dbgs() <<
"Found an OR reduction PHI." << *Phi <<
"\n");
869 LLVM_DEBUG(
dbgs() <<
"Found an AND reduction PHI." << *Phi <<
"\n");
874 LLVM_DEBUG(
dbgs() <<
"Found a XOR reduction PHI." << *Phi <<
"\n");
879 LLVM_DEBUG(
dbgs() <<
"Found a SMAX reduction PHI." << *Phi <<
"\n");
884 LLVM_DEBUG(
dbgs() <<
"Found a SMIN reduction PHI." << *Phi <<
"\n");
889 LLVM_DEBUG(
dbgs() <<
"Found a UMAX reduction PHI." << *Phi <<
"\n");
894 LLVM_DEBUG(
dbgs() <<
"Found a UMIN reduction PHI." << *Phi <<
"\n");
899 LLVM_DEBUG(
dbgs() <<
"Found an integer conditional select reduction PHI."
905 LLVM_DEBUG(
dbgs() <<
"Found an FMult reduction PHI." << *Phi <<
"\n");
910 LLVM_DEBUG(
dbgs() <<
"Found an FAdd reduction PHI." << *Phi <<
"\n");
915 LLVM_DEBUG(
dbgs() <<
"Found a float MAX reduction PHI." << *Phi <<
"\n");
920 LLVM_DEBUG(
dbgs() <<
"Found a float MIN reduction PHI." << *Phi <<
"\n");
925 LLVM_DEBUG(
dbgs() <<
"Found a float conditional select reduction PHI."
926 <<
" PHI." << *Phi <<
"\n");
931 LLVM_DEBUG(
dbgs() <<
"Found an FMulAdd reduction PHI." << *Phi <<
"\n");
936 LLVM_DEBUG(
dbgs() <<
"Found a float MAXIMUM reduction PHI." << *Phi <<
"\n");
941 LLVM_DEBUG(
dbgs() <<
"Found a float MINIMUM reduction PHI." << *Phi <<
"\n");
952 if (Phi->getParent() != TheLoop->
getHeader() ||
953 Phi->getNumIncomingValues() != 2)
960 if (!Preheader || !Latch)
964 if (Phi->getBasicBlockIndex(Preheader) < 0 ||
965 Phi->getBasicBlockIndex(Latch) < 0)
970 auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
977 while (
auto *PrevPhi = dyn_cast_or_null<PHINode>(Previous)) {
978 if (PrevPhi->getParent() != Phi->getParent())
980 if (!SeenPhis.
insert(PrevPhi).second)
982 Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch));
985 if (!Previous || !TheLoop->
contains(Previous) || isa<PHINode>(Previous))
997 auto TryToPushSinkCandidate = [&](
Instruction *SinkCandidate) {
999 if (Previous == SinkCandidate)
1002 if (!Seen.
insert(SinkCandidate).second)
1008 if (SinkCandidate->getParent() != PhiBB ||
1009 SinkCandidate->mayHaveSideEffects() ||
1010 SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
1015 if (isa<PHINode>(SinkCandidate))
1025 while (!WorkList.
empty()) {
1028 if (!TryToPushSinkCandidate(cast<Instruction>(
User)))
1045 return ConstantInt::get(Tp, 0);
1048 return ConstantInt::get(Tp, 1);
1051 return ConstantInt::get(Tp, -1,
true);
1054 return ConstantFP::get(Tp, 1.0L);
1064 return ConstantFP::get(Tp, 0.0L);
1065 return ConstantFP::get(Tp, -0.0L);
1067 return ConstantInt::get(Tp, -1,
true);
1069 return ConstantInt::get(Tp, 0);
1071 return ConstantInt::get(Tp,
1074 return ConstantInt::get(Tp,
1078 "nnan, nsz is expected to be set for FP min reduction.");
1082 "nnan, nsz is expected to be set for FP max reduction.");
1100 return Instruction::Add;
1102 return Instruction::Mul;
1104 return Instruction::Or;
1106 return Instruction::And;
1108 return Instruction::Xor;
1110 return Instruction::FMul;
1113 return Instruction::FAdd;
1119 return Instruction::ICmp;
1125 return Instruction::FCmp;
1151 unsigned ExpectedUses = 1;
1152 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp)
1158 if (isa<PHINode>(UI))
1160 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1163 if (isa<SelectInst>(UI))
1172 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1181 return Cur->getOpcode() == RedOp;
1185 unsigned ExtraPhiUses = 0;
1187 if (
auto ExitPhi = dyn_cast<PHINode>(LoopExitInstr)) {
1188 if (ExitPhi->getNumIncomingValues() != 2)
1191 Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0));
1192 Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1));
1197 else if (Inc1 == Phi)
1210 if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->
hasNUses(2))
1215 if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses))
1222 while (Cur != RdxInstr) {
1223 if (!Cur || !isCorrectOpcode(Cur) || !Cur->
hasNUses(ExpectedUses))
1227 Cur = getNextInstruction(Cur);
1231 return ReductionOperations;
1237 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
1238 assert(IK != IK_NoInduction &&
"Not an induction");
1242 assert(StartValue &&
"StartValue is null");
1244 "StartValue is not a pointer for pointer induction");
1246 "StartValue is not an integer for integer induction");
1249 assert((!getConstIntStepValue() || !getConstIntStepValue()->
isZero()) &&
1250 "Step value is zero");
1253 "StepValue is not an integer");
1256 "StepValue is not FP for FpInduction");
1257 assert((IK != IK_FpInduction ||
1259 (InductionBinOp->getOpcode() == Instruction::FAdd ||
1260 InductionBinOp->getOpcode() == Instruction::FSub))) &&
1261 "Binary opcode should be specified for FP induction");
1264 for (
auto &Inst : *Casts) {
1265 RedundantCasts.push_back(Inst);
1271 if (isa<SCEVConstant>(Step))
1272 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
1281 assert(Phi->getType()->isFloatingPointTy() &&
"Unexpected Phi type");
1283 if (TheLoop->
getHeader() != Phi->getParent())
1288 if (Phi->getNumIncomingValues() != 2)
1290 Value *BEValue =
nullptr, *StartValue =
nullptr;
1291 if (TheLoop->
contains(Phi->getIncomingBlock(0))) {
1292 BEValue = Phi->getIncomingValue(0);
1293 StartValue = Phi->getIncomingValue(1);
1296 "Unexpected Phi node in the loop");
1297 BEValue = Phi->getIncomingValue(1);
1298 StartValue = Phi->getIncomingValue(0);
1305 Value *Addend =
nullptr;
1306 if (BOp->
getOpcode() == Instruction::FAdd) {
1311 }
else if (BOp->
getOpcode() == Instruction::FSub)
1319 if (
auto *
I = dyn_cast<Instruction>(Addend))
1366 assert(CastInsts.
empty() &&
"CastInsts is expected to be empty.");
1367 auto *PN = cast<PHINode>(PhiScev->
getValue());
1368 assert(PSE.
getSCEV(PN) == AR &&
"Unexpected phi node SCEV expression");
1379 auto getDef = [&](
const Value *Val) ->
Value * {
1385 Value *Def =
nullptr;
1386 if (L->isLoopInvariant(Op0))
1388 else if (L->isLoopInvariant(Op1))
1398 Value *Val = PN->getIncomingValueForBlock(Latch);
1406 bool InCastSequence =
false;
1407 auto *Inst = dyn_cast<Instruction>(Val);
1411 if (!Inst || !L->contains(Inst)) {
1414 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.
getSCEV(Val));
1416 InCastSequence =
true;
1417 if (InCastSequence) {
1420 if (!CastInsts.
empty())
1421 if (!Inst->hasOneUse())
1428 Inst = dyn_cast<Instruction>(Val);
1431 return InCastSequence;
1437 Type *PhiTy = Phi->getType();
1451 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1463 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1469 if (PhiScev != AR && SymbolicPhi) {
1482 Type *PhiTy = Phi->getType();
1488 const SCEV *PhiScev = Expr ? Expr : SE->
getSCEV(Phi);
1496 if (AR->
getLoop() != TheLoop) {
1500 dbgs() <<
"LV: PHI is a recurrence with respect to an outer loop.\n");
1508 &&
"Invalid Phi node, not present in loop header");
1520 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1526 dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR, SmallVectorImpl< Instruction * > &CastInsts)
This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expr...
static void collectCastInstrs(Loop *TheLoop, Instruction *Exit, Type *RecurrenceType, SmallPtrSetImpl< Instruction * > &Casts, unsigned &MinWidthCastToRecurTy)
Collect cast instructions that can be ignored in the vectorizer's cost model, given a reduction exit ...
static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst, Instruction *Exit, PHINode *Phi)
static Instruction * lookThroughAnd(PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction * > &Visited, SmallPtrSetImpl< Instruction * > &CI)
Determines if Phi may have been type-promoted.
static std::pair< Type *, bool > computeRecurrenceType(Instruction *Exit, DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT)
Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit...
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Module.h This file contains the declarations for the Module class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
BinaryOps getOpcode() const
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
static Constant * getInfinity(Type *Ty, bool Negative=false)
This is the shared class of boolean and integer constants.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Convenience struct for specifying and reasoning about fast-math flags.
bool noSignedZeros() const
void setNoSignedZeros(bool B=true)
void setNoNaNs(bool B=true)
static FastMathFlags getFast()
A struct for saving information about induction variables.
@ IK_FpInduction
Floating point induction variable.
@ IK_PtrInduction
Pointer induction var. Step = C.
@ IK_IntInduction
Integer induction variable. Step = C.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D)
Returns true if Phi is a floating point induction in the loop L.
InductionDescriptor()=default
Default constructor - creates an invalid induction.
ConstantInt * getConstIntStepValue() const
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
const BasicBlock * getParent() const
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
BlockT * getHeader() const
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
This POD struct holds information about a potential recurrence operation.
RecurKind getRecKind() const
Instruction * getPatternInst() const
bool isRecurrence() const
Instruction * getExactFPMathInst() const
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
static bool isFPMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating-point min/max kind.
static bool isFMulAddIntrinsic(Instruction *I)
Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
static bool isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, DominatorTree *DT)
Returns true if Phi is a fixed-order recurrence.
unsigned getOpcode() const
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction * > &Insts, unsigned MaxNumUses)
Returns true if instruction I has multiple uses in Insts.
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction in TheLoop.
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction * > &Set)
Returns true if all uses of the instruction I is within the Set.
TrackingVH< Value > getRecurrenceStartValue() const
SmallVector< Instruction *, 4 > getReductionOpChain(PHINode *Phi, Loop *L) const
Attempts to find a chain of operations from Phi to LoopExitInst that can be treated as a set of reduc...
static bool isAnyOfRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
static InstDesc isAnyOfPattern(Loop *Loop, PHINode *OrigPhi, Instruction *I, InstDesc &Prev)
Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...
static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I)
Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode),...
Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const
Returns identity corresponding to the RecurrenceKind.
StoreInst * IntermediateStore
Reductions may store temporary or final result to an invariant address.
static bool isFloatingPointRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating point kind.
static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I, RecurKind Kind, InstDesc &Prev, FastMathFlags FuncFMF)
Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a ...
static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind, const InstDesc &Prev)
Returns a struct describing if the instruction is a llvm.
static bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.
static bool isIntegerRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer kind.
static bool isIntMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer min/max kind.
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
const Loop * getLoop() const
This class represents a constant integer value.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
const SCEV * getUnknown(Value *V)
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Value * getPointerOperand()
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
bool isHalfTy() const
Return true if this is 'half', a 16-bit IEEE fp type.
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
MaxMin_match< FCmpInst, LHS, RHS, ufmin_pred_ty > m_UnordFMin(const LHS &L, const RHS &R)
Match an 'unordered' floating point minimum function.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
MaxMin_match< FCmpInst, LHS, RHS, ufmax_pred_ty > m_UnordFMax(const LHS &L, const RHS &R)
Match an 'unordered' floating point maximum function.
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
MaxMin_match< FCmpInst, LHS, RHS, ofmax_pred_ty > m_OrdFMax(const LHS &L, const RHS &R)
Match an 'ordered' floating point maximum function.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty > m_OrdFMin(const LHS &L, const RHS &R)
Match an 'ordered' floating point minimum function.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
This is an optimization pass for GlobalISel generic memory operations.
T bit_ceil(T Value)
Returns the smallest integral power of two no smaller than Value if Value is nonzero.
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
RecurKind
These are the kinds of recurrences that we support.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ FAnyOf
Any_of reduction with select(fcmp(),x,y) where one of (x,y) is loop invariant, and both x and y are i...
@ Or
Bitwise or logical OR of integers.
@ FMinimum
FP min with llvm.minimum semantics.
@ Mul
Product of integers.
@ Xor
Bitwise or logical XOR of integers.
@ FMax
FP max implemented in terms of select(cmp()).
@ FMaximum
FP max with llvm.maximum semantics.
@ FMulAdd
Sum of float products with llvm.fmuladd(a * b + sum).
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ And
Bitwise or logical AND of integers.
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ FMin
FP min implemented in terms of select(cmp()).
@ IAnyOf
Any_of reduction with select(icmp(),x,y) where one of (x,y) is loop invariant, and both x and y are i...
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?