Index: lib/Analysis/CFLAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAliasAnalysis.cpp +++ lib/Analysis/CFLAliasAnalysis.cpp @@ -64,13 +64,23 @@ : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {} CFLAAResult::~CFLAAResult() {} -/// We use ExternalRelation to describe an externally visible interaction +/// We use InterfaceValue to describe parameters/return value, as well as +/// potential memory locations that are pointed to by parameters/return value, +/// of a function. +/// Index is an integer which represents a single parameter or a return value. +/// When the index is 0, it refers to the return value. Non-zero index i refers +/// to the i-th parameter. +/// DerefLevel indicates the number of dereferences one must perform on the +/// parameter/return value to get this InterfaceValue. +struct InterfaceValue { + unsigned Index; + unsigned DerefLevel; +}; + +/// We use ExternalRelation to describe an externally visible aliasing relations /// between parameters/return value of a function. -/// Both From and To are integer indices that represent a single parameter or -/// return value. When the index is 0, they represent the return value. Non-zero -/// index i represents the i-th parameter. struct ExternalRelation { - unsigned From, To; + InterfaceValue From, To; }; /// Information we have about a function and would like to keep around. @@ -244,6 +254,16 @@ std::size_t size() const { return NodeImpls.size(); } }; +// Interprocedural assignment edges that CFLGraph may not easily model +struct InterprocEdge { + struct Node { + Value *Value; + unsigned DerefLevel; + }; + + Node From, To; +}; + /// Gets the edges our graph should have, based on an Instruction* class GetEdgesVisitor : public InstVisitor { CFLAAResult &AA; @@ -252,6 +272,7 @@ CFLGraph &Graph; SmallPtrSetImpl &Externals; SmallPtrSetImpl &Escapes; + SmallVectorImpl &InterprocEdges; static bool hasUsefulEdges(ConstantExpr *CE) { // ConstantExpr doesn't have terminators, invokes, or fences, so only needs @@ -288,9 +309,10 @@ public: GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI, CFLGraph &Graph, SmallPtrSetImpl &Externals, - SmallPtrSetImpl &Escapes) - : AA(AA), TLI(TLI), Graph(Graph), Externals(Externals), Escapes(Escapes) { - } + SmallPtrSetImpl &Escapes, + SmallVectorImpl &InterprocEdges) + : AA(AA), TLI(TLI), Graph(Graph), Externals(Externals), Escapes(Escapes), + InterprocEdges(InterprocEdges) {} void visitInstruction(Instruction &) { llvm_unreachable("Unsupported instruction encountered"); @@ -405,18 +427,20 @@ auto &RetParamRelations = FnInfo->getRetParamRelations(); for (auto &Relation : RetParamRelations) { - auto FromIndex = Relation.From; - auto ToIndex = Relation.To; + auto FromIndex = Relation.From.Index; + auto ToIndex = Relation.To.Index; auto FromVal = (FromIndex == 0) ? CS.getInstruction() : CS.getArgument(FromIndex - 1); auto ToVal = (ToIndex == 0) ? CS.getInstruction() : CS.getArgument(ToIndex - 1); if (FromVal->getType()->isPointerTy() && - ToVal->getType()->isPointerTy()) - // Actual arguments must be defined before they are used at callsite. - // Therefore by the time we reach here, FromVal and ToVal should - // already exist in the graph. We can go ahead and add them directly - Graph.addEdge(FromVal, ToVal, EdgeType::Assign); + ToVal->getType()->isPointerTy()) { + auto FromLevel = Relation.From.DerefLevel; + auto ToLevel = Relation.To.DerefLevel; + InterprocEdges.push_back( + InterprocEdge{InterprocEdge::Node{FromVal, FromLevel}, + InterprocEdge::Node{ToVal, ToLevel}}); + } } } @@ -533,6 +557,7 @@ // Auxiliary structures used by the builder SmallPtrSet ExternalValues; SmallPtrSet EscapedValues; + SmallVector InterprocEdges; // Helper functions @@ -569,7 +594,8 @@ if (!hasUsefulEdges(&Inst)) return; - GetEdgesVisitor(Analysis, TLI, Graph, ExternalValues, EscapedValues) + GetEdgesVisitor(Analysis, TLI, Graph, ExternalValues, EscapedValues, + InterprocEdges) .visit(Inst); } @@ -601,6 +627,9 @@ const SmallPtrSet &getEscapedValues() const { return EscapedValues; } + const SmallVector &getInterprocEdges() const { + return InterprocEdges; + } }; } @@ -712,93 +741,62 @@ return false; } -/// Gets whether the sets at Index1 above, below, or equal to the sets at -/// Index2. Returns None if they are not in the same set chain. -static Optional getIndexRelation(const StratifiedSets &Sets, - StratifiedIndex Index1, - StratifiedIndex Index2) { - if (Index1 == Index2) - return Level::Same; - - const auto *Current = &Sets.getLink(Index1); - while (Current->hasBelow()) { - if (Current->Below == Index2) - return Level::Below; - Current = &Sets.getLink(Current->Below); - } - - Current = &Sets.getLink(Index1); - while (Current->hasAbove()) { - if (Current->Above == Index2) - return Level::Above; - Current = &Sets.getLink(Current->Above); - } - - return None; -} - CFLAAResult::FunctionInfo::FunctionInfo(Function &Fn, const SmallVectorImpl &RetVals, StratifiedSets S) : Sets(std::move(S)) { - LLVM_CONSTEXPR unsigned ExpectedMaxArgs = 8; + // Historically, an arbitrary upper-bound of 50 args was selected. We may want + // to remove this if it doesn't really matter in practice. + if (Fn.arg_size() > MaxSupportedArgsInSummary) + return; + + // InterfaceMap here tries to group together all InterfaceValues that share + // the same StratifiedIndex. + DenseMap> InterfaceMap; + // Insert the given parameter/return value as well as the values below it into + // InterfaceMap + auto AddToInterfaceMap = [this, &InterfaceMap](unsigned InterfaceIndex, + StratifiedIndex SetIndex) { + unsigned Level = 0; + while (true) { + InterfaceMap[SetIndex].push_back(InterfaceValue{InterfaceIndex, Level}); + auto &Link = Sets.getLink(SetIndex); + if (Link.hasBelow()) { + ++Level; + SetIndex = Link.Below; + } else + break; + } + }; - // Collect StratifiedInfo for each parameter - SmallVector, ExpectedMaxArgs> ParamInfos; + // Populate InterfaceMap for parameters + unsigned I = 0; for (auto &Param : Fn.args()) { - if (Param.getType()->isPointerTy()) - ParamInfos.push_back(Sets.find(&Param)); - else - ParamInfos.push_back(None); - } - // Collect StratifiedInfo for each return value - SmallVector, 4> RetInfos; - RetInfos.reserve(RetVals.size()); - for (unsigned I = 0, E = RetVals.size(); I != E; ++I) - RetInfos.push_back(Sets.find(RetVals[I])); - - // This summary generation algorithm is n^2. An arbitrary upper-bound of 50 - // args was selected, so it doesn't take too long in insane cases. - if (Fn.arg_size() <= MaxSupportedArgsInSummary) { - for (unsigned I = 0, E = ParamInfos.size(); I != E; ++I) { - auto &MainInfo = ParamInfos[I]; - if (!MainInfo) - continue; - - // Adding edges between arguments for arguments that may end up aliasing - // each other. This is necessary for functions such as - // void foo(int** a, int** b) { *a = *b; } - // (Technically, the proper sets for this would be those below - // Arguments[I] and Arguments[X], but our algorithm will produce - // extremely similar, and equally correct, results either way) - for (unsigned X = I + 1; X != E; ++X) { - auto &SubInfo = ParamInfos[X]; - if (!SubInfo) - continue; - - auto MaybeRelation = - getIndexRelation(Sets, MainInfo->Index, SubInfo->Index); - if (!MaybeRelation.hasValue()) - continue; - - RetParamRelations.push_back(ExternalRelation{1 + I, 1 + X}); - } + if (Param.getType()->isPointerTy()) { + auto ParamInfo = Sets.find(&Param); + if (ParamInfo.hasValue()) + AddToInterfaceMap(I + 1, ParamInfo->Index); + } + ++I; + } - // Adding an edge from argument -> return value for each parameter that - // may alias the return value - for (unsigned X = 0, XE = RetInfos.size(); X != XE; ++X) { - auto &RetInfo = RetInfos[X]; - if (!RetInfo) - continue; + // Populate InterfaceMap for return values + for (unsigned I = 0, E = RetVals.size(); I != E; ++I) { + auto RetInfo = Sets.find(RetVals[I]); + if (RetInfo.hasValue()) + AddToInterfaceMap(0, RetInfo->Index); + } - auto MaybeRelation = - getIndexRelation(Sets, MainInfo->Index, RetInfo->Index); - if (!MaybeRelation.hasValue()) - continue; + // Collect aliasing Interfaces values, and keep track of them in + // RetParamRelations + for (const auto &mapping : InterfaceMap) { + auto &Interfaces = mapping.second; + if (Interfaces.size() <= 1) + continue; - RetParamRelations.push_back(ExternalRelation{1 + I, 0}); - } - } + auto Base = Interfaces.front(); + for (size_t I = 1, E = Interfaces.size(); I < E; ++I) + RetParamRelations.push_back(ExternalRelation{Base, Interfaces[I]}); } } @@ -856,6 +854,17 @@ } } + // Special handling for interprocedural aliases + for (auto &Edge : GraphBuilder.getInterprocEdges()) { + auto FromVal = Edge.From.Value; + auto ToVal = Edge.To.Value; + SetBuilder.add(FromVal); + SetBuilder.add(ToVal); + SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal, + Edge.To.DerefLevel); + } + + // Special handling for opaque external functions for (auto *Escape : GraphBuilder.getEscapedValues()) { SetBuilder.add(Escape); SetBuilder.noteAttributes(Escape, AttrEscaped); Index: lib/Analysis/StratifiedSets.h =================================================================== --- lib/Analysis/StratifiedSets.h +++ lib/Analysis/StratifiedSets.h @@ -412,6 +412,26 @@ return addAtMerging(ToAdd, MainIndex); } + /// \brief Merge the set "MainBelow"-levels below "Main" and the set + /// "ToAddBelow"-levels below "ToAdd". + void addBelowWith(const T &Main, unsigned MainBelow, const T &ToAdd, + unsigned ToAddBelow) { + assert(has(Main)); + assert(has(ToAdd)); + + auto GetIndexBelow = [this](StratifiedIndex Index, unsigned NumLevel) { + for (unsigned I = 0; I < NumLevel; ++I) { + auto Link = linksAt(Index); + Index = Link.hasBelow() ? Link.getBelow() : addLinkBelow(Index); + } + return Index; + }; + auto MainIndex = GetIndexBelow(*indexOf(Main), MainBelow); + auto ToAddIndex = GetIndexBelow(*indexOf(ToAdd), ToAddBelow); + if (&linksAt(MainIndex) != &linksAt(ToAddIndex)) + merge(MainIndex, ToAddIndex); + } + void noteAttributes(const T &Main, const StratifiedAttrs &NewAttrs) { assert(has(Main)); auto *Info = *get(Main); Index: test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll +++ test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll @@ -4,9 +4,6 @@ ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; xfail for now due to buggy interproc analysis -; XFAIL: * - define i32* @return_deref_arg_multilevel_callee(i32*** %arg1) { %deref = load i32**, i32*** %arg1 %deref2 = load i32*, i32** %deref @@ -23,7 +20,6 @@ ; CHECK: NoAlias: i32* %c, i32** %lpp ; CHECK: MayAlias: i32* %a, i32* %lpp_deref ; CHECK: NoAlias: i32* %b, i32* %lpp_deref -; CHECK: MayAlias: i32* %lpp_deref, i32** %p ; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp ; CHECK: MayAlias: i32* %a, i32* %lp ; CHECK: NoAlias: i32* %b, i32* %lp Index: test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll +++ test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll @@ -4,9 +4,6 @@ ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; xfail for now due to buggy interproc analysis -; XFAIL: * - define i32* @return_deref_arg_callee(i32** %arg1) { %deref = load i32*, i32** %arg1 ret i32* %deref Index: test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll +++ test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll @@ -4,9 +4,6 @@ ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; xfail for now due to buggy interproc analysis -; XFAIL: * - declare noalias i8* @malloc(i64) define i32*** @return_ref_arg_multilevel_callee(i32* %arg1) { @@ -21,9 +18,7 @@ ; CHECK-LABEL: Function: test_return_ref_arg_multilevel ; CHECK: NoAlias: i32* %a, i32*** %b ; CHECK: NoAlias: i32** %p, i32*** %b -; CHECK: NoAlias: i32*** %b, i32*** %pp ; CHECK: NoAlias: i32* %a, i32** %lb -; CHECK: NoAlias: i32** %lb, i32** %p ; CHECK: NoAlias: i32** %lb, i32*** %pp ; CHECK: NoAlias: i32** %lb, i32*** %b ; CHECK: MayAlias: i32* %a, i32* %lb_deref @@ -33,6 +28,10 @@ ; CHECK: MayAlias: i32* %lb_deref, i32* %lp ; CHECK: NoAlias: i32* %lp, i32** %lpp ; CHECK: MayAlias: i32* %lp, i32* %lpp_deref + +; We could've proven the following facts if the analysis were inclusion-based: +; NoAlias: i32*** %b, i32*** %pp +; NoAlias: i32** %lb, i32** %p define void @test_return_ref_arg_multilevel() { %a = alloca i32, align 4 %p = alloca i32*, align 8 Index: test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll +++ test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll @@ -4,9 +4,6 @@ ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; xfail for now due to buggy interproc analysis -; XFAIL: * - declare noalias i8* @malloc(i64) define i32** @return_ref_arg_callee(i32* %arg1) { @@ -16,13 +13,15 @@ ret i32** %ptr_cast } ; CHECK-LABEL: Function: test_return_ref_arg -; CHECK: NoAlias: i32** %b, i32** %p ; CHECK: MayAlias: i32* %a, i32* %lb ; CHECK: NoAlias: i32* %lb, i32** %p ; CHECK: NoAlias: i32* %lb, i32** %b ; CHECK: NoAlias: i32* %lp, i32** %p ; CHECK: NoAlias: i32* %lp, i32** %b ; CHECK: MayAlias: i32* %lb, i32* %lp + +; We could've proven the following facts if the analysis were inclusion-based: +; NoAlias: i32** %b, i32** %p define void @test_return_ref_arg() { %a = alloca i32, align 4 %p = alloca i32*, align 8 Index: test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll +++ test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll @@ -4,9 +4,6 @@ ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; xfail for now due to buggy interproc analysis -; XFAIL: * - declare noalias i8* @malloc(i64) define void @store_arg_multilevel_callee(i32*** %arg1, i32* %arg2) { @@ -17,7 +14,6 @@ ret void } ; CHECK-LABEL: Function: test_store_arg_multilevel -; CHECK: NoAlias: i32* %a, i32* %b ; CHECK: NoAlias: i32* %a, i32** %lpp ; CHECK: NoAlias: i32* %b, i32** %lpp ; CHECK: MayAlias: i32** %lpp, i32** %p @@ -27,10 +23,13 @@ ; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp ; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp ; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp ; CHECK: NoAlias: i32* %lp, i32*** %pp ; CHECK: NoAlias: i32* %lp, i32** %lpp ; CHECK: MayAlias: i32* %lp, i32* %lpp_deref + +; We could've proven the following facts if the analysis were inclusion-based: +; NoAlias: i32* %a, i32* %b +; NoAlias: i32* %b, i32* %lp define void @test_store_arg_multilevel() { %a = alloca i32, align 4 %b = alloca i32, align 4 Index: test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll +++ test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll @@ -4,22 +4,21 @@ ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; xfail for now due to buggy interproc analysis -; XFAIL: * - define void @store_arg_callee(i32** %arg1, i32* %arg2) { store i32* %arg2, i32** %arg1 ret void } ; CHECK-LABEL: Function: test_store_arg -; CHECK: NoAlias: i32* %a, i32* %b ; CHECK: NoAlias: i32* %a, i32** %p ; CHECK: NoAlias: i32* %b, i32** %p ; CHECK: MayAlias: i32* %a, i32* %lp ; CHECK: MayAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %a, i32* %lq ; CHECK: MayAlias: i32* %b, i32* %lq -; CHECK: NoAlias: i32* %lp, i32* %lq +; CHECK: MayAlias: i32* %lp, i32* %lq + +; We could've proven the following facts if the analysis were inclusion-based: +; NoAlias: i32* %a, i32* %b +; NoAlias: i32* %a, i32* %lq define void @test_store_arg() { %a = alloca i32, align 4 %b = alloca i32, align 4