From f78fe57aeb383146ec336af98af606e5c25417db Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Wed, 22 Jul 2020 14:53:22 +0100 Subject: [PATCH] [SCEVExpander] Fix indentation/formatting (NFC). The declarations inside the llvm namespace where indented too much. Fix it by re-running clang-format on the whole file. --- .../Transforms/Utils/ScalarEvolutionExpander.h | 710 ++++++++++----------- 1 file changed, 349 insertions(+), 361 deletions(-) diff --git a/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h b/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h index 0c88f9f..5cc89df 100644 --- a/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h +++ b/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h @@ -26,410 +26,398 @@ #include "llvm/Support/CommandLine.h" namespace llvm { - extern cl::opt SCEVCheapExpansionBudget; +extern cl::opt SCEVCheapExpansionBudget; + +/// Return true if the given expression is safe to expand in the sense that +/// all materialized values are safe to speculate anywhere their operands are +/// defined. +bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE); + +/// Return true if the given expression is safe to expand in the sense that +/// all materialized values are defined and safe to speculate at the specified +/// location and their operands are defined at this location. +bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, + 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 +/// memory. +class SCEVExpander : public SCEVVisitor { + ScalarEvolution &SE; + const DataLayout &DL; + + // New instructions receive a name to identify them with the current pass. + const char *IVName; + + // InsertedExpressions caches Values for reuse, so must track RAUW. + DenseMap, TrackingVH> + InsertedExpressions; + + // InsertedValues only flags inserted instructions so needs no RAUW. + DenseSet> InsertedValues; + DenseSet> InsertedPostIncValues; + + /// A memoization of the "relevant" loop for a given SCEV. + DenseMap RelevantLoops; + + /// 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; + + /// When this is non-null, addrecs expanded in the loop it indicates should + /// be inserted with increments at IVIncInsertPos. + const Loop *IVIncInsertLoop; + + /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV + /// increment at this position. + Instruction *IVIncInsertPos; + + /// Phis that complete an IV chain. Reuse + DenseSet> ChainedPhis; + + /// When true, SCEVExpander tries to expand expressions in "canonical" form. + /// When false, expressions are expanded in a more literal form. + /// + /// In "canonical" form addrecs are expanded as arithmetic based on a + /// canonical induction variable. Note that CanonicalMode doesn't guarantee + /// that all expressions are expanded in "canonical" form. For some + /// expressions literal mode can be preferred. + 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. + bool LSRMode; + + typedef IRBuilder BuilderType; + BuilderType Builder; + + // RAII object that stores the current insertion point and restores it when + // the object is destroyed. This includes the debug location. Duplicated + // from InsertPointGuard to add SetInsertPoint() which is used to updated + // InsertPointGuards stack when insert points are moved during SCEV + // expansion. + class SCEVInsertPointGuard { + IRBuilderBase &Builder; + AssertingVH Block; + BasicBlock::iterator Point; + DebugLoc DbgLoc; + SCEVExpander *SE; + + SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete; + SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete; - /// Return true if the given expression is safe to expand in the sense that - /// all materialized values are safe to speculate anywhere their operands are - /// defined. - bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE); + public: + SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE) + : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()), + DbgLoc(B.getCurrentDebugLocation()), SE(SE) { + SE->InsertPointGuards.push_back(this); + } - /// Return true if the given expression is safe to expand in the sense that - /// all materialized values are defined and safe to speculate at the specified - /// location and their operands are defined at this location. - bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, - ScalarEvolution &SE); + ~SCEVInsertPointGuard() { + // These guards should always created/destroyed in FIFO order since they + // are used to guard lexically scoped blocks of code in + // ScalarEvolutionExpander. + assert(SE->InsertPointGuards.back() == this); + SE->InsertPointGuards.pop_back(); + Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point)); + Builder.SetCurrentDebugLocation(DbgLoc); + } - /// 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 - /// memory. - class SCEVExpander : public SCEVVisitor { - ScalarEvolution &SE; - const DataLayout &DL; - - // New instructions receive a name to identify them with the current pass. - const char* IVName; - - // InsertedExpressions caches Values for reuse, so must track RAUW. - DenseMap, TrackingVH> - InsertedExpressions; - - // InsertedValues only flags inserted instructions so needs no RAUW. - DenseSet> InsertedValues; - DenseSet> InsertedPostIncValues; - - /// A memoization of the "relevant" loop for a given SCEV. - DenseMap RelevantLoops; - - /// 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; - - /// When this is non-null, addrecs expanded in the loop it indicates should - /// be inserted with increments at IVIncInsertPos. - const Loop *IVIncInsertLoop; - - /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV - /// increment at this position. - Instruction *IVIncInsertPos; - - /// Phis that complete an IV chain. Reuse - DenseSet> ChainedPhis; - - /// When true, SCEVExpander tries to expand expressions in "canonical" form. - /// When false, expressions are expanded in a more literal form. - /// - /// In "canonical" form addrecs are expanded as arithmetic based on a - /// canonical induction variable. Note that CanonicalMode doesn't guarantee - /// that all expressions are expanded in "canonical" form. For some - /// expressions literal mode can be preferred. - 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. - bool LSRMode; - - typedef IRBuilder BuilderType; - BuilderType Builder; - - // RAII object that stores the current insertion point and restores it when - // the object is destroyed. This includes the debug location. Duplicated - // from InsertPointGuard to add SetInsertPoint() which is used to updated - // InsertPointGuards stack when insert points are moved during SCEV - // expansion. - class SCEVInsertPointGuard { - IRBuilderBase &Builder; - AssertingVH Block; - BasicBlock::iterator Point; - DebugLoc DbgLoc; - SCEVExpander *SE; - - SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete; - SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete; - - public: - SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE) - : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()), - DbgLoc(B.getCurrentDebugLocation()), SE(SE) { - SE->InsertPointGuards.push_back(this); - } - - ~SCEVInsertPointGuard() { - // These guards should always created/destroyed in FIFO order since they - // are used to guard lexically scoped blocks of code in - // ScalarEvolutionExpander. - assert(SE->InsertPointGuards.back() == this); - SE->InsertPointGuards.pop_back(); - Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point)); - Builder.SetCurrentDebugLocation(DbgLoc); - } - - BasicBlock::iterator GetInsertPoint() const { return Point; } - void SetInsertPoint(BasicBlock::iterator I) { Point = I; } - }; - - /// Stack of pointers to saved insert points, used to keep insert points - /// consistent when instructions are moved. - SmallVector InsertPointGuards; + BasicBlock::iterator GetInsertPoint() const { return Point; } + void SetInsertPoint(BasicBlock::iterator I) { Point = I; } + }; + + /// Stack of pointers to saved insert points, used to keep insert points + /// consistent when instructions are moved. + SmallVector InsertPointGuards; #ifndef NDEBUG - const char *DebugType; + const char *DebugType; #endif - friend struct SCEVVisitor; + friend struct SCEVVisitor; - public: - /// 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)) { +public: + /// 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 = ""; + DebugType = ""; #endif - } + } - ~SCEVExpander() { - // Make sure the insert point guard stack is consistent. - assert(InsertPointGuards.empty()); - } + ~SCEVExpander() { + // Make sure the insert point guard stack is consistent. + assert(InsertPointGuards.empty()); + } #ifndef NDEBUG - void setDebugType(const char* s) { DebugType = s; } + void setDebugType(const char *s) { DebugType = s; } #endif - /// 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(); - InsertedValues.clear(); - InsertedPostIncValues.clear(); - ChainedPhis.clear(); - } - - /// Return true for expressions that can't be evaluated at runtime - /// within given \b Budget. - /// - /// At is a parameter which specifies point in code where user is going to - /// expand this expression. Sometimes this knowledge can lead to - /// a less pessimistic cost estimation. - bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget, - const TargetTransformInfo *TTI, - const Instruction *At) { - assert(TTI && "This function requires TTI to be provided."); - assert(At && "This function requires At instruction to be provided."); - if (!TTI) // In assert-less builds, avoid crashing - return true; // by always claiming to be high-cost. - SmallVector Worklist; - SmallPtrSet Processed; - int BudgetRemaining = Budget * TargetTransformInfo::TCC_Basic; - Worklist.emplace_back(Expr); - while (!Worklist.empty()) { - const SCEV *S = Worklist.pop_back_val(); - if (isHighCostExpansionHelper(S, L, *At, BudgetRemaining, *TTI, - Processed, Worklist)) - return true; - } - assert(BudgetRemaining >= 0 && "Should have returned from inner loop."); - return false; - } - - /// 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); - - /// Return the induction variable increment's IV operand. - Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos, - bool allowScale); - - /// Utility for hoisting an IV increment. - bool hoistIVInc(Instruction *IncV, Instruction *InsertPos); - - /// 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); - - /// 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); - - /// 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); - - - /// Generates a code sequence that evaluates this predicate. The inserted - /// instructions will be at position \p Loc. The result will be of type i1 - /// and will have a value of 0 when the predicate is false and 1 otherwise. - Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc); - - /// A specialized variant of expandCodeForPredicate, handling the case when - /// we are expanding code for a SCEVEqualPredicate. - Value *expandEqualPredicate(const SCEVEqualPredicate *Pred, - Instruction *Loc); - - /// Generates code that evaluates if the \p AR expression will overflow. - Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, - bool Signed); - - /// A specialized variant of expandCodeForPredicate, handling the case when - /// we are expanding code for a SCEVWrapPredicate. - Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc); - - /// A specialized variant of expandCodeForPredicate, handling the case when - /// we are expanding code for a SCEVUnionPredicate. - Value *expandUnionPredicate(const SCEVUnionPredicate *Pred, - Instruction *Loc); - - /// 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; - } - - /// 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; + /// 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(); + InsertedValues.clear(); + InsertedPostIncValues.clear(); + ChainedPhis.clear(); + } + + /// Return true for expressions that can't be evaluated at runtime + /// within given \b Budget. + /// + /// At is a parameter which specifies point in code where user is going to + /// expand this expression. Sometimes this knowledge can lead to + /// a less pessimistic cost estimation. + bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget, + const TargetTransformInfo *TTI, + const Instruction *At) { + assert(TTI && "This function requires TTI to be provided."); + assert(At && "This function requires At instruction to be provided."); + if (!TTI) // In assert-less builds, avoid crashing + return true; // by always claiming to be high-cost. + SmallVector Worklist; + SmallPtrSet Processed; + int BudgetRemaining = Budget * TargetTransformInfo::TCC_Basic; + Worklist.emplace_back(Expr); + while (!Worklist.empty()) { + const SCEV *S = Worklist.pop_back_val(); + if (isHighCostExpansionHelper(S, L, *At, BudgetRemaining, *TTI, Processed, + Worklist)) + return true; } + assert(BudgetRemaining >= 0 && "Should have returned from inner loop."); + return false; + } + + /// 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); + + /// Return the induction variable increment's IV operand. + Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos, + bool allowScale); + + /// Utility for hoisting an IV increment. + bool hoistIVInc(Instruction *IncV, Instruction *InsertPos); + + /// 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); + + /// 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); + + /// 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); + + /// Generates a code sequence that evaluates this predicate. The inserted + /// instructions will be at position \p Loc. The result will be of type i1 + /// and will have a value of 0 when the predicate is false and 1 otherwise. + Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc); + + /// A specialized variant of expandCodeForPredicate, handling the case when + /// we are expanding code for a SCEVEqualPredicate. + Value *expandEqualPredicate(const SCEVEqualPredicate *Pred, Instruction *Loc); + + /// Generates code that evaluates if the \p AR expression will overflow. + Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, + bool Signed); + + /// A specialized variant of expandCodeForPredicate, handling the case when + /// we are expanding code for a SCEVWrapPredicate. + Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc); + + /// A specialized variant of expandCodeForPredicate, handling the case when + /// we are expanding code for a SCEVUnionPredicate. + Value *expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc); + + /// 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; + } + + /// 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; + } + + /// 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(); + } + + /// 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; } + + /// Set the current insertion point. This is useful if multiple calls to + /// expandCodeFor() are going to be made with the same insert point and the + /// insert point may be moved during one of the expansions (e.g. if the + /// insert point is not a block terminator). + void setInsertPoint(Instruction *IP) { + assert(IP); + Builder.SetInsertPoint(IP); + } + + /// 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(); } + + /// Set location information used by debugging information. + void SetCurrentDebugLocation(DebugLoc L) { + Builder.SetCurrentDebugLocation(std::move(L)); + } + + /// Get location information used by debugging information. + const DebugLoc &getCurrentDebugLocation() const { + return Builder.getCurrentDebugLocation(); + } + + /// 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); } + + /// Try to find existing LLVM IR value for S available at the point At. + Value *getExactExistingExpansion(const SCEV *S, const Instruction *At, + Loop *L); + + /// Try to find the ValueOffsetPair for S. The function is mainly used to + /// check whether S can be expanded cheaply. If this returns a non-None + /// value, we know we can codegen the `ValueOffsetPair` into a suitable + /// expansion identical with S so that S can be expanded cheaply. + /// + /// 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 an exhaustive search. I.e if it + /// didn't find any value it does not mean that there is no such value. + /// + Optional + getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L); - /// Disable all post-inc expansion. - void clearPostInc() { - PostIncLoops.clear(); +private: + LLVMContext &getContext() const { return SE.getContext(); } - // When we change the post-inc loop set, cached expansions may no - // longer be valid. - InsertedPostIncValues.clear(); - } + /// Recursive helper function for isHighCostExpansion. + bool isHighCostExpansionHelper(const SCEV *S, Loop *L, const Instruction &At, + int &BudgetRemaining, + const TargetTransformInfo &TTI, + SmallPtrSetImpl &Processed, + SmallVectorImpl &Worklist); - /// 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; } + /// Insert the specified binary operator, doing a small amount of work to + /// avoid inserting an obviously redundant operation, and hoisting to an + /// outer loop when the opportunity is there and it is safe. + Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, + SCEV::NoWrapFlags Flags, bool IsSafeToHoist); - void enableLSRMode() { LSRMode = true; } + /// 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 creating a new one. + Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op, + BasicBlock::iterator IP); - /// Set the current insertion point. This is useful if multiple calls to - /// expandCodeFor() are going to be made with the same insert point and the - /// insert point may be moved during one of the expansions (e.g. if the - /// insert point is not a block terminator). - void setInsertPoint(Instruction *IP) { - assert(IP); - Builder.SetInsertPoint(IP); - } + /// 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); - /// 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(); } + /// 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 *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V); - /// Set location information used by debugging information. - void SetCurrentDebugLocation(DebugLoc L) { - Builder.SetCurrentDebugLocation(std::move(L)); - } + /// Find a previous Value in ExprValueMap for expand. + ScalarEvolution::ValueOffsetPair + FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt); - /// Get location information used by debugging information. - const DebugLoc &getCurrentDebugLocation() const { - return Builder.getCurrentDebugLocation(); - } + Value *expand(const SCEV *S); - /// 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); - } + /// Determine the most "relevant" loop for the given SCEV. + const Loop *getRelevantLoop(const SCEV *); - void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); } - - /// Try to find existing LLVM IR value for S available at the point At. - Value *getExactExistingExpansion(const SCEV *S, const Instruction *At, - Loop *L); - - /// Try to find the ValueOffsetPair for S. The function is mainly used to - /// check whether S can be expanded cheaply. If this returns a non-None - /// value, we know we can codegen the `ValueOffsetPair` into a suitable - /// expansion identical with S so that S can be expanded cheaply. - /// - /// 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 an exhaustive search. I.e if it - /// didn't find any value it does not mean that there is no such value. - /// - Optional - getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L); - - private: - LLVMContext &getContext() const { return SE.getContext(); } - - /// Recursive helper function for isHighCostExpansion. - bool isHighCostExpansionHelper(const SCEV *S, Loop *L, - const Instruction &At, int &BudgetRemaining, - const TargetTransformInfo &TTI, - SmallPtrSetImpl &Processed, - SmallVectorImpl &Worklist); - - /// Insert the specified binary operator, doing a small amount of work to - /// avoid inserting an obviously redundant operation, and hoisting to an - /// outer loop when the opportunity is there and it is safe. - Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, - SCEV::NoWrapFlags Flags, bool IsSafeToHoist); - - /// 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 creating a new one. - Value *ReuseOrCreateCast(Value *V, Type *Ty, - Instruction::CastOps Op, - BasicBlock::iterator IP); - - /// 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); - - /// 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 *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V); - - /// Find a previous Value in ExprValueMap for expand. - ScalarEvolution::ValueOffsetPair - FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt); - - Value *expand(const SCEV *S); - - /// Determine the most "relevant" loop for the given SCEV. - const Loop *getRelevantLoop(const SCEV *); - - Value *visitConstant(const SCEVConstant *S) { - return S->getValue(); - } + Value *visitConstant(const SCEVConstant *S) { return S->getValue(); } - Value *visitTruncateExpr(const SCEVTruncateExpr *S); + Value *visitTruncateExpr(const SCEVTruncateExpr *S); - Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); + Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); - Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); + Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); - Value *visitAddExpr(const SCEVAddExpr *S); + Value *visitAddExpr(const SCEVAddExpr *S); - Value *visitMulExpr(const SCEVMulExpr *S); + Value *visitMulExpr(const SCEVMulExpr *S); - Value *visitUDivExpr(const SCEVUDivExpr *S); + Value *visitUDivExpr(const SCEVUDivExpr *S); - Value *visitAddRecExpr(const SCEVAddRecExpr *S); + Value *visitAddRecExpr(const SCEVAddRecExpr *S); - Value *visitSMaxExpr(const SCEVSMaxExpr *S); + Value *visitSMaxExpr(const SCEVSMaxExpr *S); - Value *visitUMaxExpr(const SCEVUMaxExpr *S); + Value *visitUMaxExpr(const SCEVUMaxExpr *S); - Value *visitSMinExpr(const SCEVSMinExpr *S); + Value *visitSMinExpr(const SCEVSMinExpr *S); - Value *visitUMinExpr(const SCEVUMinExpr *S); + Value *visitUMinExpr(const SCEVUMinExpr *S); - Value *visitUnknown(const SCEVUnknown *S) { - return S->getValue(); - } + Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); } - void rememberInstruction(Value *I); + void rememberInstruction(Value *I); - bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); + bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); - bool isExpandedAddRecExprPHI(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); + 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); - void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, - Instruction *Pos, PHINode *LoopPhi); + void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, + Instruction *Pos, PHINode *LoopPhi); - void fixupInsertPoints(Instruction *I); - }; -} + void fixupInsertPoints(Instruction *I); +}; +} // namespace llvm #endif -- 2.7.4