[CFLAA] Remove non-pointer values from CFLGraph

[grievejia]

Summary

This patch introduces no functionality changes.

The goal is to only let CFLAA track pointer values. Non-pointer values do not need to be added to CFLGraph, and any alias queries involving at least one non-pointer value can be answered with "NoAlias" (basicaa does this so I guess with the introduction of AttrEscape it would be fine for CFLAA to do it as well).

One more change has to be done to achieve this goal, though. For instructions like ptrtoint, the operand is a pointer yet the result is not. Ideally we would want to add the operand to CFLGraph and tag it as AttrEscape, and just ignore the result. However, without this patch we cannot do that since StratifiedAttrs are attached to CFLGrpah's edges, not nodes. All we can do there was to add an edge from the operand to the result with AttrEscape attached to the edge, but then we have to add a non-pointer value (the result) as a node to the graph. This patch fix this issue by moving StratifiedAttrs from edges to nodes.

[• dberlin]

It's not clear to me why you don't, long term, end up with attributes both
for edges and nodes.

For example, for edges, to support field-sensitive analysis, you will
either need the offset or something as an edge attribute, so you can
differentiate what edge to follow for a given offset.
(unless y'all know another way)

[grievejia]

In D21387#458889, @dberlin wrote:

It's not clear to me why you don't, long term, end up with attributes both
for edges and nodes.

For example, for edges, to support field-sensitive analysis, you will
either need the offset or something as an edge attribute, so you can
differentiate what edge to follow for a given offset.
(unless y'all know another way)

Edge attributes could be useful. I totally agree.

However, the semanitics of StratifiedAttr, in it current form, describes something about nodes, not edges. When CFLGraph gets translated to StratifiedSets, those "edge" attributes on CFLGraph will become "node" attributes in StratifiedSets anyway. So IMO it makes more sense to move StratifiedAttr from edges to nodes in CFLGraph.

You are right that for field sensitivity we may need to attach certain information to edges in the future. But those information will look very different from the StratifiedAttr we have right now.

[• dberlin]

SGTM then.
I'll let george continue taking a look.

[george.burgess.iv]

LGTM -- thanks for the patch!

llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp

enum class EdgeType {
   Reference
 };
 
 /// 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;
+
+  struct NodeInfo {
+    EdgeList Edges;
+    StratifiedAttrs Attr;
+  };
+
+  typedef DenseMap<Node, NodeInfo> 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 {
+  const NodeInfo *getNode(Node N) const {
     auto Itr = NodeImpls.find(N);
     if (Itr == NodeImpls.end())
       return nullptr;
     return &Itr->second;
   }
-  EdgeList *getNode(Node N) {
+  NodeInfo *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;
 
 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;
+    return NodeImpls.insert(std::make_pair(N, NodeInfo{EdgeList(), AttrNone}))
+        .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);
+  void addAttr(Node N, StratifiedAttrs Attr) {
+    auto *Info = getNode(N);
+    assert(Info != nullptr);
+    Info->Attr |= Attr;
+  }
 
-    FromEdges->push_back(Edge{Attr, Type, To});
-    ToEdges->push_back(Edge{Attr, flipWeight(Type), From});
+  void addEdge(Node From, Node To, EdgeType Type) {
+    auto *FromInfo = getNode(From);
+    assert(FromInfo != nullptr);
+    auto *ToInfo = getNode(To);
+    assert(ToInfo != nullptr);
+
+    FromInfo->Edges.push_back(Edge{Type, To});
+    ToInfo->Edges.push_back(Edge{flipWeight(Type), From});
+  }
+
+  StratifiedAttrs attrFor(Node N) const {
+    auto *Info = getNode(N);
+    assert(Info != nullptr);
+    return Info->Attr;
   }
 
   iterator_range<const_edge_iterator> edgesFor(Node N) const {
-    auto Edges = getNode(N);
-    assert(Edges != nullptr);
-    return make_range(Edges->begin(), Edges->end());
+    auto *Info = getNode(N);
+    assert(Info != nullptr);
+    auto &Edges = Info->Edges;
+    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)));
   }
 
