[PATCH 0/4] Fix shifts-assigns and avoid warns on deadcode

[PATCH 0/4] Fix shifts-assigns and avoid warns on deadcode

[Luc Van Oostenryck]

Sparse warns shifts by a negative or oversized amount but
it does this even on code that will not be executed. It's
annoying because such warnings are given for generic macros.

The strategy for these warnings is changed in patch 4:
they are delayed until after the elimination of deadcode.
This uncovered a bug in the type evaluation and the linearization
of shift-assigns which is now solved in patch 2 & 3.

Thanks to Stafford Horne to bring this back to my attention.

This series is available for testing & review at:
  git://git.kernel.org/pub/scm/devel/sparse/sparse.git bad-shift-equal


Luc Van Oostenryck (4):
  shift-assign: add more testcases for bogus linearization
  shift-assign: fix linearization of shift-assign
  shift-assign: restrict shift count to unsigned int
  bad-shift: wait dead code elimination to warn about bad shifts

 evaluate.c                         |  11 +-
 expand.c                           |  18 --
 linearize.c                        |  44 ++++
 simplify.c                         |  20 +-
 validation/expand/bad-shift.c      |   8 +-
 validation/linear/bug-assign-op0.c |   1 -
 validation/linear/shift-assign1.c  | 319 +++++++++++++++++++++++++++++
 validation/linear/shift-assign2.c  |  53 +++++
 validation/optim/shift-big.c       |  12 +-
 validation/shift-negative.c        |   4 +-
 validation/shift-undef-long.c      |   7 +-
 validation/shift-undef.c           |  52 ++---
 12 files changed, 462 insertions(+), 87 deletions(-)
 create mode 100644 validation/linear/shift-assign1.c
 create mode 100644 validation/linear/shift-assign2.c


base-commit: 4c6cbe557c48205f9b3d2aae4c166cd66446b240
-- 
2.28.0

[PATCH 1/4] shift-assign: add more testcases for bogus linearization

[Luc Van Oostenryck]

The usual conversions must not be applied to shifts.
This causes problems for shift-assigns.

So, add testcases for all combinations of size and signedness.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/linear/shift-assign1.c | 320 ++++++++++++++++++++++++++++++
 validation/linear/shift-assign2.c |  54 +++++
 2 files changed, 374 insertions(+)

