32#define DEBUG_TYPE "iv-descriptors"
36 for (
const Use &
Use :
I->operands())
37 if (!Set.
count(dyn_cast<Instruction>(
Use)))
76 const APInt *M =
nullptr;
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");
242 bool FoundReduxOp =
false;
248 bool FoundStartPHI =
false;
253 unsigned NumCmpSelectPatternInst = 0;
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");
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);
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);
419 if (IsAPhi && Cur != Phi && !
areAllUsesIn(Cur, VisitedInsts))
423 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
424 ++NumCmpSelectPatternInst;
426 (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
427 ++NumCmpSelectPatternInst;
430 FoundReduxOp |= !IsAPhi && Cur != Start;
451 if (ExitInstruction == Cur)
458 if (ExitInstruction !=
nullptr || Cur == Phi)
467 ExitInstruction = Cur;
474 InstDesc IgnoredVal(
false,
nullptr);
475 if (VisitedInsts.
insert(UI).second) {
476 if (isa<PHINode>(UI)) {
480 if (
SI &&
SI->getPointerOperand() == Cur) {
487 }
else if (!isa<PHINode>(UI) &&
488 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
489 !isa<SelectInst>(UI)) ||
498 FoundStartPHI =
true;
508 NumCmpSelectPatternInst != 0)
526 if (ExitInstruction &&
528 LLVM_DEBUG(
dbgs() <<
"Last store Instruction of reduction value does not "
529 "store last calculated value of the reduction: "
536 if (!ExitInstruction)
540 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
543 const bool IsOrdered =
572 std::tie(ComputedType, IsSigned) =
574 if (ComputedType != RecurrenceType)
592 MinWidthCastToRecurrenceType);
602 FMF, ExactFPMathInst, RecurrenceType, IsSigned,
603 IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
637 if (
auto *
Select = dyn_cast<SelectInst>(*
I->user_begin()))
647 Value *NonPhi =
nullptr;
649 if (OrigPhi == dyn_cast<PHINode>(
SI->getTrueValue()))
650 NonPhi =
SI->getFalseValue();
651 else if (OrigPhi == dyn_cast<PHINode>(
SI->getFalseValue()))
652 NonPhi =
SI->getTrueValue();
669 assert((isa<CmpInst>(
I) || isa<SelectInst>(
I) || isa<CallInst>(
I)) &&
670 "Expected a cmp or select or call instruction");
678 if (
auto *
Select = dyn_cast<SelectInst>(*
I->user_begin()))
683 if (!isa<IntrinsicInst>(
I) &&
728 CmpInst *CI = dyn_cast<CmpInst>(
SI->getCondition());
733 Value *TrueVal =
SI->getTrueValue();
734 Value *FalseVal =
SI->getFalseValue();
737 if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
738 (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
742 isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
743 : dyn_cast<Instruction>(TrueVal);
744 if (!I1 || !I1->isBinaryOp())
757 Instruction *IPhi = isa<PHINode>(*Op1) ? dyn_cast<Instruction>(Op1)
758 : dyn_cast<Instruction>(Op2);
759 if (!IPhi || IPhi != FalseVal)
770 switch (
I->getOpcode()) {
773 case Instruction::PHI:
775 case Instruction::Sub:
776 case Instruction::Add:
778 case Instruction::Mul:
780 case Instruction::And:
782 case Instruction::Or:
784 case Instruction::Xor:
786 case Instruction::FDiv:
787 case Instruction::FMul:
789 I->hasAllowReassoc() ?
nullptr :
I);
790 case Instruction::FSub:
791 case Instruction::FAdd:
793 I->hasAllowReassoc() ?
nullptr :
I);
794 case Instruction::Select:
799 case Instruction::FCmp:
800 case Instruction::ICmp:
801 case Instruction::Call:
806 (isa<FPMathOperator>(
I) &&
I->hasNoNaNs() &&
807 I->hasNoSignedZeros())) &&
812 I->hasAllowReassoc() ?
nullptr :
I);
819 unsigned MaxNumUses) {
820 unsigned NumUses = 0;
821 for (
const Use &U :
I->operands()) {
822 if (Insts.
count(dyn_cast<Instruction>(U)))
824 if (NumUses > MaxNumUses)
840 F.getFnAttribute(
"no-nans-fp-math").getValueAsBool());
842 F.getFnAttribute(
"no-signed-zeros-fp-math").getValueAsBool());
846 LLVM_DEBUG(
dbgs() <<
"Found an ADD reduction PHI." << *Phi <<
"\n");
851 LLVM_DEBUG(
dbgs() <<
"Found a MUL reduction PHI." << *Phi <<
"\n");
856 LLVM_DEBUG(
dbgs() <<
"Found an OR reduction PHI." << *Phi <<
"\n");
861 LLVM_DEBUG(
dbgs() <<
"Found an AND reduction PHI." << *Phi <<
"\n");
866 LLVM_DEBUG(
dbgs() <<
"Found a XOR reduction PHI." << *Phi <<
"\n");
871 LLVM_DEBUG(
dbgs() <<
"Found a SMAX reduction PHI." << *Phi <<
"\n");
876 LLVM_DEBUG(
dbgs() <<
"Found a SMIN reduction PHI." << *Phi <<
"\n");
881 LLVM_DEBUG(
dbgs() <<
"Found a UMAX reduction PHI." << *Phi <<
"\n");
886 LLVM_DEBUG(
dbgs() <<
"Found a UMIN reduction PHI." << *Phi <<
"\n");
891 LLVM_DEBUG(
dbgs() <<
"Found an integer conditional select reduction PHI."
897 LLVM_DEBUG(
dbgs() <<
"Found an FMult reduction PHI." << *Phi <<
"\n");
902 LLVM_DEBUG(
dbgs() <<
"Found an FAdd reduction PHI." << *Phi <<
"\n");
907 LLVM_DEBUG(
dbgs() <<
"Found a float MAX reduction PHI." << *Phi <<
"\n");
912 LLVM_DEBUG(
dbgs() <<
"Found a float MIN reduction PHI." << *Phi <<
"\n");
917 LLVM_DEBUG(
dbgs() <<
"Found a float conditional select reduction PHI."
918 <<
" PHI." << *Phi <<
"\n");
923 LLVM_DEBUG(
dbgs() <<
"Found an FMulAdd reduction PHI." << *Phi <<
"\n");
943 if (!Preheader || !Latch)
960 while (
auto *PrevPhi = dyn_cast_or_null<PHINode>(Previous)) {
961 if (PrevPhi->getParent() != Phi->
getParent())
963 if (!SeenPhis.
insert(PrevPhi).second)
965 Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch));
968 if (!Previous || !TheLoop->
contains(Previous) || isa<PHINode>(Previous) ||
969 SinkAfter.
count(Previous))
982 return A->comesBefore(
B);
984 std::set<
Instruction *,
decltype(CompareByComesBefore)> InstrsToSink(
985 CompareByComesBefore);
989 auto TryToPushSinkCandidate = [&](
Instruction *SinkCandidate) {
991 if (SinkCandidate->getParent() == PhiBB &&
992 InstrsToSink.find(SinkCandidate) != InstrsToSink.
end())
996 if (Previous == SinkCandidate)
1003 if (SinkCandidate->getParent() != PhiBB ||
1004 SinkCandidate->mayHaveSideEffects() ||
1005 SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
1011 auto It = SinkAfter.
find(SinkCandidate);
1012 if (It != SinkAfter.
end()) {
1013 auto *OtherPrev = It->second;
1016 auto EarlierIt = SinkAfter.
find(OtherPrev);
1017 while (EarlierIt != SinkAfter.
end()) {
1019 EarlierIt = SinkAfter.
find(EarlierInst);
1021 if (EarlierIt != SinkAfter.
end() &&
1024 OtherPrev = EarlierInst;
1027 if (OtherPrev != It->second && !DT->
dominates(It->second, OtherPrev))
1032 if (DT->
dominates(Previous, OtherPrev) || Previous == OtherPrev)
1039 [SinkCandidate](
const std::pair<Instruction *, Instruction *> &
P) {
1040 return P.second == SinkCandidate;
1047 SinkAfter.
erase(SinkCandidate);
1052 if (isa<PHINode>(SinkCandidate))
1056 InstrsToSink.insert(SinkCandidate);
1063 while (!WorkList.
empty()) {
1066 if (!TryToPushSinkCandidate(cast<Instruction>(
User)))
1073 SinkAfter[
I] = Previous;
1121 "nnan, nsz is expected to be set for FP min reduction.");
1125 "nnan, nsz is expected to be set for FP max reduction.");
1139 return Instruction::Add;
1141 return Instruction::Mul;
1143 return Instruction::Or;
1145 return Instruction::And;
1147 return Instruction::Xor;
1149 return Instruction::FMul;
1152 return Instruction::FAdd;
1158 return Instruction::ICmp;
1162 return Instruction::FCmp;
1188 unsigned ExpectedUses = 1;
1189 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp)
1195 if (isa<PHINode>(UI))
1197 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1200 if (isa<SelectInst>(UI))
1209 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1218 return Cur->getOpcode() == RedOp;
1222 unsigned ExtraPhiUses = 0;
1224 if (
auto ExitPhi = dyn_cast<PHINode>(LoopExitInstr)) {
1225 if (ExitPhi->getNumIncomingValues() != 2)
1228 Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0));
1229 Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1));
1234 else if (Inc1 == Phi)
1247 if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->
hasNUses(2))
1252 if (!Phi->
hasNUses(ExpectedUses + ExtraPhiUses))
1259 while (Cur != RdxInstr) {
1260 if (!Cur || !isCorrectOpcode(Cur) || !Cur->
hasNUses(ExpectedUses))
1264 Cur = getNextInstruction(Cur);
1268 return ReductionOperations;
1275 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp),
1276 ElementType(ElementType) {
1277 assert(IK != IK_NoInduction &&
"Not an induction");
1281 assert(StartValue &&
"StartValue is null");
1283 "StartValue is not a pointer for pointer induction");
1285 "StartValue is not an integer for integer induction");
1288 assert((!getConstIntStepValue() || !getConstIntStepValue()->
isZero()) &&
1289 "Step value is zero");
1291 assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
1292 "Step value should be constant for pointer induction");
1294 "StepValue is not an integer");
1297 "StepValue is not FP for FpInduction");
1298 assert((IK != IK_FpInduction ||
1300 (InductionBinOp->getOpcode() == Instruction::FAdd ||
1301 InductionBinOp->getOpcode() == Instruction::FSub))) &&
1302 "Binary opcode should be specified for FP induction");
1304 if (IK == IK_PtrInduction)
1305 assert(ElementType &&
"Pointer induction must have element type");
1307 assert(!ElementType &&
"Non-pointer induction cannot have element type");
1310 for (
auto &Inst : *Casts) {
1311 RedundantCasts.push_back(Inst);
1317 if (isa<SCEVConstant>(Step))
1318 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
1336 Value *BEValue =
nullptr, *StartValue =
nullptr;
1342 "Unexpected Phi node in the loop");
1351 Value *Addend =
nullptr;
1352 if (BOp->
getOpcode() == Instruction::FAdd) {
1357 }
else if (BOp->
getOpcode() == Instruction::FSub)
1365 if (
auto *
I = dyn_cast<Instruction>(Addend))
1412 assert(CastInsts.
empty() &&
"CastInsts is expected to be empty.");
1413 auto *PN = cast<PHINode>(PhiScev->
getValue());
1414 assert(PSE.
getSCEV(PN) == AR &&
"Unexpected phi node SCEV expression");
1425 auto getDef = [&](
const Value *Val) ->
Value * {
1431 Value *Def =
nullptr;
1432 if (L->isLoopInvariant(Op0))
1434 else if (L->isLoopInvariant(Op1))
1444 Value *Val = PN->getIncomingValueForBlock(Latch);
1452 bool InCastSequence =
false;
1453 auto *Inst = dyn_cast<Instruction>(Val);
1457 if (!Inst || !L->contains(Inst)) {
1460 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.
getSCEV(Val));
1462 InCastSequence =
true;
1463 if (InCastSequence) {
1466 if (!CastInsts.
empty())
1467 if (!Inst->hasOneUse())
1474 Inst = dyn_cast<Instruction>(Val);
1477 return InCastSequence;
1497 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1509 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1515 if (PhiScev != AR && SymbolicPhi) {
1534 const SCEV *PhiScev = Expr ? Expr : SE->
getSCEV(Phi);
1542 if (AR->
getLoop() != TheLoop) {
1546 dbgs() <<
"LV: PHI is a recurrence with respect to an outer loop.\n");
1560 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1568 nullptr, CastsToIgnore);
1587 TypeSize TySize =
DL.getTypeAllocSize(ElementType);
1601 nullptr, ElementType);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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.
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
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.
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
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 / sizeof(elem).
@ 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.
This class implements a map that also provides access to all stored values in a deterministic order.
size_type count(const KeyT &Key) const
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
iterator find(const KeyT &Key)
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Class to represent pointers.
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.
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 isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, MapVector< Instruction *, Instruction * > &SinkAfter, DominatorTree *DT)
Returns true if Phi is a fixed-order recurrence.
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 InstDesc isSelectCmpPattern(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.
static bool isSelectCmpRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
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.
ConstantInt * getValue() const
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 * getConstant(ConstantInt *V)
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.
Type * getNonOpaquePointerElementType() const
Only use this method in code that is not reachable with opaque pointers, or part of deprecated method...
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
bool isHalfTy() const
Return true if this is 'half', a 16-bit IEEE fp type.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
static IntegerType * getInt8Ty(LLVMContext &C)
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.
constexpr ScalarTy getFixedValue() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
constexpr bool isZero() const
#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.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
RecurKind
These are the kinds of recurrences that we support.
@ UMin
Unisgned integer min implemented in terms of select(cmp()).
@ Or
Bitwise or logical OR of integers.
@ SelectFCmp
Integer select(fcmp(),x,y) where one of (x,y) is loop invariant.
@ Mul
Product of integers.
@ Xor
Bitwise or logical XOR of integers.
@ FMax
FP max implemented in terms of select(cmp()).
@ FMulAdd
Fused multiply-add of floats (a * b + c).
@ 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()).
@ SelectICmp
Integer select(icmp(),x,y) where one of (x,y) is loop invariant.
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
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?