Re: ipa vrp implementation in gcc

[Jan Hubicka <hubicka at ucw dot cz>]

> On Mon, Jan 11, 2016 at 1:38 AM, Kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
> > Hi All,
> >
> > I am looking at implementing a ipa vrp pass. Jan Hubicka also talks
> > about this in 2013 GNU Cauldron as one of the optimization he would like
> > to see in gcc. So my question is, is any one implementing it. If not we
> > would like to do that.
> >
> > I also looked at the ipa-cp implementation to see how this can be done.
> > Going by this, one of the way to implement this is (skipping all the
> > details):
> >
> > - Have an early tree-vrp so that we can have value ranges for parameters
> > at call sites.
> 
> I'd rather use the IPA analysis phase for this and use a VRP algorithm
> that doesn't require ASSERT_EXPR insertion.

Another potential use of value ranges is the profile estimation. 
http://www.lighterra.com/papers/valuerangeprop/Patterson1995-ValueRangeProp.pdf
It seems to me that we may want to have something that can feed sane loop
bounds for profile estimation as well and we can easily store the known
value ranges to SSA name annotations.
So I think separate local pass to compute value ranges (perhaps with less
accuracy than full blown VRP) is desirable.
> 
> > - Create jump functions that captures the value ranges of call sites
> > propagate the value ranges. In 2013 talk, Jan Hubicka talks about
> >
> > - Modifying ipa-prop.[h|c] to handles this but wouldn't it be easier to
> > have its own and much more simpler implementation ?
> 
> No idea.

I think the ipa-prop.c probably won't need any siginificant changes.  The 
code basically analyze what values are passed thorugh the function and
this works for constants as well as for intervals. In fact ipa-cp already
uses the same ipa-prop analysis for 
 1) constant propagation
 2) alignment propagation
 3) propagation of known polymorphic call contextes.

So replacing 1) by value range propagation should be easily doable. 
I would also like to replace alignment propagation by bitwise constant
propagation (i.e. propagating what bits are known to be zero and what
bits are known to be one). We already do have bitwise CCP, so we could
deal with this basically in the same way as we deal with value ranges.

ipa-prop could use bit of clenaing up and modularizing that I hope will
be done next stage1 :)

> 
> > - Once we have the value ranges for parameter/return values, we could
> > rely on tree-vrp to use this and do the optimizations
> 
> Yep.  IPA transform phase should annotate parameter default defs with
> computed ranges.

Yep, in addition we will end up with known value ranges stored in aggregates
for that we need better separate representaiton

See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68930
> 
> > Does this make any sense? Any thoughts/suggestions to work on this is
> > highly appreciated.
> 
> IPA alignment propagation should already be somewhat similar as in doing
> an intersection step during propagation.

The merge operation is same as VRP does, but yep, IPA alignment code is good
one to follow for start.  Martin implemented it in a bit limited way so it
never performs cloning, but we can deal with that incrementally.
> 
> Richard.
> 
> > Thanks,
> > Kugan