diff --git a/validation/linear/shift-assign1.c b/validation/linear/shift-assign1.c
new file mode 100644
index 000000000000..9b3137bb2d04
--- /dev/null
+++ b/validation/linear/shift-assign1.c
@@ -0,0 +1,320 @@
+typedef  __INT16_TYPE__ s16;
+typedef  __INT32_TYPE__ s32;
+typedef  __INT64_TYPE__ s64;
+typedef __UINT16_TYPE__ u16;
+typedef __UINT32_TYPE__ u32;
+typedef __UINT64_TYPE__ u64;
+
+s16 s16s16(s16 a, s16 b) { a >>= b; return a; }
+s16 s16s32(s16 a, s32 b) { a >>= b; return a; }
+s16 s16s64(s16 a, s64 b) { a >>= b; return a; }
+s16 s16u16(s16 a, u16 b) { a >>= b; return a; }
+s16 s16u32(s16 a, u32 b) { a >>= b; return a; }
+s16 s16u64(s16 a, u64 b) { a >>= b; return a; }
+s32 s32s16(s32 a, s16 b) { a >>= b; return a; }
+s32 s32s32(s32 a, s32 b) { a >>= b; return a; }
+s32 s32s64(s32 a, s64 b) { a >>= b; return a; }
+s32 s32u16(s32 a, u16 b) { a >>= b; return a; }
+s32 s32u32(s32 a, u32 b) { a >>= b; return a; }
+s32 s32u64(s32 a, u64 b) { a >>= b; return a; }
+s64 s64s16(s64 a, s16 b);
+s64 s64s32(s64 a, s32 b);
+s64 s64s64(s64 a, s64 b) { a >>= b; return a; }
+s64 s64u16(s64 a, u16 b) { a >>= b; return a; }
+s64 s64u32(s64 a, u32 b) { a >>= b; return a; }
+s64 s64u64(s64 a, u64 b) { a >>= b; return a; }
+u16 u16s16(u16 a, s16 b) { a >>= b; return a; }
+u16 u16s32(u16 a, s32 b) { a >>= b; return a; }
+u16 u16s64(u16 a, s64 b) { a >>= b; return a; }
+u16 u16u16(u16 a, u16 b) { a >>= b; return a; }
+u16 u16u32(u16 a, u32 b) { a >>= b; return a; }
+u16 u16u64(u16 a, u64 b) { a >>= b; return a; }
+u32 u32s16(u32 a, s16 b) { a >>= b; return a; }
+u32 u32s32(u32 a, s32 b) { a >>= b; return a; }
+u32 u32s64(u32 a, s64 b) { a >>= b; return a; }
+u32 u32u16(u32 a, u16 b) { a >>= b; return a; }
+u32 u32u32(u32 a, u32 b) { a >>= b; return a; }
+u32 u32u64(u32 a, u64 b) { a >>= b; return a; }
+u64 u64s16(u64 a, s16 b);
+u64 u64s32(u64 a, s32 b);
+u64 u64s64(u64 a, s64 b) { a >>= b; return a; }
+u64 u64u16(u64 a, u16 b) { a >>= b; return a; }
+u64 u64u32(u64 a, u32 b) { a >>= b; return a; }
+u64 u64u64(u64 a, u64 b) { a >>= b; return a; }
+
+/*
+ * check-name: shift-assign1
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-start
+s16s16:
+.L0:
+	<entry-point>
+	sext.32     %r2 <- (16) %arg2
+	sext.32     %r4 <- (16) %arg1
+	asr.32      %r5 <- %r4, %r2
+	trunc.16    %r6 <- (32) %r5
+	ret.16      %r6
+
+
+s16s32:
+.L2:
+	<entry-point>
+	sext.32     %r11 <- (16) %arg1
+	asr.32      %r12 <- %r11, %arg2
+	trunc.16    %r13 <- (32) %r12
+	ret.16      %r13
+
+
+s16s64:
+.L4:
+	<entry-point>
+	trunc.32    %r17 <- (64) %arg2
+	sext.32     %r19 <- (16) %arg1
+	asr.32      %r20 <- %r19, %r17
+	trunc.16    %r21 <- (32) %r20
+	ret.16      %r21
+
+
+s16u16:
+.L6:
+	<entry-point>
+	zext.32     %r25 <- (16) %arg2
+	sext.32     %r27 <- (16) %arg1
+	asr.32      %r28 <- %r27, %r25
+	trunc.16    %r29 <- (32) %r28
+	ret.16      %r29
+
+
+s16u32:
+.L8:
+	<entry-point>
+	sext.32     %r34 <- (16) %arg1
+	asr.32      %r35 <- %r34, %arg2
+	trunc.16    %r36 <- (32) %r35
+	ret.16      %r36
+
+
+s16u64:
+.L10:
+	<entry-point>
+	trunc.32    %r40 <- (64) %arg2
+	sext.32     %r42 <- (16) %arg1
+	asr.32      %r43 <- %r42, %r40
+	trunc.16    %r44 <- (32) %r43
+	ret.16      %r44
+
+
+s32s16:
+.L12:
+	<entry-point>
+	sext.32     %r48 <- (16) %arg2
+	asr.32      %r50 <- %arg1, %r48
+	ret.32      %r50
+
+
+s32s32:
+.L14:
+	<entry-point>
+	asr.32      %r55 <- %arg1, %arg2
+	ret.32      %r55
+
+
+s32s64:
+.L16:
+	<entry-point>
+	trunc.32    %r59 <- (64) %arg2
+	asr.32      %r61 <- %arg1, %r59
+	ret.32      %r61
+
+
+s32u16:
+.L18:
+	<entry-point>
+	zext.32     %r65 <- (16) %arg2
+	asr.32      %r67 <- %arg1, %r65
+	ret.32      %r67
+
+
+s32u32:
+.L20:
+	<entry-point>
+	asr.32      %r72 <- %arg1, %arg2
+	ret.32      %r72
+
+
+s32u64:
+.L22:
+	<entry-point>
+	trunc.32    %r76 <- (64) %arg2
+	asr.32      %r78 <- %arg1, %r76
+	ret.32      %r78
+
+
+s64s64:
+.L24:
+	<entry-point>
+	asr.64      %r83 <- %arg1, %arg2
+	ret.64      %r83
+
+
+s64u16:
+.L26:
+	<entry-point>
+	zext.64     %r88 <- (16) %arg2
+	asr.64      %r90 <- %arg1, %r88
+	ret.64      %r90
+
+
+s64u32:
+.L28:
+	<entry-point>
+	zext.64     %r94 <- (32) %arg2
+	asr.64      %r96 <- %arg1, %r94
+	ret.64      %r96
+
+
+s64u64:
+.L30:
+	<entry-point>
+	asr.64      %r101 <- %arg1, %arg2
+	ret.64      %r101
+
+
+u16s16:
+.L32:
+	<entry-point>
+	sext.32     %r105 <- (16) %arg2
+	zext.32     %r107 <- (16) %arg1
+	asr.32      %r108 <- %r107, %r105
+	trunc.16    %r109 <- (32) %r108
+	ret.16      %r109
+
+
+u16s32:
+.L34:
+	<entry-point>
+	zext.32     %r114 <- (16) %arg1
+	asr.32      %r115 <- %r114, %arg2
+	trunc.16    %r116 <- (32) %r115
+	ret.16      %r116
+
+
+u16s64:
+.L36:
+	<entry-point>
+	trunc.32    %r120 <- (64) %arg2
+	zext.32     %r122 <- (16) %arg1
+	asr.32      %r123 <- %r122, %r120
+	trunc.16    %r124 <- (32) %r123
+	ret.16      %r124
+
+
+u16u16:
+.L38:
+	<entry-point>
+	zext.32     %r128 <- (16) %arg2
+	zext.32     %r130 <- (16) %arg1
+	asr.32      %r131 <- %r130, %r128
+	trunc.16    %r132 <- (32) %r131
+	ret.16      %r132
+
+
+u16u32:
+.L40:
+	<entry-point>
+	zext.32     %r137 <- (16) %arg1
+	asr.32      %r138 <- %r137, %arg2
+	trunc.16    %r139 <- (32) %r138
+	ret.16      %r139
+
+
+u16u64:
+.L42:
+	<entry-point>
+	trunc.32    %r143 <- (64) %arg2
+	zext.32     %r145 <- (16) %arg1
+	asr.32      %r146 <- %r145, %r143
+	trunc.16    %r147 <- (32) %r146
+	ret.16      %r147
+
+
+u32s16:
+.L44:
+	<entry-point>
+	sext.32     %r151 <- (16) %arg2
+	lsr.32      %r153 <- %arg1, %r151
+	ret.32      %r153
+
+
+u32s32:
+.L46:
+	<entry-point>
+	lsr.32      %r158 <- %arg1, %arg2
+	ret.32      %r158
+
+
+u32s64:
+.L48:
+	<entry-point>
+	trunc.32    %r162 <- (64) %arg2
+	lsr.32      %r164 <- %arg1, %r162
+	ret.32      %r164
+
+
+u32u16:
+.L50:
+	<entry-point>
+	zext.32     %r168 <- (16) %arg2
+	lsr.32      %r170 <- %arg1, %r168
+	ret.32      %r170
+
+
+u32u32:
+.L52:
+	<entry-point>
+	lsr.32      %r175 <- %arg1, %arg2
+	ret.32      %r175
+
+
+u32u64:
+.L54:
+	<entry-point>
+	trunc.32    %r179 <- (64) %arg2
+	lsr.32      %r181 <- %arg1, %r179
+	ret.32      %r181
+
+
+u64s64:
+.L56:
+	<entry-point>
+	lsr.64      %r186 <- %arg1, %arg2
+	ret.64      %r186
+
+
+u64u16:
+.L58:
+	<entry-point>
+	zext.64     %r191 <- (16) %arg2
+	lsr.64      %r193 <- %arg1, %r191
+	ret.64      %r193
+
+
+u64u32:
+.L60:
+	<entry-point>
+	zext.64     %r197 <- (32) %arg2
+	lsr.64      %r199 <- %arg1, %r197
+	ret.64      %r199
+
+
+u64u64:
+.L62:
+	<entry-point>
+	lsr.64      %r204 <- %arg1, %arg2
+	ret.64      %r204
+
+
+ * check-output-end
+ */
diff --git a/validation/linear/shift-assign2.c b/validation/linear/shift-assign2.c
new file mode 100644
index 000000000000..30d74376478e
--- /dev/null
+++ b/validation/linear/shift-assign2.c
@@ -0,0 +1,54 @@
+typedef  __INT16_TYPE__ s16;
+typedef  __INT32_TYPE__ s32;
+typedef  __INT64_TYPE__ s64;
+typedef __UINT16_TYPE__ u16;
+typedef __UINT32_TYPE__ u32;
+typedef __UINT64_TYPE__ u64;
+
+s64 s64s16(s64 a, s16 b) { a >>= b; return a; }
+s64 s64s32(s64 a, s32 b) { a >>= b; return a; }
+u64 u64s16(u64 a, s16 b) { a >>= b; return a; }
+u64 u64s32(u64 a, s32 b) { a >>= b; return a; }
+
+/*
+ * check-name: shift-assign2
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-start
+s64s16:
+.L0:
+	<entry-point>
+	sext.32     %r2 <- (16) %arg2
+	zext.64     %r3 <- (32) %r2
+	asr.64      %r5 <- %arg1, %r3
+	ret.64      %r5
+
+
+s64s32:
+.L2:
+	<entry-point>
+	zext.64     %r9 <- (32) %arg2
+	asr.64      %r11 <- %arg1, %r9
+	ret.64      %r11
+
+
+u64s16:
+.L4:
+	<entry-point>
+	sext.32     %r15 <- (16) %arg2
+	zext.64     %r16 <- (32) %r15
+	lsr.64      %r18 <- %arg1, %r16
+	ret.64      %r18
+
+
+u64s32:
+.L6:
+	<entry-point>
+	zext.64     %r22 <- (32) %arg2
+	lsr.64      %r24 <- %arg1, %r22
+	ret.64      %r24
+
+
+ * check-output-end
+ */
-- 
2.28.0

