[CFLAA] Add support for AliasAttrs in CFLAndersAliasAnalysis

[grievejia]

Summary

This patch teaches CFLAnders to understand AliasAttrs properly.

Initially I thought that propagating AliasAttrs should be performed along with propagating ReachSet. However, after several attempts I settled down on the current implementation where AliasAttrs are propagated after ReachSet has reached its fixpoint. This approach seems to be simpler to write.

[george.burgess.iv]

Thanks for the patch!

lib/Analysis/CFLAndersAliasAnalysis.cpp

159 ↗

(On Diff #63886)

Missing period.

167 ↗

(On Diff #63886)

insert + map brings the implication of "won't be inserted if the key already exists." Could we rename this to 'merge', or 'add', or something like that, please? :)

433 ↗

(On Diff #63886)

Do we "push the attributes down" at any point?

E.g. given

void doFoo(int ***a) {
  int **b = *a;
  int *c = *b;
}

Will c end up with AttrCaller?

463 ↗

(On Diff #63886)

Can we either move IValueAttrMap, or just call buildAttrMap in the FunctionInfo ctor call here, please?

[grievejia]

Rebase and fixed the downward propagation issue.

[george.burgess.iv]

Looks good -- will commit later today. Thanks for working on this!

llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp

public:
   const MemSet *getMemoryAliases(InstantiatedValue V) const {
     auto Itr = MemMap.find(V);
     if (Itr == MemMap.end())
       return nullptr;
     return &Itr->second;
   }
 };
 
+// We use AliasAttrMap to keep track of the AliasAttr of each node.
+class AliasAttrMap {
+  typedef DenseMap<InstantiatedValue, AliasAttrs> MapType;
+  MapType AttrMap;
+
+public:
+  typedef MapType::const_iterator const_iterator;
+
+  bool add(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<const_iterator> mappings() const {
+    return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
+  }
+};
+
 struct WorkListItem {
   InstantiatedValue From;
   InstantiatedValue To;
   MatchState State;
 };
 }
 
 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
   /// are properly ordered: if a and b alias each other, and a < b, then b is in
   /// AliasMap[a] but not vice versa.
   DenseMap<const Value *, std::vector<const Value *>> AliasMap;
 
+  /// Map a value to its corresponding AliasAttrs
+  DenseMap<const Value *, AliasAttrs> AttrMap;
+
   /// Summary of externally visible effects.
   AliasSummary Summary;
 
+  AliasAttrs getAttrs(const Value *) const;
+
 public:
-  FunctionInfo(const ReachabilitySet &);
+  FunctionInfo(const ReachabilitySet &, 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,
+                                              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)
       continue;
 
     auto Val = OuterMapping.first.Val;
     auto &AliasList = AliasMap[Val];
     for (const auto &InnerMapping : OuterMapping.second) {
       // Again, AliasMap only cares about top-level values
       if (InnerMapping.first.DerefLevel == 0)
         AliasList.push_back(InnerMapping.first.Val);
     }
 
     // Sort AliasList for faster lookup
     std::sort(AliasList.begin(), AliasList.end(), std::less<const Value *>());
   }
 
   // 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);
 
   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,
+                           std::less<const Value *>()))
+      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,
-                            std::less<const Value *>());
+  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,
                       MatchState State, ReachabilitySet &ReachSet,
                       std::vector<WorkListItem> &WorkList) {
   if (From == To)
     return;
   if (ReachSet.insert(From, To, State))
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
                                 ReachabilitySet &ReachSet, AliasMemSet &MemSet,
                                 std::vector<WorkListItem> &WorkList) {
   auto FromNode = Item.From;
   auto ToNode = Item.To;
 
   auto NodeInfo = Graph.getNode(ToNode);
   assert(NodeInfo != nullptr);
 
-  // TODO: propagate AliasAttr as well
   // TODO: propagate field offsets
 
   // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
   // relations that are symmetric, we could actually cut the storage by half by
   // sorting FromNode and ToNode before insertion happens.
 
   // The newly added value alias pair may pontentially generate more memory
   // alias pairs. Check for them here.
case MatchState::FlowToMemAlias: {
     for (const auto &AssignEdge : NodeInfo->Edges)
       propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet,
                 WorkList);
     break;
   }
   }
 }
 
