[PATCH] PR tree-optimization/31178 - Add rshift side effect.

[PATCH] PR tree-optimization/31178 - Add rshift side effect.

[Andrew MacLeod]

[-- 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" } } */

Re: [PATCH] PR tree-optimization/31178 - Add rshift side effect.

[Richard Biener]

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.
>

Re: [PATCH] PR tree-optimization/31178 - Add rshift side effect.

[Andrew MacLeod]

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

Re: [PATCH] PR tree-optimization/31178 - Add rshift side effect.

[Richard Biener]

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
>
>
>