[PATCH 2/4] shift-assign: fix linearization of shift-assign

[Luc Van Oostenryck]

The result of a shift-assigns has the same type as the left
operand but the shift itself must be done on the promoted type.
The usual conversions are not done for shifts.

The problem is that this promoted type is not stored explicitly
in the data structure.  This is specific to shift-assigns because
for other operations, for example add-assign, the usual conversions
must be done and the resulting type can be found on the RHS.

Since at linearization, the LHS and the RHS must have the same type,
the solution is to cast the RHS to LHS's promoted type during
evaluation.

This solve a bunch of problems with shift-assigns, like doing
logical shift when an arithmetic shift was needed.

Fixes: efdefb100d086aaabf20d475c3d1a65cbceeb534
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 evaluate.c                         |  6 +++++-
 validation/linear/bug-assign-op0.c |  1 -
 validation/linear/shift-assign1.c  |  1 -
 validation/shift-undef.c           | 16 ++++++++--------
 4 files changed, 13 insertions(+), 11 deletions(-)

diff --git a/evaluate.c b/evaluate.c
index dddea76182ad..6d8ecd7f6c25 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -1342,8 +1342,12 @@ static int evaluate_assign_op(struct expression *expr)
 				return 1;
 		} else if (op == SPECIAL_SHR_ASSIGN || op == SPECIAL_SHL_ASSIGN) {
 			// shifts do integer promotions, but that's it.
+			unrestrict(expr->left, tclass, &t);
+			target = integer_promotion(t);
+
 			unrestrict(expr->right, sclass, &s);
-			target = integer_promotion(s);
+			source = integer_promotion(s);
+			expr->right = cast_to(expr->right, source);
 			goto Cast;
 		} else if (!(sclass & TYPE_RESTRICT))
 			goto usual;
diff --git a/validation/linear/bug-assign-op0.c b/validation/linear/bug-assign-op0.c
index 0cabc6222b8a..b351bb5149be 100644
--- a/validation/linear/bug-assign-op0.c
+++ b/validation/linear/bug-assign-op0.c
@@ -46,7 +46,6 @@ unsigned int sldivu(unsigned int u, long s)
 /*
  * check-name: bug-assign-op0
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-start
 asr:
diff --git a/validation/linear/shift-assign1.c b/validation/linear/shift-assign1.c
index 9b3137bb2d04..4c96fc283121 100644
--- a/validation/linear/shift-assign1.c
+++ b/validation/linear/shift-assign1.c
@@ -45,7 +45,6 @@ u64 u64u64(u64 a, u64 b) { a >>= b; return a; }
 /*
  * check-name: shift-assign1
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-start
 s16s16:
diff --git a/validation/shift-undef.c b/validation/shift-undef.c
index 4e94fa23d122..613c6b95b113 100644
--- a/validation/shift-undef.c
+++ b/validation/shift-undef.c
@@ -140,23 +140,23 @@ shift-undef.c:32:11: warning: shift too big (100) for type int
 shift-undef.c:33:11: warning: shift too big (101) for type unsigned int
 shift-undef.c:34:11: warning: shift too big (102) for type unsigned int
 shift-undef.c:35:11: warning: shift count is negative (-1)
-shift-undef.c:36:11: warning: shift count is negative (-2)
-shift-undef.c:37:11: warning: shift count is negative (-3)
+shift-undef.c:36:11: warning: shift too big (4294967294) for type unsigned int
+shift-undef.c:37:11: warning: shift too big (4294967293) for type unsigned int
 shift-undef.c:38:25: warning: shift too big (103) for type int
 shift-undef.c:39:25: warning: shift too big (104) for type unsigned int
 shift-undef.c:40:25: warning: shift too big (105) for type unsigned int
 shift-undef.c:41:25: warning: shift count is negative (-4)
-shift-undef.c:42:25: warning: shift count is negative (-5)
-shift-undef.c:43:25: warning: shift count is negative (-6)
+shift-undef.c:42:25: warning: shift too big (4294967291) for type unsigned int
+shift-undef.c:43:25: warning: shift too big (4294967290) for type unsigned int
 shift-undef.c:44:30: warning: shift too big (106) for type int
 shift-undef.c:45:30: warning: shift too big (107) for type unsigned int
 shift-undef.c:46:30: warning: shift too big (108) for type unsigned int
 shift-undef.c:47:30: warning: shift count is negative (-7)
-shift-undef.c:48:30: warning: shift count is negative (-8)
-shift-undef.c:49:30: warning: shift count is negative (-9)
+shift-undef.c:48:30: warning: shift too big (4294967288) for type unsigned int
+shift-undef.c:49:30: warning: shift too big (4294967287) for type unsigned int
 shift-undef.c:50:26: warning: shift too big (109) for type int
-shift-undef.c:51:26: warning: shift too big (110) for type int
-shift-undef.c:52:26: warning: shift too big (111) for type int
+shift-undef.c:51:26: warning: shift too big (110) for type unsigned int
+shift-undef.c:52:26: warning: shift too big (111) for type unsigned int
 shift-undef.c:53:26: warning: shift count is negative (-10)
 shift-undef.c:54:26: warning: shift count is negative (-11)
 shift-undef.c:55:26: warning: shift count is negative (-12)
-- 
2.28.0

[PATCH 3/4] shift-assign: restrict shift count to unsigned int

[Luc Van Oostenryck]

After the RHS of shift-assigns had been integer-promoted,
both gcc & clang seems to restrict it to an unsigned int.
This only make a difference when the shift count is negative
and would it make it UB.

Better to have the same generated code, so make the same here.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 evaluate.c                        | 5 +++++
 validation/linear/shift-assign2.c | 1 -
 2 files changed, 5 insertions(+), 1 deletion(-)

diff --git a/evaluate.c b/evaluate.c
index 6d8ecd7f6c25..a9adc72f6b57 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -1348,6 +1348,11 @@ static int evaluate_assign_op(struct expression *expr)
 			unrestrict(expr->right, sclass, &s);
 			source = integer_promotion(s);
 			expr->right = cast_to(expr->right, source);
+
+			// both gcc & clang seems to do this, so ...
+			if (target->bit_size > source->bit_size)
+				expr->right = cast_to(expr->right, &uint_ctype);
+
 			goto Cast;
 		} else if (!(sclass & TYPE_RESTRICT))
 			goto usual;
diff --git a/validation/linear/shift-assign2.c b/validation/linear/shift-assign2.c
index 30d74376478e..9990ac38e800 100644
--- a/validation/linear/shift-assign2.c
+++ b/validation/linear/shift-assign2.c
@@ -13,7 +13,6 @@ u64 u64s32(u64 a, s32 b) { a >>= b; return a; }
 /*
  * check-name: shift-assign2
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-start
 s64s16:
-- 
2.28.0

[PATCH 4/4] bad-shift: wait dead code elimination to warn about bad shifts

[Luc Van Oostenryck]

Sparse complains when a shift amount is too big for the size
of its operand or if it's negative.

However, it does this even for expressions that are never evaluated.
It's especially annoying in the kernel for type generic macros,
for example the ones in arch/*/include/asm/cmpxchg.h

