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=2f660c9c5b3689aa3e866b47391f00664f5b55e5;hb=72644dfdcd64c186ae04e7a4a125429603e3e7cd;hpb=f04fa483b83227c570bc58e1684ea096430a6697 diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 2f660c9c5b3..e5647860db5 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -11,114 +11,283 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H -#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H +#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H +#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/Analysis/ScalarEvolution.h" #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 namespace llvm { - class TargetData; + class TargetTransformInfo; - /// SCEVExpander - This class uses information about analyze scalars to + /// 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, ScalarEvolution &SE); + + /// 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, - /// and destroy it when finished to allow the release of the associated + /// and destroy it when finished to allow the release of the associated /// memory. - struct SCEVExpander : public SCEVVisitor { + class SCEVExpander : public SCEVVisitor { ScalarEvolution &SE; - LoopInfo &LI; - const TargetData &TD; - std::map InsertedExpressions; - std::set InsertedInstructions; + const DataLayout &DL; + + // New instructions receive a name to identifies them with the current pass. + const char* IVName; + + // 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; + + /// A memoization of the "relevant" loop for a given SCEV. + DenseMap RelevantLoops; + + /// \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; + + /// \brief When this is non-null, addrecs expanded in the loop it indicates + /// should be inserted with increments at IVIncInsertPos. + const Loop *IVIncInsertLoop; - Instruction *InsertPt; + /// \brief When expanding addrecs in the IVIncInsertLoop loop, insert the IV + /// increment at this position. + Instruction *IVIncInsertPos; + + /// \brief Phis that complete an IV chain. Reuse + std::set > ChainedPhis; + + /// \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; + + /// \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; + BuilderType Builder; + +#ifndef NDEBUG + const char *DebugType; +#endif friend struct SCEVVisitor; + public: - SCEVExpander(ScalarEvolution &se, LoopInfo &li, const TargetData &td) - : SE(se), LI(li), TD(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 + } - LoopInfo &getLoopInfo() const { return LI; } +#ifndef NDEBUG + 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() { InsertedExpressions.clear(); } + void clear() { + InsertedExpressions.clear(); + InsertedValues.clear(); + InsertedPostIncValues.clear(); + ChainedPhis.clear(); + } - /// isInsertedInstruction - 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 InsertedInstructions.count(I); + /// \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); + + /// \brief Return the induction variable increment's IV operand. + Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos, + bool allowScale); + + /// \brief Utility for hoisting an IV increment. + bool hoistIVInc(Instruction *IncV, Instruction *InsertPos); + + /// \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 = nullptr); + + /// \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); + + /// \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"); + IVIncInsertLoop = L; + IVIncInsertPos = Pos; + } + + /// \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; + } + + /// \brief Disable all post-inc expansion. + void clearPostInc() { + PostIncLoops.clear(); + + // When we change the post-inc loop set, cached expansions may no + // longer be valid. + InsertedPostIncValues.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. - Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){ - assert(Ty->isInteger() && "Can only insert integer induction variables!"); - SCEVHandle H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), - SE.getIntegerSCEV(1, Ty), L); - return expand(H); + /// \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; } + + /// \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(); } - /// addInsertedValue - Remember the specified instruction as being the - /// canonical form for the specified SCEV. - void addInsertedValue(Instruction *I, SCEV *S) { - InsertedExpressions[S] = (Value*)I; - InsertedInstructions.insert(I); + /// \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); } - Instruction *getInsertionPoint() const { return InsertPt; } - - /// expandCodeFor - Insert code to directly compute the specified SCEV - /// expression into the program. The inserted code is inserted into the - /// specified block. - Value *expandCodeFor(SCEVHandle SH, const Type *Ty, Instruction *IP); - - /// InsertCastOfTo - Insert a cast of V to the specified type, doing what - /// we can to share the casts. - Value *InsertCastOfTo(Instruction::CastOps opcode, Value *V, - const Type *Ty); - /// InsertBinop - Insert the specified binary operator, doing a small amount + 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(); } + + /// \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. - static Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, - Value *RHS, Instruction *InsertPt); - protected: - Value *expand(SCEV *S); + Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS); + + /// \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); + + /// \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); + + /// \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, + PointerType *PTy, Type *Ty, Value *V); + + Value *expand(const SCEV *S); + + /// \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); - Value *visitConstant(SCEVConstant *S) { + /// \brief Determine the most "relevant" loop for the given SCEV. + const Loop *getRelevantLoop(const SCEV *); + + Value *visitConstant(const SCEVConstant *S) { return S->getValue(); } - Value *visitTruncateExpr(SCEVTruncateExpr *S); + Value *visitTruncateExpr(const SCEVTruncateExpr *S); - Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S); + Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); - Value *visitSignExtendExpr(SCEVSignExtendExpr *S); + Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); - Value *visitAddExpr(SCEVAddExpr *S); + Value *visitAddExpr(const SCEVAddExpr *S); - Value *visitMulExpr(SCEVMulExpr *S); + Value *visitMulExpr(const SCEVMulExpr *S); - Value *visitUDivExpr(SCEVUDivExpr *S); + Value *visitUDivExpr(const SCEVUDivExpr *S); - Value *visitAddRecExpr(SCEVAddRecExpr *S); + Value *visitAddRecExpr(const SCEVAddRecExpr *S); - Value *visitSMaxExpr(SCEVSMaxExpr *S); + Value *visitSMaxExpr(const SCEVSMaxExpr *S); - Value *visitUMaxExpr(SCEVUMaxExpr *S); + Value *visitUMaxExpr(const SCEVUMaxExpr *S); - Value *visitUnknown(SCEVUnknown *S) { + Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); } + + void rememberInstruction(Value *I); + + bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); + + bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); + + Value *expandAddRecExprLiterally(const SCEVAddRecExpr *); + PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, + const Loop *L, + Type *ExpandTy, + Type *IntTy, + Type *&TruncTy, + bool &InvertStep); + Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, + Type *ExpandTy, Type *IntTy, bool useSubtract); }; } #endif -