Index: lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAndersAliasAnalysis.cpp +++ 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" Index: lib/Analysis/CFLGraph.h =================================================================== --- /dev/null +++ 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 EdgeList; + + struct NodeInfo { + EdgeList Edges; + StratifiedAttrs Attr; + }; + + typedef DenseMap 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 + NodeDerefFun; + +public: + typedef EdgeList::const_iterator const_edge_iterator; + typedef mapped_iterator + 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 edgesFor(Node N) const { + auto *Info = getNode(N); + assert(Info != nullptr); + auto &Edges = Info->Edges; + return make_range(Edges.begin(), Edges.end()); + } + + iterator_range nodes() const { + return make_range( + 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 Index: lib/Analysis/CFLSteensAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLSteensAliasAnalysis.cpp +++ 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 using namespace llvm; +using namespace llvm::cflaa; #define DEBUG_TYPE "cfl-steens-aa" @@ -163,126 +164,6 @@ /// 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 EdgeList; - - struct NodeInfo { - EdgeList Edges; - StratifiedAttrs Attr; - }; - - typedef DenseMap 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 - NodeDerefFun; - -public: - typedef EdgeList::const_iterator const_edge_iterator; - typedef mapped_iterator - 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 edgesFor(Node N) const { - auto *Info = getNode(N); - assert(Info != nullptr); - auto &Edges = Info->Edges; - return make_range(Edges.begin(), Edges.end()); - } - - iterator_range nodes() const { - return make_range( - 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; Index: lib/Analysis/StratifiedSets.h =================================================================== --- lib/Analysis/StratifiedSets.h +++ lib/Analysis/StratifiedSets.h @@ -22,6 +22,7 @@ #include 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 @@ bool inbounds(StratifiedIndex N) const { return N < Links.size(); } }; } +} #endif // LLVM_ADT_STRATIFIEDSETS_H