Richard Biener <richard.guent...@gmail.com> writes: > On Thu, Aug 10, 2023 at 3:44 PM Richard Sandiford > <richard.sandif...@arm.com> wrote: >> >> 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. > > Though we have that available already in vec::, just need to > port that over to array_slice:: and use that from vec::?
array_slice was supposed to be a close approximation to std::span. I think it's more idiomatic to use the standard library on it, rather than adding our own custom substitutes (even if we can move the code from elsewhere). std::lower_bound supports lambdas, rather than needing to use the void * thing. Thanks, Richard