From e3094283e38d9e6f6a4a7a14a3a5d0f2af67d5d5 Mon Sep 17 00:00:00 2001 From: Nuno Lopes Date: Wed, 25 Jul 2012 17:29:22 +0000 Subject: MemoryBuiltins: add support to determine the size of strdup'ed non-constant strings git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160742 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/MemoryBuiltins.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index e674e74..7684082 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -201,6 +201,7 @@ class ObjectSizeOffsetEvaluator typedef SmallPtrSet PtrSetTy; const TargetData *TD; + const TargetLibraryInfo *TLI; LLVMContext &Context; BuilderTy Builder; ObjectSizeOffsetVisitor Visitor; @@ -215,7 +216,8 @@ class ObjectSizeOffsetEvaluator SizeOffsetEvalType compute_(Value *V); public: - ObjectSizeOffsetEvaluator(const TargetData *TD, LLVMContext &Context); + ObjectSizeOffsetEvaluator(const TargetData *TD, const TargetLibraryInfo *TLI, + LLVMContext &Context); SizeOffsetEvalType compute(Value *V); bool knownSize(SizeOffsetEvalType SizeOffset) { -- cgit v1.1 From 6e699bf38dd862331532bd6f74ec491bdfad5db9 Mon Sep 17 00:00:00 2001 From: Nuno Lopes Date: Wed, 25 Jul 2012 18:49:28 +0000 Subject: revert r160742: it's breaking CMake build original commit msg: MemoryBuiltins: add support to determine the size of strdup'ed non-constant strings git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160751 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/MemoryBuiltins.h | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index 7684082..e674e74 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -201,7 +201,6 @@ class ObjectSizeOffsetEvaluator typedef SmallPtrSet PtrSetTy; const TargetData *TD; - const TargetLibraryInfo *TLI; LLVMContext &Context; BuilderTy Builder; ObjectSizeOffsetVisitor Visitor; @@ -216,8 +215,7 @@ class ObjectSizeOffsetEvaluator SizeOffsetEvalType compute_(Value *V); public: - ObjectSizeOffsetEvaluator(const TargetData *TD, const TargetLibraryInfo *TLI, - LLVMContext &Context); + ObjectSizeOffsetEvaluator(const TargetData *TD, LLVMContext &Context); SizeOffsetEvalType compute(Value *V); bool knownSize(SizeOffsetEvalType SizeOffset) { -- cgit v1.1 From f63f8834250e5bd50b1cc5b2649acdf42988abad Mon Sep 17 00:00:00 2001 From: Hongbin Zheng Date: Thu, 2 Aug 2012 14:20:02 +0000 Subject: Implement the block_iterator of Region based on df_iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161177 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/RegionInfo.h | 72 +++++++++++++++++++++----------------- 1 file changed, 40 insertions(+), 32 deletions(-) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index eae94e7..c76a8a7 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -500,50 +500,58 @@ public: /// Region. The iterator also iterates over BasicBlocks that are elements of /// a subregion of this Region. It is therefore called a flat iterator. //@{ - template + template class block_iterator_wrapper - : public std::iterator { - typedef std::iterator + : public df_iterator::type*> { + typedef df_iterator::type*> super; - - RegionNodeItT Iter; - public: - typedef block_iterator_wrapper Self; + typedef block_iterator_wrapper Self; typedef typename super::pointer pointer; - block_iterator_wrapper(RegionNodeItT Iter) : Iter(Iter) {} - - bool operator==(const Self &RHS) const { return Iter == RHS.Iter; } - bool operator!=(const Self &RHS) const { return Iter != RHS.Iter; } - pointer operator*() const { - return (*Iter)->template getNodeAs(); + // Construct the begin iterator. + block_iterator_wrapper(pointer Entry, pointer Exit) : super(df_begin(Entry)) + { + // Mark the exit of the region as visited, so that the children of the + // exit and the exit itself, i.e. the block outside the region will never + // be visited. + super::Visited.insert(Exit); } - Self& operator++() { - ++Iter; - return *this; - } - Self operator++(int) { - Self tmp = *this; - ++*this; - return tmp; - } + // Construct the end iterator. + block_iterator_wrapper() : super(df_end(0)) {} + + /*implicit*/ block_iterator_wrapper(super I) : super(I) {} - const Self &operator=(const Self &I) { - Iter = I.Iter; - return *this; + // FIXME: Even a const_iterator returns a non-const BasicBlock pointer. + // This was introduced for backwards compatibility, but should + // be removed as soon as all users are fixed. + BasicBlock *operator*() const { + return const_cast(super::operator*()); } }; - typedef block_iterator_wrapper block_iterator; - typedef block_iterator_wrapper - const_block_iterator; - block_iterator block_begin(); - block_iterator block_end(); + typedef block_iterator_wrapper block_iterator; + typedef block_iterator_wrapper const_block_iterator; - const_block_iterator block_begin() const; - const_block_iterator block_end() const; + block_iterator block_begin() { + return block_iterator(getEntry(), getExit()); + } + + block_iterator block_end() { + return block_iterator(); + } + + const_block_iterator block_begin() const { + return const_block_iterator(getEntry(), getExit()); + } + const_block_iterator block_end() const { + return const_block_iterator(); + } //@} /// @name Element Iterators -- cgit v1.1 From 5258d9f96767d898af4756930ce0c66a31ddf7d9 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Thu, 2 Aug 2012 14:44:01 +0000 Subject: include/llvm/Analysis/RegionInfo.h: Appease msvc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161179 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/RegionInfo.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index c76a8a7..188d11c 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -523,7 +523,7 @@ public: } // Construct the end iterator. - block_iterator_wrapper() : super(df_end(0)) {} + block_iterator_wrapper() : super(df_end((BasicBlock *)0)) {} /*implicit*/ block_iterator_wrapper(super I) : super(I) {} -- cgit v1.1 From 702bcce747cd3fd89049b16d37c9c88952b5af81 Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Tue, 7 Aug 2012 17:30:46 +0000 Subject: The dominance computation already has logic for computing if an edge dominates a use or a BB, but it is inline in the handling of the invoke instruction. This patch refactors it so that it can be used in other cases. For example, in define i32 @f(i32 %x) { bb0: %cmp = icmp eq i32 %x, 0 br i1 %cmp, label %bb2, label %bb1 bb1: br label %bb2 bb2: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] %foo = add i32 %cond, %x ret i32 %foo } GVN should be able to replace %x with 0 in any use that is dominated by the true edge out of bb0. In the above example the only such use is the one in the phi. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161429 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/Dominators.h | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 45be59b..25fb363 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -705,6 +705,20 @@ DominatorTreeBase::properlyDominates(const NodeT *A, const NodeT *B) { EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase); +class BasicBlockEdge { + const BasicBlock *Start; + const BasicBlock *End; +public: + BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : + Start(Start_), End(End_) { } + const BasicBlock *getStart() const { + return Start; + } + const BasicBlock *getEnd() const { + return End; + } +}; + //===------------------------------------- /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to /// compute a normal dominator tree. @@ -778,6 +792,8 @@ public: bool dominates(const Instruction *Def, const Use &U) const; bool dominates(const Instruction *Def, const Instruction *User) const; bool dominates(const Instruction *Def, const BasicBlock *BB) const; + bool dominates(const BasicBlockEdge &BBE, const Use &U) const; + bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const { return DT->properlyDominates(A, B); -- cgit v1.1 From 25ac7518ffda5f4256e8333dde4801270bb26418 Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Fri, 10 Aug 2012 14:05:55 +0000 Subject: Move BasicBlockEdge to the cpp file. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161663 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/Dominators.h | 14 +------------- 1 file changed, 1 insertion(+), 13 deletions(-) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 25fb363..1289edd 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -705,19 +705,7 @@ DominatorTreeBase::properlyDominates(const NodeT *A, const NodeT *B) { EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase); -class BasicBlockEdge { - const BasicBlock *Start; - const BasicBlock *End; -public: - BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : - Start(Start_), End(End_) { } - const BasicBlock *getStart() const { - return Start; - } - const BasicBlock *getEnd() const { - return End; - } -}; +class BasicBlockEdge; //===------------------------------------- /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to -- cgit v1.1 From a3a3219b3a972db6449548abf7e0c9112e8ce7b9 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Mon, 13 Aug 2012 15:29:53 +0000 Subject: Fix a documentation typo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161758 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/MemoryDependenceAnalysis.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index 81ad3f0..7e049d6 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -124,11 +124,11 @@ namespace llvm { } /// isClobber - Return true if this MemDepResult represents a query that is - /// a instruction clobber dependency. + /// an instruction clobber dependency. bool isClobber() const { return Value.getInt() == Clobber; } /// isDef - Return true if this MemDepResult represents a query that is - /// a instruction definition dependency. + /// an instruction definition dependency. bool isDef() const { return Value.getInt() == Def; } /// isNonLocal - Return true if this MemDepResult represents a query that -- cgit v1.1 From 0c34ae88bfe6ab40fc30784f131510992438ea43 Mon Sep 17 00:00:00 2001 From: Bill Wendling Date: Wed, 15 Aug 2012 12:22:35 +0000 Subject: Set the branch probability of branching to the 'normal' destination of an invoke instruction to something absurdly high, while setting the probability of branching to the 'unwind' destination to the bare minimum. This should set cause the normal destination's invoke blocks to be moved closer to the invoke. PR13612 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161944 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/BranchProbabilityInfo.h | 1 + 1 file changed, 1 insertion(+) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 2ced796..006daa0 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -122,6 +122,7 @@ private: bool calcLoopBranchHeuristics(BasicBlock *BB); bool calcZeroHeuristics(BasicBlock *BB); bool calcFloatingPointHeuristics(BasicBlock *BB); + bool calcInvokeHeuristics(BasicBlock *BB); }; } -- cgit v1.1 From 05130597262f3ed00dc4881d64795d117c76e3fc Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Thu, 16 Aug 2012 15:09:43 +0000 Subject: Teach GVN to reason about edges dominating uses. This allows it to handle cases where some fact lake a=b dominates a use in a phi, but doesn't dominate the basic block itself. This feature could also be implemented by splitting critical edges, but at least with the current algorithm reasoning about the dominance directly is faster. The time for running "opt -O2" in the testcase in pr10584 is 1.003 times slower and on gcc as a single file it is 1.0007 times faster. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162023 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/Dominators.h | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 1289edd..a1cc196 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -705,7 +705,20 @@ DominatorTreeBase::properlyDominates(const NodeT *A, const NodeT *B) { EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase); -class BasicBlockEdge; +class BasicBlockEdge { + const BasicBlock *Start; + const BasicBlock *End; +public: + BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : + Start(Start_), End(End_) { } + const BasicBlock *getStart() const { + return Start; + } + const BasicBlock *getEnd() const { + return End; + } + bool isSingleEdge() const; +}; //===------------------------------------- /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to -- cgit v1.1 From 168843c0137ad67c24a3930244a9c5f60add320d Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Fri, 17 Aug 2012 19:26:41 +0000 Subject: MemoryBuiltins: Properly guard ObjectSizeOffsetVisitor against cycles in the IR. The previous fix only checked for simple cycles, use a set to catch longer cycles too. Drop the broken check from the ObjectSizeOffsetEvaluator. The BoundsChecking pass doesn't have to deal with invalid IR like InstCombine does. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162120 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/MemoryBuiltins.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/llvm/Analysis') diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index e674e74..e16f389 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -146,6 +146,7 @@ class ObjectSizeOffsetVisitor bool RoundToAlign; unsigned IntTyBits; APInt Zero; + SmallPtrSet SeenInsts; APInt align(APInt Size, uint64_t Align); @@ -203,7 +204,6 @@ class ObjectSizeOffsetEvaluator const TargetData *TD; LLVMContext &Context; BuilderTy Builder; - ObjectSizeOffsetVisitor Visitor; IntegerType *IntTy; Value *Zero; CacheMapTy CacheMap; -- cgit v1.1