[prev in list] [next in list] [prev in thread] [next in thread]
List: cfe-dev
Subject: [cfe-dev] Patch for llvm::DepthFirstIterator.h and
From: Olaf Krzikalla <Olaf.Krzikalla () tu-dresden ! de>
Date: 2009-06-26 12:32:44
Message-ID: 4A44BFEC.9050301 () tu-dresden ! de
[Download RAW message or body]
Hi @clang and @llvm,
attached you'll find a patch dealing with some iterator issues I already
mentioned in both lists. Since there was no reaction I cross-post again
- now IMHO production-ready code.
The patch is considered to get checked-in out of the box. It should not
affect the behavior of existing and working code. I really need it for
clang AST processing.
Changes:
1. Both iterators now can deal with sub-nodes==0 - they just skip them
silently. For AST processing this is badly needed as you sometimes have
0-nodes in the AST (e.g. in 'for(;;) {}'). Until now both iterators
crash if they traverse a sub-node==0.
2. In llvm::PostOrderIterator.h I fixed a compile bug which occured if
used with external storage (which apparently nobody does until now).
3. I changed the behavior of llvm::DepthFirstIterator.h regarding the
retrieving of the first child. This is now retrieved in exactly that
moment it's needed. Until now it was retrieved too early, thus you
actually couldn't change the childs of a just processed node. I can't
think of an insane working example, which would break due to this change.
4. I added a public skipChilds member function to df_iterator which acts
similiar to operator++. However it skips all childs of the currently
processed node and returns *this. You can use it like in
for (i = df_begin(), e = df_end(); i!=e;)
{
foo() ? i.skipChilds() : ++i;
}
Best
Olaf Krzikalla
["llvm-iterator.patch" (text/plain)]
Index: DepthFirstIterator.h
===================================================================
--- DepthFirstIterator.h (revision 74169)
+++ DepthFirstIterator.h (working copy)
@@ -72,25 +72,51 @@
// VisitStack - Used to maintain the ordering. Top = current block
// First element is node pointer, second is the 'next child' to visit
std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
+ NodeType* CurrentTopNode;
private:
inline df_iterator(NodeType *Node) {
this->Visited.insert(Node);
- VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node)));
+ CurrentTopNode = Node;
}
- inline df_iterator() { /* End is when stack is empty */ }
+ inline df_iterator() { CurrentTopNode = 0; /* End is when stack is empty */ }
inline df_iterator(NodeType *Node, SetType &S)
: df_iterator_storage<SetType, ExtStorage>(S) {
- if (!S.count(Node)) {
+ CurrentTopNode = S.count(Node) ? 0 : Node;
+ if (CurrentTopNode) {
this->Visited.insert(Node);
- VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node)));
}
}
inline df_iterator(SetType &S)
: df_iterator_storage<SetType, ExtStorage>(S) {
// End is when stack is empty
+ CurrentTopNode = 0;
}
+ inline void toNext()
+ {
+ do {
+ std::pair<NodeType *, ChildItTy> &Top = VisitStack.back();
+ NodeType *Node = Top.first;
+ ChildItTy &It = Top.second;
+
+ while (It != GT::child_end(Node)) {
+ NodeType *Next = *It++;
+ if (Next && !this->Visited.count(Next)) { // Has our next sibling been visited?
+ // No, do it now.
+ this->Visited.insert(Next);
+ CurrentTopNode = Next;
+ return;
+ }
+ }
+
+ // Oops, ran out of successors... go up a level on the stack.
+ VisitStack.pop_back();
+ } while (!VisitStack.empty());
+
+ CurrentTopNode = 0;
+ }
+
public:
typedef typename super::pointer pointer;
typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self;
@@ -108,13 +134,14 @@
static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); }
inline bool operator==(const _Self& x) const {
- return VisitStack.size() == x.VisitStack.size() &&
+ return CurrentTopNode == x.CurrentTopNode &&
+ VisitStack.size() == x.VisitStack.size() &&
VisitStack == x.VisitStack;
}
inline bool operator!=(const _Self& x) const { return !operator==(x); }
inline pointer operator*() const {
- return VisitStack.back().first;
+ return CurrentTopNode;
}
// This is a nonstandard operator-> that dereferences the pointer an extra
@@ -124,24 +151,17 @@
inline NodeType *operator->() const { return operator*(); }
inline _Self& operator++() { // Preincrement
- do {
- std::pair<NodeType *, ChildItTy> &Top = VisitStack.back();
- NodeType *Node = Top.first;
- ChildItTy &It = Top.second;
+ VisitStack.push_back(std::make_pair(CurrentTopNode, GT::child_begin(CurrentTopNode)));
+ toNext();
+ return *this;
+ }
- while (It != GT::child_end(Node)) {
- NodeType *Next = *It++;
- if (!this->Visited.count(Next)) { // Has our next sibling been visited?
- // No, do it now.
- this->Visited.insert(Next);
- VisitStack.push_back(std::make_pair(Next, GT::child_begin(Next)));
- return *this;
- }
- }
-
- // Oops, ran out of successors... go up a level on the stack.
- VisitStack.pop_back();
- } while (!VisitStack.empty());
+ inline _Self& skipChilds() { // skips all childs of the current node and traverses to next node
+ if (!VisitStack.empty()) {
+ toNext();
+ } else {
+ CurrentTopNode = 0;
+ }
return *this;
}
Index: PostOrderIterator.h
===================================================================
--- PostOrderIterator.h (revision 74169)
+++ PostOrderIterator.h (working copy)
@@ -56,7 +56,7 @@
void traverseChild() {
while (VisitStack.top().second != GT::child_end(VisitStack.top().first)) {
NodeType *BB = *VisitStack.top().second++;
- if (!this->Visited.count(BB)) { // If the block is not visited...
+ if (BB && !this->Visited.count(BB)) { // If the block is not visited...
this->Visited.insert(BB);
VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
}
@@ -64,15 +64,17 @@
}
inline po_iterator(NodeType *BB) {
- this->Visited.insert(BB);
- VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
- traverseChild();
+ if (BB) {
+ this->Visited.insert(BB);
+ VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
+ traverseChild();
+ }
}
inline po_iterator() {} // End is when stack is empty.
inline po_iterator(NodeType *BB, SetType &S) :
- po_iterator_storage<SetType, ExtStorage>(&S) {
- if(!S.count(BB)) {
+ po_iterator_storage<SetType, ExtStorage>(S) {
+ if(BB && !S.count(BB)) {
this->Visited.insert(BB);
VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
traverseChild();
@@ -80,7 +82,7 @@
}
inline po_iterator(SetType &S) :
- po_iterator_storage<SetType, ExtStorage>(&S) {
+ po_iterator_storage<SetType, ExtStorage>(S) {
} // End is when stack is empty.
public:
typedef typename super::pointer pointer;
_______________________________________________
cfe-dev mailing list
cfe-dev@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic