[CFLAA] Handle global/arg attrs more sanely.

Prior to this patch, we used argument/global stratified attributes in
order to note that a value could have come from either dereferencing a
global/arg, or from the assignment from a global/arg.

Now, AttrUnknown is placed on sets when we see a dereference, instead of
the global/arg attributes. This allows us to be more aggressive in the
future when we see global/arg attributes without AttrUnknown.

Patch by Jia Chen.

Differential Revision: http://reviews.llvm.org/D21110

llvm-svn: 272335

3 files changed, 58 insertions, 24 deletions

diff --git a/llvm/lib/Analysis/CFLAliasAnalysis.cpp b/llvm/lib/Analysis/CFLAliasAnalysis.cpp
index 24bc4e937a9..3a6f1ca2585 100644
--- a/llvm/lib/Analysis/CFLAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/CFLAliasAnalysis.cpp
@@ -657,6 +657,10 @@ typedef DenseMap<Value *, GraphT::Node> NodeMapT;
 /// as globals or arguments
 static bool isGlobalOrArgAttr(StratifiedAttrs Attr);
 
+/// Given a StratifiedAttrs, returns true if the corresponding values come from
+/// an unknown source (such as opaque memory or an integer cast)
+static bool isUnknownAttr(StratifiedAttrs Attr);
+
 /// Given an argument number, returns the appropriate StratifiedAttr to set.
 static StratifiedAttr argNumberToAttr(unsigned ArgNum);
 
@@ -750,6 +754,10 @@ static bool isGlobalOrArgAttr(StratifiedAttrs Attr) {
   return Attr.reset(AttrEscapedIndex).reset(AttrUnknownIndex).any();
 }
 
+static bool isUnknownAttr(StratifiedAttrs Attr) {
+  return Attr.test(AttrUnknownIndex);
+}
+
 static Optional<StratifiedAttr> valueToAttr(Value *Val) {
   if (isa<GlobalValue>(Val))
     return AttrGlobal;
@@ -955,6 +963,7 @@ CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
   StratifiedSetsBuilder<Value *> Builder;
 
   SmallVector<GraphT::Node, 16> Worklist;
+  SmallPtrSet<Value *, 16> Globals;
   for (auto &Pair : Map) {
     Worklist.clear();
 
@@ -968,9 +977,8 @@ CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
       if (canSkipAddingToSets(CurValue))
         continue;
 
-      Optional<StratifiedAttr> MaybeCurAttr = valueToAttr(CurValue);
-      if (MaybeCurAttr)
-        Builder.noteAttributes(CurValue, *MaybeCurAttr);
+      if (isa<GlobalValue>(CurValue))
+        Globals.insert(CurValue);
 
       for (const auto &EdgeTuple : Graph.edgesFor(Node)) {
         auto Weight = std::get<0>(EdgeTuple);
@@ -980,6 +988,8 @@ CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
 
         if (canSkipAddingToSets(OtherValue))
           continue;
+        if (isa<GlobalValue>(OtherValue))
+          Globals.insert(OtherValue);
 
         bool Added;
         switch (directionOfEdgeType(Label)) {
@@ -995,10 +1005,6 @@ CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
         }
 
         auto Aliasing = Weight.second;
-        if (MaybeCurAttr)
-          Aliasing |= *MaybeCurAttr;
-        if (auto MaybeOtherAttr = valueToAttr(OtherValue))
-          Aliasing |= *MaybeOtherAttr;
         Builder.noteAttributes(CurValue, Aliasing);
         Builder.noteAttributes(OtherValue, Aliasing);
 
@@ -1008,18 +1014,21 @@ CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
     }
   }
 
-  // There are times when we end up with parameters not in our graph (i.e. if
-  // it's only used as the condition of a branch). Other bits of code depend on
-  // things that were present during construction being present in the graph.
-  // So, we add all present arguments here.
-  for (auto &Arg : Fn->args()) {
-    if (!Builder.add(&Arg))
-      continue;
+  // Special handling for globals and arguments
+  auto ProcessGlobalOrArgValue = [&Builder](Value &Val) {
+    Builder.add(&Val);
+    auto Attr = valueToAttr(&Val);
+    if (Attr.hasValue()) {
+      Builder.noteAttributes(&Val, *Attr);
+      // TODO: do we need to filter out non-pointer values here?
+      Builder.addAttributesBelow(&Val, AttrUnknown);
+    }
+  };
 
-    auto Attr = valueToAttr(&Arg);
-    if (Attr.hasValue())
-      Builder.noteAttributes(&Arg, *Attr);
-  }
+  for (auto &Arg : Fn->args())
+    ProcessGlobalOrArgValue(Arg);
+  for (auto *Global : Globals)
+    ProcessGlobalOrArgValue(*Global);
 
   return FunctionInfo(Builder.build(), std::move(ReturnedValues));
 }
@@ -1104,13 +1113,13 @@ AliasResult CFLAAResult::query(const MemoryLocation &LocA,
   // bit more interesting. We follow three general rules described below:
   // - Non-local values may alias each other
   // - AttrNone values do not alias any non-local values
-  // - AttrEscaped values do not alias globals/arguments, but they may alias
+  // - AttrEscaped do not alias globals/arguments, but they may alias
   // AttrUnknown values
   if (SetA.Index == SetB.Index)
     return MayAlias;
   if (AttrsA.none() || AttrsB.none())
     return NoAlias;
-  if (AttrsA.test(AttrUnknownIndex) || AttrsB.test(AttrUnknownIndex))
+  if (isUnknownAttr(AttrsA) || isUnknownAttr(AttrsB))
     return MayAlias;
   if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
     return MayAlias;
diff --git a/llvm/lib/Analysis/StratifiedSets.h b/llvm/lib/Analysis/StratifiedSets.h
index ae1befbdf95..0e20343af1e 100644
--- a/llvm/lib/Analysis/StratifiedSets.h
+++ b/llvm/lib/Analysis/StratifiedSets.h
@@ -395,6 +395,17 @@ public:
     return addAtMerging(ToAdd, Below);
   }
 
+  /// \brief Set the StratifiedAttrs of the set below "Main". If there is no set
+  /// below "Main", create one for it.
+  void addAttributesBelow(const T &Main, StratifiedAttrs Attr) {
+    assert(has(Main));
+    auto Index = *indexOf(Main);
+    auto Link = linksAt(Index);
+
+    auto BelowIndex = Link.hasBelow() ? Link.getBelow() : addLinkBelow(Index);
+    linksAt(BelowIndex).setAttrs(Attr);
+  }
+
   bool addWith(const T &Main, const T &ToAdd) {
     assert(has(Main));
     auto MainIndex = *indexOf(Main);
diff --git a/llvm/test/Analysis/CFLAliasAnalysis/attr-escape.ll b/llvm/test/Analysis/CFLAliasAnalysis/attr-escape.ll
index 6e366d5560f..a7ab3e83829 100644
--- a/llvm/test/Analysis/CFLAliasAnalysis/attr-escape.ll
+++ b/llvm/test/Analysis/CFLAliasAnalysis/attr-escape.ll
@@ -3,16 +3,30 @@
 ; 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: escape_ptrtoint
-; CHECK: NoAlias: i32* %a, i32* %x
-; CHECK: NoAlias: i32* %b, i32* %x
+; 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 @escape_ptrtoint(i32* %x) {
+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
+}