Re: ipa vrp implementation in gcc

["Bin.Cheng" <amker dot cheng at gmail dot com>]

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.

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