[CFLAA] Tag actual arguments as AttrEscaped instead of AttrUnknown

[grievejia]

Summary

The primary focus of this patch is to mark actual arguments AttrEscaped and mark everything they point to AttrUnknown. This allows us to get better precision when an alias query contains at least one value that escapes by being an argument at an opaque callsite.

It also did a bit of refactoring for the graph building codes. I probably need to apologize, since I should have separate the refactoring and the functionality changes into two different patches.

[grievejia]

Separate escaped values from external values

[george.burgess.iv]

Yay precision!

I should have separate the refactoring and the functionality changes into two different patches

So... why wasn't this done, then?

lib/Analysis/CFLAliasAnalysis.cpp

132

Redundant private

194–207

Looks like all the users of this fail if we return null. Is there a reason we try to handle it gracefully here?

200

Same here.

216

FWIW, I had to remove these ctors from D21233, because they made the windows buildbots angry. Apparently it's a bug in MSVC2013.

If these don't have any use, please remove them from this patch, as well.

232

Style nit: Braces.

365

Comment disappeared?

366

Is there a reason we went from /// to // for these?

478

const auto &

497–498

Useless braces

499–500

Please fold this into the above condition

504–505

Useless braces

511

Please remove the braces here and below...

(And the parens on !CS.onlyReadsMemory())

511

Why do we care about the size of Targets here? Looks like we'll mark nothing as escaped if we can't find a target of a function.

517

auto *

518

Looks like we won't add this to the sets if Fn->doesNotAlias(0).

651

Is there a reason we can't hand back a const& here instead?

Also, same thoughts about things that look+feel like accessors (but call move) as in D21261.

654

And here

809–810

This seems pointless to have as a lambda if we're just using it in one place.

820

Same for this.

826

If we hand back a const& above, this needs to become a const auto&. Also, why not just call GraphBuilder.getExternalValues() in the range for?

827

auto *

830

This, too.

831

auto *

test/Analysis/CFLAliasAnalysis/attr-escape.ll

53

Can we have a test for callsites marked as readonly, (if we currently support them) as well?

[grievejia]

In D21262#456620, @george.burgess.iv wrote:

I should have separate the refactoring and the functionality changes into two different patches

So... why wasn't this done, then?

By the time I realized this, I've already made too many modifications...

Also, let me rebase this patch to get rid of the changes that have already been applied to the patch that this one depends on (apparently there doesn't seem to have "phabricator rebase" functionality...).

[grievejia]

In D21262#456704, @grievejia wrote:

Also, let me rebase this patch to get rid of the changes that have already been applied to the patch that this one depends on (apparently there doesn't seem to have "phabricator rebase" functionality...).

Sorry, I meant "to include the changes that have already been...".

lib/Analysis/CFLAliasAnalysis.cpp

194–207

IMO deferring the null-check to the users is more flexible. If we hardcode the check inside this function, things could become ugly if we add another user that wants the result of the lookup but doesn't want to panic if the lookup fails.

We only have two callers here, so I guess the typing overhead is still acceptable?

216

This will be fixed by the rebase.

232

What exactly is the problem here? Should I remove the braces after "if (auto CExpr = ...", or should I add braces after "if (hasUsefulEdges..."?

365

Ooops...

366

The struct becomes private. Only tryInterproceduralAnalysis() uses it now.

511

I wasn't quite sure whether to use CS.onlyReadsMemory() or CS.getCalledFunction()->onlyReadsMemory() here. It looks like the two functions essentially do the same thing. Initially used the latter and switched to the former after a while (the size check was there just to make sure CS.getCalledFunction() != nullptr). So I think I'll just remove it now.

518

Which is intended: noalias return values are treated like mallocs.

test/Analysis/CFLAliasAnalysis/attr-escape.ll

53

I'm not aware that we can mark the callsite (instead of the function) readonly. How can we distinguish the two in our codes?

[grievejia]

Rebase and style updates.

[george.burgess.iv]

lib/Analysis/CFLAliasAnalysis.cpp

132

Not done

194–208

If we see the flexibility being useful in the future, then I'm fine with it; I was just wondering if this was intentional or not.

216

Looks like they might have slipped by. :)

232

The former, please.

Generally, the style rule is "useless braces shouldn't exist, unless they help readability somehow."

366

I don't see what that has to do with the comment style, but I agree that it probably doesn't matter.

511

Sounds good.

(Also, it looks like CS.onlyReadsMemory() will check for callsite attributes (e.g. readonly/readnone) for us, so you picked the better option there, I think.)

518

Ah, I forgot that we added the nodes at the beginning of the function now -- my mistake. :)

test/Analysis/CFLAliasAnalysis/attr-escape.ll

53

If you're talking about tests, call void @foo(args) readonly is the syntax, IIRC. It's definitely less common than just using a function-level attribute.

If you're talking about in CFLAA, I think I sort of addressed that in an earlier response.

[grievejia]

More style fixes and an updated test.

[george.burgess.iv]

LGTM. Thanks for the patch!

[grievejia]

