32#define DEBUG_TYPE "iv-descriptors"
36 for (
const Use &
Use :
I->operands())
37 if (!Set.
count(dyn_cast<Instruction>(
Use)))
73 if (!Phi->hasOneUse())
76 const APInt *M =
nullptr;
77 Instruction *
I, *J = cast<Instruction>(Phi->use_begin()->getUser());
82 int32_t Bits = (*M + 1).exactLogBase2();
99 bool IsSigned =
false;
109 auto Mask = DB->getDemandedBits(Exit);
110 MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero();
113 if (MaxBitWidth ==
DL.getTypeSizeInBits(Exit->
getType()) && AC && DT) {
118 auto NumTypeBits =
DL.getTypeSizeInBits(Exit->
getType());
119 MaxBitWidth = NumTypeBits - NumSignBits;
121 if (!Bits.isNonNegative()) {
142 Type *RecurrenceType,
144 unsigned &MinWidthCastToRecurTy) {
149 MinWidthCastToRecurTy = -1U;
151 while (!Worklist.
empty()) {
154 if (
auto *Cast = dyn_cast<CastInst>(Val)) {
155 if (Cast->getSrcTy() == RecurrenceType) {
162 if (Cast->getDestTy() == RecurrenceType) {
167 MinWidthCastToRecurTy = std::min<unsigned>(
168 MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits());
174 for (
Value *O : cast<User>(Val)->operands())
175 if (
auto *
I = dyn_cast<Instruction>(O))
209 LLVM_DEBUG(
dbgs() <<
"LV: Found an ordered reduction: Phi: " << *Phi
210 <<
", ExitInst: " << *Exit <<
"\n");
219 if (Phi->getNumIncomingValues() != 2)
223 if (Phi->getParent() != TheLoop->
getHeader())
242 bool FoundReduxOp =
false;
248 bool FoundStartPHI =
false;
253 unsigned NumCmpSelectPatternInst = 0;
257 Type *RecurrenceType = Phi->getType();
259 unsigned MinWidthCastToRecurrenceType;
261 bool IsSigned =
false;
278 Start =
lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
285 VisitedInsts.
insert(Start);
314 while (!Worklist.
empty()) {
319 if (
auto *SI = dyn_cast<StoreInst>(Cur)) {
321 LLVM_DEBUG(
dbgs() <<
"Store instructions are not processed without "
322 <<
"Scalar Evolution Analysis\n");
326 const SCEV *PtrScev = SE->
getSCEV(SI->getPointerOperand());
329 const SCEV *OtherScev =
332 if (OtherScev != PtrScev) {
333 LLVM_DEBUG(
dbgs() <<
"Storing reduction value to different addresses "
334 <<
"inside the loop: " << *SI->getPointerOperand()
343 LLVM_DEBUG(
dbgs() <<
"Storing reduction value to non-uniform address "
344 <<
"inside the loop: " << *SI->getPointerOperand()
360 bool IsAPhi = isa<PHINode>(Cur);
363 if (Cur != Phi && IsAPhi && Cur->
getParent() == Phi->getParent())
368 if (!Cur->
isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
369 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
379 ExactFPMathInst = ExactFPMathInst ==
nullptr
387 if (
auto *Sel = dyn_cast<SelectInst>(ReduxDesc.
getPatternInst())) {
392 if (
auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
393 CurFMF |= FCmp->getFastMathFlags();
404 bool IsASelect = isa<SelectInst>(Cur);
418 if (IsAPhi && Cur != Phi && !
areAllUsesIn(Cur, VisitedInsts))
422 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
423 ++NumCmpSelectPatternInst;
425 (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
426 ++NumCmpSelectPatternInst;
429 FoundReduxOp |= !IsAPhi && Cur != Start;
450 if (ExitInstruction == Cur)
457 if (ExitInstruction !=
nullptr || Cur == Phi)
466 ExitInstruction = Cur;
473 InstDesc IgnoredVal(
false,
nullptr);
474 if (VisitedInsts.
insert(UI).second) {
475 if (isa<PHINode>(UI)) {
479 if (SI && SI->getPointerOperand() == Cur) {
486 }
else if (!isa<PHINode>(UI) &&
487 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
488 !isa<SelectInst>(UI)) ||
497 FoundStartPHI =
true;
507 NumCmpSelectPatternInst != 0)
525 if (ExitInstruction &&
527 LLVM_DEBUG(
dbgs() <<
"Last store Instruction of reduction value does not "
528 "store last calculated value of the reduction: "
535 if (!ExitInstruction)
539 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
542 const bool IsOrdered =
571 std::tie(ComputedType, IsSigned) =
573 if (ComputedType != RecurrenceType)
591 MinWidthCastToRecurrenceType);
601 FMF, ExactFPMathInst, RecurrenceType, IsSigned,
602 IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
636 if (
auto *
Select = dyn_cast<SelectInst>(*
I->user_begin()))
646 Value *NonPhi =
nullptr;
648 if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))
649 NonPhi = SI->getFalseValue();
650 else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))
651 NonPhi = SI->getTrueValue();
668 assert((isa<CmpInst>(
I) || isa<SelectInst>(
I) || isa<CallInst>(
I)) &&
669 "Expected a cmp or select or call instruction");
677 if (
auto *
Select = dyn_cast<SelectInst>(*
I->user_begin()))
682 if (!isa<IntrinsicInst>(
I) &&
731 CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
736 Value *TrueVal = SI->getTrueValue();
737 Value *FalseVal = SI->getFalseValue();
740 if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
741 (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
745 isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
746 : dyn_cast<Instruction>(TrueVal);
747 if (!I1 || !I1->isBinaryOp())
760 Instruction *IPhi = isa<PHINode>(*Op1) ? dyn_cast<Instruction>(Op1)
761 : dyn_cast<Instruction>(Op2);
762 if (!IPhi || IPhi != FalseVal)
773 switch (
I->getOpcode()) {
776 case Instruction::PHI:
778 case Instruction::Sub:
779 case Instruction::Add:
781 case Instruction::Mul:
783 case Instruction::And:
785 case Instruction::Or:
787 case Instruction::Xor:
789 case Instruction::FDiv:
790 case Instruction::FMul:
792 I->hasAllowReassoc() ?
nullptr :
I);
793 case Instruction::FSub:
794 case Instruction::FAdd:
796 I->hasAllowReassoc() ?
nullptr :
I);
797 case Instruction::Select:
802 case Instruction::FCmp:
803 case Instruction::ICmp:
804 case Instruction::Call:
807 auto HasRequiredFMF = [&]() {
810 if (isa<FPMathOperator>(
I) &&
I->hasNoNaNs() &&
I->hasNoSignedZeros())
822 I->hasAllowReassoc() ?
nullptr :
I);
829 unsigned MaxNumUses) {
830 unsigned NumUses = 0;
831 for (
const Use &U :
I->operands()) {
832 if (Insts.
count(dyn_cast<Instruction>(U)))
834 if (NumUses > MaxNumUses)
850 F.getFnAttribute(
"no-nans-fp-math").getValueAsBool());
852 F.getFnAttribute(
"no-signed-zeros-fp-math").getValueAsBool());
856 LLVM_DEBUG(
dbgs() <<
"Found an ADD reduction PHI." << *Phi <<
"\n");
861 LLVM_DEBUG(
dbgs() <<
"Found a MUL reduction PHI." << *Phi <<
"\n");
866 LLVM_DEBUG(
dbgs() <<
"Found an OR reduction PHI." << *Phi <<
"\n");
871 LLVM_DEBUG(
dbgs() <<
"Found an AND reduction PHI." << *Phi <<
"\n");
876 LLVM_DEBUG(
dbgs() <<
"Found a XOR reduction PHI." << *Phi <<
"\n");
881 LLVM_DEBUG(
dbgs() <<
"Found a SMAX reduction PHI." << *Phi <<
"\n");
886 LLVM_DEBUG(
dbgs() <<
"Found a SMIN reduction PHI." << *Phi <<
"\n");
891 LLVM_DEBUG(
dbgs() <<
"Found a UMAX reduction PHI." << *Phi <<
"\n");
896 LLVM_DEBUG(
dbgs() <<
"Found a UMIN reduction PHI." << *Phi <<
"\n");
901 LLVM_DEBUG(
dbgs() <<
"Found an integer conditional select reduction PHI."
907 LLVM_DEBUG(
dbgs() <<
"Found an FMult reduction PHI." << *Phi <<
"\n");
912 LLVM_DEBUG(
dbgs() <<
"Found an FAdd reduction PHI." << *Phi <<
"\n");
917 LLVM_DEBUG(
dbgs() <<
"Found a float MAX reduction PHI." << *Phi <<
"\n");
922 LLVM_DEBUG(
dbgs() <<
"Found a float MIN reduction PHI." << *Phi <<
"\n");
927 LLVM_DEBUG(
dbgs() <<
"Found a float conditional select reduction PHI."
928 <<
" PHI." << *Phi <<
"\n");
933 LLVM_DEBUG(
dbgs() <<
"Found an FMulAdd reduction PHI." << *Phi <<
"\n");
938 LLVM_DEBUG(
dbgs() <<
"Found a float MAXIMUM reduction PHI." << *Phi <<
"\n");
943 LLVM_DEBUG(
dbgs() <<
"Found a float MINIMUM reduction PHI." << *Phi <<
"\n");
954 if (Phi->getParent() != TheLoop->
getHeader() ||
955 Phi->getNumIncomingValues() != 2)
962 if (!Preheader || !Latch)
966 if (Phi->getBasicBlockIndex(Preheader) < 0 ||
967 Phi->getBasicBlockIndex(Latch) < 0)
972 auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
979 while (
auto *PrevPhi = dyn_cast_or_null<PHINode>(Previous)) {
980 if (PrevPhi->getParent() != Phi->getParent())
982 if (!SeenPhis.
insert(PrevPhi).second)
984 Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch));
987 if (!Previous || !TheLoop->
contains(Previous) || isa<PHINode>(Previous))
999 auto TryToPushSinkCandidate = [&](
Instruction *SinkCandidate) {
1001 if (Previous == SinkCandidate)
1004 if (!Seen.
insert(SinkCandidate).second)
1010 if (SinkCandidate->getParent() != PhiBB ||
1011 SinkCandidate->mayHaveSideEffects() ||
1012 SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
1017 if (isa<PHINode>(SinkCandidate))
1027 while (!WorkList.
empty()) {
1030 if (!TryToPushSinkCandidate(cast<Instruction>(
User)))
1080 "nnan, nsz is expected to be set for FP min reduction.");
1084 "nnan, nsz is expected to be set for FP max reduction.");
1102 return Instruction::Add;
1104 return Instruction::Mul;
1106 return Instruction::Or;
1108 return Instruction::And;
1110 return Instruction::Xor;
1112 return Instruction::FMul;
1115 return Instruction::FAdd;
1121 return Instruction::ICmp;
1127 return Instruction::FCmp;
1153 unsigned ExpectedUses = 1;
1154 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp)
1160 if (isa<PHINode>(UI))
1162 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1165 if (isa<SelectInst>(UI))
1174 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1183 return Cur->getOpcode() == RedOp;
1187 unsigned ExtraPhiUses = 0;
1189 if (
auto ExitPhi = dyn_cast<PHINode>(LoopExitInstr)) {
1190 if (ExitPhi->getNumIncomingValues() != 2)
1193 Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0));
1194 Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1));
1199 else if (Inc1 == Phi)
1212 if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->
hasNUses(2))
1217 if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses))
1224 while (Cur != RdxInstr) {
1225 if (!Cur || !isCorrectOpcode(Cur) || !Cur->
hasNUses(ExpectedUses))
1229 Cur = getNextInstruction(Cur);
1233 return ReductionOperations;
1239 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
1240 assert(IK != IK_NoInduction &&
"Not an induction");
1244 assert(StartValue &&
"StartValue is null");
1246 "StartValue is not a pointer for pointer induction");
1248 "StartValue is not an integer for integer induction");
1251 assert((!getConstIntStepValue() || !getConstIntStepValue()->
isZero()) &&
1252 "Step value is zero");
1255 "StepValue is not an integer");
1258 "StepValue is not FP for FpInduction");
1259 assert((IK != IK_FpInduction ||
1261 (InductionBinOp->getOpcode() == Instruction::FAdd ||
1262 InductionBinOp->getOpcode() == Instruction::FSub))) &&
1263 "Binary opcode should be specified for FP induction");
1266 for (
auto &Inst : *Casts) {
1267 RedundantCasts.push_back(Inst);
1273 if (isa<SCEVConstant>(Step))
1274 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
1283 assert(Phi->getType()->isFloatingPointTy() &&
"Unexpected Phi type");
1285 if (TheLoop->
getHeader() != Phi->getParent())
1290 if (Phi->getNumIncomingValues() != 2)
1292 Value *BEValue =
nullptr, *StartValue =
nullptr;
1293 if (TheLoop->
contains(Phi->getIncomingBlock(0))) {
1294 BEValue = Phi->getIncomingValue(0);
1295 StartValue = Phi->getIncomingValue(1);
1298 "Unexpected Phi node in the loop");
1299 BEValue = Phi->getIncomingValue(1);
1300 StartValue = Phi->getIncomingValue(0);
1307 Value *Addend =
nullptr;
1308 if (BOp->
getOpcode() == Instruction::FAdd) {
1313 }
else if (BOp->
getOpcode() == Instruction::FSub)
1321 if (
auto *
I = dyn_cast<Instruction>(Addend))
1368 assert(CastInsts.
empty() &&
"CastInsts is expected to be empty.");
1369 auto *PN = cast<PHINode>(PhiScev->
getValue());
1370 assert(PSE.
getSCEV(PN) == AR &&
"Unexpected phi node SCEV expression");
1381 auto getDef = [&](
const Value *Val) ->
Value * {
1387 Value *Def =
nullptr;
1388 if (L->isLoopInvariant(Op0))
1390 else if (L->isLoopInvariant(Op1))
1400 Value *Val = PN->getIncomingValueForBlock(Latch);
1408 bool InCastSequence =
false;
1409 auto *Inst = dyn_cast<Instruction>(Val);
1413 if (!Inst || !L->contains(Inst)) {
1416 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.
getSCEV(Val));
1418 InCastSequence =
true;
1419 if (InCastSequence) {
1422 if (!CastInsts.
empty())
1423 if (!Inst->hasOneUse())
1430 Inst = dyn_cast<Instruction>(Val);
1433 return InCastSequence;
1439 Type *PhiTy = Phi->getType();
1453 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1465 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1471 if (PhiScev != AR && SymbolicPhi) {
1484 Type *PhiTy = Phi->getType();
1490 const SCEV *PhiScev = Expr ? Expr : SE->
getSCEV(Phi);
1498 if (AR->
getLoop() != TheLoop) {
1502 dbgs() <<
"LV: PHI is a recurrence with respect to an outer loop.\n");
1510 &&
"Invalid Phi node, not present in loop header");
1522 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1528 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 * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
static Constant * getInfinity(Type *Ty, bool Negative=false)
This is the shared class of boolean and integer constants.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
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
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
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...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
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.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
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 hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
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?