[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
George Burgess IV
george.burgess.iv at gmail.com
Fri Jan 30 06:15:55 PST 2015
I'm not exactly thrilled about the size of this diff -- I'll happily break
it up into more manageable bits later today, because some of it is test
fixes, another bit is a minor bug fix, etc.
Important bit (WRT ConstantExpr): moved the loop body from buildGraphFrom
into a new function. The body has a few tweaks to call constexprToEdges on
all ConstantExprs that we encounter. constexprToEdges, naturally,
interprets a ConstantExpr (and all nested ConstantExprs) and places the
results into a SmallVector<Edge>.
I'm assuming this method of handling ConstantExprs isn't 100% correct
because I was told that handling them correctly would be more difficult
than I think it is. I can't quite figure out why, so examples of cases that
break my code would be greatly appreciated. :)
George
On Mon, Jan 26, 2015 at 2:43 PM, George Burgess IV <
george.burgess.iv at gmail.com> wrote:
> Inline
>
> George
>
> On Jan 26, 2015, at 1:05 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
>
> George, given that, can you just build constexpr handling (it's not as
> easy as you think) as a separate funciton and have it use it in the right
> places?
>
> Will do. :)
>
> FWIW, my current list of CFLAA issues is:
>
> 1. Unknown values (results from ptrtoint, incoming pointers, etc) are not
> treated as unknown. These should be done through graph edge (so that they
> can be one way, otherwise, you will unify everything :P)
>
> 2. Constexpr handling
>
> ^^^ These are correctness issues. I'm pretty sure there are a few more but
> i haven't finished auditing
> 3. In a number of places we treat non-pointers as memory-locations and
> unify them with pointers. This introduces a lot of spurious aliasing.
> 4. More generally, we induce a lot of spurious aliasing through things at
> different dereference levels. In these cases, one may to the other, but,
> for example, if we have a foo***, and a foo* (and neither pointers to
> unknown things or escapes), the only way for foo *** to alias foo* is if
> there is a graph path with two dereferences between them.
> We seem to get this wrong sometimes.
>
> Agreed on all four. Though naturally it should be fixed, I’d like to see
> how much of an issue #4 ends up being when we properly deal with #3.
>
>
> On Sun Jan 25 2015 at 6:44:07 PM Chandler Carruth <chandlerc at google.com>
> wrote:
>
>>
>> On Sun, Jan 25, 2015 at 6:37 PM, George Burgess IV <
>> george.burgess.iv at gmail.com> wrote:
>>
>>> > Fixing that still gives a wrong result, i haven't started to track
>>> down what *else* is going on here.
>>>
>>> Running with the attached diff + a modified buildGraphFrom to handle the
>>> constexpr GEPs, we seem to flag everything in test2.ll (conservatively)
>>> correctly.
>>>
>>> Is `store` the only place we can expect to see these constexpr analogs,
>>> or is just about anywhere fair game?
>>>
>>
>> Any Value can be a ConstantExpr, so all operands to instructions are fair
>> game.
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/e0d4dfe0/attachment.html>
-------------- next part --------------
diff --git a/lib/Analysis/CFLAliasAnalysis.cpp b/lib/Analysis/CFLAliasAnalysis.cpp
index 9783671..cbb8599 100644
--- a/lib/Analysis/CFLAliasAnalysis.cpp
+++ b/lib/Analysis/CFLAliasAnalysis.cpp
@@ -28,6 +28,7 @@
// time.
//===----------------------------------------------------------------------===//
+
#include "StratifiedSets.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
@@ -46,6 +47,7 @@
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include <cassert>
+#include <memory>
#include <forward_list>
#include <tuple>
@@ -220,12 +222,13 @@ public:
if (LocA.Size == LocB.Size) {
return MustAlias;
} else {
- return PartialAlias;
+ return MayAlias;
}
}
// Comparisons between global variables and other constants should be
// handled by BasicAA.
+ // TODO: ConstantExpr handling
if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) {
return MayAlias;
}
@@ -456,10 +459,11 @@ public:
template <typename InstT> void visitCallLikeInst(InstT &Inst) {
SmallVector<Function *, 4> Targets;
if (getPossibleTargets(&Inst, Targets)) {
+ auto InitialSize = Output.size();
if (tryInterproceduralAnalysis(Targets, &Inst, Inst.arg_operands()))
return;
// Cleanup from interprocedural analysis
- Output.clear();
+ Output.erase(Output.begin()+InitialSize, Output.end());
}
for (Value *V : Inst.arg_operands())
@@ -720,6 +724,22 @@ static void argsToEdges(CFLAliasAnalysis &, Instruction *,
// given an EdgeType.
static Level directionOfEdgeType(EdgeType);
+// Gets the edges of a ConstantExpr as if it was an Instruction. This
+// function also acts on any nested ConstantExprs, adding the edges
+// of those to the given SmallVector as well.
+static void constexprToEdges(CFLAliasAnalysis &, ConstantExpr &,
+ SmallVectorImpl<Edge> &);
+
+// Given an Instruction, this will add it to the graph, along with any
+// Instructions that are potentially only available from said Instruction
+// For example, given the following line:
+// %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
+// addInstructionToGraph would add both the `load` and `getelementptr`
+// instructions to the graph appropriately.
+static void addInstructionToGraph(CFLAliasAnalysis &, Instruction &,
+ SmallVectorImpl<Value *> &, NodeMapT &,
+ GraphT &);
+
// Builds the graph needed for constructing the StratifiedSets for the
// given function
static void buildGraphFrom(CFLAliasAnalysis &, Function *,
@@ -816,6 +836,43 @@ static Level directionOfEdgeType(EdgeType Weight) {
static void buildGraphFrom(CFLAliasAnalysis &Analysis, Function *Fn,
SmallVectorImpl<Value *> &ReturnedValues,
NodeMapT &Map, GraphT &Graph) {
+ for (auto &Bb : Fn->getBasicBlockList()) {
+ for (auto &Inst : Bb.getInstList()) {
+ addInstructionToGraph(Analysis, Inst, ReturnedValues, Map, Graph);
+ }
+ }
+}
+
+static void constexprToEdges(CFLAliasAnalysis &Analysis,
+ ConstantExpr &CExprToCollapse,
+ SmallVectorImpl<Edge> &Results) {
+ SmallVector<ConstantExpr*, 4> Worklist;
+ Worklist.push_back(&CExprToCollapse);
+
+ SmallVector<Edge, 8> ConstexprEdges;
+ while (!Worklist.empty()) {
+ auto* CExpr = Worklist.pop_back_val();
+ std::unique_ptr<Instruction> Inst(CExpr->getAsInstruction());
+
+ ConstexprEdges.clear();
+ argsToEdges(Analysis, Inst.get(), ConstexprEdges);
+ for (auto& Edge : ConstexprEdges) {
+ assert(Edge.From == Inst.get() &&
+ "Expected ConstantExpr edge `From` to evaluate to the ConstantExpr");
+ // Inst doesn't exist outside of this loop
+ Edge.From = CExpr;
+
+ if (auto* ArgExpr = dyn_cast<ConstantExpr>(Edge.To))
+ Worklist.push_back(ArgExpr);
+ }
+
+ Results.append(ConstexprEdges.begin(), ConstexprEdges.end());
+ }
+}
+
+static void addInstructionToGraph(CFLAliasAnalysis &Analysis, Instruction &Inst,
+ SmallVectorImpl<Value *> &ReturnedValues,
+ NodeMapT &Map, GraphT &Graph) {
const auto findOrInsertNode = [&Map, &Graph](Value *Val) {
auto Pair = Map.insert(std::make_pair(Val, GraphT::Node()));
auto &Iter = Pair.first;
@@ -826,40 +883,63 @@ static void buildGraphFrom(CFLAliasAnalysis &Analysis, Function *Fn,
return Iter->second;
};
- SmallVector<Edge, 8> Edges;
- for (auto &Bb : Fn->getBasicBlockList()) {
- for (auto &Inst : Bb.getInstList()) {
- // We don't want the edges of most "return" instructions, but we *do* want
- // to know what can be returned.
- if (auto *Ret = dyn_cast<ReturnInst>(&Inst))
- ReturnedValues.push_back(Ret);
+ // We don't want the edges of most "return" instructions, but we *do* want
+ // to know what can be returned.
+ if (isa<ReturnInst>(&Inst))
+ ReturnedValues.push_back(&Inst);
- if (!hasUsefulEdges(&Inst))
- continue;
+ if (!hasUsefulEdges(&Inst))
+ return;
- Edges.clear();
- argsToEdges(Analysis, &Inst, Edges);
+ SmallVector<Edge, 8> Edges;
+ argsToEdges(Analysis, &Inst, Edges);
+
+ // In the case of an unused alloca (or similar), edges may be empty. Note
+ // that it exists so we can potentially answer NoAlias.
+ if (Edges.empty()) {
+ auto MaybeVal = getTargetValue(&Inst);
+ assert(MaybeVal.hasValue());
+ auto *Target = *MaybeVal;
+ findOrInsertNode(Target);
+ return;
+ }
- // In the case of an unused alloca (or similar), edges may be empty. Note
- // that it exists so we can potentially answer NoAlias.
- if (Edges.empty()) {
- auto MaybeVal = getTargetValue(&Inst);
- assert(MaybeVal.hasValue());
- auto *Target = *MaybeVal;
- findOrInsertNode(Target);
- continue;
- }
+ const auto addEdgeToGraph = [&Graph, &findOrInsertNode](const Edge& E) {
+ auto To = findOrInsertNode(E.To);
+ auto From = findOrInsertNode(E.From);
+ auto FlippedWeight = flipWeight(E.Weight);
+ auto Attrs = E.AdditionalAttrs;
+ Graph.addEdge(From, To, std::make_pair(E.Weight, Attrs),
+ std::make_pair(FlippedWeight, Attrs));
+ };
- for (const Edge &E : Edges) {
- auto To = findOrInsertNode(E.To);
- auto From = findOrInsertNode(E.From);
- auto FlippedWeight = flipWeight(E.Weight);
- auto Attrs = E.AdditionalAttrs;
- Graph.addEdge(From, To, std::make_pair(E.Weight, Attrs),
- std::make_pair(FlippedWeight, Attrs));
- }
- }
+ SmallVector<ConstantExpr*, 4> ConstantExprs;
+ for (const Edge &E : Edges) {
+ addEdgeToGraph(E);
+ if (auto* Constexpr = dyn_cast<ConstantExpr>(E.To))
+ ConstantExprs.push_back(Constexpr);
+ if (auto* Constexpr = dyn_cast<ConstantExpr>(E.From))
+ ConstantExprs.push_back(Constexpr);
}
+
+ for (ConstantExpr* CE : ConstantExprs) {
+ Edges.clear();
+ constexprToEdges(Analysis, *CE, Edges);
+ std::for_each(Edges.begin(), Edges.end(), addEdgeToGraph);
+ }
+}
+
+static bool canSkipAddingToSets(Value* Val) {
+ // Constants can share instances, which may falsely unify multiple
+ // sets, e.g. in
+ // store i32* null, i32** %ptr1
+ // store i32* null, i32** %ptr2
+ // clearly ptr1 and ptr2 should not be unified into the same set, so
+ // we should filter out the (potentially shared) instance to
+ // i32* null.
+ return isa<Constant>(Val) &&
+ !isa<GlobalValue>(Val) &&
+ !isa<ConstantExpr>(Val);
}
static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) {
@@ -881,7 +961,6 @@ static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) {
};
StratifiedSetsBuilder<Value *> Builder;
-
SmallVector<GraphT::Node, 16> Worklist;
for (auto &Pair : Map) {
Worklist.clear();
@@ -893,7 +972,7 @@ static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) {
while (!Worklist.empty()) {
auto Node = Worklist.pop_back_val();
auto *CurValue = findValueOrDie(Node);
- if (isa<Constant>(CurValue) && !isa<GlobalValue>(CurValue))
+ if (canSkipAddingToSets(CurValue))
continue;
for (const auto &EdgeTuple : Graph.edgesFor(Node)) {
@@ -902,7 +981,7 @@ static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) {
auto &OtherNode = std::get<1>(EdgeTuple);
auto *OtherValue = findValueOrDie(OtherNode);
- if (isa<Constant>(OtherValue) && !isa<GlobalValue>(OtherValue))
+ if (canSkipAddingToSets(OtherValue))
continue;
bool Added;
@@ -937,7 +1016,15 @@ static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) {
// things that were present during construction being present in the graph.
// So, we add all present arguments here.
for (auto &Arg : Fn->args()) {
- Builder.add(&Arg);
+ if (!Builder.add(&Arg))
+ continue;
+
+ auto MaybeAttrIndex = valueToAttrIndex(&Arg);
+ assert(MaybeAttrIndex.hasValue() && "Args should always have attr indecies");
+
+ StratifiedAttrs Attrs;
+ Attrs.set(*MaybeAttrIndex);
+ Builder.noteAttributes(&Arg, Attrs);
}
return FunctionInfo(Builder.build(), std::move(ReturnedValues));
@@ -993,18 +1080,18 @@ CFLAliasAnalysis::query(const AliasAnalysis::Location &LocA,
auto SetB = *MaybeB;
if (SetA.Index == SetB.Index)
- return AliasAnalysis::PartialAlias;
+ return AliasAnalysis::MayAlias;
auto AttrsA = Sets.getLink(SetA.Index).Attrs;
auto AttrsB = Sets.getLink(SetB.Index).Attrs;
// Stratified set attributes are used as markets to signify whether a member
- // of a StratifiedSet (or a member of a set above the current set) has
+ // of a StratifiedSet (or a member of a set above the current set) has
// interacted with either arguments or globals. "Interacted with" meaning
- // its value may be different depending on the value of an argument or
+ // its value may be different depending on the value of an argument or
// global. The thought behind this is that, because arguments and globals
// may alias each other, if AttrsA and AttrsB have touched args/globals,
- // we must conservatively say that they alias. However, if at least one of
- // the sets has no values that could legally be altered by changing the value
+ // we must conservatively say that they alias. However, if at least one of
+ // the sets has no values that could legally be altered by changing the value
// of an argument or global, then we don't have to be as conservative.
if (AttrsA.any() && AttrsB.any())
return AliasAnalysis::MayAlias;
diff --git a/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll b/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll
index 9ae200b..b0ac8e9 100644
--- a/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll
+++ b/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll
@@ -7,15 +7,50 @@
%T = type { i32, [10 x i8] }
@G = external global %T
+ at G2 = external global %T
-; CHECK: Function: test
-; CHECK-NOT: May:
+; TODO: Quite a few of these are MayAlias because we don't yet consider
+; constant offsets in CFLAA. If we start doing so, then we'll need to
+; change these test cases
+; CHECK: Function: test
+; CHECK: MayAlias: i32* %D, i32* %F
+; CHECK: MayAlias: i32* %D, i8* %X
+; CHECK: MayAlias: i32* %F, i8* %X
define void @test() {
%D = getelementptr %T* @G, i64 0, i32 0
- %E = getelementptr %T* @G, i64 0, i32 1, i64 5
%F = getelementptr i32* getelementptr (%T* @G, i64 0, i32 0), i64 0
%X = getelementptr [10 x i8]* getelementptr (%T* @G, i64 0, i32 1), i64 0, i64 5
ret void
}
+
+; CHECK: Function: simplecheck
+; CHECK: MayAlias: i32* %F, i32* %arg0
+; CHECK: MayAlias: i32* %H, i32* %arg0
+; CHECK: MayAlias: i32* %F, i32* %H
+define void @simplecheck(i32* %arg0) {
+ %F = getelementptr i32* getelementptr (%T* @G, i64 0, i32 0), i64 0
+ %H = getelementptr %T* @G2, i64 0, i32 0
+
+ ret void
+}
+
+; Ensure that CFLAA properly identifies and handles escaping variables (i.e.
+; globals) in nested ConstantExprs
+
+; CHECK: Function: checkNesting
+; CHECK: MayAlias: i32* %A, i32* %arg0
+
+%NestedT = type { [1 x [1 x i32]] }
+ at NT = external global %NestedT
+define void @checkNesting(i32* %arg0) {
+ %A = getelementptr
+ [1 x i32]* getelementptr
+ ([1 x [1 x i32]]* getelementptr (%NestedT* @NT, i64 0, i32 0),
+ i64 0,
+ i32 0),
+ i64 0,
+ i32 0
+ ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll b/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll
index 664ea9e..4d29f68 100644
--- a/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll
+++ b/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll
@@ -2,8 +2,9 @@
; RUN: opt -S -tbaa -gvn < %s | FileCheck %s
; Adapted from the BasicAA full-store-partial-alias.ll test.
-; CFL AA should notice that the store stores to the entire %u object,
+; CFL AA could notice that the store stores to the entire %u object,
; so the %tmp5 load is PartialAlias with the store and suppress TBAA.
+; FIXME: However, right now, CFLAA cannot prove PartialAlias here
; Without CFL AA, TBAA should say that %tmp5 is NoAlias with the store.
target datalayout = "e-p:64:64:64"
@@ -14,8 +15,9 @@ target datalayout = "e-p:64:64:64"
@endianness_test = global i64 1, align 8
define i32 @signbit(double %x) nounwind {
+; FIXME: This would be ret i32 0 if CFLAA could prove PartialAlias
; CFLAA: ret i32 %tmp5.lobit
-; CHECK: ret i32 0
+; CHECK: ret i32 0
entry:
%u = alloca %union.anon, align 8
%tmp9 = getelementptr inbounds %union.anon* %u, i64 0, i32 0
diff --git a/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll b/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
index a0195d7..557bc40 100644
--- a/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
+++ b/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
@@ -3,9 +3,10 @@
target datalayout = "e-p:32:32:32"
-; CHECK: 1 partial alias response
-
-define i32 @test(i32* %tab, i32 %indvar) nounwind {
+; FIXME: This could be PartialAlias but CFLAA can't currently prove it
+; CHECK: 1 may alias response
+define i32 @test(i32 %indvar) nounwind {
+ %tab = alloca i32, align 4
%tmp31 = mul i32 %indvar, -2
%tmp32 = add i32 %tmp31, 30
%t.5 = getelementptr i32* %tab, i32 %tmp32
diff --git a/test/Analysis/CFLAliasAnalysis/must-and-partial.ll b/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
index df7de38..2585a56 100644
--- a/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
+++ b/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
@@ -1,14 +1,15 @@
; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
-
; When merging MustAlias and PartialAlias, merge to PartialAlias
; instead of MayAlias.
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"
-; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
-define i8 @test0(i8* %base, i1 %x) {
+; FIXME: This could be PartialAlias but CFLAA can't currently prove it
+; CHECK: MayAlias: i16* %bigbase0, i8* %phi
+define i8 @test0(i1 %x) {
entry:
+ %base = alloca i8, align 1
%baseplusone = getelementptr i8* %base, i64 1
br i1 %x, label %red, label %green
red:
@@ -24,9 +25,11 @@ green:
ret i8 %loaded
}
-; CHECK: PartialAlias: i16* %bigbase1, i8* %sel
-define i8 @test1(i8* %base, i1 %x) {
+; FIXME: This could be PartialAlias but CFLAA can't currently prove it
+; CHECK: MayAlias: i16* %bigbase1, i8* %sel
+define i8 @test1(i1 %x) {
entry:
+ %base = alloca i8, align 4
%baseplusone = getelementptr i8* %base, i64 1
%sel = select i1 %x, i8* %baseplusone, i8* %base
store i8 0, i8* %sel
@@ -37,3 +40,16 @@ entry:
%loaded = load i8* %sel
ret i8 %loaded
}
+
+; Incoming pointer arguments should not be PartialAlias because we do not know their initial state
+; even if they are nocapture
+; CHECK: MayAlias: double* %A, double* %Index
+define void @testr2(double* nocapture readonly %A, double* nocapture readonly %Index) {
+entry:
+ %arrayidx22 = getelementptr inbounds double* %Index, i64 2
+ %0 = load double* %arrayidx22
+ %arrayidx25 = getelementptr inbounds double* %A, i64 2
+ %1 = load double* %arrayidx25
+ %mul26 = fmul double %0, %1
+ ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll b/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll
index 8afedf2..3475285 100644
--- a/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll
+++ b/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll
@@ -18,7 +18,7 @@ define void @test(i1 %cond,
i32* %arg31, i32* %arg32, i32* %arg33, i32* %arg34, i32* %arg35) {
; CHECK: 946 Total Alias Queries Performed
- ; CHECK: 810 no alias responses (85.6%)
+ ; CHECK: 43 no alias responses (4.5%)
%a = alloca i32, align 4
%b = select i1 %cond, i32* %arg35, i32* %arg34
%c = select i1 %cond, i32* %arg34, i32* %arg33
More information about the llvm-dev
mailing list