So, remove all warnings done at expansion time and avoid any
simplifications of such expressions. Same, at linearization
and optimization time but in this case mark the instructions as
'tainted' to inhibit any further simplifications. Finally, at the
end of the optimization phase, warn for the tainted instructions.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 expand.c                      | 18 -------------
 linearize.c                   | 44 ++++++++++++++++++++++++++++++++
 simplify.c                    | 20 ++++-----------
 validation/expand/bad-shift.c |  8 +++---
 validation/optim/shift-big.c  | 12 ++++++---
 validation/shift-negative.c   |  4 +--
 validation/shift-undef-long.c |  7 +++--
 validation/shift-undef.c      | 48 +++++++++--------------------------
 8 files changed, 78 insertions(+), 83 deletions(-)

diff --git a/expand.c b/expand.c
index b07893318382..623b180025ad 100644
--- a/expand.c
+++ b/expand.c
@@ -170,22 +170,6 @@ Float:
 	expr->type = EXPR_FVALUE;
 }
 
-static void warn_shift_count(struct expression *expr, struct symbol *ctype, long long count)
-{
-	if (count < 0) {
-		if (!Wshift_count_negative)
-			return;
-		warning(expr->pos, "shift count is negative (%lld)", count);
-		return;
-	}
-	if (ctype->type == SYM_NODE)
-		ctype = ctype->ctype.base_type;
-
-	if (!Wshift_count_overflow)
-		return;
-	warning(expr->pos, "shift too big (%llu) for type %s", count, show_typename(ctype));
-}
-
 /* Return true if constant shift size is valid */
 static bool check_shift_count(struct expression *expr, struct expression *right)
 {
@@ -194,8 +178,6 @@ static bool check_shift_count(struct expression *expr, struct expression *right)
 
 	if (count >= 0 && count < ctype->bit_size)
 		return true;
-	if (!conservative)
-		warn_shift_count(expr, ctype, count);
 	return false;
 }
 
diff --git a/linearize.c b/linearize.c
index 4927468183b0..5a8e74970d98 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2468,6 +2468,49 @@ static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stm
 	return VOID;
 }
 
+static void check_tainted_insn(struct instruction *insn)
+{
+	unsigned long long uval;
+	long long sval;
+	pseudo_t src2;
+
+	switch (insn->opcode) {
+	case OP_DIVU: case OP_DIVS:
+	case OP_MODU: case OP_MODS:
+		if (insn->src2 == value_pseudo(0))
+			warning(insn->pos, "divide by zero");
+		break;
+	case OP_SHL: case OP_LSR: case OP_ASR:
+		src2 = insn->src2;
+		if (src2->type != PSEUDO_VAL)
+			break;
+		uval = src2->value;
+		if (uval < insn->size)
+			break;
+		sval = sign_extend(uval, insn->size);
+		if (Wshift_count_negative && sval < 0)
+			warning(insn->pos, "shift count is negative (%lld)", sval);
+		else if (Wshift_count_overflow)
+			warning(insn->pos, "shift too big (%llu) for type %s", uval, show_typename(insn->type));
+	}
+}
+
+///
+// issue warnings after all possible DCE
+static void late_warnings(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+	FOR_EACH_PTR(ep->bbs, bb) {
+		struct instruction *insn;
+		FOR_EACH_PTR(bb->insns, insn) {
+			if (!insn->bb)
+				continue;
+			if (insn->tainted)
+				check_tainted_insn(insn);
+		} END_FOR_EACH_PTR(insn);
+	} END_FOR_EACH_PTR(bb);
+}
+
 static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
 {
 	struct statement *stmt = base_type->stmt;
@@ -2514,6 +2557,7 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	add_one_insn(ep, ret);
 
 	optimize(ep);
+	late_warnings(ep);
 	return ep;
 }
 
diff --git a/simplify.c b/simplify.c
index 7850bcdc6069..f6b79685f439 100644
--- a/simplify.c
+++ b/simplify.c
@@ -754,28 +754,18 @@ static long long check_shift_count(struct instruction *insn, unsigned long long
 	unsigned int size = insn->size;
 	long long sval = uval;
 
+	if (insn->tainted)
+		return -1;
+
 	if (uval < size)
 		return uval;
 
+	insn->tainted = 1;
 	sval = sign_extend_safe(sval, size);
 	sval = sign_extend_safe(sval, bits_in_int);
 	if (sval < 0)
 		insn->src2 = value_pseudo(sval);
-	if (insn->tainted)
-		return sval;
-
-	if (sval < 0 && Wshift_count_negative)
-		warning(insn->pos, "shift count is negative (%lld)", sval);
-	if (sval > 0 && Wshift_count_overflow) {
-		struct symbol *ctype = insn->type;
-		const char *tname;
-		if (ctype->type == SYM_NODE)
-			ctype = ctype->ctype.base_type;
-		tname = show_typename(ctype);
-		warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
-	}
-	insn->tainted = 1;
-	return sval;
+	return -1;
 }
 
 static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
diff --git a/validation/expand/bad-shift.c b/validation/expand/bad-shift.c
index 22c4341f1680..b68866c2b048 100644
--- a/validation/expand/bad-shift.c
+++ b/validation/expand/bad-shift.c
@@ -56,9 +56,9 @@ rneg:
  * check-output-end
  *
  * check-error-start
-expand/bad-shift.c:5:18: warning: shift too big (32) for type int
-expand/bad-shift.c:10:18: warning: shift count is negative (-1)
-expand/bad-shift.c:15:18: warning: shift too big (32) for type int
-expand/bad-shift.c:20:18: warning: shift count is negative (-1)
+expand/bad-shift.c:5:21: warning: shift too big (32) for type int
+expand/bad-shift.c:10:21: warning: shift count is negative (-1)
+expand/bad-shift.c:15:21: warning: shift too big (32) for type int
+expand/bad-shift.c:20:21: warning: shift count is negative (-1)
  * check-error-end
  */
diff --git a/validation/optim/shift-big.c b/validation/optim/shift-big.c
index 84bcd2ce01a3..e7bf22fe36ff 100644
--- a/validation/optim/shift-big.c
+++ b/validation/optim/shift-big.c
@@ -50,13 +50,15 @@ lsr31:
 lsr32:
 .L8:
 	<entry-point>
-	ret.32      $0
+	lsr.32      %r14 <- %arg1, $32
+	ret.32      %r14
 
 
 lsr33:
 .L10:
 	<entry-point>
-	ret.32      $0
+	lsr.32      %r17 <- %arg1, $33
+	ret.32      %r17
 
 
 shl31:
