[Bug tree-optimization/110199] New: [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[Bug tree-optimization/110199] New: [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

            Bug ID: 110199
           Summary: [12/13/14 Regression] Missing VRP transformation with
                    MIN_EXPR and known relation
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pinskia at gcc dot gnu.org
  Target Milestone: ---

Take:
```
int test(int a, int b)
{
    if (a <= b)
        return a < b ? a : b;
    return 0;
}
```
This used to be optimized in GCC 11 and before via EVRP:

pushing new range for b_3(D): int [a_2(D), +INF]  EQUIVALENCES: { b_3(D) } (1
elements)
evrp visiting stmt _5 = MIN_EXPR <a_2(D), b_3(D)>;

extract_range_from_stmt visiting:
_5 = MIN_EXPR <a_2(D), b_3(D)>;
Intersecting
  int VARYING
and
  int VARYING
to
  int VARYING
Folding statement: _5 = MIN_EXPR <a_2(D), b_3(D)>;
Folded into: _5 = a_2(D);


But in GCC 12 and above it is missed:
Folding statement: _5 = MIN_EXPR <a_2(D), b_3(D)>;
 folding with relation a_2(D) <= b_3(D)
Not folded

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.4

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I suspect this was moving over to ranger and somehow this transformation was
lost (maybe due to a missing testcase?)

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I Kinda see how to implement this by creating
operator_min::fold_range/operator_max::fold_range but I am still new on using
these interfaces so I am not 100% sure how to use them.

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Andrew Pinski from comment #2)
> I Kinda see how to implement this by creating
> operator_min::fold_range/operator_max::fold_range but I am still new on
> using these interfaces so I am not 100% sure how to use them.

Actually, on ranger, we'd be able to make the range choice of the range of a_2
or b_3, but it can't rewrite the IL...  and since the range of both is varying,
fold_range would still return varying.  Unless we indicate there are relations.
 fodl_range itself only takes what it is given, so we have to query the
relations first. 

In theory all that is missing is to teach simplification about relation
queries. For instance, in simplify_using_ranges::fold_cond_with_ops, we are
invoking the range-op handler without any relations.. we query the ranges, but
not the relation. If we add something like this (and make sure both operands
are symbolic)

diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
index ecb294131b0..ad2c2d6c090 100644
--- a/gcc/vr-values.cc
+++ b/gcc/vr-values.cc
@@ -315,10 +315,17 @@ simplify_using_ranges::fold_cond_with_ops (enum tree_code
code,
       || !query->range_of_expr (r1, op1, s))
     return NULL_TREE;

+  relation_kind rel = VREL_VARYING;
+  if (gimple_range_ssa_p (op0) && gimple_range_ssa_p (op1))
+    rel = query->query_relation (s, op0, op1);
+  // Create a trio with the relation set between op0 and op2 for folding.
+  // TRIOS are lhs-op0, lhs-op1, op0-op1 relations.
+  relation_trio trio (VREL_VARYING, VREL_VARYING, rel);
+
   tree type = TREE_TYPE (op0);
   int_range<1> res;
   range_op_handler handler (code);
-  if (handler && handler.fold_range (res, type, r0, r1))
+  if (handler && handler.fold_range (res, type, r0, r1, trio))
     {
       if (res == range_true (type))
        return boolean_true_node;

This should do what you want I think...   fold_range should use the relation
passed in to determine that the condition is always true or false.

I have not fully tested this patch, fwiw.

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Just looking at the generated code of #c0 with -O2 on x86_64, this regressed
with
r13-3596-ge7310e24b1c0ca67b1bb507c1330b2bf39e59e32
Andrew, are you going to address this for GCC 14, or defer to GCC 15?

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Jakub Jelinek from comment #4)
> Just looking at the generated code of #c0 with -O2 on x86_64, this regressed
> with
> r13-3596-ge7310e24b1c0ca67b1bb507c1330b2bf39e59e32
> Andrew, are you going to address this for GCC 14, or defer to GCC 15?

Id prefer to defer it I think. Although we can run that thru the testings if
anyone really wants it. 

Maybe in GCC 15 someone can add relations in general to simplifications

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[law at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |law at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2024-03-07
                 CC|                            |law at gcc dot gnu.org

--- Comment #6 from Jeffrey A. Law <law at gcc dot gnu.org> ---
I think this is trivial to do in DOM and not handling these cases could easily
be seen as an oversight.

When we fail to find an expression in the hash table of available expressions,
we have a bit of existing code that can ask about a relation between two
operands of a binary operator and based on that relation possibly simplify the
original expression.

So for example, if we have:

 _4 = MIN_EXPR <a_2(D), b_3(D)>;

And the MIN_EXPR expression isn't in the hash table, we look to see if we have
recorded a_2 == b_3 and if so we simplify the MIN_EXPR into a copy.

So this is just a matter of extending that code ever so slightly to do an
additional lookup.

[Bug tree-optimization/110199] [12/13/14 Regression] Missing VRP transformation with MIN_EXPR and known relation

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110199

--- Comment #7 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jeff Law <law@gcc.gnu.org>:

https://gcc.gnu.org/g:8fe27ed193d60f6cd8b34761858a720c95eabbdb

commit r14-9419-g8fe27ed193d60f6cd8b34761858a720c95eabbdb
Author: jlaw <jeffreyalaw@gmail.com>
Date:   Sun Mar 10 11:58:00 2024 -0600

    [committed] [PR tree-optimization/110199] Simplify MIN/MAX more often

    So as I mentioned in the BZ, the case of

    t = MIN_EXPR (A, B)

    where we know something about the relationship between A and B can be
trivially
    handled by some existing code in DOM.  That existing code would simplify
when A
    == B.  But by testing GE and LE instead of EQ we can cover more cases with
    minimal effort.  When applicable the MIN/MAX turns into a simple copy.

    I made one other change.  We have other binary operations that we simplify
when
    we know something about the relationship between the operands.  That code
was
    not canonicalizing the order of operands when building the expression to
lookup
    in the hash tables to discover that relationship.  Since those paths are
only
    testing for equality, we can trivially reverse them and not have to worry
about
    changing codes or anything like that.  So extremely safe and avoids having
to
    come back and fix that code to match the MIN_EXPR/MAX_EXPR case later.

    Bootstrapped on x86 and also tested on the crosses.  I briefly thought
there
    was an sh regression, but that was actually the recent fwprop changes
twiddling
    code generation for one test.

            PR tree-optimization/110199
    gcc/
            * tree-ssa-scopedtables.cc
            (avail_exprs_stack::simplify_binary_operation): Generalize handling
            of MIN_EXPR/MAX_EXPR to allow additional simplifications. 
Canonicalize
            comparison operands for other cases.

    gcc/testsuite

            * gcc.dg/tree-ssa/minmax-27.c: New test.
            * gcc.dg/tree-ssa/minmax-28.c: New test.