diff options
Diffstat (limited to 'include/llvm/Analysis')
23 files changed, 182 insertions, 132 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 43bcc34..6999bd1 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -145,6 +145,19 @@ public: Location getLocation(const AtomicRMWInst *RMWI); static Location getLocationForSource(const MemTransferInst *MTI); static Location getLocationForDest(const MemIntrinsic *MI); + Location getLocation(const Instruction *Inst) { + if (auto *I = dyn_cast<LoadInst>(Inst)) + return getLocation(I); + else if (auto *I = dyn_cast<StoreInst>(Inst)) + return getLocation(I); + else if (auto *I = dyn_cast<VAArgInst>(Inst)) + return getLocation(I); + else if (auto *I = dyn_cast<AtomicCmpXchgInst>(Inst)) + return getLocation(I); + else if (auto *I = dyn_cast<AtomicRMWInst>(Inst)) + return getLocation(I); + llvm_unreachable("unsupported memory instruction"); + } /// Alias analysis result - Either we know for sure that it does not alias, we /// know for sure it must alias, or we don't know anything: The two pointers @@ -352,6 +365,24 @@ public: return (MRB & ModRef) && (MRB & ArgumentPointees); } + /// getModRefInfo - Return information about whether or not an + /// instruction may read or write memory (without regard to a + /// specific location) + ModRefResult getModRefInfo(const Instruction *I) { + if (auto CS = ImmutableCallSite(I)) { + auto MRB = getModRefBehavior(CS); + if (MRB & ModRef) + return ModRef; + else if (MRB & Ref) + return Ref; + else if (MRB & Mod) + return Mod; + return NoModRef; + } + + return getModRefInfo(I, Location()); + } + /// getModRefInfo - Return information about whether or not an instruction may /// read or write the specified memory location. An instruction /// that doesn't read or write memory may be trivially LICM'd for example. @@ -472,6 +503,10 @@ public: ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, uint64_t Size){ return getModRefInfo(I, Location(P, Size)); } + /// getModRefInfo - Return information about whether a call and an instruction + /// may refer to the same memory locations. + ModRefResult getModRefInfo(Instruction *I, + ImmutableCallSite Call); /// getModRefInfo - Return information about whether two call sites may refer /// to the same set of memory locations. See diff --git a/include/llvm/Analysis/AssumptionCache.h b/include/llvm/Analysis/AssumptionCache.h index fc1393f..1f00b69 100644 --- a/include/llvm/Analysis/AssumptionCache.h +++ b/include/llvm/Analysis/AssumptionCache.h @@ -165,7 +165,7 @@ public: AssumptionCache &getAssumptionCache(Function &F); AssumptionCacheTracker(); - ~AssumptionCacheTracker(); + ~AssumptionCacheTracker() override; void releaseMemory() override { AssumptionCaches.shrink_and_clear(); } diff --git a/include/llvm/Analysis/BlockFrequencyInfo.h b/include/llvm/Analysis/BlockFrequencyInfo.h index 3289a28..f27c32d 100644 --- a/include/llvm/Analysis/BlockFrequencyInfo.h +++ b/include/llvm/Analysis/BlockFrequencyInfo.h @@ -34,7 +34,7 @@ public: BlockFrequencyInfo(); - ~BlockFrequencyInfo(); + ~BlockFrequencyInfo() override; void getAnalysisUsage(AnalysisUsage &AU) const override; diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h index 57b5154..9acc863 100644 --- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -718,9 +718,6 @@ void IrreducibleGraph::addEdges(const BlockNode &Node, /// /// It has some known flaws. /// -/// - Loop scale is limited to 4096 per loop (2^12) to avoid exhausting -/// BlockFrequency's 64-bit integer precision. -/// /// - The model of irreducible control flow is a rough approximation. /// /// Modelling irreducible control flow exactly involves setting up and diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index 64d288a..14b8822 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -318,7 +318,7 @@ public: static char ID; // Class identification, replacement for typeinfo CallGraphWrapperPass(); - virtual ~CallGraphWrapperPass(); + ~CallGraphWrapperPass() override; /// \brief The internal \c CallGraph around which the rest of this interface /// is wrapped. diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h index ce0b899..0b3b2ea 100644 --- a/include/llvm/Analysis/DependenceAnalysis.h +++ b/include/llvm/Analysis/DependenceAnalysis.h @@ -219,7 +219,7 @@ namespace llvm { public: FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, unsigned Levels); - ~FullDependence() { delete[] DV; } + ~FullDependence() override { delete[] DV; } /// isLoopIndependent - Returns true if this is a loop-independent /// dependence. diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index fdee9f8..79ed74d 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -107,7 +107,7 @@ public: static char ID; InlineCostAnalysis(); - ~InlineCostAnalysis(); + ~InlineCostAnalysis() override; // Pass interface implementation. void getAnalysisUsage(AnalysisUsage &AU) const override; diff --git a/include/llvm/Analysis/JumpInstrTableInfo.h b/include/llvm/Analysis/JumpInstrTableInfo.h index 591e794..b6dad47 100644 --- a/include/llvm/Analysis/JumpInstrTableInfo.h +++ b/include/llvm/Analysis/JumpInstrTableInfo.h @@ -39,7 +39,7 @@ public: /// The default byte alignment for jump tables is 16, which is large but /// usually safe. JumpInstrTableInfo(uint64_t ByteAlign = 16); - virtual ~JumpInstrTableInfo(); + ~JumpInstrTableInfo() override; const char *getPassName() const override { return "Jump-Instruction Table Info"; } diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h index 8e5bbfb..1051cff 100644 --- a/include/llvm/Analysis/LazyValueInfo.h +++ b/include/llvm/Analysis/LazyValueInfo.h @@ -39,7 +39,7 @@ public: LazyValueInfo() : FunctionPass(ID), PImpl(nullptr) { initializeLazyValueInfoPass(*PassRegistry::getPassRegistry()); } - ~LazyValueInfo() { assert(!PImpl && "releaseMemory not called"); } + ~LazyValueInfo() override { assert(!PImpl && "releaseMemory not called"); } /// This is used to return true/false/dunno results. enum Tristate { diff --git a/include/llvm/Analysis/LibCallAliasAnalysis.h b/include/llvm/Analysis/LibCallAliasAnalysis.h index 49e0dc8..df95e0e 100644 --- a/include/llvm/Analysis/LibCallAliasAnalysis.h +++ b/include/llvm/Analysis/LibCallAliasAnalysis.h @@ -36,8 +36,8 @@ namespace llvm { : FunctionPass(ID), LCI(LC) { initializeLibCallAliasAnalysisPass(*PassRegistry::getPassRegistry()); } - ~LibCallAliasAnalysis(); - + ~LibCallAliasAnalysis() override; + ModRefResult getModRefInfo(ImmutableCallSite CS, const Location &Loc) override; diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h index 0a9dc07..a4393bb 100644 --- a/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/include/llvm/Analysis/LoopAccessAnalysis.h @@ -339,6 +339,10 @@ public: bool needsChecking(unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const; + /// \brief Return true if any pointer requires run-time checking according + /// to needsChecking. + bool needsAnyChecking(const SmallVectorImpl<int> *PtrPartition) const; + /// \brief Print the list run-time memory checks necessary. /// /// If \p PtrPartition is set, it contains the partition number for @@ -428,6 +432,13 @@ public: /// Only used in DEBUG build but we don't want NDEBUG-dependent ABI. unsigned NumSymbolicStrides; + /// \brief Checks existence of store to invariant address inside loop. + /// If the loop has any store to invariant address, then it returns true, + /// else returns false. + bool hasStoreToLoopInvariantAddress() const { + return StoreToLoopInvariantAddress; + } + private: /// \brief Analyze the loop. Substitute symbolic strides using Strides. void analyzeLoop(const ValueToValueMap &Strides); @@ -465,6 +476,10 @@ private: /// \brief Cache the result of analyzeLoop. bool CanVecMem; + /// \brief Indicator for storing to uniform addresses. + /// If a loop has write to a loop invariant address then it should be true. + bool StoreToLoopInvariantAddress; + /// \brief The diagnostics report generated for the analysis. E.g. why we /// couldn't analyze the loop. Optional<LoopAccessReport> Report; diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 85c2da7..f3d85e6 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -464,23 +464,20 @@ public: /// cannot find a terminating instruction with location information, /// it returns an unknown location. DebugLoc getStartLoc() const { - DebugLoc StartLoc; BasicBlock *HeadBB; // Try the pre-header first. - if ((HeadBB = getLoopPreheader()) != nullptr) { - StartLoc = HeadBB->getTerminator()->getDebugLoc(); - if (!StartLoc.isUnknown()) - return StartLoc; - } + if ((HeadBB = getLoopPreheader()) != nullptr) + if (DebugLoc DL = HeadBB->getTerminator()->getDebugLoc()) + return DL; // If we have no pre-header or there are no instructions with debug // info in it, try the header. HeadBB = getHeader(); if (HeadBB) - StartLoc = HeadBB->getTerminator()->getDebugLoc(); + return HeadBB->getTerminator()->getDebugLoc(); - return StartLoc; + return DebugLoc(); } private: diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h index 7cc4a77..0490bb1 100644 --- a/include/llvm/Analysis/LoopInfoImpl.h +++ b/include/llvm/Analysis/LoopInfoImpl.h @@ -409,9 +409,6 @@ class PopulateLoopsDFS { typedef typename BlockTraits::ChildIteratorType SuccIterTy; LoopInfoBase<BlockT, LoopT> *LI; - DenseSet<const BlockT *> VisitedBlocks; - std::vector<std::pair<BlockT*, SuccIterTy> > DFSStack; - public: PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li): LI(li) {} @@ -420,36 +417,13 @@ public: protected: void insertIntoLoop(BlockT *Block); - - BlockT *dfsSource() { return DFSStack.back().first; } - SuccIterTy &dfsSucc() { return DFSStack.back().second; } - SuccIterTy dfsSuccEnd() { return BlockTraits::child_end(dfsSource()); } - - void pushBlock(BlockT *Block) { - DFSStack.push_back(std::make_pair(Block, BlockTraits::child_begin(Block))); - } }; /// Top-level driver for the forward DFS within the loop. template<class BlockT, class LoopT> void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { - pushBlock(EntryBlock); - VisitedBlocks.insert(EntryBlock); - while (!DFSStack.empty()) { - // Traverse the leftmost path as far as possible. - while (dfsSucc() != dfsSuccEnd()) { - BlockT *BB = *dfsSucc(); - ++dfsSucc(); - if (!VisitedBlocks.insert(BB).second) - continue; - - // Push the next DFS successor onto the stack. - pushBlock(BB); - } - // Visit the top of the stack in postorder and backtrack. - insertIntoLoop(dfsSource()); - DFSStack.pop_back(); - } + for (BlockT *BB : post_order(EntryBlock)) + insertIntoLoop(BB); } /// Add a single Block to its ancestor loops in PostOrder. If the block is a @@ -498,10 +472,9 @@ Analyze(DominatorTreeBase<BlockT> &DomTree) { // Postorder traversal of the dominator tree. DomTreeNodeBase<BlockT>* DomRoot = DomTree.getRootNode(); - for (po_iterator<DomTreeNodeBase<BlockT>*> DomIter = po_begin(DomRoot), - DomEnd = po_end(DomRoot); DomIter != DomEnd; ++DomIter) { + for (auto DomNode : post_order(DomRoot)) { - BlockT *Header = DomIter->getBlock(); + BlockT *Header = DomNode->getBlock(); SmallVector<BlockT *, 4> Backedges; // Check each predecessor of the potential loop header. diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index abc2b90..c8453e9 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -329,7 +329,7 @@ namespace llvm { public: MemoryDependenceAnalysis(); - ~MemoryDependenceAnalysis(); + ~MemoryDependenceAnalysis() override; static char ID; /// Pass Implementation stuff. This doesn't do any analysis eagerly. diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 8d11e80..d112ab1 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -138,6 +138,13 @@ namespace llvm { //===--------------------------------------------------------------------===// // + // createDivergenceAnalysisPass - This pass determines which branches in a GPU + // program are divergent. + // + FunctionPass *createDivergenceAnalysisPass(); + + //===--------------------------------------------------------------------===// + // // Minor pass prototypes, allowing us to expose them through bugpoint and // analyze. FunctionPass *createInstCountPass(); diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 72cd357..0f7e2b8 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -30,7 +30,7 @@ struct PostDominatorTree : public FunctionPass { DT = new DominatorTreeBase<BasicBlock>(true); } - ~PostDominatorTree(); + ~PostDominatorTree() override; bool runOnFunction(Function &F) override; diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index 1c7f4d3..7ceb086 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -820,8 +820,6 @@ public: inline RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion = false) : RegionNodeBase<RegionTraits<Function>>(Parent, Entry, isSubRegion) {} - ~RegionNode() {} - bool operator==(const Region &RN) const { return this == reinterpret_cast<const RegionNode *>(&RN); } @@ -842,7 +840,7 @@ class RegionInfo : public RegionInfoBase<RegionTraits<Function>> { public: explicit RegionInfo(); - virtual ~RegionInfo(); + ~RegionInfo() override; // updateStatistics - Update statistic about created regions. void updateStatistics(Region *R) final; @@ -858,7 +856,7 @@ public: static char ID; explicit RegionInfoPass(); - ~RegionInfoPass(); + ~RegionInfoPass() override; RegionInfo &getRegionInfo() { return RI; } diff --git a/include/llvm/Analysis/RegionInfoImpl.h b/include/llvm/Analysis/RegionInfoImpl.h index b0dc263..b31eefc 100644 --- a/include/llvm/Analysis/RegionInfoImpl.h +++ b/include/llvm/Analysis/RegionInfoImpl.h @@ -487,7 +487,7 @@ void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level, OS.indent(level * 2 + 2); if (Style == PrintBB) { - for (const auto &BB : blocks()) + for (const auto *BB : blocks()) OS << BB->getName() << ", "; // TODO: remove the last "," } else if (Style == PrintRN) { for (const_element_iterator I = element_begin(), E = element_end(); @@ -714,10 +714,8 @@ void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) { // regions from the bottom of the dominance tree. If the small regions are // detected first, detection of bigger regions is faster, as we can jump // over the small regions. - for (po_iterator<DomTreeNodeT *> FI = po_begin(N), FE = po_end(N); FI != FE; - ++FI) { - findRegionsWithEntry(FI->getBlock(), ShortCut); - } + for (auto DomNode : post_order(N)) + findRegionsWithEntry(DomNode->getBlock(), ShortCut); } template <class Tr> diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 4360414..1240b85 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -256,6 +256,10 @@ namespace llvm { /// Mark predicate values currently being processed by isImpliedCond. DenseSet<Value*> PendingLoopPredicates; + /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of + /// conditions dominating the backedge of a loop. + bool WalkingBEDominatingConds; + /// ExitLimit - Information about the number of loop iterations for which a /// loop exit's branch condition evaluates to the not-taken path. This is a /// temporary pair of exact and max expressions that are eventually diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index b0b0946..8ec2078 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -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, @@ -48,37 +48,36 @@ namespace llvm { std::set<AssertingVH<Value> > InsertedValues; std::set<AssertingVH<Value> > InsertedPostIncValues; - /// RelevantLoops - A memoization of the "relevant" loop for a given SCEV. + /// A memoization of the "relevant" loop for a given SCEV. DenseMap<const SCEV *, const Loop *> 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}<L> in post-inc mode /// returns the add instruction that adds one to the phi for {0,+,1}<L>, /// 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<AssertingVH<PHINode> > 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<true, TargetFolder> BuilderType; @@ -91,7 +90,7 @@ namespace llvm { friend struct SCEVVisitor<SCEVExpander, Value*>; public: - /// SCEVExpander - Construct a SCEVExpander in "canonical" mode. + /// \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), @@ -106,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() { @@ -116,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<const SCEV *, 8> 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<WeakVH> &DeadInsts, 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"); @@ -148,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(); @@ -166,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); } @@ -192,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<const SCEV *> &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, @@ -217,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. + /// \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) { diff --git a/include/llvm/Analysis/TargetFolder.h b/include/llvm/Analysis/TargetFolder.h index f691296..12bf9fe 100644 --- a/include/llvm/Analysis/TargetFolder.h +++ b/include/llvm/Analysis/TargetFolder.h @@ -130,34 +130,35 @@ public: // Memory Instructions //===--------------------------------------------------------------------===// - Constant *CreateGetElementPtr(Constant *C, + Constant *CreateGetElementPtr(Type *Ty, Constant *C, ArrayRef<Constant *> IdxList) const { - return Fold(ConstantExpr::getGetElementPtr(C, IdxList)); + return Fold(ConstantExpr::getGetElementPtr(Ty, C, IdxList)); } - Constant *CreateGetElementPtr(Constant *C, Constant *Idx) const { + Constant *CreateGetElementPtr(Type *Ty, Constant *C, Constant *Idx) const { // This form of the function only exists to avoid ambiguous overload // warnings about whether to convert Idx to ArrayRef<Constant *> or // ArrayRef<Value *>. - return Fold(ConstantExpr::getGetElementPtr(C, Idx)); + return Fold(ConstantExpr::getGetElementPtr(Ty, C, Idx)); } - Constant *CreateGetElementPtr(Constant *C, + Constant *CreateGetElementPtr(Type *Ty, Constant *C, ArrayRef<Value *> IdxList) const { - return Fold(ConstantExpr::getGetElementPtr(C, IdxList)); + return Fold(ConstantExpr::getGetElementPtr(Ty, C, IdxList)); } - Constant *CreateInBoundsGetElementPtr(Constant *C, + Constant *CreateInBoundsGetElementPtr(Type *Ty, Constant *C, ArrayRef<Constant *> IdxList) const { - return Fold(ConstantExpr::getInBoundsGetElementPtr(C, IdxList)); + return Fold(ConstantExpr::getInBoundsGetElementPtr(Ty, C, IdxList)); } - Constant *CreateInBoundsGetElementPtr(Constant *C, Constant *Idx) const { + Constant *CreateInBoundsGetElementPtr(Type *Ty, Constant *C, + Constant *Idx) const { // This form of the function only exists to avoid ambiguous overload // warnings about whether to convert Idx to ArrayRef<Constant *> or // ArrayRef<Value *>. - return Fold(ConstantExpr::getInBoundsGetElementPtr(C, Idx)); + return Fold(ConstantExpr::getInBoundsGetElementPtr(Ty, C, Idx)); } - Constant *CreateInBoundsGetElementPtr(Constant *C, + Constant *CreateInBoundsGetElementPtr(Type *Ty, Constant *C, ArrayRef<Value *> IdxList) const { - return Fold(ConstantExpr::getInBoundsGetElementPtr(C, IdxList)); + return Fold(ConstantExpr::getInBoundsGetElementPtr(Ty, C, IdxList)); } //===--------------------------------------------------------------------===// diff --git a/include/llvm/Analysis/TargetTransformInfo.h b/include/llvm/Analysis/TargetTransformInfo.h index fdb2010..f4195fb 100644 --- a/include/llvm/Analysis/TargetTransformInfo.h +++ b/include/llvm/Analysis/TargetTransformInfo.h @@ -190,12 +190,21 @@ public: /// comments for a detailed explanation of the cost values. unsigned getUserCost(const User *U) const; - /// \brief hasBranchDivergence - Return true if branch divergence exists. + /// \brief Return true if branch divergence exists. + /// /// Branch divergence has a significantly negative impact on GPU performance /// when threads in the same wavefront take different paths due to conditional /// branches. bool hasBranchDivergence() const; + /// \brief Returns whether V is a source of divergence. + /// + /// This function provides the target-dependent information for + /// the target-independent DivergenceAnalysis. DivergenceAnalysis first + /// builds the dependency graph, and then runs the reachability algorithm + /// starting with the sources of divergence. + bool isSourceOfDivergence(const Value *V) const; + /// \brief Test whether calls to a function lower to actual program function /// calls. /// @@ -252,6 +261,9 @@ public: /// loop body even when the number of loop iterations is not known at /// compile time). bool Runtime; + /// Allow emitting expensive instructions (such as divisions) when computing + /// the trip count of a loop for runtime unrolling. + bool AllowExpensiveTripCount; }; /// \brief Get target-customized preferences for the generic loop unrolling @@ -520,6 +532,7 @@ public: ArrayRef<const Value *> Arguments) = 0; virtual unsigned getUserCost(const User *U) = 0; virtual bool hasBranchDivergence() = 0; + virtual bool isSourceOfDivergence(const Value *V) = 0; virtual bool isLoweredToCall(const Function *F) = 0; virtual void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) = 0; virtual bool isLegalAddImmediate(int64_t Imm) = 0; @@ -619,6 +632,9 @@ public: } unsigned getUserCost(const User *U) override { return Impl.getUserCost(U); } bool hasBranchDivergence() override { return Impl.hasBranchDivergence(); } + bool isSourceOfDivergence(const Value *V) override { + return Impl.isSourceOfDivergence(V); + } bool isLoweredToCall(const Function *F) override { return Impl.isLoweredToCall(F); } diff --git a/include/llvm/Analysis/TargetTransformInfoImpl.h b/include/llvm/Analysis/TargetTransformInfoImpl.h index f4bf07f..b00de77 100644 --- a/include/llvm/Analysis/TargetTransformInfoImpl.h +++ b/include/llvm/Analysis/TargetTransformInfoImpl.h @@ -164,6 +164,8 @@ public: bool hasBranchDivergence() { return false; } + bool isSourceOfDivergence(const Value *V) { return false; } + bool isLoweredToCall(const Function *F) { // FIXME: These should almost certainly not be handled here, and instead // handled with the help of TLI or the target itself. This was largely @@ -408,7 +410,7 @@ public: ->getGEPCost(GEP->getPointerOperand(), Indices); } - if (ImmutableCallSite CS = U) { + if (auto CS = ImmutableCallSite(U)) { const Function *F = CS.getCalledFunction(); if (!F) { // Just use the called value type. |