Re: BB reordering question

[Archie Cobbs <archie at dellroad dot org>]

Zdenek Dvorak wrote:
> > I have a simple question that hopefully has a simple answer...
> > I'm using GCC (gcc (GCC) 3.2.2 20030222 (Red Hat Linux 3.2.2-5))
> > for x86 to compile machine generated code that looks like this:
> > 
> >     function()
> >     {
> >       const void *lables[] = { &&label1, &&label2, &&label3, ... };
> > 
> >       label1:
> > 	    blah blah
> > 	    if (blah)
> > 		    goto label3;
> > 	    blah
> >       label2:
> > 	    blah
> > 	    ..
> > 	    if (blah)
> > 		    goto *labels[i];
> > 	    ...
> >       label3:
> > 	    blah
> > 	    ...
> >       ...
> >     }
> > 
> > At the end of each basic block, control either flows into the next
> > basic block, there is a return from the function, or there is a call
> > to another non-returning function marked __attribute__((noreturn)).
> > 
> > A requirement states that the labels[] array must be sorted in strictly
> > ascending order (all basic blocks are nonempty). But I'd also like to
> > enable as many optimizations as possible. So my question is, what is
> > the best choice of optimizations that won't reorder any blocks, ever?
> > 
> > I've tried "-O2 -fno-reorder-blocks"; it *almost* works but not quite.
> > 
> > E.g. if the last BB terminates with a call to a noreturn function,
> > GCC will still reorder it, presumably so an epilogue is at the end
> > of the function in memory (I saw some related (?) mailing list
> > comments: http://gcc.gnu.org/ml/gcc-patches/2002-05/msg02293.html).
> > 
> > First, is this a bug, feature, or am I confused about what the
> > "-fno-reorder-blocks" flag is supposed to do?
> 
> -fno-reorder-blocks switches of basic block reordering pass. It however
> has nothing to do with other passes that may change the order of the
> blocks.
> 
> > Is there some other way for me to get the desired result other than
> > disabling optimzation altogether?
> 
> No, as far as I am aware of; I believe that even just cleanup_cfg may
> reorder the blocks sometimes, and it is run even if optimizations are
> disabled completely.
> 
> I would just recommend to avoid such hacks (I am not quite sure what
> you want to achieve anyway; I can think of only one reason why you might
> want to have the array sorted, and it is if you wanted to do binary
> search over it, but it does not make any sense me).

My application involves analyzing the C call stack (following saved
frame pointers to find saved PC's) and needs to be able to figure
out not only which function a PC corresponds to (that's easier) but
also which basic block the saved PC corresponds to (i.e., within
which basic block the invocation on the call stack happened).

So the array doesn't literally have to be sorted, but I do need to
be able to reliably map a saved PC to a basic block. E.g. for this case:

    label0:
	    ...
    label1:
	    ...
	    function(x, y);
	    ...
    lable2:
	    ...

the application needs to be able to know for certain that the function
call happened between label1 and label2 (and not between some other
two labels) when analyzing the stack.

Perhaps it would work to simply deduce the BB permutation after the fact
(by sorting the labels[] array) and apply its inverse at mapping time?
Are there any gotchas with this approach?

Thanks for your help!

-Archie

__________________________________________________________________________
Archie Cobbs     *    Halloo Communications    *     http://www.halloo.com