[PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Philipp Tomsich]

From: Philipp Tomsich <prt@gnu.org>

While most shifts wider than the bitwidth of a type will be caught by
other passes, it is possible that these show up for VRP.
Consider the following example:
  int func (int a, int b, int c)
  {
    return (a << ((b && c) - 1));
  }

This adds simplify_using_ranges::simplify_lshift_using_ranges to
detect and rewrite such cases.  If the intersection of meaningful
shift amounts for the underlying type and the value-range computed
for the shift-amount (whether an integer constant or a variable) is
empty, the statement is replaced with the zero-constant of the same
precision as the result.

gcc/ChangeLog:

       * vr-values.h (simplify_using_ranges): Declare.
       * vr-values.c (simplify_lshift_using_ranges): New function.
       (simplify): Use simplify_lshift_using_ranges for LSHIFT_EXPR.

---

 gcc/ChangeLog   |  6 ++++++
 gcc/vr-values.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/vr-values.h |  1 +
 3 files changed, 66 insertions(+)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 89317d4..b8b9beb 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2020-11-16  Philipp Tomsich  <prt@gnu.org>
+
+	* vr-values.h (simplify_using_ranges): Declare.
+	* vr-values.c (simplify_lshift_using_ranges): New function.
+	(simplify): Use simplify_lshift_using_ranges for LSHIFT_EXPR.
+
 2020-11-13  Jan Hubicka  <jh@suse.cz>
 
 	* tree-ssa-alias.c (ao_ref_base_alias_ptr_type): Remove accidental
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 9f5943a..da7208e 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -3318,6 +3318,58 @@ simplify_using_ranges::simplify_div_or_mod_using_ranges
   return false;
 }
 
+/* Simplify a lshift, if the shift-amount is larger than the
+   bit-width of the type.  Return true if we do simplify.  */
+bool
+simplify_using_ranges::simplify_lshift_using_ranges
+				(gimple_stmt_iterator *gsi,
+				 gimple *stmt)
+{
+  tree op0 = gimple_assign_rhs1 (stmt);
+  tree op1 = gimple_assign_rhs2 (stmt);
+  value_range vr1;
+
+  /* We only support integral types.  */
+  if (INTEGRAL_TYPE_P (op0))
+    return false;
+
+  if (TREE_CODE (op1) == INTEGER_CST)
+    vr1.set (op1);
+  else if (TREE_CODE (op1) == SSA_NAME)
+    vr1 = *(query->get_value_range (op1, stmt));
+  else
+    return false;
+
+  if (vr1.varying_p () || vr1.undefined_p ())
+    return false;
+
+  /* Shift amounts are valid up to the type precision.  Any shift that
+     is outside of the range [0, type precision - 1] can be rewritten
+     to a constant result.  */
+  const unsigned prec = TYPE_PRECISION (TREE_TYPE (op0));
+  value_range valid (build_zero_cst (TREE_TYPE (op1)),
+		     build_int_cst (TREE_TYPE (op1), prec - 1),
+		     VR_RANGE);
+
+  valid.intersect (vr1);
+  if (valid.undefined_p ())
+    {
+      /* If the intersection is empty (i.e. undefined), then we can replace the
+	 shift with the zero-constant.  */
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "\nReplacing shift beyond precision in stmt: ");
+	  print_gimple_stmt (dump_file, stmt, 0);
+	}
+      gimple_assign_set_rhs_from_tree (gsi, build_zero_cst (TREE_TYPE (op0)));
+      update_stmt (gsi_stmt (*gsi));
+      return true;
+    }
+
+  return false;
+}
+
 /* Simplify a min or max if the ranges of the two operands are
    disjoint.   Return true if we do simplify.  */
 
@@ -4422,6 +4474,13 @@ simplify_using_ranges::simplify (gimple_stmt_iterator *gsi)
 	case MAX_EXPR:
 	  return simplify_min_or_max_using_ranges (gsi, stmt);
 
+	case LSHIFT_EXPR:
+	  if ((TREE_CODE (rhs1) == SSA_NAME
+	       || TREE_CODE (rhs1) == INTEGER_CST)
+	      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
+	    return simplify_lshift_using_ranges (gsi, stmt);
+	  break;
+
 	default:
 	  break;
 	}
diff --git a/gcc/vr-values.h b/gcc/vr-values.h
index 59fac0c..18fd5c1 100644
--- a/gcc/vr-values.h
+++ b/gcc/vr-values.h
@@ -48,6 +48,7 @@ private:
   bool simplify_div_or_mod_using_ranges (gimple_stmt_iterator *, gimple *);
   bool simplify_abs_using_ranges (gimple_stmt_iterator *, gimple *);
   bool simplify_bit_ops_using_ranges (gimple_stmt_iterator *, gimple *);
+  bool simplify_lshift_using_ranges (gimple_stmt_iterator *, gimple *);
   bool simplify_min_or_max_using_ranges (gimple_stmt_iterator *, gimple *);
   bool simplify_cond_using_ranges_1 (gcond *);
   bool fold_cond (gcond *);
-- 
1.8.3.1

[PATCH v1 2/2] RISC-V: Adjust predicates for immediate shift operands

[Philipp Tomsich]

From: Philipp Tomsich <prt@gnu.org>

In case a negative shift operand makes it through into the backend,
it will be treated as unsigned and truncated (using a mask) to fit
into the range 0..31 (for SImode) and 0..63 (for DImode).

