IntervalIterator.h [plain text]
#ifndef LLVM_INTERVAL_ITERATOR_H
#define LLVM_INTERVAL_ITERATOR_H
#include "llvm/Analysis/IntervalPartition.h"
#include "llvm/Function.h"
#include "llvm/Support/CFG.h"
#include <algorithm>
#include <set>
#include <vector>
namespace llvm {
inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) {
return BB;
}
inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
return IP->getBlockInterval(BB);
}
inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
Int->Nodes.push_back(BB);
}
inline void addNodeToInterval(Interval *Int, Interval *I) {
copy(I->Nodes.begin(), I->Nodes.end(), back_inserter(Int->Nodes));
}
template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy*>,
class IGT = GraphTraits<Inverse<NodeTy*> > >
class IntervalIterator {
std::vector<std::pair<Interval*, typename Interval::succ_iterator> > IntStack;
std::set<BasicBlock*> Visited;
OrigContainer_t *OrigContainer;
bool IOwnMem; public:
typedef IntervalIterator<NodeTy, OrigContainer_t> _Self;
typedef std::forward_iterator_tag iterator_category;
IntervalIterator() {} IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
OrigContainer = M;
if (!ProcessInterval(&M->front())) {
assert(0 && "ProcessInterval should never fail for first interval!");
}
}
IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
OrigContainer = &IP;
if (!ProcessInterval(IP.getRootInterval())) {
assert(0 && "ProcessInterval should never fail for first interval!");
}
}
inline ~IntervalIterator() {
if (IOwnMem)
while (!IntStack.empty()) {
delete operator*();
IntStack.pop_back();
}
}
inline bool operator==(const _Self& x) const { return IntStack == x.IntStack;}
inline bool operator!=(const _Self& x) const { return !operator==(x); }
inline const Interval *operator*() const { return IntStack.back().first; }
inline Interval *operator*() { return IntStack.back().first; }
inline const Interval *operator->() const { return operator*(); }
inline Interval *operator->() { return operator*(); }
_Self& operator++() { assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
do {
Interval::succ_iterator &SuccIt = IntStack.back().second,
EndIt = succ_end(IntStack.back().first);
while (SuccIt != EndIt) { bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
++SuccIt; if (Done) return *this; }
if (IOwnMem) delete IntStack.back().first;
IntStack.pop_back();
} while (!IntStack.empty());
return *this;
}
inline _Self operator++(int) { _Self tmp = *this; ++*this; return tmp;
}
private:
bool ProcessInterval(NodeTy *Node) {
BasicBlock *Header = getNodeHeader(Node);
if (Visited.count(Header)) return false;
Interval *Int = new Interval(Header);
Visited.insert(Header);
for (typename GT::ChildIteratorType I = GT::child_begin(Node),
E = GT::child_end(Node); I != E; ++I)
ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
IntStack.push_back(std::make_pair(Int, succ_begin(Int)));
return true;
}
void ProcessNode(Interval *Int, NodeTy *Node) {
assert(Int && "Null interval == bad!");
assert(Node && "Null Node == bad!");
BasicBlock *NodeHeader = getNodeHeader(Node);
if (Visited.count(NodeHeader)) { if (Int->contains(NodeHeader)) { return;
} else { if (!Int->isSuccessor(NodeHeader)) Int->Successors.push_back(NodeHeader);
}
} else { for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
E = IGT::child_end(Node); I != E; ++I) {
if (!Int->contains(*I)) { if (!Int->isSuccessor(NodeHeader)) Int->Successors.push_back(NodeHeader);
return; }
}
addNodeToInterval(Int, Node);
Visited.insert(NodeHeader);
if (Int->isSuccessor(NodeHeader)) {
Int->Successors.erase(std::remove(Int->Successors.begin(),
Int->Successors.end(), NodeHeader),
Int->Successors.end());
}
for (typename GT::ChildIteratorType It = GT::child_begin(Node),
End = GT::child_end(Node); It != End; ++It)
ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
}
}
};
typedef IntervalIterator<BasicBlock, Function> function_interval_iterator;
typedef IntervalIterator<Interval, IntervalPartition>
interval_part_interval_iterator;
inline function_interval_iterator intervals_begin(Function *F,
bool DeleteInts = true) {
return function_interval_iterator(F, DeleteInts);
}
inline function_interval_iterator intervals_end(Function *) {
return function_interval_iterator();
}
inline interval_part_interval_iterator
intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
return interval_part_interval_iterator(IP, DeleteIntervals);
}
inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
return interval_part_interval_iterator();
}
}
#endif