George Burgess IV
2015-Jan-30 14:15 UTC
[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
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
Hal Finkel
2015-Jan-30 15:56 UTC
[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
----- Original Message -----> From: "George Burgess IV" <george.burgess.iv at gmail.com> > To: "Daniel Berlin" <dberlin at dberlin.org> > Cc: "Chandler Carruth" <chandlerc at google.com>, "Hal Finkel" <hfinkel at anl.gov>, "Jiangning Liu" > <Jiangning.Liu at arm.com>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Friday, January 30, 2015 8:15:55 AM > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers > > > > 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.Yes, please break it into independent parts.> > > 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. > :)I had thought that the case that Danny had looked at had a constant GEP, and so this constant might alias with other global pointers. How is that handled now? Thanks again, Hal> > > 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. > >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
George Burgess IV
2015-Jan-30 16:29 UTC
[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
> I had thought that the case that Danny had looked at had a constant GEP,and so this constant might alias with other global pointers. How is that handled now? That issue had to do with that we assumed that for all arguments of a given Instruction, each argument was either an Argument, GlobalValue, or Inst in `for (auto& Bb : Inst.getBasicBlockList()) for (auto& Inst : Bb.getInstList())`. ConstantExprs didn't fit into this instruction, because they aren't reached by said nested loop. With this fix, if we detect that there's a relevant ConstantExpr, we'll look into it as if it were a regular Instruction inside of Bb.getInstList(), which causes us to correctly detect the globals, etc. (I included a test case specifically for this -- it's ugly, but we have ~3 nested GEPs with a global at the innermost GEP. It produces the appropriate output) George On Fri, Jan 30, 2015 at 10:56 AM, Hal Finkel <hfinkel at anl.gov> wrote:> ----- Original Message ----- > > From: "George Burgess IV" <george.burgess.iv at gmail.com> > > To: "Daniel Berlin" <dberlin at dberlin.org> > > Cc: "Chandler Carruth" <chandlerc at google.com>, "Hal Finkel" < > hfinkel at anl.gov>, "Jiangning Liu" > > <Jiangning.Liu at arm.com>, "LLVM Developers Mailing List" < > llvmdev at cs.uiuc.edu> > > Sent: Friday, January 30, 2015 8:15:55 AM > > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 > numbers > > > > > > > > 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. > > Yes, please break it into independent parts. > > > > > > > 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. > > :) > > I had thought that the case that Danny had looked at had a constant GEP, > and so this constant might alias with other global pointers. How is that > handled now? > > Thanks again, > Hal > > > > > > > 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. > > > > > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/2d4cdae9/attachment.html>
Apparently Analagous Threads
- [LLVMdev] question about enabling cfl-aa and collecting a57 numbers
- [LLVMdev] question about enabling cfl-aa and collecting a57 numbers
- [LLVMdev] question about enabling cfl-aa and collecting a57 numbers
- [LLVMdev] question about enabling cfl-aa and collecting a57 numbers
- [LLVMdev] question about enabling cfl-aa and collecting a57 numbers