Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Marc Glisse <marc dot glisse at inria dot fr>]

On Mon, 13 Feb 2017, Jeff Law wrote:

> On 02/13/2017 09:15 AM, Marc Glisse wrote:
> > On Mon, 13 Feb 2017, Jeff Law wrote:
> >
> > > On 02/12/2017 12:13 AM, Marc Glisse wrote:
> > > > On Tue, 7 Feb 2017, Jeff Law wrote:
> > > >
> > > > > * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
> > > > > if the numerator has the range ~[0,0] make the resultant range ~[0,0].
> > > >
> > > > If I understand correctly, for x /[ex] 4 with x!=0, we currently split
> > > > ~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
> > > > which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
> > > > union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
> > > > could change the union function, but this patch prefers changing the
> > > > code elsewhere so that the new behavior is restricted to the
> > > > EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
> > > > a new non-contiguous version of ranges, where union would already work).
> > > > Is that it?
> > > That was one of alternate approaches I suggested.
> > >
> > > Part of the problem is the conversion of ~[0,0] is imprecise when it's
> > > going to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the
> > > thread.  As a result of that imprecision, the ranges we get are
> > > [INT_MIN/4,0] U [0,INT_MAX/4].
> >
> > If VRP for [1, INT_MAX] /[ex] 4 produces [0, INT_MAX/4] instead of [1,
> > INT_MAX/4], that's a bug that should be fixed in any case. You shouldn't
> > need [4, INT_MAX] for that.
> Agreed.  But given it doesn't actually make anything around 79095 easier, I'd 
> just assume defer to gcc-8.

That all depends how you handle the intersection/union thing.

> I suspect that we'll see nicely refined anti-ranges, but rarely see 
> improvements in the generated code.
>
> > > If we fix that imprecision so that the conversion yields [INT_MIN,-4]
> > > U [4, INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U
> > > [1,INT_MAX/4], which union_ranges turns into [INT_MIN/4,INT_MAX/4].
> > > We still end up needing a hack in union_ranges that will look a hell
> > > of a lot like the one we're contemplating for intersect_ranges.
> >
> > That was the point of my question. Do we want to put that "hack" (prefer
> > an anti-range in some cases) in a central place where it would apply any
> > time we try to replace [a,b]U[c,d] (b+1<c) with a single range (and
> > where it would naturally disappear when we start allowing multiple
> > ranges), or do we prefer to put it in the few odd places where we have
> > reason to believe that it will help, while the usual strategy (produce
> > [a,d]) remains preferable in general? From your patch it seems to be the
> > later case, which makes sense.
> I suspect we'll still need both.  The code to prefer ~[0,0] when intersecting 
> ranges likely needs to stay regardless of other improvements we make to 
> EXACT_DIV_EXPR.
>
> This is because we have to produce a wide range, including zero during vrp1 
> and it's only during vrp2 that we can exclude zero.  Thus no matter what we 
> do, we end up in intersect_ranges and have to make a guess about whether to 
> prefer the wide range of anti-singleton range of ~[0,0].

In the cases where intersect_ranges (with at least one anti-range) ends up 
with a union [a,b]U[c,d] with b+1<c, it could call union_ranges (or they 
could both call the same helper), and we would have all the logic in a 
single place to decide whether we want [a,d] or ~[b+1,c-1]. When we move 
to multiple range components, an interesting place will be the heuristics 
to go down from n components to 3 (or whatever number we pick), trying to 
preserve the largest holes, the hole containing 0 if there is one, the 
holes with numbers of small magnitude, etc.

In my opinion, having the logic in a non-central place like 
extract_range_from_binary_expr_1 makes sense if we want a different 
heuristic for this case than the general case. If the heuristic is 
duplicated in a central place like vrp_intersect, that's probably not the 
case, so I'd favor having the logic in exactly one place.

(I am not asking you to change anything, just discussing some 
possibilities)

--
Marc Glisse