Consider the following output illustrating the issue and shows how
the shift amount is truncated):
 #(insn 16 15 53 (set (reg:DI 10 a0 [orig:72 <retval> ] [72])
 #        (sign_extend:DI (ashift:SI (reg:SI 15 a5 [orig:73 a ] [73])
 #                (const_int -1 [0xffffffffffffffff])))) "isolated.c":3:13 168 {*ashlsi3_extend}
 #     (expr_list:REG_DEAD (reg:SI 15 a5 [orig:73 a ] [73])
 #        (nil)))
	  slliw	a0,a5,31	#, <retval>, a	# 16	[c=8 l=4]  *ashlsi3_extend

This change adjusts the predicates to allow immediate shifts for the
supported ranges 0..31 and 0..63, respectively, only.  As immediates
outside of these ranges can no longer pass the constraint-check, the
implementation of the patterns emitting the respective shift can also
be simplified.  Larger shift amounts will now be forced along a path
resulting in a non-immediate shift.

A new testcase is added to check that non-immediate shift instructions
are emitted.

gcc/ChangeLog:

       * config/riscv/predicates.md (riscv_shift_imm_si, riscv_shift_si,
       riscv_shift_imm_di, riscv_shift_di): New.
       * config/riscv/riscv.md: Use 'riscv_shift_si' and 'riscv_shift_di'
       in definition of shift instructions; remove (now unnecessary)
       truncation of immediates.

gcc/testsuite/ChangeLog:

       * gcc.target/riscv/shift-negative-amount.c: New.

---

 gcc/ChangeLog                                       |  5 +++++
 gcc/config/riscv/predicates.md                      | 16 ++++++++++++++++
 gcc/config/riscv/riscv.md                           | 21 ++++-----------------
 gcc/testsuite/ChangeLog                             |  4 ++++
 .../gcc.target/riscv/shift-negative-amount.c        | 14 ++++++++++++++
 5 files changed, 43 insertions(+), 17 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/riscv/shift-negative-amount.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b8b9beb..6ca8ee0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,10 @@
 2020-11-16  Philipp Tomsich  <prt@gnu.org>
 
+	* config/riscv/predicates.md (riscv_shift_imm_si, riscv_shift_si,
+	riscv_shift_imm_di, riscv_shift_di): New.
+	* config/riscv/riscv.md: Use 'riscv_shift_si' and 'riscv_shift_di'
+	in definition of shift instructions; remove (now unnecessary)
+	truncation of immediates.
 	* vr-values.h (simplify_using_ranges): Declare.
 	* vr-values.c (simplify_lshift_using_ranges): New function.
 	(simplify): Use simplify_lshift_using_ranges for LSHIFT_EXPR.
diff --git a/gcc/config/riscv/predicates.md b/gcc/config/riscv/predicates.md
index f764fe7..fb35871 100644
--- a/gcc/config/riscv/predicates.md
+++ b/gcc/config/riscv/predicates.md
@@ -27,6 +27,22 @@
   (ior (match_operand 0 "const_arith_operand")
        (match_operand 0 "register_operand")))
 
+(define_predicate "riscv_shift_imm_si"
+  (and (match_code "const_int")
+       (match_test "(unsigned HOST_WIDE_INT) INTVAL (op) < 32")))
+
+(define_predicate "riscv_shift_si"
+  (ior (match_operand 0 "riscv_shift_imm_si")
+       (match_operand 0 "register_operand")))
+
+(define_predicate "riscv_shift_imm_di"
+  (and (match_code "const_int")
+       (match_test "(unsigned HOST_WIDE_INT) INTVAL (op) < 64")))
+
+(define_predicate "riscv_shift_di"
+  (ior (match_operand 0 "riscv_shift_imm_di")
+       (match_operand 0 "register_operand")))
+
 (define_predicate "lui_operand"
   (and (match_code "const_int")
        (match_test "LUI_OPERAND (INTVAL (op))")))
diff --git a/gcc/config/riscv/riscv.md b/gcc/config/riscv/riscv.md
index f15bad3..7b34839 100644
--- a/gcc/config/riscv/riscv.md
+++ b/gcc/config/riscv/riscv.md
@@ -1574,13 +1574,9 @@
   [(set (match_operand:SI     0 "register_operand" "= r")
 	(any_shift:SI
 	    (match_operand:SI 1 "register_operand" "  r")
-	    (match_operand:QI 2 "arith_operand"    " rI")))]
+	    (match_operand:QI 2 "riscv_shift_si"   " rI")))]
   ""
 {
-  if (GET_CODE (operands[2]) == CONST_INT)
-    operands[2] = GEN_INT (INTVAL (operands[2])
-			   & (GET_MODE_BITSIZE (SImode) - 1));
-
   return TARGET_64BIT ? "<insn>%i2w\t%0,%1,%2" : "<insn>%i2\t%0,%1,%2";
 }
   [(set_attr "type" "shift")
@@ -1629,13 +1625,9 @@
   [(set (match_operand:DI 0 "register_operand"     "= r")
 	(any_shift:DI
 	    (match_operand:DI 1 "register_operand" "  r")
-	    (match_operand:QI 2 "arith_operand"    " rI")))]
+	    (match_operand:QI 2 "riscv_shift_di"   " rI")))]
   "TARGET_64BIT"
 {
-  if (GET_CODE (operands[2]) == CONST_INT)
-    operands[2] = GEN_INT (INTVAL (operands[2])
-			   & (GET_MODE_BITSIZE (DImode) - 1));
-
   return "<insn>%i2\t%0,%1,%2";
 }
   [(set_attr "type" "shift")
@@ -1685,14 +1677,9 @@
   [(set (match_operand:DI                   0 "register_operand" "= r")
 	(sign_extend:DI
 	    (any_shift:SI (match_operand:SI 1 "register_operand" "  r")
-			  (match_operand:QI 2 "arith_operand"    " rI"))))]
+			  (match_operand:QI 2 "riscv_shift_si"   " rI"))))]
   "TARGET_64BIT"
