Index: lib/Analysis/AliasAnalysisSummary.h =================================================================== --- lib/Analysis/AliasAnalysisSummary.h +++ lib/Analysis/AliasAnalysisSummary.h @@ -145,6 +145,13 @@ // FIXME: Do we need to guard against integer overflow here? return LHS + RHS; } +inline int64_t subOffset(int64_t LHS, int64_t RHS) { + if (LHS == UnknownOffset || RHS == UnknownOffset) + return UnknownOffset; + // FIXME: Do we need to guard against integer overflow here? + return LHS - RHS; +} +inline int64_t negOffset(int64_t Offset) { return subOffset(0, Offset); } /// We use ExternalRelation to describe an externally visible aliasing relations /// between parameters/return value of a function. Index: lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAndersAliasAnalysis.cpp +++ lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -139,11 +139,55 @@ bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) { return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset; } +} + +// Specialize DenseMapInfo for OffsetValue. +template <> struct DenseMapInfo { + static OffsetValue getEmptyKey() { + return OffsetValue{DenseMapInfo::getEmptyKey(), + DenseMapInfo::getEmptyKey()}; + } + static OffsetValue getTombstoneKey() { + return OffsetValue{DenseMapInfo::getTombstoneKey(), + DenseMapInfo::getEmptyKey()}; + } + static unsigned getHashValue(const OffsetValue &OVal) { + return DenseMapInfo>::getHashValue( + std::make_pair(OVal.Val, OVal.Offset)); + } + static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) { + return LHS == RHS; + } +}; + +// Specialize DenseMapInfo for OffsetInstantiatedValue. +template <> struct DenseMapInfo { + static OffsetInstantiatedValue getEmptyKey() { + return OffsetInstantiatedValue{ + DenseMapInfo::getEmptyKey(), + DenseMapInfo::getEmptyKey()}; + } + static OffsetInstantiatedValue getTombstoneKey() { + return OffsetInstantiatedValue{ + DenseMapInfo::getTombstoneKey(), + DenseMapInfo::getEmptyKey()}; + } + static unsigned getHashValue(const OffsetInstantiatedValue &OVal) { + return DenseMapInfo>::getHashValue( + std::make_pair(OVal.IVal, OVal.Offset)); + } + static bool isEqual(const OffsetInstantiatedValue &LHS, + const OffsetInstantiatedValue &RHS) { + return LHS == RHS; + } +}; + +namespace { // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in // the paper) during the analysis. class ReachabilitySet { - typedef DenseMap ValueStateMap; + typedef DenseMap ValueStateMap; typedef DenseMap ValueReachMap; ValueReachMap ReachMap; @@ -152,9 +196,10 @@ typedef ValueReachMap::const_iterator const_value_iterator; // Insert edge 'From->To' at state 'State' - bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) { + bool insert(InstantiatedValue From, InstantiatedValue To, int64_t Offset, + MatchState State) { assert(From != To); - auto &States = ReachMap[To][From]; + auto &States = ReachMap[To][OffsetInstantiatedValue{From, Offset}]; auto Idx = static_cast(State); if (!States.test(Idx)) { States.set(Idx); @@ -239,6 +284,7 @@ struct WorkListItem { InstantiatedValue From; InstantiatedValue To; + int64_t Offset; MatchState State; }; @@ -246,52 +292,12 @@ struct Record { InterfaceValue IValue; unsigned DerefLevel; + int64_t Offset; }; SmallVector FromRecords, ToRecords; }; } -// Specialize DenseMapInfo for OffsetValue. -template <> struct DenseMapInfo { - static OffsetValue getEmptyKey() { - return OffsetValue{DenseMapInfo::getEmptyKey(), - DenseMapInfo::getEmptyKey()}; - } - static OffsetValue getTombstoneKey() { - return OffsetValue{DenseMapInfo::getTombstoneKey(), - DenseMapInfo::getEmptyKey()}; - } - static unsigned getHashValue(const OffsetValue &OVal) { - return DenseMapInfo>::getHashValue( - std::make_pair(OVal.Val, OVal.Offset)); - } - static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) { - return LHS == RHS; - } -}; - -// Specialize DenseMapInfo for OffsetInstantiatedValue. -template <> struct DenseMapInfo { - static OffsetInstantiatedValue getEmptyKey() { - return OffsetInstantiatedValue{ - DenseMapInfo::getEmptyKey(), - DenseMapInfo::getEmptyKey()}; - } - static OffsetInstantiatedValue getTombstoneKey() { - return OffsetInstantiatedValue{ - DenseMapInfo::getTombstoneKey(), - DenseMapInfo::getEmptyKey()}; - } - static unsigned getHashValue(const OffsetInstantiatedValue &OVal) { - return DenseMapInfo>::getHashValue( - std::make_pair(OVal.IVal, OVal.Offset)); - } - static bool isEqual(const OffsetInstantiatedValue &LHS, - const OffsetInstantiatedValue &RHS) { - return LHS == RHS; - } -}; - class CFLAndersAAResult::FunctionInfo { /// Map a value to other values that may alias it /// Since the alias relation is symmetric, to save some space we assume values @@ -361,9 +367,10 @@ auto Val = OuterMapping.first.Val; auto &AliasList = AliasMap[Val]; for (const auto &InnerMapping : OuterMapping.second) { + auto OVal = InnerMapping.first; // Again, AliasMap only cares about top-level values - if (InnerMapping.first.DerefLevel == 0) - AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset}); + if (OVal.IVal.DerefLevel == 0) + AliasList.push_back(OffsetValue{OVal.IVal.Val, negOffset(OVal.Offset)}); } // Sort AliasList for faster lookup @@ -402,24 +409,26 @@ for (const auto &OuterMapping : ReachSet.value_mappings()) { if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) { for (const auto &InnerMapping : OuterMapping.second) { + auto OVal = InnerMapping.first; + auto SrcIVal = OVal.IVal; + auto Offset = OVal.Offset; // If Src is a param/return value, we get a same-level assignment. - if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) { + if (auto Src = getInterfaceValue(SrcIVal, 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, UnknownOffset}); + ExtRelations.push_back(ExternalRelation{*Dst, *Src, Offset}); // 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}); + ValueSummary::Record{*Dst, SrcIVal.DerefLevel, Offset}); if (hasWriteOnlyState(InnerMapping.second)) ValueMap[SrcIVal.Val].ToRecords.push_back( - ValueSummary::Record{*Dst, SrcIVal.DerefLevel}); + ValueSummary::Record{*Dst, SrcIVal.DerefLevel, Offset}); } } } @@ -436,16 +445,22 @@ auto SrcIndex = FromRecord.IValue.Index; auto SrcLevel = FromRecord.IValue.DerefLevel; + auto SrcOffset = FromRecord.Offset; auto DstIndex = ToRecord.IValue.Index; auto DstLevel = ToRecord.IValue.DerefLevel; + auto DstOffset = ToRecord.Offset; + if (ToLevel > FromLevel) SrcLevel += ToLevel - FromLevel; else DstLevel += FromLevel - ToLevel; - ExtRelations.push_back(ExternalRelation{ - InterfaceValue{SrcIndex, SrcLevel}, - InterfaceValue{DstIndex, DstLevel}, UnknownOffset}); + // FIXME: The following ExternalRelation is INCORRECT when SrcLevel > 0 + // or DstLevel > 0. + ExtRelations.push_back( + ExternalRelation{InterfaceValue{SrcIndex, SrcLevel}, + InterfaceValue{DstIndex, DstLevel}, + subOffset(SrcOffset, DstOffset)}); } } } @@ -555,12 +570,13 @@ } static void propagate(InstantiatedValue From, InstantiatedValue To, - MatchState State, ReachabilitySet &ReachSet, + int64_t Offset, MatchState State, + ReachabilitySet &ReachSet, std::vector &WorkList) { if (From == To) return; - if (ReachSet.insert(From, To, State)) - WorkList.push_back(WorkListItem{From, To, State}); + if (ReachSet.insert(From, To, Offset, State)) + WorkList.push_back(WorkListItem{From, To, Offset, State}); } static void initializeWorkList(std::vector &WorkList, @@ -574,13 +590,14 @@ // Insert all immediate assignment neighbors to the worklist for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) { auto Src = InstantiatedValue{Val, I}; - // If there's an assignment edge from X to Y, it means Y is reachable from - // X at S2 and X is reachable from Y at S1 + // If there's an assignment edge from X + Offset to Y, it means (Y - + // Offset) is reachable from X at state FlowToWriteOnly and (X + Offset) + // is reachable from Y at state FlowFromReadOnly for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) { - propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet, - WorkList); - propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet, - WorkList); + propagate(Edge.Other, Src, Edge.Offset, MatchState::FlowFromReadOnly, + ReachSet, WorkList); + propagate(Src, Edge.Other, negOffset(Edge.Offset), + MatchState::FlowToWriteOnly, ReachSet, WorkList); } } } @@ -599,6 +616,7 @@ std::vector &WorkList) { auto FromNode = Item.From; auto ToNode = Item.To; + auto Offset = Item.Offset; auto NodeInfo = Graph.getNode(ToNode); assert(NodeInfo != nullptr); @@ -611,25 +629,31 @@ // The newly added value alias pair may pontentially generate more memory // alias pairs. Check for them here. - auto FromNodeBelow = getNodeBelow(Graph, FromNode); - auto ToNodeBelow = getNodeBelow(Graph, ToNode); - if (FromNodeBelow && ToNodeBelow && - MemSet.insert(*FromNodeBelow, *ToNodeBelow)) { - propagate(*FromNodeBelow, *ToNodeBelow, - MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList); - for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) { - auto Src = Mapping.first; - auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) { - if (Mapping.second.test(static_cast(FromState))) - propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList); - }; - - MemAliasPropagate(MatchState::FlowFromReadOnly, - MatchState::FlowFromMemAliasReadOnly); - MemAliasPropagate(MatchState::FlowToWriteOnly, - MatchState::FlowToMemAliasWriteOnly); - MemAliasPropagate(MatchState::FlowToReadWrite, - MatchState::FlowToMemAliasReadWrite); + // Note that MemAlias reachability can only be triggered when Offset is 0 or + // Unknown + if (Offset == 0 || Offset == UnknownOffset) { + auto FromNodeBelow = getNodeBelow(Graph, FromNode); + auto ToNodeBelow = getNodeBelow(Graph, ToNode); + if (FromNodeBelow && ToNodeBelow && + MemSet.insert(*FromNodeBelow, *ToNodeBelow)) { + propagate(*FromNodeBelow, *ToNodeBelow, Offset, + MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList); + for (const auto &Mapping : + ReachSet.reachableValueAliases(*FromNodeBelow)) { + auto SrcOVal = Mapping.first; + auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) { + if (Mapping.second.test(static_cast(FromState))) + propagate(SrcOVal.IVal, *ToNodeBelow, SrcOVal.Offset, ToState, + ReachSet, WorkList); + }; + + MemAliasPropagate(MatchState::FlowFromReadOnly, + MatchState::FlowFromMemAliasReadOnly); + MemAliasPropagate(MatchState::FlowToWriteOnly, + MatchState::FlowToMemAliasWriteOnly); + MemAliasPropagate(MatchState::FlowToReadWrite, + MatchState::FlowToMemAliasReadWrite); + } } } @@ -643,16 +667,20 @@ // should precede any assignment edges on the path from X to Y. auto NextAssignState = [&](MatchState State) { for (const auto &AssignEdge : NodeInfo->Edges) - propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList); + propagate(FromNode, AssignEdge.Other, + subOffset(Offset, AssignEdge.Offset), State, ReachSet, + WorkList); }; auto NextRevAssignState = [&](MatchState State) { for (const auto &RevAssignEdge : NodeInfo->ReverseEdges) - propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList); + propagate(FromNode, RevAssignEdge.Other, + addOffset(Offset, RevAssignEdge.Offset), State, ReachSet, + WorkList); }; auto NextMemState = [&](MatchState State) { if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) { for (const auto &MemAlias : *AliasSet) - propagate(FromNode, MemAlias, State, ReachSet, WorkList); + propagate(FromNode, MemAlias, Offset, State, ReachSet, WorkList); } }; @@ -718,7 +746,7 @@ // Propagate attr on the same level for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) { - auto Src = Mapping.first; + auto Src = Mapping.first.IVal; if (AttrMap.add(Src, DstAttr)) NextList.push_back(Src); } Index: lib/Analysis/CFLGraph.h =================================================================== --- lib/Analysis/CFLGraph.h +++ lib/Analysis/CFLGraph.h @@ -368,7 +368,7 @@ if (IRelation.hasValue()) { Graph.addNode(IRelation->From); Graph.addNode(IRelation->To); - Graph.addEdge(IRelation->From, IRelation->To); + Graph.addEdge(IRelation->From, IRelation->To, IRelation->Offset); } } Index: test/Analysis/CFLAliasAnalysis/Andersen/gep_basic.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/gep_basic.ll @@ -0,0 +1,25 @@ +; This testcase ensures that CFLAA correctly handles basic field offset +; calculation. + +; 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: Function: test_basic_gep +; CHECK: MayAlias: [3 x i32]* %a, i32* %a4 +; CHECK: MayAlias: [3 x i32]* %a, i32* %a8 +; CHECK: NoAlias: i32* %a4, i32* %a8 +; CHECK: MayAlias: [3 x i32]* %a, i32* %b +; CHECK: NoAlias: i32* %a4, i32* %b +; CHECK: NoAlias: i32* %a8, i32* %b +; CHECK: MayAlias: [3 x i32]* %a, i32* %b4 +; CHECK: MayAlias: i32* %a4, i32* %b4 +; CHECK: NoAlias: i32* %a8, i32* %b4 +; CHECK: NoAlias: i32* %b, i32* %b4 +define void @test_basic_gep() { + %a = alloca [3 x i32], align 4 + %a4 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 1 + %a8 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 2 + %b = bitcast [3 x i32]* %a to i32* + %b4 = getelementptr inbounds i32, i32* %b, i32 1 + ret void +} Index: test/Analysis/CFLAliasAnalysis/Andersen/gep_memalias.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/gep_memalias.ll @@ -0,0 +1,27 @@ +; This testcase ensures that CFLAA correctly handles aliasing patterns that +; involves both field arithmetic and reference/dereference + +; 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: Function: test_mem_gep +; CHECK: NoAlias: i64* %b, i64** %acast +; CHECK: NoAlias: i64** %acast, i64** %aoff +; CHECK: NoAlias: i64* %b, i64** %acastoff +; CHECK: NoAlias: i64** %acast, i64** %acastoff +; CHECK: NoAlias: [2 x i64*]* %a, i64* %acastload +; CHECK: MayAlias: i64* %acastload, i64* %b +; CHECK: NoAlias: i64* %acastload, i64** %aoff +; CHECK: NoAlias: i64* %acastload, i64** %acast +; CHECK: NoAlias: i64* %acastload, i64** %acastoff +define void @test_mem_gep() { + %a = alloca [2 x i64*], align 8 + %b = alloca i64, align 4 + %aoff = getelementptr inbounds [2 x i64*], [2 x i64*]* %a, i64 0, i64 1 + store i64* %b, i64** %aoff + + %acast = bitcast [2 x i64*]* %a to i64** + %acastoff = getelementptr inbounds i64*, i64** %acast, i64 1 + %acastload = load i64*, i64** %acastoff + ret void +} Index: test/Analysis/CFLAliasAnalysis/Andersen/gep_unknown.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/gep_unknown.ll @@ -0,0 +1,25 @@ +; This testcase ensures that CFLAA correctly handles field offset +; calculations that involve UnknownOffset. + +; 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: Function: test_unknown_gep +; CHECK: MayAlias: [3 x i32]* %a, i32* %an +; CHECK: MayAlias: i32* %a4, i32* %an +; CHECK: MayAlias: i32* %a8, i32* %an +; CHECK: MayAlias: i32* %an, i32* %b +; CHECK: MayAlias: [3 x i32]* %a, i32* %bn +; CHECK: MayAlias: i32* %a4, i32* %bn +; CHECK: MayAlias: i32* %a8, i32* %bn +; CHECK: MayAlias: i32* %an, i32* %bn +; CHECK: MayAlias: i32* %b, i32* %bn +define void @test_unknown_gep(i32 %n) { + %a = alloca [3 x i32], align 4 + %a4 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 1 + %a8 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 2 + %an = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 %n + %b = bitcast [3 x i32]* %a to i32* + %bn = getelementptr inbounds i32, i32* %b, i32 %n + ret void +} Index: test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg-gep.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg-gep.ll @@ -0,0 +1,30 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return one of its parameters with certain field offset + +; 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 + +%S = type { i32, i32, i32 } + +define i32* @return_arg_gep(%S* %arg1, %S* %arg2) { + %acast = bitcast %S* %arg1 to i32* + %aoffset = getelementptr i32, i32* %acast, i32 1 + ret i32* %aoffset +} +; CHECK-LABEL: Function: test_return_arg_gep +; CHECK: NoAlias: %S* %a, %S* %b +; CHECK: MayAlias: %S* %a, i32* %c +; CHECK: NoAlias: %S* %b, i32* %c +; CHECK: NoAlias: i32* %acast, i32* %c +; CHECK: NoAlias: i32* %acast, i32* %d +define void @test_return_arg_gep() { + %a = alloca %S, align 8 + %b = alloca %S, align 8 + + %c = call i32* @return_arg_gep(%S* %a, %S* %b) + %d = getelementptr %S, %S* %a, i32 0, i32 1 + ; We need %acast here for precise offset checking (it has smaller Size) + %acast = bitcast %S* %a to i32* + + ret void +} \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-gep.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-gep.ll @@ -0,0 +1,38 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return the dereference of one of its parameters with field offsets + +; 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 + +%S = type { i32, i32, i32 } + +define i32* @return_deref_arg_gep(%S** %arg1) { + %deref = load %S*, %S** %arg1 + %deref_off = getelementptr %S, %S* %deref, i32 0, i32 1 + ret i32* %deref_off +} +; CHECK-LABEL: Function: test_return_deref_arg_gep +; CHECK: NoAlias: %S** %p, i32* %c +; CHECK: NoAlias: %S* %lp, %S** %p +; CHECK: MayAlias: %S* %lp, i32* %c +; CHECK: NoAlias: %S** %p, i32* %lp_off +; CHECK: MayAlias: i32* %c, i32* %lp_off +; CHECK: MayAlias: %S* %lp, i32* %lp_off +; CHECK: NoAlias: %S** %p, i32* %acast +; CHECK: NoAlias: i32* %acast, i32* %c +; CHECK: MayAlias: %S* %lp, i32* %acast +; CHECK: NoAlias: i32* %acast, i32* %lp_off +define void @test_return_deref_arg_gep() { + %a = alloca %S, align 8 + %p = alloca %S*, align 8 + + store %S* %a, %S** %p + %c = call i32* @return_deref_arg_gep(%S** %p) + + %lp = load %S*, %S** %p + %lp_off = getelementptr %S, %S* %lp, i32 0, i32 1 + ; We need %acast here for precise offset checking (it has smaller Size) + %acast = bitcast %S* %a to i32* + + ret void +} \ No newline at end of file