X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpander.h;h=e5647860db5c136f5d043f36f7c60931937399a4;hp=3f8f149cb4207d07b35ede29612b9121fa66ff8c;hb=72644dfdcd64c186ae04e7a4a125429603e3e7cd;hpb=3b9a911efcf280950f878a050728450423875639 diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 3f8f149cb42..e5647860db5 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -11,24 +11,24 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H -#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H +#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H +#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H -#include "llvm/IRBuilder.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ScalarEvolutionNormalization.h" -#include "llvm/Support/TargetFolder.h" -#include "llvm/Support/ValueHandle.h" +#include "llvm/Analysis/TargetFolder.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/ValueHandle.h" #include namespace llvm { - class TargetLowering; + class TargetTransformInfo; /// Return true if the given expression is safe to expand in the sense that /// all materialized values are safe to speculate. - bool isSafeToExpand(const SCEV *S); + 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,46 +36,48 @@ 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; - std::map, AssertingVH > + // InsertedExpressions caches Values for reuse, so must track RAUW. + std::map, TrackingVH > InsertedExpressions; + // InsertedValues only flags inserted instructions so needs no RAUW. 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; @@ -88,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.TD)) { + /// \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 @@ -102,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() { @@ -112,31 +115,42 @@ 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. + /// 'At' is an optional parameter which specifies point in code where user + /// is going to expand this expression. Sometimes this knowledge can lead to + /// a more accurate cost estimation. + bool isHighCostExpansion(const SCEV *Expr, Loop *L, + const Instruction *At = nullptr) { + SmallPtrSet Processed; + return isHighCostExpansionHelper(Expr, L, At, 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 TargetLowering *TLI = 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"); @@ -144,16 +158,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(); @@ -162,50 +175,61 @@ 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); } void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); } + /// \brief Try to find LLVM IR value for 'S' available at the point 'At'. + // 'L' is a hint which tells in which loop to look for the suitable value. + // On success return value which is equivalent to the expanded 'S' at point + // 'At'. Return nullptr if value was not found. + // Note that this function does not perform exhaustive search. I.e if it + // didn't find any value it does not mean that there is no such value. + Value *findExistingExpansion(const SCEV *S, const Instruction *At, Loop *L); + 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, + const Instruction *At, + 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, @@ -213,13 +237,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) { @@ -250,8 +274,6 @@ namespace llvm { void rememberInstruction(Value *I); - void restoreInsertPoint(BasicBlock *BB, BasicBlock::iterator I); - bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); @@ -260,7 +282,9 @@ namespace llvm { PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, const Loop *L, Type *ExpandTy, - Type *IntTy); + Type *IntTy, + Type *&TruncTy, + bool &InvertStep); Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy, Type *IntTy, bool useSubtract); };