-{
-  if (GET_CODE (operands[2]) == CONST_INT)
-    operands[2] = GEN_INT (INTVAL (operands[2]) & 0x1f);
-
-  return "<insn>%i2w\t%0,%1,%2";
-}
+  "<insn>%i2w\t%0,%1,%2"
   [(set_attr "type" "shift")
    (set_attr "mode" "SI")])
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index a748ff6..1efe87d 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2020-11-16  Philipp Tomsich  <prt@gnu.org>
+
+	* gcc.target/riscv/shift-negative-amount.c: New.
+
 2020-11-13  Joseph Myers  <joseph@codesourcery.com>
 
 	* gcc.dg/binary-constants-2.c, gcc.dg/binary-constants-3.c,
diff --git a/gcc/testsuite/gcc.target/riscv/shift-negative-amount.c b/gcc/testsuite/gcc.target/riscv/shift-negative-amount.c
new file mode 100644
index 0000000..0db5e4d
--- /dev/null
+++ b/gcc/testsuite/gcc.target/riscv/shift-negative-amount.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-march=rv64gc -mabi=lp64 -O2 -fno-tree-vrp" } */
+
+int shift1 (int a, int b, int c)
+{
+  return (a << ((b && c) - 1));
+}
+
+long int shift2 (long int a, long int b, long int c)
+{
+  return (a << ((b && c) - 1));
+}
+/* { dg-final { scan-assembler "sllw" } } */
+/* { dg-final { scan-assembler "sll" } } */
-- 
1.8.3.1

Re: [PATCH v1 2/2] RISC-V: Adjust predicates for immediate shift operands

[Jim Wilson]

On Mon, Nov 16, 2020 at 10:57 AM Philipp Tomsich <philipp.tomsich@vrull.eu>
wrote:

> In case a negative shift operand makes it through into the backend,
> it will be treated as unsigned and truncated (using a mask) to fit
> into the range 0..31 (for SImode) and 0..63 (for DImode).
>

This is a de-optimization.  This doesn't make any sense.  The ISA manual
clearly states the shift counts are truncated.  Some targets do this with
SHIFT_COUNT_TRUNCATED, but that is known to cause problems, so the RISC-V
port is doing it in the shift expanders.  I believe that other targets do
this too.

Also, note that replacing
  slli a0, a0, 31
with
  li a1, -1;
  sll a0, a0, a1
doesn't change the operation performed.  The shift count is still truncated
to 31, and so you get the exact same result from both code sequences.  All
you have done is make the code bigger and slower which is undesirable.

Also note that the testcase has implementation defined results, so there is
no wrong answer here, and nothing wrong with what the RISC-V port is doing.

+/* { dg-final { scan-assembler "sll" } } */
>

I don't think that this will work as a grep for sll will also match slli.
You would need to add a space or tab or maybe both to the search string to
prevent matches with slli.  Or alternatively use scan-assembler-not "slli"
which will match and fail for both slli and slliw.

Jim

Re: [PATCH v1 2/2] RISC-V: Adjust predicates for immediate shift operands

[Philipp Tomsich]

Jim,

On Mon, 16 Nov 2020 at 23:28, Jim Wilson <jimw@sifive.com> wrote:
>
> On Mon, Nov 16, 2020 at 10:57 AM Philipp Tomsich <philipp.tomsich@vrull.eu>
wrote:
>>
>> In case a negative shift operand makes it through into the backend,
>> it will be treated as unsigned and truncated (using a mask) to fit
>> into the range 0..31 (for SImode) and 0..63 (for DImode).
>
>
> This is a de-optimization.  This doesn't make any sense.  The ISA manual
clearly states the shift counts are truncated.  Some targets do this with
SHIFT_COUNT_TRUNCATED, but that is known to cause problems, so the RISC-V
port is doing it in the shift expanders.  I believe that other targets do
this too.

This is an de-optimization only, if applied without patch 1 from the
series: the change to VRP ensures that the backend will never see a shift
wider than the immediate field.
The problem is that if a negative shift-amount makes it to the backend,
unindented code may be generated (as a shift-amount, in my reading, should
always be interpreted as unsigned).

Note that with tree-vrp turned on (and patch 1 of the series applied), you
will see

.L3:
li a0,0

generated, anyway.

> Also, note that replacing
>   slli a0, a0, 31
> with
>   li a1, -1;
>   sll a0, a0, a1
> doesn't change the operation performed.  The shift count is still
truncated to 31, and so you get the exact same result from both code
sequences.  All you have done is make the code bigger and slower which is
undesirable.

I do agree that this does not address the issue of a shift that is wider
than the register width, even though it makes sure we reject this from the
immediate field.
That said: what is the correct behavior/result of this operation?

> Also note that the testcase has implementation defined results, so there
is no wrong answer here, and nothing wrong with what the RISC-V port is
doing.
>
>> +/* { dg-final { scan-assembler "sll" } } */
>
>
> I don't think that this will work as a grep for sll will also match
slli.  You would need to add a space or tab or maybe both to the search
string to prevent matches with slli.  Or alternatively use
scan-assembler-not "slli" which will match and fail for both slli and slliw.

