diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-07-17 15:35:40 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-07-17 15:35:40 +0000 |
commit | 31f18eeb2bff53ce48c9c980f0b0676401d593c8 (patch) | |
tree | 2c14394011c8fb010cb7871545e2650ef35f77be | |
parent | 9d26b0ba06479d9debadebce19344169f72407dd (diff) | |
download | external_llvm-31f18eeb2bff53ce48c9c980f0b0676401d593c8.zip external_llvm-31f18eeb2bff53ce48c9c980f0b0676401d593c8.tar.gz external_llvm-31f18eeb2bff53ce48c9c980f0b0676401d593c8.tar.bz2 |
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
-rw-r--r-- | include/llvm/ADT/PostOrderIterator.h | 69 | ||||
-rw-r--r-- | 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 63a2b52..c0e3829 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -23,26 +23,65 @@ namespace llvm { -template<class SetType, bool External> // 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 SetType, bool External> class po_iterator_storage { -public: SetType Visited; -}; +public: + // Return true if edge destination should be visited. + template<typename NodeType> + 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<class SetType> -struct DFSetTraits { - static void finishPostorder( - typename SetType::iterator::value_type, SetType &) {} + // Called after all children of BB have been visited. + template<typename NodeType> + void finishPostorder(NodeType *BB) {} }; +/// Specialization of po_iterator_storage that references an external set. template<class SetType> class po_iterator_storage<SetType, true> { + 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<class NodeType> + bool insertEdge(NodeType *From, NodeType *To) { return Visited.insert(To); } + + // Called after all children of BB have been visited. + template<class NodeType> + void finishPostorder(NodeType *BB) {} }; template<class GraphT, @@ -64,14 +103,15 @@ class po_iterator : public std::iterator<std::forward_iterator_tag, void traverseChild() { while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) { NodeType *BB = *VisitStack.back().second++; - if (this->Visited.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<std::forward_iterator_tag, inline po_iterator(NodeType *BB, SetType &S) : po_iterator_storage<SetType, ExtStorage>(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<SetType>::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 269ac80..68f25f7 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, true> { + 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<LoopBlocksTraversal> { - static void finishPostorder(BasicBlock *BB, LoopBlocksTraversal& LBT) { - LBT.finishPostorder(BB); - } -}; +inline bool po_iterator_storage<LoopBlocksTraversal, true>:: +insertEdge(BasicBlock *From, BasicBlock *To) { + return LBT.visitPreorder(To); +} + +inline void po_iterator_storage<LoopBlocksTraversal, true>:: +finishPostorder(BasicBlock *BB) { + LBT.finishPostorder(BB); +} } // End namespace llvm |