Skip to content

Commit 0d10a9d

Browse files
aschwaighoferaschwaighofer
committedJan 2, 2014
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: 198290
1 parent 1878762 commit 0d10a9d

File tree

7 files changed

+171
-42
lines changed

7 files changed

+171
-42
lines changed
 

‎llvm/lib/Analysis/BasicAliasAnalysis.cpp

+112-37
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818
#include "llvm/ADT/SmallVector.h"
1919
#include "llvm/Analysis/AliasAnalysis.h"
2020
#include "llvm/Analysis/CaptureTracking.h"
21+
#include "llvm/Analysis/Dominators.h"
2122
#include "llvm/Analysis/InstructionSimplify.h"
2223
#include "llvm/Analysis/MemoryBuiltins.h"
2324
#include "llvm/Analysis/ValueTracking.h"
@@ -38,6 +39,12 @@
3839
#include <algorithm>
3940
using namespace llvm;
4041

42+
/// Cutoff after which to stop analysing a set of phi nodes potentially involved
43+
/// in a cycle. Because we are analysing 'through' phi nodes we need to be
44+
/// careful with value equivalence. We use dominance to make sure a value cannot
45+
/// be involved in a cycle.
46+
const unsigned MaxNumPhiBBsValueDominanceCheck = 20;
47+
4148
//===----------------------------------------------------------------------===//
4249
// Useful predicates
4350
//===----------------------------------------------------------------------===//
@@ -403,42 +410,6 @@ DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
403410
return V;
404411
}
405412

