[CFLAA] Include externally-visible memory aliasing information in function summaries

[grievejia]

Summary

CFLAA's support for interprocedural analysis was rather limited. For each function argument/return value, it only records whether if the given value is somehow related (i.e. can be obtained through assignments/reference/derefence) to other argument/return values. If the relation is found, an assignment edge is added (i.e. merge the two values into the same StratifiedSet). For example, if it sees a call instruction like this:

call void @f(i32** %x, i32* %y)

and if function @f is defined like this:

define void @f(%i32** %a, i32* %b) {
  store i32* %b, i32** %a
  ret void
}

Then the analysis will try to say, at the callsite, that %x and %y are aliases. However, doing interprocedural analysis in this way is neither sound nor precise. It is imprecise because it is obvious that callee @f does not do anything to make its arguments alias each other, yet the analysis conclude that they may. It is unsound because if we add another instruction after the callsite:

%z = load i32*, i32** %x

, the analysis will not be able to detect %z and %y may-alias each other.

It seems to me that the core issue here is that our function summaries are not detailed enough to provide adequate information to the caller. Given a function @f, we can't just say "the first argument is somehow related to the second argument, but yeah we don't know exactly what the relationship is". What we really want instead is something more concrete, such as "the first argument is related to the second argument, and here's the relationship: the dereference of the first argument may-alias with the second argument". Summaries in the latter form give precise instructions on how to deal with actual arguments/actual return value at the callsite where the summary is instantiated.

This patch implements the idea illustrated in the last paragraph. Previously, the "RetParamRelation" struct inside FunctionInfo only includes related-pairs of parameters/return values. Now we refine the pairs by extending each parameters/return values with an additional DerefLevel N, which allows us to represent things like "derefrence the first argument N times". For instance, for the function @f mentioned before we will put [(param0, DerefLevel = 1), (param1, DerefLevel=0)] into the summary. At callsite where this summary is instantiated, we will create a new StratifiedSet below the set of %x, and merge it with the StratifiedSet of %y. To support this kind of operation where the DerefLevels of both elements of the pair are non-zero, a new interface to StratifiedSetBuilder needs to be added.

I've also changed the algorithm we used to generate function summaries. Here is how we checked whether two parameters %a and %b are related in the past:

• Find the StratifiedSet that %a belongs to
• Find all StratifiedSets that come above %a, and see if %b is in there
• Find all StratifiedSets that come below %a, and see if %b is in there

The algorithm is correct but if we were to do this for all pairs of parameters, it becomes O(n^2). Here is the approach I used in this patch:

• Declare a hashmap that maps from StratifiedSets to lists of parameters
• Scan the parameter list. For each parameter p, get the corresponding StratifiedSets s, and add (s->p) to the hashmap
• Scan the hashmap. For each StratifiedSet, if the mapped list has more than one element, then we know that every parameters in the list alias every other one

I think my approach should do less work and has a linear complexity (I could be wrong about this, though). One drawback of this approach (or at least in the way I'm doing it) is that we may end up with redundant items in the summary. Take @f as an example again: the summary not only contains the aforementioned entry [(param0, DerefLevel = 1), (param1, DerefLevel=0)] , we may end up with another entry [(param0, DerefLevel = 2), (param1, DerefLevel=1)] as well. The second entry is redundant here because it can be implied from the first entry. That being said, the issue does not affect soundness, and it may be fixable, so I am not very concerned about it.

With this patch ready, I am finally able to remove some xfailed test cases I introduced in an earlier patch. There are still two xfailed left untouched, since fixing them requires me putting even more information (e.g. which InterfaceValue(s) may be tagged with AttrUnknown) into the summary. They will be handled by subsequent patches.

[george.burgess.iv]

Woohoo bugfixes! Thanks for the patch.

lib/Analysis/CFLAliasAnalysis.cpp

747 ↗

(On Diff #61307)

FWIW, MSVC2013 didn't like templating on a local (yes, even though said local was const. I can't wait until we bump passed 2013), so I had to change this code a bit. Please rebase. :)

