On September 20, 2017 1:10:25 AM GMT+02:00, Jeff Law <l...@redhat.com> wrote: >On 07/26/2017 05:20 AM, Richard Biener wrote: >> On Tue, Jul 25, 2017 at 4:50 PM, Andrew MacLeod <amacl...@redhat.com> >wrote: >>> On 07/25/2017 03:12 AM, Richard Biener wrote: >>>> >>>> On Fri, Jul 21, 2017 at 9:30 PM, Aldy Hernandez <al...@redhat.com> >wrote: >>>>> >>>>> On Mon, Jul 17, 2017 at 6:23 AM, Richard Biener >>>>> <richard.guent...@gmail.com> wrote: >>>>>> >>>>>> On Mon, Jul 17, 2017 at 8:51 AM, Aldy Hernandez ><al...@redhat.com> >>>>>> wrote: >>>>>>> >>>>>>> How does this look? >>>>>> >>>>>> It's a change that on its own doesn't look worthwhile to me. >>>>>> >>>>>> So please post the changes that will build ontop of this. Like >removing >>>>>> anti-ranges from VRP or your on-demand value-range stuff. >>>>>> >>>>>> Thanks, >>>>>> Richard. >>>>> >>>>> From the looks of it, we can have a variety of VRP ranges that >are not >>>>> representable at all with the an integer range class. For >instance, I >>>>> see the following ranges built in set_value_range(): >>>>> >>>>> [INT, (nop_expr SSA)] >>>>> >>>>> [INT, (plus_expr SSA INT)] >>>>> >>>>> [(negate_expr SSA), (negate_expr SSA)] >>>>> >>>>> [(plus_expr (negate_expr SSA INT)), >>>>> (plus_expr (negate_expr SSA) INT)] >>>>> >>>>> [SSA, SSA] >>>>> >>>>> So...I guess the first suggestion is out of the question ;-). >>>> >>>> Well. We do not want range operations implemented twice (really!) >>>> so range operations need to work on both representations. So we >>>> should think of a way to get rid of anti-ranges in VRP which, >frankly, >>>> means that for the sake symbolic ranges we have to trade them >>>> with handling open/closed ranges which I'm not sure will be less of >>>> a hassle to handle? >>> >>> >>> I originally looked at ranges with symbolic expressions, but as soon >as >>> there are ranges comprised of more than 1 range, symbolics became a >>> nightmare. At best you can do endpoints, and even then you have to >start >>> adding complexity.. [0, 100] Union [5, x_4] now has to become >[0, >>> max(100, x_4)] , and chained operations were making the expressions >more and >>> more complicated. Trying to maintain these expression across >optimizations >>> was also very problematic as the IL changes and these expressions >are not in >>> the IL and don't suffer updates easily. >>> >>> At which point one asks themselves whether it actually makes sense >to >>> integrate that into the range representation, or try a different >tactic. >>> >>> Seems to me its cleaner to have an integral range, and when >appropriate >>> track symbols separately to determine if their values can be >refined. If >>> at some point you can resolve those symbols to an integral value, >then you >>> simply update the integral range with the new range you've >determined. >>> >>> VRP chooses to do this by creating a completely different structure >for >>> ranges, and representing endpoints as expression trees. It then >updates the >>> integral ranges at the end of the pass. It uses anti-ranges as a >shorthand >>> to handle a special case of a range comprised of 2 ranges. As it >stands >>> right now, VRP's version of union and intersection can never have >much in >>> common with a general integral range implementation. They are 2 very >>> different beasts. >>> >>> So we cant do much about VRP internally yet without some significant >>> surgery. >>> >>> This issue seems orthogonal to me though. irange is not intended to >ever do >>> anything with symbols, thus can never replace VRPs internal >value_range >>> class. We're simply replacing "struct range_info_def" with a new >range >>> structure and API which can support more precise ranges than a pair >of >>> integral endpoints. We'll then build on that by providing routines >which >>> can generate more precise range information as well. >>> >>> For the moment we provide an implementation with the same precision >to >>> a) ensure code generation remains the same >>> b) allow the compiler to use it for a while to make sure no bugs >have been >>> introduced >>> c) and there is nothing that would utilize the additional >precision yet >>> anyway. >>> >>> I just think its important to get it in the code base so its being >used and >>> we can be sure its correct. >> >> But nothing uses all the methods. >> >> And we're ending up with two variants of range + range, etc. >But I think this is inevitable. Consider for example floating point >ranges. There's a belief that a limited form of VRP would be useful >(essentially tracking if the FP value could have the value 0 and >perhaps >tracking NaNs as well). We're not likely to be tracking actual values, >but boolean states about what values an object may or may not have.
Sure. But they both handle integer constants. So factor that out of the VRP Workers. >I could also well see building another set of evaluation routines which >track zero, nonzero and unknown bits for integer values on top of the >basic framework Andrew is working on. > >To some degree symbolics feel the same in that I suspect that we most >often are going to want to work with them as expressions. I don't say you necessarily need to track symbolics and constants in the same lattice. But then you need to split it and I fear also allow cross-effects. >Which leads me to wonder if we really need to templateize all the new >code so that we can have a different storage for the ranges and >different ways to extract ranges from operations we see. > >Additionally, Andrew claims that handling symbolics really isn't needed >-- I'm still wrapping my head around all the implications of the >terminal names and how we can utilize them. > > >The more I think about the general desire to eliminate the range >extraction and propagation step from VRP and instead build on top of Huh, I never intended to do that. >this framework is going to require doing something with symbolics, >plain >and simple. We're not going to be able to remove those hunks of VRP if >we don't do *something* for symbolics. Indeed. >So I come back to the do we template-ize irange so that we get frange, >srange and possibly others, do we change the underlying storage to >trees, or do we have a polymorphic data structure that adjusts to the >integer, floating and symbolic handling? No. Have separate workers operating on Specific types. Like we have those for tracking one/zero bits in CCP. > >> >> irange is a nearly subset of what VRP can handle so it should be able >to re-use >> VRP workers. The 'nearly' part is that VRP currently doesn't handle >multiple >> ranges. For an unknown reason you didn't start with teaching VRP >that bit. >Perhaps, but the general belief is that VRP as we know it today >wouldn't >exist in this new world. Computation of range information would be >separate from utilizing range information for optimization/analysis >purposes. VRP is an optimization pass in itself and setting ranges on SSA names is only a secondary purpose. > > >One approach would be to take the existing bits from VRP and try to >pull >them out into its own little module, then extending it to allow the >kinds of queries we need to do. We felt it was actually going to be >better to start over, building a system to answer the queries we want >from the ground up. And probably repeat all wrong-code we eliminated from VRP... Also a separate pass always results in more test coverage than you'd get for (unused) infrastructure. >The belief is that what we're going to end up would replace huge >amounts >of VRP (eliminating ASSERT_EXPRs and anti-ranges along the way). I believe it when I see it. I've only seen some sketch of a range storage class so far. >> >> Yes, symbolic ranges complicate that conversion a bit (getting rid of >> anti-ranges >> in VRP) but you could have either kept anti-ranges for symbolic >ranges only >> or have open/closed ranges. The issue with symbolic ranges here is >that >> from >> >> if (a != b) >> >> we derive a symbolic range for a that is ~[b, b]. If you want to >make that >> a union of two ranges you have [MIN, b - 1] U [b + 1, MAX] _but_ both >> b - 1 or b + 1 might actually overflow! So you need to use [MIN, b[ >U ]b, MAX] >> here (which means both can be empty if b == MIN or b == MAX). >But how often is this useful in practice and how much are we willing to >pay to get this level of generality? I wonder if just the ability to >record simple symbolics and very simple manipulations is sufficient to >do what we need in practice. It's quite important to remove range checking code. Richard. > >Jeff
