diff options
author | George Burgess IV <george.burgess.iv@gmail.com> | 2016-07-06 00:36:12 +0000 |
---|---|---|
committer | George Burgess IV <george.burgess.iv@gmail.com> | 2016-07-06 00:36:12 +0000 |
commit | 02af278314f7b14c6c06bd7d7c86924c713be3a9 (patch) | |
tree | ca9fd296d2b58113cbbe686b44212f306f08dd22 /lib/Analysis | |
parent | a3d4e373c03df88ca9d4a03ea5ce97bfac85a02a (diff) |
[CFLAA] Split the CFL graph out from CFLSteens. NFC.
Patch by Jia Chen.
Differential Revision: http://reviews.llvm.org/D21963
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@274591 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis')
-rw-r--r-- | lib/Analysis/CFLAndersAliasAnalysis.cpp | 2 | ||||
-rw-r--r-- | lib/Analysis/CFLGraph.h | 151 | ||||
-rw-r--r-- | lib/Analysis/CFLSteensAliasAnalysis.cpp | 124 | ||||
-rw-r--r-- | lib/Analysis/StratifiedSets.h | 2 |
4 files changed, 157 insertions, 122 deletions
diff --git a/lib/Analysis/CFLAndersAliasAnalysis.cpp b/lib/Analysis/CFLAndersAliasAnalysis.cpp index 8db2051d673..b7c4c318587 100644 --- a/lib/Analysis/CFLAndersAliasAnalysis.cpp +++ b/lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -25,9 +25,11 @@ // 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" diff --git a/lib/Analysis/CFLGraph.h b/lib/Analysis/CFLGraph.h new file mode 100644 index 00000000000..a37951346a8 --- /dev/null +++ b/lib/Analysis/CFLGraph.h @@ -0,0 +1,151 @@ +//======- 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 diff --git a/lib/Analysis/CFLSteensAliasAnalysis.cpp b/lib/Analysis/CFLSteensAliasAnalysis.cpp index 7da2cf22f40..1f91468f546 100644 --- a/lib/Analysis/CFLSteensAliasAnalysis.cpp +++ b/lib/Analysis/CFLSteensAliasAnalysis.cpp @@ -36,7 +36,7 @@ // 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" @@ -57,6 +57,7 @@ #include <tuple> using namespace llvm; +using namespace llvm::cflaa; #define DEBUG_TYPE "cfl-steens-aa" @@ -148,7 +149,6 @@ LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex; // 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; @@ -163,126 +163,6 @@ LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50; /// 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; diff --git a/lib/Analysis/StratifiedSets.h b/lib/Analysis/StratifiedSets.h index 45c317d4a82..b06027a1847 100644 --- a/lib/Analysis/StratifiedSets.h +++ b/lib/Analysis/StratifiedSets.h @@ -22,6 +22,7 @@ #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 @@ -644,4 +645,5 @@ private: bool inbounds(StratifiedIndex N) const { return N < Links.size(); } }; } +} #endif // LLVM_ADT_STRATIFIEDSETS_H |