Index: lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAndersAliasAnalysis.cpp +++ lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -156,6 +156,38 @@ } }; +// We use AliasAttrMap to keep track of the AliasAttr of each node +class AliasAttrMap { + typedef DenseMap MapType; + MapType AttrMap; + +public: + typedef MapType::const_iterator const_iterator; + + bool insert(InstantiatedValue V, AliasAttrs Attr) { + if (Attr.none()) + return false; + auto &OldAttr = AttrMap[V]; + auto NewAttr = OldAttr | Attr; + if (OldAttr == NewAttr) + return false; + OldAttr = NewAttr; + return true; + } + + AliasAttrs getAttrs(InstantiatedValue V) const { + AliasAttrs Attr; + auto Itr = AttrMap.find(V); + if (Itr != AttrMap.end()) + Attr = Itr->second; + return Attr; + } + + iterator_range mappings() const { + return make_range(AttrMap.begin(), AttrMap.end()); + } +}; + struct WorkListItem { InstantiatedValue From; InstantiatedValue To; @@ -170,17 +202,33 @@ /// AliasMap[a] but not vice versa. DenseMap> AliasMap; + /// Map a value to its corresponding AliasAttrs + DenseMap AttrMap; + /// Summary of externally visible effects. AliasSummary Summary; + AliasAttrs getAttrs(const Value *) const; + public: - FunctionInfo(const ReachabilitySet &); + FunctionInfo(const ReachabilitySet &, const AliasAttrMap &); bool mayAlias(const Value *LHS, const Value *RHS) const; const AliasSummary &getAliasSummary() const { return Summary; } }; -CFLAndersAAResult::FunctionInfo::FunctionInfo(const ReachabilitySet &ReachSet) { +CFLAndersAAResult::FunctionInfo::FunctionInfo(const ReachabilitySet &ReachSet, + const AliasAttrMap &AMap) { + // Populate AttrMap + for (const auto &Mapping : AMap.mappings()) { + auto IVal = Mapping.first; + + // AttrMap only cares about top-level values + if (IVal.DerefLevel == 0) + AttrMap[IVal.Val] = Mapping.second; + } + + // Populate AliasMap for (const auto &OuterMapping : ReachSet.value_mappings()) { // AliasMap only cares about top-level values if (OuterMapping.first.DerefLevel > 0) @@ -201,6 +249,16 @@ // TODO: Populate function summary here } +AliasAttrs CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const { + assert(V != nullptr); + + AliasAttrs Attr; + auto Itr = AttrMap.find(V); + if (Itr != AttrMap.end()) + Attr = Itr->second; + return Attr; +} + bool CFLAndersAAResult::FunctionInfo::mayAlias(const Value *LHS, const Value *RHS) const { assert(LHS && RHS); @@ -208,12 +266,23 @@ std::swap(LHS, RHS); auto Itr = AliasMap.find(LHS); - if (Itr == AliasMap.end()) - return false; + if (Itr != AliasMap.end()) { + if (std::binary_search(Itr->second.begin(), Itr->second.end(), RHS)) + return true; + } - // TODO: Check AliasAttrs before drawing any conclusions + // Even if LHS and RHS are not reachable, they may still alias due to their + // AliasAttrs + auto AttrsA = getAttrs(LHS); + auto AttrsB = getAttrs(RHS); - return std::binary_search(Itr->second.begin(), Itr->second.end(), RHS); + if (AttrsA.none() || AttrsB.none()) + return false; + if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB)) + return true; + if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB)) + return true; + return false; } static void propagate(InstantiatedValue From, InstantiatedValue To, @@ -264,7 +333,6 @@ auto NodeInfo = Graph.getNode(ToNode); assert(NodeInfo != nullptr); - // TODO: propagate AliasAttr as well // TODO: propagate field offsets // The newly added value alias pair may pontentially generate more memory @@ -338,6 +406,34 @@ } } +static AliasAttrMap buildAttrMap(const CFLGraph &Graph, + const ReachabilitySet &ReachSet) { + AliasAttrMap AttrMap; + + // Initialize each node with its original AliasAttrs in CFLGraph + for (const auto &Mapping : Graph.value_mappings()) { + auto Val = Mapping.first; + auto &ValueInfo = Mapping.second; + for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) { + auto Node = InstantiatedValue{Val, I}; + AttrMap.insert(Node, ValueInfo.getNodeInfoAtLevel(I).Attr); + } + } + + for (const auto &OuterMapping : ReachSet.value_mappings()) { + auto Dst = OuterMapping.first; + for (const auto &InnerMapping : OuterMapping.second) { + auto Src = InnerMapping.first; + + // Reachability is symmetric. We need to insert both ways + AttrMap.insert(Dst, Graph.attrFor(Src)); + AttrMap.insert(Src, Graph.attrFor(Dst)); + } + } + + return AttrMap; +} + CFLAndersAAResult::FunctionInfo CFLAndersAAResult::buildInfoFrom(const Function &Fn) { CFLGraphBuilder GraphBuilder( @@ -360,7 +456,11 @@ NextList.clear(); } - return FunctionInfo(ReachSet); + // Now that we have all the reachability info, propagate AliasAttrs according + // to it + auto IValueAttrMap = buildAttrMap(Graph, ReachSet); + + return FunctionInfo(ReachSet, IValueAttrMap); } void CFLAndersAAResult::scan(const Function &Fn) { Index: test/Analysis/CFLAliasAnalysis/Andersen/attrs.ll =================================================================== --- /dev/null +++ test/Analysis/CFLAliasAnalysis/Andersen/attrs.ll @@ -0,0 +1,94 @@ +; This testcase ensures that CFL AA handles escaped values no more conservative than it should + +; 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: test_local +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %a, i32* %aAlias +; CHECK: NoAlias: i32* %aAlias, i32* %b +define void @test_local() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %aint = ptrtoint i32* %a to i64 + %aAlias = inttoptr i64 %aint to i32* + ret void +} + +; CHECK-LABEL: Function: test_global_param +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: MayAlias: i32* %a, i32* %xload +; CHECK: MayAlias: i32* %a, i32* %gload +; CHECK: MayAlias: i32* %gload, i32* %xload +; CHECK: MayAlias: i32** %x, i32** @ext_global +; CHECK: NoAlias: i32* %a, i32** @ext_global +@ext_global = external global i32* +define void @test_global_param(i32** %x) { + %a = alloca i32, align 4 + %aint = ptrtoint i32* %a to i64 + %xload = load i32*, i32** %x + %gload = load i32*, i32** @ext_global + ret void +} + +declare void @external_func(i32**) +; CHECK-LABEL: Function: test_external_call +; CHECK: NoAlias: i32* %b, i32* %x +; CHECK: NoAlias: i32* %b, i32** %a +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: MayAlias: i32* %c, i32** %a +; CHECK: NoAlias: i32* %b, i32* %c +define void @test_external_call(i32* %x) { + %a = alloca i32*, align 8 + %b = alloca i32, align 4 + call void @external_func(i32** %a) + %c = load i32*, i32** %a + ret void +} + +declare void @external_func_readonly(i32**) readonly +; CHECK-LABEL: Function: test_external_call_func_readonly +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %c, i32** %a +define void @test_external_call_func_readonly(i32* %x) { + %a = alloca i32*, align 8 + %b = alloca i32, align 4 + store i32* %x, i32** %a, align 4 + call void @external_func_readonly(i32** %a) + %c = load i32*, i32** %a + ret void +} + +; CHECK-LABEL: Function: test_external_call_callsite_readonly +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %c, i32** %a +define void @test_external_call_callsite_readonly(i32* %x) { + %a = alloca i32*, align 8 + %b = alloca i32, align 4 + store i32* %x, i32** %a, align 4 + call void @external_func(i32** %a) readonly + %c = load i32*, i32** %a + ret void +} + +declare i32* @external_func_normal_return(i32*) +; CHECK-LABEL: Function: test_external_call_normal_return +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: MayAlias: i32* %a, i32* %c +define void @test_external_call_normal_return(i32* %x) { + %a = alloca i32, align 8 + %b = alloca i32, align 4 + %c = call i32* @external_func_normal_return(i32* %a) + ret void +} + +declare noalias i32* @external_func_noalias_return(i32*) +; CHECK-LABEL: Function: test_external_call_noalias_return +; CHECK: NoAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %a, i32* %c +define void @test_external_call_noalias_return(i32* %x) { + %a = alloca i32, align 8 + %b = alloca i32, align 4 + %c = call i32* @external_func_noalias_return(i32* %a) + ret void +}