Index: lib/Analysis/CFLAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAliasAnalysis.cpp +++ lib/Analysis/CFLAliasAnalysis.cpp @@ -512,141 +512,81 @@ } }; -/// Set building requires a weighted bidirectional graph. -template class WeightedBidirectionalGraph { -public: - typedef std::size_t Node; - +/// The Program Expression Graph (PEG) of CFL analysis +class CFLGraph { private: - const static Node StartNode = Node(0); + typedef Value *Node; struct Edge { - EdgeTypeT Weight; + StratifiedAttrs Attr; + EdgeType Type; Node Other; - - Edge(const EdgeTypeT &W, const Node &N) : Weight(W), Other(N) {} - - bool operator==(const Edge &E) const { - return Weight == E.Weight && Other == E.Other; - } - - bool operator!=(const Edge &E) const { return !operator==(E); } - }; - - struct NodeImpl { - std::vector Edges; }; - std::vector NodeImpls; - - bool inbounds(Node NodeIndex) const { return NodeIndex < NodeImpls.size(); } - - const NodeImpl &getNode(Node N) const { return NodeImpls[N]; } - NodeImpl &getNode(Node N) { return NodeImpls[N]; } - -public: - /// \brief Iterator for edges. Because this graph is bidirected, we don't - /// allow modification of the edges using this iterator. Additionally, the - /// iterator becomes invalid if you add edges to or from the node you're - /// getting the edges of. - struct EdgeIterator : public std::iterator> { - EdgeIterator(const typename std::vector::const_iterator &Iter) - : Current(Iter) {} - - EdgeIterator(NodeImpl &Impl) : Current(Impl.begin()) {} - - EdgeIterator &operator++() { - ++Current; - return *this; + typedef std::vector EdgeList; + 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"); + } - EdgeIterator operator++(int) { - EdgeIterator Copy(Current); - operator++(); - return Copy; - } - - std::tuple &operator*() { - Store = std::make_tuple(Current->Weight, Current->Other); - return Store; - } - - bool operator==(const EdgeIterator &Other) const { - return Current == Other.Current; - } - - bool operator!=(const EdgeIterator &Other) const { - return !operator==(Other); - } - - private: - typename std::vector::const_iterator Current; - std::tuple Store; - }; - - /// Wrapper for EdgeIterator with begin()/end() calls. - struct EdgeIterable { - EdgeIterable(const std::vector &Edges) - : BeginIter(Edges.begin()), EndIter(Edges.end()) {} - - EdgeIterator begin() { return EdgeIterator(BeginIter); } - - EdgeIterator end() { return EdgeIterator(EndIter); } - - private: - typename std::vector::const_iterator BeginIter; - typename std::vector::const_iterator EndIter; - }; - - // ----- Actual graph-related things ----- // - - WeightedBidirectionalGraph() {} - - WeightedBidirectionalGraph(WeightedBidirectionalGraph &&Other) - : NodeImpls(std::move(Other.NodeImpls)) {} - - WeightedBidirectionalGraph & - operator=(WeightedBidirectionalGraph &&Other) { - NodeImpls = std::move(Other.NodeImpls); - return *this; + const EdgeList *getNode(Node N) const { + auto Itr = NodeImpls.find(N); + if (Itr == NodeImpls.end()) + return nullptr; + else + return &Itr->second; } + EdgeList &getOrCreateNode(Node N) { return NodeImpls[N]; } - Node addNode() { - auto Index = NodeImpls.size(); - auto NewNode = Node(Index); - NodeImpls.push_back(NodeImpl()); - return NewNode; + 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; + + CFLGraph() = default; + CFLGraph(CFLGraph &&) = default; + CFLGraph &operator=(CFLGraph &&) = default; + + void addNode(Node N) { getOrCreateNode(N); } + + void addEdge(Node From, Node To, EdgeType Type, + StratifiedAttrs Attr = StratifiedAttrs()) { + auto &FromEdges = getOrCreateNode(From); + auto &ToEdges = getOrCreateNode(To); + FromEdges.push_back(Edge{Attr, Type, To}); + ToEdges.push_back(Edge{Attr, flipWeight(Type), From}); } - void addEdge(Node From, Node To, const EdgeTypeT &Weight, - const EdgeTypeT &ReverseWeight) { - assert(inbounds(From)); - assert(inbounds(To)); - auto &FromNode = getNode(From); - auto &ToNode = getNode(To); - FromNode.Edges.push_back(Edge(Weight, To)); - ToNode.Edges.push_back(Edge(ReverseWeight, From)); + iterator_range edgesFor(Node N) const { + auto Edges = getNode(N); + assert(Edges != nullptr); + return make_range(Edges->begin(), Edges->end()); } - iterator_range edgesFor(const Node &N) const { - const auto &Node = getNode(N); - return make_range(EdgeIterator(Node.Edges.begin()), - EdgeIterator(Node.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(); } - - /// Gets an arbitrary node in the graph as a starting point for traversal. - Node getEntryNode() { - assert(inbounds(StartNode)); - return StartNode; - } }; - -typedef WeightedBidirectionalGraph> GraphT; -typedef DenseMap NodeMapT; } //===----------------------------------------------------------------------===// @@ -667,9 +607,6 @@ /// Given a Value, potentially return which StratifiedAttr it maps to. static Optional valueToAttr(Value *Val); -/// Gets the inverse of a given EdgeType. -static EdgeType flipWeight(EdgeType Initial); - /// Gets edges of the given Instruction*, writing them to the SmallVector*. static void argsToEdges(CFLAAResult &, Instruction *, SmallVectorImpl &, const TargetLibraryInfo &); @@ -685,7 +622,7 @@ /// Builds the graph needed for constructing the StratifiedSets for the /// given function static void buildGraphFrom(CFLAAResult &, Function *, - SmallVectorImpl &, NodeMapT &, GraphT &, + SmallVectorImpl &, CFLGraph &, const TargetLibraryInfo &); /// Gets the edges of a ConstantExpr as if it was an Instruction. This function @@ -702,8 +639,8 @@ /// addInstructionToGraph would add both the `load` and `getelementptr` /// instructions to the graph appropriately. static void addInstructionToGraph(CFLAAResult &, Instruction &, - SmallVectorImpl &, NodeMapT &, - GraphT &, const TargetLibraryInfo &); + SmallVectorImpl &, CFLGraph &, + const TargetLibraryInfo &); /// Determines whether it would be pointless to add the given Value to our sets. static bool canSkipAddingToSets(Value *Val); @@ -777,18 +714,6 @@ return 1 << (ArgNum + AttrFirstArgIndex); } -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"); -} - static void argsToEdges(CFLAAResult &Analysis, Instruction *Inst, SmallVectorImpl &Output, const TargetLibraryInfo &TLI) { @@ -851,18 +776,8 @@ static void addInstructionToGraph(CFLAAResult &Analysis, Instruction &Inst, SmallVectorImpl &ReturnedValues, - NodeMapT &Map, GraphT &Graph, + CFLGraph &Graph, const TargetLibraryInfo &TLI) { - const auto findOrInsertNode = [&Map, &Graph](Value *Val) { - auto Pair = Map.insert(std::make_pair(Val, GraphT::Node())); - auto &Iter = Pair.first; - if (Pair.second) { - auto NewNode = Graph.addNode(); - Iter->second = NewNode; - } - return Iter->second; - }; - // We don't want the edges of most "return" instructions, but we *do* want // to know what can be returned. if (isa(&Inst)) @@ -880,17 +795,12 @@ auto MaybeVal = getTargetValue(&Inst); assert(MaybeVal.hasValue()); auto *Target = *MaybeVal; - findOrInsertNode(Target); + Graph.addNode(Target); return; } - auto addEdgeToGraph = [&](const Edge &E) { - auto To = findOrInsertNode(E.To); - auto From = findOrInsertNode(E.From); - auto FlippedWeight = flipWeight(E.Weight); - auto Attrs = E.AdditionalAttrs; - Graph.addEdge(From, To, std::make_pair(E.Weight, Attrs), - std::make_pair(FlippedWeight, Attrs)); + auto addEdgeToGraph = [&Graph](const Edge &E) { + Graph.addEdge(E.From, E.To, E.Weight, E.AdditionalAttrs); }; SmallVector ConstantExprs; @@ -911,13 +821,12 @@ static void buildGraphFrom(CFLAAResult &Analysis, Function *Fn, SmallVectorImpl &ReturnedValues, - NodeMapT &Map, GraphT &Graph, - const TargetLibraryInfo &TLI) { + 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, Map, Graph, TLI); + addInstructionToGraph(Analysis, Inst, ReturnedValues, Graph, TLI); } static bool canSkipAddingToSets(Value *Val) { @@ -943,74 +852,56 @@ // Builds the graph + StratifiedSets for a function. CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) { - NodeMapT Map; - GraphT Graph; + CFLGraph Graph; SmallVector ReturnedValues; - buildGraphFrom(*this, Fn, ReturnedValues, Map, Graph, TLI); - - DenseMap NodeValueMap; - NodeValueMap.reserve(Map.size()); - for (const auto &Pair : Map) - NodeValueMap.insert(std::make_pair(Pair.second, Pair.first)); - - const auto findValueOrDie = [&NodeValueMap](GraphT::Node Node) { - auto ValIter = NodeValueMap.find(Node); - assert(ValIter != NodeValueMap.end()); - return ValIter->second; - }; + buildGraphFrom(*this, Fn, ReturnedValues, Graph, TLI); StratifiedSetsBuilder Builder; - SmallVector Worklist; + SmallVector Worklist; SmallPtrSet Globals; - for (auto &Pair : Map) { - Worklist.clear(); - - auto *Value = Pair.first; - Builder.add(Value); - auto InitialNode = Pair.second; - Worklist.push_back(InitialNode); - while (!Worklist.empty()) { - auto Node = Worklist.pop_back_val(); - auto *CurValue = findValueOrDie(Node); - if (canSkipAddingToSets(CurValue)) - continue; - if (isa(CurValue)) - Globals.insert(CurValue); - - for (const auto &EdgeTuple : Graph.edgesFor(Node)) { - auto Weight = std::get<0>(EdgeTuple); - auto Label = Weight.first; - auto &OtherNode = std::get<1>(EdgeTuple); - auto *OtherValue = findValueOrDie(OtherNode); - - if (canSkipAddingToSets(OtherValue)) - continue; - if (isa(OtherValue)) - Globals.insert(OtherValue); - - bool Added; - switch (directionOfEdgeType(Label)) { - case Level::Above: - Added = Builder.addAbove(CurValue, OtherValue); - break; - case Level::Below: - Added = Builder.addBelow(CurValue, OtherValue); - break; - case Level::Same: - Added = Builder.addWith(CurValue, OtherValue); - break; - } + for (auto Node : Graph.nodes()) + Worklist.push_back(Node); - auto Aliasing = Weight.second; - Builder.noteAttributes(CurValue, Aliasing); - Builder.noteAttributes(OtherValue, Aliasing); + while (!Worklist.empty()) { + auto *CurValue = Worklist.pop_back_val(); + Builder.add(CurValue); + if (canSkipAddingToSets(CurValue)) + continue; + + if (isa(CurValue)) + Globals.insert(CurValue); + + for (const auto &Edge : Graph.edgesFor(CurValue)) { + auto Label = Edge.Type; + auto *OtherValue = Edge.Other; - if (Added) - Worklist.push_back(OtherNode); + if (canSkipAddingToSets(OtherValue)) + continue; + if (isa(OtherValue)) + Globals.insert(OtherValue); + + bool Added; + switch (directionOfEdgeType(Label)) { + case Level::Above: + Added = Builder.addAbove(CurValue, OtherValue); + break; + case Level::Below: + Added = Builder.addBelow(CurValue, OtherValue); + break; + case Level::Same: + Added = Builder.addWith(CurValue, OtherValue); + break; } + + auto Aliasing = Edge.Attr; + Builder.noteAttributes(CurValue, Aliasing); + Builder.noteAttributes(OtherValue, Aliasing); + + if (Added) + Worklist.push_back(OtherValue); } }