Re: ipa vrp implementation in gcc

[Richard Biener <richard dot guenther at gmail dot com>]

On Wed, Feb 10, 2016 at 11:00 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Mon, Jan 18, 2016 at 5:10 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>> On Mon, Jan 18, 2016 at 12:00 AM, Kugan
>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> > Hi,
>>> >
>>> >> 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.
>>> >
>>> > Thanks for the reference. I am looking at implementing a local pass for
>>> > VRP. The value range computation in tree-vrp is based on the above
>>> > reference and uses ASSERT_EXPR insertion (I understand that you posted
>>> > the reference above for profile estimation). As Richard mentioned in his
>>> > reply, the local pass should not rely on ASSERT_EXPR insertion.
>>> > Therefore, do you have any specific algorithm in mind (i.e. Any
>>> > published paper or reference from book)?. Of course we can tweak the
>>> > algorithm from the reference above but would like to understand what
>>> > your intension are.
>>>
>>> I have (very incomplete) prototype patches to do a dominator-based
>>> approach instead (what is refered to downthread as non-iterating approach).
>>> That's cheaper and is what I'd like to provide as an "utility style" interface
>>> to things liker niter analysis which need range-info based on a specific
>>> dominator (the loop header for example).
>>
>> In general, given that we have existing VRP implementation I would suggest
>> first implementing the IPA propagation and profile estimation bits using
>> existing VRP pass and then try to compare the simple dominator based approach
>> with the VRP we have and see what are the compile time/code quality effects
>> of both. Based on that we can decide how complex VRP we really want.
> Hi Honza,
> These two are not conflict with each other, right?  The control-flow
> sensitive VRP in each function could well inherit IPA analysis
> results.

Of course.  Like the 2nd VRP pass inherits the results of the 1st.

Richard.

> Thanks,
> bin
>>
>> It will be probably also more fun to implement it this way :)
>> I plan to collect some data on early VRP and firefox today or tomorrow.
>>
>> Honza
>>>
>>> Richard.
>>>
>>> >> 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 :)
>>> >
>>> > We (Myself and Prathamesh) are interested in working on LTO
>>> > improvements. Let us have a look at this.
>>> >
>>> >>>
>>> >>>> - 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
>>> >>>
>>> >
>>> > Thanks,
>>> > Kugan