406-
/// GetIndexDifference - Dest and Src are the variable indices from two
407-
/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base
408-
/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic
409-
/// difference between the two pointers.
410-
static void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
411-
const SmallVectorImpl<VariableGEPIndex> &Src) {
412-
if (Src.empty()) return;
413-
414-
for (unsigned i = 0, e = Src.size(); i != e; ++i) {
415-
const Value *V = Src[i].V;
416-
ExtensionKind Extension = Src[i].Extension;
417-
int64_t Scale = Src[i].Scale;
418-
419-
// Find V in Dest. This is N^2, but pointer indices almost never have more
420-
// than a few variable indexes.
421-
for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
422-
if (Dest[j].V != V || Dest[j].Extension != Extension) continue;
423-
424-
// If we found it, subtract off Scale V's from the entry in Dest. If it
425-
// goes to zero, remove the entry.
426-
if (Dest[j].Scale != Scale)
427-
Dest[j].Scale -= Scale;
428-
else
429-
Dest.erase(Dest.begin()+j);
430-
Scale = 0;
431-
break;
432-
}
433-
434-
// If we didn't consume this entry, add it to the end of the Dest list.
435-
if (Scale) {
436-
VariableGEPIndex Entry = { V, Extension, -Scale };
437-
Dest.push_back(Entry);
438-
}
439-
}
440-
}
441-
442413
//===----------------------------------------------------------------------===//
443414
// BasicAliasAnalysis Pass
444415
//===----------------------------------------------------------------------===//
@@ -482,6 +453,7 @@ namespace {
482453

483454
virtual AliasResult alias(const Location &LocA,
484455
const Location &LocB) {
456+
DT = 0;
485457
assert(AliasCache.empty() && "AliasCache must be cleared after use!");
486458
assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
487459
"BasicAliasAnalysis doesn't support interprocedural queries.");
@@ -492,6 +464,7 @@ namespace {
492464
// SmallDenseMap if it ever grows larger.
493465
// FIXME: This should really be shrink_to_inline_capacity_and_clear().
494466
AliasCache.shrink_and_clear();
467+
VisitedPhiBBs.clear();
495468
return Alias;
496469
}
497470

@@ -532,9 +505,41 @@ namespace {
532505
typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
533506
AliasCacheTy AliasCache;
534507

508+
/// \brief Track phi nodes we have visited. When interpret "Value" pointer
509+
/// equality as value equality we need to make sure that the "Value" is not
510+
/// part of a cycle. Otherwise, two uses could come from different
511+
/// "iterations" of a cycle and see different values for the same "Value"
512+
/// pointer.
513+
/// The following example shows the problem:
514+
/// %p = phi(%alloca1, %addr2)
515+
/// %l = load %ptr
516+
/// %addr1 = gep, %alloca2, 0, %l
517+
/// %addr2 = gep %alloca2, 0, (%l + 1)
518+
/// alias(%p, %addr1) -> MayAlias !
519+
/// store %l, ...
520+
SmallPtrSet<const BasicBlock*, 8> VisitedPhiBBs;
521+
535522
// Visited - Track instructions visited by pointsToConstantMemory.
536523
SmallPtrSet<const Value*, 16> Visited;
537524

525+
// We use the dominator tree to check values can't be part of a cycle.
526+
DominatorTree *DT;
527+
528+
/// \brief Check whether two Values can be considered equivalent.
529+
///
530+
/// In addition to pointer equivalence of \p V1 and \p V2 this checks
531+
/// whether they can not be part of a cycle in the value graph by looking at
532+
/// all visited phi nodes an making sure that the value dominates all of
533+
/// them.
534+
bool isValueEqual(const Value *V1, const Value *V2);
535+
536+
/// \brief Dest and Src are the variable indices from two decomposed
537+
/// GetElementPtr instructions GEP1 and GEP2 which have common base
538+
/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic
539+
/// difference between the two pointers.
540+
void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
541+
const SmallVectorImpl<VariableGEPIndex> &Src);
542+
538543
// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP
539544
// instruction against another.
540545
AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
@@ -1094,6 +1099,10 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize,
10941099
const MDNode *PNTBAAInfo,
10951100
const Value *V2, uint64_t V2Size,
10961101
const MDNode *V2TBAAInfo) {
1102+
// Track phi nodes we have visited. We use this information when we determine
1103+
// value equivalence.
1104+
VisitedPhiBBs.insert(PN->getParent());
1105+
10971106
// If the values are PHIs in the same block, we can do a more precise
10981107
// as well as efficient check: just check for aliases between the values
10991108
// on corresponding edges.
@@ -1187,7 +1196,7 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,
11871196
V2 = V2->stripPointerCasts();
11881197

11891198
// Are we checking for alias of the same value?
1190-
if (V1 == V2) return MustAlias;
1199+
if (isValueEqual(V1, V2)) return MustAlias;
11911200

11921201
if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
11931202
return NoAlias; // Scalars cannot alias each other
@@ -1307,3 +1316,69 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,
13071316
Location(V2, V2Size, V2TBAAInfo));
13081317
return AliasCache[Locs] = Result;
13091318
}
1319+
1320+
bool BasicAliasAnalysis::isValueEqual(const Value *V, const Value *V2) {
1321+
if (V != V2)
1322+
return false;
1323+
1324+
const Instruction *Inst = dyn_cast<Instruction>(V);
1325+
if (!Inst)
1326+
return true;
1327+
1328+
// Use the dominance if available.
1329+
DT = getAnalysisIfAvailable<DominatorTree>();
1330+
if (DT) {
1331+
if (VisitedPhiBBs.size() > MaxNumPhiBBsValueDominanceCheck)
1332+
return false;
1333+
1334+
// Make sure that the visited phis are dominated by the Value.
1335+
for (SmallPtrSet<const BasicBlock *, 8>::iterator
1336+
PI = VisitedPhiBBs.begin(),
1337+
PE = VisitedPhiBBs.end();
1338+
PI != PE; ++PI)
1339+
if (!DT->dominates(Inst, *PI))
1340+
return false;
1341+
return true;
1342+
}
1343+
1344+
return false;
1345+
}
1346+
1347+
/// GetIndexDifference - Dest and Src are the variable indices from two
1348+
/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base
1349+
/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic
1350+
/// difference between the two pointers.
1351+
void BasicAliasAnalysis::GetIndexDifference(
1352+
SmallVectorImpl<VariableGEPIndex> &Dest,
1353+
const SmallVectorImpl<VariableGEPIndex> &Src) {
1354+
if (Src.empty())
1355+
return;
1356+
1357+
for (unsigned i = 0, e = Src.size(); i != e; ++i) {
1358+
const Value *V = Src[i].V;
1359+
ExtensionKind Extension = Src[i].Extension;
1360+
int64_t Scale = Src[i].Scale;
1361+
1362+
// Find V in Dest. This is N^2, but pointer indices almost never have more
1363+
// than a few variable indexes.
1364+
for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
1365+
if (!isValueEqual(Dest[j].V, V) || Dest[j].Extension != Extension)
1366+
continue;
1367+
1368+
// If we found it, subtract off Scale V's from the entry in Dest. If it
1369+
// goes to zero, remove the entry.
1370+
if (Dest[j].Scale != Scale)
1371+
Dest[j].Scale -= Scale;
1372+
else
1373+
Dest.erase(Dest.begin() + j);
1374+
Scale = 0;
1375+
break;
1376+
}
1377+
1378+
// If we didn't consume this entry, add it to the end of the Dest list.
1379+
if (Scale) {
1380+
VariableGEPIndex Entry = { V, Extension, -Scale };
1381+
Dest.push_back(Entry);
1382+
}
1383+
}
1384+
}

