Index: include/llvm/Analysis/Utils/LoopUtils.h =================================================================== --- include/llvm/Analysis/Utils/LoopUtils.h +++ include/llvm/Analysis/Utils/LoopUtils.h @@ -0,0 +1,344 @@ +//===- llvm/Analysis/Utils/LoopUtils.h - Loop utilities ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines some loop transformation utilities. ReccurenceDescriptor +// and InductionDescriptor classes are currently housed here. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_UTILS_LOOPUTILS_H +#define LLVM_ANALYSIS_UTILS_LOOPUTILS_H + +#include "llvm/IR/IRBuilder.h" + +namespace llvm { + +class AssumptionCache; +class DataLayout; +class DemandedBits; +class DominatorTree; +class Loop; +class PredicatedScalarEvolution; +class ScalarEvolution; +class SCEV; + +/// 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 &CI) + : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK), + UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) { + CastInsts.insert(CI.begin(), CI.end()); + } + + /// This POD struct holds information about a potential recurrence operation. + class InstDesc { + public: + InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr) + : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid), + UnsafeAlgebraInst(UAI) {} + + InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr) + : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K), + UnsafeAlgebraInst(UAI) {} + + bool isRecurrence() { return IsRecurrence; } + + bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } + + Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } + + MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; } + + 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 InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, + InstDesc &Prev, bool HasFunNoNaNAttr); + + /// Returns true if instruction I has multiple uses in Insts + static bool hasMultipleUsesOf(Instruction *I, + SmallPtrSetImpl &Insts); + + /// Returns true if all uses of the instruction I is within the Set. + static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl &Set); + + /// 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 InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev); + + /// Returns identity corresponding to the RecurrenceKind. + static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp); + + /// Returns the opcode of binary operation corresponding to the + /// RecurrenceKind. + static unsigned getRecurrenceBinOp(RecurrenceKind Kind); + + /// 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 + /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are + /// non-null, the minimal bit width needed to compute the reduction will be + /// computed. + static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, + bool HasFunNoNaNAttr, + RecurrenceDescriptor &RedDes, + DemandedBits *DB = nullptr, + AssumptionCache *AC = nullptr, + DominatorTree *DT = nullptr); + + /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor + /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are + /// non-null, the minimal bit width needed to compute the reduction will be + /// computed. + static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, + RecurrenceDescriptor &RedDes, + DemandedBits *DB = nullptr, + AssumptionCache *AC = nullptr, + DominatorTree *DT = nullptr); + + /// Returns true if Phi is a first-order recurrence. A first-order recurrence + /// is a non-reduction recurrence relation in which the value of the + /// recurrence in the current loop iteration equals a value defined in the + /// previous iteration. \p SinkAfter includes pairs of instructions where the + /// first will be rescheduled to appear after the second if/when the loop is + /// vectorized. It may be augmented with additional pairs if needed in order + /// to handle Phi as a first-order recurrence. + static bool + isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, + DenseMap &SinkAfter, + DominatorTree *DT); + + RecurrenceKind getRecurrenceKind() { return Kind; } + + MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } + + TrackingVH 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); + + /// 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 &getCastInsts() { return CastInsts; } + + /// Returns true if all source operands of the recurrence are SExtInsts. + bool isSigned() { return IsSigned; } + +private: + // The starting value of the recurrence. + // It does not have to be zero! + TrackingVH StartValue; + // The instruction who's value is used outside the loop. + Instruction *LoopExitInstr = nullptr; + // The kind of the recurrence. + RecurrenceKind Kind = RK_NoRecurrence; + // If this a min/max recurrence the kind of recurrence. + MinMaxRecurrenceKind MinMaxKind = MRK_Invalid; + // First occurrence of unasfe algebra in the PHI's use-chain. + Instruction *UnsafeAlgebraInst = nullptr; + // The type of the recurrence. + Type *RecurrenceType = nullptr; + // True if all source operands of the recurrence are SExtInsts. + bool IsSigned = false; + // Instructions used for type-promoting the recurrence. + SmallPtrSet 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). + IK_FpInduction ///< Floating point induction variable. + }; + +public: + /// Default constructor - creates an invalid induction. + InductionDescriptor() = default; + + /// 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, ScalarEvolution *SE, + const DataLayout& DL) const; + + Value *getStartValue() const { return StartValue; } + InductionKind getKind() const { return IK; } + const SCEV *getStep() const { return Step; } + ConstantInt *getConstIntStepValue() const; + + /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an + /// induction, the induction descriptor \p D will contain the data describing + /// this induction. If by some other means the caller has a better SCEV + /// expression for \p Phi than the one returned by the ScalarEvolution + /// analysis, it can be passed through \p Expr. If the def-use chain + /// associated with the phi includes casts (that we know we can ignore + /// under proper runtime checks), they are passed through \p CastsToIgnore. + static bool + isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, + InductionDescriptor &D, const SCEV *Expr = nullptr, + SmallVectorImpl *CastsToIgnore = nullptr); + + /// Returns true if \p Phi is a floating point induction in the loop \p L. + /// If \p Phi is an induction, the induction descriptor \p D will contain + /// the data describing this induction. + static bool isFPInductionPHI(PHINode *Phi, const Loop* L, + ScalarEvolution *SE, InductionDescriptor &D); + + /// Returns true if \p Phi is a loop \p L induction, in the context associated + /// with the run-time predicate of PSE. If \p Assume is true, this can add + /// further SCEV predicates to \p PSE in order to prove that \p Phi is an + /// induction. + /// If \p Phi is an induction, \p D will contain the data describing this + /// induction. + static bool isInductionPHI(PHINode *Phi, const Loop* L, + PredicatedScalarEvolution &PSE, + InductionDescriptor &D, bool Assume = false); + + /// Returns true if the induction type is FP and the binary operator does + /// not have the "fast-math" property. Such operation requires a relaxed FP + /// mode. + bool hasUnsafeAlgebra() { + return InductionBinOp && !cast(InductionBinOp)->isFast(); + } + + /// Returns induction operator that does not have "fast-math" property + /// and requires FP unsafe mode. + Instruction *getUnsafeAlgebraInst() { + if (!InductionBinOp || cast(InductionBinOp)->isFast()) + return nullptr; + return InductionBinOp; + } + + /// Returns binary opcode of the induction operator. + Instruction::BinaryOps getInductionOpcode() const { + return InductionBinOp ? InductionBinOp->getOpcode() : + Instruction::BinaryOpsEnd; + } + + /// Returns a reference to the type cast instructions in the induction + /// update chain, that are redundant when guarded with a runtime + /// SCEV overflow check. + const SmallVectorImpl &getCastInsts() const { + return RedundantCasts; + } + +private: + /// Private constructor - used by \c isInductionPHI. + InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step, + BinaryOperator *InductionBinOp = nullptr, + SmallVectorImpl *Casts = nullptr); + + /// Start value. + TrackingVH StartValue; + /// Induction kind. + InductionKind IK = IK_NoInduction; + /// Step value. + const SCEV *Step = nullptr; + // Instruction that advances induction variable. + BinaryOperator *InductionBinOp = nullptr; + // Instructions used for type-casts of the induction variable, + // that are redundant when guarded with a runtime SCEV overflow check. + SmallVector RedundantCasts; +}; + +} // end namespace llvm + +#endif // LLVM_ANALYSIS_UTILS_LOOPUTILS_H Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -14,351 +14,20 @@ #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/SetVector.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/DemandedBits.h" -#include "llvm/Analysis/EHPersonalities.h" -#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/Utils/LoopUtils.h" #include "llvm/IR/Dominators.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Operator.h" -#include "llvm/IR/ValueHandle.h" -#include "llvm/Support/Casting.h" namespace llvm { -class AliasSet; class AliasSetTracker; -class BasicBlock; -class DataLayout; -class Loop; class LoopInfo; +class LoopSafetyInfo; class OptimizationRemarkEmitter; -class PredicatedScalarEvolution; class PredIteratorCache; -class ScalarEvolution; -class SCEV; class TargetLibraryInfo; -class TargetTransformInfo; - - -/// 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 &CI) - : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK), - UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) { - CastInsts.insert(CI.begin(), CI.end()); - } - - /// This POD struct holds information about a potential recurrence operation. - class InstDesc { - public: - InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr) - : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid), - UnsafeAlgebraInst(UAI) {} - - InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr) - : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K), - UnsafeAlgebraInst(UAI) {} - - bool isRecurrence() { return IsRecurrence; } - - bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } - - Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } - - MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; } - - 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 InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, - InstDesc &Prev, bool HasFunNoNaNAttr); - - /// Returns true if instruction I has multiple uses in Insts - static bool hasMultipleUsesOf(Instruction *I, - SmallPtrSetImpl &Insts); - - /// Returns true if all uses of the instruction I is within the Set. - static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl &Set); - - /// 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 InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev); - - /// Returns identity corresponding to the RecurrenceKind. - static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp); - - /// Returns the opcode of binary operation corresponding to the - /// RecurrenceKind. - static unsigned getRecurrenceBinOp(RecurrenceKind Kind); - - /// 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 - /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are - /// non-null, the minimal bit width needed to compute the reduction will be - /// computed. - static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, - bool HasFunNoNaNAttr, - RecurrenceDescriptor &RedDes, - DemandedBits *DB = nullptr, - AssumptionCache *AC = nullptr, - DominatorTree *DT = nullptr); - - /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor - /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are - /// non-null, the minimal bit width needed to compute the reduction will be - /// computed. - static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, - RecurrenceDescriptor &RedDes, - DemandedBits *DB = nullptr, - AssumptionCache *AC = nullptr, - DominatorTree *DT = nullptr); - - /// Returns true if Phi is a first-order recurrence. A first-order recurrence - /// is a non-reduction recurrence relation in which the value of the - /// recurrence in the current loop iteration equals a value defined in the - /// previous iteration. \p SinkAfter includes pairs of instructions where the - /// first will be rescheduled to appear after the second if/when the loop is - /// vectorized. It may be augmented with additional pairs if needed in order - /// to handle Phi as a first-order recurrence. - static bool - isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, - DenseMap &SinkAfter, - DominatorTree *DT); - - RecurrenceKind getRecurrenceKind() { return Kind; } - - MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } - - TrackingVH 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); - - /// 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 &getCastInsts() { return CastInsts; } - - /// Returns true if all source operands of the recurrence are SExtInsts. - bool isSigned() { return IsSigned; } - -private: - // The starting value of the recurrence. - // It does not have to be zero! - TrackingVH StartValue; - // The instruction who's value is used outside the loop. - Instruction *LoopExitInstr = nullptr; - // The kind of the recurrence. - RecurrenceKind Kind = RK_NoRecurrence; - // If this a min/max recurrence the kind of recurrence. - MinMaxRecurrenceKind MinMaxKind = MRK_Invalid; - // First occurrence of unasfe algebra in the PHI's use-chain. - Instruction *UnsafeAlgebraInst = nullptr; - // The type of the recurrence. - Type *RecurrenceType = nullptr; - // True if all source operands of the recurrence are SExtInsts. - bool IsSigned = false; - // Instructions used for type-promoting the recurrence. - SmallPtrSet 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). - IK_FpInduction ///< Floating point induction variable. - }; - -public: - /// Default constructor - creates an invalid induction. - InductionDescriptor() = default; - - /// 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, ScalarEvolution *SE, - const DataLayout& DL) const; - - Value *getStartValue() const { return StartValue; } - InductionKind getKind() const { return IK; } - const SCEV *getStep() const { return Step; } - ConstantInt *getConstIntStepValue() const; - - /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an - /// induction, the induction descriptor \p D will contain the data describing - /// this induction. If by some other means the caller has a better SCEV - /// expression for \p Phi than the one returned by the ScalarEvolution - /// analysis, it can be passed through \p Expr. If the def-use chain - /// associated with the phi includes casts (that we know we can ignore - /// under proper runtime checks), they are passed through \p CastsToIgnore. - static bool - isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, - InductionDescriptor &D, const SCEV *Expr = nullptr, - SmallVectorImpl *CastsToIgnore = nullptr); - - /// Returns true if \p Phi is a floating point induction in the loop \p L. - /// If \p Phi is an induction, the induction descriptor \p D will contain - /// the data describing this induction. - static bool isFPInductionPHI(PHINode *Phi, const Loop* L, - ScalarEvolution *SE, InductionDescriptor &D); - - /// Returns true if \p Phi is a loop \p L induction, in the context associated - /// with the run-time predicate of PSE. If \p Assume is true, this can add - /// further SCEV predicates to \p PSE in order to prove that \p Phi is an - /// induction. - /// If \p Phi is an induction, \p D will contain the data describing this - /// induction. - static bool isInductionPHI(PHINode *Phi, const Loop* L, - PredicatedScalarEvolution &PSE, - InductionDescriptor &D, bool Assume = false); - - /// Returns true if the induction type is FP and the binary operator does - /// not have the "fast-math" property. Such operation requires a relaxed FP - /// mode. - bool hasUnsafeAlgebra() { - return InductionBinOp && !cast(InductionBinOp)->isFast(); - } - - /// Returns induction operator that does not have "fast-math" property - /// and requires FP unsafe mode. - Instruction *getUnsafeAlgebraInst() { - if (!InductionBinOp || cast(InductionBinOp)->isFast()) - return nullptr; - return InductionBinOp; - } - - /// Returns binary opcode of the induction operator. - Instruction::BinaryOps getInductionOpcode() const { - return InductionBinOp ? InductionBinOp->getOpcode() : - Instruction::BinaryOpsEnd; - } - - /// Returns a reference to the type cast instructions in the induction - /// update chain, that are redundant when guarded with a runtime - /// SCEV overflow check. - const SmallVectorImpl &getCastInsts() const { - return RedundantCasts; - } - -private: - /// Private constructor - used by \c isInductionPHI. - InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step, - BinaryOperator *InductionBinOp = nullptr, - SmallVectorImpl *Casts = nullptr); - - /// Start value. - TrackingVH StartValue; - /// Induction kind. - InductionKind IK = IK_NoInduction; - /// Step value. - const SCEV *Step = nullptr; - // Instruction that advances induction variable. - BinaryOperator *InductionBinOp = nullptr; - // Instructions used for type-casts of the induction variable, - // that are redundant when guarded with a runtime SCEV overflow check. - SmallVector RedundantCasts; -}; BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA); Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -46,9 +46,10 @@ Loads.cpp LoopAccessAnalysis.cpp LoopAnalysisManager.cpp - LoopUnrollAnalyzer.cpp LoopInfo.cpp LoopPass.cpp + LoopUnrollAnalyzer.cpp + LoopUtils.cpp MemDepPrinter.cpp MemDerefPrinter.cpp MemoryBuiltins.cpp Index: lib/Analysis/LoopUtils.cpp =================================================================== --- lib/Analysis/LoopUtils.cpp +++ lib/Analysis/LoopUtils.cpp @@ -0,0 +1,1126 @@ +//===-- LoopUtils.cpp - Loop Utility functions -------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines common loop utility functions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/Utils/LoopUtils.h" +#include "llvm/Analysis/DemandedBits.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" +#include "llvm/Analysis/ScalarEvolutionExpander.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/KnownBits.h" + +using namespace llvm; +using namespace llvm::PatternMatch; + +#define DEBUG_TYPE "loop-utils" + +bool RecurrenceDescriptor::areAllUsesIn(Instruction *I, + SmallPtrSetImpl &Set) { + for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) + if (!Set.count(dyn_cast(*Use))) + return false; + return true; +} + +bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) { + switch (Kind) { + default: + break; + case RK_IntegerAdd: + case RK_IntegerMult: + case RK_IntegerOr: + case RK_IntegerAnd: + case RK_IntegerXor: + case RK_IntegerMinMax: + return true; + } + return false; +} + +bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) { + return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind); +} + +bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) { + switch (Kind) { + default: + break; + case RK_IntegerAdd: + case RK_IntegerMult: + case RK_FloatAdd: + case RK_FloatMult: + return true; + } + return false; +} + +/// 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 &Visited, + SmallPtrSetImpl &CI) { + if (!Phi->hasOneUse()) + return Phi; + + const APInt *M = nullptr; + Instruction *I, *J = cast(Phi->use_begin()->getUser()); + + // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT + // with a new integer type of the corresponding bit width. + if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) { + int32_t Bits = (*M + 1).exactLogBase2(); + if (Bits > 0) { + RT = IntegerType::get(Phi->getContext(), Bits); + Visited.insert(Phi); + CI.insert(J); + return J; + } + } + return Phi; +} + +/// Compute the minimal bit width needed to represent a reduction whose exit +/// instruction is given by Exit. +static std::pair computeRecurrenceType(Instruction *Exit, + DemandedBits *DB, + AssumptionCache *AC, + DominatorTree *DT) { + bool IsSigned = false; + const DataLayout &DL = Exit->getModule()->getDataLayout(); + uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType()); + + if (DB) { + // Use the demanded bits analysis to determine the bits that are live out + // of the exit instruction, rounding up to the nearest power of two. If the + // use of demanded bits results in a smaller bit width, we know the value + // must be positive (i.e., IsSigned = false), because if this were not the + // case, the sign bit would have been demanded. + auto Mask = DB->getDemandedBits(Exit); + MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros(); + } + + if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) { + // If demanded bits wasn't able to limit the bit width, we can try to use + // value tracking instead. This can be the case, for example, if the value + // may be negative. + auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT); + auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType()); + MaxBitWidth = NumTypeBits - NumSignBits; + KnownBits Bits = computeKnownBits(Exit, DL); + if (!Bits.isNonNegative()) { + // If the value is not known to be non-negative, we set IsSigned to true, + // meaning that we will use sext instructions instead of zext + // instructions to restore the original type. + IsSigned = true; + if (!Bits.isNegative()) + // If the value is not known to be negative, we don't known what the + // upper bit is, and therefore, we don't know what kind of extend we + // will need. In this case, just increase the bit width by one bit and + // use sext. + ++MaxBitWidth; + } + } + if (!isPowerOf2_64(MaxBitWidth)) + MaxBitWidth = NextPowerOf2(MaxBitWidth); + + return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth), + IsSigned); +} + +/// Collect cast instructions that can be ignored in the vectorizer's cost +/// model, given a reduction exit value and the minimal type in which the +/// reduction can be represented. +static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit, + Type *RecurrenceType, + SmallPtrSetImpl &Casts) { + + SmallVector Worklist; + SmallPtrSet Visited; + Worklist.push_back(Exit); + + while (!Worklist.empty()) { + Instruction *Val = Worklist.pop_back_val(); + Visited.insert(Val); + if (auto *Cast = dyn_cast(Val)) + if (Cast->getSrcTy() == RecurrenceType) { + // If the source type of a cast instruction is equal to the recurrence + // type, it will be eliminated, and should be ignored in the vectorizer + // cost model. + Casts.insert(Cast); + continue; + } + + // Add all operands to the work list if they are loop-varying values that + // we haven't yet visited. + for (Value *O : cast(Val)->operands()) + if (auto *I = dyn_cast(O)) + if (TheLoop->contains(I) && !Visited.count(I)) + Worklist.push_back(I); + } +} + +bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind, + Loop *TheLoop, bool HasFunNoNaNAttr, + RecurrenceDescriptor &RedDes, + DemandedBits *DB, + AssumptionCache *AC, + DominatorTree *DT) { + if (Phi->getNumIncomingValues() != 2) + return false; + + // Reduction variables are only found in the loop header block. + if (Phi->getParent() != TheLoop->getHeader()) + return false; + + // Obtain the reduction start value from the value that comes from the loop + // preheader. + Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()); + + // ExitInstruction is the single value which is used outside the loop. + // We only allow for a single reduction value to be used outside the loop. + // This includes users of the reduction, variables (which form a cycle + // which ends in the phi node). + Instruction *ExitInstruction = nullptr; + // Indicates that we found a reduction operation in our scan. + bool FoundReduxOp = false; + + // We start with the PHI node and scan for all of the users of this + // instruction. All users must be instructions that can be used as reduction + // variables (such as ADD). We must have a single out-of-block user. The cycle + // must include the original PHI. + bool FoundStartPHI = false; + + // To recognize min/max patterns formed by a icmp select sequence, we store + // the number of instruction we saw from the recognized min/max pattern, + // to make sure we only see exactly the two instructions. + unsigned NumCmpSelectPatternInst = 0; + InstDesc ReduxDesc(false, nullptr); + + // Data used for determining if the recurrence has been type-promoted. + Type *RecurrenceType = Phi->getType(); + SmallPtrSet CastInsts; + Instruction *Start = Phi; + bool IsSigned = false; + + SmallPtrSet VisitedInsts; + SmallVector Worklist; + + // Return early if the recurrence kind does not match the type of Phi. If the + // recurrence kind is arithmetic, we attempt to look through AND operations + // resulting from the type promotion performed by InstCombine. Vector + // operations are not limited to the legal integer widths, so we may be able + // to evaluate the reduction in the narrower width. + if (RecurrenceType->isFloatingPointTy()) { + if (!isFloatingPointRecurrenceKind(Kind)) + return false; + } else { + if (!isIntegerRecurrenceKind(Kind)) + return false; + if (isArithmeticRecurrenceKind(Kind)) + Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts); + } + + Worklist.push_back(Start); + VisitedInsts.insert(Start); + + // A value in the reduction can be used: + // - By the reduction: + // - Reduction operation: + // - One use of reduction value (safe). + // - Multiple use of reduction value (not safe). + // - PHI: + // - All uses of the PHI must be the reduction (safe). + // - Otherwise, not safe. + // - By instructions outside of the loop (safe). + // * One value may have several outside users, but all outside + // uses must be of the same value. + // - By an instruction that is not part of the reduction (not safe). + // This is either: + // * An instruction type other than PHI or the reduction operation. + // * A PHI in the header other than the initial PHI. + while (!Worklist.empty()) { + Instruction *Cur = Worklist.back(); + Worklist.pop_back(); + + // No Users. + // If the instruction has no users then this is a broken chain and can't be + // a reduction variable. + if (Cur->use_empty()) + return false; + + bool IsAPhi = isa(Cur); + + // A header PHI use other than the original PHI. + if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) + return false; + + // Reductions of instructions such as Div, and Sub is only possible if the + // LHS is the reduction variable. + if (!Cur->isCommutative() && !IsAPhi && !isa(Cur) && + !isa(Cur) && !isa(Cur) && + !VisitedInsts.count(dyn_cast(Cur->getOperand(0)))) + return false; + + // Any reduction instruction must be of one of the allowed kinds. We ignore + // the starting value (the Phi or an AND instruction if the Phi has been + // type-promoted). + if (Cur != Start) { + ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); + if (!ReduxDesc.isRecurrence()) + return false; + } + + // A reduction operation must only have one use of the reduction value. + if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax && + hasMultipleUsesOf(Cur, VisitedInsts)) + return false; + + // All inputs to a PHI node must be a reduction value. + if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) + return false; + + if (Kind == RK_IntegerMinMax && + (isa(Cur) || isa(Cur))) + ++NumCmpSelectPatternInst; + if (Kind == RK_FloatMinMax && (isa(Cur) || isa(Cur))) + ++NumCmpSelectPatternInst; + + // Check whether we found a reduction operator. + FoundReduxOp |= !IsAPhi && Cur != Start; + + // Process users of current instruction. Push non-PHI nodes after PHI nodes + // onto the stack. This way we are going to have seen all inputs to PHI + // nodes once we get to them. + SmallVector NonPHIs; + SmallVector PHIs; + for (User *U : Cur->users()) { + Instruction *UI = cast(U); + + // Check if we found the exit user. + BasicBlock *Parent = UI->getParent(); + if (!TheLoop->contains(Parent)) { + // If we already know this instruction is used externally, move on to + // the next user. + if (ExitInstruction == Cur) + continue; + + // Exit if you find multiple values used outside or if the header phi + // node is being used. In this case the user uses the value of the + // previous iteration, in which case we would loose "VF-1" iterations of + // the reduction operation if we vectorize. + if (ExitInstruction != nullptr || Cur == Phi) + return false; + + // The instruction used by an outside user must be the last instruction + // before we feed back to the reduction phi. Otherwise, we loose VF-1 + // operations on the value. + if (!is_contained(Phi->operands(), Cur)) + return false; + + ExitInstruction = Cur; + continue; + } + + // Process instructions only once (termination). Each reduction cycle + // value must only be used once, except by phi nodes and min/max + // reductions which are represented as a cmp followed by a select. + InstDesc IgnoredVal(false, nullptr); + if (VisitedInsts.insert(UI).second) { + if (isa(UI)) + PHIs.push_back(UI); + else + NonPHIs.push_back(UI); + } else if (!isa(UI) && + ((!isa(UI) && !isa(UI) && + !isa(UI)) || + !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())) + return false; + + // Remember that we completed the cycle. + if (UI == Phi) + FoundStartPHI = true; + } + Worklist.append(PHIs.begin(), PHIs.end()); + Worklist.append(NonPHIs.begin(), NonPHIs.end()); + } + + // This means we have seen one but not the other instruction of the + // pattern or more than just a select and cmp. + if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) && + NumCmpSelectPatternInst != 2) + return false; + + if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) + return false; + + if (Start != Phi) { + // If the starting value is not the same as the phi node, we speculatively + // looked through an 'and' instruction when evaluating a potential + // arithmetic reduction to determine if it may have been type-promoted. + // + // We now compute the minimal bit width that is required to represent the + // reduction. If this is the same width that was indicated by the 'and', we + // can represent the reduction in the smaller type. The 'and' instruction + // will be eliminated since it will essentially be a cast instruction that + // can be ignore in the cost model. If we compute a different type than we + // did when evaluating the 'and', the 'and' will not be eliminated, and we + // will end up with different kinds of operations in the recurrence + // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is + // the case. + // + // The vectorizer relies on InstCombine to perform the actual + // type-shrinking. It does this by inserting instructions to truncate the + // exit value of the reduction to the width indicated by RecurrenceType and + // then extend this value back to the original width. If IsSigned is false, + // a 'zext' instruction will be generated; otherwise, a 'sext' will be + // used. + // + // TODO: We should not rely on InstCombine to rewrite the reduction in the + // smaller type. We should just generate a correctly typed expression + // to begin with. + Type *ComputedType; + std::tie(ComputedType, IsSigned) = + computeRecurrenceType(ExitInstruction, DB, AC, DT); + if (ComputedType != RecurrenceType) + return false; + + // The recurrence expression will be represented in a narrower type. If + // there are any cast instructions that will be unnecessary, collect them + // in CastInsts. Note that the 'and' instruction was already included in + // this list. + // + // TODO: A better way to represent this may be to tag in some way all the + // instructions that are a part of the reduction. The vectorizer cost + // model could then apply the recurrence type to these instructions, + // without needing a white list of instructions to ignore. + collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts); + } + + // We found a reduction var if we have reached the original phi node and we + // only have a single instruction with out-of-loop users. + + // The ExitInstruction(Instruction which is allowed to have out-of-loop users) + // is saved as part of the RecurrenceDescriptor. + + // Save the description of this reduction variable. + RecurrenceDescriptor RD( + RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(), + ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts); + RedDes = RD; + + return true; +} + +/// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction +/// pattern corresponding to a min(X, Y) or max(X, Y). +RecurrenceDescriptor::InstDesc +RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) { + + assert((isa(I) || isa(I) || isa(I)) && + "Expect a select instruction"); + Instruction *Cmp = nullptr; + SelectInst *Select = nullptr; + + // We must handle the select(cmp()) as a single instruction. Advance to the + // select. + if ((Cmp = dyn_cast(I)) || (Cmp = dyn_cast(I))) { + if (!Cmp->hasOneUse() || !(Select = dyn_cast(*I->user_begin()))) + return InstDesc(false, I); + return InstDesc(Select, Prev.getMinMaxKind()); + } + + // Only handle single use cases for now. + if (!(Select = dyn_cast(I))) + return InstDesc(false, I); + if (!(Cmp = dyn_cast(I->getOperand(0))) && + !(Cmp = dyn_cast(I->getOperand(0)))) + return InstDesc(false, I); + if (!Cmp->hasOneUse()) + return InstDesc(false, I); + + Value *CmpLeft; + Value *CmpRight; + + // Look for a min/max pattern. + if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return InstDesc(Select, MRK_UIntMin); + else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return InstDesc(Select, MRK_UIntMax); + else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return InstDesc(Select, MRK_SIntMax); + else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return InstDesc(Select, MRK_SIntMin); + else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return InstDesc(Select, MRK_FloatMin); + else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return InstDesc(Select, MRK_FloatMax); + else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return InstDesc(Select, MRK_FloatMin); + else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return InstDesc(Select, MRK_FloatMax); + + return InstDesc(false, I); +} + +RecurrenceDescriptor::InstDesc +RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, + InstDesc &Prev, bool HasFunNoNaNAttr) { + bool FP = I->getType()->isFloatingPointTy(); + Instruction *UAI = Prev.getUnsafeAlgebraInst(); + if (!UAI && FP && !I->isFast()) + UAI = I; // Found an unsafe (unvectorizable) algebra instruction. + + switch (I->getOpcode()) { + default: + return InstDesc(false, I); + case Instruction::PHI: + return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst()); + case Instruction::Sub: + case Instruction::Add: + return InstDesc(Kind == RK_IntegerAdd, I); + case Instruction::Mul: + return InstDesc(Kind == RK_IntegerMult, I); + case Instruction::And: + return InstDesc(Kind == RK_IntegerAnd, I); + case Instruction::Or: + return InstDesc(Kind == RK_IntegerOr, I); + case Instruction::Xor: + return InstDesc(Kind == RK_IntegerXor, I); + case Instruction::FMul: + return InstDesc(Kind == RK_FloatMult, I, UAI); + case Instruction::FSub: + case Instruction::FAdd: + return InstDesc(Kind == RK_FloatAdd, I, UAI); + case Instruction::FCmp: + case Instruction::ICmp: + case Instruction::Select: + if (Kind != RK_IntegerMinMax && + (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) + return InstDesc(false, I); + return isMinMaxSelectCmpPattern(I, Prev); + } +} + +bool RecurrenceDescriptor::hasMultipleUsesOf( + Instruction *I, SmallPtrSetImpl &Insts) { + unsigned NumUses = 0; + for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; + ++Use) { + if (Insts.count(dyn_cast(*Use))) + ++NumUses; + if (NumUses > 1) + return true; + } + + return false; +} +bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, + RecurrenceDescriptor &RedDes, + DemandedBits *DB, AssumptionCache *AC, + DominatorTree *DT) { + + BasicBlock *Header = TheLoop->getHeader(); + Function &F = *Header->getParent(); + bool HasFunNoNaNAttr = + F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true"; + + if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB, + AC, DT)) { + DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB, + AC, DT)) { + DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB, + AC, DT)) { + DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB, + AC, DT)) { + DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB, + AC, DT)) { + DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes, + DB, AC, DT)) { + DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB, + AC, DT)) { + DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB, + AC, DT)) { + DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB, + AC, DT)) { + DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n"); + return true; + } + // Not a reduction of known type. + return false; +} + +bool RecurrenceDescriptor::isFirstOrderRecurrence( + PHINode *Phi, Loop *TheLoop, + DenseMap &SinkAfter, DominatorTree *DT) { + + // Ensure the phi node is in the loop header and has two incoming values. + if (Phi->getParent() != TheLoop->getHeader() || + Phi->getNumIncomingValues() != 2) + return false; + + // Ensure the loop has a preheader and a single latch block. The loop + // vectorizer will need the latch to set up the next iteration of the loop. + auto *Preheader = TheLoop->getLoopPreheader(); + auto *Latch = TheLoop->getLoopLatch(); + if (!Preheader || !Latch) + return false; + + // Ensure the phi node's incoming blocks are the loop preheader and latch. + if (Phi->getBasicBlockIndex(Preheader) < 0 || + Phi->getBasicBlockIndex(Latch) < 0) + return false; + + // Get the previous value. The previous value comes from the latch edge while + // the initial value comes form the preheader edge. + auto *Previous = dyn_cast(Phi->getIncomingValueForBlock(Latch)); + if (!Previous || !TheLoop->contains(Previous) || isa(Previous) || + SinkAfter.count(Previous)) // Cannot rely on dominance due to motion. + return false; + + // Ensure every user of the phi node is dominated by the previous value. + // The dominance requirement ensures the loop vectorizer will not need to + // vectorize the initial value prior to the first iteration of the loop. + // TODO: Consider extending this sinking to handle other kinds of instructions + // and expressions, beyond sinking a single cast past Previous. + if (Phi->hasOneUse()) { + auto *I = Phi->user_back(); + if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() && + DT->dominates(Previous, I->user_back())) { + if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking. + SinkAfter[I] = Previous; + return true; + } + } + + for (User *U : Phi->users()) + if (auto *I = dyn_cast(U)) { + if (!DT->dominates(Previous, I)) + return false; + } + + return true; +} + +/// This function returns the identity element (or neutral element) for +/// the operation K. +Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K, + Type *Tp) { + switch (K) { + case RK_IntegerXor: + case RK_IntegerAdd: + case RK_IntegerOr: + // Adding, Xoring, Oring zero to a number does not change it. + return ConstantInt::get(Tp, 0); + case RK_IntegerMult: + // Multiplying a number by 1 does not change it. + return ConstantInt::get(Tp, 1); + case RK_IntegerAnd: + // AND-ing a number with an all-1 value does not change it. + return ConstantInt::get(Tp, -1, true); + case RK_FloatMult: + // Multiplying a number by 1 does not change it. + return ConstantFP::get(Tp, 1.0L); + case RK_FloatAdd: + // Adding zero to a number does not change it. + return ConstantFP::get(Tp, 0.0L); + default: + llvm_unreachable("Unknown recurrence kind"); + } +} + +/// This function translates the recurrence kind to an LLVM binary operator. +unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) { + switch (Kind) { + case RK_IntegerAdd: + return Instruction::Add; + case RK_IntegerMult: + return Instruction::Mul; + case RK_IntegerOr: + return Instruction::Or; + case RK_IntegerAnd: + return Instruction::And; + case RK_IntegerXor: + return Instruction::Xor; + case RK_FloatMult: + return Instruction::FMul; + case RK_FloatAdd: + return Instruction::FAdd; + case RK_IntegerMinMax: + return Instruction::ICmp; + case RK_FloatMinMax: + return Instruction::FCmp; + default: + llvm_unreachable("Unknown recurrence operation"); + } +} + +Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder, + MinMaxRecurrenceKind RK, + Value *Left, Value *Right) { + CmpInst::Predicate P = CmpInst::ICMP_NE; + switch (RK) { + default: + llvm_unreachable("Unknown min/max recurrence kind"); + case MRK_UIntMin: + P = CmpInst::ICMP_ULT; + break; + case MRK_UIntMax: + P = CmpInst::ICMP_UGT; + break; + case MRK_SIntMin: + P = CmpInst::ICMP_SLT; + break; + case MRK_SIntMax: + P = CmpInst::ICMP_SGT; + break; + case MRK_FloatMin: + P = CmpInst::FCMP_OLT; + break; + case MRK_FloatMax: + P = CmpInst::FCMP_OGT; + break; + } + + // We only match FP sequences that are 'fast', so we can unconditionally + // set it on any generated instructions. + IRBuilder<>::FastMathFlagGuard FMFG(Builder); + FastMathFlags FMF; + FMF.setFast(); + Builder.setFastMathFlags(FMF); + + Value *Cmp; + if (RK == MRK_FloatMin || RK == MRK_FloatMax) + Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp"); + else + Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp"); + + Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select"); + return Select; +} + +InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K, + const SCEV *Step, BinaryOperator *BOp, + SmallVectorImpl *Casts) + : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) { + assert(IK != IK_NoInduction && "Not an induction"); + + // Start value type should match the induction kind and the value + // itself should not be null. + assert(StartValue && "StartValue is null"); + assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && + "StartValue is not a pointer for pointer induction"); + assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && + "StartValue is not an integer for integer induction"); + + // Check the Step Value. It should be non-zero integer value. + assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && + "Step value is zero"); + + assert((IK != IK_PtrInduction || getConstIntStepValue()) && + "Step value should be constant for pointer induction"); + assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) && + "StepValue is not an integer"); + + assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && + "StepValue is not FP for FpInduction"); + assert((IK != IK_FpInduction || (InductionBinOp && + (InductionBinOp->getOpcode() == Instruction::FAdd || + InductionBinOp->getOpcode() == Instruction::FSub))) && + "Binary opcode should be specified for FP induction"); + + if (Casts) { + for (auto &Inst : *Casts) { + RedundantCasts.push_back(Inst); + } + } +} + +int InductionDescriptor::getConsecutiveDirection() const { + ConstantInt *ConstStep = getConstIntStepValue(); + if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne())) + return ConstStep->getSExtValue(); + return 0; +} + +ConstantInt *InductionDescriptor::getConstIntStepValue() const { + if (isa(Step)) + return dyn_cast(cast(Step)->getValue()); + return nullptr; +} + +Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index, + ScalarEvolution *SE, + const DataLayout& DL) const { + + SCEVExpander Exp(*SE, DL, "induction"); + assert(Index->getType() == Step->getType() && + "Index type does not match StepValue type"); + switch (IK) { + case IK_IntInduction: { + assert(Index->getType() == StartValue->getType() && + "Index type does not match StartValue type"); + + // FIXME: Theoretically, we can call getAddExpr() of ScalarEvolution + // and calculate (Start + Index * Step) for all cases, without + // special handling for "isOne" and "isMinusOne". + // But in the real life the result code getting worse. We mix SCEV + // expressions and ADD/SUB operations and receive redundant + // intermediate values being calculated in different ways and + // Instcombine is unable to reduce them all. + + if (getConstIntStepValue() && + getConstIntStepValue()->isMinusOne()) + return B.CreateSub(StartValue, Index); + if (getConstIntStepValue() && + getConstIntStepValue()->isOne()) + return B.CreateAdd(StartValue, Index); + const SCEV *S = SE->getAddExpr(SE->getSCEV(StartValue), + SE->getMulExpr(Step, SE->getSCEV(Index))); + return Exp.expandCodeFor(S, StartValue->getType(), &*B.GetInsertPoint()); + } + case IK_PtrInduction: { + assert(isa(Step) && + "Expected constant step for pointer induction"); + const SCEV *S = SE->getMulExpr(SE->getSCEV(Index), Step); + Index = Exp.expandCodeFor(S, Index->getType(), &*B.GetInsertPoint()); + return B.CreateGEP(nullptr, StartValue, Index); + } + case IK_FpInduction: { + assert(Step->getType()->isFloatingPointTy() && "Expected FP Step value"); + assert(InductionBinOp && + (InductionBinOp->getOpcode() == Instruction::FAdd || + InductionBinOp->getOpcode() == Instruction::FSub) && + "Original bin op should be defined for FP induction"); + + Value *StepValue = cast(Step)->getValue(); + + // Floating point operations had to be 'fast' to enable the induction. + FastMathFlags Flags; + Flags.setFast(); + + Value *MulExp = B.CreateFMul(StepValue, Index); + if (isa(MulExp)) + // We have to check, the MulExp may be a constant. + cast(MulExp)->setFastMathFlags(Flags); + + Value *BOp = B.CreateBinOp(InductionBinOp->getOpcode() , StartValue, + MulExp, "induction"); + if (isa(BOp)) + cast(BOp)->setFastMathFlags(Flags); + + return BOp; + } + case IK_NoInduction: + return nullptr; + } + llvm_unreachable("invalid enum"); +} + +bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop, + ScalarEvolution *SE, + InductionDescriptor &D) { + + // Here we only handle FP induction variables. + assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type"); + + if (TheLoop->getHeader() != Phi->getParent()) + return false; + + // The loop may have multiple entrances or multiple exits; we can analyze + // this phi if it has a unique entry value and a unique backedge value. + if (Phi->getNumIncomingValues() != 2) + return false; + Value *BEValue = nullptr, *StartValue = nullptr; + if (TheLoop->contains(Phi->getIncomingBlock(0))) { + BEValue = Phi->getIncomingValue(0); + StartValue = Phi->getIncomingValue(1); + } else { + assert(TheLoop->contains(Phi->getIncomingBlock(1)) && + "Unexpected Phi node in the loop"); + BEValue = Phi->getIncomingValue(1); + StartValue = Phi->getIncomingValue(0); + } + + BinaryOperator *BOp = dyn_cast(BEValue); + if (!BOp) + return false; + + Value *Addend = nullptr; + if (BOp->getOpcode() == Instruction::FAdd) { + if (BOp->getOperand(0) == Phi) + Addend = BOp->getOperand(1); + else if (BOp->getOperand(1) == Phi) + Addend = BOp->getOperand(0); + } else if (BOp->getOpcode() == Instruction::FSub) + if (BOp->getOperand(0) == Phi) + Addend = BOp->getOperand(1); + + if (!Addend) + return false; + + // The addend should be loop invariant + if (auto *I = dyn_cast(Addend)) + if (TheLoop->contains(I)) + return false; + + // FP Step has unknown SCEV + const SCEV *Step = SE->getUnknown(Addend); + D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp); + return true; +} + +/// This function is called when we suspect that the update-chain of a phi node +/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts, +/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime +/// predicate P under which the SCEV expression for the phi can be the +/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the +/// cast instructions that are involved in the update-chain of this induction. +/// A caller that adds the required runtime predicate can be free to drop these +/// cast instructions, and compute the phi using \p AR (instead of some scev +/// expression with casts). +/// +/// For example, without a predicate the scev expression can take the following +/// form: +/// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy) +/// +/// It corresponds to the following IR sequence: +/// %for.body: +/// %x = phi i64 [ 0, %ph ], [ %add, %for.body ] +/// %casted_phi = "ExtTrunc i64 %x" +/// %add = add i64 %casted_phi, %step +/// +/// where %x is given in \p PN, +/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate, +/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of +/// several forms, for example, such as: +/// ExtTrunc1: %casted_phi = and %x, 2^n-1 +/// or: +/// ExtTrunc2: %t = shl %x, m +/// %casted_phi = ashr %t, m +/// +/// If we are able to find such sequence, we return the instructions +/// we found, namely %casted_phi and the instructions on its use-def chain up +/// to the phi (not including the phi). +static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, + const SCEVUnknown *PhiScev, + const SCEVAddRecExpr *AR, + SmallVectorImpl &CastInsts) { + + assert(CastInsts.empty() && "CastInsts is expected to be empty."); + auto *PN = cast(PhiScev->getValue()); + assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression"); + const Loop *L = AR->getLoop(); + + // Find any cast instructions that participate in the def-use chain of + // PhiScev in the loop. + // FORNOW/TODO: We currently expect the def-use chain to include only + // two-operand instructions, where one of the operands is an invariant. + // createAddRecFromPHIWithCasts() currently does not support anything more + // involved than that, so we keep the search simple. This can be + // extended/generalized as needed. + + auto getDef = [&](const Value *Val) -> Value * { + const BinaryOperator *BinOp = dyn_cast(Val); + if (!BinOp) + return nullptr; + Value *Op0 = BinOp->getOperand(0); + Value *Op1 = BinOp->getOperand(1); + Value *Def = nullptr; + if (L->isLoopInvariant(Op0)) + Def = Op1; + else if (L->isLoopInvariant(Op1)) + Def = Op0; + return Def; + }; + + // Look for the instruction that defines the induction via the + // loop backedge. + BasicBlock *Latch = L->getLoopLatch(); + if (!Latch) + return false; + Value *Val = PN->getIncomingValueForBlock(Latch); + if (!Val) + return false; + + // Follow the def-use chain until the induction phi is reached. + // If on the way we encounter a Value that has the same SCEV Expr as the + // phi node, we can consider the instructions we visit from that point + // as part of the cast-sequence that can be ignored. + bool InCastSequence = false; + auto *Inst = dyn_cast(Val); + while (Val != PN) { + // If we encountered a phi node other than PN, or if we left the loop, + // we bail out. + if (!Inst || !L->contains(Inst)) { + return false; + } + auto *AddRec = dyn_cast(PSE.getSCEV(Val)); + if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR)) + InCastSequence = true; + if (InCastSequence) { + // Only the last instruction in the cast sequence is expected to have + // uses outside the induction def-use chain. + if (!CastInsts.empty()) + if (!Inst->hasOneUse()) + return false; + CastInsts.push_back(Inst); + } + Val = getDef(Val); + if (!Val) + return false; + Inst = dyn_cast(Val); + } + + return InCastSequence; +} + +bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop, + PredicatedScalarEvolution &PSE, + InductionDescriptor &D, + bool Assume) { + Type *PhiTy = Phi->getType(); + + // Handle integer and pointer inductions variables. + // Now we handle also FP induction but not trying to make a + // recurrent expression from the PHI node in-place. + + if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && + !PhiTy->isFloatTy() && !PhiTy->isDoubleTy() && !PhiTy->isHalfTy()) + return false; + + if (PhiTy->isFloatingPointTy()) + return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D); + + const SCEV *PhiScev = PSE.getSCEV(Phi); + const auto *AR = dyn_cast(PhiScev); + + // We need this expression to be an AddRecExpr. + if (Assume && !AR) + AR = PSE.getAsAddRec(Phi); + + if (!AR) { + DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n"); + return false; + } + + // Record any Cast instructions that participate in the induction update + const auto *SymbolicPhi = dyn_cast(PhiScev); + // If we started from an UnknownSCEV, and managed to build an addRecurrence + // only after enabling Assume with PSCEV, this means we may have encountered + // cast instructions that required adding a runtime check in order to + // guarantee the correctness of the AddRecurence respresentation of the + // induction. + if (PhiScev != AR && SymbolicPhi) { + SmallVector Casts; + if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts)) + return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts); + } + + return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR); +} + +bool InductionDescriptor::isInductionPHI( + PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE, + InductionDescriptor &D, const SCEV *Expr, + SmallVectorImpl *CastsToIgnore) { + Type *PhiTy = Phi->getType(); + // We only handle integer and pointer inductions variables. + if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy()) + return false; + + // Check that the PHI is consecutive. + const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi); + const SCEVAddRecExpr *AR = dyn_cast(PhiScev); + + if (!AR) { + DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n"); + return false; + } + + if (AR->getLoop() != TheLoop) { + // FIXME: We should treat this as a uniform. Unfortunately, we + // don't currently know how to handled uniform PHIs. + DEBUG(dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n"); + return false; + } + + Value *StartValue = + Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader()); + const SCEV *Step = AR->getStepRecurrence(*SE); + // Calculate the pointer stride and check if it is consecutive. + // The stride may be a constant or a loop invariant integer value. + const SCEVConstant *ConstStep = dyn_cast(Step); + if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop)) + return false; + + if (PhiTy->isIntegerTy()) { + D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/ nullptr, + CastsToIgnore); + return true; + } + + assert(PhiTy->isPointerTy() && "The PHI must be a pointer"); + // Pointer induction should be a constant. + if (!ConstStep) + return false; + + ConstantInt *CV = ConstStep->getValue(); + Type *PointerElementType = PhiTy->getPointerElementType(); + // The pointer stride cannot be determined if the pointer element type is not + // sized. + if (!PointerElementType->isSized()) + return false; + + const DataLayout &DL = Phi->getModule()->getDataLayout(); + int64_t Size = static_cast(DL.getTypeAllocSize(PointerElementType)); + if (!Size) + return false; + + int64_t CVSize = CV->getSExtValue(); + if (CVSize % Size) + return false; + auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size, + true /* signed */); + D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue); + return true; +} Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -43,6 +43,7 @@ #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemorySSA.h" +#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" Index: lib/Transforms/Scalar/LoopIdiomRecognize.cpp =================================================================== --- lib/Transforms/Scalar/LoopIdiomRecognize.cpp +++ lib/Transforms/Scalar/LoopIdiomRecognize.cpp @@ -52,6 +52,7 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -37,6 +37,7 @@ #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/Utils/Local.h" Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -13,1131 +13,17 @@ #include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/ADT/ScopeExit.h" -#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" -#include "llvm/Analysis/InstructionSimplify.h" -#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" -#include "llvm/Analysis/MustExecute.h" -#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" -#include "llvm/Analysis/ScalarEvolutionExpander.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/Analysis/ValueTracking.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/PatternMatch.h" -#include "llvm/IR/ValueHandle.h" -#include "llvm/Pass.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/KnownBits.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" using namespace llvm; -using namespace llvm::PatternMatch; #define DEBUG_TYPE "loop-utils" -bool RecurrenceDescriptor::areAllUsesIn(Instruction *I, - SmallPtrSetImpl &Set) { - for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) - if (!Set.count(dyn_cast(*Use))) - return false; - return true; -} - -bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) { - switch (Kind) { - default: - break; - case RK_IntegerAdd: - case RK_IntegerMult: - case RK_IntegerOr: - case RK_IntegerAnd: - case RK_IntegerXor: - case RK_IntegerMinMax: - return true; - } - return false; -} - -bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) { - return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind); -} - -bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) { - switch (Kind) { - default: - break; - case RK_IntegerAdd: - case RK_IntegerMult: - case RK_FloatAdd: - case RK_FloatMult: - return true; - } - return false; -} - -/// 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 &Visited, - SmallPtrSetImpl &CI) { - if (!Phi->hasOneUse()) - return Phi; - - const APInt *M = nullptr; - Instruction *I, *J = cast(Phi->use_begin()->getUser()); - - // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT - // with a new integer type of the corresponding bit width. - if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) { - int32_t Bits = (*M + 1).exactLogBase2(); - if (Bits > 0) { - RT = IntegerType::get(Phi->getContext(), Bits); - Visited.insert(Phi); - CI.insert(J); - return J; - } - } - return Phi; -} - -/// Compute the minimal bit width needed to represent a reduction whose exit -/// instruction is given by Exit. -static std::pair computeRecurrenceType(Instruction *Exit, - DemandedBits *DB, - AssumptionCache *AC, - DominatorTree *DT) { - bool IsSigned = false; - const DataLayout &DL = Exit->getModule()->getDataLayout(); - uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType()); - - if (DB) { - // Use the demanded bits analysis to determine the bits that are live out - // of the exit instruction, rounding up to the nearest power of two. If the - // use of demanded bits results in a smaller bit width, we know the value - // must be positive (i.e., IsSigned = false), because if this were not the - // case, the sign bit would have been demanded. - auto Mask = DB->getDemandedBits(Exit); - MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros(); - } - - if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) { - // If demanded bits wasn't able to limit the bit width, we can try to use - // value tracking instead. This can be the case, for example, if the value - // may be negative. - auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT); - auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType()); - MaxBitWidth = NumTypeBits - NumSignBits; - KnownBits Bits = computeKnownBits(Exit, DL); - if (!Bits.isNonNegative()) { - // If the value is not known to be non-negative, we set IsSigned to true, - // meaning that we will use sext instructions instead of zext - // instructions to restore the original type. - IsSigned = true; - if (!Bits.isNegative()) - // If the value is not known to be negative, we don't known what the - // upper bit is, and therefore, we don't know what kind of extend we - // will need. In this case, just increase the bit width by one bit and - // use sext. - ++MaxBitWidth; - } - } - if (!isPowerOf2_64(MaxBitWidth)) - MaxBitWidth = NextPowerOf2(MaxBitWidth); - - return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth), - IsSigned); -} - -/// Collect cast instructions that can be ignored in the vectorizer's cost -/// model, given a reduction exit value and the minimal type in which the -/// reduction can be represented. -static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit, - Type *RecurrenceType, - SmallPtrSetImpl &Casts) { - - SmallVector Worklist; - SmallPtrSet Visited; - Worklist.push_back(Exit); - - while (!Worklist.empty()) { - Instruction *Val = Worklist.pop_back_val(); - Visited.insert(Val); - if (auto *Cast = dyn_cast(Val)) - if (Cast->getSrcTy() == RecurrenceType) { - // If the source type of a cast instruction is equal to the recurrence - // type, it will be eliminated, and should be ignored in the vectorizer - // cost model. - Casts.insert(Cast); - continue; - } - - // Add all operands to the work list if they are loop-varying values that - // we haven't yet visited. - for (Value *O : cast(Val)->operands()) - if (auto *I = dyn_cast(O)) - if (TheLoop->contains(I) && !Visited.count(I)) - Worklist.push_back(I); - } -} - -bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind, - Loop *TheLoop, bool HasFunNoNaNAttr, - RecurrenceDescriptor &RedDes, - DemandedBits *DB, - AssumptionCache *AC, - DominatorTree *DT) { - if (Phi->getNumIncomingValues() != 2) - return false; - - // Reduction variables are only found in the loop header block. - if (Phi->getParent() != TheLoop->getHeader()) - return false; - - // Obtain the reduction start value from the value that comes from the loop - // preheader. - Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()); - - // ExitInstruction is the single value which is used outside the loop. - // We only allow for a single reduction value to be used outside the loop. - // This includes users of the reduction, variables (which form a cycle - // which ends in the phi node). - Instruction *ExitInstruction = nullptr; - // Indicates that we found a reduction operation in our scan. - bool FoundReduxOp = false; - - // We start with the PHI node and scan for all of the users of this - // instruction. All users must be instructions that can be used as reduction - // variables (such as ADD). We must have a single out-of-block user. The cycle - // must include the original PHI. - bool FoundStartPHI = false; - - // To recognize min/max patterns formed by a icmp select sequence, we store - // the number of instruction we saw from the recognized min/max pattern, - // to make sure we only see exactly the two instructions. - unsigned NumCmpSelectPatternInst = 0; - InstDesc ReduxDesc(false, nullptr); - - // Data used for determining if the recurrence has been type-promoted. - Type *RecurrenceType = Phi->getType(); - SmallPtrSet CastInsts; - Instruction *Start = Phi; - bool IsSigned = false; - - SmallPtrSet VisitedInsts; - SmallVector Worklist; - - // Return early if the recurrence kind does not match the type of Phi. If the - // recurrence kind is arithmetic, we attempt to look through AND operations - // resulting from the type promotion performed by InstCombine. Vector - // operations are not limited to the legal integer widths, so we may be able - // to evaluate the reduction in the narrower width. - if (RecurrenceType->isFloatingPointTy()) { - if (!isFloatingPointRecurrenceKind(Kind)) - return false; - } else { - if (!isIntegerRecurrenceKind(Kind)) - return false; - if (isArithmeticRecurrenceKind(Kind)) - Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts); - } - - Worklist.push_back(Start); - VisitedInsts.insert(Start); - - // A value in the reduction can be used: - // - By the reduction: - // - Reduction operation: - // - One use of reduction value (safe). - // - Multiple use of reduction value (not safe). - // - PHI: - // - All uses of the PHI must be the reduction (safe). - // - Otherwise, not safe. - // - By instructions outside of the loop (safe). - // * One value may have several outside users, but all outside - // uses must be of the same value. - // - By an instruction that is not part of the reduction (not safe). - // This is either: - // * An instruction type other than PHI or the reduction operation. - // * A PHI in the header other than the initial PHI. - while (!Worklist.empty()) { - Instruction *Cur = Worklist.back(); - Worklist.pop_back(); - - // No Users. - // If the instruction has no users then this is a broken chain and can't be - // a reduction variable. - if (Cur->use_empty()) - return false; - - bool IsAPhi = isa(Cur); - - // A header PHI use other than the original PHI. - if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) - return false; - - // Reductions of instructions such as Div, and Sub is only possible if the - // LHS is the reduction variable. - if (!Cur->isCommutative() && !IsAPhi && !isa(Cur) && - !isa(Cur) && !isa(Cur) && - !VisitedInsts.count(dyn_cast(Cur->getOperand(0)))) - return false; - - // Any reduction instruction must be of one of the allowed kinds. We ignore - // the starting value (the Phi or an AND instruction if the Phi has been - // type-promoted). - if (Cur != Start) { - ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); - if (!ReduxDesc.isRecurrence()) - return false; - } - - // A reduction operation must only have one use of the reduction value. - if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax && - hasMultipleUsesOf(Cur, VisitedInsts)) - return false; - - // All inputs to a PHI node must be a reduction value. - if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) - return false; - - if (Kind == RK_IntegerMinMax && - (isa(Cur) || isa(Cur))) - ++NumCmpSelectPatternInst; - if (Kind == RK_FloatMinMax && (isa(Cur) || isa(Cur))) - ++NumCmpSelectPatternInst; - - // Check whether we found a reduction operator. - FoundReduxOp |= !IsAPhi && Cur != Start; - - // Process users of current instruction. Push non-PHI nodes after PHI nodes - // onto the stack. This way we are going to have seen all inputs to PHI - // nodes once we get to them. - SmallVector NonPHIs; - SmallVector PHIs; - for (User *U : Cur->users()) { - Instruction *UI = cast(U); - - // Check if we found the exit user. - BasicBlock *Parent = UI->getParent(); - if (!TheLoop->contains(Parent)) { - // If we already know this instruction is used externally, move on to - // the next user. - if (ExitInstruction == Cur) - continue; - - // Exit if you find multiple values used outside or if the header phi - // node is being used. In this case the user uses the value of the - // previous iteration, in which case we would loose "VF-1" iterations of - // the reduction operation if we vectorize. - if (ExitInstruction != nullptr || Cur == Phi) - return false; - - // The instruction used by an outside user must be the last instruction - // before we feed back to the reduction phi. Otherwise, we loose VF-1 - // operations on the value. - if (!is_contained(Phi->operands(), Cur)) - return false; - - ExitInstruction = Cur; - continue; - } - - // Process instructions only once (termination). Each reduction cycle - // value must only be used once, except by phi nodes and min/max - // reductions which are represented as a cmp followed by a select. - InstDesc IgnoredVal(false, nullptr); - if (VisitedInsts.insert(UI).second) { - if (isa(UI)) - PHIs.push_back(UI); - else - NonPHIs.push_back(UI); - } else if (!isa(UI) && - ((!isa(UI) && !isa(UI) && - !isa(UI)) || - !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())) - return false; - - // Remember that we completed the cycle. - if (UI == Phi) - FoundStartPHI = true; - } - Worklist.append(PHIs.begin(), PHIs.end()); - Worklist.append(NonPHIs.begin(), NonPHIs.end()); - } - - // This means we have seen one but not the other instruction of the - // pattern or more than just a select and cmp. - if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) && - NumCmpSelectPatternInst != 2) - return false; - - if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) - return false; - - if (Start != Phi) { - // If the starting value is not the same as the phi node, we speculatively - // looked through an 'and' instruction when evaluating a potential - // arithmetic reduction to determine if it may have been type-promoted. - // - // We now compute the minimal bit width that is required to represent the - // reduction. If this is the same width that was indicated by the 'and', we - // can represent the reduction in the smaller type. The 'and' instruction - // will be eliminated since it will essentially be a cast instruction that - // can be ignore in the cost model. If we compute a different type than we - // did when evaluating the 'and', the 'and' will not be eliminated, and we - // will end up with different kinds of operations in the recurrence - // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is - // the case. - // - // The vectorizer relies on InstCombine to perform the actual - // type-shrinking. It does this by inserting instructions to truncate the - // exit value of the reduction to the width indicated by RecurrenceType and - // then extend this value back to the original width. If IsSigned is false, - // a 'zext' instruction will be generated; otherwise, a 'sext' will be - // used. - // - // TODO: We should not rely on InstCombine to rewrite the reduction in the - // smaller type. We should just generate a correctly typed expression - // to begin with. - Type *ComputedType; - std::tie(ComputedType, IsSigned) = - computeRecurrenceType(ExitInstruction, DB, AC, DT); - if (ComputedType != RecurrenceType) - return false; - - // The recurrence expression will be represented in a narrower type. If - // there are any cast instructions that will be unnecessary, collect them - // in CastInsts. Note that the 'and' instruction was already included in - // this list. - // - // TODO: A better way to represent this may be to tag in some way all the - // instructions that are a part of the reduction. The vectorizer cost - // model could then apply the recurrence type to these instructions, - // without needing a white list of instructions to ignore. - collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts); - } - - // We found a reduction var if we have reached the original phi node and we - // only have a single instruction with out-of-loop users. - - // The ExitInstruction(Instruction which is allowed to have out-of-loop users) - // is saved as part of the RecurrenceDescriptor. - - // Save the description of this reduction variable. - RecurrenceDescriptor RD( - RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(), - ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts); - RedDes = RD; - - return true; -} - -/// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction -/// pattern corresponding to a min(X, Y) or max(X, Y). -RecurrenceDescriptor::InstDesc -RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) { - - assert((isa(I) || isa(I) || isa(I)) && - "Expect a select instruction"); - Instruction *Cmp = nullptr; - SelectInst *Select = nullptr; - - // We must handle the select(cmp()) as a single instruction. Advance to the - // select. - if ((Cmp = dyn_cast(I)) || (Cmp = dyn_cast(I))) { - if (!Cmp->hasOneUse() || !(Select = dyn_cast(*I->user_begin()))) - return InstDesc(false, I); - return InstDesc(Select, Prev.getMinMaxKind()); - } - - // Only handle single use cases for now. - if (!(Select = dyn_cast(I))) - return InstDesc(false, I); - if (!(Cmp = dyn_cast(I->getOperand(0))) && - !(Cmp = dyn_cast(I->getOperand(0)))) - return InstDesc(false, I); - if (!Cmp->hasOneUse()) - return InstDesc(false, I); - - Value *CmpLeft; - Value *CmpRight; - - // Look for a min/max pattern. - if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return InstDesc(Select, MRK_UIntMin); - else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return InstDesc(Select, MRK_UIntMax); - else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return InstDesc(Select, MRK_SIntMax); - else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return InstDesc(Select, MRK_SIntMin); - else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return InstDesc(Select, MRK_FloatMin); - else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return InstDesc(Select, MRK_FloatMax); - else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return InstDesc(Select, MRK_FloatMin); - else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return InstDesc(Select, MRK_FloatMax); - - return InstDesc(false, I); -} - -RecurrenceDescriptor::InstDesc -RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, - InstDesc &Prev, bool HasFunNoNaNAttr) { - bool FP = I->getType()->isFloatingPointTy(); - Instruction *UAI = Prev.getUnsafeAlgebraInst(); - if (!UAI && FP && !I->isFast()) - UAI = I; // Found an unsafe (unvectorizable) algebra instruction. - - switch (I->getOpcode()) { - default: - return InstDesc(false, I); - case Instruction::PHI: - return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst()); - case Instruction::Sub: - case Instruction::Add: - return InstDesc(Kind == RK_IntegerAdd, I); - case Instruction::Mul: - return InstDesc(Kind == RK_IntegerMult, I); - case Instruction::And: - return InstDesc(Kind == RK_IntegerAnd, I); - case Instruction::Or: - return InstDesc(Kind == RK_IntegerOr, I); - case Instruction::Xor: - return InstDesc(Kind == RK_IntegerXor, I); - case Instruction::FMul: - return InstDesc(Kind == RK_FloatMult, I, UAI); - case Instruction::FSub: - case Instruction::FAdd: - return InstDesc(Kind == RK_FloatAdd, I, UAI); - case Instruction::FCmp: - case Instruction::ICmp: - case Instruction::Select: - if (Kind != RK_IntegerMinMax && - (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) - return InstDesc(false, I); - return isMinMaxSelectCmpPattern(I, Prev); - } -} - -bool RecurrenceDescriptor::hasMultipleUsesOf( - Instruction *I, SmallPtrSetImpl &Insts) { - unsigned NumUses = 0; - for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; - ++Use) { - if (Insts.count(dyn_cast(*Use))) - ++NumUses; - if (NumUses > 1) - return true; - } - - return false; -} -bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, - RecurrenceDescriptor &RedDes, - DemandedBits *DB, AssumptionCache *AC, - DominatorTree *DT) { - - BasicBlock *Header = TheLoop->getHeader(); - Function &F = *Header->getParent(); - bool HasFunNoNaNAttr = - F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true"; - - if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB, - AC, DT)) { - DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n"); - return true; - } - if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB, - AC, DT)) { - DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n"); - return true; - } - if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB, - AC, DT)) { - DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n"); - return true; - } - if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB, - AC, DT)) { - DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n"); - return true; - } - if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB, - AC, DT)) { - DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n"); - return true; - } - if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes, - DB, AC, DT)) { - DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n"); - return true; - } - if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB, - AC, DT)) { - DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n"); - return true; - } - if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB, - AC, DT)) { - DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n"); - return true; - } - if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB, - AC, DT)) { - DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n"); - return true; - } - // Not a reduction of known type. - return false; -} - -bool RecurrenceDescriptor::isFirstOrderRecurrence( - PHINode *Phi, Loop *TheLoop, - DenseMap &SinkAfter, DominatorTree *DT) { - - // Ensure the phi node is in the loop header and has two incoming values. - if (Phi->getParent() != TheLoop->getHeader() || - Phi->getNumIncomingValues() != 2) - return false; - - // Ensure the loop has a preheader and a single latch block. The loop - // vectorizer will need the latch to set up the next iteration of the loop. - auto *Preheader = TheLoop->getLoopPreheader(); - auto *Latch = TheLoop->getLoopLatch(); - if (!Preheader || !Latch) - return false; - - // Ensure the phi node's incoming blocks are the loop preheader and latch. - if (Phi->getBasicBlockIndex(Preheader) < 0 || - Phi->getBasicBlockIndex(Latch) < 0) - return false; - - // Get the previous value. The previous value comes from the latch edge while - // the initial value comes form the preheader edge. - auto *Previous = dyn_cast(Phi->getIncomingValueForBlock(Latch)); - if (!Previous || !TheLoop->contains(Previous) || isa(Previous) || - SinkAfter.count(Previous)) // Cannot rely on dominance due to motion. - return false; - - // Ensure every user of the phi node is dominated by the previous value. - // The dominance requirement ensures the loop vectorizer will not need to - // vectorize the initial value prior to the first iteration of the loop. - // TODO: Consider extending this sinking to handle other kinds of instructions - // and expressions, beyond sinking a single cast past Previous. - if (Phi->hasOneUse()) { - auto *I = Phi->user_back(); - if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() && - DT->dominates(Previous, I->user_back())) { - if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking. - SinkAfter[I] = Previous; - return true; - } - } - - for (User *U : Phi->users()) - if (auto *I = dyn_cast(U)) { - if (!DT->dominates(Previous, I)) - return false; - } - - return true; -} - -/// This function returns the identity element (or neutral element) for -/// the operation K. -Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K, - Type *Tp) { - switch (K) { - case RK_IntegerXor: - case RK_IntegerAdd: - case RK_IntegerOr: - // Adding, Xoring, Oring zero to a number does not change it. - return ConstantInt::get(Tp, 0); - case RK_IntegerMult: - // Multiplying a number by 1 does not change it. - return ConstantInt::get(Tp, 1); - case RK_IntegerAnd: - // AND-ing a number with an all-1 value does not change it. - return ConstantInt::get(Tp, -1, true); - case RK_FloatMult: - // Multiplying a number by 1 does not change it. - return ConstantFP::get(Tp, 1.0L); - case RK_FloatAdd: - // Adding zero to a number does not change it. - return ConstantFP::get(Tp, 0.0L); - default: - llvm_unreachable("Unknown recurrence kind"); - } -} - -/// This function translates the recurrence kind to an LLVM binary operator. -unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) { - switch (Kind) { - case RK_IntegerAdd: - return Instruction::Add; - case RK_IntegerMult: - return Instruction::Mul; - case RK_IntegerOr: - return Instruction::Or; - case RK_IntegerAnd: - return Instruction::And; - case RK_IntegerXor: - return Instruction::Xor; - case RK_FloatMult: - return Instruction::FMul; - case RK_FloatAdd: - return Instruction::FAdd; - case RK_IntegerMinMax: - return Instruction::ICmp; - case RK_FloatMinMax: - return Instruction::FCmp; - default: - llvm_unreachable("Unknown recurrence operation"); - } -} - -Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder, - MinMaxRecurrenceKind RK, - Value *Left, Value *Right) { - CmpInst::Predicate P = CmpInst::ICMP_NE; - switch (RK) { - default: - llvm_unreachable("Unknown min/max recurrence kind"); - case MRK_UIntMin: - P = CmpInst::ICMP_ULT; - break; - case MRK_UIntMax: - P = CmpInst::ICMP_UGT; - break; - case MRK_SIntMin: - P = CmpInst::ICMP_SLT; - break; - case MRK_SIntMax: - P = CmpInst::ICMP_SGT; - break; - case MRK_FloatMin: - P = CmpInst::FCMP_OLT; - break; - case MRK_FloatMax: - P = CmpInst::FCMP_OGT; - break; - } - - // We only match FP sequences that are 'fast', so we can unconditionally - // set it on any generated instructions. - IRBuilder<>::FastMathFlagGuard FMFG(Builder); - FastMathFlags FMF; - FMF.setFast(); - Builder.setFastMathFlags(FMF); - - Value *Cmp; - if (RK == MRK_FloatMin || RK == MRK_FloatMax) - Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp"); - else - Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp"); - - Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select"); - return Select; -} - -InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K, - const SCEV *Step, BinaryOperator *BOp, - SmallVectorImpl *Casts) - : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) { - assert(IK != IK_NoInduction && "Not an induction"); - - // Start value type should match the induction kind and the value - // itself should not be null. - assert(StartValue && "StartValue is null"); - assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && - "StartValue is not a pointer for pointer induction"); - assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && - "StartValue is not an integer for integer induction"); - - // Check the Step Value. It should be non-zero integer value. - assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && - "Step value is zero"); - - assert((IK != IK_PtrInduction || getConstIntStepValue()) && - "Step value should be constant for pointer induction"); - assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) && - "StepValue is not an integer"); - - assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && - "StepValue is not FP for FpInduction"); - assert((IK != IK_FpInduction || (InductionBinOp && - (InductionBinOp->getOpcode() == Instruction::FAdd || - InductionBinOp->getOpcode() == Instruction::FSub))) && - "Binary opcode should be specified for FP induction"); - - if (Casts) { - for (auto &Inst : *Casts) { - RedundantCasts.push_back(Inst); - } - } -} - -int InductionDescriptor::getConsecutiveDirection() const { - ConstantInt *ConstStep = getConstIntStepValue(); - if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne())) - return ConstStep->getSExtValue(); - return 0; -} - -ConstantInt *InductionDescriptor::getConstIntStepValue() const { - if (isa(Step)) - return dyn_cast(cast(Step)->getValue()); - return nullptr; -} - -Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index, - ScalarEvolution *SE, - const DataLayout& DL) const { - - SCEVExpander Exp(*SE, DL, "induction"); - assert(Index->getType() == Step->getType() && - "Index type does not match StepValue type"); - switch (IK) { - case IK_IntInduction: { - assert(Index->getType() == StartValue->getType() && - "Index type does not match StartValue type"); - - // FIXME: Theoretically, we can call getAddExpr() of ScalarEvolution - // and calculate (Start + Index * Step) for all cases, without - // special handling for "isOne" and "isMinusOne". - // But in the real life the result code getting worse. We mix SCEV - // expressions and ADD/SUB operations and receive redundant - // intermediate values being calculated in different ways and - // Instcombine is unable to reduce them all. - - if (getConstIntStepValue() && - getConstIntStepValue()->isMinusOne()) - return B.CreateSub(StartValue, Index); - if (getConstIntStepValue() && - getConstIntStepValue()->isOne()) - return B.CreateAdd(StartValue, Index); - const SCEV *S = SE->getAddExpr(SE->getSCEV(StartValue), - SE->getMulExpr(Step, SE->getSCEV(Index))); - return Exp.expandCodeFor(S, StartValue->getType(), &*B.GetInsertPoint()); - } - case IK_PtrInduction: { - assert(isa(Step) && - "Expected constant step for pointer induction"); - const SCEV *S = SE->getMulExpr(SE->getSCEV(Index), Step); - Index = Exp.expandCodeFor(S, Index->getType(), &*B.GetInsertPoint()); - return B.CreateGEP(nullptr, StartValue, Index); - } - case IK_FpInduction: { - assert(Step->getType()->isFloatingPointTy() && "Expected FP Step value"); - assert(InductionBinOp && - (InductionBinOp->getOpcode() == Instruction::FAdd || - InductionBinOp->getOpcode() == Instruction::FSub) && - "Original bin op should be defined for FP induction"); - - Value *StepValue = cast(Step)->getValue(); - - // Floating point operations had to be 'fast' to enable the induction. - FastMathFlags Flags; - Flags.setFast(); - - Value *MulExp = B.CreateFMul(StepValue, Index); - if (isa(MulExp)) - // We have to check, the MulExp may be a constant. - cast(MulExp)->setFastMathFlags(Flags); - - Value *BOp = B.CreateBinOp(InductionBinOp->getOpcode() , StartValue, - MulExp, "induction"); - if (isa(BOp)) - cast(BOp)->setFastMathFlags(Flags); - - return BOp; - } - case IK_NoInduction: - return nullptr; - } - llvm_unreachable("invalid enum"); -} - -bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop, - ScalarEvolution *SE, - InductionDescriptor &D) { - - // Here we only handle FP induction variables. - assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type"); - - if (TheLoop->getHeader() != Phi->getParent()) - return false; - - // The loop may have multiple entrances or multiple exits; we can analyze - // this phi if it has a unique entry value and a unique backedge value. - if (Phi->getNumIncomingValues() != 2) - return false; - Value *BEValue = nullptr, *StartValue = nullptr; - if (TheLoop->contains(Phi->getIncomingBlock(0))) { - BEValue = Phi->getIncomingValue(0); - StartValue = Phi->getIncomingValue(1); - } else { - assert(TheLoop->contains(Phi->getIncomingBlock(1)) && - "Unexpected Phi node in the loop"); - BEValue = Phi->getIncomingValue(1); - StartValue = Phi->getIncomingValue(0); - } - - BinaryOperator *BOp = dyn_cast(BEValue); - if (!BOp) - return false; - - Value *Addend = nullptr; - if (BOp->getOpcode() == Instruction::FAdd) { - if (BOp->getOperand(0) == Phi) - Addend = BOp->getOperand(1); - else if (BOp->getOperand(1) == Phi) - Addend = BOp->getOperand(0); - } else if (BOp->getOpcode() == Instruction::FSub) - if (BOp->getOperand(0) == Phi) - Addend = BOp->getOperand(1); - - if (!Addend) - return false; - - // The addend should be loop invariant - if (auto *I = dyn_cast(Addend)) - if (TheLoop->contains(I)) - return false; - - // FP Step has unknown SCEV - const SCEV *Step = SE->getUnknown(Addend); - D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp); - return true; -} - -/// This function is called when we suspect that the update-chain of a phi node -/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts, -/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime -/// predicate P under which the SCEV expression for the phi can be the -/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the -/// cast instructions that are involved in the update-chain of this induction. -/// A caller that adds the required runtime predicate can be free to drop these -/// cast instructions, and compute the phi using \p AR (instead of some scev -/// expression with casts). -/// -/// For example, without a predicate the scev expression can take the following -/// form: -/// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy) -/// -/// It corresponds to the following IR sequence: -/// %for.body: -/// %x = phi i64 [ 0, %ph ], [ %add, %for.body ] -/// %casted_phi = "ExtTrunc i64 %x" -/// %add = add i64 %casted_phi, %step -/// -/// where %x is given in \p PN, -/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate, -/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of -/// several forms, for example, such as: -/// ExtTrunc1: %casted_phi = and %x, 2^n-1 -/// or: -/// ExtTrunc2: %t = shl %x, m -/// %casted_phi = ashr %t, m -/// -/// If we are able to find such sequence, we return the instructions -/// we found, namely %casted_phi and the instructions on its use-def chain up -/// to the phi (not including the phi). -static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, - const SCEVUnknown *PhiScev, - const SCEVAddRecExpr *AR, - SmallVectorImpl &CastInsts) { - - assert(CastInsts.empty() && "CastInsts is expected to be empty."); - auto *PN = cast(PhiScev->getValue()); - assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression"); - const Loop *L = AR->getLoop(); - - // Find any cast instructions that participate in the def-use chain of - // PhiScev in the loop. - // FORNOW/TODO: We currently expect the def-use chain to include only - // two-operand instructions, where one of the operands is an invariant. - // createAddRecFromPHIWithCasts() currently does not support anything more - // involved than that, so we keep the search simple. This can be - // extended/generalized as needed. - - auto getDef = [&](const Value *Val) -> Value * { - const BinaryOperator *BinOp = dyn_cast(Val); - if (!BinOp) - return nullptr; - Value *Op0 = BinOp->getOperand(0); - Value *Op1 = BinOp->getOperand(1); - Value *Def = nullptr; - if (L->isLoopInvariant(Op0)) - Def = Op1; - else if (L->isLoopInvariant(Op1)) - Def = Op0; - return Def; - }; - - // Look for the instruction that defines the induction via the - // loop backedge. - BasicBlock *Latch = L->getLoopLatch(); - if (!Latch) - return false; - Value *Val = PN->getIncomingValueForBlock(Latch); - if (!Val) - return false; - - // Follow the def-use chain until the induction phi is reached. - // If on the way we encounter a Value that has the same SCEV Expr as the - // phi node, we can consider the instructions we visit from that point - // as part of the cast-sequence that can be ignored. - bool InCastSequence = false; - auto *Inst = dyn_cast(Val); - while (Val != PN) { - // If we encountered a phi node other than PN, or if we left the loop, - // we bail out. - if (!Inst || !L->contains(Inst)) { - return false; - } - auto *AddRec = dyn_cast(PSE.getSCEV(Val)); - if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR)) - InCastSequence = true; - if (InCastSequence) { - // Only the last instruction in the cast sequence is expected to have - // uses outside the induction def-use chain. - if (!CastInsts.empty()) - if (!Inst->hasOneUse()) - return false; - CastInsts.push_back(Inst); - } - Val = getDef(Val); - if (!Val) - return false; - Inst = dyn_cast(Val); - } - - return InCastSequence; -} - -bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop, - PredicatedScalarEvolution &PSE, - InductionDescriptor &D, - bool Assume) { - Type *PhiTy = Phi->getType(); - - // Handle integer and pointer inductions variables. - // Now we handle also FP induction but not trying to make a - // recurrent expression from the PHI node in-place. - - if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && - !PhiTy->isFloatTy() && !PhiTy->isDoubleTy() && !PhiTy->isHalfTy()) - return false; - - if (PhiTy->isFloatingPointTy()) - return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D); - - const SCEV *PhiScev = PSE.getSCEV(Phi); - const auto *AR = dyn_cast(PhiScev); - - // We need this expression to be an AddRecExpr. - if (Assume && !AR) - AR = PSE.getAsAddRec(Phi); - - if (!AR) { - DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n"); - return false; - } - - // Record any Cast instructions that participate in the induction update - const auto *SymbolicPhi = dyn_cast(PhiScev); - // If we started from an UnknownSCEV, and managed to build an addRecurrence - // only after enabling Assume with PSCEV, this means we may have encountered - // cast instructions that required adding a runtime check in order to - // guarantee the correctness of the AddRecurence respresentation of the - // induction. - if (PhiScev != AR && SymbolicPhi) { - SmallVector Casts; - if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts)) - return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts); - } - - return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR); -} - -bool InductionDescriptor::isInductionPHI( - PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE, - InductionDescriptor &D, const SCEV *Expr, - SmallVectorImpl *CastsToIgnore) { - Type *PhiTy = Phi->getType(); - // We only handle integer and pointer inductions variables. - if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy()) - return false; - - // Check that the PHI is consecutive. - const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi); - const SCEVAddRecExpr *AR = dyn_cast(PhiScev); - - if (!AR) { - DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n"); - return false; - } - - if (AR->getLoop() != TheLoop) { - // FIXME: We should treat this as a uniform. Unfortunately, we - // don't currently know how to handled uniform PHIs. - DEBUG(dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n"); - return false; - } - - Value *StartValue = - Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader()); - const SCEV *Step = AR->getStepRecurrence(*SE); - // Calculate the pointer stride and check if it is consecutive. - // The stride may be a constant or a loop invariant integer value. - const SCEVConstant *ConstStep = dyn_cast(Step); - if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop)) - return false; - - if (PhiTy->isIntegerTy()) { - D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/ nullptr, - CastsToIgnore); - return true; - } - - assert(PhiTy->isPointerTy() && "The PHI must be a pointer"); - // Pointer induction should be a constant. - if (!ConstStep) - return false; - - ConstantInt *CV = ConstStep->getValue(); - Type *PointerElementType = PhiTy->getPointerElementType(); - // The pointer stride cannot be determined if the pointer element type is not - // sized. - if (!PointerElementType->isSized()) - return false; - - const DataLayout &DL = Phi->getModule()->getDataLayout(); - int64_t Size = static_cast(DL.getTypeAllocSize(PointerElementType)); - if (!Size) - return false; - - int64_t CVSize = CV->getSExtValue(); - if (CVSize % Size) - return false; - auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size, - true /* signed */); - D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue); - return true; -} - bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA) { bool Changed = false; Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -82,6 +82,7 @@ #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/Utils/LoopUtils.h" #include "llvm/Analysis/VectorUtils.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" @@ -121,7 +122,6 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/LoopSimplify.h" -#include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/LoopVersioning.h" #include #include