// reachable from the loop header.
//===----------------------------------------------------------------------===//
-#ifndef LLVM_ANALYSIS_LOOP_ITERATOR_H
-#define LLVM_ANALYSIS_LOOP_ITERATOR_H
+#ifndef LLVM_ANALYSIS_LOOPITERATOR_H
+#define LLVM_ANALYSIS_LOOPITERATOR_H
-#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Analysis/LoopInfo.h"
Loop *getLoop() const { return L; }
+ /// Traverse the loop blocks and store the DFS result.
+ void perform(LoopInfo *LI);
+
/// Return true if postorder numbers are assigned to all loop blocks.
bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
}
};
-/// Define a graph of blocks within a loop. Allows LoopBlocksTraversal to
-/// use the generic po_iterator with specialized GraphTraits.
-struct LoopBlocksGraph {
- Loop *L;
-
- LoopBlocksGraph(Loop *Container) : L(Container) {}
-};
-
-template<> struct GraphTraits<LoopBlocksGraph> :
- public GraphTraits<BasicBlock*> {
-
- static BasicBlock *getEntryNode(LoopBlocksGraph G) {
- return G.L->getHeader();
- }
+/// 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:
/// Graph traversal iterator.
- typedef po_iterator<LoopBlocksGraph, LoopBlocksTraversal, true> POTIterator;
+ typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
private:
LoopBlocksDFS &DFS;
/// finishPostorder to record the DFS result.
POTIterator begin() {
assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
- return po_ext_begin(LoopBlocksGraph(DFS.L), *this);
+ assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
+ return po_ext_begin(DFS.L->getHeader(), *this);
}
POTIterator end() {
- return po_ext_end(LoopBlocksGraph(DFS.L), *this);
+ // po_ext_end interface requires a basic block, but ignores its value.
+ return po_ext_end(DFS.L->getHeader(), *this);
}
/// Called by po_iterator upon reaching a block via a CFG edge. If this block
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