{}
};
-/// This POD struct holds information about a potential reduction operation.
-class ReductionInstDesc {
+/// The RecurrenceDescriptor is used to identify recurrences variables in a
+/// loop. Reduction is a special case of recurrence that has uses of the
+/// recurrence variable outside the loop. The method isReductionPHI identifies
+/// reductions that are basic recurrences.
+///
+/// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
+/// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
+/// array[i]; } is a summation of array elements. Basic recurrences are a
+/// special case of chains of recurrences (CR). See ScalarEvolution for CR
+/// references.
+
+/// This struct holds information about recurrence variables.
+class RecurrenceDescriptor {
public:
- // This enum represents the kind of minmax reduction.
- enum MinMaxReductionKind {
+ /// This enum represents the kinds of recurrences that we support.
+ enum RecurrenceKind {
+ RK_NoRecurrence, ///< Not a recurrence.
+ RK_IntegerAdd, ///< Sum of integers.
+ RK_IntegerMult, ///< Product of integers.
+ RK_IntegerOr, ///< Bitwise or logical OR of numbers.
+ RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
+ RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
+ RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
+ RK_FloatAdd, ///< Sum of floats.
+ RK_FloatMult, ///< Product of floats.
+ RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
+ };
+
+ // This enum represents the kind of minmax recurrence.
+ enum MinMaxRecurrenceKind {
MRK_Invalid,
MRK_UIntMin,
MRK_UIntMax,
MRK_FloatMin,
MRK_FloatMax
};
- ReductionInstDesc(bool IsRedux, Instruction *I)
- : IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {}
- ReductionInstDesc(Instruction *I, MinMaxReductionKind K)
- : IsReduction(true), PatternLastInst(I), MinMaxKind(K) {}
+ RecurrenceDescriptor()
+ : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence),
+ MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr),
+ RecurrenceType(nullptr), IsSigned(false) {}
+
+ RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
+ MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
+ bool Signed, SmallPtrSetImpl<Instruction *> &CI)
+ : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
+ UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
+ CastInsts.insert(CI.begin(), CI.end());
+ }
- bool isReduction() { return IsReduction; }
+ /// This POD struct holds information about a potential recurrence operation.
+ class InstDesc {
- MinMaxReductionKind getMinMaxKind() { return MinMaxKind; }
-
- Instruction *getPatternInst() { return PatternLastInst; }
+ public:
+ InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
+ : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
+ UnsafeAlgebraInst(UAI) {}
-private:
- // Is this instruction a reduction candidate.
- bool IsReduction;
- // The last instruction in a min/max pattern (select of the select(icmp())
- // pattern), or the current reduction instruction otherwise.
- Instruction *PatternLastInst;
- // If this is a min/max pattern the comparison predicate.
- MinMaxReductionKind MinMaxKind;
-};
+ InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
+ : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
+ UnsafeAlgebraInst(UAI) {}
-/// This struct holds information about reduction variables.
-class ReductionDescriptor {
+ bool isRecurrence() { return IsRecurrence; }
-public:
- /// This enum represents the kinds of reductions that we support.
- enum ReductionKind {
- RK_NoReduction, ///< Not a reduction.
- RK_IntegerAdd, ///< Sum of integers.
- RK_IntegerMult, ///< Product of integers.
- RK_IntegerOr, ///< Bitwise or logical OR of numbers.
- RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
- RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
- RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
- RK_FloatAdd, ///< Sum of floats.
- RK_FloatMult, ///< Product of floats.
- RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
- };
+ bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
- ReductionDescriptor()
- : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoReduction),
- MinMaxKind(ReductionInstDesc::MRK_Invalid) {}
+ Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
- ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K,
- ReductionInstDesc::MinMaxReductionKind MK)
- : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {}
+ MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
- /// Returns a struct describing if the instruction 'I' can be a reduction
- /// variable of type 'Kind'. If the reduction is a min/max pattern of
+ Instruction *getPatternInst() { return PatternLastInst; }
+
+ private:
+ // Is this instruction a recurrence candidate.
+ bool IsRecurrence;
+ // The last instruction in a min/max pattern (select of the select(icmp())
+ // pattern), or the current recurrence instruction otherwise.
+ Instruction *PatternLastInst;
+ // If this is a min/max pattern the comparison predicate.
+ MinMaxRecurrenceKind MinMaxKind;
+ // Recurrence has unsafe algebra.
+ Instruction *UnsafeAlgebraInst;
+ };
+
+ /// Returns a struct describing if the instruction 'I' can be a recurrence
+ /// variable of type 'Kind'. If the recurrence is a min/max pattern of
/// select(icmp()) this function advances the instruction pointer 'I' from the
/// compare instruction to the select instruction and stores this pointer in
/// 'PatternLastInst' member of the returned struct.
- static ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind,
- ReductionInstDesc &Prev,
- bool HasFunNoNaNAttr);
+ static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
+ InstDesc &Prev, bool HasFunNoNaNAttr);
- /// Returns true if instuction I has multiple uses in Insts
+ /// Returns true if instruction I has multiple uses in Insts
static bool hasMultipleUsesOf(Instruction *I,
SmallPtrSetImpl<Instruction *> &Insts);
/// Returns a struct describing if the instruction if the instruction is a
/// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
/// or max(X, Y).
- static ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I,
- ReductionInstDesc &Prev);
+ static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
- /// Returns identity corresponding to the ReductionKind.
- static Constant *getReductionIdentity(ReductionKind K, Type *Tp);
+ /// Returns identity corresponding to the RecurrenceKind.
+ static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
- /// Returns the opcode of binary operation corresponding to the ReductionKind.
- static unsigned getReductionBinOp(ReductionKind Kind);
+ /// Returns the opcode of binary operation corresponding to the
+ /// RecurrenceKind.
+ static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
- /// Returns a Min/Max operation corresponding to MinMaxReductionKind.
- static Value *createMinMaxOp(IRBuilder<> &Builder,
- ReductionInstDesc::MinMaxReductionKind RK,
+ /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
+ static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK,
Value *Left, Value *Right);
/// Returns true if Phi is a reduction of type Kind and adds it to the
- /// ReductionDescriptor.
- static bool AddReductionVar(PHINode *Phi, ReductionKind Kind, Loop *TheLoop,
+ /// RecurrenceDescriptor.
+ static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
bool HasFunNoNaNAttr,
- ReductionDescriptor &RedDes);
+ RecurrenceDescriptor &RedDes);
- /// Returns true if Phi is a reduction in TheLoop. The ReductionDescriptor is
+ /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
/// returned in RedDes.
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
- ReductionDescriptor &RedDes);
+ RecurrenceDescriptor &RedDes);
- ReductionKind getReductionKind() { return Kind; }
+ RecurrenceKind getRecurrenceKind() { return Kind; }
- ReductionInstDesc::MinMaxReductionKind getMinMaxReductionKind() {
- return MinMaxKind;
- }
+ MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
- TrackingVH<Value> getReductionStartValue() { return StartValue; }
+ TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
Instruction *getLoopExitInstr() { return LoopExitInstr; }
+ /// Returns true if the recurrence has unsafe algebra which requires a relaxed
+ /// floating-point model.
+ bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
+
+ /// Returns first unsafe algebra instruction in the PHI node's use-chain.
+ Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
+
+ /// Returns true if the recurrence kind is an integer kind.
+ static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
+
+ /// Returns true if the recurrence kind is a floating point kind.
+ static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
+
+ /// Returns true if the recurrence kind is an arithmetic kind.
+ static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
+
+ /// Determines if Phi may have been type-promoted. If Phi has a single user
+ /// that ANDs the Phi with a type mask, return the user. RT is updated to
+ /// account for the narrower bit width represented by the mask, and the AND
+ /// instruction is added to CI.
+ static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
+ SmallPtrSetImpl<Instruction *> &Visited,
+ SmallPtrSetImpl<Instruction *> &CI);
+
+ /// Returns true if all the source operands of a recurrence are either
+ /// SExtInsts or ZExtInsts. This function is intended to be used with
+ /// lookThroughAnd to determine if the recurrence has been type-promoted. The
+ /// source operands are added to CI, and IsSigned is updated to indicate if
+ /// all source operands are SExtInsts.
+ static bool getSourceExtensionKind(Instruction *Start, Instruction *Exit,
+ Type *RT, bool &IsSigned,
+ SmallPtrSetImpl<Instruction *> &Visited,
+ SmallPtrSetImpl<Instruction *> &CI);
+
+ /// Returns the type of the recurrence. This type can be narrower than the
+ /// actual type of the Phi if the recurrence has been type-promoted.
+ Type *getRecurrenceType() { return RecurrenceType; }
+
+ /// Returns a reference to the instructions used for type-promoting the
+ /// recurrence.
+ SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
+
+ /// Returns true if all source operands of the recurrence are SExtInsts.
+ bool isSigned() { return IsSigned; }
+
private:
- // The starting value of the reduction.
+ // The starting value of the recurrence.
// It does not have to be zero!
TrackingVH<Value> StartValue;
// The instruction who's value is used outside the loop.
Instruction *LoopExitInstr;
- // The kind of the reduction.
- ReductionKind Kind;
- // If this a min/max reduction the kind of reduction.
- ReductionInstDesc::MinMaxReductionKind MinMaxKind;
+ // The kind of the recurrence.
+ RecurrenceKind Kind;
+ // If this a min/max recurrence the kind of recurrence.
+ MinMaxRecurrenceKind MinMaxKind;
+ // First occurance of unasfe algebra in the PHI's use-chain.
+ Instruction *UnsafeAlgebraInst;
+ // The type of the recurrence.
+ Type *RecurrenceType;
+ // True if all source operands of the recurrence are SExtInsts.
+ bool IsSigned;
+ // Instructions used for type-promoting the recurrence.
+ SmallPtrSet<Instruction *, 8> CastInsts;
+};
+
+/// A struct for saving information about induction variables.
+class InductionDescriptor {
+public:
+ /// This enum represents the kinds of inductions that we support.
+ enum InductionKind {
+ IK_NoInduction, ///< Not an induction variable.
+ IK_IntInduction, ///< Integer induction variable. Step = C.
+ IK_PtrInduction ///< Pointer induction var. Step = C / sizeof(elem).
+ };
+
+private:
+ /// Private constructor - use \c isInductionPHI.
+ InductionDescriptor(Value *Start, InductionKind K, ConstantInt *Step);
+public:
+ /// Default constructor - creates an invalid induction.
+ InductionDescriptor()
+ : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {}
+
+ /// Get the consecutive direction. Returns:
+ /// 0 - unknown or non-consecutive.
+ /// 1 - consecutive and increasing.
+ /// -1 - consecutive and decreasing.
+ int getConsecutiveDirection() const;
+
+ /// Compute the transformed value of Index at offset StartValue using step
+ /// StepValue.
+ /// For integer induction, returns StartValue + Index * StepValue.
+ /// For pointer induction, returns StartValue[Index * StepValue].
+ /// FIXME: The newly created binary instructions should contain nsw/nuw
+ /// flags, which can be found from the original scalar operations.
+ Value *transform(IRBuilder<> &B, Value *Index) const;
+
+ Value *getStartValue() const { return StartValue; }
+ InductionKind getKind() const { return IK; }
+ ConstantInt *getStepValue() const { return StepValue; }
+
+ static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
+ InductionDescriptor &D);
+
+private:
+ /// Start value.
+ TrackingVH<Value> StartValue;
+ /// Induction kind.
+ InductionKind IK;
+ /// Step value.
+ ConstantInt *StepValue;
};
BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
/// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
/// passed into it.
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
- AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr,
- AssumptionCache *AC = nullptr);
+ ScalarEvolution *SE = nullptr, AssumptionCache *AC = nullptr);
/// \brief Put loop into LCSSA form.
///
/// first order w.r.t the DominatorTree. This allows us to visit definitions
/// before uses, allowing us to hoist a loop body in one pass without iteration.
/// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
-/// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
+/// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
/// loop and loop safety information as arguments. It returns changed status.
bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
TargetLibraryInfo *, Loop *, AliasSetTracker *,
LICMSafetyInfo *);
-/// \brief Try to promote memory values to scalars by sinking stores out of
+/// \brief Try to promote memory values to scalars by sinking stores out of
/// the loop and moving loads to before the loop. We do this by looping over
/// the stores in the loop, looking for stores to Must pointers which are
/// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
LICMSafetyInfo *);
/// \brief Computes safety information for a loop
-/// checks loop body & header for the possiblity of may throw
+/// checks loop body & header for the possibility of may throw
/// exception, it takes LICMSafetyInfo and loop as argument.
/// Updates safety information in LICMSafetyInfo argument.
void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
-/// \brief Checks if the given PHINode in a loop header is an induction
-/// variable. Returns true if this is an induction PHI along with the step
-/// value.
-bool isInductionPHI(PHINode *, ScalarEvolution *, ConstantInt *&);
+/// \brief Returns the instructions that use values defined in the loop.
+SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
}
#endif
projects / oota-llvm.git / blobdiff