X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpander.h;h=8ec2078258d111be7a78ee6bbfe48f13cbd7fd24;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=3e57ba877ee1f3c887e09042a69212eb38c9a764;hpb=eb3d76da81e2148ed7c577594c873ba147f4f435;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 3e57ba877ee..8ec2078258d 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -16,9 +16,9 @@ #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ScalarEvolutionNormalization.h" +#include "llvm/Analysis/TargetFolder.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/ValueHandle.h" -#include "llvm/Support/TargetFolder.h" #include namespace llvm { @@ -28,7 +28,7 @@ namespace llvm { /// all materialized values are safe to speculate. bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE); - /// SCEVExpander - This class uses information about analyze scalars to + /// This class uses information about analyze scalars to /// rewrite expressions in canonical form. /// /// Clients should create an instance of this class when rewriting is needed, @@ -36,6 +36,7 @@ namespace llvm { /// memory. class SCEVExpander : public SCEVVisitor { ScalarEvolution &SE; + const DataLayout &DL; // New instructions receive a name to identifies them with the current pass. const char* IVName; @@ -47,37 +48,36 @@ namespace llvm { std::set > InsertedValues; std::set > InsertedPostIncValues; - /// RelevantLoops - A memoization of the "relevant" loop for a given SCEV. + /// A memoization of the "relevant" loop for a given SCEV. DenseMap RelevantLoops; - /// PostIncLoops - Addrecs referring to any of the given loops are expanded + /// \brief Addrecs referring to any of the given loops are expanded /// in post-inc mode. For example, expanding {1,+,1} in post-inc mode /// returns the add instruction that adds one to the phi for {0,+,1}, /// as opposed to a new phi starting at 1. This is only supported in /// non-canonical mode. PostIncLoopSet PostIncLoops; - /// IVIncInsertPos - When this is non-null, addrecs expanded in the - /// loop it indicates should be inserted with increments at - /// IVIncInsertPos. + /// \brief When this is non-null, addrecs expanded in the loop it indicates + /// should be inserted with increments at IVIncInsertPos. const Loop *IVIncInsertLoop; - /// IVIncInsertPos - When expanding addrecs in the IVIncInsertLoop loop, - /// insert the IV increment at this position. + /// \brief When expanding addrecs in the IVIncInsertLoop loop, insert the IV + /// increment at this position. Instruction *IVIncInsertPos; - /// Phis that complete an IV chain. Reuse + /// \brief Phis that complete an IV chain. Reuse std::set > ChainedPhis; - /// CanonicalMode - When true, expressions are expanded in "canonical" - /// form. In particular, addrecs are expanded as arithmetic based on - /// a canonical induction variable. When false, expression are expanded - /// in a more literal form. + /// \brief When true, expressions are expanded in "canonical" form. In + /// particular, addrecs are expanded as arithmetic based on a canonical + /// induction variable. When false, expression are expanded in a more + /// literal form. bool CanonicalMode; - /// When invoked from LSR, the expander is in "strength reduction" mode. The - /// only difference is that phi's are only reused if they are already in - /// "expanded" form. + /// \brief When invoked from LSR, the expander is in "strength reduction" + /// mode. The only difference is that phi's are only reused if they are + /// already in "expanded" form. bool LSRMode; typedef IRBuilder BuilderType; @@ -90,11 +90,12 @@ namespace llvm { friend struct SCEVVisitor; public: - /// SCEVExpander - Construct a SCEVExpander in "canonical" mode. - explicit SCEVExpander(ScalarEvolution &se, const char *name) - : SE(se), IVName(name), IVIncInsertLoop(0), IVIncInsertPos(0), - CanonicalMode(true), LSRMode(false), - Builder(se.getContext(), TargetFolder(se.DL)) { + /// \brief Construct a SCEVExpander in "canonical" mode. + explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL, + const char *name) + : SE(se), DL(DL), IVName(name), IVIncInsertLoop(nullptr), + IVIncInsertPos(nullptr), CanonicalMode(true), LSRMode(false), + Builder(se.getContext(), TargetFolder(DL)) { #ifndef NDEBUG DebugType = ""; #endif @@ -104,7 +105,7 @@ namespace llvm { void setDebugType(const char* s) { DebugType = s; } #endif - /// clear - Erase the contents of the InsertedExpressions map so that users + /// \brief Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or /// different places within the same BasicBlock can do so. void clear() { @@ -114,31 +115,38 @@ namespace llvm { ChainedPhis.clear(); } - /// getOrInsertCanonicalInductionVariable - This method returns the - /// canonical induction variable of the specified type for the specified - /// loop (inserting one if there is none). A canonical induction variable - /// starts at zero and steps by one on each iteration. + /// \brief Return true for expressions that may incur non-trivial cost to + /// evaluate at runtime. + bool isHighCostExpansion(const SCEV *Expr, Loop *L) { + SmallPtrSet Processed; + return isHighCostExpansionHelper(Expr, L, Processed); + } + + /// \brief This method returns the canonical induction variable of the + /// specified type for the specified loop (inserting one if there is none). + /// A canonical induction variable starts at zero and steps by one on each + /// iteration. PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty); - /// getIVIncOperand - Return the induction variable increment's IV operand. + /// \brief Return the induction variable increment's IV operand. Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale); - /// hoistIVInc - Utility for hoisting an IV increment. + /// \brief Utility for hoisting an IV increment. bool hoistIVInc(Instruction *IncV, Instruction *InsertPos); - /// replaceCongruentIVs - replace congruent phis with their most canonical + /// \brief replace congruent phis with their most canonical /// representative. Return the number of phis eliminated. unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl &DeadInsts, - const TargetTransformInfo *TTI = NULL); + const TargetTransformInfo *TTI = nullptr); - /// expandCodeFor - Insert code to directly compute the specified SCEV - /// expression into the program. The inserted code is inserted into the - /// specified block. + /// \brief Insert code to directly compute the specified SCEV expression + /// into the program. The inserted code is inserted into the specified + /// block. Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I); - /// setIVIncInsertPos - Set the current IV increment loop and position. + /// \brief Set the current IV increment loop and position. void setIVIncInsertPos(const Loop *L, Instruction *Pos) { assert(!CanonicalMode && "IV increment positions are not supported in CanonicalMode"); @@ -146,16 +154,15 @@ namespace llvm { IVIncInsertPos = Pos; } - /// setPostInc - Enable post-inc expansion for addrecs referring to the - /// given loops. Post-inc expansion is only supported in non-canonical - /// mode. + /// \brief Enable post-inc expansion for addrecs referring to the given + /// loops. Post-inc expansion is only supported in non-canonical mode. void setPostInc(const PostIncLoopSet &L) { assert(!CanonicalMode && "Post-inc expansion is not supported in CanonicalMode"); PostIncLoops = L; } - /// clearPostInc - Disable all post-inc expansion. + /// \brief Disable all post-inc expansion. void clearPostInc() { PostIncLoops.clear(); @@ -164,23 +171,22 @@ namespace llvm { InsertedPostIncValues.clear(); } - /// disableCanonicalMode - Disable the behavior of expanding expressions in - /// canonical form rather than in a more literal form. Non-canonical mode - /// is useful for late optimization passes. + /// \brief Disable the behavior of expanding expressions in canonical form + /// rather than in a more literal form. Non-canonical mode is useful for + /// late optimization passes. void disableCanonicalMode() { CanonicalMode = false; } void enableLSRMode() { LSRMode = true; } - /// clearInsertPoint - Clear the current insertion point. This is useful - /// if the instruction that had been serving as the insertion point may - /// have been deleted. + /// \brief Clear the current insertion point. This is useful if the + /// instruction that had been serving as the insertion point may have been + /// deleted. void clearInsertPoint() { Builder.ClearInsertionPoint(); } - /// isInsertedInstruction - Return true if the specified instruction was - /// inserted by the code rewriter. If so, the client should not modify the - /// instruction. + /// \brief Return true if the specified instruction was inserted by the code + /// rewriter. If so, the client should not modify the instruction. bool isInsertedInstruction(Instruction *I) const { return InsertedValues.count(I) || InsertedPostIncValues.count(I); } @@ -190,24 +196,27 @@ namespace llvm { private: LLVMContext &getContext() const { return SE.getContext(); } - /// InsertBinop - Insert the specified binary operator, doing a small amount + /// \brief Recursive helper function for isHighCostExpansion. + bool isHighCostExpansionHelper(const SCEV *S, Loop *L, + SmallPtrSetImpl &Processed); + + /// \brief Insert the specified binary operator, doing a small amount /// of work to avoid inserting an obviously redundant operation. Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS); - /// ReuseOrCreateCast - Arange for there to be a cast of V to Ty at IP, - /// reusing an existing cast if a suitable one exists, moving an existing - /// cast if a suitable one exists but isn't in the right place, or - /// or creating a new one. + /// \brief Arrange for there to be a cast of V to Ty at IP, reusing an + /// existing cast if a suitable one exists, moving an existing cast if a + /// suitable one exists but isn't in the right place, or or creating a new + /// one. Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op, BasicBlock::iterator IP); - /// InsertNoopCastOfTo - Insert a cast of V to the specified type, - /// which must be possible with a noop cast, doing what we can to - /// share the casts. + /// \brief Insert a cast of V to the specified type, which must be possible + /// with a noop cast, doing what we can to share the casts. Value *InsertNoopCastOfTo(Value *V, Type *Ty); - /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP + /// \brief Expand a SCEVAddExpr with a pointer type into a GEP /// instead of using ptrtoint+arithmetic+inttoptr. Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end, @@ -215,13 +224,13 @@ namespace llvm { Value *expand(const SCEV *S); - /// expandCodeFor - Insert code to directly compute the specified SCEV - /// expression into the program. The inserted code is inserted into the - /// SCEVExpander's current insertion point. If a type is specified, the - /// result will be expanded to have that type, with a cast if necessary. - Value *expandCodeFor(const SCEV *SH, Type *Ty = 0); + /// \brief Insert code to directly compute the specified SCEV expression + /// into the program. The inserted code is inserted into the SCEVExpander's + /// current insertion point. If a type is specified, the result will be + /// expanded to have that type, with a cast if necessary. + Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr); - /// getRelevantLoop - Determine the most "relevant" loop for the given SCEV. + /// \brief Determine the most "relevant" loop for the given SCEV. const Loop *getRelevantLoop(const SCEV *); Value *visitConstant(const SCEVConstant *S) {