Good catch. I turned this check around, but submitted the wrong one.

Thanks,
Philipp.

Re: [PATCH v1 2/2] RISC-V: Adjust predicates for immediate shift operands

[Jim Wilson]

On Mon, Nov 16, 2020 at 2:45 PM Philipp Tomsich <philipp.tomsich@vrull.eu>
wrote:

> This is an de-optimization only, if applied without patch 1 from the
> series: the change to VRP ensures that the backend will never see a shift
> wider than the immediate field.
> The problem is that if a negative shift-amount makes it to the backend,
> unindented code may be generated (as a shift-amount, in my reading, should
> always be interpreted as unsigned).
>

I doubt that you are catching every possible case.  What kind of testing
have you done to prove this?  The code you are removing does nothing
harmful, but removing it may de-optimize code.  So it should not be removed
without a very good reason and a lot of testing to make sure there is no
regression.

Shift counts do not have to be unsigned at the assembly language level.
Consider this testcase
    int sub (int i, int j) { return i << (32 - j); }
Compiling with rv32 -O2 gives me
    li a5,32
    sub a5,a5,a1
    sll a0,a0,a5
which is 3 instructions.  But since we know that shift counts are
truncated, we should be compiling this as
    neg a1,a1
    sll a0,a0,a1
which gives the exact same result with 2 instructions.  This is on my todo
list.  This deliberately uses a negative shift count, but this is well
defined in the RISC-V ISA, so this poses no problems.

There are other related things we can do here to improve code generation
for shifts.  We should not be limiting optimization at the assembly level
by what the C standard says.

You also might want to look at SHIFT_COUNT_TRUNCATED and
TARGET_SHIFT_TRUNCATION_MASK.  We already have infrastructure to handle
out-of-range shifts as the hardware dictates.  Your changes conflict with
this.  I think we should define TARGET_SHIFT_TRUNCATION_MASK for RISC-V.
That is another item on my todo list.

Jim

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jim Wilson]

On Mon, Nov 16, 2020 at 10:57 AM Philipp Tomsich <philipp.tomsich@vrull.eu>
wrote:

> This adds simplify_using_ranges::simplify_lshift_using_ranges to
> detect and rewrite such cases.  If the intersection of meaningful
> shift amounts for the underlying type and the value-range computed
> for the shift-amount (whether an integer constant or a variable) is
> empty, the statement is replaced with the zero-constant of the same
> precision as the result.
>

This has the risk of breaking some user code.  I've seen people write code
for RISC-V knowing that the hardware truncates shift counts, and so not
doing the full calculation to get the right value but just letting the
compiler/hardware calculate it for them via truncation.  Of course this
code has implemented defined result, but there is no reason to break it
unnecessarily.

Jim

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Philipp Tomsich]

On Mon, 16 Nov 2020 at 23:38, Jim Wilson <jimw@sifive.com> wrote:

> On Mon, Nov 16, 2020 at 10:57 AM Philipp Tomsich <philipp.tomsich@vrull.eu>
> wrote:
>
>> This adds simplify_using_ranges::simplify_lshift_using_ranges to
>> detect and rewrite such cases.  If the intersection of meaningful
>> shift amounts for the underlying type and the value-range computed
>> for the shift-amount (whether an integer constant or a variable) is
>> empty, the statement is replaced with the zero-constant of the same
>> precision as the result.
>>
>
> This has the risk of breaking some user code.  I've seen people write code
> for RISC-V knowing that the hardware truncates shift counts, and so not
> doing the full calculation to get the right value but just letting the
> compiler/hardware calculate it for them via truncation.  Of course this
> code has implemented defined result, but there is no reason to break it
> unnecessarily.
>

While undefined behavior (as per the C standard), GCC uses a predictable
behaviour for negative shift-amounts (and shifts that are wider than the
type):

int func(int a)
{
  return a << -1;
}

will raise the following warning:

shift-neg.c: In function 'func':
shift-neg.c:3:12: warning: left shift count is negative
[-Wshift-count-negative]
    3 |   return a << -1;
      |            ^~

and return 0:

func:
    li a0,0
    ret
    .size func, .-func


Having two different results generated here, depending on what parts of GCC
"see" the shift-amount, doesn't seem sensible and likely to cause breakage
in the long term.
I fully agree that this is undefined behavior (so no well-formed program
should rely on it), but I would prefer to have a common behavior
independent on when the constant is known.

Philipp.

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jeff Law]

On 11/16/20 11:57 AM, Philipp Tomsich wrote:
> From: Philipp Tomsich <prt@gnu.org>
>
> While most shifts wider than the bitwidth of a type will be caught by
> other passes, it is possible that these show up for VRP.
> Consider the following example:
>   int func (int a, int b, int c)
>   {
>     return (a << ((b && c) - 1));
>   }
>
> This adds simplify_using_ranges::simplify_lshift_using_ranges to
> detect and rewrite such cases.  If the intersection of meaningful
> shift amounts for the underlying type and the value-range computed
> for the shift-amount (whether an integer constant or a variable) is
> empty, the statement is replaced with the zero-constant of the same
> precision as the result.
>
> gcc/ChangeLog:
>
>        * vr-values.h (simplify_using_ranges): Declare.
>        * vr-values.c (simplify_lshift_using_ranges): New function.
>        (simplify): Use simplify_lshift_using_ranges for LSHIFT_EXPR.

Umm, isn't this a shift wider than the bitwidth undefined behavior?  We
should be generating warnings for that, not trying to further optimize
it :-)