lib/Analysis/CFLAliasAnalysis.cpp

366

It's not exposed to the outside world so I assume we don't need to use Doxygen style comment?

lib/Analysis/CFLAliasAnalysis.cpp

 };
 
 /// 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.
-template <typename Inst>
-static bool getPossibleTargets(Inst *, SmallVectorImpl<Function *> &);
-
-/// Some instructions need to have their users tracked. Instructions like
-/// `add` require you to get the users of the Instruction* itself, other
-/// instructions like `store` require you to get the users of the first
-/// operand. This function gets the "proper" value to track for each
-/// type of instruction we support.
-static Optional<Value *> getTargetValue(Instruction *);
+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;
enum class EdgeType {
 
   /// The edge used when our edge goes from a value to a handle that may have
   /// contained it at some point. Examples:
   /// %b = load %a              (%a Reference %b)
   /// %b = extractelement %a, 0 (%b Reference %a)
   Reference
 };
 
-// \brief Encodes the notion of a "use"
+/// The Program Expression Graph (PEG) of CFL analysis
+class CFLGraph {
+  typedef Value *Node;
+
   struct Edge {
-  /// Which value the edge is coming from
-  Value *From;
+    StratifiedAttrs Attr;
+    EdgeType Type;
+    Node Other;
+  };
 
-  /// Which value the edge is pointing to
-  Value *To;
+  typedef std::vector<Edge> EdgeList;
+  typedef DenseMap<Node, EdgeList> NodeMap;
+  NodeMap NodeImpls;
 
-  /// Edge weight
-  EdgeType Weight;
+  // Gets the inverse of a given EdgeType.
+  static EdgeType flipWeight(EdgeType Initial) {
+    switch (Initial) {
+    case EdgeType::Assign:
+      return EdgeType::Assign;
+    case EdgeType::Dereference:
+      return EdgeType::Reference;
+    case EdgeType::Reference:
+      return EdgeType::Dereference;
+    }
+    llvm_unreachable("Incomplete coverage of EdgeType enum");
+  }
 
-  /// Whether we aliased any external values along the way that may be
-  /// invisible to the analysis (i.e. landingpad for exceptions, calls for
-  /// interprocedural analysis, etc.)
-  StratifiedAttrs AdditionalAttrs;
+  const EdgeList *getNode(Node N) const {
+    auto Itr = NodeImpls.find(N);
+    if (Itr == NodeImpls.end())
+      return nullptr;
+    return &Itr->second;
+  }
+  EdgeList *getNode(Node N) {
+    auto Itr = NodeImpls.find(N);
+    if (Itr == NodeImpls.end())
+      return nullptr;
+    return &Itr->second;
+  }
+
+  static Node nodeDeref(const NodeMap::value_type &P) { return P.first; }
+  typedef std::pointer_to_unary_function<const NodeMap::value_type &, Node>
+      NodeDerefFun;
 
-  Edge(Value *From, Value *To, EdgeType W, StratifiedAttrs A)
-      : From(From), To(To), Weight(W), AdditionalAttrs(A) {}
+public:
+  typedef EdgeList::const_iterator const_edge_iterator;
+  typedef mapped_iterator<NodeMap::const_iterator, NodeDerefFun>
+      const_node_iterator;
+
+  bool addNode(Node N) {
+    return NodeImpls.insert(std::make_pair(N, EdgeList())).second;
+  }
+
+  void addEdge(Node From, Node To, EdgeType Type,
+               StratifiedAttrs Attr = StratifiedAttrs()) {
+    auto FromEdges = getNode(From);
+    assert(FromEdges != nullptr);
+    auto ToEdges = getNode(To);
+    assert(ToEdges != nullptr);
+
+    FromEdges->push_back(Edge{Attr, Type, To});
+    ToEdges->push_back(Edge{Attr, flipWeight(Type), From});
+  }
+
+  iterator_range<const_edge_iterator> edgesFor(Node N) const {
+    auto Edges = getNode(N);
+    assert(Edges != nullptr);
+    return make_range(Edges->begin(), Edges->end());
+  }
+
+  iterator_range<const_node_iterator> nodes() const {
+    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(); }
 };
 
 /// Gets the edges our graph should have, based on an Instruction*
 class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
   CFLAAResult &AA;
-  SmallVectorImpl<Edge> &Output;
   const TargetLibraryInfo &TLI;
 
+  CFLGraph &Graph;
+  SmallPtrSetImpl<Value *> &Externals;
+  SmallPtrSetImpl<Value *> &Escapes;
+
+  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 addNode(Value *Val) {
+    if (!Graph.addNode(Val))
+      return;
+
+    if (isa<GlobalValue>(Val))
+      Externals.insert(Val);
+    else if (auto CExpr = dyn_cast<ConstantExpr>(Val))
+      if (hasUsefulEdges(CExpr))
+        visitConstantExpr(CExpr);
+  }
+
+  void addEdge(Value *From, Value *To, EdgeType Type, StratifiedAttrs Attr) {
+    addNode(From);
+    if (To != From)
+      addNode(To);
+    Graph.addEdge(From, To, Type, Attr);
+  }
+
 public:
