[CFLAA] Moved CFLGraph out of CFLSteensAliasAnalysis

[grievejia]

Summary

CFLGraph can be useful to both CFLSteensAliasAnalysis and CFLAndersAliasAnalysis. Move it out to for future use by CFLAndersAliasAnalysis.

[grievejia]

Added the cflaa namespace

[george.burgess.iv]

LGTM * 2; thanks for the patches! Will commit the trio of patches tomorrow
(sorry that I didn't get the one in today: couldn't carve out a chunk of
time to commit + stare at bots).

llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp

 
 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
 // CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because
 // FunctionPasses are only allowed to inspect the Function that they're being
 // run on. Realistically, this likely isn't a problem until we allow
 // FunctionPasses to run concurrently.
 
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "CFLGraph.h"
 #include "llvm/Pass.h"
 
 using namespace llvm;
+using namespace llvm::cflaa;
 
 #define DEBUG_TYPE "cfl-anders-aa"
 
 CFLAndersAAResult::CFLAndersAAResult() = default;
 
 char CFLAndersAA::PassID;
 
 CFLAndersAAResult CFLAndersAA::run(Function &F, AnalysisManager<Function> &AM) {

llvm/trunk/lib/Analysis/CFLGraph.h

+//======- CFLGraph.h - Abstract stratified sets implementation. --------======//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file defines CFLGraph, an auxiliary data structure used by CFL-based
+/// alias analysis.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CFLGRAPH_H
+#define LLVM_ANALYSIS_CFLGRAPH_H
+
+#include "StratifiedSets.h"
+
+namespace llvm {
+
+class Value;
+
+namespace cflaa {
+
+/// Edges can be one of four "weights" -- each weight must have an inverse
+/// weight (Assign has Assign; Reference has Dereference).
+enum class EdgeType {
+  /// The weight assigned when assigning from or to a value. For example, in:
+  /// %b = getelementptr %a, 0
+  /// ...The relationships are %b assign %a, and %a assign %b. This used to be
+  /// two edges, but having a distinction bought us nothing.
+  Assign,
+
+  /// The edge used when we have an edge going from some handle to a Value.
+  /// Examples of this include:
+  /// %b = load %a              (%b Dereference %a)
+  /// %b = extractelement %a, 0 (%a Dereference %b)
+  Dereference,
+
+  /// 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 The Program Expression Graph (PEG) of CFL analysis
+/// CFLGraph is auxiliary data structure used by CFL-based alias analysis to
+/// describe flow-insensitive pointer-related behaviors. Given an LLVM function,
+/// the main purpose of this graph is to abstract away unrelated facts and
+/// translate the rest into a form that can be easily digested by CFL analyses.
+class CFLGraph {
+  typedef Value *Node;
+
+  struct Edge {
+    EdgeType Type;
+    Node Other;
+  };
+
+  typedef std::vector<Edge> EdgeList;
+
+  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 NodeInfo *getNode(Node N) const {
+    auto Itr = NodeImpls.find(N);
+    if (Itr == NodeImpls.end())
+      return nullptr;
+    return &Itr->second;
+  }
+  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, NodeInfo{EdgeList(), 0})).second;
+  }
+
+  void addAttr(Node N, StratifiedAttrs Attr) {
+    auto *Info = getNode(N);
+    assert(Info != nullptr);
+    Info->Attr |= Attr;
+  }
+
+  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 *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)));
+  }
+
+  bool empty() const { return NodeImpls.empty(); }
+  std::size_t size() const { return NodeImpls.size(); }
+};
+}
+}
+
+#endif

llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp

 
 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
 // CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because
 // FunctionPasses are only allowed to inspect the Function that they're being
 // run on. Realistically, this likely isn't a problem until we allow
 // FunctionPasses to run concurrently.
 
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
-#include "StratifiedSets.h"
+#include "CFLGraph.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <memory>
 #include <tuple>
 
 using namespace llvm;
+using namespace llvm::cflaa;
 
 #define DEBUG_TYPE "cfl-steens-aa"
 
 CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
     : AAResultBase(), TLI(TLI) {}
 CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
     : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
 CFLSteensAAResult::~CFLSteensAAResult() {}

 LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4;
 LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex;
 LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex;
 
 // NOTE: These aren't StratifiedAttrs because bitsets don't have a constexpr
 // ctor for some versions of MSVC that we support. We could maybe refactor,
 // but...
 using StratifiedAttr = unsigned;
-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 StratifiedAttr AttrCaller = 1 << AttrCallerIndex;
 LLVM_CONSTEXPR StratifiedAttr ExternalAttrMask =
     AttrEscaped | AttrUnknown | AttrGlobal;
 
 /// 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 };
 
-/// Edges can be one of four "weights" -- each weight must have an inverse
-/// weight (Assign has Assign; Reference has Dereference).
-enum class EdgeType {
-  /// The weight assigned when assigning from or to a value. For example, in:
-  /// %b = getelementptr %a, 0
-  /// ...The relationships are %b assign %a, and %a assign %b. This used to be
-  /// two edges, but having a distinction bought us nothing.
-  Assign,
-
-  /// The edge used when we have an edge going from some handle to a Value.
-  /// Examples of this include:
-  /// %b = load %a              (%b Dereference %a)
-  /// %b = extractelement %a, 0 (%a Dereference %b)
-  Dereference,
-
-  /// 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
-};
-
-/// The Program Expression Graph (PEG) of CFL analysis
-class CFLGraph {
-  typedef Value *Node;
-
-  struct Edge {
-    EdgeType Type;
-    Node Other;
-  };
-
-  typedef std::vector<Edge> EdgeList;
-
-  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 NodeInfo *getNode(Node N) const {
-    auto Itr = NodeImpls.find(N);
-    if (Itr == NodeImpls.end())
-      return nullptr;
-    return &Itr->second;
-  }
-  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, NodeInfo{EdgeList(), AttrNone}))
-        .second;
-  }
-
-  void addAttr(Node N, StratifiedAttrs Attr) {
-    auto *Info = getNode(N);
-    assert(Info != nullptr);
-    Info->Attr |= Attr;
-  }
-
-  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 *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)));
-  }
-
-  bool empty() const { return NodeImpls.empty(); }
-  std::size_t size() const { return NodeImpls.size(); }
-};
-
 // This is the result of instantiating InterfaceValue at a particular callsite
 struct InterprocNode {
   Value *Val;
   unsigned DerefLevel;
 };
 
 // Interprocedural assignment edges that CFLGraph may not easily model
 struct InterprocEdge {

llvm/trunk/lib/Analysis/StratifiedSets.h

 #include <bitset>
 #include <cassert>
 #include <cmath>
 #include <type_traits>
 #include <utility>
 #include <vector>
 
 namespace llvm {
+namespace cflaa {
 /// An index into Stratified Sets.
 typedef unsigned StratifiedIndex;
 /// NOTE: ^ This can't be a short -- bootstrapping clang has a case where
 /// ~1M sets exist.
 
 // \brief Container of information related to a value in a StratifiedSet.
 struct StratifiedInfo {
   StratifiedIndex Index;
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