+static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
+                                 const ReachabilitySet &ReachSet) {
+  AliasAttrMap AttrMap;
+  std::vector<InstantiatedValue> WorkList, NextList;
+
+  // 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.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
+      WorkList.push_back(Node);
+    }
+  }
+
+  while (!WorkList.empty()) {
+    for (const auto &Dst : WorkList) {
+      auto DstAttr = AttrMap.getAttrs(Dst);
+      if (DstAttr.none())
+        continue;
+
+      // Propagate attr on the same level
+      for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
+        auto Src = Mapping.first;
+        if (AttrMap.add(Src, DstAttr))
+          NextList.push_back(Src);
+      }
+
+      // Propagate attr to the levels below
+      auto DstBelow = getNodeBelow(Graph, Dst);
+      while (DstBelow) {
+        if (AttrMap.add(*DstBelow, DstAttr)) {
+          NextList.push_back(*DstBelow);
+          break;
+        }
+        DstBelow = getNodeBelow(Graph, *DstBelow);
+      }
+    }
+    WorkList.swap(NextList);
+    NextList.clear();
+  }
+
+  return AttrMap;
+}
+
 CFLAndersAAResult::FunctionInfo
 CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
   CFLGraphBuilder<CFLAndersAAResult> GraphBuilder(
       *this, TLI,
       // Cast away the constness here due to GraphBuilder's API requirement
       const_cast<Function &>(Fn));
   auto &Graph = GraphBuilder.getCFLGraph();
 
   ReachabilitySet ReachSet;
   AliasMemSet MemSet;
 
   std::vector<WorkListItem> WorkList, NextList;
   initializeWorkList(WorkList, ReachSet, Graph);
   // TODO: make sure we don't stop before the fix point is reached
   while (!WorkList.empty()) {
     for (const auto &Item : WorkList)
       processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
 
     NextList.swap(WorkList);
     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, std::move(IValueAttrMap));
 }
 
 void CFLAndersAAResult::scan(const Function &Fn) {
   auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
   (void)InsertPair;
   assert(InsertPair.second &&
          "Trying to scan a function that has already been cached");
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/attrs-below.ll

+; This testcase ensures that AliasAttrs are propagated not only on the same 
+; level but also downward.
+
+; 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_attr_below
+; CHECK: MayAlias: i64* %q, i64*** %p
+; CHECK: NoAlias: i64* %esc, i64*** %p
+; CHECK: NoAlias: i64* %esc, i64* %q
+
+; CHECK: MayAlias: i64* %unknown, i64*** %p
+; CHECK: MayAlias: i64* %q, i64* %unknown
+; CHECK: MayAlias: i64* %esc, i64* %unknown
+; CHECK: MayAlias: i64* %q, i64** %pdrf
+; CHECK: MayAlias: i64* %esc, i64** %pdrf
+; CHECK: MayAlias: i64* %unknown, i64** %pdrf
+; CHECK: MayAlias: i64* %pdrf2, i64* %q
+; CHECK: MayAlias: i64* %esc, i64* %pdrf2
+; CHECK: MayAlias: i64* %pdrf2, i64* %unknown
+define void @test_attr_below(i64*** %p, i64* %q) {
+  %esc = alloca i64, align 8
+  %escint = ptrtoint i64* %esc to i64
+  %unknown = inttoptr i64 %escint to i64*
+
+  %pdrf = load i64**, i64*** %p
+  %pdrf2 = load i64*, i64** %pdrf
+
+  ret void
+}
+
+; CHECK-LABEL: Function: test_attr_assign_below
+; CHECK: MayAlias: i64** %sel, i64*** %p
+; CHECK: MayAlias: i64* %q, i64** %sel
+; CHECK: MayAlias: i64** %a, i64** %sel
+; CHECK: MayAlias: i64** %pdrf, i64** %sel
+
+; CHECK: MayAlias: i64** %c, i64*** %p
+; CHECK: MayAlias: i64* %q, i64** %c
+; CHECK: MayAlias: i64** %a, i64** %c
+; CHECK: MayAlias: i64** %c, i64** %pdrf
+; CHECK: MayAlias: i64** %c, i64** %sel
+
+; CHECK: MayAlias: i64* %d, i64*** %p
+; CHECK: MayAlias: i64* %d, i64* %q
+; CHECK: MayAlias: i64* %d, i64** %pdrf
+; CHECK: MayAlias: i64* %d, i64** %sel
+define void @test_attr_assign_below(i64*** %p, i64* %q, i1 %cond) {
+  %a = alloca i64*, align 8
+  %pdrf = load i64**, i64*** %p
+  %sel = select i1 %cond, i64** %a, i64** %pdrf
+
+  %b = alloca i64**, align 8
+  store i64** %sel, i64*** %b
+
+  %c = load i64**, i64*** %b
+  %d = load i64*, i64** %c
+
+  ret void
+}
+

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/attrs.ll

+; 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
+}