-  GetEdgesVisitor(CFLAAResult &AA, SmallVectorImpl<Edge> &Output,
-                  const TargetLibraryInfo &TLI)
-      : AA(AA), Output(Output), TLI(TLI) {}
+  GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI,
+                  CFLGraph &Graph, SmallPtrSetImpl<Value *> &Externals,
+                  SmallPtrSetImpl<Value *> &Escapes)
+      : AA(AA), TLI(TLI), Graph(Graph), Externals(Externals), Escapes(Escapes) {
+  }
 
   void visitInstruction(Instruction &) {
     llvm_unreachable("Unsupported instruction encountered");
   }
 
   void visitPtrToIntInst(PtrToIntInst &Inst) {
     auto *Ptr = Inst.getOperand(0);
-    Output.push_back(Edge(Ptr, &Inst, EdgeType::Assign, AttrEscaped));
+    addEdge(Ptr, &Inst, EdgeType::Assign, AttrEscaped);
   }
 
   void visitIntToPtrInst(IntToPtrInst &Inst) {
     auto *Ptr = &Inst;
-    Output.push_back(Edge(Ptr, Ptr, EdgeType::Assign, AttrUnknown));
+    addEdge(Ptr, Ptr, EdgeType::Assign, AttrUnknown);
   }
 
   void visitCastInst(CastInst &Inst) {
-    Output.push_back(
-        Edge(&Inst, Inst.getOperand(0), EdgeType::Assign, AttrNone));
+    auto *Src = Inst.getOperand(0);
+    addEdge(Src, &Inst, EdgeType::Assign, AttrNone);
   }
 
   void visitBinaryOperator(BinaryOperator &Inst) {
     auto *Op1 = Inst.getOperand(0);
     auto *Op2 = Inst.getOperand(1);
-    Output.push_back(Edge(&Inst, Op1, EdgeType::Assign, AttrNone));
-    Output.push_back(Edge(&Inst, Op2, EdgeType::Assign, AttrNone));
+    addEdge(Op1, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(Op2, &Inst, EdgeType::Assign, AttrNone);
   }
 
   void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
     auto *Ptr = Inst.getPointerOperand();
     auto *Val = Inst.getNewValOperand();
-    Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone));
+    addEdge(Ptr, Val, EdgeType::Dereference, AttrNone);
   }
 
   void visitAtomicRMWInst(AtomicRMWInst &Inst) {
     auto *Ptr = Inst.getPointerOperand();
     auto *Val = Inst.getValOperand();
-    Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone));
+    addEdge(Ptr, Val, EdgeType::Dereference, AttrNone);
   }
 
   void visitPHINode(PHINode &Inst) {
     for (Value *Val : Inst.incoming_values())
-      Output.push_back(Edge(&Inst, Val, EdgeType::Assign, AttrNone));
+      addEdge(Val, &Inst, EdgeType::Assign, AttrNone);
   }
 
   void visitGetElementPtrInst(GetElementPtrInst &Inst) {
     auto *Op = Inst.getPointerOperand();
-    Output.push_back(Edge(&Inst, Op, EdgeType::Assign, AttrNone));
+    addEdge(Op, &Inst, EdgeType::Assign, AttrNone);
   }
 
   void visitSelectInst(SelectInst &Inst) {
     // Condition is not processed here (The actual statement producing
     // the condition result is processed elsewhere). For select, the
     // condition is evaluated, but not loaded, stored, or assigned
     // simply as a result of being the condition of a select.
 
     auto *TrueVal = Inst.getTrueValue();
-    Output.push_back(Edge(&Inst, TrueVal, EdgeType::Assign, AttrNone));
     auto *FalseVal = Inst.getFalseValue();
-    Output.push_back(Edge(&Inst, FalseVal, EdgeType::Assign, AttrNone));
+    addEdge(TrueVal, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(FalseVal, &Inst, EdgeType::Assign, AttrNone);
   }
 
-  void visitAllocaInst(AllocaInst &) {}
+  void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); }
 
   void visitLoadInst(LoadInst &Inst) {
     auto *Ptr = Inst.getPointerOperand();
     auto *Val = &Inst;
-    Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone));
+    addEdge(Val, Ptr, EdgeType::Reference, AttrNone);
   }
 
   void visitStoreInst(StoreInst &Inst) {
     auto *Ptr = Inst.getPointerOperand();
     auto *Val = Inst.getValueOperand();
-    Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone));
+    addEdge(Ptr, Val, EdgeType::Dereference, AttrNone);
   }
 
   void visitVAArgInst(VAArgInst &Inst) {
     // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it does
     // two things:
     //  1. Loads a value from *((T*)*Ptr).
     //  2. Increments (stores to) *Ptr by some target-specific amount.
     // For now, we'll handle this like a landingpad instruction (by placing the
     // result in its own group, and having that group alias externals).
     auto *Val = &Inst;
-    Output.push_back(Edge(Val, Val, EdgeType::Assign, AttrUnknown));
+    addEdge(Val, Val, EdgeType::Assign, 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.
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 (i.e. landingpad for exceptions, calls for
+    // interprocedural analysis, etc.)
+    StratifiedAttrs AdditionalAttrs;
+  };
+
   bool
   tryInterproceduralAnalysis(const SmallVectorImpl<Function *> &Fns,
                              Value *FuncValue,
                              const iterator_range<User::op_iterator> &Args) {
     const unsigned ExpectedMaxArgs = 8;
     const unsigned MaxSupportedArgs = 50;
     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)
       return false;
 
     // Exit early if we'll fail anyway
     for (auto *Fn : Fns) {
       if (isFunctionExternal(Fn) || Fn->isVarArg())
         return false;
       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 *Fn : Fns) {
               getIndexRelation(Sets, ParamInfo.Index, RetInfo.Index);
           if (MaybeRelation.hasValue()) {
             AddEdge = true;
             Externals |= RetAttrs | ParamAttrs;
           }
         }
         if (AddEdge)
           Output.push_back(
-              Edge(FuncValue, ArgVal, EdgeType::Assign, Externals));
+              Edge{FuncValue, ArgVal, EdgeType::Assign, Externals});
       }
 
       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; }
