similar to: [LLVMdev] Depth First Sort of Machine Basic Blocks just before emitting code

On Apr 13, 2009, at 11:20 AM, Daniel M Gessel wrote: > 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

That looks like it does a preorder depth first traversal (I think). I'm looking for postorder. Is there a trivial transform between the two? (I don't know one.) Am I wrong about the preorder/postorder? If not, anything lurking for postorder traversal? Thanks, Dan On Apr 13, 2009, at 2:35 PM, Chris Lattner wrote: > > On Apr 13, 2009, at 11:20 AM, Daniel M Gessel wrote:

Too obvious! Thanks Dan On Apr 13, 2009, at 7:58 PM, John Mosby wrote: > po_iterator (ADT/PostOrderIterator.h) ? > > On Mon, Apr 13, 2009 at 5:40 PM, Daniel M Gessel <gessel at apple.com> > wrote: > That looks like it does a preorder depth first traversal (I think). > I'm looking for postorder. Is there a trivial transform between the > two? (I don't know

po_iterator (ADT/PostOrderIterator.h) ? On Mon, Apr 13, 2009 at 5:40 PM, Daniel M Gessel <gessel at apple.com> wrote: > That looks like it does a preorder depth first traversal (I think). > I'm looking for postorder. Is there a trivial transform between the > two? (I don't know one.) > > Am I wrong about the preorder/postorder? If not, anything lurking for >

I use the following code to do the depth first search on the DSGraph. And I always got this error message. Couldn't figure out what's wrong. Could you please let me know? Besides, I really have no idea about what those functions do. Is there any documentation about DSGraph functions besides the pool allocation paper? Thanks, xiaodong Code: for( df_iterator<DSNode*> I =

Hi John, It looks pretty good. Thanks for working on this. Some comments: 1. Some of the functions that you introduced, e.g. stringifyCSRegSet probably ought to be "static" and ifdef'ed out when NDEBUG is defined. 2. + // DEBUG + if (! MBB->empty() && ! CSRUsed[MBB].intersects(restore)) { + MachineInstr* MI = BeforeI; + DOUT <<

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

Hi everyone, My apologies if this isn?t the right place to submit this?I?m new to the R-devel community and still figuring out what is where. If people want to skip my writeup and just look at the code, I?ve made a repository for it here: https://github.com/ahl27/new_dendrapply/tree/master. I?m not quite sure how to integrate it into a fork of R-devel; the package structure is different from

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

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

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

Here is an updated patch for shrink wrapping with: - spills/restores done with stack slot stores/loads - stack adjustment removed - refactoring (but still in need of more) - spill/restore insertion code unified with spill/restore placement code Documentation available here<http://wiki.github.com/jdmdj/llvm-work/shrink-wrapping-work> illustrates shrink wrapping with loops and discusses a

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

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:

On Mon, Mar 2, 2009 at 10:35 AM, Evan Cheng <echeng at apple.com> wrote: > > On Mar 1, 2009, at 2:57 PM, John Mosby wrote: > > Obviously, all of this applies only when spills are done with push/pop, > which is the case on x86. I used this issue to start looking at generalizing > how spills and restores are handled, before looking too closely at other > targets, and

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

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 them as graphs, walk them, etc. (Both BasicBlock

Hi, Well, yes i did try your suggestion but i keep on running into a compilation problem. The error is: llvm[0]: Compiling Hello.cpp for Release build (PIC) /home/saraswat/llvm/llvm-2.1/include/llvm/ADT/GraphTraits.h: In instantiation of `llvm::GraphTraits<llvm::ilist_iterator<llvm::BasicBlock> >': Hello.cpp:59: instantiated from here

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 >

Has anyone extended Rails''s acts_as_tree to use the Modified Preorder Traversal algorithm? This is a really clever trick for optimizing access to trees stored in databases, as described lucidly in this article: http://www.sitepoint.com/article/hierarchical-data-database/2 It adds two integer fields, a "left counter" and "right counter", to each row. By