[Bug tree-optimization/91789] New: Value ranges determined from comparisons not used transitively

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[Bug tree-optimization/91789] New: Value ranges determined from comparisons not used transitively

jason at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91789

            Bug ID: 91789
           Summary: Value ranges determined from comparisons not used
                    transitively
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: drepper.fsp+rhbz at gmail dot com
  Target Milestone: ---

Take the following code:

int foo(int a, int b)
{
  if (b < a)
    __builtin_unreachable();
  if (a < 0)
    return -1;
  if (b < 0)
    return 0;
  return 1;
}

The compiler should be able to determine that the b < 0 can never be true.  At
that point in the code a >= 0 and b >= a, therefore transitively b >= 0.


The problem is not tied to __builtin_unreachable as can be seen by changing the
code slightly:

int foo(int a, int b)
{
  if (b < a)
    return 2;
  if (a < 0)
    return -1;
  if (b < 0)
    return 0;
  return 1;
}

After the initial test b < a is handled there is still a threeway comparison.

The problem can be seen with 9.2.1 as well as the current trunk version.  clang
8.0.0 generates pretty much the same code as gcc.
Reply | Threaded
Open this post in threaded view
|

[Bug tree-optimization/91789] Value ranges determined from comparisons not used transitively

jason at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91789

Eric Gallager <egallager at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
                 CC|                            |egallager at gcc dot gnu.org
             Blocks|                            |85316

--- Comment #1 from Eric Gallager <egallager at gcc dot gnu.org> ---
If I understood the "Project Ranger" talk at Cauldron correctly, the new
version of VRP that it'll provide will probably fix this.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85316
[Bug 85316] [meta-bug] VRP range propagation missed cases
Reply | Threaded
Open this post in threaded view
|

[Bug tree-optimization/91789] Value ranges determined from comparisons not used transitively

jason at gcc dot gnu.org
In reply to this post by jason at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91789

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
We do manage if you swap the order of the first 2 comparisons, because this way
we don't need to remember symbolic ranges: a<0 yields a range [0,inf] for a,
b<a yields [0,inf] for b, and b<0 folds to false.
If ranger "fixes" this by working backwards, please make sure it works with
both orders.
Reply | Threaded
Open this post in threaded view
|

[Bug tree-optimization/91789] Value ranges determined from comparisons not used transitively

jason at gcc dot gnu.org
In reply to this post by jason at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91789

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2019-09-17
     Ever confirmed|0                           |1

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So EVRP sees

Visiting controlling predicate if (a_3(D) < 0)
Adding assert for a_3(D) from a_3(D) >= 0
Intersecting
  int [0, +INF]  EQUIVALENCES: { a_3(D) } (1 elements)
and
  int [-INF, b_2(D)]  EQUIVALENCES: { a_3(D) } (1 elements)
to
  int [0, +INF]  EQUIVALENCES: { a_3(D) } (1 elements)
Intersecting
  int [-INF, b_2(D)]
and
  int [0, +INF]
to
  int [-INF, b_2(D)]

where the intersection could produce [0, b_2(D)] with the twist
that this range might be empty in case b_2(D) < 0.

The issue in the intersection routine is that we use predicates like

  else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
           && (mineq || operand_less_p (*vr0min, vr1min) == 1))

when we mean less-or-equal but for symbolic values with
maxeq = vrp_operand_equal_p (*vr0max, vr1max) this isn't the same.

compare_values could in theory represent this (but it doesn't).

IMHO this has nothing to do with "backward" or "forward" processing
but simply with how combination of the predicates/ranges works.
Reply | Threaded
Open this post in threaded view
|

[Bug tree-optimization/91789] Value ranges determined from comparisons not used transitively

jason at gcc dot gnu.org
In reply to this post by jason at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91789

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
The ranger isn't really about forwards vs backwards, its about an approach in
which the basics are understood without special casing, and when applied
properly, direction won't matter... eliminating this sort of ordering issue.

This is another example which we intend to just always "get", but requires
multiple components to work together:

It requires 2 different things.
1) ranges to know that after the second conditional a = [0, MAX]
2) relationals such that the property b >= a is known after the first
conditional.

- For strictly ranges, the final conditional produces b = [MIN, -1] on the TRUE
edge.
- If the known relations are queried, and the known relation b >= a is applied
to a = [0, MAX], rangeops calculates b >= [0, MAX] and we get a range of [0,
MAX] for b

Since both must be true simultaneously, the results [MIN, -1] and [0, MAX] will
be intersected and produces an empty range on the TRUE edge, which in ranger
world means the range is impossible. Thus we know the edge is not executable
and can be removed.

This range evaluation code is present in the ranger now and resolves the range
parts, but wont make trunk this release.  

The relational code is being developed for next stage 1, so does not exist yet.
It is required to replace VRP and the symbolic representation currently used by
value_range for equivalences and relations. This will be my focus over the next
few months.

I would anticipate this being fixed in the next release when the ranger goes
live. I will add this test to my testsuite to ensure it works as expected.