jeff

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Philipp Tomsich]

Jeff,

On Tue, 17 Nov 2020 at 00:38, Jeff Law <law@redhat.com> wrote:

>
> On 11/16/20 11:57 AM, Philipp Tomsich wrote:
> > From: Philipp Tomsich <prt@gnu.org>
> >
> > While most shifts wider than the bitwidth of a type will be caught by
> > other passes, it is possible that these show up for VRP.
> > Consider the following example:
> >   int func (int a, int b, int c)
> >   {
> >     return (a << ((b && c) - 1));
> >   }
> >
> > This adds simplify_using_ranges::simplify_lshift_using_ranges to
> > detect and rewrite such cases.  If the intersection of meaningful
> > shift amounts for the underlying type and the value-range computed
> > for the shift-amount (whether an integer constant or a variable) is
> > empty, the statement is replaced with the zero-constant of the same
> > precision as the result.
> >
> > gcc/ChangeLog:
> >
> >        * vr-values.h (simplify_using_ranges): Declare.
> >        * vr-values.c (simplify_lshift_using_ranges): New function.
> >        (simplify): Use simplify_lshift_using_ranges for LSHIFT_EXPR.
>
> Umm, isn't this a shift wider than the bitwidth undefined behavior?  We
> should be generating warnings for that, not trying to further optimize
> it :-)
>

The shift is undefined behavior on the language level (for C) and a warning
will be generated, if such a shift is encountered; additionally, the shift
will be
replaced with the value 0.

However, in the above case, the shift is generated only in the middle end:
At 136t.walloca, I still have:

>   # RANGE [-1, 0]
>   _1 = iftmp.1_2 + -1;
>   _6 = a_5(D) << _1;

Whereas at 137t.pre, this is changed into:

> Found partial redundancy for expression {lshift_expr,a_5(D),_1} (0006)
> Inserted _9 = a_5(D) << -1;


In other words, the change to VRP canonicalizes what a lshift_expr with an
shift-amount outside of the type width means... it doesn't assume anything
about the original language.
Do we assume that a LSHIFT_EXPR has the same semantics as for a
C-language shift-left? If so, then pre should not generate the LSHIFT_EXPR
for _9... or we might even catch this later in path isolation (as undefined
behavior, insert a __builtin_trap() and emit a warning)?

Note that in his comment to patch 2/2, Jim has noted that user code for
RISC-V may assume a truncation of the shift-operand...

Philipp.

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jeff Law]

On 11/17/20 4:53 AM, Philipp Tomsich wrote:
> Jeff,
>
> On Tue, 17 Nov 2020 at 00:38, Jeff Law <law@redhat.com
> <mailto:law@redhat.com>> wrote:
>
>
>     On 11/16/20 11:57 AM, Philipp Tomsich wrote:
>     > From: Philipp Tomsich <prt@gnu.org <mailto:prt@gnu.org>>
>     >
>     > While most shifts wider than the bitwidth of a type will be
>     caught by
>     > other passes, it is possible that these show up for VRP.
>     > Consider the following example:
>     >   int func (int a, int b, int c)
>     >   {
>     >     return (a << ((b && c) - 1));
>     >   }
>     >
>     > This adds simplify_using_ranges::simplify_lshift_using_ranges to
>     > detect and rewrite such cases.  If the intersection of meaningful
>     > shift amounts for the underlying type and the value-range computed
>     > for the shift-amount (whether an integer constant or a variable) is
>     > empty, the statement is replaced with the zero-constant of the same
>     > precision as the result.
>     >
>     > gcc/ChangeLog:
>     >
>     >        * vr-values.h (simplify_using_ranges): Declare.
>     >        * vr-values.c (simplify_lshift_using_ranges): New function.
>     >        (simplify): Use simplify_lshift_using_ranges for LSHIFT_EXPR.
>
>     Umm, isn't this a shift wider than the bitwidth undefined
>     behavior?  We
>     should be generating warnings for that, not trying to further optimize
>     it :-)
>
>
> The shift is undefined behavior on the language level (for C) and a
> warning
> will be generated, if such a shift is encountered; additionally, the
> shift will be
> replaced with the value 0.
>
> However, in the above case, the shift is generated only in the middle end:
> At 136t.walloca, I still have:
>
>       # RANGE [-1, 0]
>       _1 = iftmp.1_2 + -1;
>       _6 = a_5(D) << _1;
>
> Whereas at 137t.pre, this is changed into:
>
>     Found partial redundancy for expression {lshift_expr,a_5(D),_1} (0006)
>     Inserted _9 = a_5(D) << -1;
>
>
> In other words, the change to VRP canonicalizes what a lshift_expr with an
> shift-amount outside of the type width means... it doesn't assume anything
> about the original language.
> Do we assume that a LSHIFT_EXPR has the same semantics as for a
> C-language shift-left? If so, then pre should not generate the LSHIFT_EXPR
> for _9... or we might even catch this later in path isolation (as
> undefined
> behavior, insert a __builtin_trap() and emit a warning)?
>
> Note that in his comment to patch 2/2, Jim has noted that user code for
> RISC-V may assume a truncation of the shift-operand...
What I'd suggest doing would be to leave the invalid shift count in the
IL in VRP, then extend the erroneous path isolation code to turn an
invalid shift into a trap (conditionally of course).

jeff

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Philipp Tomsich]

Jakub,