@@ -69,13 +71,15 @@ shl31:
 shl32:
 .L14:
 	<entry-point>
-	ret.32      $0
+	shl.32      %r23 <- %arg1, $32
+	ret.32      %r23
 
 
 shl33:
 .L16:
 	<entry-point>
-	ret.32      $0
+	shl.32      %r26 <- %arg1, $33
+	ret.32      %r26
 
 
  * check-output-end
diff --git a/validation/shift-negative.c b/validation/shift-negative.c
index fff5cf123dd6..6df02b18468f 100644
--- a/validation/shift-negative.c
+++ b/validation/shift-negative.c
@@ -9,8 +9,8 @@ unsigned int fo2(unsigned int a) { return a >> ((a & 0) ^ ~0); }
  * check-command: sparse -Wno-decl $file
  *
  * check-error-start
-shift-negative.c:1:45: warning: shift count is negative (-1)
-shift-negative.c:2:45: warning: shift count is negative (-1)
+shift-negative.c:1:48: warning: shift count is negative (-1)
+shift-negative.c:2:48: warning: shift count is negative (-1)
 shift-negative.c:4:59: warning: shift count is negative (-1)
 shift-negative.c:5:59: warning: shift count is negative (-1)
  * check-error-end
diff --git a/validation/shift-undef-long.c b/validation/shift-undef-long.c
index 326267436ec7..985fe4c4c595 100644
--- a/validation/shift-undef-long.c
+++ b/validation/shift-undef-long.c
@@ -13,9 +13,8 @@ static unsigned very_big_shift(unsigned int a)
  * check-command: sparse -m64 $file
  *
  * check-error-start
-shift-undef-long.c:4:16: warning: shift too big (4294967295) for type unsigned int
-shift-undef-long.c:5:16: warning: shift too big (4294967296) for type unsigned int
-shift-undef-long.c:6:16: warning: shift too big (4294967296) for type unsigned int
-shift-undef-long.c:7:16: warning: shift count is negative (-4294967296)
+shift-undef-long.c:4:25: warning: shift count is negative (-1)
+shift-undef-long.c:5:47: warning: shift too big (4294967296) for type unsigned int
+shift-undef-long.c:7:20: warning: shift count is negative (-4294967296)
  * check-error-end
  */
diff --git a/validation/shift-undef.c b/validation/shift-undef.c
index 613c6b95b113..0c7541e9ffd9 100644
--- a/validation/shift-undef.c
+++ b/validation/shift-undef.c
@@ -112,48 +112,24 @@ void hw_write(u32 val)
  * check-command: sparse -Wno-decl $file
  *
  * check-error-start
-shift-undef.c:3:15: warning: shift too big (100) for type int
-shift-undef.c:4:15: warning: shift too big (101) for type unsigned int
-shift-undef.c:5:15: warning: shift too big (102) for type unsigned int
-shift-undef.c:6:15: warning: shift count is negative (-1)
-shift-undef.c:7:15: warning: shift count is negative (-2)
-shift-undef.c:8:15: warning: shift count is negative (-3)
-shift-undef.c:9:25: warning: shift too big (103) for type int
-shift-undef.c:10:25: warning: shift too big (104) for type unsigned int
-shift-undef.c:11:25: warning: shift too big (105) for type unsigned int
-shift-undef.c:12:25: warning: shift count is negative (-4)
-shift-undef.c:13:25: warning: shift count is negative (-5)
-shift-undef.c:14:25: warning: shift count is negative (-6)
-shift-undef.c:15:30: warning: shift too big (106) for type int
-shift-undef.c:16:30: warning: shift too big (107) for type unsigned int
-shift-undef.c:17:30: warning: shift too big (108) for type unsigned int
-shift-undef.c:18:30: warning: shift count is negative (-7)
-shift-undef.c:19:30: warning: shift count is negative (-8)
-shift-undef.c:20:30: warning: shift count is negative (-9)
+shift-undef.c:3:18: warning: shift too big (100) for type int
+shift-undef.c:4:18: warning: shift too big (101) for type unsigned int
+shift-undef.c:5:18: warning: shift too big (102) for type unsigned int
+shift-undef.c:6:19: warning: shift count is negative (-1)
+shift-undef.c:7:19: warning: shift count is negative (-2)
+shift-undef.c:8:19: warning: shift count is negative (-3)
 shift-undef.c:21:29: warning: shift too big (109) for type int
 shift-undef.c:22:29: warning: shift too big (110) for type unsigned int
 shift-undef.c:23:29: warning: shift too big (111) for type unsigned int
 shift-undef.c:24:29: warning: shift count is negative (-10)
 shift-undef.c:25:29: warning: shift count is negative (-11)
 shift-undef.c:26:29: warning: shift count is negative (-12)
-shift-undef.c:32:11: warning: shift too big (100) for type int
-shift-undef.c:33:11: warning: shift too big (101) for type unsigned int
-shift-undef.c:34:11: warning: shift too big (102) for type unsigned int
-shift-undef.c:35:11: warning: shift count is negative (-1)
-shift-undef.c:36:11: warning: shift too big (4294967294) for type unsigned int
-shift-undef.c:37:11: warning: shift too big (4294967293) for type unsigned int
-shift-undef.c:38:25: warning: shift too big (103) for type int
-shift-undef.c:39:25: warning: shift too big (104) for type unsigned int
-shift-undef.c:40:25: warning: shift too big (105) for type unsigned int
-shift-undef.c:41:25: warning: shift count is negative (-4)
-shift-undef.c:42:25: warning: shift too big (4294967291) for type unsigned int
-shift-undef.c:43:25: warning: shift too big (4294967290) for type unsigned int
-shift-undef.c:44:30: warning: shift too big (106) for type int
-shift-undef.c:45:30: warning: shift too big (107) for type unsigned int
-shift-undef.c:46:30: warning: shift too big (108) for type unsigned int
-shift-undef.c:47:30: warning: shift count is negative (-7)
-shift-undef.c:48:30: warning: shift too big (4294967288) for type unsigned int
-shift-undef.c:49:30: warning: shift too big (4294967287) for type unsigned int
+shift-undef.c:32:15: warning: shift too big (100) for type int
+shift-undef.c:33:15: warning: shift too big (101) for type unsigned int
+shift-undef.c:34:15: warning: shift too big (102) for type unsigned int
+shift-undef.c:35:16: warning: shift count is negative (-1)
+shift-undef.c:36:16: warning: shift count is negative (-2)
+shift-undef.c:37:16: warning: shift count is negative (-3)
 shift-undef.c:50:26: warning: shift too big (109) for type int
 shift-undef.c:51:26: warning: shift too big (110) for type unsigned int
 shift-undef.c:52:26: warning: shift too big (111) for type unsigned int
-- 
2.28.0

Re: [PATCH 4/4] bad-shift: wait dead code elimination to warn about bad shifts

[Stafford Horne]

