[PATCH v2 0/8] division-by-zero warnings

[PATCH v2 0/8] division-by-zero warnings

[Luc Van Oostenryck]

The goal of this series is to add the 'division by zero'
warnings that are missing. Indeed, sparse only warned about
division by zero when the LHS was a constant. When the LHS
was not a constant (and thus also when the division was part
of a compound assignement) no warning was ever issued.

Note: the floating point division need similar changes
      which will be part of another series.

Changes since v1:
- add the warnins for compound assignments at expansion time too
- code restructuration and simplification
- test cases consolidation


This series is also available in the git repository at:
  git://github.com/lucvoo/sparse.git div-by-zero-v2


Luc Van Oostenryck (8):
  add is_pseudo_value()
  add a .warned field to struct instruction
  div0: warn on integer divide by 0 also when the lhs is not constant
  div0: also check for compound assignments
  div0: add warning option -Wdiv-by-zero
  div0: use -Wdiv-by-zero
  div0: warn also during simplification
  div0: warn on float divide by 0 also when the lhs is not constant

 expand.c                    | 42 +++++++++++++++----------
 lib.c                       |  2 ++
 lib.h                       |  1 +
 linearize.c                 | 17 +++++++++++
 linearize.h                 | 12 ++++++--
 simplify.c                  | 12 ++++++++
 validation/div-by-zero-fp.c | 24 +++++++++++++++
 validation/div-by-zero.c    | 74 +++++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 166 insertions(+), 18 deletions(-)
 create mode 100644 validation/div-by-zero-fp.c
 create mode 100644 validation/div-by-zero.c

-- 
2.13.0

[PATCH v2 1/8] add is_pseudo_value()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/linearize.h b/linearize.h
index bac82d7ff..c704b87b4 100644
--- a/linearize.h
+++ b/linearize.h
@@ -45,6 +45,13 @@ extern struct pseudo void_pseudo;
 
 #define VOID (&void_pseudo)
 