755 ↗

(On Diff #61307)

This still seems n^2-ish in some cases, which I believe ultimately makes this algorithm n^3 time, and n^2 storage. Imagine we have:

void foo(int **a, int ***b, int ****c) {
  *c = b;
  *b = a;
  int *d = *a;
}

That would give us one "chain" of

a
^
b
^
c
^
d

When scanning these, it looks like we'll add 4 entries for a, 3 entries for b, and 2 for c. It also looks like we may end up with 6 entries in cases like:

void foo(int ***a, int ***b) {
  int **ad = *a;
  int *add = *ad;
  int **bd = *b;
  int *bdd = *bd;
}

When I think we shouldn't have more than 2 (or 4, depending on how we want to handle attributes).

Assuming I'm not missing something, I think we can improve on this. AIUI, given two stratifiedset chains:

a
^
b  e
^  ^
c  f
^  ^
d  g
   ^
   h

Adding an assignment edge between b and e (or c and f, or d and g) produces the same result as adding assignment edges between all of the aforementioned pairs.

If this is correct, we can knock down the time+space complexity a bit, I think. The rough idea I have for how to do this is:

• Build a map, M, of StratifiedIndex -> vector<Value *>, where each vector is the list of Args/Return values that are in that StratifiedSet
• For each element, E, in the above map:
  • Add entries to RetParamRelations that represent assignment between E.second[0] and E.second[1..E.second.size()] (**)
  • For each set index S below E.first:
    • If we don't find a mapping in M for S, try the next lower set.
    • Otherwise, given said mapping, M', for a set N levels below E, add an entry that represents N levels of dereference between E.second[0] and M'.second[0] in RetParamRelations.

(** If you want, you can probably do this when building the map, and just make the map a StratifiedIndex -> Value* map. I realized this after writing the above, and am lazy :) )

With this, it looks like we'll end up with a linear number of entries (worst-case; best case, we'll have 0), and we'll end up walking N*M StratifiedSets total (N = number of args/returns, M = max(chain length))

758 ↗

(On Diff #61307)

I don't care either way, but if you want to just use [&] for captures in the future, you're welcome to. :)

764 ↗

