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

[Maxim Kuvyrkov]

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