On Tue, 17 Nov 2020 at 16:56, Jeff Law <law@redhat.com> wrote:
>
>
>
> On 11/17/20 4:53 AM, Philipp Tomsich wrote:
> > Jeff,
> >
> > On Tue, 17 Nov 2020 at 00:38, Jeff Law <law@redhat.com
> > <mailto:law@redhat.com>> wrote:
> >
> >
> >     On 11/16/20 11:57 AM, Philipp Tomsich wrote:
> >     > From: Philipp Tomsich <prt@gnu.org <mailto:prt@gnu.org>>
> >     >
> >     > While most shifts wider than the bitwidth of a type will be
> >     caught by
> >     > other passes, it is possible that these show up for VRP.
> >     > Consider the following example:
> >     >   int func (int a, int b, int c)
> >     >   {
> >     >     return (a << ((b && c) - 1));
> >     >   }
> >     >
> >     > This adds simplify_using_ranges::simplify_lshift_using_ranges to
> >     > detect and rewrite such cases.  If the intersection of meaningful
> >     > shift amounts for the underlying type and the value-range computed
> >     > for the shift-amount (whether an integer constant or a variable) is
> >     > empty, the statement is replaced with the zero-constant of the same
> >     > precision as the result.
> >     >
> >     > gcc/ChangeLog:
> >     >
> >     >        * vr-values.h (simplify_using_ranges): Declare.
> >     >        * vr-values.c (simplify_lshift_using_ranges): New function.
> >     >        (simplify): Use simplify_lshift_using_ranges for LSHIFT_EXPR.
> >
> >     Umm, isn't this a shift wider than the bitwidth undefined
> >     behavior?  We
> >     should be generating warnings for that, not trying to further optimize
> >     it :-)
> >
> >
> > The shift is undefined behavior on the language level (for C) and a
> > warning
> > will be generated, if such a shift is encountered; additionally, the
> > shift will be
> > replaced with the value 0.
> >
> > However, in the above case, the shift is generated only in the middle end:
> > At 136t.walloca, I still have:
> >
> >       # RANGE [-1, 0]
> >       _1 = iftmp.1_2 + -1;
> >       _6 = a_5(D) << _1;
> >
> > Whereas at 137t.pre, this is changed into:
> >
> >     Found partial redundancy for expression {lshift_expr,a_5(D),_1} (0006)
> >     Inserted _9 = a_5(D) << -1;
> >
> >
> > In other words, the change to VRP canonicalizes what a lshift_expr with an
> > shift-amount outside of the type width means... it doesn't assume anything
> > about the original language.
> > Do we assume that a LSHIFT_EXPR has the same semantics as for a
> > C-language shift-left? If so, then pre should not generate the LSHIFT_EXPR
> > for _9... or we might even catch this later in path isolation (as
> > undefined
> > behavior, insert a __builtin_trap() and emit a warning)?
> >
> > Note that in his comment to patch 2/2, Jim has noted that user code for
> > RISC-V may assume a truncation of the shift-operand...
> What I'd suggest doing would be to leave the invalid shift count in the
> IL in VRP, then extend the erroneous path isolation code to turn an
> invalid shift into a trap (conditionally of course).

You had originally suggested to add this to VRP ...
Given the various comments to this patch, do you still want any of
this in VRP or
would you rather see this only in path isolation?

Philipp.

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jakub Jelinek]

On Tue, Nov 17, 2020 at 05:29:57PM +0100, Philipp Tomsich wrote:
> > > In other words, the change to VRP canonicalizes what a lshift_expr with an
> > > shift-amount outside of the type width means... it doesn't assume anything
> > > about the original language.
> > > Do we assume that a LSHIFT_EXPR has the same semantics as for a
> > > C-language shift-left? If so, then pre should not generate the LSHIFT_EXPR
> > > for _9... or we might even catch this later in path isolation (as
> > > undefined
> > > behavior, insert a __builtin_trap() and emit a warning)?
> > >
> > > Note that in his comment to patch 2/2, Jim has noted that user code for
> > > RISC-V may assume a truncation of the shift-operand...
> > What I'd suggest doing would be to leave the invalid shift count in the
> > IL in VRP, then extend the erroneous path isolation code to turn an
> > invalid shift into a trap (conditionally of course).
> 
> You had originally suggested to add this to VRP ...
> Given the various comments to this patch, do you still want any of
> this in VRP or
> would you rather see this only in path isolation?

Well, I said if we want to do it at all, it should be done in VRP, because
there is not really a difference between ((int) x) << 32 and ((int) x) << y
for y in [32, 137] etc.
Otherwise it is the general question of what to do upon proven UB, and that
is a topic discussed several years during Cauldron that it would be nice to
have switches where users can choose what to do in that case,
__builtin_unreachable (), __builtin_trap (), ... and another thing is where
we should warn about it (tight e.g. to the __builtin_warning thing, because
we don't want these warnings for dead code).

So, e.g. if we had __builtin_warning (dunno where Martin S. is with that),
we could e.g. queue a __builtin_warning and add __builtin_unreachable (or
other possibilities), or e.g. during VRP just canonicalize proven always
out of bound shifts to shifts by an out of bound constant and let some later
pass warn and/or add __builtin_warning.

	Jakub

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jeff Law]