On Thu, Aug 06, 2020 at 09:30:03PM +0200, Luc Van Oostenryck wrote:
> Sparse complains when a shift amount is too big for the size
> of its operand or if it's negative.
> 
> However, it does this even for expressions that are never evaluated.
> It's especially annoying in the kernel for type generic macros,
> for example the ones in arch/*/include/asm/cmpxchg.h
> 
> So, remove all warnings done at expansion time and avoid any
> simplifications of such expressions. Same, at linearization
> and optimization time but in this case mark the instructions as
> 'tainted' to inhibit any further simplifications. Finally, at the
> end of the optimization phase, warn for the tainted instructions.
> 
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  expand.c                      | 18 -------------
>  linearize.c                   | 44 ++++++++++++++++++++++++++++++++
>  simplify.c                    | 20 ++++-----------
>  validation/expand/bad-shift.c |  8 +++---
>  validation/optim/shift-big.c  | 12 ++++++---
>  validation/shift-negative.c   |  4 +--
>  validation/shift-undef-long.c |  7 +++--
>  validation/shift-undef.c      | 48 +++++++++--------------------------
>  8 files changed, 78 insertions(+), 83 deletions(-)
> 
> diff --git a/expand.c b/expand.c
> index b07893318382..623b180025ad 100644
> --- a/expand.c
> +++ b/expand.c
> @@ -170,22 +170,6 @@ Float:
>  	expr->type = EXPR_FVALUE;
>  }
>  
> -static void warn_shift_count(struct expression *expr, struct symbol *ctype, long long count)
> -{
> -	if (count < 0) {
> -		if (!Wshift_count_negative)
> -			return;
> -		warning(expr->pos, "shift count is negative (%lld)", count);
> -		return;
> -	}
> -	if (ctype->type == SYM_NODE)
> -		ctype = ctype->ctype.base_type;
> -
> -	if (!Wshift_count_overflow)
> -		return;
> -	warning(expr->pos, "shift too big (%llu) for type %s", count, show_typename(ctype));
> -}
> -
>  /* Return true if constant shift size is valid */
>  static bool check_shift_count(struct expression *expr, struct expression *right)
>  {
> @@ -194,8 +178,6 @@ static bool check_shift_count(struct expression *expr, struct expression *right)
>  
>  	if (count >= 0 && count < ctype->bit_size)
>  		return true;
> -	if (!conservative)
> -		warn_shift_count(expr, ctype, count);
>  	return false;
>  }
>  
> diff --git a/linearize.c b/linearize.c
> index 4927468183b0..5a8e74970d98 100644
> --- a/linearize.c
> +++ b/linearize.c
> @@ -2468,6 +2468,49 @@ static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stm
>  	return VOID;
>  }
>  
> +static void check_tainted_insn(struct instruction *insn)
> +{
> +	unsigned long long uval;
> +	long long sval;
> +	pseudo_t src2;
> +
> +	switch (insn->opcode) {
> +	case OP_DIVU: case OP_DIVS:
> +	case OP_MODU: case OP_MODS:
> +		if (insn->src2 == value_pseudo(0))
> +			warning(insn->pos, "divide by zero");
> +		break;

Is this divide by zero a new check?  I get the shift, but is this new?

> +	case OP_SHL: case OP_LSR: case OP_ASR:
> +		src2 = insn->src2;
> +		if (src2->type != PSEUDO_VAL)
> +			break;
> +		uval = src2->value;
> +		if (uval < insn->size)
> +			break;
> +		sval = sign_extend(uval, insn->size);
> +		if (Wshift_count_negative && sval < 0)
> +			warning(insn->pos, "shift count is negative (%lld)", sval);
> +		else if (Wshift_count_overflow)
> +			warning(insn->pos, "shift too big (%llu) for type %s", uval, show_typename(insn->type));

Makes sense.

> +	}
> +}
> +
> +///
> +// issue warnings after all possible DCE
> +static void late_warnings(struct entrypoint *ep)
> +{
> +	struct basic_block *bb;
> +	FOR_EACH_PTR(ep->bbs, bb) {
> +		struct instruction *insn;
> +		FOR_EACH_PTR(bb->insns, insn) {
> +			if (!insn->bb)
> +				continue;
> +			if (insn->tainted)
> +				check_tainted_insn(insn);
> +		} END_FOR_EACH_PTR(insn);
> +	} END_FOR_EACH_PTR(bb);
> +}
> +
>  static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
>  {
>  	struct statement *stmt = base_type->stmt;
> @@ -2514,6 +2557,7 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
>  	add_one_insn(ep, ret);
>  
>  	optimize(ep);
> +	late_warnings(ep);
>  	return ep;
>  }
>  
> diff --git a/simplify.c b/simplify.c
> index 7850bcdc6069..f6b79685f439 100644
> --- a/simplify.c
> +++ b/simplify.c
> @@ -754,28 +754,18 @@ static long long check_shift_count(struct instruction *insn, unsigned long long
>  	unsigned int size = insn->size;
>  	long long sval = uval;
>  
> +	if (insn->tainted)
> +		return -1;
> +
>  	if (uval < size)
>  		return uval;
>  
> +	insn->tainted = 1;
>  	sval = sign_extend_safe(sval, size);
>  	sval = sign_extend_safe(sval, bits_in_int);
>  	if (sval < 0)
>  		insn->src2 = value_pseudo(sval);
> -	if (insn->tainted)
> -		return sval;
> -
> -	if (sval < 0 && Wshift_count_negative)
> -		warning(insn->pos, "shift count is negative (%lld)", sval);
> -	if (sval > 0 && Wshift_count_overflow) {
> -		struct symbol *ctype = insn->type;
> -		const char *tname;
> -		if (ctype->type == SYM_NODE)
> -			ctype = ctype->ctype.base_type;
> -		tname = show_typename(ctype);
> -		warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
> -	}
> -	insn->tainted = 1;
> -	return sval;
> +	return -1;
>  }
>  
>  static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
> diff --git a/validation/expand/bad-shift.c b/validation/expand/bad-shift.c
> index 22c4341f1680..b68866c2b048 100644
> --- a/validation/expand/bad-shift.c
> +++ b/validation/expand/bad-shift.c
> @@ -56,9 +56,9 @@ rneg:
>   * check-output-end
>   *
>   * check-error-start
> -expand/bad-shift.c:5:18: warning: shift too big (32) for type int
> -expand/bad-shift.c:10:18: warning: shift count is negative (-1)
> -expand/bad-shift.c:15:18: warning: shift too big (32) for type int
> -expand/bad-shift.c:20:18: warning: shift count is negative (-1)
> +expand/bad-shift.c:5:21: warning: shift too big (32) for type int
> +expand/bad-shift.c:10:21: warning: shift count is negative (-1)
> +expand/bad-shift.c:15:21: warning: shift too big (32) for type int
> +expand/bad-shift.c:20:21: warning: shift count is negative (-1)
>   * check-error-end
>   */
> diff --git a/validation/optim/shift-big.c b/validation/optim/shift-big.c
> index 84bcd2ce01a3..e7bf22fe36ff 100644
> --- a/validation/optim/shift-big.c
> +++ b/validation/optim/shift-big.c
> @@ -50,13 +50,15 @@ lsr31:
>  lsr32:
>  .L8:
>  	<entry-point>
> -	ret.32      $0
> +	lsr.32      %r14 <- %arg1, $32
> +	ret.32      %r14
>  
>  
>  lsr33:
>  .L10:
>  	<entry-point>
> -	ret.32      $0
> +	lsr.32      %r17 <- %arg1, $33
> +	ret.32      %r17
>  
>  
>  shl31:
> @@ -69,13 +71,15 @@ shl31:
>  shl32:
>  .L14:
>  	<entry-point>
> -	ret.32      $0
> +	shl.32      %r23 <- %arg1, $32
> +	ret.32      %r23
>  
>  
>  shl33:
>  .L16:
>  	<entry-point>
> -	ret.32      $0
> +	shl.32      %r26 <- %arg1, $33
> +	ret.32      %r26
>  
>  
>   * check-output-end
> diff --git a/validation/shift-negative.c b/validation/shift-negative.c
> index fff5cf123dd6..6df02b18468f 100644
> --- a/validation/shift-negative.c
> +++ b/validation/shift-negative.c
> @@ -9,8 +9,8 @@ unsigned int fo2(unsigned int a) { return a >> ((a & 0) ^ ~0); }
>   * check-command: sparse -Wno-decl $file
>   *
>   * check-error-start
> -shift-negative.c:1:45: warning: shift count is negative (-1)
> -shift-negative.c:2:45: warning: shift count is negative (-1)
> +shift-negative.c:1:48: warning: shift count is negative (-1)
> +shift-negative.c:2:48: warning: shift count is negative (-1)
>  shift-negative.c:4:59: warning: shift count is negative (-1)
>  shift-negative.c:5:59: warning: shift count is negative (-1)
>   * check-error-end
> diff --git a/validation/shift-undef-long.c b/validation/shift-undef-long.c
> index 326267436ec7..985fe4c4c595 100644
> --- a/validation/shift-undef-long.c
> +++ b/validation/shift-undef-long.c
> @@ -13,9 +13,8 @@ static unsigned very_big_shift(unsigned int a)
>   * check-command: sparse -m64 $file
>   *
>   * check-error-start
> -shift-undef-long.c:4:16: warning: shift too big (4294967295) for type unsigned int
> -shift-undef-long.c:5:16: warning: shift too big (4294967296) for type unsigned int
> -shift-undef-long.c:6:16: warning: shift too big (4294967296) for type unsigned int
> -shift-undef-long.c:7:16: warning: shift count is negative (-4294967296)
> +shift-undef-long.c:4:25: warning: shift count is negative (-1)
> +shift-undef-long.c:5:47: warning: shift too big (4294967296) for type unsigned int
> +shift-undef-long.c:7:20: warning: shift count is negative (-4294967296)
>   * check-error-end
>   */
> diff --git a/validation/shift-undef.c b/validation/shift-undef.c
> index 613c6b95b113..0c7541e9ffd9 100644
> --- a/validation/shift-undef.c
> +++ b/validation/shift-undef.c
> @@ -112,48 +112,24 @@ void hw_write(u32 val)
>   * check-command: sparse -Wno-decl $file
>   *
>   * check-error-start
> -shift-undef.c:3:15: warning: shift too big (100) for type int
> -shift-undef.c:4:15: warning: shift too big (101) for type unsigned int
> -shift-undef.c:5:15: warning: shift too big (102) for type unsigned int
> -shift-undef.c:6:15: warning: shift count is negative (-1)
> -shift-undef.c:7:15: warning: shift count is negative (-2)
> -shift-undef.c:8:15: warning: shift count is negative (-3)
> -shift-undef.c:9:25: warning: shift too big (103) for type int
> -shift-undef.c:10:25: warning: shift too big (104) for type unsigned int
> -shift-undef.c:11:25: warning: shift too big (105) for type unsigned int
> -shift-undef.c:12:25: warning: shift count is negative (-4)
> -shift-undef.c:13:25: warning: shift count is negative (-5)
> -shift-undef.c:14:25: warning: shift count is negative (-6)
> -shift-undef.c:15:30: warning: shift too big (106) for type int
> -shift-undef.c:16:30: warning: shift too big (107) for type unsigned int
> -shift-undef.c:17:30: warning: shift too big (108) for type unsigned int
> -shift-undef.c:18:30: warning: shift count is negative (-7)
> -shift-undef.c:19:30: warning: shift count is negative (-8)
> -shift-undef.c:20:30: warning: shift count is negative (-9)
> +shift-undef.c:3:18: warning: shift too big (100) for type int
> +shift-undef.c:4:18: warning: shift too big (101) for type unsigned int
> +shift-undef.c:5:18: warning: shift too big (102) for type unsigned int
> +shift-undef.c:6:19: warning: shift count is negative (-1)
> +shift-undef.c:7:19: warning: shift count is negative (-2)
> +shift-undef.c:8:19: warning: shift count is negative (-3)
>  shift-undef.c:21:29: warning: shift too big (109) for type int
>  shift-undef.c:22:29: warning: shift too big (110) for type unsigned int
>  shift-undef.c:23:29: warning: shift too big (111) for type unsigned int
>  shift-undef.c:24:29: warning: shift count is negative (-10)
>  shift-undef.c:25:29: warning: shift count is negative (-11)
>  shift-undef.c:26:29: warning: shift count is negative (-12)
> -shift-undef.c:32:11: warning: shift too big (100) for type int
> -shift-undef.c:33:11: warning: shift too big (101) for type unsigned int
> -shift-undef.c:34:11: warning: shift too big (102) for type unsigned int
> -shift-undef.c:35:11: warning: shift count is negative (-1)
> -shift-undef.c:36:11: warning: shift too big (4294967294) for type unsigned int
> -shift-undef.c:37:11: warning: shift too big (4294967293) for type unsigned int
> -shift-undef.c:38:25: warning: shift too big (103) for type int
> -shift-undef.c:39:25: warning: shift too big (104) for type unsigned int
> -shift-undef.c:40:25: warning: shift too big (105) for type unsigned int
> -shift-undef.c:41:25: warning: shift count is negative (-4)
> -shift-undef.c:42:25: warning: shift too big (4294967291) for type unsigned int
> -shift-undef.c:43:25: warning: shift too big (4294967290) for type unsigned int
> -shift-undef.c:44:30: warning: shift too big (106) for type int
> -shift-undef.c:45:30: warning: shift too big (107) for type unsigned int
> -shift-undef.c:46:30: warning: shift too big (108) for type unsigned int
> -shift-undef.c:47:30: warning: shift count is negative (-7)
> -shift-undef.c:48:30: warning: shift too big (4294967288) for type unsigned int
> -shift-undef.c:49:30: warning: shift too big (4294967287) for type unsigned int
> +shift-undef.c:32:15: warning: shift too big (100) for type int
> +shift-undef.c:33:15: warning: shift too big (101) for type unsigned int
> +shift-undef.c:34:15: warning: shift too big (102) for type unsigned int
> +shift-undef.c:35:16: warning: shift count is negative (-1)
> +shift-undef.c:36:16: warning: shift count is negative (-2)
> +shift-undef.c:37:16: warning: shift count is negative (-3)
>  shift-undef.c:50:26: warning: shift too big (109) for type int
>  shift-undef.c:51:26: warning: shift too big (110) for type unsigned int
>  shift-undef.c:52:26: warning: shift too big (111) for type unsigned int
> -- 
> 2.28.0
> 

