From 31f18eeb2bff53ce48c9c980f0b0676401d593c8 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 17 Jul 2012 15:35:40 +0000 Subject: [PATCH] Allow for customized graph edge pruning in PostOrderIterator.h Make it possible to prune individual graph edges from a post-order traversal by specializing the po_iterator_storage template. Previously, it was only possible to prune full graph nodes. Edge pruning makes it possible to remove loop back-edges, for example. Also replace the existing DFSetTraits customization hook with a po_iterator_storage method for observing the post-order. DFSetTraits was only used by LoopIterator.h which now provides a po_iterator_storage specialization. Thanks to Sean and Chandler for reviewing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160366 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/PostOrderIterator.h | 69 ++++++++++++++++++++++------ include/llvm/Analysis/LoopIterator.h | 42 ++++++++--------- 2 files changed, 73 insertions(+), 38 deletions(-) diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index 63a2b5219f7..c0e38292ecc 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -23,26 +23,65 @@ namespace llvm { -template // Non-external set +// The po_iterator_storage template provides access to the set of already +// visited nodes during the po_iterator's depth-first traversal. +// +// The default implementation simply contains a set of visited nodes, while +// the Extended=true version uses a reference to an external set. +// +// It is possible to prune the depth-first traversal in several ways: +// +// - When providing an external set that already contains some graph nodes, +// those nodes won't be visited again. This is useful for restarting a +// post-order traversal on a graph with nodes that aren't dominated by a +// single node. +// +// - By providing a custom SetType class, unwanted graph nodes can be excluded +// by having the insert() function return false. This could for example +// confine a CFG traversal to blocks in a specific loop. +// +// - Finally, by specializing the po_iterator_storage template itself, graph +// edges can be pruned by returning false in the insertEdge() function. This +// could be used to remove loop back-edges from the CFG seen by po_iterator. +// +// A specialized po_iterator_storage class can observe both the pre-order and +// the post-order. The insertEdge() function is called in a pre-order, while +// the finishPostorder() function is called just before the po_iterator moves +// on to the next node. + +/// Default po_iterator_storage implementation with an internal set object. +template class po_iterator_storage { -public: SetType Visited; -}; +public: + // Return true if edge destination should be visited. + template + bool insertEdge(NodeType *From, NodeType *To) { + return Visited.insert(To); + } -/// DFSetTraits - Allow the SetType used to record depth-first search results to -/// optionally record node postorder. -template -struct DFSetTraits { - static void finishPostorder( - typename SetType::iterator::value_type, SetType &) {} + // Called after all children of BB have been visited. + template + void finishPostorder(NodeType *BB) {} }; +/// Specialization of po_iterator_storage that references an external set. template class po_iterator_storage { + SetType &Visited; public: po_iterator_storage(SetType &VSet) : Visited(VSet) {} po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {} - SetType &Visited; + + // Return true if edge destination should be visited, called with From = 0 for + // the root node. + // Graph edges can be pruned by specializing this function. + template + bool insertEdge(NodeType *From, NodeType *To) { return Visited.insert(To); } + + // Called after all children of BB have been visited. + template + void finishPostorder(NodeType *BB) {} }; templateVisited.insert(BB)) { // If the block is not visited... + if (this->insertEdge(VisitStack.back().first, BB)) { + // If the block is not visited... VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); } } } inline po_iterator(NodeType *BB) { - this->Visited.insert(BB); + this->insertEdge((NodeType*)0, BB); VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); traverseChild(); } @@ -79,7 +119,7 @@ class po_iterator : public std::iterator(S) { - if (this->Visited.insert(BB)) { + if (this->insertEdge((NodeType*)0, BB)) { VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); traverseChild(); } @@ -117,8 +157,7 @@ public: inline NodeType *operator->() const { return operator*(); } inline _Self& operator++() { // Preincrement - DFSetTraits::finishPostorder(VisitStack.back().first, - this->Visited); + this->finishPostorder(VisitStack.back().first); VisitStack.pop_back(); if (!VisitStack.empty()) traverseChild(); diff --git a/include/llvm/Analysis/LoopIterator.h b/include/llvm/Analysis/LoopIterator.h index 269ac807405..68f25f74bc2 100644 --- a/include/llvm/Analysis/LoopIterator.h +++ b/include/llvm/Analysis/LoopIterator.h @@ -109,6 +109,16 @@ public: } }; +/// Specialize po_iterator_storage to record postorder numbers. +template<> class po_iterator_storage { + LoopBlocksTraversal &LBT; +public: + po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} + // These functions are defined below. + bool insertEdge(BasicBlock *From, BasicBlock *To); + void finishPostorder(BasicBlock *BB); +}; + /// Traverse the blocks in a loop using a depth-first search. class LoopBlocksTraversal { public: @@ -155,31 +165,17 @@ public: DFS.PostBlocks.push_back(BB); DFS.PostNumbers[BB] = DFS.PostBlocks.size(); } - - //===---------------------------------------------------------------------- - // Implement part of the std::set interface for the purpose of driving the - // generic po_iterator. - - /// Return true if the block is outside the loop or has already been visited. - /// Sorry if this is counterintuitive. - bool count(BasicBlock *BB) const { - return !DFS.L->contains(LI->getLoopFor(BB)) || DFS.PostNumbers.count(BB); - } - - /// If this block is contained in the loop and has not been visited, return - /// true and assign a preorder number. This is a proxy for visitPreorder - /// called by POIterator. - bool insert(BasicBlock *BB) { - return visitPreorder(BB); - } }; -/// Specialize DFSetTraits to record postorder numbers. -template<> struct DFSetTraits { - static void finishPostorder(BasicBlock *BB, LoopBlocksTraversal& LBT) { - LBT.finishPostorder(BB); - } -}; +inline bool po_iterator_storage:: +insertEdge(BasicBlock *From, BasicBlock *To) { + return LBT.visitPreorder(To); +} + +inline void po_iterator_storage:: +finishPostorder(BasicBlock *BB) { + LBT.finishPostorder(BB); +} } // End namespace llvm -- 2.34.1