diff options
author | Tom Stellard <thomas.stellard@amd.com> | 2014-04-11 19:35:37 +0000 |
---|---|---|
committer | Tom Stellard <thomas.stellard@amd.com> | 2014-04-11 19:35:37 +0000 |
commit | 2840a1c0f3047fd881c930156ddd1c5a435c824c (patch) | |
tree | 15ca11075f5d3c8aed0e0388c154cb3c1a1ba3f3 | |
parent | 16004dc2c5d280d1ab72bab3304ebd07a7e66a6f (diff) | |
download | llvm-2840a1c0f3047fd881c930156ddd1c5a435c824c.zip llvm-2840a1c0f3047fd881c930156ddd1c5a435c824c.tar.gz llvm-2840a1c0f3047fd881c930156ddd1c5a435c824c.tar.bz2 |
Merging r198290:
------------------------------------------------------------------------
r198290 | aschwaighofer | 2014-01-01 22:31:36 -0500 (Wed, 01 Jan 2014) | 23 lines
BasicAA: Fix value equality and phi cycles
When there are cycles in the value graph we have to be careful interpreting
"Value*" identity as "value" equivalence. We interpret the value of a phi node
as the value of its operands.
When we check for value equivalence now we make sure that the "Value*" dominates
all cycles (phis).
%0 = phi [%noaliasval, %addr2]
%l = load %ptr
%addr1 = gep @a, 0, %l
%addr2 = gep @a, 0, (%l + 1)
store %ptr ...
Before this patch we would return NoAlias for (%0, %addr1) which is wrong
because the value of the load is from different iterations of the loop.
Tested on x86_64 -mavx at O3 and O3 -flto with no performance or compile time
regressions.
PR18068
radar://15653794
------------------------------------------------------------------------
llvm-svn: 206051
-rw-r--r-- | llvm/lib/Analysis/BasicAliasAnalysis.cpp | 149 | ||||
-rw-r--r-- | llvm/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll | 2 | ||||
-rw-r--r-- | llvm/test/Analysis/BasicAA/phi-aa.ll | 54 | ||||
-rw-r--r-- | llvm/test/Analysis/BasicAA/phi-spec-order.ll | 2 | ||||
-rw-r--r-- | llvm/test/Analysis/GlobalsModRef/aliastest.ll | 2 | ||||
-rw-r--r-- | llvm/test/Transforms/ObjCARC/weak-copies.ll | 2 | ||||
-rw-r--r-- | llvm/test/Transforms/ObjCARC/weak-dce.ll | 2 | ||||
-rwxr-xr-x | llvm/utils/release/test-release.sh | 35 |
8 files changed, 204 insertions, 44 deletions
diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index b2c2011..14268ec 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -18,6 +18,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ValueTracking.h" @@ -38,6 +39,12 @@ #include <algorithm> using namespace llvm; +/// Cutoff after which to stop analysing a set of phi nodes potentially involved +/// in a cycle. Because we are analysing 'through' phi nodes we need to be +/// careful with value equivalence. We use dominance to make sure a value cannot +/// be involved in a cycle. +const unsigned MaxNumPhiBBsValueDominanceCheck = 20; + //===----------------------------------------------------------------------===// // Useful predicates //===----------------------------------------------------------------------===// @@ -403,42 +410,6 @@ DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, return V; } -/// GetIndexDifference - Dest and Src are the variable indices from two -/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base -/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic -/// difference between the two pointers. -static void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, - const SmallVectorImpl<VariableGEPIndex> &Src) { - if (Src.empty()) return; - - for (unsigned i = 0, e = Src.size(); i != e; ++i) { - const Value *V = Src[i].V; - ExtensionKind Extension = Src[i].Extension; - int64_t Scale = Src[i].Scale; - - // Find V in Dest. This is N^2, but pointer indices almost never have more - // than a few variable indexes. - for (unsigned j = 0, e = Dest.size(); j != e; ++j) { - if (Dest[j].V != V || Dest[j].Extension != Extension) continue; - - // If we found it, subtract off Scale V's from the entry in Dest. If it - // goes to zero, remove the entry. - if (Dest[j].Scale != Scale) - Dest[j].Scale -= Scale; - else - Dest.erase(Dest.begin()+j); - Scale = 0; - break; - } - - // If we didn't consume this entry, add it to the end of the Dest list. - if (Scale) { - VariableGEPIndex Entry = { V, Extension, -Scale }; - Dest.push_back(Entry); - } - } -} - //===----------------------------------------------------------------------===// // BasicAliasAnalysis Pass //===----------------------------------------------------------------------===// @@ -482,6 +453,7 @@ namespace { virtual AliasResult alias(const Location &LocA, const Location &LocB) { + DT = 0; assert(AliasCache.empty() && "AliasCache must be cleared after use!"); assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && "BasicAliasAnalysis doesn't support interprocedural queries."); @@ -492,6 +464,7 @@ namespace { // SmallDenseMap if it ever grows larger. // FIXME: This should really be shrink_to_inline_capacity_and_clear(). AliasCache.shrink_and_clear(); + VisitedPhiBBs.clear(); return Alias; } @@ -532,9 +505,41 @@ namespace { typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy; AliasCacheTy AliasCache; + /// \brief Track phi nodes we have visited. When interpret "Value" pointer + /// equality as value equality we need to make sure that the "Value" is not + /// part of a cycle. Otherwise, two uses could come from different + /// "iterations" of a cycle and see different values for the same "Value" + /// pointer. + /// The following example shows the problem: + /// %p = phi(%alloca1, %addr2) + /// %l = load %ptr + /// %addr1 = gep, %alloca2, 0, %l + /// %addr2 = gep %alloca2, 0, (%l + 1) + /// alias(%p, %addr1) -> MayAlias ! + /// store %l, ... + SmallPtrSet<const BasicBlock*, 8> VisitedPhiBBs; + // Visited - Track instructions visited by pointsToConstantMemory. SmallPtrSet<const Value*, 16> Visited; + // We use the dominator tree to check values can't be part of a cycle. + DominatorTree *DT; + + /// \brief Check whether two Values can be considered equivalent. + /// + /// In addition to pointer equivalence of \p V1 and \p V2 this checks + /// whether they can not be part of a cycle in the value graph by looking at + /// all visited phi nodes an making sure that the value dominates all of + /// them. + bool isValueEqual(const Value *V1, const Value *V2); + + /// \brief Dest and Src are the variable indices from two decomposed + /// GetElementPtr instructions GEP1 and GEP2 which have common base + /// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic + /// difference between the two pointers. + void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, + const SmallVectorImpl<VariableGEPIndex> &Src); + // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP // instruction against another. AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size, @@ -1094,6 +1099,10 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, const MDNode *PNTBAAInfo, const Value *V2, uint64_t V2Size, const MDNode *V2TBAAInfo) { + // Track phi nodes we have visited. We use this information when we determine + // value equivalence. + VisitedPhiBBs.insert(PN->getParent()); + // If the values are PHIs in the same block, we can do a more precise // as well as efficient check: just check for aliases between the values // on corresponding edges. @@ -1187,7 +1196,7 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, V2 = V2->stripPointerCasts(); // Are we checking for alias of the same value? - if (V1 == V2) return MustAlias; + if (isValueEqual(V1, V2)) return MustAlias; if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) return NoAlias; // Scalars cannot alias each other @@ -1307,3 +1316,69 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, Location(V2, V2Size, V2TBAAInfo)); return AliasCache[Locs] = Result; } + +bool BasicAliasAnalysis::isValueEqual(const Value *V, const Value *V2) { + if (V != V2) + return false; + + const Instruction *Inst = dyn_cast<Instruction>(V); + if (!Inst) + return true; + + // Use the dominance if available. + DT = getAnalysisIfAvailable<DominatorTree>(); + if (DT) { + if (VisitedPhiBBs.size() > MaxNumPhiBBsValueDominanceCheck) + return false; + + // Make sure that the visited phis are dominated by the Value. + for (SmallPtrSet<const BasicBlock *, 8>::iterator + PI = VisitedPhiBBs.begin(), + PE = VisitedPhiBBs.end(); + PI != PE; ++PI) + if (!DT->dominates(Inst, *PI)) + return false; + return true; + } + + return false; +} + +/// GetIndexDifference - Dest and Src are the variable indices from two +/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base +/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic +/// difference between the two pointers. +void BasicAliasAnalysis::GetIndexDifference( + SmallVectorImpl<VariableGEPIndex> &Dest, + const SmallVectorImpl<VariableGEPIndex> &Src) { + if (Src.empty()) + return; + + for (unsigned i = 0, e = Src.size(); i != e; ++i) { + const Value *V = Src[i].V; + ExtensionKind Extension = Src[i].Extension; + int64_t Scale = Src[i].Scale; + + // Find V in Dest. This is N^2, but pointer indices almost never have more + // than a few variable indexes. + for (unsigned j = 0, e = Dest.size(); j != e; ++j) { + if (!isValueEqual(Dest[j].V, V) || Dest[j].Extension != Extension) + continue; + + // If we found it, subtract off Scale V's from the entry in Dest. If it + // goes to zero, remove the entry. + if (Dest[j].Scale != Scale) + Dest[j].Scale -= Scale; + else + Dest.erase(Dest.begin() + j); + Scale = 0; + break; + } + + // If we didn't consume this entry, add it to the end of the Dest list. + if (Scale) { + VariableGEPIndex Entry = { V, Extension, -Scale }; + Dest.push_back(Entry); + } + } +} diff --git a/llvm/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll b/llvm/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll index 06a804c..c6a9cd9 100644 --- a/llvm/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll +++ b/llvm/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -basicaa -aa-eval -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -domtree -basicaa -aa-eval -disable-output 2>&1 | FileCheck %s ; TEST that A[1][0] may alias A[0][i]. target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128" diff --git a/llvm/test/Analysis/BasicAA/phi-aa.ll b/llvm/test/Analysis/BasicAA/phi-aa.ll index 6aa26c1..ed2d23e 100644 --- a/llvm/test/Analysis/BasicAA/phi-aa.ll +++ b/llvm/test/Analysis/BasicAA/phi-aa.ll @@ -1,12 +1,20 @@ ; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -domtree -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s --check-prefix=DOM +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + ; rdar://7282591 @X = common global i32 0 @Y = common global i32 0 @Z = common global i32 0 +; CHECK-LABEL: foo ; CHECK: NoAlias: i32* %P, i32* @Z +; DOM-LABEL: foo +; DOM: NoAlias: i32* %P, i32* @Z + define void @foo(i32 %cond) nounwind { entry: %"alloca point" = bitcast i32 0 to i32 @@ -29,3 +37,49 @@ bb2: return: ret void } + +; Pointers can vary in between iterations of loops. +; PR18068 + +; CHECK-LABEL: pr18068 +; CHECK: MayAlias: i32* %0, i32* %arrayidx5 + +; DOM-LABEL: pr18068 +; DOM: MayAlias: i32* %0, i32* %arrayidx5 + +define i32 @pr18068(i32* %jj7, i32* %j) { +entry: + %oa5 = alloca [100 x i32], align 16 + br label %codeRepl + +codeRepl: + %0 = phi i32* [ %arrayidx13, %for.body ], [ %j, %entry ] + %targetBlock = call i1 @cond(i32* %jj7) + br i1 %targetBlock, label %for.body, label %bye + +for.body: + %1 = load i32* %jj7, align 4 + %idxprom4 = zext i32 %1 to i64 + %arrayidx5 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom4 + %2 = load i32* %arrayidx5, align 4 + %sub6 = sub i32 %2, 6 + store i32 %sub6, i32* %arrayidx5, align 4 + ; %0 and %arrayidx5 can alias! It is not safe to DSE the above store. + %3 = load i32* %0, align 4 + store i32 %3, i32* %arrayidx5, align 4 + %sub11 = add i32 %1, -1 + %idxprom12 = zext i32 %sub11 to i64 + %arrayidx13 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom12 + call void @inc(i32* %jj7) + br label %codeRepl + +bye: + %.reload = load i32* %jj7, align 4 + ret i32 %.reload +} + +declare i1 @cond(i32*) + +declare void @inc(i32*) + + diff --git a/llvm/test/Analysis/BasicAA/phi-spec-order.ll b/llvm/test/Analysis/BasicAA/phi-spec-order.ll index 4172d09..3c9fa923 100644 --- a/llvm/test/Analysis/BasicAA/phi-spec-order.ll +++ b/llvm/test/Analysis/BasicAA/phi-spec-order.ll @@ -1,6 +1,6 @@ target datalayout = "E-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-f128:128:128-v128:128:128-n32:64" target triple = "powerpc64-bgq-linux" -; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -domtree -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s @X = external global [16000 x double], align 32 @Y = external global [16000 x double], align 32 diff --git a/llvm/test/Analysis/GlobalsModRef/aliastest.ll b/llvm/test/Analysis/GlobalsModRef/aliastest.ll index 4cfed71..864c516 100644 --- a/llvm/test/Analysis/GlobalsModRef/aliastest.ll +++ b/llvm/test/Analysis/GlobalsModRef/aliastest.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -basicaa -globalsmodref-aa -gvn -S | FileCheck %s +; RUN: opt < %s -domtree -basicaa -globalsmodref-aa -gvn -S | FileCheck %s @X = internal global i32 4 ; <i32*> [#uses=1] diff --git a/llvm/test/Transforms/ObjCARC/weak-copies.ll b/llvm/test/Transforms/ObjCARC/weak-copies.ll index 5dab4e0..599689b 100644 --- a/llvm/test/Transforms/ObjCARC/weak-copies.ll +++ b/llvm/test/Transforms/ObjCARC/weak-copies.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -basicaa -objc-arc < %s | FileCheck %s +; RUN: opt -S -domtree -basicaa -objc-arc < %s | FileCheck %s target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" target triple = "x86_64-apple-darwin11.0.0" diff --git a/llvm/test/Transforms/ObjCARC/weak-dce.ll b/llvm/test/Transforms/ObjCARC/weak-dce.ll index f094671..787fb90 100644 --- a/llvm/test/Transforms/ObjCARC/weak-dce.ll +++ b/llvm/test/Transforms/ObjCARC/weak-dce.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -basicaa -objc-arc < %s | FileCheck %s +; RUN: opt -S -domtree -basicaa -objc-arc < %s | FileCheck %s ; rdar://11434915 ; Delete the weak calls and replace them with just the net retain. diff --git a/llvm/utils/release/test-release.sh b/llvm/utils/release/test-release.sh index 91dac4c..90c5f1a 100755 --- a/llvm/utils/release/test-release.sh +++ b/llvm/utils/release/test-release.sh @@ -26,6 +26,7 @@ Base_url="http://llvm.org/svn/llvm-project" Release="" Release_no_dot="" RC="" +DOT="" Triple="" use_gzip="no" do_checkout="yes" @@ -45,6 +46,7 @@ function usage() { echo "" echo " -release X.Y The release number to test." echo " -rc NUM The pre-release candidate number." + echo " -dot NUM The dot release to test e.g. X.Y.DOT_NUM [default: 0]" echo " -final The final release candidate." echo " -triple TRIPLE The target triple for this machine." echo " -j NUM Number of compile jobs to run. [default: 3]" @@ -76,6 +78,13 @@ while [ $# -gt 0 ]; do -final | --final ) RC=final ;; + -dot | --dot ) + shift + DOT="$1" + if [ $DOT -eq 0 ]; then + DOT="" + fi + ;; -triple | --triple ) shift Triple="$1" @@ -137,6 +146,10 @@ while [ $# -gt 0 ]; do shift done +if [ -n "$DOT" ]; then + Release="$Release.$DOT" +fi + # Check required arguments. if [ -z "$Release" ]; then echo "error: no release number specified" @@ -217,12 +230,29 @@ if [ `uname -s` != "Darwin" ]; then check_program_exists 'objdump' fi +function get_svn_tag() { + case $1 in + # llvm and clang are the only projects currently doing dot releases. + llvm | cfe) + if [ -z $DOT ]; then + SvnTag="$RC" + else + SvnTag="dot$DOT-$RC" + fi + ;; + *) + SvnTag="$RC" + ;; + esac +} + # Make sure that the URLs are valid. function check_valid_urls() { for proj in $projects ; do echo "# Validating $proj SVN URL" - if ! svn ls $Base_url/$proj/tags/RELEASE_$Release_no_dot/$RC > /dev/null 2>&1 ; then + get_svn_tag "$proj" + if ! svn ls $Base_url/$proj/tags/RELEASE_$Release_no_dot/$SvnTag > /dev/null 2>&1 ; then echo "llvm $Release release candidate $RC doesn't exist!" exit 1 fi @@ -235,7 +265,8 @@ function export_sources() { for proj in $projects ; do echo "# Exporting $proj $Release-RC$RC sources" - if ! svn export -q $Base_url/$proj/tags/RELEASE_$Release_no_dot/$RC $proj.src ; then + get_svn_tag "$proj" + if ! svn export -q $Base_url/$proj/tags/RELEASE_$Release_no_dot/$SvnTag $proj.src ; then echo "error: failed to export $proj project" exit 1 fi |