Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
> 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)?
Better to use std::lower_bound IMO, rather than implement our
own custom bsearch.
Thanks,
Richard
