* [PATCH] PR tree-optimization/31178 - Add rshift side effect.
@ 2022-05-17 18:39 Andrew MacLeod
2022-05-18 6:41 ` Richard Biener
0 siblings, 1 reply; 4+ messages in thread
From: Andrew MacLeod @ 2022-05-17 18:39 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 769 bytes --]
This patch implements side effects of the second operand of a shift
operation.
given A >> B or A << B, the range of B is restricted to [0, PRECISION_A).
Fortran is currently more permissive than this, allowing the range to be
[0, PRECISION_A], so this si the value we currently default to in this
patch. If the fortran front end were adjusted, we could adjust the end
point.
This currently bootstraps with no regressions on x86_64-pc-linux-gnu.
Is this sufficient, or should I also be checking some other flags which
may allow other values outside this range to be valid?
Andrew
PS. Note that in the testcase, one of the tests is currently disabled
as full recomputation of side-effects is not quite in place yet. WHen ti
is, I will enable the test.
[-- Attachment #2: rshift.diff --]
[-- Type: text/x-patch, Size: 3004 bytes --]
commit e283395a570328874d3215893c7781fd2770d87f
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Mon Apr 4 16:26:15 2022 -0400
Add rshift side effect.
After a shift operation, we can make deductions about the bounds of the shift
value based on the precision of the value being shifted.
Fortran is currently more permissive than the other front ends, so we set the
range of B in A >> B to [0, PRECISION_A] rather than [0, PRECISION_A) that the
other front ends require.
gcc/
PR tree-optimization/31178
* gimple-range-side-effect.cc (stmt_side_effects::stmt_side_effects):
Add suport for LSHIFT_EXPR and RSHIFT_EXPR.
gcc/testsuite/
* gcc.dg/tree-ssa/pr31178.c: New.
diff --git a/gcc/gimple-range-side-effect.cc b/gcc/gimple-range-side-effect.cc
index 548e4bea313..fdd5fdc296d 100644
--- a/gcc/gimple-range-side-effect.cc
+++ b/gcc/gimple-range-side-effect.cc
@@ -34,6 +34,7 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "gimple-walk.h"
#include "cfganal.h"
+#include "stor-layout.h" // for element_precision()
// Adapted from infer_nonnull_range_by_dereference and check_loadstore
// to process nonnull ssa_name OP in S. DATA contains a pointer to a
@@ -129,6 +130,22 @@ stmt_side_effects::stmt_side_effects (gimple *s)
if (gimple_range_ssa_p (gimple_assign_rhs2 (s)))
add_nonzero (gimple_assign_rhs2 (s));
break;
+
+ case LSHIFT_EXPR:
+ case RSHIFT_EXPR:
+ if (gimple_range_ssa_p (gimple_assign_rhs2 (s)))
+ {
+ // A << B, A >>B implies [0, PRECISION_of_A)
+ tree op1_type = TREE_TYPE (gimple_assign_rhs1 (s));
+ tree op2_type = TREE_TYPE (gimple_assign_rhs2 (s));
+ tree l = build_int_cst (op2_type, 0);
+ // C is [0, N), but fortran is [0, N], so default to [0, N].
+ tree u = build_int_cst (op2_type, element_precision (op1_type));
+ int_range_max shift (l, u);
+ add_range (gimple_assign_rhs2 (s), shift);
+ }
+ break;
+
default:
break;
}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr31178.c b/gcc/testsuite/gcc.dg/tree-ssa/pr31178.c
new file mode 100644
index 00000000000..27c72fb7104
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr31178.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp " } */
+
+/* Side effects of divide are that the divisor cannot be 0. */
+
+#include "limits.h"
+void dead (int);
+
+void
+f1 (int a, int c) {
+ int b = a;
+ if ((a << c) > 100)
+ b = c;
+
+ // Fortran allows [0, sizeof(int)] , so that is GCC default for now.
+ if (c < 0 || c > sizeof(int) * CHAR_BIT)
+ dead (b);
+}
+
+#if 0
+/* Until we get recomputation of a side effect value working, ... */
+
+int
+f2 (int a, int c) {
+ int nz = (c < 0 || c > sizeof(int) * CHAR_BIT);
+ int b = a >> c;
+ if (nz)
+ dead (0);
+ return b;
+}
+#endif
+
+/* { dg-final { scan-tree-dump-not "dead" "evrp" } } */
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] PR tree-optimization/31178 - Add rshift side effect.
2022-05-17 18:39 [PATCH] PR tree-optimization/31178 - Add rshift side effect Andrew MacLeod
@ 2022-05-18 6:41 ` Richard Biener
2022-05-18 13:15 ` Andrew MacLeod
0 siblings, 1 reply; 4+ messages in thread
From: Richard Biener @ 2022-05-18 6:41 UTC (permalink / raw)
To: Andrew MacLeod, Jakub Jelinek; +Cc: gcc-patches
On Tue, May 17, 2022 at 8:41 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This patch implements side effects of the second operand of a shift
> operation.
>
> given A >> B or A << B, the range of B is restricted to [0, PRECISION_A).
>
> Fortran is currently more permissive than this, allowing the range to be
> [0, PRECISION_A], so this si the value we currently default to in this
> patch. If the fortran front end were adjusted, we could adjust the end
> point.
>
> This currently bootstraps with no regressions on x86_64-pc-linux-gnu.
>
> Is this sufficient, or should I also be checking some other flags which
> may allow other values outside this range to be valid?
I think the "undefined behavior" side-effects are dangerous since
I know of no code that makes sure to clamp the shift argument when
hoisting it. sanitizing shifts will also not help to discover such latent
issues since sanitizing is happening early and it will most definitely
avoid the hoisting itself.
As to that we _definitely_ want a way to disable this [assumption
that the shift operand is in-range] if we make that assumption
even on IL state after optimizations.
Candidates to look for are invariant motion, ifcombine,
partial PRE, PRE in general (we possibly hoist such expressions
across function calls that might terminate the program normally).
That is, what prevents
if (n > 32)
abort ();
x = i << n;
to be transformed to
x = i << n;
if (n > 32)
abort ();
? Yes, that's probably a latent issue in some sense but you would
now optimize the if (n > 32) abort () away while previously x would
have an undetermined value but we'd still abort.
Do you have some statistics on how this particular side-effect
improves code generation?
Richard.
>
> Andrew
>
>
> PS. Note that in the testcase, one of the tests is currently disabled
> as full recomputation of side-effects is not quite in place yet. WHen ti
> is, I will enable the test.
>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] PR tree-optimization/31178 - Add rshift side effect.
2022-05-18 6:41 ` Richard Biener
@ 2022-05-18 13:15 ` Andrew MacLeod
2022-05-19 5:56 ` Richard Biener
0 siblings, 1 reply; 4+ messages in thread
From: Andrew MacLeod @ 2022-05-18 13:15 UTC (permalink / raw)
To: Richard Biener, Jakub Jelinek; +Cc: gcc-patches
On 5/18/22 02:41, Richard Biener wrote:
> On Tue, May 17, 2022 at 8:41 PM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> This patch implements side effects of the second operand of a shift
>> operation.
>>
>> given A >> B or A << B, the range of B is restricted to [0, PRECISION_A).
>>
>> Fortran is currently more permissive than this, allowing the range to be
>> [0, PRECISION_A], so this si the value we currently default to in this
>> patch. If the fortran front end were adjusted, we could adjust the end
>> point.
>>
>> This currently bootstraps with no regressions on x86_64-pc-linux-gnu.
>>
>> Is this sufficient, or should I also be checking some other flags which
>> may allow other values outside this range to be valid?
> I think the "undefined behavior" side-effects are dangerous since
> I know of no code that makes sure to clamp the shift argument when
> hoisting it. sanitizing shifts will also not help to discover such latent
> issues since sanitizing is happening early and it will most definitely
> avoid the hoisting itself.
>
> As to that we _definitely_ want a way to disable this [assumption
> that the shift operand is in-range] if we make that assumption
> even on IL state after optimizations.
>
> Candidates to look for are invariant motion, ifcombine,
> partial PRE, PRE in general (we possibly hoist such expressions
> across function calls that might terminate the program normally).
>
> That is, what prevents
>
> if (n > 32)
> abort ();
> x = i << n;
>
> to be transformed to
>
> x = i << n;
> if (n > 32)
> abort ();
>
> ? Yes, that's probably a latent issue in some sense but you would
> now optimize the if (n > 32) abort () away while previously x would
> have an undetermined value but we'd still abort.
>
> Do you have some statistics on how this particular side-effect
> improves code generation?
>
> Richard.
None whatsoever... just a PR requesting it that has been open for 15
years :-)
If we don't want to do this optimization, then we should kill the PR. I
can also attach the path to the PR than if anyone cares enough about
this functionality, they could pursue the other effects...
Andrew
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] PR tree-optimization/31178 - Add rshift side effect.
2022-05-18 13:15 ` Andrew MacLeod
@ 2022-05-19 5:56 ` Richard Biener
0 siblings, 0 replies; 4+ messages in thread
From: Richard Biener @ 2022-05-19 5:56 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: Jakub Jelinek, gcc-patches
On Wed, May 18, 2022 at 3:16 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 5/18/22 02:41, Richard Biener wrote:
> > On Tue, May 17, 2022 at 8:41 PM Andrew MacLeod via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >> This patch implements side effects of the second operand of a shift
> >> operation.
> >>
> >> given A >> B or A << B, the range of B is restricted to [0, PRECISION_A).
> >>
> >> Fortran is currently more permissive than this, allowing the range to be
> >> [0, PRECISION_A], so this si the value we currently default to in this
> >> patch. If the fortran front end were adjusted, we could adjust the end
> >> point.
> >>
> >> This currently bootstraps with no regressions on x86_64-pc-linux-gnu.
> >>
> >> Is this sufficient, or should I also be checking some other flags which
> >> may allow other values outside this range to be valid?
> > I think the "undefined behavior" side-effects are dangerous since
> > I know of no code that makes sure to clamp the shift argument when
> > hoisting it. sanitizing shifts will also not help to discover such latent
> > issues since sanitizing is happening early and it will most definitely
> > avoid the hoisting itself.
> >
> > As to that we _definitely_ want a way to disable this [assumption
> > that the shift operand is in-range] if we make that assumption
> > even on IL state after optimizations.
> >
> > Candidates to look for are invariant motion, ifcombine,
> > partial PRE, PRE in general (we possibly hoist such expressions
> > across function calls that might terminate the program normally).
> >
> > That is, what prevents
> >
> > if (n > 32)
> > abort ();
> > x = i << n;
> >
> > to be transformed to
> >
> > x = i << n;
> > if (n > 32)
> > abort ();
> >
> > ? Yes, that's probably a latent issue in some sense but you would
> > now optimize the if (n > 32) abort () away while previously x would
> > have an undetermined value but we'd still abort.
> >
> > Do you have some statistics on how this particular side-effect
> > improves code generation?
> >
> > Richard.
>
> None whatsoever... just a PR requesting it that has been open for 15
> years :-)
>
> If we don't want to do this optimization, then we should kill the PR. I
> can also attach the path to the PR than if anyone cares enough about
> this functionality, they could pursue the other effects...
Linking from the bug to this patch submission and the discussion would
certainly be helpful.
I think most of the undefined behavior exploiting we do would benefit
from a mode where the code exploiting the undefined behavior would
instead instrument the code to abort the program. That way it would
be much easier to detect GCCs wrongdoing (introducing such
undefined behavior when sanitizers are otherwise clean) rather than
waiting on the rare occasion where the bogus exploitation triggers
a miscompile in actual code.
Richard.
> Andrew
>
>
>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2022-05-19 5:56 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-05-17 18:39 [PATCH] PR tree-optimization/31178 - Add rshift side effect Andrew MacLeod
2022-05-18 6:41 ` Richard Biener
2022-05-18 13:15 ` Andrew MacLeod
2022-05-19 5:56 ` Richard Biener
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).