* [PATCH] recognize implied ranges for modulo.
@ 2020-11-17 22:01 Andrew MacLeod
2020-11-18 8:35 ` Aldy Hernandez
0 siblings, 1 reply; 3+ messages in thread
From: Andrew MacLeod @ 2020-11-17 22:01 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 519 bytes --]
PR 91029 observes when
a % b > 0 && b >= 0,
then a has an implied range of a >=0. likewise
a % b < 0 implies a range of a <= 0.
This patch is a good example of how range-ops can be leveraged to solve
problems. It simply implements operator_trunc_mod::op1_range() to solve
for 'A' when the LHS and 'b' are known to be within the specified
ranges. I also added a a test case to show folding of conditions
based on that.
Bootstrapped on x86_64-pc-linux-gnu, no regressions. pushed.
Andrew
[-- Attachment #2: mod.diff --]
[-- Type: text/x-patch, Size: 2583 bytes --]
commit 1e27e7a582a9b86bcf86f5c103cd947672746e97
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Tue Nov 17 14:47:58 2020 -0500
recognize implied ranges for modulo.
implement op1_range for modulo with implied positive and negative ranges.
gcc/
PR tree-optimization/91029
* range-op.cc (operator_trunc_mod::op1_range): New.
gcc/testsuite/
* gcc.dg/pr91029.c: New.
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index d0adc95527a..f37796cac70 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -2634,6 +2634,9 @@ public:
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_trunc_mod;
void
@@ -2680,6 +2683,31 @@ operator_trunc_mod::wi_fold (irange &r, tree type,
value_range_with_overflow (r, type, new_lb, new_ub);
}
+bool
+operator_trunc_mod::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ // PR 91029. Check for signed truncation with op2 >= 0.
+ if (TYPE_SIGN (type) == SIGNED && wi::ge_p (op2.lower_bound (), 0, SIGNED))
+ {
+ unsigned prec = TYPE_PRECISION (type);
+ // if a & b >=0 , then a >= 0.
+ if (wi::ge_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;
+ }
+ }
+ return false;
+}
+
class operator_logical_not : public range_operator
{
diff --git a/gcc/testsuite/gcc.dg/pr91029.c b/gcc/testsuite/gcc.dg/pr91029.c
new file mode 100644
index 00000000000..8a4134c5d96
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr91029.c
@@ -0,0 +1,47 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+void kill (void);
+int xx;
+
+void f1 (int i)
+{
+ if ((i % 7) == 3)
+ {
+ xx = (i < 0);
+ if (xx)
+ kill ();
+ }
+}
+
+void f2 (int i)
+{
+ if ((i % 7) >= 0)
+ {
+ xx = (i < 0);
+ if (xx)
+ kill ();
+ }
+}
+
+void f3 (int i)
+{
+ if ((i % 7) == -3)
+ {
+ xx = (i > 0);
+ if (xx)
+ kill ();
+ }
+}
+
+void f4 (int i)
+{
+ if ((i % 7) < 0)
+ {
+ xx = (i > 0);
+ if (xx)
+ kill ();
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] recognize implied ranges for modulo.
2020-11-17 22:01 [PATCH] recognize implied ranges for modulo Andrew MacLeod
@ 2020-11-18 8:35 ` Aldy Hernandez
2020-11-18 14:22 ` Andrew MacLeod
0 siblings, 1 reply; 3+ messages in thread
From: Aldy Hernandez @ 2020-11-18 8:35 UTC (permalink / raw)
To: Andrew MacLeod, gcc-patches
On 11/17/20 11:01 PM, Andrew MacLeod wrote:
> PR 91029 observes when
>
> a % b > 0 && b >= 0,
>
> then a has an implied range of a >=0. likewise
Shouldn't that be && b > 0? b == 0 is undefined.
>
> a % b < 0 implies a range of a <= 0.
>
> This patch is a good example of how range-ops can be leveraged to solve
> problems. It simply implements operator_trunc_mod::op1_range() to solve
> for 'A' when the LHS and 'b' are known to be within the specified
> ranges. I also added a a test case to show folding of conditions
> based on that.
>
> Bootstrapped on x86_64-pc-linux-gnu, no regressions. pushed.
>
> Andrew
> diff --git a/gcc/range-op.cc b/gcc/range-op.cc
> index d0adc95527a..f37796cac70 100644
> --- a/gcc/range-op.cc
> +++ b/gcc/range-op.cc
> @@ -2634,6 +2634,9 @@ public:
> const wide_int &lh_ub,
> const wide_int &rh_lb,
> const wide_int &rh_ub) const;
> + virtual bool op1_range (irange &r, tree type,
> + const irange &lhs,
> + const irange &op2) const;
> } op_trunc_mod;
>
> void
> @@ -2680,6 +2683,31 @@ operator_trunc_mod::wi_fold (irange &r, tree type,
> value_range_with_overflow (r, type, new_lb, new_ub);
> }
>
> +bool
> +operator_trunc_mod::op1_range (irange &r, tree type,
> + const irange &lhs,
> + const irange &op2) const
> +{
> + // PR 91029. Check for signed truncation with op2 >= 0.
> + if (TYPE_SIGN (type) == SIGNED && wi::ge_p (op2.lower_bound (), 0, SIGNED))
> + {
> + unsigned prec = TYPE_PRECISION (type);
> + // if a & b >=0 , then a >= 0.
Shouldn't comment be %, not & ??.
> + if (wi::ge_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.
Similarly here.
> + if (wi::lt_p (lhs.upper_bound (), 0, SIGNED))
> + {
> + r = value_range (type, wi::min_value (prec, SIGNED), wi::zero (prec));
> + return true;
> + }
> + }
> + return false;
> +}
> +
>
Thanks for doing this BTW.
Aldy
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] recognize implied ranges for modulo.
2020-11-18 8:35 ` Aldy Hernandez
@ 2020-11-18 14:22 ` Andrew MacLeod
0 siblings, 0 replies; 3+ messages in thread
From: Andrew MacLeod @ 2020-11-18 14:22 UTC (permalink / raw)
To: Aldy Hernandez, gcc-patches
On 11/18/20 3:35 AM, Aldy Hernandez wrote:
>
>
> On 11/17/20 11:01 PM, Andrew MacLeod wrote:
>> PR 91029 observes when
>>
>> a % b > 0 && b >= 0,
>>
>> then a has an implied range of a >=0. likewise
>
> Shouldn't that be && b > 0? b == 0 is undefined.
>
>
If you were folding, sure, but I think its OK for equation solving..
whats important is that b is not negative.
I can easily imagine having a positive LHS and an unknown unsigned
value for b.. we could still conclude that 'a' is positive even though
0 is in the "possible ranges" for 'b'
Andrew
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-11-18 14:22 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-11-17 22:01 [PATCH] recognize implied ranges for modulo Andrew MacLeod
2020-11-18 8:35 ` Aldy Hernandez
2020-11-18 14:22 ` Andrew MacLeod
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).