Re: Patch: Support IA-64 speculation [3/5]

[Maxim Kuvyrkov <mkuvyrkov at ispras dot ru>]

Daniel Berlin wrote:

> Kenneth Zadeck posted code that finds all sorts of regions in the
> control flow graph, and nicely sets up BB style links for them (IE you
> can walk them like you walk BB's).
I didn't know about Kenneth's code. Will take a look at it in a week or two.
> It was based on algorithms in a compiler book that was never published.
>
> It used to depend on the basic block renumbering patch, but since that
> has been committed, the patch should be much much smaller (I emailed
> kenny asking him to see if he could redo it real quick).
>
> Look at 
> http://gcc.gnu.org/ml/gcc-patches/2005-09/msg01888.html
>
> Mainly, the regions.c part.
>
> You'll note it is also *very* heavily commented.
>
> Also, if you think that is overkill, and you only want something that
> finds, for example, SESE regions, you can write something that will find
> SESE regions in linear time based on the algorithms in
> http://citeseer.ist.psu.edu/johnson93finding.html
> and 
> http://citeseer.ist.psu.edu/johnson94program.html
>
> (This is only a couple hundred lines of code, I did it a year or so ago
> and sent it to Jan Hubicka because he wanted it for something).
>
> IMHO, my real problem not sure why we need to have two region finding
> algorithms (they really are different algorithms), instead of one, and
> why it should need to iterate on reducible CFG's.
>
> Ideally, we'd just use one of the "good" ones, like Kenny's, which
> should meet the needs of everyone involved.  If you are not amenable to
> that (i'll state that it is an eventual goal to use that region code in
> the scheduler as the region finder), it should still be possible to
> generate the regions we want, using the SESE algorithm, or a modication
> of it, in linear time.
>
> --Dan

My goal in writing this code was to form regions from the "rest" of
basic blocks (straight flow code between cycles) and get an idea of
their impact on scheduling. As a result, I've understood that interblock
scheduling needs more accurate instruction priority computation to
provide satisfactory tuning-space. In fact, presently, control 
speculation is a worst-case choice in haifa scheduler.

I'm now working on improving instruction priority computation. With it I
hope to make interblock speculation (and large regions) more profitable.

Maxim