‎llvm/test/Analysis/BasicAA/2006-03-03-BadArraySubscript.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
; RUN: opt < %s -basicaa -aa-eval -disable-output 2>&1 | FileCheck %s
1+
; RUN: opt < %s -domtree -basicaa -aa-eval -disable-output 2>&1 | FileCheck %s
22
; TEST that A[1][0] may alias A[0][i].
33
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"
44

‎llvm/test/Analysis/BasicAA/phi-aa.ll

+54
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,20 @@
11
; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
2+
; RUN: opt < %s -domtree -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s --check-prefix=DOM
3+
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"
4+
target triple = "x86_64-unknown-linux-gnu"
5+
26
; rdar://7282591
37

48
@X = common global i32 0
59
@Y = common global i32 0
610
@Z = common global i32 0
711

12+
; CHECK-LABEL: foo
813
; CHECK: NoAlias: i32* %P, i32* @Z
914

15+
; DOM-LABEL: foo
16+
; DOM: NoAlias: i32* %P, i32* @Z
17+
1018
define void @foo(i32 %cond) nounwind {
1119
entry:
1220
%"alloca point" = bitcast i32 0 to i32
@@ -29,3 +37,49 @@ bb2:
2937
return:
3038
ret void
3139
}
40+
41+
; Pointers can vary in between iterations of loops.
42+
; PR18068
43+
44+
; CHECK-LABEL: pr18068
45+
; CHECK: MayAlias: i32* %0, i32* %arrayidx5
46+
47+
; DOM-LABEL: pr18068
48+
; DOM: MayAlias: i32* %0, i32* %arrayidx5
49+
50+
define i32 @pr18068(i32* %jj7, i32* %j) {
51+
entry:
52+
%oa5 = alloca [100 x i32], align 16
53+
br label %codeRepl
54+
55+
codeRepl:
56+
%0 = phi i32* [ %arrayidx13, %for.body ], [ %j, %entry ]
57+
%targetBlock = call i1 @cond(i32* %jj7)
58+
br i1 %targetBlock, label %for.body, label %bye
59+
60+
for.body:
61+
%1 = load i32* %jj7, align 4
62+
%idxprom4 = zext i32 %1 to i64
63+
%arrayidx5 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom4
64+
%2 = load i32* %arrayidx5, align 4
65+
%sub6 = sub i32 %2, 6
66+
store i32 %sub6, i32* %arrayidx5, align 4
67+
; %0 and %arrayidx5 can alias! It is not safe to DSE the above store.
68+
%3 = load i32* %0, align 4
69+
store i32 %3, i32* %arrayidx5, align 4
70+
%sub11 = add i32 %1, -1
71+
%idxprom12 = zext i32 %sub11 to i64
72+
%arrayidx13 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom12
73+
call void @inc(i32* %jj7)
74+
br label %codeRepl
75+
76+
bye:
77+
%.reload = load i32* %jj7, align 4
78+
ret i32 %.reload
79+
}
80+
81+
declare i1 @cond(i32*)
82+
83+
declare void @inc(i32*)
84+
85+

‎llvm/test/Analysis/BasicAA/phi-spec-order.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
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"
22
target triple = "powerpc64-bgq-linux"
3-
; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
3+
; RUN: opt < %s -domtree -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
44

55
@X = external global [16000 x double], align 32
66
@Y = external global [16000 x double], align 32

‎llvm/test/Analysis/GlobalsModRef/aliastest.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
; RUN: opt < %s -basicaa -globalsmodref-aa -gvn -S | FileCheck %s
1+
; RUN: opt < %s -domtree -basicaa -globalsmodref-aa -gvn -S | FileCheck %s
22

33
@X = internal global i32 4 ; <i32*> [#uses=1]
44

‎llvm/test/Transforms/ObjCARC/weak-copies.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
; RUN: opt -S -basicaa -objc-arc < %s | FileCheck %s
1+
; RUN: opt -S -domtree -basicaa -objc-arc < %s | FileCheck %s
22

33
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"
44
target triple = "x86_64-apple-darwin11.0.0"

‎llvm/test/Transforms/ObjCARC/weak-dce.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
; RUN: opt -S -basicaa -objc-arc < %s | FileCheck %s
1+
; RUN: opt -S -domtree -basicaa -objc-arc < %s | FileCheck %s
22
; rdar://11434915
33

44
; Delete the weak calls and replace them with just the net retain.

0 commit comments

Comments
 (0)
Please sign in to comment.