[CFLAA] Add interprocerual analysis support to CFLAndersAliasAnalysis

[grievejia]

Summary

This patch finally makes CFLAnders properly build function summaries.

The approach I took was more complicated than I expected. Initially, I thought that the information we need to build the summary is all included in the ReachabilitySet, and I could just iterate over it once to populate the entire function summary. However, it turns out that we might have cases like this:

define i32* @f(i32*** %arg1) {
  %d = load i32**, i32*** arg1
  %d2 = load i32*, i32** %d
  ret i32* %d2
}

Here node (%d2, 0) does not value-alias with any other nodes in ReachabilitySet [1][2]. All we can deduce from ReachSet is that (%d, 1) is assigned to (%d2, 0), and (%arg, 1) is assigned to (%d, 0). The value %d here acts as an "intermediate value" that connects assignments from/to its different DerefLevel. Such a connection is not something we could obvious obtain from ReachabilitySet, which only holds assignments that are on the same level. If we don't check for this case, we will incorrectly conclude that the return value of @f has no relation with the parameter %arg1 of @f.

There could be many ways to resolve the above issue. The proposed solution in this patch is to build a read&write set for each value V in the function, holding param/return values that are read into or write from V, respectively. If both the read set and the write set of V are non-empty, then we know that V has been used as an "intermediate value", and we should add an cross-level assignment summary edge from everything in the write set to everything in the read set. An alternative design is to bake those read/write sets into ReachabilitySet itself so we don't have to build additional structures at summary construction time. But I decided to go with the current approach since it is relatively cleaner and easy to think about.

[1] Here I use the pair notation (x, y) to denote an InstantiatedValue with value x and dereference-level y.
[2] In theory, (%d2, 0) should alias (%arg1, 2), but our CFL matching algorithm doesn't add the node (%arg1, 2) into ReachabilitySet. The algorithm doesn't do it because (%arg1, 2) never gets explicitly referenced in the function body. If we were to add (%arg1, 2), we need to also consider questions like "why don't we add (%arg1, 3)", "at which DerefLevel should we stop adding nodes", and things may quickly get unnecessarily complicated that way.

[george.burgess.iv]

Yay tests! Thanks for the patch

lib/Analysis/CFLAndersAliasAnalysis.cpp

99 ↗

(On Diff #64264)

Is there a reason these aren't static?

256 ↗

(On Diff #64264)

Nit: Apparently we have a function called is_contained in STLExtras that does just this. So, can we use llvm::is_contained(RetVals, Val)) instead, please? :)

302 ↗

