From d3f293348768667c07770e433ff00af51fee73a2 Mon Sep 17 00:00:00 2001 From: Jakub Jelinek Date: Fri, 20 Nov 2020 00:02:21 +0100 Subject: [PATCH] ranger: Improve a % b operand ranges [PR91029] As mentioned in the PR, the previous PR91029 patch was testing op2 >= 0 which is unnecessary, even negative op2 values will work the same, furthermore, from if a % b > 0 we can deduce a > 0 rather than just a >= 0 (0 % b would be 0), and it actually valid even for other constants than 0, a % b > 5 means a > 5 (a % b has the same sign as a and a in [0, 5] would result in a % b in [0, 5]. Also, we can deduce a range for the other operand, if we know a % b >= 20, then b must be (in absolute value for signed modulo) > 20, for a % [0, 20] the result would be [0, 19]. 2020-11-19 Jakub Jelinek PR tree-optimization/91029 * range-op.cc (operator_trunc_mod::op1_range): Don't require signed types, nor require that op2 >= 0. Implement (a % b) >= x && x > 0 implies a >= x and (a % b) <= x && x < 0 implies a <= x. (operator_trunc_mod::op2_range): New method. * gcc.dg/tree-ssa/pr91029-1.c: New test. * gcc.dg/tree-ssa/pr91029-2.c: New test. --- gcc/range-op.cc | 69 ++++++++++++---- gcc/testsuite/gcc.dg/tree-ssa/pr91029-1.c | 68 ++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr91029-2.c | 98 +++++++++++++++++++++++ 3 files changed, 219 insertions(+), 16 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr91029-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr91029-2.c diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 5bf37e1ad82..36f9fd66cb3 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -2645,6 +2645,9 @@ public: virtual bool op1_range (irange &r, tree type, const irange &lhs, const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_trunc_mod; void @@ -2694,24 +2697,58 @@ operator_trunc_mod::wi_fold (irange &r, tree type, bool operator_trunc_mod::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &) const { - // PR 91029. Check for signed truncation with op2 >= 0. - if (TYPE_SIGN (type) == SIGNED && wi::ge_p (op2.lower_bound (), 0, SIGNED)) + // PR 91029. + signop sign = TYPE_SIGN (type); + unsigned prec = TYPE_PRECISION (type); + // (a % b) >= x && x > 0 , then a >= x. + if (wi::gt_p (lhs.lower_bound (), 0, sign)) { - unsigned prec = TYPE_PRECISION (type); - // if a % b > 0 , then a >= 0. - if (wi::gt_p (lhs.lower_bound (), 0, SIGNED)) - { - r = value_range (type, wi::zero (prec), wi::max_value (prec, SIGNED)); - return true; - } - // if a % b < 0 , then a <= 0. - if (wi::lt_p (lhs.upper_bound (), 0, SIGNED)) - { - r = value_range (type, wi::min_value (prec, SIGNED), wi::zero (prec)); - return true; - } + r = value_range (type, lhs.lower_bound (), wi::max_value (prec, sign)); + return true; + } + // (a % b) <= x && x < 0 , then a <= x. + if (wi::lt_p (lhs.upper_bound (), 0, sign)) + { + r = value_range (type, wi::min_value (prec, sign), lhs.upper_bound ()); + return true; + } + return false; +} + +bool +operator_trunc_mod::op2_range (irange &r, tree type, + const irange &lhs, + const irange &) const +{ + // PR 91029. + signop sign = TYPE_SIGN (type); + unsigned prec = TYPE_PRECISION (type); + // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed + // or b > x for unsigned. + if (wi::gt_p (lhs.lower_bound (), 0, sign)) + { + if (sign == SIGNED) + r = value_range (type, wi::neg (lhs.lower_bound ()), + lhs.lower_bound (), VR_ANTI_RANGE); + else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign), + sign)) + r = value_range (type, lhs.lower_bound () + 1, + wi::max_value (prec, sign)); + else + return false; + return true; + } + // (a % b) <= x && x < 0 , then b is in ~[x, -x]. + if (wi::lt_p (lhs.upper_bound (), 0, sign)) + { + if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign)) + r = value_range (type, lhs.upper_bound (), + wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE); + else + return false; + return true; } return false; } diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr91029-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr91029-1.c new file mode 100644 index 00000000000..d52734b20f9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr91029-1.c @@ -0,0 +1,68 @@ +/* PR tree-optimization/91029 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void kill (void); +int xx; + +void f1 (int i, int j) +{ + if ((i % j) == 3) + { + xx = (i < 3); + if (xx) + kill (); + } +} + +void f2 (int i, int j) +{ + if ((i % j) > 0) + { + xx = (i <= 0); + if (xx) + kill (); + } +} + +void f3 (int i, int j) +{ + if ((i % j) == -3) + { + xx = (i > -3); + if (xx) + kill (); + } +} + +void f4 (int i, int j) +{ + if ((i % j) < 0) + { + xx = (i >= 0); + if (xx) + kill (); + } +} + +void f5 (int i, int j) +{ + if ((i % j) > 42) + { + xx = (i <= 42); + if (xx) + kill (); + } +} + +void f6 (int i, int j) +{ + if ((i % j) < -124) + { + xx = (i >= -124); + if (xx) + kill (); + } +} + +/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr91029-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr91029-2.c new file mode 100644 index 00000000000..ad9213a41b7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr91029-2.c @@ -0,0 +1,98 @@ +/* PR tree-optimization/91029 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void kill (void); +int xx; + +void f1 (int i, int j) +{ + if ((i % j) == 3) + { + xx = (j <= 3 && j >= -3); + if (xx) + kill (); + } +} + +void f2 (int i, int j) +{ + if ((i % j) > 0) + { + xx = (j <= 1 && j >= -1); + if (xx) + kill (); + } +} + +void f3 (int i, int j) +{ + if ((i % j) == -3) + { + xx = (j <= 3 && j >= -3); + if (xx) + kill (); + } +} + +void f4 (int i, int j) +{ + if ((i % j) < 0) + { + xx = (j <= 1 && j >= -1); + if (xx) + kill (); + } +} + +void f5 (int i, int j) +{ + if ((i % j) > 42) + { + xx = (j <= 43 && j >= -43); + if (xx) + kill (); + } +} + +void f6 (int i, int j) +{ + if ((i % j) < -124) + { + xx = (j <= 125 && j >= -125); + if (xx) + kill (); + } +} + +void f7 (unsigned int i, unsigned int j) +{ + if ((i % j) == 3) + { + xx = (j <= 3); + if (xx) + kill (); + } +} + +void f8 (unsigned int i, unsigned int j) +{ + if ((i % j) > 0) + { + xx = (j <= 1); + if (xx) + kill (); + } +} + +void f9 (unsigned int i, unsigned int j) +{ + if ((i % j) >= 124) + { + xx = (j <= 124); + if (xx) + kill (); + } +} + +/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */ -- 2.30.2