for (auto *Fn : Fns) {
           auto &SubAttrs = Sets.getLink(SubInfo.Index).Attrs;
           auto MaybeRelation =
               getIndexRelation(Sets, MainInfo.Index, SubInfo.Index);
 
           if (!MaybeRelation.hasValue())
             continue;
 
           auto NewAttrs = SubAttrs | MainAttrs;
-          Output.push_back(Edge(MainVal, SubVal, EdgeType::Assign, NewAttrs));
+          Output.push_back(Edge{MainVal, SubVal, EdgeType::Assign, NewAttrs});
         }
       }
     }
+
+    // Commit all edges in Output to CFLGraph
+    for (const auto &Edge : Output)
+      addEdge(Edge.From, Edge.To, Edge.Weight, Edge.AdditionalAttrs);
+
     return true;
   }
 
-  template <typename InstT> void visitCallLikeInst(InstT &Inst) {
+  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())
+      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)) {
-      Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrNone));
-      return;
-    } else if (isFreeCall(&Inst, &TLI)) {
-      assert(Inst.getNumArgOperands() == 1);
-      auto argVal = Inst.arg_begin()->get();
-      Output.push_back(Edge(argVal, argVal, EdgeType::Assign, AttrNone));
+    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(&Inst, Targets)) {
-      if (tryInterproceduralAnalysis(Targets, &Inst, Inst.arg_operands()))
+    if (getPossibleTargets(CS, Targets))
+      if (tryInterproceduralAnalysis(Targets, Inst, CS.args()))
         return;
-      // Cleanup from interprocedural analysis
-      Output.clear();
-    }
 
     // Because the function is opaque, we need to note that anything
-    // could have happened to the arguments, and that the result could alias
-    // just about anything, too.
-    // The goal of the loop is in part to unify many Values into one set, so we
-    // don't care if the function is void there.
-    for (Value *V : Inst.arg_operands())
-      Output.push_back(Edge(&Inst, V, EdgeType::Assign, AttrUnknown));
-    if (Inst.getNumArgOperands() == 0 &&
-        Inst.getType() != Type::getVoidTy(Inst.getContext()))
-      Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrUnknown));
+    // 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()) {
+        Escapes.insert(V);
       }
 