void addNode(Value *Val) {
 
     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) {
+  void addNodeWithAttr(Value *Val, StratifiedAttrs Attr) {
+    addNode(Val);
+    Graph.addAttr(Val, Attr);
+  }
+
+  void addEdge(Value *From, Value *To, EdgeType Type) {
+    if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
+      return;
     addNode(From);
     if (To != From)
       addNode(To);
-    Graph.addEdge(From, To, Type, Attr);
+    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) {
   }
 
   void visitInstruction(Instruction &) {
     llvm_unreachable("Unsupported instruction encountered");
   }
 
   void visitPtrToIntInst(PtrToIntInst &Inst) {
     auto *Ptr = Inst.getOperand(0);
-    addEdge(Ptr, &Inst, EdgeType::Assign, AttrEscaped);
+    addNodeWithAttr(Ptr, AttrEscaped);
   }
 
   void visitIntToPtrInst(IntToPtrInst &Inst) {
     auto *Ptr = &Inst;
-    addEdge(Ptr, Ptr, EdgeType::Assign, AttrUnknown);
+    addNodeWithAttr(Ptr, AttrUnknown);
   }
 
   void visitCastInst(CastInst &Inst) {
     auto *Src = Inst.getOperand(0);
-    addEdge(Src, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(Src, &Inst, EdgeType::Assign);
   }
 
   void visitBinaryOperator(BinaryOperator &Inst) {
     auto *Op1 = Inst.getOperand(0);
     auto *Op2 = Inst.getOperand(1);
-    addEdge(Op1, &Inst, EdgeType::Assign, AttrNone);
-    addEdge(Op2, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(Op1, &Inst, EdgeType::Assign);
+    addEdge(Op2, &Inst, EdgeType::Assign);
   }
 
   void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
     auto *Ptr = Inst.getPointerOperand();
     auto *Val = Inst.getNewValOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference, AttrNone);
+    addEdge(Ptr, Val, EdgeType::Dereference);
   }
 
   void visitAtomicRMWInst(AtomicRMWInst &Inst) {
     auto *Ptr = Inst.getPointerOperand();
     auto *Val = Inst.getValOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference, AttrNone);
+    addEdge(Ptr, Val, EdgeType::Dereference);
   }
 
   void visitPHINode(PHINode &Inst) {
     for (Value *Val : Inst.incoming_values())
-      addEdge(Val, &Inst, EdgeType::Assign, AttrNone);
+      addEdge(Val, &Inst, EdgeType::Assign);
   }
 
   void visitGetElementPtrInst(GetElementPtrInst &Inst) {
     auto *Op = Inst.getPointerOperand();
-    addEdge(Op, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(Op, &Inst, EdgeType::Assign);
   }
 
   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();
     auto *FalseVal = Inst.getFalseValue();
-    addEdge(TrueVal, &Inst, EdgeType::Assign, AttrNone);
-    addEdge(FalseVal, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(TrueVal, &Inst, EdgeType::Assign);
+    addEdge(FalseVal, &Inst, EdgeType::Assign);
   }
 
   void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); }
 
   void visitLoadInst(LoadInst &Inst) {
     auto *Ptr = Inst.getPointerOperand();
     auto *Val = &Inst;
-    addEdge(Val, Ptr, EdgeType::Reference, AttrNone);
+    addEdge(Val, Ptr, EdgeType::Reference);
   }
 
   void visitStoreInst(StoreInst &Inst) {
     auto *Ptr = Inst.getPointerOperand();
     auto *Val = Inst.getValueOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference, AttrNone);
+    addEdge(Ptr, Val, EdgeType::Dereference);
   }
 
   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;