Re: [PATCH 0/4] Fix shifts-assigns and avoid warns on deadcode

[Stafford Horne]

On Thu, Aug 06, 2020 at 09:29:59PM +0200, Luc Van Oostenryck wrote:
> Sparse warns shifts by a negative or oversized amount but
> it does this even on code that will not be executed. It's
> annoying because such warnings are given for generic macros.
> 
> The strategy for these warnings is changed in patch 4:
> they are delayed until after the elimination of deadcode.
> This uncovered a bug in the type evaluation and the linearization
> of shift-assigns which is now solved in patch 2 & 3.
> 
> Thanks to Stafford Horne to bring this back to my attention.
> 
> This series is available for testing & review at:
>   git://git.kernel.org/pub/scm/devel/sparse/sparse.git bad-shift-equal

Thanks!

I see you merged this already, I tested it and see no regressions on my kernel
build, and confirm the xchg issues are fixed.

Sorry, I reviewed this early but didn't respond until now as I had time to test.

I just had one question on 4/4.

-Stafford

> Luc Van Oostenryck (4):
>   shift-assign: add more testcases for bogus linearization
>   shift-assign: fix linearization of shift-assign
>   shift-assign: restrict shift count to unsigned int
>   bad-shift: wait dead code elimination to warn about bad shifts
> 
>  evaluate.c                         |  11 +-
>  expand.c                           |  18 --
>  linearize.c                        |  44 ++++
>  simplify.c                         |  20 +-
>  validation/expand/bad-shift.c      |   8 +-
>  validation/linear/bug-assign-op0.c |   1 -
>  validation/linear/shift-assign1.c  | 319 +++++++++++++++++++++++++++++
>  validation/linear/shift-assign2.c  |  53 +++++
>  validation/optim/shift-big.c       |  12 +-
>  validation/shift-negative.c        |   4 +-
>  validation/shift-undef-long.c      |   7 +-
>  validation/shift-undef.c           |  52 ++---
>  12 files changed, 462 insertions(+), 87 deletions(-)
>  create mode 100644 validation/linear/shift-assign1.c
>  create mode 100644 validation/linear/shift-assign2.c
> 
> 
> base-commit: 4c6cbe557c48205f9b3d2aae4c166cd66446b240
> -- 
> 2.28.0
> 