-  void visitCallInst(CallInst &Inst) { visitCallLikeInst(Inst); }
-
-  void visitInvokeInst(InvokeInst &Inst) { visitCallLikeInst(Inst); }
+    if (!Inst->getType()->isVoidTy()) {
+      auto *Fn = CS.getCalledFunction();
+      if (Fn == nullptr || !Fn->doesNotAlias(0))
+        addEdge(Inst, Inst, EdgeType::Assign, AttrUnknown);
+    }
+  }
 
   /// Because vectors/aggregates are immutable and unaddressable, there's
   /// nothing we can do to coax a value out of them, other than calling
   /// Extract{Element,Value}. We can effectively treat them as pointers to
   /// arbitrary memory locations we can store in and load from.
   void visitExtractElementInst(ExtractElementInst &Inst) {
     auto *Ptr = Inst.getVectorOperand();
     auto *Val = &Inst;
-    Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone));
+    addEdge(Val, Ptr, EdgeType::Reference, AttrNone);
   }
 
   void visitInsertElementInst(InsertElementInst &Inst) {
     auto *Vec = Inst.getOperand(0);
     auto *Val = Inst.getOperand(1);
-    Output.push_back(Edge(&Inst, Vec, EdgeType::Assign, AttrNone));
-    Output.push_back(Edge(&Inst, Val, EdgeType::Dereference, AttrNone));
+    addEdge(Vec, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(&Inst, Val, EdgeType::Dereference, AttrNone);
   }
 
   void visitLandingPadInst(LandingPadInst &Inst) {
     // Exceptions come from "nowhere", from our analysis' perspective.
     // So we place the instruction its own group, noting that said group may
     // alias externals
-    Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrUnknown));
+    addEdge(&Inst, &Inst, EdgeType::Assign, AttrUnknown);
   }
 
   void visitInsertValueInst(InsertValueInst &Inst) {
     auto *Agg = Inst.getOperand(0);
     auto *Val = Inst.getOperand(1);
-    Output.push_back(Edge(&Inst, Agg, EdgeType::Assign, AttrNone));
-    Output.push_back(Edge(&Inst, Val, EdgeType::Dereference, AttrNone));
+    addEdge(Agg, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(&Inst, Val, EdgeType::Dereference, AttrNone);
   }
 
   void visitExtractValueInst(ExtractValueInst &Inst) {
     auto *Ptr = Inst.getAggregateOperand();
-    Output.push_back(Edge(&Inst, Ptr, EdgeType::Reference, AttrNone));
+    addEdge(&Inst, Ptr, EdgeType::Reference, AttrNone);
   }
 
   void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
     auto *From1 = Inst.getOperand(0);
     auto *From2 = Inst.getOperand(1);
-    Output.push_back(Edge(&Inst, From1, EdgeType::Assign, AttrNone));
-    Output.push_back(Edge(&Inst, From2, EdgeType::Assign, AttrNone));
+    addEdge(From1, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(From2, &Inst, EdgeType::Assign, AttrNone);
   }
 
   void visitConstantExpr(ConstantExpr *CE) {
     switch (CE->getOpcode()) {
     default:
       llvm_unreachable("Unknown instruction type encountered!");
 // Build the switch statement using the Instruction.def file.
 #define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
   case Instruction::OPCODE:                                                    \
     visit##OPCODE(*(CLASS *)CE);                                               \
     break;
 #include "llvm/IR/Instruction.def"
     }
   }
 };
 
-/// For a given instruction, we need to know which Value* to get the
-/// users of in order to build our graph. In some cases (i.e. add),
-/// we simply need the Instruction*. In other cases (i.e. store),
-/// finding the users of the Instruction* is useless; we need to find
-/// the users of the first operand. This handles determining which
-/// value to follow for us.
-///
-/// Note: we *need* to keep this in sync with GetEdgesVisitor. Add
-/// something to GetEdgesVisitor, add it here -- remove something from
-/// GetEdgesVisitor, remove it here.
-class GetTargetValueVisitor
-    : public InstVisitor<GetTargetValueVisitor, Value *> {
-public:
-  Value *visitInstruction(Instruction &Inst) { return &Inst; }
-
-  Value *visitStoreInst(StoreInst &Inst) { return Inst.getPointerOperand(); }
-
-  Value *visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
-    return Inst.getPointerOperand();
-  }
-
-  Value *visitAtomicRMWInst(AtomicRMWInst &Inst) {
-    return Inst.getPointerOperand();
-  }
-
-  Value *visitInsertElementInst(InsertElementInst &Inst) {
-    return Inst.getOperand(0);
-  }
-
-  Value *visitInsertValueInst(InsertValueInst &Inst) {
-    return Inst.getAggregateOperand();
-  }
-};
-
-/// The Program Expression Graph (PEG) of CFL analysis
-class CFLGraph {
-  typedef Value *Node;
-
-  struct Edge {
-    StratifiedAttrs Attr;
-    EdgeType Type;
-    Node Other;
-  };
-
-  typedef std::vector<Edge> EdgeList;
-  typedef DenseMap<Node, EdgeList> NodeMap;
-  NodeMap NodeImpls;
-
-  // Gets the inverse of a given EdgeType.
-  static EdgeType flipWeight(EdgeType Initial) {
-    switch (Initial) {
-    case EdgeType::Assign:
-      return EdgeType::Assign;
-    case EdgeType::Dereference:
-      return EdgeType::Reference;
-    case EdgeType::Reference:
-      return EdgeType::Dereference;
-    }
-    llvm_unreachable("Incomplete coverage of EdgeType enum");
-  }
-
-  const EdgeList *getNode(Node N) const {
-    auto Itr = NodeImpls.find(N);
-    if (Itr == NodeImpls.end())
-      return nullptr;
-    return &Itr->second;
-  }
-  EdgeList &getOrCreateNode(Node N) { return NodeImpls[N]; }
-
-  static Node nodeDeref(const NodeMap::value_type &P) { return P.first; }
-  typedef std::pointer_to_unary_function<const NodeMap::value_type &, Node>
-      NodeDerefFun;
-
-public:
-  typedef EdgeList::const_iterator const_edge_iterator;
-  typedef mapped_iterator<NodeMap::const_iterator, NodeDerefFun>
-      const_node_iterator;
-
-  void addNode(Node N) { getOrCreateNode(N); }
-
-  void addEdge(Node From, Node To, EdgeType Type,
-               StratifiedAttrs Attr = StratifiedAttrs()) {
-
-    // We can't getOrCreateNode() twice in a row here since the second call may
-    // invalidate the reference returned from the first call
-    getOrCreateNode(From);
-    auto &ToEdges = getOrCreateNode(To);
-    auto &FromEdges = getOrCreateNode(From);
-
-    FromEdges.push_back(Edge{Attr, Type, To});
-    ToEdges.push_back(Edge{Attr, flipWeight(Type), From});
-  }
-
-  iterator_range<const_edge_iterator> edgesFor(Node N) const {
-    auto Edges = getNode(N);
-    assert(Edges != nullptr);
-    return make_range(Edges->begin(), Edges->end());
-  }
-
-  iterator_range<const_node_iterator> nodes() const {
-    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(); }
-};
-
 class CFLGraphBuilder {
   // Input of the builder
   CFLAAResult &Analysis;
   const TargetLibraryInfo &TLI;
 
   // Output of the builder
   CFLGraph Graph;
   SmallVector<Value *, 4> ReturnedValues;
 
   // Auxiliary structures used by the builder
+  SmallPtrSet<Value *, 8> ExternalValues;
+  SmallPtrSet<Value *, 8> EscapedValues;
 
   // 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);
     return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
            !IsNonInvokeTerminator;
   }
 
