[CFLAA] Propagate StratifiedAttrs from callee to caller

[grievejia]

Summary

This patch adds yet another entry in CFLAAResult::FunctionInfo that keeps track of what StratifiedAttrs we should propagate for those InterfaceValues. This is crucial for the soundness of the analysis since otherwise the caller won't be able to know if the arguments they pass to the callee will escape/alias globals/alias unknown pointers or not.

Previously, anything below the arguments of the callee is marked with "AttrUnknown". This is too conservative, because although the callee doesn't know what's below those arguments, the caller has a perfect idea. It would be nice to distinguish between "things the caller knows but the callee doesn't" and "things that both caller and callee don't know". In this patch, we introduce another StratifiedAttr called "AttrCaller" to represent the former case, and let "AttrUnknown" to represent only the latter case. We also handle these two attributes differently in our interprocedural analysis: AttrUnknown needs to be propagated to the caller, while AttrCaller doesn't have to.

In addition to AttrUnknown, AttrEscaped and AttrGlobal are also propagated. Those are the three attributes that I think are meaningful to the caller.

With this patch I am finally able to turn the last two remaining xfail test cases into xpass. Yay!

[george.burgess.iv]

Thanks for the patch!

lib/Analysis/CFLAliasAnalysis.cpp

94 ↗

