Re: How to detect whether we're inside of a loop??

[Jan Hubicka <jh at suse dot cz>]

> Jan Hubicka wrote:
> > > Daniel Berlin wrote:
> > > > On Wednesday, April 9, 2003, at 02:25  PM, Geoff Keating wrote:
> > > > > Why don't you just use the support that GCC already has for
> > > > > detecting the probability that a block will be executed?
> > > > 
> > > > Because it's at the tree level he's talking about, not the RTL
> > > > level.
> > > 
> > > FWIW, once tree-ssa-vrp is implemented, you get branch
> > > prediction with it for free.  Would that help?
> > Definitly :)
> > We already do have branch prediction algorithm at RTL level.  I
> > would like to port it to tree-ssa as soon as we realize how to
> > maintain the profile over RTL expansion....
> 
> Yes that would be nice.  Already when I first posted the pointer to the
> SSA-VRP paper to Diego, it was discussed that we should figure out a way to

How expansive the SSA-VRP is?  All ways of doing VRP seems to be very
expensive and/or dificult and the value of having accurate VRP
information is not too well understood (at least by me), so I am not
sure it is wortwhile to do in the production compiler.  On the other
hand it is so cool toy so I would like to see it happen in any case
and I guess we will find use for it later.

Note that VRP does not completely replace the existing branch prediction
algorithm.  Only when combined together it leads to beter prediction.
Also the paper on VRP based branch prediction is doing stronger form of
it - it propagates onot only intervals but each value range is
subdivided into multiple intervals each having different probability, so
the overall analysis are even more tricky.

> bring branch predictions from trees to RTL.  Diego said that he expected it
> to be quite hard to do because RTL is so different from trees.  He also
> suggested that we could maybe use RTL NOTEs for it...

Yes, I think everyone wonders about how this can be done.

It can be great if we were able to do expansion preserving the CFG
structure (ie take expresion of each basic block in tree CFG and expand
them into RTL and modify the expanders for expresion doing the control
flow to inject code into proper basic block).

This will introduce new basic blocks, but we can call
find_sub_basic_blocks as we do after instruction splitting - in fact RTL
expansion should be as easy as instruction splitting from this point of
view if done properly.

There are other showstoppers waiting - we need to replace all the passes
destroying CFG first - loop optimizer, sibcall, EH expansion.
We are working on that.

Honza

> 
> Greetz
> Steven
>