-  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;
-  }
-
-  // Gets edges of the given Instruction*, writing them to the SmallVector*.
-  void argsToEdges(Instruction *Inst, SmallVectorImpl<Edge> &Output) {
-    assert(hasUsefulEdges(Inst) &&
-           "Expected instructions to have 'useful' edges");
-    GetEdgesVisitor v(Analysis, Output, TLI);
-    v.visit(Inst);
-  }
-
-  // Gets edges of the given ConstantExpr*, writing them to the SmallVector*.
-  void argsToEdges(ConstantExpr *CE, SmallVectorImpl<Edge> &Output) {
-    assert(hasUsefulEdges(CE) &&
-           "Expected constant expr to have 'useful' edges");
-    GetEdgesVisitor v(Analysis, Output, TLI);
-    v.visitConstantExpr(CE);
-  }
-
-  // Gets the edges of a ConstantExpr as if it was an Instruction. This function
-  // also acts on any nested ConstantExprs, adding the edges of those to the
-  // given SmallVector as well.
-  void constexprToEdges(ConstantExpr &CExprToCollapse,
-                        SmallVectorImpl<Edge> &Results) {
-    SmallVector<ConstantExpr *, 4> Worklist;
-    Worklist.push_back(&CExprToCollapse);
-
-    SmallVector<Edge, 8> ConstexprEdges;
-    SmallPtrSet<ConstantExpr *, 4> Visited;
-    while (!Worklist.empty()) {
-      auto *CExpr = Worklist.pop_back_val();
-
-      if (!hasUsefulEdges(CExpr))
-        continue;
-
-      ConstexprEdges.clear();
-      argsToEdges(CExpr, ConstexprEdges);
-      for (auto &Edge : ConstexprEdges) {
-        if (auto *Nested = dyn_cast<ConstantExpr>(Edge.From))
-          if (Visited.insert(Nested).second)
-            Worklist.push_back(Nested);
-
-        if (auto *Nested = dyn_cast<ConstantExpr>(Edge.To))
-          if (Visited.insert(Nested).second)
-            Worklist.push_back(Nested);
-      }
-
-      Results.append(ConstexprEdges.begin(), ConstexprEdges.end());
-    }
-  }
-
-  // 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())
-        addInstructionToGraph(Inst);
+  void addArgumentToGraph(Argument &Arg) {
+    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 (isa<ReturnInst>(&Inst))
       ReturnedValues.push_back(&Inst);
 
     if (!hasUsefulEdges(&Inst))
       return;
 
-    SmallVector<Edge, 8> Edges;
-    argsToEdges(&Inst, Edges);
-
-    // In the case of an unused alloca (or similar), edges may be empty. Note
-    // that it exists so we can potentially answer NoAlias.
-    if (Edges.empty()) {
-      auto MaybeVal = getTargetValue(&Inst);
-      assert(MaybeVal.hasValue());
-      auto *Target = *MaybeVal;
-      Graph.addNode(Target);
-      return;
-    }
+    GetEdgesVisitor(Analysis, TLI, Graph, ExternalValues, EscapedValues)
+        .visit(Inst);
 
-    auto addEdgeToGraph = [this](const Edge &E) {
-      Graph.addEdge(E.From, E.To, E.Weight, E.AdditionalAttrs);
-    };
-
-    SmallVector<ConstantExpr *, 4> ConstantExprs;
-    for (const Edge &E : Edges) {
-      addEdgeToGraph(E);
-      if (auto *Constexpr = dyn_cast<ConstantExpr>(E.To))
-        ConstantExprs.push_back(Constexpr);
-      if (auto *Constexpr = dyn_cast<ConstantExpr>(E.From))
-        ConstantExprs.push_back(Constexpr);
-    }
+  // 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())
+        addInstructionToGraph(Inst);
 
-    for (ConstantExpr *CE : ConstantExprs) {
-      Edges.clear();
-      constexprToEdges(*CE, Edges);
-      std::for_each(Edges.begin(), Edges.end(), addEdgeToGraph);
-    }
+    for (auto &Arg : Fn.args())
+      addArgumentToGraph(Arg);
   }
 
 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 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
 /// as globals or arguments
 static bool isGlobalOrArgAttr(StratifiedAttrs Attr);