(On Diff #61683)

Nit: Please add a period.

107 ↗

(On Diff #61683)

Nit: Period, please.

151 ↗

(On Diff #61683)

Is there a reason this isn't a StratifiedAttrs? (The more we add here, the more I think having a separate type for a single bit and a set of bits was a dumb decision, but we can deal with that later)

267 ↗

(On Diff #61683)

Please rebase -- GCC didn't like the name of this variable. :)

(Don't worry about compiling with GCC before you throw a patch up for review; I'm happy to do it prior to submitting)

645 ↗

(On Diff #61683)

Nit: Is there a reason this isn't a member of the CFLGraphBuilder?

736 ↗

(On Diff #61683)

Do we need a .reset(AttrCallerIndex) here, as well?

828 ↗

(On Diff #61683)

Please remove the extra brackets

test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll

20 ↗

(On Diff #61683)

Yay accuracy

[grievejia]

Merged master, and updated several places according to the review.

lib/Analysis/CFLAliasAnalysis.cpp

645 ↗

(On Diff #61683)

Can you elaborate? Which variable did you refer to?

[george.burgess.iv]

LGTM. Thanks for the patch!

lib/Analysis/CFLAliasAnalysis.cpp

644–645 ↗

(On Diff #61745)

Sure -- why doesn't CFLGraphBuilder have a member of type GetEdgesVisitor, instead of constructing it in-place here? It doesn't really matter either way, I'm just wondering if there's a reason, since all we're basically doing is loading it up with member variables and calling visit.

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

644–645 ↗

(On Diff #61745)

But even if GetEdgeVisitor becomes a member of CFLGraphBuilder, we still have to load the member up and call visit, no?

[grievejia]

Thanks for the review!

llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp

 }
 
 /// We use ExternalRelation to describe an externally visible aliasing relations
 /// between parameters/return value of a function.
 struct ExternalRelation {
   InterfaceValue From, To;
 };
 
+/// We use ExternalAttribute to describe an externally visible StratifiedAttrs
+/// for parameters/return value.
+struct ExternalAttribute {
+  InterfaceValue IValue;
+  StratifiedAttrs Attr;
+};
+
 /// 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;
 
+  // RetParamAttributes is a collection of ExternalAttributes.
+  SmallVector<ExternalAttribute, 8> RetParamAttributes;
+
 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;
   }
+  const SmallVectorImpl<ExternalAttribute> &getRetParamAttributes() const {
+    return RetParamAttributes;
+  }
 };
 
 /// 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.
 static bool getPossibleTargets(CallSite, SmallVectorImpl<Function *> &);
 
 const StratifiedIndex StratifiedLink::SetSentinel =
     std::numeric_limits<StratifiedIndex>::max();
 
 namespace {
 /// StratifiedInfo Attribute things.
-typedef unsigned StratifiedAttr;
 LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs;
 LLVM_CONSTEXPR unsigned AttrEscapedIndex = 0;
 LLVM_CONSTEXPR unsigned AttrUnknownIndex = 1;
 LLVM_CONSTEXPR unsigned AttrGlobalIndex = 2;
-LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 3;
+LLVM_CONSTEXPR unsigned AttrCallerIndex = 3;
+LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4;
 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;
+LLVM_CONSTEXPR StratifiedAttrs AttrNone = 0;
+LLVM_CONSTEXPR StratifiedAttrs AttrEscaped = 1 << AttrEscapedIndex;
+LLVM_CONSTEXPR StratifiedAttrs AttrUnknown = 1 << AttrUnknownIndex;
+LLVM_CONSTEXPR StratifiedAttrs AttrGlobal = 1 << AttrGlobalIndex;
+LLVM_CONSTEXPR StratifiedAttrs AttrCaller = 1 << AttrCallerIndex;
+LLVM_CONSTEXPR StratifiedAttrs ExternalAttrMask =
+    (1 << AttrEscapedIndex) | (1 << AttrUnknownIndex) | (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 };
 
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 *Val;
-    unsigned DerefLevel;
-  };
+// This is the result of instantiating InterfaceValue at a particular callsite
+struct InterprocNode {
 
-  Node From, To;
+// Interprocedural assignment edges that CFLGraph may not easily model
+struct InterprocEdge {
+  InterprocNode From, To;
+};
+
+// Interprocedural attribute tagging that CFLGraph may not easily model
+struct InterprocAttr {
+  InterprocNode Node;
+  StratifiedAttrs Attr;
 };
 
 /// Gets the edges our graph should have, based on an Instruction*
 class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
   CFLAAResult &AA;
   const TargetLibraryInfo &TLI;
 
   CFLGraph &Graph;
+  SmallVectorImpl<Value *> &ReturnValues;
   SmallPtrSetImpl<Value *> &Externals;
   SmallPtrSetImpl<Value *> &Escapes;
   SmallVectorImpl<InterprocEdge> &InterprocEdges;
+  SmallVectorImpl<InterprocAttr> &InterprocAttrs;
 
   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) {
     addNode(From);
     if (To != From)
       addNode(To);
     Graph.addEdge(From, To, Type);
   }
 
 public:
   GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI,
-                  CFLGraph &Graph, SmallPtrSetImpl<Value *> &Externals,
+                  CFLGraph &Graph, SmallVectorImpl<Value *> &ReturnValues,
+                  SmallPtrSetImpl<Value *> &Externals,
                   SmallPtrSetImpl<Value *> &Escapes,
-                  SmallVectorImpl<InterprocEdge> &InterprocEdges)
-      : AA(AA), TLI(TLI), Graph(Graph), Externals(Externals), Escapes(Escapes),
-        InterprocEdges(InterprocEdges) {}
+                  SmallVectorImpl<InterprocEdge> &InterprocEdges,
+                  SmallVectorImpl<InterprocAttr> &InterprocAttrs)
+      : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues),
+        Externals(Externals), Escapes(Escapes), InterprocEdges(InterprocEdges),
+        InterprocAttrs(InterprocAttrs) {}
 
   void visitInstruction(Instruction &) {
     llvm_unreachable("Unsupported instruction encountered");
   }
 
+  void visitReturnInst(ReturnInst &Inst) {
+    if (auto RetVal = Inst.getReturnValue()) {
+      if (RetVal->getType()->isPointerTy()) {
+        addNode(RetVal);
+        ReturnValues.push_back(RetVal);
+      }
+    }
+  }
+
   void visitPtrToIntInst(PtrToIntInst &Inst) {
     auto *Ptr = Inst.getOperand(0);
     addNodeWithAttr(Ptr, AttrEscaped);
   }
 
   void visitIntToPtrInst(IntToPtrInst &Inst) {
     auto *Ptr = &Inst;
     addNodeWithAttr(Ptr, AttrUnknown);
for (auto *Fn : Fns) {
         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;
     }
 
+    auto InstantiateInterfaceIndex = [&CS](unsigned Index) {
+      auto Value =
+          (Index == 0) ? CS.getInstruction() : CS.getArgument(Index - 1);
+      return Value->getType()->isPointerTy() ? Value : nullptr;
+    };
+
     for (auto *Fn : Fns) {
       auto &FnInfo = AA.ensureCached(Fn);
       assert(FnInfo.hasValue());
 
       auto &RetParamRelations = FnInfo->getRetParamRelations();
       for (auto &Relation : RetParamRelations) {
-        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()) {
+        auto FromVal = InstantiateInterfaceIndex(Relation.From.Index);
+        auto ToVal = InstantiateInterfaceIndex(Relation.To.Index);
+        if (FromVal && ToVal) {
           auto FromLevel = Relation.From.DerefLevel;
           auto ToLevel = Relation.To.DerefLevel;
           InterprocEdges.push_back(
-              InterprocEdge{InterprocEdge::Node{FromVal, FromLevel},
-                            InterprocEdge::Node{ToVal, ToLevel}});
+              InterprocEdge{InterprocNode{FromVal, FromLevel},
+                            InterprocNode{ToVal, ToLevel}});
+        }
+      }
+
+      auto &RetParamAttributes = FnInfo->getRetParamAttributes();
+      for (auto &Attribute : RetParamAttributes) {
+        if (auto Val = InstantiateInterfaceIndex(Attribute.IValue.Index)) {
+          InterprocAttrs.push_back(InterprocAttr{
+              InterprocNode{Val, Attribute.IValue.DerefLevel}, Attribute.Attr});
         }
       }
     }
 
     return true;
   }
 
   void visitCallSite(CallSite CS) {
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;
+  SmallVector<InterprocAttr, 8> InterprocAttrs;
 
   // 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);
+    bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
+                                    !isa<InvokeInst>(Inst) &&
+                                    !isa<ReturnInst>(Inst);
     return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
-           !IsNonInvokeTerminator;
+           !IsNonInvokeRetTerminator;
   }
 
   void addArgumentToGraph(Argument &Arg) {
     if (Arg.getType()->isPointerTy()) {
       Graph.addNode(&Arg);
       ExternalValues.insert(&Arg);
     }
   }
 
   // Given an Instruction, this will add it to the graph, along with any
   // 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 (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,
-                    InterprocEdges)
+    GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues,
+                    EscapedValues, InterprocEdges, InterprocAttrs)
         .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 SmallPtrSet<Value *, 8> &getExternalValues() const {
     return ExternalValues;
   }
   const SmallPtrSet<Value *, 8> &getEscapedValues() const {
     return EscapedValues;
   }
   const SmallVector<InterprocEdge, 8> &getInterprocEdges() const {
     return InterprocEdges;
   }
+  const SmallVector<InterprocAttr, 8> &getInterprocAttrs() const {
+    return InterprocAttrs;
+  }
 };
 }
 
 //===----------------------------------------------------------------------===//
 // Function declarations that require types defined in the namespace above
 //===----------------------------------------------------------------------===//
 
 /// Given a StratifiedAttrs, returns true if it marks the corresponding values
 /// as globals or arguments
 static bool isGlobalOrArgAttr(StratifiedAttrs Attr);
 
 /// Given a StratifiedAttrs, returns true if the corresponding values come from
 /// an unknown source (such as opaque memory or an integer cast)
 static bool isUnknownAttr(StratifiedAttrs Attr);
 
 /// Given an argument number, returns the appropriate StratifiedAttr to set.