(On Diff #61307)

Nit: if (!Link.hasBelow()) break; seems cleaner to me

784 ↗

(On Diff #61307)

for (auto *V : RetVals)?

785 ↗

(On Diff #61307)

Can we assert that RetVals[I] is a pointer here? I realize that it's only meant to hold values of pointer type, but that isn't exactly locally obvious IMO. :)

792 ↗

(On Diff #61307)

Nit: Mapping

792 ↗

(On Diff #61307)

It looks like there are cases where this won't add the correct StratifiedAttrs to sets. Consider:

int **g;
void foo(int **a) {
  *a = *g;
}

void bar() {
  int *p, *p2;
  *g = p2;

  int **a = &p;
  foo(a);
  // p and p2 now alias
}

Because there's only arg and no return values when analyzing foo, Interfaces.size() will never be > 1, so we'll end up with no RetParamRelations. We need to somehow apply the attributes from the set containing a in foo to the set containing a in bar, though.

799 ↗

(On Diff #61307)

Looks like RetParamRelations will hold n^2 elements, because InterfaceMap holds n^2 elements.

863 ↗

(On Diff #61307)

Looks like we do a linear walk of StratifiedSet chains for every iteration of this loop, so this might be n^3ish overall, assuming RetParamRelations contains n^2 elements?

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

755 ↗

(On Diff #61307)

Well, I'm not convinced that the current algorithm has an n^2 complexity. I think the complexity should be O(m*n), where m is the max chain length, even without your enhancement. You are right that m can sometimes be greater or equal to n, which essentially makes it O(n^2). However, normally I wouldn't expect m to be greater than 3 in most cases (at least I myself rarely write functions that handle pointers of >3 depth). So I would say m can almost be treated as a constant term.

I do agree that the algorithm can be improved in the way you described. If I understand correctly, you are suggesting that the InterfaceMap population algorithm should be executed in a "breadth-first" manner rather than a "depth-first" manner, since the former allows us to detect redundant entries earlier hence we can just shortcut exit if redundancies were found.

I'll try to change the codes as you suggested. Thanks for the comment!

758 ↗

(On Diff #61307)

Won't [&] unnecessarily capture things we don't need in the closure?

792 ↗

(On Diff #61307)

That's the reason why there are still two xfail test cases, and that's the reason why I mentioned in the description section that more work need to be done here :)

I think almost all StratifiedAttr in the callee's graph is useless to the caller, except for AttrUnknown. The summary should also include a list of InterfaceValues that must be tagged with AttrUnknown. However, we currently tag all nodes below formal parameters "AttrUnknown", so doing what I suggested before would unnecessarily tag too many "AttrUnknown"s in the caller. I think we may need to introduce another StratifiedAttr here just to distinguish between "things below parameters, which are known by the caller" and "things that are truly unknown, such as globals or inttoptr".

Anyway, whatever we do, that's going to be the story for the next patch :)

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

792 ↗

(On Diff #61307)

After a second thought, maybe AttrEscaped is useful to the caller as well...

[george.burgess.iv]

lib/Analysis/CFLAliasAnalysis.cpp

755 ↗

(On Diff #61307)

at least I myself rarely write functions that handle pointers of >3 depth

FWIW, RetVals[I]->getType() goes through 3 levels of indirection, since RetVals is a reference to a vector of pointers. :)

However, normally I wouldn't expect m to be greater than 3 in most cases

I'd buy that both m and n are generally going to stay < 8 for the vast majority of real-world code, yeah.

the InterfaceMap population algorithm should be executed in a "breadth-first" manner rather than a "depth-first"

Sounds correct to me.

758 ↗

(On Diff #61307)

I thought that initially, too -- the answer is apparently "nope". Only things that you actually use in the lambda need to be captured; if you like to read standardese, 5.1.2p12 (and bits around there) may be interesting to you.

792 ↗

(On Diff #61307)

AttrGlobal would probably be useful, too. As would AttrUnknown under any sets tagged with AttrGlobal. :)

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

755 ↗

(On Diff #61307)

Now that I think about it, I'm not so sure if skipping shortcut exit is a safe option. My concern is a case like this:

a
^
b  < d
^
c

, where two parameters both belongs to set b, yet their dereferences belongs to set c and d, resp. If this is possible (which I assume highly likely since otherwise the analysis becomes indistinguishable from Steensgard), then "A and B aliases implies *A and *B also aliases" is going to be a false statement.

[grievejia]

Style update

[george.burgess.iv]

lib/Analysis/CFLAliasAnalysis.cpp

760 ↗

(On Diff #61569)

Currently, we unify stratifiedsets both upwards and downwards -- the reason behind this is "that's how I interpreted the paper when I wrote StratifiedSets." :P

If you want to fix that, then feel free. And yeah, if we do change stratifiedsets to that model, then my proposed approach is broken.

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

760 ↗

(On Diff #61569)

I'll probably kick off another discussion on the topic of unifying strategy: its impact on performance can be very, very big...

[grievejia]

Added early exit in summary construction.

[grievejia]

Another minor style update

[george.burgess.iv]

LGTM -- will commit tomorrow.

Thanks for the patch!

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
+/// We use InterfaceValue to describe parameters/return value, as well as
+/// potential memory locations that are pointed to by parameters/return value,
+/// of a function.
+/// Index is an integer which represents a single parameter or a return value.
+/// When the index is 0, it refers to the return value. Non-zero index i refers
+/// to the i-th parameter.
+/// DerefLevel indicates the number of dereferences one must perform on the
+/// parameter/return value to get this InterfaceValue.
+struct InterfaceValue {
+  unsigned Index;
+  unsigned DerefLevel;
+};
+
+bool operator==(InterfaceValue lhs, InterfaceValue rhs) {
+  return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel;
+}
+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.
-/// 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;
+  InterfaceValue From, To;
 };
 
 /// Information we have about a function and would like to keep around.
 class CFLAAResult::FunctionInfo {
   StratifiedSets<Value *> Sets;
 
   // RetParamRelations is a collection of ExternalRelations.
   SmallVector<ExternalRelation, 8> RetParamRelations;
return make_range<const_node_iterator>(
         map_iterator(NodeImpls.begin(), NodeDerefFun(nodeDeref)),
         map_iterator(NodeImpls.end(), NodeDerefFun(nodeDeref)));
   }
 
   bool empty() const { return NodeImpls.empty(); }
   std::size_t size() const { return NodeImpls.size(); }
 };
 
+// Interprocedural assignment edges that CFLGraph may not easily model
+struct InterprocEdge {
+  struct Node {
+    Value *Value;
+    unsigned DerefLevel;
+  };
+
+  Node From, To;
+};
+
 /// Gets the edges our graph should have, based on an Instruction*
 class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
   CFLAAResult &AA;
   const TargetLibraryInfo &TLI;
 
   CFLGraph &Graph;
   SmallPtrSetImpl<Value *> &Externals;
   SmallPtrSetImpl<Value *> &Escapes;
+  SmallVectorImpl<InterprocEdge> &InterprocEdges;
 
   static bool hasUsefulEdges(ConstantExpr *CE) {
     // ConstantExpr doesn't have terminators, invokes, or fences, so only needs
     // to check for compares.
     return CE->getOpcode() != Instruction::ICmp &&
            CE->getOpcode() != Instruction::FCmp;
   }
 
void addEdge(Value *From, Value *To, EdgeType Type) {
     if (To != From)
       addNode(To);
     Graph.addEdge(From, To, Type);
   }
 
 public:
   GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI,
                   CFLGraph &Graph, SmallPtrSetImpl<Value *> &Externals,
-                  SmallPtrSetImpl<Value *> &Escapes)
-      : AA(AA), TLI(TLI), Graph(Graph), Externals(Externals), Escapes(Escapes) {
-  }
+                  SmallPtrSetImpl<Value *> &Escapes,
+                  SmallVectorImpl<InterprocEdge> &InterprocEdges)
+      : AA(AA), TLI(TLI), Graph(Graph), Externals(Externals), Escapes(Escapes),
+        InterprocEdges(InterprocEdges) {}
 
   void visitInstruction(Instruction &) {
     llvm_unreachable("Unsupported instruction encountered");
   }
 
   void visitPtrToIntInst(PtrToIntInst &Inst) {
     auto *Ptr = Inst.getOperand(0);
     addNodeWithAttr(Ptr, AttrEscaped);
bool tryInterproceduralAnalysis(CallSite CS,
     }
 
     for (auto *Fn : Fns) {
       auto &FnInfo = AA.ensureCached(Fn);
       assert(FnInfo.hasValue());
 
       auto &RetParamRelations = FnInfo->getRetParamRelations();
       for (auto &Relation : RetParamRelations) {
-        auto FromIndex = Relation.From;
-        auto ToIndex = Relation.To;
+        auto FromIndex = Relation.From.Index;
+        auto ToIndex = Relation.To.Index;
         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);
+            ToVal->getType()->isPointerTy()) {
+          auto FromLevel = Relation.From.DerefLevel;
+          auto ToLevel = Relation.To.DerefLevel;
+          InterprocEdges.push_back(
+              InterprocEdge{InterprocEdge::Node{FromVal, FromLevel},
+                            InterprocEdge::Node{ToVal, ToLevel}});
+        }
       }
     }
 
     return true;
   }
 
   void visitCallSite(CallSite CS) {
     auto Inst = CS.getInstruction();
class CFLGraphBuilder {
 
   // Output of the builder
   CFLGraph Graph;
   SmallVector<Value *, 4> ReturnedValues;
 
   // Auxiliary structures used by the builder
   SmallPtrSet<Value *, 8> ExternalValues;
   SmallPtrSet<Value *, 8> EscapedValues;
+  SmallVector<InterprocEdge, 8> InterprocEdges;
 
   // Helper functions
 
   // Determines whether or not we an instruction is useless to us (e.g.
   // FenceInst)
   static bool hasUsefulEdges(Instruction *Inst) {
     bool IsNonInvokeTerminator =
         isa<TerminatorInst>(Inst) && !isa<InvokeInst>(Inst);
void addInstructionToGraph(Instruction &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)
+    GetEdgesVisitor(Analysis, TLI, Graph, ExternalValues, EscapedValues,
+                    InterprocEdges)
         .visit(Inst);
   }
 
   // Builds the graph needed for constructing the StratifiedSets for the given
   // function
   void buildGraphFrom(Function &Fn) {
     for (auto &Bb : Fn.getBasicBlockList())
       for (auto &Inst : Bb.getInstList())
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 SmallVector<InterprocEdge, 8> &getInterprocEdges() const {
+    return InterprocEdges;
+  }
 };
 }
 
 //===----------------------------------------------------------------------===//
 // 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)) {
-  // Collect StratifiedInfo for each parameter
-  SmallVector<Optional<StratifiedInfo>, 8> 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;
+  // Historically, an arbitrary upper-bound of 50 args was selected. We may want
+  // to remove this if it doesn't really matter in practice.
+  if (Fn.arg_size() > MaxSupportedArgsInSummary)
+    return;
 
-      // 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;
+  DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
 
-        auto MaybeRelation =
-            getIndexRelation(Sets, MainInfo->Index, SubInfo->Index);
-        if (!MaybeRelation.hasValue())
-          continue;
-
-        RetParamRelations.push_back(ExternalRelation{1 + I, 1 + X});
-      }
+  // Our intention here is to record all InterfaceValues that share the same
+  // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
+  // have its StratifiedIndex scanned here and check if the index is presented
+  // in InterfaceMap: if it is not, we add the correspondence to the map;
+  // otherwise, an aliasing relation is found and we add it to
+  // RetParamRelations.
+  auto AddToRetParamRelations = [this, &InterfaceMap](
+      unsigned InterfaceIndex, StratifiedIndex SetIndex) {
+    unsigned Level = 0;
+    while (true) {
+      InterfaceValue CurrValue{InterfaceIndex, Level};
+
+      auto Itr = InterfaceMap.find(SetIndex);
+      if (Itr != InterfaceMap.end()) {
+        if (CurrValue != Itr->second)
+          RetParamRelations.push_back(ExternalRelation{CurrValue, Itr->second});
+        break;
+      } else
+        InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
 
-      // 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 &Link = Sets.getLink(SetIndex);
+      if (!Link.hasBelow())
+        break;
 
-        auto MaybeRelation =
-            getIndexRelation(Sets, MainInfo->Index, RetInfo->Index);
-        if (!MaybeRelation.hasValue())
-          continue;
+      ++Level;
+      SetIndex = Link.Below;
+    }
+  };
 
-        RetParamRelations.push_back(ExternalRelation{1 + I, 0});
-      }
+  // Populate RetParamRelations for return values
+  for (auto *RetVal : RetVals) {
+    auto RetInfo = Sets.find(RetVal);
+    if (RetInfo.hasValue())
+      AddToRetParamRelations(0, RetInfo->Index);
+
+  // Populate RetParamRelations for parameters
+  unsigned I = 0;
+  for (auto &Param : Fn.args()) {
+    if (Param.getType()->isPointerTy()) {
+      auto ParamInfo = Sets.find(&Param);
+      if (ParamInfo.hasValue())
+        AddToRetParamRelations(I + 1, ParamInfo->Index);
     }
+    ++I;
   }
 }
 
 // Builds the graph + StratifiedSets for a function.
 CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
   CFLGraphBuilder GraphBuilder(*this, TLI, *Fn);
   StratifiedSetsBuilder<Value *> SetBuilder;
 
for (auto *External : GraphBuilder.getExternalValues()) {
     SetBuilder.add(External);
     auto Attr = valueToAttr(External);
     if (Attr.hasValue()) {
       SetBuilder.noteAttributes(External, *Attr);
       SetBuilder.addAttributesBelow(External, AttrUnknown);
     }
   }
 
+  // Special handling for interprocedural aliases
+  for (auto &Edge : GraphBuilder.getInterprocEdges()) {
+    auto FromVal = Edge.From.Value;
+    auto ToVal = Edge.To.Value;
+    SetBuilder.add(FromVal);
+    SetBuilder.add(ToVal);
+    SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal,
+                            Edge.To.DerefLevel);
+  }
+
+  // Special handling for opaque external functions
   for (auto *Escape : GraphBuilder.getEscapedValues()) {
     SetBuilder.add(Escape);
     SetBuilder.noteAttributes(Escape, AttrEscaped);
     SetBuilder.addAttributesBelow(Escape, AttrUnknown);
   }
 
   return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
 }

llvm/trunk/lib/Analysis/StratifiedSets.h

public:
   }
 
   bool addWith(const T &Main, const T &ToAdd) {
     assert(has(Main));
     auto MainIndex = *indexOf(Main);
     return addAtMerging(ToAdd, MainIndex);
   }
 
+  /// \brief Merge the set "MainBelow"-levels below "Main" and the set
+  /// "ToAddBelow"-levels below "ToAdd".
+  void addBelowWith(const T &Main, unsigned MainBelow, const T &ToAdd,
+                    unsigned ToAddBelow) {
+    assert(has(Main));
+    assert(has(ToAdd));
+
+    auto GetIndexBelow = [this](StratifiedIndex Index, unsigned NumLevel) {
+      for (unsigned I = 0; I < NumLevel; ++I) {
+        auto Link = linksAt(Index);
+        Index = Link.hasBelow() ? Link.getBelow() : addLinkBelow(Index);
+      }
+      return Index;
+    };
+    auto MainIndex = GetIndexBelow(*indexOf(Main), MainBelow);
+    auto ToAddIndex = GetIndexBelow(*indexOf(ToAdd), ToAddBelow);
+    if (&linksAt(MainIndex) != &linksAt(ToAddIndex))
+      merge(MainIndex, ToAddIndex);
+  }
+
   void noteAttributes(const T &Main, const StratifiedAttrs &NewAttrs) {
     assert(has(Main));
     auto *Info = *get(Main);
     auto &Link = linksAt(Info->Index);
     Link.setAttrs(NewAttrs);
   }
 
 private:
StratifiedIndex addLinks() {
     Links.push_back(BuilderLink(Link));
     return Link;
   }
 
   bool inbounds(StratifiedIndex N) const { return N < Links.size(); }
 };
 }
 #endif // LLVM_ADT_STRATIFIEDSETS_H
 No newline at end of file

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

 ; 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
+
+; We could've proven the following facts if the analysis were inclusion-based:
+; NoAlias: i32*** %b, i32*** %pp
+; NoAlias: i32** %lb, i32** %p
 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
+
+; We could've proven the following facts if the analysis were inclusion-based:
+; NoAlias: i32** %b, i32** %p
 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-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
+
+; We could've proven the following facts if the analysis were inclusion-based:
+; NoAlias: i32* %a, i32* %b
+; NoAlias: i32* %b, i32* %lp
 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.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
+; CHECK: MayAlias: i32* %lp, i32* %lq
+
+; We could've proven the following facts if the analysis were inclusion-based:
+; NoAlias: i32* %a, i32* %b
+; NoAlias: i32* %a, 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