if (auto *Inst = dyn_cast<Instruction>(Val)) {
     return Bb->getParent();
   }
 
   if (auto *Arg = dyn_cast<Argument>(Val))
     return Arg->getParent();
   return None;
 }
 
-template <typename Inst>
-static bool getPossibleTargets(Inst *Call,
+static bool getPossibleTargets(CallSite CS,
                                SmallVectorImpl<Function *> &Output) {
-  if (auto *Fn = Call->getCalledFunction()) {
+  if (auto *Fn = CS.getCalledFunction()) {
     Output.push_back(Fn);
     return true;
   }
 
   // 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 Optional<Value *> getTargetValue(Instruction *Inst) {
-  GetTargetValueVisitor V;
-  return V.visit(Inst);
-}
-
 static bool isGlobalOrArgAttr(StratifiedAttrs Attr) {
   return Attr.reset(AttrEscapedIndex).reset(AttrUnknownIndex).any();
 }
 
 static bool isUnknownAttr(StratifiedAttrs Attr) {
   return Attr.test(AttrUnknownIndex);
 }
 

 
 // 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;
-  SmallPtrSet<Value *, 16> Globals;
   for (auto Node : Graph.nodes())
     Worklist.push_back(Node);
 
   while (!Worklist.empty()) {
     auto *CurValue = Worklist.pop_back_val();
     SetBuilder.add(CurValue);
     if (canSkipAddingToSets(CurValue))
       continue;
 
-    if (isa<GlobalValue>(CurValue))
-      Globals.insert(CurValue);
-
     for (const auto &Edge : Graph.edgesFor(CurValue)) {
       auto Label = Edge.Type;
       auto *OtherValue = Edge.Other;
 
       if (canSkipAddingToSets(OtherValue))
         continue;
-      if (isa<GlobalValue>(OtherValue))
-        Globals.insert(OtherValue);
 
       bool Added;
       switch (directionOfEdgeType(Label)) {
       case Level::Above:
         Added = SetBuilder.addAbove(CurValue, OtherValue);
         break;
       case Level::Below:
         Added = SetBuilder.addBelow(CurValue, OtherValue);
         break;
       case Level::Same:
         Added = SetBuilder.addWith(CurValue, OtherValue);
         break;
       }
 
       auto Aliasing = Edge.Attr;
       SetBuilder.noteAttributes(CurValue, Aliasing);
       SetBuilder.noteAttributes(OtherValue, Aliasing);
 
       if (Added)
         Worklist.push_back(OtherValue);
     }
   }
 
   // Special handling for globals and arguments
-  auto ProcessGlobalOrArgValue = [&SetBuilder](Value &Val) {
-    SetBuilder.add(&Val);
-    auto Attr = valueToAttr(&Val);
+  for (auto *External : GraphBuilder.getExternalValues()) {
+    SetBuilder.add(External);
+    auto Attr = valueToAttr(External);
     if (Attr.hasValue()) {
-      SetBuilder.noteAttributes(&Val, *Attr);
-      // TODO: do we need to filter out non-pointer values here?
-      SetBuilder.addAttributesBelow(&Val, AttrUnknown);
-    }
-  };
+      SetBuilder.noteAttributes(External, *Attr);
+      SetBuilder.addAttributesBelow(External, AttrUnknown);
+    }
 
-  for (auto &Arg : Fn->args())
-    ProcessGlobalOrArgValue(Arg);
-  for (auto *Global : Globals)
-    ProcessGlobalOrArgValue(*Global);
+  for (auto *Escape : GraphBuilder.getEscapedValues()) {
+    SetBuilder.add(Escape);
+    SetBuilder.noteAttributes(Escape, AttrEscaped);
+    SetBuilder.addAttributesBelow(Escape, AttrUnknown);
+  }
 
   return FunctionInfo(SetBuilder.build(), GraphBuilder.takeReturnValues());
 }
 
 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");
 
   // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
   // may get evaluated after operator[], potentially triggering a DenseMap
   // resize and invalidating the reference returned by operator[]
   auto FunInfo = buildSetsFrom(Fn);
   Cache[Fn] = std::move(FunInfo);
 

lib/Analysis/StratifiedSets.h

StratifiedIndex addLinks() {
     auto Link = Links.size();
     Links.push_back(BuilderLink(Link));
     return Link;
   }
 
   bool inbounds(StratifiedIndex N) const { return N < Links.size(); }
 };
 }
-#endif // LLVM_ADT_STRATIFIEDSETS_H
+#endif // LLVM_ADT_STRATIFIEDSETS_H
 No newline at end of file

test/Analysis/CFLAliasAnalysis/attr-escape.ll

 @ext_global = external global i32*
 define void @test_global_param(i32** %x) {
   %a = alloca i32, align 4
   %aint = ptrtoint i32* %a to i64
   %xload = load i32*, i32** %x
   %gload = load i32*, i32** @ext_global
   ret void
 }