(On Diff #64264)

I realize that Args and RetVals will generally be small, but can we use a set (for either) instead, please?

303 ↗

(On Diff #64264)

Nit: is_contained

339 ↗

(On Diff #64264)

Do we intend to do nothing here if it InnerMapping is e.g. FlowToReadWrite?

test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll

32 ↗

(On Diff #64264)

Is this a cleanup from before, or is this as a result of this change? If the former, I'll commit it separately. :)

[grievejia]

lib/Analysis/CFLAndersAliasAnalysis.cpp

302 ↗

(On Diff #64264)

If the vectors are small, isn't it unlikely that sets will be faster?

339 ↗

(On Diff #64264)

Yes. All XXXReadWrite states are not useful here.

The reason is, again, that (X, Y, XXXReadWrite) represent structures like "X = Z; Y = Z;". In other words, there is no transitive assignments from X to Y or from Y to X. If you reason about the inclusion relations, the points-to set of X does not have to be a subset of the points-to set of Y, and vice versa. It's therefore imprecise to add "X = Y" or "Y = X" to the function summary.

What should be added to the summary is "X=Z" and "Y=Z", but we don't know what Z is so we can't do that. It is fine that we don't know Z though: if such a Z exists, we must have (X, Z, XXXReadOnly), (Z, X, XXXWriteOnly), (Y, Z, XXXReadOnly), and (Z, Y, XXXWriteOnly) all stored somewhere in ReachSet. Z will eventually be processed when those entries are encountered

test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll

32 ↗

(On Diff #64264)

This is a cleanup. I made a mistake. %b must alias %lp here.

[grievejia]

lib/Analysis/CFLAndersAliasAnalysis.cpp

99 ↗

(On Diff #64264)

They are defined inside anonymous namespace so I assume they're implicitly static? We did the same thing for those StratifiedIndices.

[grievejia]

Replace std::find with is_contained

[george.burgess.iv]

Looks good -- thanks again! (Will commit the change to interproc-store-arg-multilevel.ll separately, as promised, to make it clear that it's unrelated)

lib/Analysis/CFLAndersAliasAnalysis.cpp

110 ↗

(On Diff #64514)

That makes sense, then; generally the preference in LLVM tends to be "only put structs/classes in anonymous namespaces; make everything else static," but so long as these aren't externally visible, I'm happy.

313 ↗

(On Diff #64514)

Yeah, I guess I don't see a real-world case where either of these will (practically) be huge, so you're right. :)

llvm/trunk/lib/Analysis/AliasAnalysisSummary.h

 };
 
 inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
   return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
 }
 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.
 struct ExternalRelation {
   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 {
   InterfaceValue IValue;
   AliasAttrs Attr;
 };
 
 /// AliasSummary is just a collection of ExternalRelation and ExternalAttribute

llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp

enum class MatchState : uint8_t {
   // X and Y.
   FlowToWriteOnly,
   FlowToReadWrite,
   // The following two states together represent S4 in the paper.
   FlowToMemAliasWriteOnly,
   FlowToMemAliasReadWrite,
 };
 
+typedef std::bitset<7> StateSet;
+LLVM_CONSTEXPR StateSet ReadOnlyStateMask =
+    (1 << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
+    (1 << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
+LLVM_CONSTEXPR StateSet WriteOnlyStateMask =
+    (1 << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
+    (1 << static_cast<uint8_t>(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<InstantiatedValue, StateSet> ValueStateMap;
   typedef DenseMap<InstantiatedValue, ValueStateMap> ValueReachMap;
   ValueReachMap ReachMap;
 
 public:
   typedef ValueStateMap::const_iterator const_valuestate_iterator;
   typedef ValueReachMap::const_iterator const_value_iterator;
 
   // 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<size_t>(State);
     if (!States.test(Idx)) {
       States.set(Idx);
       return true;
     }
     return false;
   }
public:
   }
 };
 
 struct WorkListItem {
   InstantiatedValue From;
   InstantiatedValue To;
   MatchState State;
 };
+
+struct ValueSummary {
+  struct Record {
+    InterfaceValue IValue;
+    unsigned DerefLevel;
+  };
+  SmallVector<Record, 4> FromRecords, ToRecords;
+};
 }
 
 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 &, AliasAttrMap);
+  FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
+               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<InterfaceValue>
+getInterfaceValue(InstantiatedValue IValue,
+                  const SmallVectorImpl<Value *> &RetVals) {
+  auto Val = IValue.Val;
+
+  Optional<unsigned> Index;
+  if (auto Arg = dyn_cast<Argument>(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<const Value *, AliasAttrs> &AttrMap,
+                            const AliasAttrMap &AMap) {
   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
+static void
+populateAliasMap(DenseMap<const Value *, std::vector<const Value *>> &AliasMap,
+                 const ReachabilitySet &ReachSet) {
   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 *>());
   }
+}
+
+static void populateExternalRelations(
+    SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
+    const SmallVectorImpl<Value *> &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<Value *, ValueSummary> 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<ExternalAttribute> &ExtAttributes, const Function &Fn,
+    const SmallVectorImpl<Value *> &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<Value *> &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 {
   assert(V != nullptr);
 
   AliasAttrs Attr;
   auto Itr = AttrMap.find(V);
   if (Itr != AttrMap.end())
while (!WorkList.empty()) {
     NextList.swap(WorkList);
     NextList.clear();
   }
 
   // Now that we have all the reachability info, propagate AliasAttrs according
   // 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) {
   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/basic-interproc.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-deref-escape.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-escape.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-multilevel.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-escape.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg-multilevel.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-unknown.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-multilevel.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-unknown.ll

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

llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg.ll

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