[CFLAA] Code cleanup: group all graph-building codes into one class

[grievejia]

Summary

This patch introduce no functionality changes.

It added a new class CFLGraphBuilder which groups together all codes related to graph building. This change effectively reduce the number of arguments for functions like "buildGraphFrom()", "addInstructionToGraph()", etc.

[george.burgess.iv]

Thanks for the patch.

lib/Analysis/CFLAliasAnalysis.cpp

588

Redundant private

728

Things that look and feel like accessors (but that visibly modify the state of their object) seem sketchy to me.

849–850

Useless newline

853

I don't like that this builder is essentially partially-alive (Graph has been moved from, ReturnedValues hasn't) for the majority of this function.

Can we either:

• Have get*() return references (that we move from at the end of the function), or
• Move everything out of Builder at the top of the function, and declare it entirely dead+useless

instead?

[grievejia]

Style fixes

[george.burgess.iv]

Looks good with one more comment.

lib/Analysis/CFLAliasAnalysis.cpp

728

...Half done?

If you want to keep the std::move in this accessor, that's fine -- maybe we can just rename it to something like takeReturnValues, or anything that makes it obvious that it's going to modify the object.

[grievejia]

Rename getReturnValue() to takeReturnValue()

[george.burgess.iv]

LGTM. Thanks for the patch!

lib/Analysis/CFLAliasAnalysis.cpp

 
 /// 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 *);
 
-/// Determines whether or not we an instruction is useless to us (e.g.
-/// FenceInst)
-static bool hasUsefulEdges(Instruction *);
-
 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;
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
+
+  // 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);
+  }
+
+  // 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;
+    }
+
+    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);
+    }
+
+    for (ConstantExpr *CE : ConstantExprs) {
+      Edges.clear();
+      constexprToEdges(*CE, Edges);
+      std::for_each(Edges.begin(), Edges.end(), addEdgeToGraph);
+    }
+  }
+
+public:
+  CFLGraphBuilder(CFLAAResult &Analysis, const TargetLibraryInfo &TLI,
+                  Function &Fn)
+      : Analysis(Analysis), TLI(TLI) {
+    buildGraphFrom(Fn);
+  }
+
+  const CFLGraph &getCFLGraph() { return Graph; }
+  SmallVector<Value *, 4> getReturnValues() {
+    return std::move(ReturnedValues);
+  }
+};
 }
 
 //===----------------------------------------------------------------------===//
 // 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);
 
 /// Given a Value, potentially return which StratifiedAttr it maps to.
 static Optional<StratifiedAttr> valueToAttr(Value *Val);
 
-/// Gets edges of the given Instruction*, writing them to the SmallVector*.
-static void argsToEdges(CFLAAResult &, Instruction *, SmallVectorImpl<Edge> &,
-                        const TargetLibraryInfo &);
-
-/// Gets edges of the given ConstantExpr*, writing them to the SmallVector*.
-static void argsToEdges(CFLAAResult &, ConstantExpr *, SmallVectorImpl<Edge> &,
-                        const TargetLibraryInfo &);
-
 /// Gets the "Level" that one should travel in StratifiedSets
 /// given an EdgeType.
 static Level directionOfEdgeType(EdgeType);
 
-/// Builds the graph needed for constructing the StratifiedSets for the
-/// given function
-static void buildGraphFrom(CFLAAResult &, Function *,
-                           SmallVectorImpl<Value *> &, CFLGraph &,
-                           const TargetLibraryInfo &);
-
-/// 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.
-static void constexprToEdges(CFLAAResult &, ConstantExpr &,
-                             SmallVectorImpl<Edge> &,
-                             const TargetLibraryInfo &);
-
-/// 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.
-static void addInstructionToGraph(CFLAAResult &, Instruction &,
-                                  SmallVectorImpl<Value *> &, CFLGraph &,
-                                  const TargetLibraryInfo &);
-
 /// Determines whether it would be pointless to add the given Value to our sets.
 static bool canSkipAddingToSets(Value *Val);
 
 static Optional<Function *> parentFunctionOfValue(Value *Val) {
   if (auto *Inst = dyn_cast<Instruction>(Val)) {
     auto *Bb = Inst->getParent();
     return Bb->getParent();
   }
static bool getPossibleTargets(Inst *Call,
   return false;
 }
 
 static Optional<Value *> getTargetValue(Instruction *Inst) {
   GetTargetValueVisitor V;
   return V.visit(Inst);
 }
 
-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;
-}
-
 static bool isGlobalOrArgAttr(StratifiedAttrs Attr) {
   return Attr.reset(AttrEscapedIndex).reset(AttrUnknownIndex).any();
 }
 
 static bool isUnknownAttr(StratifiedAttrs Attr) {
   return Attr.test(AttrUnknownIndex);
 }
 

 }
 
 static StratifiedAttr argNumberToAttr(unsigned ArgNum) {
   if (ArgNum >= AttrMaxNumArgs)
     return AttrUnknown;
   return 1 << (ArgNum + AttrFirstArgIndex);
 }
 