Re: [PATCH 0/4] Fix shifts-assigns and avoid warns on deadcode

[Luc Van Oostenryck]

On Sat, Aug 15, 2020 at 06:59:49PM +0900, Stafford Horne wrote:
> On Thu, Aug 06, 2020 at 09:29:59PM +0200, Luc Van Oostenryck wrote:
> > Sparse warns shifts by a negative or oversized amount but
> > it does this even on code that will not be executed. It's
> > annoying because such warnings are given for generic macros.
> > 
> > The strategy for these warnings is changed in patch 4:
> > they are delayed until after the elimination of deadcode.
> > This uncovered a bug in the type evaluation and the linearization
> > of shift-assigns which is now solved in patch 2 & 3.
> > 
> > Thanks to Stafford Horne to bring this back to my attention.
> > 
> > This series is available for testing & review at:
> >   git://git.kernel.org/pub/scm/devel/sparse/sparse.git bad-shift-equal
> 
> Thanks!
> 
> I see you merged this already, I tested it and see no regressions on my kernel
> build, and confirm the xchg issues are fixed.
> 
> Sorry, I reviewed this early but didn't respond until now as I had time to test.

I should have waited a little more before merging (but OTOH, I thought,
it would be easier for you to give it a try before sending your PR
to Linus if already merged).

-- Luc

Re: [PATCH 4/4] bad-shift: wait dead code elimination to warn about bad shifts

[Luc Van Oostenryck]

On Sat, Aug 15, 2020 at 06:57:03PM +0900, Stafford Horne wrote:
> On Thu, Aug 06, 2020 at 09:30:03PM +0200, Luc Van Oostenryck wrote:
> > --- a/linearize.c
> > +++ b/linearize.c
> > @@ -2468,6 +2468,49 @@ static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stm
> >  	return VOID;
> >  }
> >  
> > +static void check_tainted_insn(struct instruction *insn)
> > +{
> > +	unsigned long long uval;
> > +	long long sval;
> > +	pseudo_t src2;
> > +
> > +	switch (insn->opcode) {
> > +	case OP_DIVU: case OP_DIVS:
> > +	case OP_MODU: case OP_MODS:
> > +		if (insn->src2 == value_pseudo(0))
> > +			warning(insn->pos, "divide by zero");
> > +		break;
> 
> Is this divide by zero a new check?  I get the shift, but is this new?

Yes, and no. The warning is already given (using 'division by zero')
but, like for shifts before this series, issued early, before dead code
elimination is done. So, code like the following:
	...
	if (d != 0)
		r = a / d;
	...
issues the warning nevertheless. So, the check here above is now unused
but is a preparation for the part 2 doing the same for division by zero
by zero.

Best regards,
-- Luc

Re: [PATCH 4/4] bad-shift: wait dead code elimination to warn about bad shifts

[Stafford Horne]

On Sat, Aug 15, 2020 at 01:15:40PM +0200, Luc Van Oostenryck wrote:
> On Sat, Aug 15, 2020 at 06:57:03PM +0900, Stafford Horne wrote:
> > On Thu, Aug 06, 2020 at 09:30:03PM +0200, Luc Van Oostenryck wrote:
> > > --- a/linearize.c
> > > +++ b/linearize.c
> > > @@ -2468,6 +2468,49 @@ static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stm
> > >  	return VOID;
> > >  }
> > >  
> > > +static void check_tainted_insn(struct instruction *insn)
> > > +{
> > > +	unsigned long long uval;
> > > +	long long sval;
> > > +	pseudo_t src2;
> > > +
> > > +	switch (insn->opcode) {
> > > +	case OP_DIVU: case OP_DIVS:
> > > +	case OP_MODU: case OP_MODS:
> > > +		if (insn->src2 == value_pseudo(0))
> > > +			warning(insn->pos, "divide by zero");
> > > +		break;
> > 
> > Is this divide by zero a new check?  I get the shift, but is this new?
> 
> Yes, and no. The warning is already given (using 'division by zero')
> but, like for shifts before this series, issued early, before dead code
> elimination is done. So, code like the following:
> 	...
> 	if (d != 0)
> 		r = a / d;
> 	...
> issues the warning nevertheless. So, the check here above is now unused
> but is a preparation for the part 2 doing the same for division by zero
> by zero.

I see, it's preparation for part 2, makes sense.

-Stafford