search for: depthfirstiterator

Hi Pabhat, Have you checked out DepthFirstIterator? (include/llvm/ADT/ DepthFirstIterator.h). It provides an iterator abstraction to perform a forward/reverse DFS traversal of a graph. Many of the LLVM datatypes that represent graphs have a template specialization of the GraphTraits<> class which allows separate algorithms to treat...

Hi all, Is there a way to walk through ALL the predecessors of a basic block in a CFG. I tried to iterate over the preds using this method for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++I) { BasicBlock *PredBB = *PI; } but this only gives the immediate predecessors for a basic block. For example, in this sample control flow graph. entry -> bb1 -> bb2 -> bb4

...call to `idf_begin(llvm::ilist_iterator<llvm::BasicBlock>&)' Hello.cpp:59: error: no matching function for call to `idf_end(llvm::ilist_iterator<llvm::BasicBlock>&)' My source code for this pass is below: #include "llvm/Support/CFG.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" virtual bool runOnFunction(Function& F) { //for each function iterating over the basic blocks for (Function::iterator b = F.begin(); b != F.end(); ++b) { for (idf_iterator<BasicBlock*> I=idf_begin(b); I!=idf_end...

...tions do. Is there any documentation about DSGraph functions besides the pool allocation paper? Thanks, xiaodong Code: for( df_iterator<DSNode*> I = df_begin(pnode), E=df_end(pnode); I!=E; ++ i) { ; } Error Message: gmake Compiling MemLeakage.cpp ../../../include/Support/DepthFirstIterator.h: In member function `void df_iterator<GraphT, GT>::reverseEnterNode() [with GraphT = DSNode*, GT = GraphTraits<DSNode*>]': ../../../include/Support/DepthFirstIterator.h:49: instantiated from `df_iterator<GraphT, GT>::df_iterator(GT::NodeType*, bool) [with GraphT = DS...

Here is the latest shrink wrapping patch, with fixes for issues identified by Evan. I am including a few small additions/fixes to include/llvm/ADT/{SparseBitVector,DepthFirstIterator}.h. Files: include/llvm/ADT/DepthFirstIterator.h include/llvm/ADT/SparseBitVector.h lib/CodeGen/PrologEpilogInserter.cpp Evan, let me know how it looks when you get a chance. Thanks much, John > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http:/...

Hi, I've done all the minor changes you recommended and have attached a new patch including both files again (even if po_iterator didn't change). However: Dan Gohman schrieb: > The plural of "child" is "children"; please rename this function > accordingly. Is "childs" just sloppy, is it american english or is it just a misconception of foreigners

...es 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...

...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, w...

...ing the computation of the first child until > it's needed (that is in the preincrement operator). The only open > question would be: how do we mark the children iterator invalid > before its first use. This does sound like a useful use-case, but I am uncomfortable with making DepthFirstIterator any heavier (by adding "CurrentTopNode" to it), is there another way to solve this problem? > The second one (poi) have to be applied anyway, as it fixes a > compile bug rendering po_ext_iterator currently unusable. Thanks, applied! http://lists.cs.uiuc.edu/pipermail/llvm-comm...

Hi @llvm, below is a copy of a message I sent to clang a hour before. I guess it's more appropriate here. --snip-- While trying to eleminate as much std::tr1::function as possible I stumbled over a design flaw in llvm::df_iterator. Consider the following code: void for_all_stmts(Stmt* S, const std::tr1::function<void(Stmt*)>& fn) { if (S) { fn(S); for

...ce part of his patch has already been committed)? Evan On Mar 16, 2009, at 3:23 PM, John Mosby wrote: > Here is the latest shrink wrapping patch, with fixes for issues > identified by Evan. > > I am including a few small additions/fixes to include/llvm/ADT/ > {SparseBitVector,DepthFirstIterator}.h. > > Files: > include/llvm/ADT/DepthFirstIterator.h > include/llvm/ADT/SparseBitVector.h > lib/CodeGen/PrologEpilogInserter.cpp > > Evan, let me know how it looks when you get a chance. > > Thanks much, > John > > > <shrink- > wrapping.P3.patch...

...> For nefarious reasons I won't go into (this is for a quick hack that > will be thrown away in a week or two), I'd like my Asm printer to get > MBBs in a depth first order. > > Is there an existing pass or function that will let me do this easily? Check out "llvm/ADT/DepthFirstIterator.h", it lets you iterate over arbitrary graphs (including CFGs) in depth first order. grep the source base for df_begin etc to see examples of use. -Chris

...iterator changes only, some (IMHO non-critical but needed) po_iterator changes are still in the pipeline and posted by me in another thread. I hope, the current approach fits all needs. Chris Lattner schrieb: > This does sound like a useful use-case, but I am uncomfortable with > making DepthFirstIterator any heavier > BTW: in order to make DepthFirstIterator more lightweight wouldn't it be better to make the visit tracking an opt-in. Thus don't provide llvm::SmallPtrSet as a default for SetType but a simple stub class implementing count and insert only. I've never used the vis...

For nefarious reasons I won't go into (this is for a quick hack that will be thrown away in a week or two), I'd like my Asm printer to get MBBs in a depth first order. Is there an existing pass or function that will let me do this easily? Thanks, Dan

llvm, What is the best way to implement a traversal of the DS graph, starting at a scalar and processing all nodes to which the scalar allows access? Currently the links vector is not public and there is no apparent way to bound the getLink call (ie a getNumLinks call).... Dave

...vm/Analysis/DSGraphTraits.h" DSNode *N = ... // Visit all children of a node... for (DSNode::iterator I = N->begin(), E = N->end(); I != E; ++I) if (I->getNode()) visit(I->getNode(), I->getOffset()); // Depth first traversal from a node: #include "Support/DepthFirstIterator.h" for (df_iterator<DSNode*> I = df_begin(N), E = df_end(); I != E; ++I) visit(*I); Note that this hasn't been tested recently, but it should basically work. -Chris -- http://llvm.cs.uiuc.edu/ http://www.nondot.org/~sabre/Projects/

The following now works for me: const DSNode *N1 = ...; df_iterator<const DSNode*> X1 = df_begin(N1), XE1 = df_end(N1); DSNode *N2 = ...; df_iterator<DSNode*> X2 = df_begin(N2), XE2 = df_end(N2); You need the following #includes: #include "Support/DepthFirstIterator.h" #include "llvm/Analysis/DSGraphTraits.h" You need this patch: http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021118/001623.html and this patch: http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021118/001628.html Unfortunately, I hadn't commited a b...

...39;t go into (this is for a quick hack that >> will be thrown away in a week or two), I'd like my Asm printer to get >> MBBs in a depth first order. >> >> Is there an existing pass or function that will let me do this >> easily? > > Check out "llvm/ADT/DepthFirstIterator.h", it lets you iterate over > arbitrary graphs (including CFGs) in depth first order. grep the > source base for df_begin etc to see examples of use. > > -Chris > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu...

Hi everyone, I'm currently trying to run a study on irreducibility of C programs, and I've implemented structural analysis (original paper by Sharir, algorithm in Muchnick's book) as an LLVM pass. When my implementation becomes a bit less buggy I'll certainly look into including it in the LLVM project. As a test for the algorithm I've been producing LLVM bitcode for C files

Hi Evan, Thanks very much for the review, I am implementing your suggestions today and will have the next patch together this weekend. A few questions/comments: On Thu, Mar 12, 2009 at 10:05 AM, Evan Cheng <echeng at apple.com> wrote: > > 1. Some of the functions that you introduced, e.g. stringifyCSRegSet > probably ought to be "static" and ifdef'ed out when NDEBUG