Re: [tree-ssa] Walking blocks in reverse

[Daniel Berlin <dberlin at dberlin dot org>]

On Friday, April 4, 2003, at 04:36  PM, Andrew MacLeod wrote:

> This is something I need which others might find useful. If you need 
> to process
> the instructions in a block in reverse, it can be *very* painful. 
> Sure, you
> can write
>   for (bsi = bsi_last(bb); !bsi_end_p (bsi); bsi_prev (&bsi))
>
> but have you looked at the implementation?...
> since CE nodes have no back link, bsi_prev() walks from the start of 
> the block
> until it finds the current stmt. Thats how it finds the previous stmt. 
> That
> means walks of big blocks in reverse may take a long time...

It's actually the most expensive part of the most expensive operation 
in SSAPRE right now (finding reaching defs for variables in new 
temporaries).
:)

> All I've implemented here is a quick stack in which we quickly walk the
> block forward pushing stmts onto the stack. When done, we pop them off 
> one
> at a time in order to process them.  So you end up with a stmt that 
> looks
> like this instead:
>
>    FOR_EACH_BSI_IN_REVERSE (bsi_stack, bsi)
>      {
>        stmt = bsi_stmt (bsi);
>      }
>
> Should we ever get a more efficient bsi_prev (), we can either replace 
> the
> macro with the bsi_prev loop, or simply replace all the macro calls 
> with
> the loop. In either case, we can throw this code away then. Until then,
> it should be handy.
>
> Is this OK to check in? Or would you rather I keep it local to the live
> range code for now?
>
> Andrew

I could use it, i had just figured i'd wait for bsi_prev to be more 
efficient, or do it myself when i got around to it.