[CFLAA] Summarize interprocedural aliasing information instead of recomputing it at callsite

[grievejia]

Summary

The primary goal of this patch is to put parameters/return value aliasing info of each function to its summary. Those info used to get computed at each callsite where the function gets invoked. If the said function gets invoked many times, we may end up with lots of redundant computations.

This patch is almost functionality-preserving, except that I've changed the criteria of marking a function f external from "f->hasLocalLinkage()" to "f->isInterposable()". I think the former is overly conservative since it only handles functions with internal or private linkage type, yet all we want for non-external functions is that they can't be overwritten while linking. If my thought turns out to be wrong, I'm happy to switch it back.

I've also made struct type CFLAAResult::FunctionInfo public. The reason is that I want a static free-function buildFunctionInfo() as well as GetEdgeVisitor::tryInterproceduralAnalysis() to access the FunctionInfo struct. I acknowledge that this is not neat, and I'm happy to be told a cleaner solution.

Finally, various test cases on interprocedural analysis were added. Unfortunately, some of them showed that our current handling of function calls/returns is very buggy. For now I've marked those tests as XFAIL, and subsequent patches will primarily focus on removing the XFAILs gradually.

[mgrang]

lib/Analysis/CFLAliasAnalysis.cpp

71 ↗

(On Diff #61106)

Period needed at end of comment.

80 ↗

(On Diff #61106)

Period needed at end of comment.

111 ↗

(On Diff #61106)

Period needed at end of comment.

[grievejia]

Comment style fixes.

Also, the "f->isInterposable()" change was reverted. It will be put into a separate patch

[grievejia]

Make FunctionInfo private to CFLAAResult again by putting all the work that buildFunctionInfo() does into the constructor of FunctionInfo().

Also, I just found out that I need to xfail another test case due to the restrictiveness of hasLocalLinkage().

[george.burgess.iv]

Thanks for the patch, and for adding all of the tests! :)

Looks good with a handful of nits.

lib/Analysis/CFLAliasAnalysis.cpp

394 ↗

(On Diff #61260)

Please add a comment explaining why this check exists.

413 ↗

(On Diff #61260)

Please add a comment to the effect of "FromVal and ToVal should already exist in the graph, so we can add this edge directly"

745 ↗

(On Diff #61260)

Nit: Remove these braces, please.

(Braces on the loop are fine IMO)

751 ↗

(On Diff #61260)

Nit: Reserve RetVals.size() elements ahead of time, please

763 ↗

(On Diff #61260)

Nit: /// -> //

775 ↗

(On Diff #61260)

If you want to simplify things a bit, Optional<T> has an implicit conversion to bool, so you can do if (getIndexRelation(...)) RetParamRelations.push_back(...);.

Entirely up to you, though.

test/Analysis/CFLAliasAnalysis/basic-interproc.ll

1 ↗

(On Diff #61260)

Nit: Please wrap comments at 80 chars, here and elsewhere.

(It's fine to leave the run lines at > 80 chars if you'd like)

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

394 ↗

(On Diff #61260)

It used to be "if (Fn->arg_size() == CS.arg_size()) return false", and I thought I asked you for justifications some time ago... I just kept what was there and relaxed it a little bit.

775 ↗

(On Diff #61260)

Thanks for the note.

I am aware of that. The reason I invoked hasValue() is consistency: I saw "XXX.hasValue()" at several other places in the same file.

test/Analysis/CFLAliasAnalysis/basic-interproc.ll

1 ↗

(On Diff #61260)

Oops sorry about that. My editor auto-wrap long comments for C++ source files (thanks to clang-format), but I forgot it didn't do the same thing for .ll files :(

[grievejia]

Style fixes.

[george.burgess.iv]

lib/Analysis/CFLAliasAnalysis.cpp

394 ↗

(On Diff #61298)

I thought I asked you for justifications some time ago

You did :)

IIRC, the best I could offer you was "we somehow devirtualized the function pointer to N different functions, and their arities didn't match up." Given that that's the best explanation we have (and if we ever do anything fancy with indirect calls, it's probably going to be the resolver's job to ensure that the potential callee makes sense to call), I'm tempted to turn this into an assert, rather than guarding against this case without knowing why. You can blame me if it ends up breaking anything. :)

It also looks like this change would also make us do interprocedural analysis on variadic functions -- I think that should be fine, but can we have a test for that, please? If it helps, here's a link to vararg stuff: http://llvm.org/docs/LangRef.html#variable-argument-handling-intrinsics

418 ↗

(On Diff #61298)

Please add a period at the end of the comment.

775 ↗

(On Diff #61260)

WFM

test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll

7 ↗

(On Diff #61298)

80 chars, please

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

394 ↗

(On Diff #61298)

Regarding variadic functions:

AFAIK, the LLVM va_arg instruction is mostly dead, at least on platforms I commonly use. The docs are outdated w.r.t. this issue. Clang handles C/C++ variadic functions in a highly platform-dependent manner, and it generally try to avoid emitting any va_arg instructions (you can verify this on your machine).

My point is that variadic function is a complex thing to support and I'm not sure this simple change will buy us that much.

[grievejia]

More style fixes

[george.burgess.iv]

lib/Analysis/CFLAliasAnalysis.cpp

394 ↗

(On Diff #61298)

My point is that variadic function is a complex thing to support and I'm not sure this simple change will buy us that much

If we don't want to support interprocedural analysis on varargs functions, that's perfectly fine with me. My point is that relaxing this check to if (param_size() > arg_size()) return false; allows variadic functions (that were given more than zero args in their arg pack) to be analyzed interprocedurally. If we don't want to support that, we should either explicitly ask the callee if it takes an arg pack (and fail if it does), or we should un-loosen this check. :)

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

394 ↗

(On Diff #61314)

My point is that relaxing this check to if (param_size() > arg_size()) return false; allows variadic functions (that were given more than zero args in their arg pack) to be analyzed interprocedurally.

It won't. See line 392 :)

[george.burgess.iv]

LGTM -- will commit. Thanks again.

lib/Analysis/CFLAliasAnalysis.cpp

394 ↗

(On Diff #61314)

...Right. I'm dumb. Sorry about that. :)

llvm/trunk/include/llvm/Analysis/CFLAliasAnalysis.h

 #include <forward_list>
 
 namespace llvm {
 
 class TargetLibraryInfo;
 
 class CFLAAResult : public AAResultBase<CFLAAResult> {
   friend AAResultBase<CFLAAResult>;
-
-  struct FunctionInfo;
+  class FunctionInfo;
 
 public:
   explicit CFLAAResult(const TargetLibraryInfo &);
   CFLAAResult(CFLAAResult &&Arg);
   ~CFLAAResult();
 
   /// Handle invalidation events from the new pass manager.
   ///

llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp

 #define DEBUG_TYPE "cfl-aa"
 
 CFLAAResult::CFLAAResult(const TargetLibraryInfo &TLI)
     : AAResultBase(), TLI(TLI) {}
 CFLAAResult::CFLAAResult(CFLAAResult &&Arg)
     : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
 CFLAAResult::~CFLAAResult() {}
 
+/// We use ExternalRelation to describe an externally visible interaction
+/// between parameters/return value of a function.
+/// Both From and To are integer indices that represent a single parameter or
+/// return value. When the index is 0, they represent the return value. Non-zero
+/// index i represents the i-th parameter.
+struct ExternalRelation {
+  unsigned From, To;
+};
+
 /// Information we have about a function and would like to keep around.
-struct CFLAAResult::FunctionInfo {
+class CFLAAResult::FunctionInfo {
   StratifiedSets<Value *> Sets;
-  // Lots of functions have < 4 returns. Adjust as necessary.
-  SmallVector<Value *, 4> ReturnedValues;
 
-  FunctionInfo(StratifiedSets<Value *> &&S, SmallVector<Value *, 4> &&RV)
-      : Sets(std::move(S)), ReturnedValues(std::move(RV)) {}
+  // RetParamRelations is a collection of ExternalRelations.
+  SmallVector<ExternalRelation, 8> RetParamRelations;
+
+public:
+  FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
+               StratifiedSets<Value *> S);
+
+  const StratifiedSets<Value *> &getStratifiedSets() const { return Sets; }
+  const SmallVectorImpl<ExternalRelation> &getRetParamRelations() const {
+    return RetParamRelations;
+  }
 };
 
 /// Try to go from a Value* to a Function*. Never returns nullptr.
 static Optional<Function *> parentFunctionOfValue(Value *);
 
 /// Returns possible functions called by the Inst* into the given
 /// SmallVectorImpl. Returns true if targets found, false otherwise. This is
 /// templated so we can use it with CallInsts and InvokeInsts.

 LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex;
 LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex;
 
 LLVM_CONSTEXPR StratifiedAttr AttrNone = 0;
 LLVM_CONSTEXPR StratifiedAttr AttrEscaped = 1 << AttrEscapedIndex;
 LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex;
 LLVM_CONSTEXPR StratifiedAttr AttrGlobal = 1 << AttrGlobalIndex;
 
+/// The maximum number of arguments we can put into a summary.
+LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50;
+
 /// StratifiedSets call for knowledge of "direction", so this is how we
 /// represent that locally.
 enum class Level { Same, Above, Below };
 
 /// Edges can be one of four "weights" -- each weight must have an inverse
 /// weight (Assign has Assign; Reference has Dereference).
 enum class EdgeType {
   /// The weight assigned when assigning from or to a value. For example, in:
void visitVAArgInst(VAArgInst &Inst) {
     // result in its own group, and having that group alias externals).
     addNodeWithAttr(&Inst, AttrUnknown);
   }
 
   static bool isFunctionExternal(Function *Fn) {
     return Fn->isDeclaration() || !Fn->hasLocalLinkage();
   }
 
-  /// Gets whether the sets at Index1 above, below, or equal to the sets at
-  /// Index2. Returns None if they are not in the same set chain.
-  static Optional<Level> getIndexRelation(const StratifiedSets<Value *> &Sets,
-                                          StratifiedIndex Index1,
-                                          StratifiedIndex Index2) {
-    if (Index1 == Index2)
-      return Level::Same;
-
-    const auto *Current = &Sets.getLink(Index1);
-    while (Current->hasBelow()) {
-      if (Current->Below == Index2)
-        return Level::Below;
-      Current = &Sets.getLink(Current->Below);
-    }
-
-    Current = &Sets.getLink(Index1);
-    while (Current->hasAbove()) {
-      if (Current->Above == Index2)
-        return Level::Above;
-      Current = &Sets.getLink(Current->Above);
-    }
-
-    return None;
-  }
-
-  // Encodes the notion of a "use"
-  struct Edge {
-    // Which value the edge is coming from
-    Value *From;
-
-    // Which value the edge is pointing to
-    Value *To;
-
-    // Edge weight
-    EdgeType Weight;
-
-    // Whether we aliased any external values along the way that may be
-    // invisible to the analysis
-    StratifiedAttrs FromAttrs, ToAttrs;
-  };
-
-  bool
-  tryInterproceduralAnalysis(const SmallVectorImpl<Function *> &Fns,
-                             Value *FuncValue,
-                             const iterator_range<User::op_iterator> &Args) {
-    const unsigned ExpectedMaxArgs = 8;
-    const unsigned MaxSupportedArgs = 50;
+  bool tryInterproceduralAnalysis(CallSite CS,
+                                  const SmallVectorImpl<Function *> &Fns) {
     assert(Fns.size() > 0);
 
-    // This algorithm is n^2, so an arbitrary upper-bound of 50 args was
-    // selected, so it doesn't take too long in insane cases.
-    if (std::distance(Args.begin(), Args.end()) > (int)MaxSupportedArgs)
+    if (CS.arg_size() > MaxSupportedArgsInSummary)
       return false;
 
     // Exit early if we'll fail anyway
     for (auto *Fn : Fns) {
       if (isFunctionExternal(Fn) || Fn->isVarArg())
         return false;
+      // Fail if the caller does not provide enough arguments
+      assert(Fn->arg_size() <= CS.arg_size());
       auto &MaybeInfo = AA.ensureCached(Fn);
       if (!MaybeInfo.hasValue())
         return false;
     }
 
-    SmallVector<Edge, 8> Output;
-    SmallVector<Value *, ExpectedMaxArgs> Arguments(Args.begin(), Args.end());
-    SmallVector<StratifiedInfo, ExpectedMaxArgs> Parameters;
     for (auto *Fn : Fns) {
-      auto &Info = *AA.ensureCached(Fn);
-      auto &Sets = Info.Sets;
-      auto &RetVals = Info.ReturnedValues;
-
-      Parameters.clear();
-      for (auto &Param : Fn->args()) {
-        auto MaybeInfo = Sets.find(&Param);
-        // Did a new parameter somehow get added to the function/slip by?
-        if (!MaybeInfo.hasValue())
-          return false;
-        Parameters.push_back(*MaybeInfo);
-      }
-
-      // Adding an edge from argument -> return value for each parameter that
-      // may alias the return value
-      for (unsigned I = 0, E = Parameters.size(); I != E; ++I) {
-        auto &ParamInfo = Parameters[I];
-        auto &ArgVal = Arguments[I];
-        bool AddEdge = false;
-        StratifiedAttrs RetAttrs, ParamAttrs;
-        for (unsigned X = 0, XE = RetVals.size(); X != XE; ++X) {
-          auto MaybeInfo = Sets.find(RetVals[X]);
-          if (!MaybeInfo.hasValue())
-            return false;
+      auto &FnInfo = AA.ensureCached(Fn);
+      assert(FnInfo.hasValue());
 
-          auto &RetInfo = *MaybeInfo;
-          RetAttrs |= Sets.getLink(RetInfo.Index).Attrs;
-          ParamAttrs |= Sets.getLink(ParamInfo.Index).Attrs;
-          auto MaybeRelation =
-              getIndexRelation(Sets, ParamInfo.Index, RetInfo.Index);
-          if (MaybeRelation.hasValue())
-            AddEdge = true;
-        }
-        if (AddEdge)
-          Output.push_back(
-              Edge{FuncValue, ArgVal, EdgeType::Assign, RetAttrs, ParamAttrs});
-      }
-
-      if (Parameters.size() != Arguments.size())
-        return false;
-
-      /// Adding edges between arguments for arguments that may end up aliasing
-      /// each other. This is necessary for functions such as
-      /// void foo(int** a, int** b) { *a = *b; }
-      /// (Technically, the proper sets for this would be those below
-      /// Arguments[I] and Arguments[X], but our algorithm will produce
-      /// extremely similar, and equally correct, results either way)
-      for (unsigned I = 0, E = Arguments.size(); I != E; ++I) {
-        auto &MainVal = Arguments[I];
-        auto &MainInfo = Parameters[I];
-        auto &MainAttrs = Sets.getLink(MainInfo.Index).Attrs;
-        for (unsigned X = I + 1; X != E; ++X) {
-          auto &SubInfo = Parameters[X];
-          auto &SubVal = Arguments[X];
-          auto &SubAttrs = Sets.getLink(SubInfo.Index).Attrs;
-          auto MaybeRelation =
-              getIndexRelation(Sets, MainInfo.Index, SubInfo.Index);
-
-          if (!MaybeRelation.hasValue())
-            continue;
-
-          Output.push_back(
-              Edge{MainVal, SubVal, EdgeType::Assign, MainAttrs, SubAttrs});
-        }
-      }
-    }
-
-    // Commit all edges in Output to CFLGraph
-    for (const auto &Edge : Output) {
-      addEdge(Edge.From, Edge.To, Edge.Weight);
-      Graph.addAttr(Edge.From, Edge.FromAttrs);
-      Graph.addAttr(Edge.To, Edge.ToAttrs);
+      auto &RetParamRelations = FnInfo->getRetParamRelations();
+      for (auto &Relation : RetParamRelations) {
+        auto FromIndex = Relation.From;
+        auto ToIndex = Relation.To;
+        auto FromVal = (FromIndex == 0) ? CS.getInstruction()
+                                        : CS.getArgument(FromIndex - 1);
+        auto ToVal =
+            (ToIndex == 0) ? CS.getInstruction() : CS.getArgument(ToIndex - 1);
+        if (FromVal->getType()->isPointerTy() &&
+            ToVal->getType()->isPointerTy())
+          // Actual arguments must be defined before they are used at callsite.
+          // Therefore by the time we reach here, FromVal and ToVal should
+          // already exist in the graph. We can go ahead and add them directly.
+          Graph.addEdge(FromVal, ToVal, EdgeType::Assign);
     }
 
     return true;
   }
 
   void visitCallSite(CallSite CS) {
     auto Inst = CS.getInstruction();
 
     // Make sure all arguments and return value are added to the graph first
     for (Value *V : CS.args())
       addNode(V);
-    if (!Inst->getType()->isVoidTy())
+    if (Inst->getType()->isPointerTy())
       addNode(Inst);
 
     // Check if Inst is a call to a library function that allocates/deallocates
     // on the heap. Those kinds of functions do not introduce any aliases.
     // TODO: address other common library functions such as realloc(), strdup(),
     // etc.
     if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI) ||
         isFreeCall(Inst, &TLI))
       return;
 
     // TODO: Add support for noalias args/all the other fun function attributes
     // that we can tack on.
     SmallVector<Function *, 4> Targets;
     if (getPossibleTargets(CS, Targets))
-      if (tryInterproceduralAnalysis(Targets, Inst, CS.args()))
+      if (tryInterproceduralAnalysis(CS, Targets))
         return;
 
     // Because the function is opaque, we need to note that anything
     // could have happened to the arguments (unless the function is marked
     // readonly or readnone), and that the result could alias just about
     // anything, too (unless the result is marked noalias).
     if (!CS.onlyReadsMemory())
       for (Value *V : CS.args()) {
         if (V->getType()->isPointerTy())
           Escapes.insert(V);
       }
 
-    if (!Inst->getType()->isVoidTy()) {
+    if (Inst->getType()->isPointerTy()) {
       auto *Fn = CS.getCalledFunction();
       if (Fn == nullptr || !Fn->doesNotAlias(0))
         Graph.addAttr(Inst, AttrUnknown);
     }
   }
 
   /// Because vectors/aggregates are immutable and unaddressable, there's
   /// nothing we can do to coax a value out of them, other than calling
class CFLGraphBuilder {
   // Instructions that are potentially only available from said Instruction
   // For example, given the following line:
   //   %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
   // addInstructionToGraph would add both the `load` and `getelementptr`
   // instructions to the graph appropriately.
   void addInstructionToGraph(Instruction &Inst) {
     // We don't want the edges of most "return" instructions, but we *do* want
     // to know what can be returned.
-    if (isa<ReturnInst>(&Inst))
-      ReturnedValues.push_back(&Inst);
+    if (auto RetInst = dyn_cast<ReturnInst>(&Inst))
+      if (auto RetVal = RetInst->getReturnValue())
+        if (RetVal->getType()->isPointerTy())
+          ReturnedValues.push_back(RetVal);
 
     if (!hasUsefulEdges(&Inst))
       return;
 
     GetEdgesVisitor(Analysis, TLI, Graph, ExternalValues, EscapedValues)
         .visit(Inst);
   }
 

 
 public:
   CFLGraphBuilder(CFLAAResult &Analysis, const TargetLibraryInfo &TLI,
                   Function &Fn)
       : Analysis(Analysis), TLI(TLI) {
     buildGraphFrom(Fn);
   }
 
-  const CFLGraph &getCFLGraph() { return Graph; }
-  SmallVector<Value *, 4> takeReturnValues() {
-    return std::move(ReturnedValues);
+  const CFLGraph &getCFLGraph() const { return Graph; }
+  const SmallVector<Value *, 4> &getReturnValues() const {
+    return ReturnedValues;
+  }
+  const SmallPtrSet<Value *, 8> &getExternalValues() const {
+    return ExternalValues;
+  }
+  const SmallPtrSet<Value *, 8> &getEscapedValues() const {
+    return EscapedValues;
   }
-  const SmallPtrSet<Value *, 8> &getExternalValues() { return ExternalValues; }
-  const SmallPtrSet<Value *, 8> &getEscapedValues() { return EscapedValues; }
 };
 }
 
 //===----------------------------------------------------------------------===//
 // Function declarations that require types defined in the namespace above
 //===----------------------------------------------------------------------===//
 
 /// Given a StratifiedAttrs, returns true if it marks the corresponding values
bool CanStoreMutableData = isa<GlobalValue>(Val) ||
                                isa<ConstantExpr>(Val) ||
                                isa<ConstantAggregate>(Val);
     return !CanStoreMutableData;
   }
 
   return false;
 }
 
+/// Gets whether the sets at Index1 above, below, or equal to the sets at
+/// Index2. Returns None if they are not in the same set chain.
+static Optional<Level> getIndexRelation(const StratifiedSets<Value *> &Sets,
+                                        StratifiedIndex Index1,
+                                        StratifiedIndex Index2) {
+  if (Index1 == Index2)
+    return Level::Same;
+
+  const auto *Current = &Sets.getLink(Index1);
+  while (Current->hasBelow()) {
+    if (Current->Below == Index2)
+      return Level::Below;
+    Current = &Sets.getLink(Current->Below);
+  }
+
+  Current = &Sets.getLink(Index1);
+  while (Current->hasAbove()) {
+    if (Current->Above == Index2)
+      return Level::Above;
+    Current = &Sets.getLink(Current->Above);
+  }
+
+  return None;
+}
+
+CFLAAResult::FunctionInfo::FunctionInfo(Function &Fn,
+                                        const SmallVectorImpl<Value *> &RetVals,
+                                        StratifiedSets<Value *> S)
+    : Sets(std::move(S)) {
+  LLVM_CONSTEXPR unsigned ExpectedMaxArgs = 8;
+
+  // Collect StratifiedInfo for each parameter
+  SmallVector<Optional<StratifiedInfo>, ExpectedMaxArgs> ParamInfos;
+  for (auto &Param : Fn.args()) {
+    if (Param.getType()->isPointerTy())
+      ParamInfos.push_back(Sets.find(&Param));
+    else
+      ParamInfos.push_back(None);
+  }
+  // Collect StratifiedInfo for each return value
+  SmallVector<Optional<StratifiedInfo>, 4> RetInfos;
+  RetInfos.reserve(RetVals.size());
+  for (unsigned I = 0, E = RetVals.size(); I != E; ++I)
+    RetInfos.push_back(Sets.find(RetVals[I]));
+
+  // This summary generation algorithm is n^2. An arbitrary upper-bound of 50
+  // args was selected, so it doesn't take too long in insane cases.
+  if (Fn.arg_size() <= MaxSupportedArgsInSummary) {
+    for (unsigned I = 0, E = ParamInfos.size(); I != E; ++I) {
+      auto &MainInfo = ParamInfos[I];
+      if (!MainInfo)
+        continue;
+
+      // Adding edges between arguments for arguments that may end up aliasing
+      // each other. This is necessary for functions such as
+      // void foo(int** a, int** b) { *a = *b; }
+      // (Technically, the proper sets for this would be those below
+      // Arguments[I] and Arguments[X], but our algorithm will produce
+      // extremely similar, and equally correct, results either way)
+      for (unsigned X = I + 1; X != E; ++X) {
+        auto &SubInfo = ParamInfos[X];
+        if (!SubInfo)
+          continue;
+
+        auto MaybeRelation =
+            getIndexRelation(Sets, MainInfo->Index, SubInfo->Index);
+        if (!MaybeRelation.hasValue())
+          continue;
+
+        RetParamRelations.push_back(ExternalRelation{1 + I, 1 + X});
+      }
+
+      // Adding an edge from argument -> return value for each parameter that
+      // may alias the return value
+      for (unsigned X = 0, XE = RetInfos.size(); X != XE; ++X) {
+        auto &RetInfo = RetInfos[X];
+        if (!RetInfo)
+          continue;
+
+        auto MaybeRelation =
+            getIndexRelation(Sets, MainInfo->Index, RetInfo->Index);
+        if (!MaybeRelation.hasValue())
+          continue;
+
+        RetParamRelations.push_back(ExternalRelation{1 + I, 0});
+      }
+    }
+  }
+}
+
 // Builds the graph + StratifiedSets for a function.
 CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
   CFLGraphBuilder GraphBuilder(*this, TLI, *Fn);
   StratifiedSetsBuilder<Value *> SetBuilder;
 
   auto &Graph = GraphBuilder.getCFLGraph();
   SmallVector<Value *, 16> Worklist;
   for (auto Node : Graph.nodes())
CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
   }
 
   for (auto *Escape : GraphBuilder.getEscapedValues()) {
     SetBuilder.add(Escape);
     SetBuilder.noteAttributes(Escape, AttrEscaped);
     SetBuilder.addAttributesBelow(Escape, AttrUnknown);
   }
 
-  return FunctionInfo(SetBuilder.build(), GraphBuilder.takeReturnValues());
+  return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
 }
 
 void CFLAAResult::scan(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");
 
AliasResult CFLAAResult::query(const MemoryLocation &LocA,
   } else {
     Fn = *MaybeFnB;
   }
 
   assert(Fn != nullptr);
   auto &MaybeInfo = ensureCached(Fn);
   assert(MaybeInfo.hasValue());
 
-  auto &Sets = MaybeInfo->Sets;
+  auto &Sets = MaybeInfo->getStratifiedSets();
   auto MaybeA = Sets.find(ValA);
   if (!MaybeA.hasValue())
     return MayAlias;
 
   auto MaybeB = Sets.find(ValB);
   if (!MaybeB.hasValue())
     return MayAlias;
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/basic-interproc.ll

-; This testcase ensures that CFL AA gives conservative answers on variables
-; that involve arguments.
+; 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-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+; 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: test2
+; CHECK-LABEL: Function: noop_callee
 ; CHECK: MayAlias: i32* %arg1, i32* %arg2
-define void @test2(i32* %arg1, i32* %arg2) {
+define void @noop_callee(i32* %arg1, i32* %arg2) {
   store i32 0, i32* %arg1
   store i32 0, i32* %arg2
-
   ret void
 }
-
-define void @test() {
+; 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 @test2(i32* %a, i32* %b)
+  call void @noop_callee(i32* %a, i32* %b)
 
   ret void
 }

llvm/trunk/test/Analysis/CFLAliasAnalysis/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-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
+
+; We have to xfail this since @return_arg_callee is treated as an opaque 
+; function, and the anlysis couldn't prove that %b and %c are not aliases 
+; XFAIL: *
+
+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/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-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
+
+; xfail for now due to buggy interproc analysis
+; XFAIL: *
+
+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: MayAlias: i32* %lpp_deref, i32** %p
+; 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/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-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
+
+; xfail for now due to buggy interproc analysis
+; XFAIL: *
+
+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/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-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
+
+; xfail for now due to buggy interproc analysis
+; XFAIL: *
+
+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/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-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
+
+; xfail for now due to buggy interproc analysis
+; XFAIL: *
+
+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/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-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
+
+; xfail for now due to buggy interproc analysis
+; XFAIL: *
+
+@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
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/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-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
+
+; xfail for now due to buggy interproc analysis
+; XFAIL: *
+
+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* %b, 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/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-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
+
+; xfail for now due to buggy interproc analysis
+; XFAIL: *
+
+@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: MayAlias: 32* %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/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-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
+
+; xfail for now due to buggy interproc analysis
+; XFAIL: *
+
+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: NoAlias: 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