On Wed, Aug 9, 2023 at 6:16 PM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> If `A` has a range of `[0,0][100,INF]` and the comparison
> of `A < 50`. This should be optimized to `A <= 0` (which then
> will be optimized to just `A == 0`).
> This patch implement this via a new function which sees if
> the constant of a comparison is in the middle of 2 range pairs
> and change the constant to the either upper bound of the first pair
> or the lower bound of the second pair depending on the comparison.
>
> This is the first step in fixing the following PRS:
> PR 110131, PR 108360, and PR 108397.
>
> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
> gcc/ChangeLog:
>
> * vr-values.cc (simplify_compare_using_range_pairs): New function.
> (simplify_using_ranges::simplify_compare_using_ranges_1): Call
> it.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/vrp124.c: New test.
> * gcc.dg/pr21643.c: Disable VRP.
> ---
> gcc/testsuite/gcc.dg/pr21643.c | 6 ++-
> gcc/testsuite/gcc.dg/tree-ssa/vrp124.c | 44 +++++++++++++++++
> gcc/vr-values.cc | 65 ++++++++++++++++++++++++++
> 3 files changed, 114 insertions(+), 1 deletion(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
>
> diff --git a/gcc/testsuite/gcc.dg/pr21643.c b/gcc/testsuite/gcc.dg/pr21643.c
> index 4e7f93d351a..7f121d7006f 100644
> --- a/gcc/testsuite/gcc.dg/pr21643.c
> +++ b/gcc/testsuite/gcc.dg/pr21643.c
> @@ -1,6 +1,10 @@
> /* PR tree-optimization/21643 */
> /* { dg-do compile } */
> -/* { dg-options "-O2 -fdump-tree-reassoc1-details --param
> logical-op-non-short-circuit=1" } */
> +/* Note VRP is able to transform `c >= 0x20` in f7
> + to `c >= 0x21` since we want to test
> + reassociation and not VRP, turn it off. */
> +
> +/* { dg-options "-O2 -fdump-tree-reassoc1-details --param
> logical-op-non-short-circuit=1 -fno-tree-vrp" } */
>
> int
> f1 (unsigned char c)
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
> b/gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
> new file mode 100644
> index 00000000000..6ccbda35d1b
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
> @@ -0,0 +1,44 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +/* Should be optimized to a == -100 */
> +int g(int a)
> +{
> + if (a == -100 || a >= 0)
> + ;
> + else
> + return 0;
> + return a < 0;
> +}
> +
> +/* Should optimize to a == 0 */
> +int f(int a)
> +{
> + if (a == 0 || a > 100)
> + ;
> + else
> + return 0;
> + return a < 50;
> +}
> +
> +/* Should be optimized to a == 0. */
> +int f2(int a)
> +{
> + if (a == 0 || a > 100)
> + ;
> + else
> + return 0;
> + return a < 100;
> +}
> +
> +/* Should optimize to a == 100 */
> +int f1(int a)
> +{
> + if (a < 0 || a == 100)
> + ;
> + else
> + return 0;
> + return a > 50;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */
> diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
> index a4fddd62841..1262e7cf9f0 100644
> --- a/gcc/vr-values.cc
> +++ b/gcc/vr-values.cc
> @@ -968,9 +968,72 @@ test_for_singularity (enum tree_code cond_code, tree op0,
> if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
> return min;
> }
> +
> return NULL;
> }
>
> +/* Simplify integer comparisons such that the constant is one of the range
> pairs.
> + For an example,
> + A has a range of [0,0][100,INF]
> + and the comparison of `A < 50`.
> + This should be optimized to `A <= 0`
> + and then test_for_singularity can optimize it to `A == 0`. */
> +
> +static bool
> +simplify_compare_using_range_pairs (tree_code &cond_code, tree &op0, tree
> &op1,
> + const value_range *vr)
> +{
> + if (TREE_CODE (op1) != INTEGER_CST
> + || vr->num_pairs () < 2)
> + return false;
> + auto val_op1 = wi::to_wide (op1);
> + tree type = TREE_TYPE (op0);
> + auto sign = TYPE_SIGN (type);
> + auto p = vr->num_pairs ();
> + /* Find the value range pair where op1
> + is in the middle of if one exist. */
> + for (unsigned i = 1; i < p; i++)
> + {
> + auto lower = vr->upper_bound (i - 1);
> + auto upper = vr->lower_bound (i);
> + if (wi::lt_p (val_op1, lower, sign))
> + continue;
> + if (wi::gt_p (val_op1, upper, sign))
> + continue;
That looks like a linear search - it looks like m_base[] is
a sorted array of values so we should be able to
binary search here? array_slice::bsearch could be
used if it existed (simply port it over from vec<> and
use array_slice from that)?
In the linear search above I'm missing an earlier out
if op1 falls inside a sub-range, you seem to walk the whole
array?
When is this transform profitable on its own and why would
it enable followup simplifications? The example you quote
is for turning the compare into a compare with zero which
is usually cheap but this case would also be easy to special
case. Transforming to an equality test in the end enables
conditional constant propagation, so that's another thing but
any other case should point out missed secondary opportunities
in ranger?
Thanks,
Richard.
> + if (cond_code == LT_EXPR
> + && val_op1 != lower)
> + {
> + op1 = wide_int_to_tree (type, lower);
> + cond_code = LE_EXPR;
> + return true;
> + }
> + if (cond_code == LE_EXPR
> + && val_op1 != upper
> + && val_op1 != lower)
> + {
> + op1 = wide_int_to_tree (type, lower);
> + cond_code = LE_EXPR;
> + return true;
> + }
> + if (cond_code == GT_EXPR
> + && val_op1 != upper)
> + {
> + op1 = wide_int_to_tree (type, upper);
> + cond_code = GE_EXPR;
> + return true;
> + }
> + if (cond_code == GE_EXPR
> + && val_op1 != lower
> + && val_op1 != upper)
> + {
> + op1 = wide_int_to_tree (type, upper);
> + cond_code = GE_EXPR;
> + return true;
> + }
> + }
> + return false;
> +}
> +
> /* Return whether the value range *VR fits in an integer type specified
> by PRECISION and UNSIGNED_P. */
>
> @@ -1235,6 +1298,8 @@ simplify_using_ranges::simplify_compare_using_ranges_1
> (tree_code &cond_code, tr
> able to simplify this conditional. */
> if (!vr.undefined_p () && !vr.varying_p ())
> {
> + if (simplify_compare_using_range_pairs (cond_code, op0, op1, &vr))
> + happened = true;
> tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
> if (new_tree)
> {
> --
> 2.31.1
>
