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.
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. 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 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. 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? > > 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. 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. 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). > > 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. Jeff