+
+static inline int is_pseudo_value(pseudo_t p, long long value)
+{
+	return p->type == PSEUDO_VAL && p->value == value;
+}
+
+
 struct multijmp {
 	struct basic_block *target;
 	int begin, end;
-- 
2.13.0

[PATCH v2 2/8] add a .warned field to struct instruction

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/linearize.h b/linearize.h
index c704b87b4..2b6cb0c86 100644
--- a/linearize.h
+++ b/linearize.h
@@ -75,8 +75,9 @@ struct asm_rules {
 DECLARE_ALLOCATOR(asm_rules);
 
 struct instruction {
-	unsigned opcode:8,
-		 size:24;
+	unsigned opcode:7;
+	unsigned warned:1;
+	unsigned size:24;
 	struct basic_block *bb;
 	struct position pos;
 	struct symbol *type;
-- 
2.13.0

[PATCH v2 3/8] div0: warn on integer divide by 0 also when the lhs is not constant

[Luc Van Oostenryck]

The current code detects and warns on division by zero but
only when the left-hand side is a constant value.

Fix that by moving up the code which detect such divisions
before checking if the LHS is a constant.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 expand.c                 |  8 ++----
 validation/div-by-zero.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 68 insertions(+), 6 deletions(-)
 create mode 100644 validation/div-by-zero.c

diff --git a/expand.c b/expand.c
index 5f908c971..0b528ea5a 100644
--- a/expand.c
+++ b/expand.c
@@ -181,6 +181,8 @@ static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
 	if (right->type != EXPR_VALUE)
 		return 0;
 	r = right->value;
+	if (!r && (expr->op == '/' || expr->op == '%'))
+		goto Div;
 	if (expr->op == SPECIAL_LEFTSHIFT || expr->op == SPECIAL_RIGHTSHIFT) {
 		if (r >= ctype->bit_size) {
 			if (conservative)
@@ -235,28 +237,22 @@ static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
 		break;
 
 	case SIGNED('/'):
-		if (!r)
-			goto Div;
 		if (l == mask && sr == -1)
 			goto Overflow;
 		v = sl / sr;
 		break;
 
 	case UNSIGNED('/'):
-		if (!r) goto Div;
 		v = l / r; 
 		break;
 
 	case SIGNED('%'):
-		if (!r)
-			goto Div;
 		if (l == mask && sr == -1)
 			goto Overflow;
 		v = sl % sr;
 		break;
 
 	case UNSIGNED('%'):
-		if (!r) goto Div;
 		v = l % r;
 		break;
 
diff --git a/validation/div-by-zero.c b/validation/div-by-zero.c
new file mode 100644
index 000000000..500ceb8eb
--- /dev/null
+++ b/validation/div-by-zero.c
@@ -0,0 +1,66 @@
+int  scdiv(int a) { return 2 / 0; }
+int iscdiv(int a) { return 2 / (int) 0; }
+int lscdiv(int a) { return 2 / (long) 0; }
+int uscdiv(int a) { return 2 / (unsigned int) 0; }
+
+int  svdiv(int a) { return a / 0; }
+int isvdiv(int a) { return a / (int) 0; }
+int lsvdiv(int a) { return a / (long) 0; }
+int usvdiv(int a) { return a / (unsigned int) 0; }
+
+int  scmod(int a) { return 2 % 0; }
+int iscmod(int a) { return 2 % (int) 0; }
+int lscmod(int a) { return 2 % (long) 0; }
+int uscmod(int a) { return 2 % (unsigned int) 0; }
+
+int  svmod(int a) { return a % 0; }
+int isvmod(int a) { return a % (int) 0; }
+int lsvmod(int a) { return a % (long) 0; }
+int usvmod(int a) { return a % (unsigned int) 0; }
+
+int xsvdiv(int a) { if (a && 0) return a / 0; return 0; }
+int asvdiv(int a) { return a /= 0; }
+int osvdiv(int a) { return a / (a && 0); }
+
+int xsvmod(int a) { if (a && 0) return a % 0; return 0; }
+int asvmod(int a) { return a %= 0; }
+int osvmod(int a) { return a % (a && 0); }
+
+int ysvdiv(int a) { if (a && 0) return a /= 0; return 0; }
+int ysvmod(int a) { if (a && 0) return a %= 0; return 0; }
+
+int zsvdiv(int a) { if (0 && (a /  0)) return 1; return 0; }
+int zsvmod(int a) { if (0 && (a /= 0)) return 1; return 0; }
+
+int wsvdiv(int a) { if (0) return a / 0; return 0; }
+int wsvmod(int a) { if (0) return a % 0; return 0; }
+int vsvdiv(int a) { if (0) return a /= 0; return 0; }
+int vsvmod(int a) { if (0) return a %= 0; return 0; }
+
+/*
+ * check-name: div-by-zero.c
+ * check-command: sparse -Wno-decl $file
+ *
+ * check-error-start
+div-by-zero.c:1:30: warning: division by zero
+div-by-zero.c:2:30: warning: division by zero
+div-by-zero.c:3:30: warning: division by zero
+div-by-zero.c:4:30: warning: division by zero
+div-by-zero.c:6:30: warning: division by zero
+div-by-zero.c:7:30: warning: division by zero
+div-by-zero.c:8:30: warning: division by zero
+div-by-zero.c:9:30: warning: division by zero
+div-by-zero.c:11:30: warning: division by zero
+div-by-zero.c:12:30: warning: division by zero
+div-by-zero.c:13:30: warning: division by zero
+div-by-zero.c:14:30: warning: division by zero
+div-by-zero.c:16:30: warning: division by zero
+div-by-zero.c:17:30: warning: division by zero
+div-by-zero.c:18:30: warning: division by zero
+div-by-zero.c:19:30: warning: division by zero
+div-by-zero.c:21:42: warning: division by zero
+div-by-zero.c:25:42: warning: division by zero
+div-by-zero.c:35:37: warning: division by zero
+div-by-zero.c:36:37: warning: division by zero
+ * check-error-end
+ */
-- 
2.13.0

[PATCH v2 4/8] div0: also check for compound assignments

[Luc Van Oostenryck]

---
 expand.c                 | 12 ++++++++++++
 validation/div-by-zero.c |  6 ++++++
 2 files changed, 18 insertions(+)

diff --git a/expand.c b/expand.c
index 0b528ea5a..5bbab17a9 100644
--- a/expand.c
+++ b/expand.c
@@ -559,6 +559,18 @@ static int expand_assignment(struct expression *expr)
 {
 	expand_expression(expr->left);
 	expand_expression(expr->right);
+	if (!conservative) {
+		switch (expr->op) {
+		case SPECIAL_DIV_ASSIGN:
+		case SPECIAL_MOD_ASSIGN:
+			if (expr->right->type != EXPR_VALUE)
+				break;
+			if (expr->right->value)
+				break;
+			warning(expr->pos, "division by zero");
+			break;
+		}
+	}
 	return SIDE_EFFECTS;
 }
 
diff --git a/validation/div-by-zero.c b/validation/div-by-zero.c
index 500ceb8eb..bd8d0dfdf 100644
--- a/validation/div-by-zero.c
+++ b/validation/div-by-zero.c
@@ -59,8 +59,14 @@ div-by-zero.c:17:30: warning: division by zero
 div-by-zero.c:18:30: warning: division by zero
 div-by-zero.c:19:30: warning: division by zero
 div-by-zero.c:21:42: warning: division by zero
+div-by-zero.c:22:30: warning: division by zero
 div-by-zero.c:25:42: warning: division by zero
+div-by-zero.c:26:30: warning: division by zero
+div-by-zero.c:29:42: warning: division by zero
+div-by-zero.c:30:42: warning: division by zero
 div-by-zero.c:35:37: warning: division by zero
 div-by-zero.c:36:37: warning: division by zero
+div-by-zero.c:37:37: warning: division by zero
+div-by-zero.c:38:37: warning: division by zero
  * check-error-end
  */
-- 
2.13.0

[PATCH v2 5/8] div0: add warning option -Wdiv-by-zero

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 lib.c | 2 ++
 lib.h | 1 +
 2 files changed, 3 insertions(+)

diff --git a/lib.c b/lib.c
index e1e6a1cbf..af2ad83a2 100644
--- a/lib.c
+++ b/lib.c
@@ -225,6 +225,7 @@ int Wdecl = 1;
 int Wdeclarationafterstatement = -1;
 int Wdefault_bitfield_sign = 0;
 int Wdesignated_init = 1;
+int Wdiv_by_zero = 1;
 int Wdo_while = 0;
 int Winit_cstring = 0;
 int Wenum_mismatch = 1;
@@ -502,6 +503,7 @@ static const struct warning {
 	{ "declaration-after-statement", &Wdeclarationafterstatement },
 	{ "default-bitfield-sign", &Wdefault_bitfield_sign },
 	{ "designated-init", &Wdesignated_init },
+	{ "div-by-zero", &Wdiv_by_zero },
 	{ "do-while", &Wdo_while },
 	{ "enum-mismatch", &Wenum_mismatch },
 	{ "sparse-error", &Wsparse_error },
diff --git a/lib.h b/lib.h
index 2c8529f93..820e69476 100644
--- a/lib.h
+++ b/lib.h
@@ -112,6 +112,7 @@ extern int Wdecl;
 extern int Wdeclarationafterstatement;
 extern int Wdefault_bitfield_sign;
 extern int Wdesignated_init;
+extern int Wdiv_by_zero;
 extern int Wdo_while;
 extern int Wenum_mismatch;
 extern int Wsparse_error;
-- 
2.13.0

[PATCH v2 6/8] div0: use -Wdiv-by-zero

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 expand.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/expand.c b/expand.c
index 5bbab17a9..71fbf209c 100644
--- a/expand.c
+++ b/expand.c
@@ -278,7 +278,7 @@ static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
 	expr->taint = left->taint | right->taint;
 	return 1;
 Div:
-	if (!conservative)
+	if (!conservative && Wdiv_by_zero)
 		warning(expr->pos, "division by zero");
 	return 0;
 Overflow:
@@ -363,7 +363,7 @@ static int simplify_float_binop(struct expression *expr)
 	expr->fvalue = res;
 	return 1;
 Div:
-	if (!conservative)
+	if (!conservative && Wdiv_by_zero)
 		warning(expr->pos, "division by zero");
 	return 0;
 }
-- 
2.13.0

[PATCH v2 7/8] div0: warn also during simplification

[Luc Van Oostenryck]

sparse now warn about divion by zero during linearization
but during simplification some expression can become constants
and so some new divisions by zero can appears.

Warn also on those new and to avoid to warn also here on the old
ones, mark the instructions for wich we have already be warned.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c              | 17 +++++++++++++++++
 simplify.c               | 12 ++++++++++++
 validation/div-by-zero.c |  2 ++
 3 files changed, 31 insertions(+)

diff --git a/linearize.c b/linearize.c
index 7313e72d8..1d21ea105 100644
--- a/linearize.c
+++ b/linearize.c
@@ -959,6 +959,21 @@ static pseudo_t linearize_store_gen(struct entrypoint *ep,
 	return value;
 }
 
+static void warn_undef_insn(struct instruction *insn)
+{
+	switch (insn->opcode) {
+	case OP_DIVU:
+	case OP_DIVS:
+	case OP_MODU:
+	case OP_MODS:
+		if (is_pseudo_value(insn->src2, 0))
+			insn->warned = 1;
+		break;
+	default:
+		break;
+	}
+}
+
 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
 {
 	struct instruction *insn = alloc_typed_instruction(op, ctype);
@@ -1208,6 +1223,7 @@ static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *e
 		oldvalue = cast_pseudo(ep, oldvalue, target->ctype, ctype);
 		opcode = opcode_sign(op_trans[expr->op - SPECIAL_BASE], ctype);
 		dst = add_binary_op(ep, ctype, opcode, oldvalue, value);
+		warn_undef_insn(dst->def);
 		value = cast_pseudo(ep, dst, ctype, expr->ctype);
 	}
 	value = linearize_store_gen(ep, value, &ad);
@@ -1323,6 +1339,7 @@ static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
 	src2 = linearize_expression(ep, expr->right);
 	op = opcode_sign(opcode[expr->op], expr->ctype);
 	dst = add_binary_op(ep, expr->ctype, op, src1, src2);
+	warn_undef_insn(dst->def);
 	return dst;
 }
 
diff --git a/simplify.c b/simplify.c
index a141ddd43..40e1c253b 100644
--- a/simplify.c
+++ b/simplify.c
@@ -404,6 +404,15 @@ static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long val
 	return 0;
 }
 
+static void check_divide_by_zero(struct instruction *insn, long long value)
+{
+	if (value != 0 || insn->warned)
+		return;
+	if (Wdiv_by_zero)
+		warning(insn->pos, "division by zero");
+	insn->warned = 1;
+}
+
 static int simplify_mul_div(struct instruction *insn, long long value)
 {
 	unsigned long long sbit = 1ULL << (insn->size - 1);
@@ -525,9 +534,12 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_MODU: case OP_MODS:
 		if (value == 1)
 			return replace_with_pseudo(insn, value_pseudo(0));
+		check_divide_by_zero(insn, value);
 		return 0;
 
 	case OP_DIVU: case OP_DIVS:
+		check_divide_by_zero(insn, value);
+		/* Fall through */
 	case OP_MULU: case OP_MULS:
 		return simplify_mul_div(insn, value);
 
diff --git a/validation/div-by-zero.c b/validation/div-by-zero.c
index bd8d0dfdf..b7c4770e6 100644
--- a/validation/div-by-zero.c
+++ b/validation/div-by-zero.c
@@ -60,8 +60,10 @@ div-by-zero.c:18:30: warning: division by zero
 div-by-zero.c:19:30: warning: division by zero
 div-by-zero.c:21:42: warning: division by zero
 div-by-zero.c:22:30: warning: division by zero
+div-by-zero.c:23:38: warning: division by zero
 div-by-zero.c:25:42: warning: division by zero
 div-by-zero.c:26:30: warning: division by zero
+div-by-zero.c:27:38: warning: division by zero
 div-by-zero.c:29:42: warning: division by zero
 div-by-zero.c:30:42: warning: division by zero
 div-by-zero.c:35:37: warning: division by zero
-- 
2.13.0

[PATCH v2 8/8] div0: warn on float divide by 0 also when the lhs is not constant

[Luc Van Oostenryck]

The current code detects and warns on division by zero but
only when the left-hand side is a constant value.

Fix that by moving up the code which detect such divisions
before checking if the LHS is a constant.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 expand.c                    | 18 ++++++++++--------
 validation/div-by-zero-fp.c | 24 ++++++++++++++++++++++++
 2 files changed, 34 insertions(+), 8 deletions(-)
 create mode 100644 validation/div-by-zero-fp.c

diff --git a/expand.c b/expand.c
index 71fbf209c..6b0dbf656 100644
--- a/expand.c
+++ b/expand.c
@@ -325,19 +325,23 @@ static int simplify_float_binop(struct expression *expr)
 	unsigned long mod = expr->ctype->ctype.modifiers;
 	long double l, r, res;
 
-	if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
+	if (right->type != EXPR_FVALUE)
 		return 0;
 
-	l = left->fvalue;
 	r = right->fvalue;
+	if (!r && expr->op == '/')
+		goto Div;
+
+	if (left->type != EXPR_FVALUE)
+		return 0;
+	l = left->fvalue;
 
 	if (mod & MOD_LONGLONG) {
 		switch (expr->op) {
 		case '+':	res = l + r; break;
 		case '-':	res = l - r; break;
 		case '*':	res = l * r; break;
-		case '/':	if (!r) goto Div;
-				res = l / r; break;
+		case '/':	res = l / r; break;
 		default: return 0;
 		}
 	} else if (mod & MOD_LONG) {
@@ -345,8 +349,7 @@ static int simplify_float_binop(struct expression *expr)
 		case '+':	res = (double) l + (double) r; break;
 		case '-':	res = (double) l - (double) r; break;
 		case '*':	res = (double) l * (double) r; break;
-		case '/':	if (!r) goto Div;
-				res = (double) l / (double) r; break;
+		case '/':	res = (double) l / (double) r; break;
 		default: return 0;
 		}
 	} else {
@@ -354,8 +357,7 @@ static int simplify_float_binop(struct expression *expr)
 		case '+':	res = (float)l + (float)r; break;
 		case '-':	res = (float)l - (float)r; break;
 		case '*':	res = (float)l * (float)r; break;
-		case '/':	if (!r) goto Div;
-				res = (float)l / (float)r; break;
+		case '/':	res = (float)l / (float)r; break;
 		default: return 0;
 		}
 	}
diff --git a/validation/div-by-zero-fp.c b/validation/div-by-zero-fp.c
new file mode 100644
index 000000000..957bc732c
--- /dev/null
+++ b/validation/div-by-zero-fp.c
@@ -0,0 +1,24 @@
+double fbad(double a) { return 2.0 / 0; }
+double gbad(double a) { return 2.0 / 0.0; }
+double fool(double a) { return a / 0; }
+double ffoo(double a) { return a / 0.0; }
+
+double fbar(double a) { if (a && 0) a / 0.0; return 0; }
+double fbaz(double a) { return a /= 0.0; }
+double fquz(double a) { return a / (a && 0); }
+
+/*
+ * check-name: div-by-zero-fp.c
+ * check-command: sparse -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-error-start
+div-by-zero-fp.c:1:36: warning: division by zero
+div-by-zero-fp.c:2:36: warning: division by zero
+div-by-zero-fp.c:3:34: warning: division by zero
+div-by-zero-fp.c:4:34: warning: division by zero
+div-by-zero-fp.c:6:39: warning: division by zero
+div-by-zero-fp.c:7:34: warning: division by zero
+div-by-zero-fp.c:8:34: warning: division by zero
+ * check-error-end
+ */
-- 
2.13.0

Re: [PATCH v2 0/8] division-by-zero warnings

[Christopher Li]

On Sat, Jun 3, 2017 at 1:01 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The goal of this series is to add the 'division by zero'
> warnings that are missing. Indeed, sparse only warned about
> division by zero when the LHS was a constant. When the LHS
> was not a constant (and thus also when the division was part
> of a compound assignement) no warning was ever issued.

This series looks fine to me.

Signed-off-By: Chris Li <sparse@chrisli.org>

Chris