-    addEdge(Val, Val, EdgeType::Assign, AttrUnknown);
+    addNodeWithAttr(&Inst, AttrUnknown);
   }
 
   static bool isFunctionExternal(Function *Fn) {
     return Fn->isDeclaration() || !Fn->hasLocalLinkage();
   }
 
   /// Gets whether the sets at Index1 above, below, or equal to the sets at
   /// Index2. Returns None if they are not in the same set chain.
struct Edge {
 
     // 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;
+    // invisible to the analysis
+    StratifiedAttrs FromAttrs, ToAttrs;
   };
 
   bool
   tryInterproceduralAnalysis(const SmallVectorImpl<Function *> &Fns,
                              Value *FuncValue,
                              const iterator_range<User::op_iterator> &Args) {
     const unsigned ExpectedMaxArgs = 8;
     const unsigned MaxSupportedArgs = 50;
for (auto *Fn : Fns) {
       }
 
       // Adding an edge from argument -> return value for each parameter that
       // may alias the return value
       for (unsigned I = 0, E = Parameters.size(); I != E; ++I) {
         auto &ParamInfo = Parameters[I];
         auto &ArgVal = Arguments[I];
         bool AddEdge = false;
-        StratifiedAttrs Externals;
+        StratifiedAttrs RetAttrs, ParamAttrs;
         for (unsigned X = 0, XE = RetVals.size(); X != XE; ++X) {
           auto MaybeInfo = Sets.find(RetVals[X]);
           if (!MaybeInfo.hasValue())
             return false;
 
           auto &RetInfo = *MaybeInfo;
-          auto RetAttrs = Sets.getLink(RetInfo.Index).Attrs;
-          auto ParamAttrs = Sets.getLink(ParamInfo.Index).Attrs;
+          RetAttrs |= Sets.getLink(RetInfo.Index).Attrs;
+          ParamAttrs |= Sets.getLink(ParamInfo.Index).Attrs;
           auto MaybeRelation =
               getIndexRelation(Sets, ParamInfo.Index, RetInfo.Index);
-          if (MaybeRelation.hasValue()) {
+          if (MaybeRelation.hasValue())
             AddEdge = true;
-            Externals |= RetAttrs | ParamAttrs;
-          }
         }
         if (AddEdge)
           Output.push_back(
-              Edge{FuncValue, ArgVal, EdgeType::Assign, Externals});
+              Edge{FuncValue, ArgVal, EdgeType::Assign, RetAttrs, ParamAttrs});
       }
 
       if (Parameters.size() != Arguments.size())
         return false;
 
       /// Adding edges between arguments for arguments that may end up aliasing
       /// each other. This is necessary for functions such as
       /// void foo(int** a, int** b) { *a = *b; }
for (auto *Fn : Fns) {
           auto &SubVal = Arguments[X];
           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, MainAttrs, SubAttrs});
         }
       }
     }
 
     // Commit all edges in Output to CFLGraph
-    for (const auto &Edge : Output)
-      addEdge(Edge.From, Edge.To, Edge.Weight, Edge.AdditionalAttrs);
+    for (const auto &Edge : Output) {
+      addEdge(Edge.From, Edge.To, Edge.Weight);
+      Graph.addAttr(Edge.From, Edge.FromAttrs);
+      Graph.addAttr(Edge.To, Edge.ToAttrs);
+    }
 
     return true;
   }
 
   void visitCallSite(CallSite CS) {
     auto Inst = CS.getInstruction();
 
     // Make sure all arguments and return value are added to the graph first
if (getPossibleTargets(CS, Targets))
         return;
 
     // Because the function is opaque, we need to note that anything
     // could have happened to the arguments (unless the function is marked
     // readonly or readnone), and that the result could alias just about
     // anything, too (unless the result is marked noalias).
     if (!CS.onlyReadsMemory())
       for (Value *V : CS.args()) {
+        if (V->getType()->isPointerTy())
           Escapes.insert(V);
       }
 
     if (!Inst->getType()->isVoidTy()) {
       auto *Fn = CS.getCalledFunction();
       if (Fn == nullptr || !Fn->doesNotAlias(0))
-        addEdge(Inst, Inst, EdgeType::Assign, AttrUnknown);
+        Graph.addAttr(Inst, AttrUnknown);
     }
   }
 
   /// Because vectors/aggregates are immutable and unaddressable, there's
   /// nothing we can do to coax a value out of them, other than calling
   /// 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;