On 11/17/20 9:46 AM, Jakub Jelinek wrote:
> On Tue, Nov 17, 2020 at 05:29:57PM +0100, Philipp Tomsich wrote:
>>>> In other words, the change to VRP canonicalizes what a lshift_expr with an
>>>> shift-amount outside of the type width means... it doesn't assume anything
>>>> about the original language.
>>>> Do we assume that a LSHIFT_EXPR has the same semantics as for a
>>>> C-language shift-left? If so, then pre should not generate the LSHIFT_EXPR
>>>> for _9... or we might even catch this later in path isolation (as
>>>> undefined
>>>> behavior, insert a __builtin_trap() and emit a warning)?
>>>>
>>>> Note that in his comment to patch 2/2, Jim has noted that user code for
>>>> RISC-V may assume a truncation of the shift-operand...
>>> What I'd suggest doing would be to leave the invalid shift count in the
>>> IL in VRP, then extend the erroneous path isolation code to turn an
>>> invalid shift into a trap (conditionally of course).
>> You had originally suggested to add this to VRP ...
>> Given the various comments to this patch, do you still want any of
>> this in VRP or
>> would you rather see this only in path isolation?
> Well, I said if we want to do it at all, it should be done in VRP, because
> there is not really a difference between ((int) x) << 32 and ((int) x) << y
> for y in [32, 137] etc.
Right.  VRP is the right place to discover, but I'm not sure it's the
right place to clean up the mess though.

> Otherwise it is the general question of what to do upon proven UB, and that
> is a topic discussed several years during Cauldron that it would be nice to
> have switches where users can choose what to do in that case,
> __builtin_unreachable (), __builtin_trap (), ... and another thing is where
> we should warn about it (tight e.g. to the __builtin_warning thing, because
> we don't want these warnings for dead code).
>
> So, e.g. if we had __builtin_warning (dunno where Martin S. is with that),
> we could e.g. queue a __builtin_warning and add __builtin_unreachable (or
> other possibilities), or e.g. during VRP just canonicalize proven always
> out of bound shifts to shifts by an out of bound constant and let some later
> pass warn and/or add __builtin_warning.
So the idea is to start funneling this through the path isolation code
and handle the various strategies there.

__builtin_warning is on hold pending a rework to make it act more like a
debug statement than a builtin function call.  The latter impacts
various heuristics, which would mean that it could impact codegen which
would highly undesirable.

jeff
>
> 	Jakub

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jakub Jelinek]

On Tue, Nov 17, 2020 at 09:54:46AM -0700, Jeff Law wrote:
> > So, e.g. if we had __builtin_warning (dunno where Martin S. is with that),
> > we could e.g. queue a __builtin_warning and add __builtin_unreachable (or
> > other possibilities), or e.g. during VRP just canonicalize proven always
> > out of bound shifts to shifts by an out of bound constant and let some later
> > pass warn and/or add __builtin_warning.
> So the idea is to start funneling this through the path isolation code
> and handle the various strategies there.

If the path isolation code would use the ranger for this, it wouldn't need
to be in VRP but could be anywhere, sure.

> __builtin_warning is on hold pending a rework to make it act more like a
> debug statement than a builtin function call.  The latter impacts
> various heuristics, which would mean that it could impact codegen which
> would highly undesirable.

Agreed on that.

	Jakub

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jeff Law]

On 11/17/20 9:58 AM, Jakub Jelinek wrote:
> On Tue, Nov 17, 2020 at 09:54:46AM -0700, Jeff Law wrote:
>>> So, e.g. if we had __builtin_warning (dunno where Martin S. is with that),
>>> we could e.g. queue a __builtin_warning and add __builtin_unreachable (or
>>> other possibilities), or e.g. during VRP just canonicalize proven always
>>> out of bound shifts to shifts by an out of bound constant and let some later
>>> pass warn and/or add __builtin_warning.
>> So the idea is to start funneling this through the path isolation code
>> and handle the various strategies there.
> If the path isolation code would use the ranger for this, it wouldn't need
> to be in VRP but could be anywhere, sure.
Good point.  I'll have to get used to having ranges available anywhere :-)

Jeff

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Philipp Tomsich]

Jeff & Jakub,

I went back to reread the C language standard and it turns out that the
delineation between defined and undefined is not as simple as I thought
that I remembered (see below).

On Tue, 17 Nov 2020 at 17:54, Jeff Law <law@redhat.com> wrote:

>
>
> On 11/17/20 9:46 AM, Jakub Jelinek wrote:
> > On Tue, Nov 17, 2020 at 05:29:57PM +0100, Philipp Tomsich wrote:
> >>>> In other words, the change to VRP canonicalizes what a lshift_expr
> with an
> >>>> shift-amount outside of the type width means... it doesn't assume
> anything
> >>>> about the original language.
> >>>> Do we assume that a LSHIFT_EXPR has the same semantics as for a
> >>>> C-language shift-left? If so, then pre should not generate the
> LSHIFT_EXPR
> >>>> for _9... or we might even catch this later in path isolation (as
> >>>> undefined
> >>>> behavior, insert a __builtin_trap() and emit a warning)?
> >>>>
> >>>> Note that in his comment to patch 2/2, Jim has noted that user code
> for
> >>>> RISC-V may assume a truncation of the shift-operand...
> >>> What I'd suggest doing would be to leave the invalid shift count in the
> >>> IL in VRP, then extend the erroneous path isolation code to turn an
> >>> invalid shift into a trap (conditionally of course).
> >> You had originally suggested to add this to VRP ...
> >> Given the various comments to this patch, do you still want any of
> >> this in VRP or
> >> would you rather see this only in path isolation?
> > Well, I said if we want to do it at all, it should be done in VRP,
> because
> > there is not really a difference between ((int) x) << 32 and ((int) x)
> << y
> > for y in [32, 137] etc.
> Right.  VRP is the right place to discover, but I'm not sure it's the
> right place to clean up the mess though.
>