-static StratifiedAttr argNumberToAttr(unsigned ArgNum);
+static StratifiedAttrs argNumberToAttr(unsigned ArgNum);
 
 /// Given a Value, potentially return which StratifiedAttr it maps to.
-static Optional<StratifiedAttr> valueToAttr(Value *Val);
+static Optional<StratifiedAttrs> valueToAttr(Value *Val);
 
 /// Gets the "Level" that one should travel in StratifiedSets
 /// given an EdgeType.
 static Level directionOfEdgeType(EdgeType);
 
 /// Determines whether it would be pointless to add the given Value to our sets.
 static bool canSkipAddingToSets(Value *Val);
 
static bool getPossibleTargets(CallSite CS,
   }
 
   // TODO: If the call is indirect, we might be able to enumerate all potential
   // targets of the call and return them, rather than just failing.
   return false;
 }
 
 static bool isGlobalOrArgAttr(StratifiedAttrs Attr) {
-  return Attr.reset(AttrEscapedIndex).reset(AttrUnknownIndex).any();
+  return Attr.reset(AttrEscapedIndex)
+      .reset(AttrUnknownIndex)
+      .reset(AttrCallerIndex)
+      .any();
 }
 
 static bool isUnknownAttr(StratifiedAttrs Attr) {
-  return Attr.test(AttrUnknownIndex);
+  return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex);
 }
 
-static Optional<StratifiedAttr> valueToAttr(Value *Val) {
+static Optional<StratifiedAttrs> valueToAttr(Value *Val) {
   if (isa<GlobalValue>(Val))
     return AttrGlobal;
 
   if (auto *Arg = dyn_cast<Argument>(Val))
     // Only pointer arguments should have the argument attribute,
     // because things can't escape through scalars without us seeing a
     // cast, and thus, interaction with them doesn't matter.
     if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())
       return argNumberToAttr(Arg->getArgNo());
   return None;
 }
 