-    addEdge(Val, Ptr, EdgeType::Reference, AttrNone);
+    addEdge(Val, Ptr, EdgeType::Reference);
   }
 
   void visitInsertElementInst(InsertElementInst &Inst) {
     auto *Vec = Inst.getOperand(0);
     auto *Val = Inst.getOperand(1);
-    addEdge(Vec, &Inst, EdgeType::Assign, AttrNone);
-    addEdge(&Inst, Val, EdgeType::Dereference, AttrNone);
+    addEdge(Vec, &Inst, EdgeType::Assign);
+    addEdge(&Inst, Val, EdgeType::Dereference);
   }
 
   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
-    addEdge(&Inst, &Inst, EdgeType::Assign, AttrUnknown);
+    addNodeWithAttr(&Inst, AttrUnknown);
   }
 
   void visitInsertValueInst(InsertValueInst &Inst) {
     auto *Agg = Inst.getOperand(0);
     auto *Val = Inst.getOperand(1);
-    addEdge(Agg, &Inst, EdgeType::Assign, AttrNone);
-    addEdge(&Inst, Val, EdgeType::Dereference, AttrNone);
+    addEdge(Agg, &Inst, EdgeType::Assign);
+    addEdge(&Inst, Val, EdgeType::Dereference);
   }
 
   void visitExtractValueInst(ExtractValueInst &Inst) {
     auto *Ptr = Inst.getAggregateOperand();
-    addEdge(&Inst, Ptr, EdgeType::Reference, AttrNone);
+    addEdge(&Inst, Ptr, EdgeType::Reference);
   }
 
   void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
     auto *From1 = Inst.getOperand(0);
     auto *From2 = Inst.getOperand(1);
-    addEdge(From1, &Inst, EdgeType::Assign, AttrNone);
-    addEdge(From2, &Inst, EdgeType::Assign, AttrNone);
+    addEdge(From1, &Inst, EdgeType::Assign);
+    addEdge(From2, &Inst, EdgeType::Assign);
   }
 
   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)                                        \
class CFLGraphBuilder {
   static bool hasUsefulEdges(Instruction *Inst) {
     bool IsNonInvokeTerminator =
         isa<TerminatorInst>(Inst) && !isa<InvokeInst>(Inst);
     return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
            !IsNonInvokeTerminator;
   }
 
   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) {
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;
 
+    auto Attr = Graph.attrFor(CurValue);
+    SetBuilder.noteAttributes(CurValue, Attr);
+
     for (const auto &Edge : Graph.edgesFor(CurValue)) {
       auto Label = Edge.Type;
       auto *OtherValue = Edge.Other;
 
       if (canSkipAddingToSets(OtherValue))
         continue;
 
       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
   for (auto *External : GraphBuilder.getExternalValues()) {
     SetBuilder.add(External);
CFLAAResult::ensureCached(Function *Fn) {
   return Iter->second;
 }
 
 AliasResult CFLAAResult::query(const MemoryLocation &LocA,
                                const MemoryLocation &LocB) {
   auto *ValA = const_cast<Value *>(LocA.Ptr);
   auto *ValB = const_cast<Value *>(LocB.Ptr);
 
+  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
+    return NoAlias;
+
   Function *Fn = nullptr;
   auto MaybeFnA = parentFunctionOfValue(ValA);
   auto MaybeFnB = parentFunctionOfValue(ValB);
   if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) {
     // The only times this is known to happen are when globals + InlineAsm are
     // involved
     DEBUG(dbgs() << "CFLAA: could not extract parent function information.\n");
     return MayAlias;