The rules for E1 << E2 are:
  - if E2 is negative => undefined
  - if E1 is unsigned => E1 x 2^E2, reduced module one more than the
maximum representable value
  - if E1 is signed and non-negative => E1 x 2^E2, if E1 x 2^E2 is
representable; otherwise, undefined

So the test case is 'undefined' due to E2 being negative.
However, if it was a large positive number, the transform would be valid if
E1 is unsigned.

I would propose the following revision to this patch:
 1. tighten the logic in VRP to handle the case of E1 being unsigned and E2
being positive...
 2. catch the undefined case of E2 being negative in path isolation

Agreed?
Philipp.

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jakub Jelinek]

On Tue, Nov 17, 2020 at 06:23:51PM +0100, Philipp Tomsich wrote:
> The rules for E1 << E2 are:
>   - if E2 is negative => undefined
>   - if E1 is unsigned => E1 x 2^E2, reduced module one more than the
> maximum representable value
>   - if E1 is signed and non-negative => E1 x 2^E2, if E1 x 2^E2 is
> representable; otherwise, undefined

Those are rules about UB -fsanitize=shift-base diagnoses, and that greatly
differs between different languages and versions of those languages, and as
we don't really record what it comes from, for the GIMPLE IL everything is
well defined.
What we were talking about before is written earlier in the
"If the value of the right operand is negative or is
greater than or equal to the width of the promoted left operand, the behavior is
undefined."
sentence and is what -fsanitize=shift-exponent diagnoses.  In the GIMPLE IL
such shifts are still UB and in RTL only depending on some target macros
(i.e. undefined for some targets, wrapping with some mask or saturating on
others).

	Jakub

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jim Wilson]

On Tue, Nov 17, 2020 at 8:46 AM Jakub Jelinek via Gcc-patches <
gcc-patches@gcc.gnu.org> wrote:

> On Tue, Nov 17, 2020 at 05:29:57PM +0100, Philipp Tomsich wrote:
> > > > In other words, the change to VRP canonicalizes what a lshift_expr
> with an
> > > > shift-amount outside of the type width means... it doesn't assume
> anything
> > > > about the original language.
>
> Well, I said if we want to do it at all, it should be done in VRP, because
> there is not really a difference between ((int) x) << 32 and ((int) x) << y
> for y in [32, 137] etc.
>

How does this stuff interact with SHIFT_COUNT_TRUNCATED and
TARGET_SHIFT_TRUNCATION_MASK?  We already provide a mechanism to
truncate shift counts to fit based on how the hardware handles out-of-range
shift counts.  Handling out-of-range shift counts differently in VRP would
confuse things.  Maybe VRP should be using SHIFT_COUNT_TRUCNATED and/or
TARGET_SHIFT_TRUNCATION_MASK here?  Or maybe we give up on the shift
truncation macros?

Jim

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Jakub Jelinek]

On Tue, Nov 17, 2020 at 09:14:31AM -0800, Jim Wilson wrote:
> On Tue, Nov 17, 2020 at 8:46 AM Jakub Jelinek via Gcc-patches <
> gcc-patches@gcc.gnu.org> wrote:
> 
> > On Tue, Nov 17, 2020 at 05:29:57PM +0100, Philipp Tomsich wrote:
> > > > > In other words, the change to VRP canonicalizes what a lshift_expr
> > with an
> > > > > shift-amount outside of the type width means... it doesn't assume
> > anything
> > > > > about the original language.
> >
> > Well, I said if we want to do it at all, it should be done in VRP, because
> > there is not really a difference between ((int) x) << 32 and ((int) x) << y
> > for y in [32, 137] etc.
> >
> 
> How does this stuff interact with SHIFT_COUNT_TRUNCATED and
> TARGET_SHIFT_TRUNCATION_MASK?  We already provide a mechanism to
> truncate shift counts to fit based on how the hardware handles out-of-range
> shift counts.  Handling out-of-range shift counts differently in VRP would
> confuse things.  Maybe VRP should be using SHIFT_COUNT_TRUCNATED and/or
> TARGET_SHIFT_TRUNCATION_MASK here?  Or maybe we give up on the shift
> truncation macros?

Those are RTL only, aren't they?  So, in GIMPLE we can still (and already do
in various places) assume that out of bounds shifts are UB, and only in RTL
follow the rules of those macros/hooks, so only at the RTL level we can e.g.
optimize x << (y & 31) to x << y if the macros/hooks say the target handles
it that way.

	Jakub

Re: [PATCH v1 1/2] Simplify shifts wider than the bitwidth of types

[Philipp Tomsich]

Jeff,

On Tue, 17 Nov 2020 at 16:56, Jeff Law <law@redhat.com> wrote:
> > Note that in his comment to patch 2/2, Jim has noted that user code for
> > RISC-V may assume a truncation of the shift-operand...
> What I'd suggest doing would be to leave the invalid shift count in the
> IL in VRP, then extend the erroneous path isolation code to turn an
> invalid shift into a trap (conditionally of course).

As I remember, FORTRAN allows both LSHIFT(i, shift) or SHIFTL(i, shift) with
'shift' less than or equal to BITSIZE(i) ... this leaves i <<
BITSIZE(i) defined for
FORTRAN and undefined for C.

This seems to indicate that an LSHIFT_EXPR is intentionally not constrained
either to C language (or any other) semantics at this time.  To handle this in
path isolation, should we have different tree expressions for a
left-shift with C
semantics and one with FORTRAN semantics?

Philipp.