-static StratifiedAttr argNumberToAttr(unsigned ArgNum) {
+static StratifiedAttrs argNumberToAttr(unsigned ArgNum) {
   if (ArgNum >= AttrMaxNumArgs)
     return AttrUnknown;
-  return 1 << (ArgNum + AttrFirstArgIndex);
+  return StratifiedAttrs(1 << (ArgNum + AttrFirstArgIndex));
 }
 
 static Level directionOfEdgeType(EdgeType Weight) {
   switch (Weight) {
   case EdgeType::Reference:
     return Level::Above;
   case EdgeType::Dereference:
     return Level::Below;
CFLAAResult::FunctionInfo::FunctionInfo(Function &Fn,
   DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
 
   // 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 = [&](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));
+      }
 
       auto &Link = Sets.getLink(SetIndex);
+      InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
+      auto ExternalAttrs = Link.Attrs & ExternalAttrMask;
+      if (ExternalAttrs.any())
+        RetParamAttributes.push_back(
+            ExternalAttribute{CurrValue, ExternalAttrs});
+
       if (!Link.hasBelow())
         break;
 
       ++Level;
       SetIndex = Link.Below;
     }
   };
 
   // Populate RetParamRelations for return values
   for (auto *RetVal : RetVals) {
+    assert(RetVal != nullptr);
+    assert(RetVal->getType()->isPointerTy());
     auto RetInfo = Sets.find(RetVal);
     if (RetInfo.hasValue())
       AddToRetParamRelations(0, RetInfo->Index);
   }
 
   // Populate RetParamRelations for parameters
   unsigned I = 0;
   for (auto &Param : Fn.args()) {
CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
   }
 
   // Special handling for globals and arguments
   for (auto *External : GraphBuilder.getExternalValues()) {
     SetBuilder.add(External);
     auto Attr = valueToAttr(External);
     if (Attr.hasValue()) {
       SetBuilder.noteAttributes(External, *Attr);
-      SetBuilder.addAttributesBelow(External, AttrUnknown);
+      if (*Attr == AttrGlobal)
+        SetBuilder.addAttributesBelow(External, 1, AttrUnknown);
+      else
+        SetBuilder.addAttributesBelow(External, 1, AttrCaller);
     }
   }
 
   // Special handling for interprocedural aliases
   for (auto &Edge : GraphBuilder.getInterprocEdges()) {
     auto FromVal = Edge.From.Val;
     auto ToVal = Edge.To.Val;
     SetBuilder.add(FromVal);
     SetBuilder.add(ToVal);
     SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal,
                             Edge.To.DerefLevel);
   }
 
+  // Special handling for interprocedural attributes
+  for (auto &IPAttr : GraphBuilder.getInterprocAttrs()) {
+    auto Val = IPAttr.Node.Val;
+    SetBuilder.add(Val);
+    SetBuilder.addAttributesBelow(Val, IPAttr.Node.DerefLevel, IPAttr.Attr);
+  }
+
   // Special handling for opaque external functions
   for (auto *Escape : GraphBuilder.getEscapedValues()) {
     SetBuilder.add(Escape);
     SetBuilder.noteAttributes(Escape, AttrEscaped);
-    SetBuilder.addAttributesBelow(Escape, AttrUnknown);
+    SetBuilder.addAttributesBelow(Escape, 1, AttrUnknown);
   }
 
   return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
 }
 
 void CFLAAResult::scan(Function *Fn) {
   auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
   (void)InsertPair;

llvm/trunk/lib/Analysis/StratifiedSets.h

bool addBelow(const T &Main, const T &ToAdd) {
     auto Index = *indexOf(Main);
     if (!linksAt(Index).hasBelow())
       addLinkBelow(Index);
 
     auto Below = linksAt(Index).getBelow();
     return addAtMerging(ToAdd, Below);
   }
 
-  /// \brief Set the StratifiedAttrs of the set below "Main". If there is no set
-  /// below "Main", create one for it.
-  void addAttributesBelow(const T &Main, StratifiedAttrs Attr) {
+  /// \brief Set the StratifiedAttrs of the set "Level"-levels below "Main". If
+  /// there is no set below "Main", create one for it.
+  void addAttributesBelow(const T &Main, unsigned Level, StratifiedAttrs Attr) {
     assert(has(Main));
     auto Index = *indexOf(Main);
-    auto Link = linksAt(Index);
+    auto *Link = &linksAt(Index);
 
-    auto BelowIndex = Link.hasBelow() ? Link.getBelow() : addLinkBelow(Index);
-    linksAt(BelowIndex).setAttrs(Attr);
+    for (unsigned I = 0; I < Level; ++I) {
+      Index = Link->hasBelow() ? Link->getBelow() : addLinkBelow(Index);
+      Link = &linksAt(Index);
+    }
+    Link->setAttrs(Attr);
   }
 
   bool addWith(const T &Main, const T &ToAdd) {
     assert(has(Main));
     auto MainIndex = *indexOf(Main);
     return addAtMerging(ToAdd, MainIndex);
   }
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/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-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
+
+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/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-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
+
+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/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-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
+
+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/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
+}
+
+@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/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
+; 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