Index: include/llvm/Analysis/CFLAliasAnalysis.h =================================================================== --- include/llvm/Analysis/CFLAliasAnalysis.h +++ include/llvm/Analysis/CFLAliasAnalysis.h @@ -31,9 +31,9 @@ class CFLAAResult : public AAResultBase { friend AAResultBase; +public: struct FunctionInfo; -public: explicit CFLAAResult(const TargetLibraryInfo &); CFLAAResult(CFLAAResult &&Arg); ~CFLAAResult(); Index: lib/Analysis/CFLAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAliasAnalysis.cpp +++ lib/Analysis/CFLAliasAnalysis.cpp @@ -64,14 +64,21 @@ : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {} CFLAAResult::~CFLAAResult() {} +/// We use ExternalRelation to describe an externally visible interaction +/// 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; +}; + /// Information we have about a function and would like to keep around. struct CFLAAResult::FunctionInfo { StratifiedSets Sets; - // Lots of functions have < 4 returns. Adjust as necessary. - SmallVector ReturnedValues; - FunctionInfo(StratifiedSets &&S, SmallVector &&RV) - : Sets(std::move(S)), ReturnedValues(std::move(RV)) {} + // RetParamRelations is a collection of ExternalRelations. + SmallVector RetParamRelations; }; /// Try to go from a Value* to a Function*. Never returns nullptr. @@ -101,6 +108,9 @@ LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex; LLVM_CONSTEXPR StratifiedAttr AttrGlobal = 1 << AttrGlobalIndex; +/// The maximum number of arguments we can put into a summary. +LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50; + /// StratifiedSets call for knowledge of "direction", so this is how we /// represent that locally. enum class Level { Same, Above, Below }; @@ -361,145 +371,40 @@ return Fn->isDeclaration() || !Fn->hasLocalLinkage(); } - /// 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; - } - - // Encodes the notion of a "use" - struct Edge { - // Which value the edge is coming from - Value *From; - - // Which value the edge is pointing to - Value *To; - - // Edge weight - EdgeType Weight; - - // Whether we aliased any external values along the way that may be - // invisible to the analysis - StratifiedAttrs FromAttrs, ToAttrs; - }; - - bool - tryInterproceduralAnalysis(const SmallVectorImpl &Fns, - Value *FuncValue, - const iterator_range &Args) { - const unsigned ExpectedMaxArgs = 8; - const unsigned MaxSupportedArgs = 50; + bool tryInterproceduralAnalysis(CallSite CS, + const SmallVectorImpl &Fns) { assert(Fns.size() > 0); - // This algorithm is n^2, so an arbitrary upper-bound of 50 args was - // selected, so it doesn't take too long in insane cases. - if (std::distance(Args.begin(), Args.end()) > (int)MaxSupportedArgs) + if (CS.arg_size() > MaxSupportedArgsInSummary) return false; // Exit early if we'll fail anyway for (auto *Fn : Fns) { if (isFunctionExternal(Fn) || Fn->isVarArg()) return false; + if (Fn->arg_size() > CS.arg_size()) + return false; auto &MaybeInfo = AA.ensureCached(Fn); if (!MaybeInfo.hasValue()) return false; } - SmallVector Output; - SmallVector Arguments(Args.begin(), Args.end()); - SmallVector Parameters; for (auto *Fn : Fns) { - auto &Info = *AA.ensureCached(Fn); - auto &Sets = Info.Sets; - auto &RetVals = Info.ReturnedValues; - - Parameters.clear(); - for (auto &Param : Fn->args()) { - auto MaybeInfo = Sets.find(&Param); - // Did a new parameter somehow get added to the function/slip by? - if (!MaybeInfo.hasValue()) - return false; - Parameters.push_back(*MaybeInfo); - } - - // Adding an edge from argument -> return value for each parameter that - // may alias the return value - for (unsigned I = 0, E = Parameters.size(); I != E; ++I) { - auto &ParamInfo = Parameters[I]; - auto &ArgVal = Arguments[I]; - bool AddEdge = false; - StratifiedAttrs RetAttrs, ParamAttrs; - for (unsigned X = 0, XE = RetVals.size(); X != XE; ++X) { - auto MaybeInfo = Sets.find(RetVals[X]); - if (!MaybeInfo.hasValue()) - return false; - - auto &RetInfo = *MaybeInfo; - RetAttrs |= Sets.getLink(RetInfo.Index).Attrs; - ParamAttrs |= Sets.getLink(ParamInfo.Index).Attrs; - auto MaybeRelation = - getIndexRelation(Sets, ParamInfo.Index, RetInfo.Index); - if (MaybeRelation.hasValue()) - AddEdge = true; - } - if (AddEdge) - Output.push_back( - Edge{FuncValue, ArgVal, EdgeType::Assign, RetAttrs, ParamAttrs}); + auto &FnInfo = AA.ensureCached(Fn); + assert(FnInfo.hasValue()); + + auto &RetParamRelations = FnInfo->RetParamRelations; + for (auto &Relation : RetParamRelations) { + auto FromIndex = Relation.From; + auto ToIndex = Relation.To; + 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()) + Graph.addEdge(FromVal, ToVal, EdgeType::Assign); } - - if (Parameters.size() != Arguments.size()) - return false; - - /// 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 I = 0, E = Arguments.size(); I != E; ++I) { - auto &MainVal = Arguments[I]; - auto &MainInfo = Parameters[I]; - auto &MainAttrs = Sets.getLink(MainInfo.Index).Attrs; - for (unsigned X = I + 1; X != E; ++X) { - auto &SubInfo = Parameters[X]; - auto &SubVal = Arguments[X]; - auto &SubAttrs = Sets.getLink(SubInfo.Index).Attrs; - auto MaybeRelation = - getIndexRelation(Sets, MainInfo.Index, SubInfo.Index); - - if (!MaybeRelation.hasValue()) - continue; - - Output.push_back( - Edge{MainVal, SubVal, EdgeType::Assign, MainAttrs, SubAttrs}); - } - } - } - - // Commit all edges in Output to CFLGraph - for (const auto &Edge : Output) { - addEdge(Edge.From, Edge.To, Edge.Weight); - Graph.addAttr(Edge.From, Edge.FromAttrs); - Graph.addAttr(Edge.To, Edge.ToAttrs); } return true; @@ -511,7 +416,7 @@ // Make sure all arguments and return value are added to the graph first for (Value *V : CS.args()) addNode(V); - if (!Inst->getType()->isVoidTy()) + if (Inst->getType()->isPointerTy()) addNode(Inst); // Check if Inst is a call to a library function that allocates/deallocates @@ -526,7 +431,7 @@ // that we can tack on. SmallVector Targets; if (getPossibleTargets(CS, Targets)) - if (tryInterproceduralAnalysis(Targets, Inst, CS.args())) + if (tryInterproceduralAnalysis(CS, Targets)) return; // Because the function is opaque, we need to note that anything @@ -539,7 +444,7 @@ Escapes.insert(V); } - if (!Inst->getType()->isVoidTy()) { + if (Inst->getType()->isPointerTy()) { auto *Fn = CS.getCalledFunction(); if (Fn == nullptr || !Fn->doesNotAlias(0)) Graph.addAttr(Inst, AttrUnknown); @@ -643,8 +548,10 @@ void addInstructionToGraph(Instruction &Inst) { // 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 (auto RetInst = dyn_cast(&Inst)) + if (auto RetVal = RetInst->getReturnValue()) + if (RetVal->getType()->isPointerTy()) + ReturnedValues.push_back(RetVal); if (!hasUsefulEdges(&Inst)) return; @@ -671,12 +578,16 @@ buildGraphFrom(Fn); } - const CFLGraph &getCFLGraph() { return Graph; } - SmallVector takeReturnValues() { - return std::move(ReturnedValues); + const CFLGraph &getCFLGraph() const { return Graph; } + const SmallVector &getReturnValues() const { + return ReturnedValues; + } + const SmallPtrSet &getExternalValues() const { + return ExternalValues; + } + const SmallPtrSet &getEscapedValues() const { + return EscapedValues; } - const SmallPtrSet &getExternalValues() { return ExternalValues; } - const SmallPtrSet &getEscapedValues() { return EscapedValues; } }; } @@ -788,6 +699,98 @@ 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; +} + +static CFLAAResult::FunctionInfo +buildFunctionInfo(Function *Fn, const SmallVectorImpl &RetVals, + StratifiedSets Sets) { + LLVM_CONSTEXPR unsigned ExpectedMaxArgs = 8; + + // Collect StratifiedInfo for each parameter + SmallVector, ExpectedMaxArgs> ParamInfos; + 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; + for (unsigned I = 0, E = RetVals.size(); I != E; ++I) + RetInfos.push_back(Sets.find(RetVals[I])); + + SmallVector RetParamRelations; + // 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}); + } + + // 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; + + auto MaybeRelation = + getIndexRelation(Sets, MainInfo->Index, RetInfo->Index); + if (!MaybeRelation.hasValue()) + continue; + + RetParamRelations.push_back(ExternalRelation{1 + I, 0}); + } + } + } + + return CFLAAResult::FunctionInfo{std::move(Sets), + std::move(RetParamRelations)}; +} + // Builds the graph + StratifiedSets for a function. CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) { CFLGraphBuilder GraphBuilder(*this, TLI, *Fn); @@ -848,7 +851,8 @@ SetBuilder.addAttributesBelow(Escape, AttrUnknown); } - return FunctionInfo(SetBuilder.build(), GraphBuilder.takeReturnValues()); + return buildFunctionInfo(Fn, GraphBuilder.getReturnValues(), + SetBuilder.build()); } void CFLAAResult::scan(Function *Fn) { Index: test/Analysis/CFLAliasAnalysis/basic-interproc-ret.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/basic-interproc-ret.ll +++ /dev/null @@ -1,26 +0,0 @@ -; This testcase ensures that CFL AA gives conservative answers on variables -; that involve arguments. - -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test -; CHECK: 4 Total Alias Queries Performed -; CHECK: 3 no alias responses -; ^ The 1 MayAlias is due to %arg1. Sadly, we don't currently have machinery -; in place to check whether %arg1 aliases %a, because BasicAA takes care of -; that for us. - -define i32* @test2(i32* %arg1) { - store i32 0, i32* %arg1 - - %a = alloca i32, align 4 - ret i32* %a -} - -define void @test() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %c = call i32* @test2(i32* %a) - - ret void -} Index: test/Analysis/CFLAliasAnalysis/basic-interproc.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/basic-interproc.ll +++ test/Analysis/CFLAliasAnalysis/basic-interproc.ll @@ -1,22 +1,21 @@ -; This testcase ensures that CFL AA gives conservative answers on variables -; that involve arguments. +; This testcase ensures that CFL AA won't be too conservative when trying to do interprocedural analysis on simple callee -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; 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 -; CHECK: Function: test2 +; CHECK-LABEL: Function: noop_callee ; CHECK: MayAlias: i32* %arg1, i32* %arg2 -define void @test2(i32* %arg1, i32* %arg2) { +define void @noop_callee(i32* %arg1, i32* %arg2) { store i32 0, i32* %arg1 store i32 0, i32* %arg2 - ret void } - -define void @test() { +; CHECK-LABEL: Function: test_noop +; CHECK: NoAlias: i32* %a, i32* %b +define void @test_noop() { %a = alloca i32, align 4 %b = alloca i32, align 4 - call void @test2(i32* %a, i32* %b) + call void @noop_callee(i32* %a, i32* %b) ret void } Index: test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll @@ -0,0 +1,20 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to return one of its parameters + +; 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 + +define i32* @return_arg_callee(i32* %arg1, i32* %arg2) { + ret i32* %arg1 +} +; CHECK-LABEL: Function: test_return_arg +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +define void @test_return_arg() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + + %c = call i32* @return_arg_callee(i32* %a, i32* %b) + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll @@ -0,0 +1,49 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to return the multi-level dereference of one of its parameters + +; 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 + ret i32* %deref2 +} +; CHECK-LABEL: Function: test_return_deref_arg_multilevel +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %c, i32** %p +; CHECK: NoAlias: i32* %c, i32*** %pp +; CHECK: MayAlias: i32** %lpp, i32** %p +; CHECK: NoAlias: i32** %lpp, i32*** %pp +; 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 +; CHECK: NoAlias: i32* %lp, i32** %p +; CHECK: NoAlias: i32* %lp, i32*** %pp +; CHECK: MayAlias: i32* %c, i32* %lp +; CHECK: NoAlias: i32* %lp, i32** %lpp +; CHECK: MayAlias: i32* %lp, i32* %lpp_deref +define void @test_return_deref_arg_multilevel() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + %pp = alloca i32**, align 8 + + store i32* %a, i32** %p + store i32** %p, i32*** %pp + %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp) + + %lpp = load i32**, i32*** %pp + %lpp_deref = load i32*, i32** %lpp + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll @@ -0,0 +1,32 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to return the dereference of one of its parameters + +; 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 +} +; CHECK-LABEL: Function: test_return_deref_arg +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: MayAlias: i32* %a, i32* %lp +; CHECK: NoAlias: i32* %b, i32* %lp +; CHECK: NoAlias: i32* %lp, i32** %p +; CHECK: MayAlias: i32* %c, i32* %lp +define void @test_return_deref_arg() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + + store i32* %a, i32** %p + %c = call i32* @return_deref_arg_callee(i32** %p) + + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll @@ -0,0 +1,51 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to return the multi-level reference of one of its parameters + +; 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) { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32*** + %ptr2 = call noalias i8* @malloc(i64 8) + %ptr_cast2 = bitcast i8* %ptr2 to i32** + store i32* %arg1, i32** %ptr_cast2 + store i32** %ptr_cast2, i32*** %ptr_cast + ret i32*** %ptr_cast +} +; 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 +; CHECK: NoAlias: i32* %lb_deref, i32** %lpp +; CHECK: MayAlias: i32* %lb_deref, i32* %lpp_deref +; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp +; CHECK: MayAlias: i32* %lb_deref, i32* %lp +; CHECK: NoAlias: i32* %lp, i32** %lpp +; CHECK: MayAlias: i32* %lp, i32* %lpp_deref +define void @test_return_ref_arg_multilevel() { + %a = alloca i32, align 4 + %p = alloca i32*, align 8 + %pp = alloca i32**, align 8 + + store i32* %a, i32** %p + store i32** %p, i32*** %pp + %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a) + + %lb = load i32**, i32*** %b + %lb_deref = load i32*, i32** %lb + %lpp = load i32**, i32*** %pp + %lpp_deref = load i32*, i32** %lpp + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll @@ -0,0 +1,36 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to return the reference of one of its parameters + +; 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) { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32** + store i32* %arg1, i32** %ptr_cast + 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 +define void @test_return_ref_arg() { + %a = alloca i32, align 4 + %p = alloca i32*, align 8 + + store i32* %a, i32** %p + %b = call i32** @return_ref_arg_callee(i32* %a) + + %lb = load i32*, i32** %b + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll @@ -0,0 +1,26 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to return an unknown pointer + +; 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: * + +@g = external global i32 + +define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) { + ret i32* @g +} +; CHECK-LABEL: Function: test_return_unknown +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +define void @test_return_unknown(i32* %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + + %c = call i32* @return_unknown_callee(i32* %a, i32* %b) + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll @@ -0,0 +1,48 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to mutate the memory pointed to by its parameters + +; 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) { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32** + store i32* %arg2, i32** %ptr_cast + store i32** %ptr_cast, i32*** %arg1 + 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 +; CHECK: MayAlias: i32* %a, i32* %lpp_deref +; CHECK: MayAlias: i32* %b, i32* %lpp_deref +; CHECK: NoAlias: i32* %lpp_deref, i32** %p +; 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 +define void @test_store_arg_multilevel() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + %pp = alloca i32**, align 8 + + store i32* %a, i32** %p + store i32** %p, i32*** %pp + call void @store_arg_multilevel_callee(i32*** %pp, i32* %b) + + %lpp = load i32**, i32*** %pp + %lpp_deref = load i32*, i32** %lpp + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll @@ -0,0 +1,34 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to mutate the memory pointed to by its parameters + +; 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: * + +@g = external global i32 + +define void @store_arg_unknown_callee(i32** %arg1) { + store i32* @g, i32** %arg1 + ret void +} +; CHECK-LABEL: Function: test_store_arg_unknown +; CHECK: NoAlias: i32* %x, i32** %p +; CHECK: NoAlias: i32* %a, i32** %p +; CHECK: NoAlias: i32* %b, i32** %p +; CHECK: MayAlias: i32* %lp, i32* %x +; CHECK: MayAlias: i32* %a, i32* %lp +; CHECK: NoAlias: i32* %b, i32* %lp +; CHECK: MayAlias: 32* %lp, i32** %p +define void @test_store_arg_unknown(i32* %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + + store i32* %a, i32** %p + call void @store_arg_unknown_callee(i32** %p) + + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll @@ -0,0 +1,36 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries to mutate the memory pointed to by its parameters + +; 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 +define void @test_store_arg() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + %q = alloca i32*, align 8 + + store i32* %a, i32** %p + store i32* %b, i32** %q + call void @store_arg_callee(i32** %p, i32* %b) + + %lp = load i32*, i32** %p + %lq = load i32*, i32** %q + + ret void +} \ No newline at end of file