Index: lib/Analysis/CFLAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAliasAnalysis.cpp +++ lib/Analysis/CFLAliasAnalysis.cpp @@ -47,6 +47,7 @@ #include "llvm/Support/ErrorHandling.h" #include #include +#include #include #include @@ -231,6 +232,10 @@ // Comparisons between global variables and other constants should be // handled by BasicAA. + // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing + // a GlobalValue and ConstantExpr, but every query needs to have at least + // one Value tied to a Function, and neither GlobalValues nor ConstantExprs + // are. if (isa(LocA.Ptr) && isa(LocB.Ptr)) { return AliasAnalysis::alias(LocA, LocB); } @@ -389,7 +394,7 @@ // I put this here to give us an upper bound on time taken by IPA. Is it // really (realistically) needed? Keep in mind that we do have an n^2 algo. - if (std::distance(Args.begin(), Args.end()) > (int) MaxSupportedArgs) + if (std::distance(Args.begin(), Args.end()) > (int)MaxSupportedArgs) return false; // Exit early if we'll fail anyway @@ -747,6 +752,25 @@ static void buildGraphFrom(CFLAliasAnalysis &, Function *, SmallVectorImpl &, NodeMapT &, GraphT &); +// 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 &); + +// 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 &, NodeMapT &, + GraphT &); + +// Notes whether it would be pointless to add the given Value to our sets. +static bool canSkipAddingToSets(Value *Val); + // Builds the graph + StratifiedSets for a function. static FunctionInfo buildSetsFrom(CFLAliasAnalysis &, Function *); @@ -818,6 +842,8 @@ static void argsToEdges(CFLAliasAnalysis &Analysis, Instruction *Inst, SmallVectorImpl &Output) { + assert(hasUsefulEdges(Inst) && + "Expected instructions to have 'useful' edges"); GetEdgesVisitor v(Analysis, Output); v.visit(Inst); } @@ -834,13 +860,41 @@ llvm_unreachable("Incomplete switch coverage"); } -// Aside: We may remove graph construction entirely, because it doesn't really -// buy us much that we don't already have. I'd like to add interprocedural -// analysis prior to this however, in case that somehow requires the graph -// produced by this for efficient execution -static void buildGraphFrom(CFLAliasAnalysis &Analysis, Function *Fn, - SmallVectorImpl &ReturnedValues, - NodeMapT &Map, GraphT &Graph) { +static void constexprToEdges(CFLAliasAnalysis &Analysis, + ConstantExpr &CExprToCollapse, + SmallVectorImpl &Results) { + SmallVector Worklist; + Worklist.push_back(&CExprToCollapse); + + SmallVector ConstexprEdges; + while (!Worklist.empty()) { + auto *CExpr = Worklist.pop_back_val(); + std::unique_ptr Inst(CExpr->getAsInstruction()); + + if (!hasUsefulEdges(Inst.get())) + continue; + + ConstexprEdges.clear(); + argsToEdges(Analysis, Inst.get(), ConstexprEdges); + for (auto &Edge : ConstexprEdges) { + if (Edge.From == Inst.get()) + Edge.From = CExpr; + else if (auto *Nested = dyn_cast(Edge.From)) + Worklist.push_back(Nested); + + if (Edge.To == Inst.get()) + Edge.To = CExpr; + else if (auto *Nested = dyn_cast(Edge.To)) + Worklist.push_back(Nested); + } + + Results.append(ConstexprEdges.begin(), ConstexprEdges.end()); + } +} + +static void addInstructionToGraph(CFLAliasAnalysis &Analysis, Instruction &Inst, + SmallVectorImpl &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; @@ -851,42 +905,86 @@ return Iter->second; }; + // We don't want the edges of most "return" instructions, but we *do* want + // to know what can be returned. + if (isa(&Inst)) + ReturnedValues.push_back(&Inst); + + if (!hasUsefulEdges(&Inst)) + return; + SmallVector 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(&Inst)) - ReturnedValues.push_back(Ret); - - if (!hasUsefulEdges(&Inst)) - continue; + 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; + } - Edges.clear(); - argsToEdges(Analysis, &Inst, Edges); + 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)); + }; - // 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; - } + SmallVector ConstantExprs; + for (const Edge &E : Edges) { + addEdgeToGraph(E); + if (auto *Constexpr = dyn_cast(E.To)) + ConstantExprs.push_back(Constexpr); + if (auto *Constexpr = dyn_cast(E.From)) + ConstantExprs.push_back(Constexpr); + } - 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)); - } - } + for (ConstantExpr *CE : ConstantExprs) { + Edges.clear(); + constexprToEdges(Analysis, *CE, Edges); + std::for_each(Edges.begin(), Edges.end(), addEdgeToGraph); } } +// Aside: We may remove graph construction entirely, because it doesn't really +// buy us much that we don't already have. I'd like to add interprocedural +// analysis prior to this however, in case that somehow requires the graph +// produced by this for efficient execution +static void buildGraphFrom(CFLAliasAnalysis &Analysis, Function *Fn, + SmallVectorImpl &ReturnedValues, + NodeMapT &Map, GraphT &Graph) { + for (auto &Bb : Fn->getBasicBlockList()) + for (auto &Inst : Bb.getInstList()) + addInstructionToGraph(Analysis, Inst, ReturnedValues, Map, Graph); +} + +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. + if (isa(Val)) { + bool Container = isa(Val) || isa(Val) || + isa(Val); + // TODO: Because all of these things are constant, we can determine whether + // the data is *actually* mutable at graph building time. This will probably + // come for free/cheap with offset awareness. + bool CanStoreMutableData = + isa(Val) || isa(Val) || Container; + return !CanStoreMutableData; + } + + return false; +} + static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) { NodeMapT Map; GraphT Graph; @@ -918,7 +1016,7 @@ while (!Worklist.empty()) { auto Node = Worklist.pop_back_val(); auto *CurValue = findValueOrDie(Node); - if (isa(CurValue) && !isa(CurValue)) + if (canSkipAddingToSets(CurValue)) continue; for (const auto &EdgeTuple : Graph.edgesFor(Node)) { @@ -927,7 +1025,7 @@ auto &OtherNode = std::get<1>(EdgeTuple); auto *OtherValue = findValueOrDie(OtherNode); - if (isa(OtherValue) && !isa(OtherValue)) + if (canSkipAddingToSets(OtherValue)) continue; bool Added; @@ -962,7 +1060,12 @@ // 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 Attrs = valueToAttrIndex(&Arg); + if (Attrs.hasValue()) + Builder.noteAttributes(&Arg, *Attrs); } return FunctionInfo(Builder.build(), std::move(ReturnedValues)); Index: test/Analysis/CFLAliasAnalysis/asm-global-bugfix.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/asm-global-bugfix.ll +++ test/Analysis/CFLAliasAnalysis/asm-global-bugfix.ll @@ -7,7 +7,7 @@ @G = private unnamed_addr constant [1 x i8] c"\00", align 1 ; CHECK: Function: test_no_crash -; CHECK: 1 no alias responses +; CHECK: 0 no alias responses define void @test_no_crash() #0 { entry: call i8* asm "nop", "=r,r"( Index: test/Analysis/CFLAliasAnalysis/const-expr-gep.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/const-expr-gep.ll +++ test/Analysis/CFLAliasAnalysis/const-expr-gep.ll @@ -7,15 +7,51 @@ %T = type { i32, [10 x i8] } @G = external global %T +@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, %T* @G, i64 0, i32 0 - %E = getelementptr %T, %T* @G, i64 0, i32 1, i64 5 %F = getelementptr i32, i32* getelementptr (%T* @G, i64 0, i32 0), i64 0 %X = getelementptr [10 x i8], [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, i32* getelementptr (%T* @G, i64 0, i32 0), i64 0 + %H = getelementptr %T, %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]] } +@NT = external global %NestedT + +define void @checkNesting(i32* %arg0) { + %A = getelementptr [1 x i32], + [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 +} Index: test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll +++ test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll @@ -18,7 +18,7 @@ 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