Index: lib/Analysis/AliasAnalysisSummary.h =================================================================== --- lib/Analysis/AliasAnalysisSummary.h +++ lib/Analysis/AliasAnalysisSummary.h @@ -120,6 +120,19 @@ inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) { return !(LHS == RHS); } +inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) { + return LHS.Index < RHS.Index || + (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel); +} +inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) { + return RHS < LHS; +} +inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) { + return !(RHS < LHS); +} +inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) { + return !(LHS < RHS); +} /// We use ExternalRelation to describe an externally visible aliasing relations /// between parameters/return value of a function. @@ -127,6 +140,25 @@ InterfaceValue From, To; }; +inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) { + return LHS.From == RHS.From && LHS.To == RHS.To; +} +inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) { + return !(LHS == RHS); +} +inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) { + return LHS.From < RHS.From || (LHS.From == RHS.From && LHS.To < RHS.To); +} +inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) { + return RHS < LHS; +} +inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) { + return !(RHS < LHS); +} +inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) { + return !(LHS < RHS); +} + /// We use ExternalAttribute to describe an externally visible AliasAttrs /// for parameters/return value. struct ExternalAttribute { Index: lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAndersAliasAnalysis.cpp +++ lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -106,10 +106,17 @@ FlowToMemAliasReadWrite, }; +typedef std::bitset<7> StateSet; +LLVM_CONSTEXPR StateSet ReadOnlyStateMask = + (1 << static_cast(MatchState::FlowFromReadOnly)) | + (1 << static_cast(MatchState::FlowFromMemAliasReadOnly)); +LLVM_CONSTEXPR StateSet WriteOnlyStateMask = + (1 << static_cast(MatchState::FlowToWriteOnly)) | + (1 << static_cast(MatchState::FlowToMemAliasWriteOnly)); + // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in // the paper) during the analysis. class ReachabilitySet { - typedef std::bitset<7> StateSet; typedef DenseMap ValueStateMap; typedef DenseMap ValueReachMap; ValueReachMap ReachMap; @@ -120,6 +127,7 @@ // Insert edge 'From->To' at state 'State' bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) { + assert(From != To); auto &States = ReachMap[To][From]; auto Idx = static_cast(State); if (!States.test(Idx)) { @@ -207,6 +215,14 @@ InstantiatedValue To; MatchState State; }; + +struct ValueSummary { + struct Record { + InterfaceValue IValue; + unsigned DerefLevel; + }; + SmallVector FromRecords, ToRecords; +}; } class CFLAndersAAResult::FunctionInfo { @@ -225,15 +241,39 @@ AliasAttrs getAttrs(const Value *) const; public: - FunctionInfo(const ReachabilitySet &, AliasAttrMap); + FunctionInfo(const Function &, const SmallVectorImpl &, + const ReachabilitySet &, AliasAttrMap); bool mayAlias(const Value *LHS, const Value *RHS) const; const AliasSummary &getAliasSummary() const { return Summary; } }; -CFLAndersAAResult::FunctionInfo::FunctionInfo(const ReachabilitySet &ReachSet, - AliasAttrMap AMap) { - // Populate AttrMap +static bool hasReadOnlyState(StateSet Set) { + return (Set & ReadOnlyStateMask).any(); +} + +static bool hasWriteOnlyState(StateSet Set) { + return (Set & WriteOnlyStateMask).any(); +} + +static Optional +getInterfaceValue(InstantiatedValue IValue, + const SmallVectorImpl &RetVals) { + auto Val = IValue.Val; + + Optional Index; + if (auto Arg = dyn_cast(Val)) + Index = Arg->getArgNo() + 1; + else if (is_contained(RetVals, Val)) + Index = 0; + + if (Index) + return InterfaceValue{*Index, IValue.DerefLevel}; + return None; +} + +static void populateAttrMap(DenseMap &AttrMap, + const AliasAttrMap &AMap) { for (const auto &Mapping : AMap.mappings()) { auto IVal = Mapping.first; @@ -241,8 +281,11 @@ if (IVal.DerefLevel == 0) AttrMap[IVal.Val] = Mapping.second; } +} - // Populate AliasMap +static void +populateAliasMap(DenseMap> &AliasMap, + const ReachabilitySet &ReachSet) { for (const auto &OuterMapping : ReachSet.value_mappings()) { // AliasMap only cares about top-level values if (OuterMapping.first.DerefLevel > 0) @@ -259,8 +302,112 @@ // Sort AliasList for faster lookup std::sort(AliasList.begin(), AliasList.end(), std::less()); } +} + +static void populateExternalRelations( + SmallVectorImpl &ExtRelations, const Function &Fn, + const SmallVectorImpl &RetVals, const ReachabilitySet &ReachSet) { + // If a function only returns one of its argument X, then X will be both an + // argument and a return value at the same time. This is an edge case that + // needs special handling here. + for (const auto &Arg : Fn.args()) { + if (is_contained(RetVals, &Arg)) { + auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0}; + auto RetVal = InterfaceValue{0, 0}; + ExtRelations.push_back(ExternalRelation{ArgVal, RetVal}); + } + } + + // Below is the core summary construction logic. + // A naive solution of adding only the value aliases that are parameters or + // return values in ReachSet to the summary won't work: It is possible that a + // parameter P is written into an intermediate value I, and the function + // subsequently returns *I. In that case, *I is does not value alias anything + // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to + // (I, 1). + // To account for the aforementioned case, we need to check each non-parameter + // and non-return value for the possibility of acting as an intermediate. + // 'ValueMap' here records, for each value, which InterfaceValues read from or + // write into it. If both the read list and the write list of a given value + // are non-empty, we know that a particular value is an intermidate and we + // need to add summary edges from the writes to the reads. + DenseMap ValueMap; + for (const auto &OuterMapping : ReachSet.value_mappings()) { + if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) { + for (const auto &InnerMapping : OuterMapping.second) { + // If Src is a param/return value, we get a same-level assignment. + if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) { + // This may happen if both Dst and Src are return values + if (*Dst == *Src) + continue; + + if (hasReadOnlyState(InnerMapping.second)) + ExtRelations.push_back(ExternalRelation{*Dst, *Src}); + // No need to check for WriteOnly state, since ReachSet is symmetric + } else { + // If Src is not a param/return, add it to ValueMap + auto SrcIVal = InnerMapping.first; + if (hasReadOnlyState(InnerMapping.second)) + ValueMap[SrcIVal.Val].FromRecords.push_back( + ValueSummary::Record{*Dst, SrcIVal.DerefLevel}); + if (hasWriteOnlyState(InnerMapping.second)) + ValueMap[SrcIVal.Val].ToRecords.push_back( + ValueSummary::Record{*Dst, SrcIVal.DerefLevel}); + } + } + } + } + + for (const auto &Mapping : ValueMap) { + for (const auto &FromRecord : Mapping.second.FromRecords) { + for (const auto &ToRecord : Mapping.second.ToRecords) { + auto ToLevel = ToRecord.DerefLevel; + auto FromLevel = FromRecord.DerefLevel; + // Same-level assignments should have already been processed by now + if (ToLevel == FromLevel) + continue; + + auto SrcIndex = FromRecord.IValue.Index; + auto SrcLevel = FromRecord.IValue.DerefLevel; + auto DstIndex = ToRecord.IValue.Index; + auto DstLevel = ToRecord.IValue.DerefLevel; + if (ToLevel > FromLevel) + SrcLevel += ToLevel - FromLevel; + else + DstLevel += FromLevel - ToLevel; + + ExtRelations.push_back( + ExternalRelation{InterfaceValue{SrcIndex, SrcLevel}, + InterfaceValue{DstIndex, DstLevel}}); + } + } + } + + // Remove duplicates in ExtRelations + std::sort(ExtRelations.begin(), ExtRelations.end()); + ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()), + ExtRelations.end()); +} + +static void populateExternalAttributes( + SmallVectorImpl &ExtAttributes, const Function &Fn, + const SmallVectorImpl &RetVals, const AliasAttrMap &AMap) { + for (const auto &Mapping : AMap.mappings()) { + if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) { + auto Attr = getExternallyVisibleAttrs(Mapping.second); + if (Attr.any()) + ExtAttributes.push_back(ExternalAttribute{*IVal, Attr}); + } + } +} - // TODO: Populate function summary here +CFLAndersAAResult::FunctionInfo::FunctionInfo( + const Function &Fn, const SmallVectorImpl &RetVals, + const ReachabilitySet &ReachSet, AliasAttrMap AMap) { + populateAttrMap(AttrMap, AMap); + populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap); + populateAliasMap(AliasMap, ReachSet); + populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet); } AliasAttrs CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const { @@ -510,7 +657,8 @@ // to it auto IValueAttrMap = buildAttrMap(Graph, ReachSet); - return FunctionInfo(ReachSet, std::move(IValueAttrMap)); + return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet, + std::move(IValueAttrMap)); } void CFLAndersAAResult::scan(const Function &Fn) { Index: test/Analysis/CFLAliasAnalysis/Andersen/basic-interproc.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/basic-interproc.ll @@ -0,0 +1,22 @@ +; 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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: noop_callee +; CHECK: MayAlias: i32* %arg1, i32* %arg2 +define void @noop_callee(i32* %arg1, i32* %arg2) { + store i32 0, i32* %arg1 + store i32 0, i32* %arg2 + ret void +} +; 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 @noop_callee(i32* %a, i32* %b) + + ret void +} Index: test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-deref-escape.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-deref-escape.ll @@ -0,0 +1,33 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to escape the memory pointed to by its parameters + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare void @opaque(i32*) +define void @escape_arg_deref(i32** %arg) { + %arg_deref = load i32*, i32** %arg + call void @opaque(i32* %arg_deref) + ret void +} +; CHECK-LABEL: Function: test_arg_deref_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32** %p, i32** %x +; CHECK: NoAlias: i32* %a, i32** %p +; CHECK: NoAlias: i32* %b, i32** %p +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %c, i32** %p +define void @test_arg_deref_escape(i32** %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 4 + + store i32* %a, i32** %p + call void @escape_arg_deref(i32** %p) + %c = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-escape.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-escape.ll @@ -0,0 +1,31 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to escape its parameters + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare void @opaque(i32*) +define void @escape_arg(i32* %arg) { + call void @opaque(i32* %arg) + ret void +} +; CHECK-LABEL: Function: test_arg_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32* %c, i32** %x +; CHECK: NoAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: MayAlias: i32* %a, i32* %d +; CHECK: MayAlias: i32* %b, i32* %d +; CHECK: NoAlias: i32* %c, i32* %d +define void @test_arg_escape(i32** %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %c = alloca i32, align 4 + call void @escape_arg(i32* %a) + call void @escape_arg(i32* %b) + %d = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg.ll @@ -0,0 +1,21 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return one of its parameters + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-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/Andersen/interproc-ret-deref-arg-multilevel.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-multilevel.ll @@ -0,0 +1,46 @@ +; 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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +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: 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/Andersen/interproc-ret-deref-arg.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg.ll @@ -0,0 +1,30 @@ +; 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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +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/Andersen/interproc-ret-escape.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-escape.ll @@ -0,0 +1,33 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return an escaped pointer + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare noalias i8* @malloc(i64) +declare void @opaque(i32*) + +define i32* @return_escaped_callee() { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32* + call void @opaque(i32* %ptr_cast) + ret i32* %ptr_cast +} +; CHECK-LABEL: Function: test_return_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32* %c, i32** %x +; CHECK: NoAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %a, i32* %d +; CHECK: MayAlias: i32* %b, i32* %d +; CHECK: MayAlias: i32* %c, i32* %d +define void @test_return_escape(i32** %x) { + %a = alloca i32, align 4 + %b = call i32* @return_escaped_callee() + %c = call i32* @return_escaped_callee() + %d = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg-multilevel.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg-multilevel.ll @@ -0,0 +1,49 @@ +; 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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +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/Andersen/interproc-ret-ref-arg.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg.ll @@ -0,0 +1,34 @@ +; 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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +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/Andersen/interproc-ret-unknown.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-unknown.ll @@ -0,0 +1,38 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return an unknown pointer + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +@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 +} + +@g2 = external global i32* +define i32** @return_unknown_callee2() { + ret i32** @g2 +} +; CHECK-LABEL: Function: test_return_unknown2 +; CHECK: MayAlias: i32* %x, i32** %a +; CHECK: MayAlias: i32* %b, i32* %x +; CHECK: MayAlias: i32* %b, i32** %a +define void @test_return_unknown2(i32* %x) { + %a = call i32** @return_unknown_callee2() + %b = load i32*, i32** %a + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-multilevel.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-multilevel.ll @@ -0,0 +1,45 @@ +; 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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +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* %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/Andersen/interproc-store-arg-unknown.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-unknown.ll @@ -0,0 +1,32 @@ +; 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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +@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: NoAlias: i32* %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/Andersen/interproc-store-arg.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg.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-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +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: MayAlias: 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 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll @@ -29,7 +29,6 @@ ; 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