-static void argsToEdges(CFLAAResult &Analysis, Instruction *Inst,
-                        SmallVectorImpl<Edge> &Output,
-                        const TargetLibraryInfo &TLI) {
-  assert(hasUsefulEdges(Inst) &&
-         "Expected instructions to have 'useful' edges");
-  GetEdgesVisitor v(Analysis, Output, TLI);
-  v.visit(Inst);
-}
-
-static void argsToEdges(CFLAAResult &Analysis, ConstantExpr *CE,
-                        SmallVectorImpl<Edge> &Output,
-                        const TargetLibraryInfo &TLI) {
-  assert(hasUsefulEdges(CE) && "Expected constant expr to have 'useful' edges");
-  GetEdgesVisitor v(Analysis, Output, TLI);
-  v.visitConstantExpr(CE);
-}
-
 static Level directionOfEdgeType(EdgeType Weight) {
   switch (Weight) {
   case EdgeType::Reference:
     return Level::Above;
   case EdgeType::Dereference:
     return Level::Below;
   case EdgeType::Assign:
     return Level::Same;
   }
   llvm_unreachable("Incomplete switch coverage");
 }
 
-static void constexprToEdges(CFLAAResult &Analysis,
-                             ConstantExpr &CExprToCollapse,
-                             SmallVectorImpl<Edge> &Results,
-                             const TargetLibraryInfo &TLI) {
-  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(Analysis, CExpr, ConstexprEdges, TLI);
-    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());
-  }
-}
-
-static void addInstructionToGraph(CFLAAResult &Analysis, Instruction &Inst,
-                                  SmallVectorImpl<Value *> &ReturnedValues,
-                                  CFLGraph &Graph,
-                                  const TargetLibraryInfo &TLI) {
-  // 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(Analysis, &Inst, Edges, TLI);
-
-  // 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;
-  }
-
-  auto addEdgeToGraph = [&Graph](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);
-  }
-
-  for (ConstantExpr *CE : ConstantExprs) {
-    Edges.clear();
-    constexprToEdges(Analysis, *CE, Edges, TLI);
-    std::for_each(Edges.begin(), Edges.end(), addEdgeToGraph);
-  }
-}
-
-static void buildGraphFrom(CFLAAResult &Analysis, Function *Fn,
-                           SmallVectorImpl<Value *> &ReturnedValues,
-                           CFLGraph &Graph, const TargetLibraryInfo &TLI) {
-  // (N.B. We may remove graph construction entirely, because it doesn't really
-  // buy us much.)
-  for (auto &Bb : Fn->getBasicBlockList())
-    for (auto &Inst : Bb.getInstList())
-      addInstructionToGraph(Analysis, Inst, ReturnedValues, Graph, TLI);
-}
-
 static bool canSkipAddingToSets(Value *Val) {
   // Constants can share instances, which may falsely unify multiple
   // sets, e.g. in
   // store i32* null, i32** %ptr1
   // store i32* null, i32** %ptr2
   // clearly ptr1 and ptr2 should not be unified into the same set, so
   // we should filter out the (potentially shared) instance to
   // i32* null.
   if (isa<Constant>(Val)) {
     // TODO: Because all of these things are constant, we can determine whether
     // the data is *actually* mutable at graph building time. This will probably
     // come for free/cheap with offset awareness.
     bool CanStoreMutableData = isa<GlobalValue>(Val) ||
                                isa<ConstantExpr>(Val) ||
                                isa<ConstantAggregate>(Val);
     return !CanStoreMutableData;
   }
 
   return false;
 }
 
 // Builds the graph + StratifiedSets for a function.
 CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
-  CFLGraph Graph;
-  SmallVector<Value *, 4> ReturnedValues;
-
-  buildGraphFrom(*this, Fn, ReturnedValues, Graph, TLI);
-
-  StratifiedSetsBuilder<Value *> Builder;
+  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();
-    Builder.add(CurValue);
+    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 = Builder.addAbove(CurValue, OtherValue);
+        Added = SetBuilder.addAbove(CurValue, OtherValue);
         break;
       case Level::Below:
-        Added = Builder.addBelow(CurValue, OtherValue);
+        Added = SetBuilder.addBelow(CurValue, OtherValue);
         break;
       case Level::Same:
-        Added = Builder.addWith(CurValue, OtherValue);
+        Added = SetBuilder.addWith(CurValue, OtherValue);
         break;
       }
 
       auto Aliasing = Edge.Attr;
-      Builder.noteAttributes(CurValue, Aliasing);
-      Builder.noteAttributes(OtherValue, Aliasing);
+      SetBuilder.noteAttributes(CurValue, Aliasing);
+      SetBuilder.noteAttributes(OtherValue, Aliasing);
 
       if (Added)
         Worklist.push_back(OtherValue);
     }
   }
 
   // Special handling for globals and arguments
-  auto ProcessGlobalOrArgValue = [&Builder](Value &Val) {
-    Builder.add(&Val);
+  auto ProcessGlobalOrArgValue = [&SetBuilder](Value &Val) {
+    SetBuilder.add(&Val);
     auto Attr = valueToAttr(&Val);
     if (Attr.hasValue()) {
-      Builder.noteAttributes(&Val, *Attr);
+      SetBuilder.noteAttributes(&Val, *Attr);
       // TODO: do we need to filter out non-pointer values here?
-      Builder.addAttributesBelow(&Val, AttrUnknown);
+      SetBuilder.addAttributesBelow(&Val, AttrUnknown);
     }
   };
 
   for (auto &Arg : Fn->args())
     ProcessGlobalOrArgValue(Arg);
   for (auto *Global : Globals)
     ProcessGlobalOrArgValue(*Global);
 
-  return FunctionInfo(Builder.build(), std::move(ReturnedValues));
+  return FunctionInfo(SetBuilder.build(), GraphBuilder.getReturnValues());
 }
 
 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");