summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTom Stellard <thomas.stellard@amd.com>2014-04-11 19:35:39 +0000
committerTom Stellard <thomas.stellard@amd.com>2014-04-11 19:35:39 +0000
commit27894bd32b80567c763f42817daf1cc65c346b57 (patch)
treefe46a6931c396976846c53fe9758d4e38e6dfa65
parentffb9f967d83cf680eb1bfea1fdd995ccef34223e (diff)
downloadllvm-27894bd32b80567c763f42817daf1cc65c346b57.tar.gz
llvm-27894bd32b80567c763f42817daf1cc65c346b57.tar.bz2
llvm-27894bd32b80567c763f42817daf1cc65c346b57.tar.xz
Merging r198400:
------------------------------------------------------------------------ r198400 | aschwaighofer | 2014-01-03 00:47:03 -0500 (Fri, 03 Jan 2014) | 18 lines BasicAA: Use reachabilty instead of dominance for checking value equality in phi cycles This allows the value equality check to work even if we don't have a dominator tree. Also add some more comments. I was worried about compile time impacts and did not implement reachability but used the dominance check in the initial patch. The trade-off was that the dominator tree was required. The llvm utility function isPotentiallyReachable cuts off the recursive search after 32 visits. Testing did not show any compile time regressions showing my worries unjustfied. No compile time or performance regressions at O3 -flto -mavx on test-suite + externals. Addresses review comments from r198290. ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_34@206052 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--lib/Analysis/BasicAliasAnalysis.cpp63
-rw-r--r--test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll2
-rw-r--r--test/Analysis/BasicAA/phi-aa.ll7
-rw-r--r--test/Analysis/BasicAA/phi-spec-order.ll2
-rw-r--r--test/Analysis/GlobalsModRef/aliastest.ll2
-rw-r--r--test/Transforms/ObjCARC/weak-copies.ll2
-rw-r--r--test/Transforms/ObjCARC/weak-dce.ll2
7 files changed, 40 insertions, 40 deletions
diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 14268ec391..f1a9dd991c 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -18,8 +18,10 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
@@ -41,9 +43,9 @@ 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;
+/// careful with value equivalence. We use reachability to make sure a value
+/// cannot be involved in a cycle.
+const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
//===----------------------------------------------------------------------===//
// Useful predicates
@@ -453,7 +455,6 @@ 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.");
@@ -522,16 +523,14 @@ namespace {
// 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);
+ /// all visited phi nodes an making sure that the phis cannot reach the
+ /// value. We have to do this because we are looking through phi nodes (That
+ /// is we say noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
+ bool isValueEqualInPotentialCycles(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
@@ -1196,7 +1195,13 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,
V2 = V2->stripPointerCasts();
// Are we checking for alias of the same value?
- if (isValueEqual(V1, V2)) return MustAlias;
+ // Because we look 'through' phi nodes we could look at "Value" pointers from
+ // different iterations. We must therefore make sure that this is not the
+ // case. The function isValueEqualInPotentialCycles ensures that this cannot
+ // happen by looking at the visited phi nodes and making sure they cannot
+ // reach the value.
+ if (isValueEqualInPotentialCycles(V1, V2))
+ return MustAlias;
if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
return NoAlias; // Scalars cannot alias each other
@@ -1317,7 +1322,8 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,
return AliasCache[Locs] = Result;
}
-bool BasicAliasAnalysis::isValueEqual(const Value *V, const Value *V2) {
+bool BasicAliasAnalysis::isValueEqualInPotentialCycles(const Value *V,
+ const Value *V2) {
if (V != V2)
return false;
@@ -1325,23 +1331,23 @@ bool BasicAliasAnalysis::isValueEqual(const Value *V, const Value *V2) {
if (!Inst)
return true;
- // Use the dominance if available.
- DT = getAnalysisIfAvailable<DominatorTree>();
- if (DT) {
- if (VisitedPhiBBs.size() > MaxNumPhiBBsValueDominanceCheck)
- return false;
+ if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
+ 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;
- }
+ // Use dominance or loop info if available.
+ DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>();
+ LoopInfo *LI = getAnalysisIfAvailable<LoopInfo>();
+
+ // Make sure that the visited phis cannot reach the Value. This ensures that
+ // the Values cannot come from different iterations of a potential cycle the
+ // phi nodes could be involved in.
+ for (SmallPtrSet<const BasicBlock *, 8>::iterator PI = VisitedPhiBBs.begin(),
+ PE = VisitedPhiBBs.end();
+ PI != PE; ++PI)
+ if (isPotentiallyReachable((*PI)->begin(), Inst, DT, LI))
+ return false;
- return false;
+ return true;
}
/// GetIndexDifference - Dest and Src are the variable indices from two
@@ -1362,7 +1368,8 @@ void BasicAliasAnalysis::GetIndexDifference(
// 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)
+ if (!isValueEqualInPotentialCycles(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
diff --git a/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll b/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll
index c6a9cd9a10..06a804c392 100644
--- a/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll
+++ b/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -domtree -basicaa -aa-eval -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -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/test/Analysis/BasicAA/phi-aa.ll b/test/Analysis/BasicAA/phi-aa.ll
index ed2d23e3ad..74279e1c4c 100644
--- a/test/Analysis/BasicAA/phi-aa.ll
+++ b/test/Analysis/BasicAA/phi-aa.ll
@@ -1,5 +1,4 @@
; 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"
@@ -12,9 +11,6 @@ target triple = "x86_64-unknown-linux-gnu"
; 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
@@ -44,9 +40,6 @@ return:
; 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
diff --git a/test/Analysis/BasicAA/phi-spec-order.ll b/test/Analysis/BasicAA/phi-spec-order.ll
index 3c9fa92363..4172d0963f 100644
--- a/test/Analysis/BasicAA/phi-spec-order.ll
+++ b/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 -domtree -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -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/test/Analysis/GlobalsModRef/aliastest.ll b/test/Analysis/GlobalsModRef/aliastest.ll
index 864c516ec9..4cfed71bfb 100644
--- a/test/Analysis/GlobalsModRef/aliastest.ll
+++ b/test/Analysis/GlobalsModRef/aliastest.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -domtree -basicaa -globalsmodref-aa -gvn -S | FileCheck %s
+; RUN: opt < %s -basicaa -globalsmodref-aa -gvn -S | FileCheck %s
@X = internal global i32 4 ; <i32*> [#uses=1]
diff --git a/test/Transforms/ObjCARC/weak-copies.ll b/test/Transforms/ObjCARC/weak-copies.ll
index 599689bc36..5dab4e049e 100644
--- a/test/Transforms/ObjCARC/weak-copies.ll
+++ b/test/Transforms/ObjCARC/weak-copies.ll
@@ -1,4 +1,4 @@
-; RUN: opt -S -domtree -basicaa -objc-arc < %s | FileCheck %s
+; RUN: opt -S -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/test/Transforms/ObjCARC/weak-dce.ll b/test/Transforms/ObjCARC/weak-dce.ll
index 787fb905fd..f09467182b 100644
--- a/test/Transforms/ObjCARC/weak-dce.ll
+++ b/test/Transforms/ObjCARC/weak-dce.ll
@@ -1,4 +1,4 @@
-; RUN: opt -S -domtree -basicaa -objc-arc < %s | FileCheck %s
+; RUN: opt -S -basicaa -objc-arc < %s | FileCheck %s
; rdar://11434915
; Delete the weak calls and replace them with just the net retain.