+
+declare void @external_func(i32**)
+; CHECK-LABEL: Function: test_external_call
+; CHECK: NoAlias: i32* %b, i32* %x
+; CHECK: NoAlias: i32* %b, i32** %a
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: MayAlias: i32* %c, i32** %a
+; CHECK: NoAlias: i32* %b, i32* %c
+define void @test_external_call(i32* %x) {
+  %a = alloca i32*, align 8
+  %b = alloca i32, align 4
+  call void @external_func(i32** %a)
+  %c = load i32*, i32** %a
+  ret void
+}
+
+declare void @external_func_readonly(i32**) readonly
+; CHECK-LABEL: Function: test_external_call_func_readonly
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: NoAlias: i32* %c, i32** %a
+define void @test_external_call_func_readonly(i32* %x) {
+  %a = alloca i32*, align 8
+  %b = alloca i32, align 4
+  store i32* %x, i32** %a, align 4
+  call void @external_func_readonly(i32** %a)
+  %c = load i32*, i32** %a
+  ret void
+}
+
+; CHECK-LABEL: Function: test_external_call_callsite_readonly
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: NoAlias: i32* %c, i32** %a
+define void @test_external_call_callsite_readonly(i32* %x) {
+  %a = alloca i32*, align 8
+  %b = alloca i32, align 4
+  store i32* %x, i32** %a, align 4
+  call void @external_func(i32** %a) readonly
+  %c = load i32*, i32** %a
+  ret void
+}
+
+declare i32* @external_func_normal_return(i32*)
+; CHECK-LABEL: Function: test_external_call_normal_return
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: MayAlias: i32* %a, i32* %c
+define void @test_external_call_normal_return(i32* %x) {
+  %a = alloca i32, align 8
+  %b = alloca i32, align 4
+  %c = call i32* @external_func_normal_return(i32* %a)
+  ret void
+}
+
+declare noalias i32* @external_func_noalias_return(i32*)
+; CHECK-LABEL: Function: test_external_call_noalias_return
+; CHECK: NoAlias: i32* %c, i32* %x
+; CHECK: NoAlias: i32* %a, i32* %c
+define void @test_external_call_noalias_return(i32* %x) {
+  %a = alloca i32, align 8
+  %b = alloca i32, align 4
+  %c = call i32* @external_func_noalias_return(i32* %a)
+  ret void
+}

test/Analysis/CFLAliasAnalysis/opaque-call-alias.ll

 ; We previously had a case where we would put results from a no-args call in
 ; its own stratified set. This would make cases like the one in @test say that
 ; nothing (except %Escapes and %Arg) can alias
 
-; RUN: opt < %s -disable-basicaa -cfl-aa -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
 
 ; CHECK:     Function: test
-; CHECK:     MayAlias: i8* %Arg, i8* %Escapes
+; CHECK:     NoAlias: i8* %Arg, i8* %Escapes
 ; CHECK:     MayAlias: i8* %Arg, i8* %Retrieved
 ; CHECK:     MayAlias: i8* %Escapes, i8* %Retrieved
 define void @test(i8* %Arg) {
   %Noalias = alloca i8
   %Escapes = alloca i8
   call void @set_thepointer(i8* %Escapes)
   %Retrieved = call i8* @get_thepointer()
   ret void
 }
 
 declare void @set_thepointer(i8* %P)
 declare i8* @get_thepointer()

test/Analysis/CFLAliasAnalysis/va.ll

-; RUN: opt < %s -disable-basicaa -cfl-aa -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
 
 ; CHECK-LABEL: Function: test1
-; CHECK: 0 no alias responses
+; CHECK: MayAlias: i32* %X, i32* %tmp
+; CHECK: MayAlias: i32* %tmp, i8** %ap
+; CHECK: NoAlias: i8** %ap, i8** %aq
+; CHECK: MayAlias: i32* %tmp, i8** %aq
 
-define i32 @test1(i32 %X, ...) {
+define i32* @test1(i32* %X, ...) {
   ; Initialize variable argument processing
   %ap = alloca i8*
   %ap2 = bitcast i8** %ap to i8*
   call void @llvm.va_start(i8* %ap2)
 
-  ; Read a single integer argument
-  %tmp = va_arg i8** %ap, i32
+  ; Read a single pointer argument
+  %tmp = va_arg i8** %ap, i32*
 
   ; Demonstrate usage of llvm.va_copy and llvm.va_end
   %aq = alloca i8*
   %aq2 = bitcast i8** %aq to i8*
   call void @llvm.va_copy(i8* %aq2, i8* %ap2)
   call void @llvm.va_end(i8* %aq2)
 
   ; Stop processing of arguments.
   call void @llvm.va_end(i8* %ap2)
-  ret i32 %tmp
+  ret i32* %tmp
 }
 
 declare void @llvm.va_start(i8*)
 declare void @llvm.va_copy(i8*, i8*)
 declare void @llvm.va_end(i8*)