llvm dev - Nov 2010 - [LLVMdev] A way to traverse machine basic blocks in order?

I'm looking for a way to traverse machine basic blocks in a specific order.
Basically I want all blocks that are predecessors to the current block to be
traversed before the current block.  I've looked at MachineDominatorTree but
this doesn't traverse them in quite the way I want them to. Anyone know of a
way to do this?

Thanks,
Micah
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101123/1cdb0f59/attachment.html>

The reverse postorder iterator does what you want. It's defined in
ADT/PostOrderIterator.h, and is used like this:

  ReversePostOrderTraversal<Function*> RPOT(&F);
  for (ReversePostOrderTraversal<Function*>::rpo_iterator RI =
RPOT.begin(),
       RE = RPOT.end(); RI != RE; ++RI)
    <work here>

Creating a ReversePostOrderTraversal is not cheap, because it first has to do a
postorder walk of the entire graph.

Cameron

On Nov 23, 2010, at 9:21 PM, Villmow, Micah wrote:
> I’m looking for a way to traverse machine basic blocks in a specific order.
> Basically I want all blocks that are predecessors to the current block to
be traversed before the current block.  I’ve looked at MachineDominatorTree but
this doesn’t traverse them in quite the way I want them to. Anyone know of a way
to do this?
>  
> Thanks,
> Micah
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101123/611a96da/attachment.html>

Cameron,
 Thanks for the tip. I understand that it is not cheap, but I must traverse the
graph in this specific order, so I really don't have a choice but I only
need to create it once per function.
 Thanks again, it does what I need and I don't have to write my own. :D

Micah

From: Cameron Zwarich [mailto:zwarich at apple.com]
Sent: Tuesday, November 23, 2010 6:34 PM
To: Villmow, Micah
Cc: LLVM Developers Mailing List
Subject: Re: [LLVMdev] A way to traverse machine basic blocks in order?

The reverse postorder iterator does what you want. It's defined in
ADT/PostOrderIterator.h, and is used like this:

  ReversePostOrderTraversal<Function*> RPOT(&F);
  for (ReversePostOrderTraversal<Function*>::rpo_iterator RI =
RPOT.begin(),
       RE = RPOT.end(); RI != RE; ++RI)
    <work here>

Creating a ReversePostOrderTraversal is not cheap, because it first has to do a
postorder walk of the entire graph.

Cameron

On Nov 23, 2010, at 9:21 PM, Villmow, Micah wrote:


I'm looking for a way to traverse machine basic blocks in a specific order.
Basically I want all blocks that are predecessors to the current block to be
traversed before the current block.  I've looked at MachineDominatorTree but
this doesn't traverse them in quite the way I want them to. Anyone know of a
way to do this?

Thanks,
Micah
_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu<mailto:LLVMdev at cs.uiuc.edu>        
http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101124/b23d0b54/attachment.html>