[PATCH 0/2] simplify binops with identical operands

[PATCH 0/2] simplify binops with identical operands

[Luc Van Oostenryck]

This serie add simplification of binops and comparison where
both operands are identical, and add an optional warning for those
comparison.


Luc Van Oostenryck (2):
  simplify '(x op x)' to '0', '1' or 'x'
  add warning option '-Wtautological-compare'

 lib.c                               |  2 ++
 lib.h                               |  1 +
 simplify.c                          | 39 +++++++++++++++++++++++++++++
 validation/optim/binops-same-args.c | 49 +++++++++++++++++++++++++++++++++++++
 validation/tautological-compare.c   | 35 ++++++++++++++++++++++++++
 5 files changed, 126 insertions(+)
 create mode 100644 validation/optim/binops-same-args.c
 create mode 100644 validation/tautological-compare.c

-- 
2.10.2

[PATCH 1/2] simplify '(x op x)' to '0', '1' or 'x'

[Luc Van Oostenryck]

Most binops can be simplified when their two operands are
identical. For example '(x ^ x)' can be simplified into '0'.

The cases '(x / x)' and '(x % x)' are not simplified since this
is correct only when x is not zero.
The cases '(x || x)' and '(x && x)' are not simplified because
it's only correct when the operands are booleans/have already
been compared against zero and the linearization don't enforce that.

This patch add the code for these simplifications as well as
their corresponding test cases.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                          | 35 ++++++++++++++++++++++++++
 validation/optim/binops-same-args.c | 49 +++++++++++++++++++++++++++++++++++++
 2 files changed, 84 insertions(+)
 create mode 100644 validation/optim/binops-same-args.c

diff --git a/simplify.c b/simplify.c
index b5cd0ea7..fde72f0a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -488,6 +488,39 @@ static int simplify_constant_binop(struct instruction *insn)
 	return REPEAT_CSE;
 }
 
+static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
+{
+	switch (insn->opcode) {
+	case OP_SET_NE:
+	case OP_SET_LT: case OP_SET_GT:
+	case OP_SET_B:  case OP_SET_A:
+	case OP_SUB:
+	case OP_XOR:
+		return replace_with_pseudo(insn, value_pseudo(0));
+
+	case OP_SET_EQ:
+	case OP_SET_LE: case OP_SET_GE:
+	case OP_SET_BE: case OP_SET_AE:
+		return replace_with_pseudo(insn, value_pseudo(1));
+
+	case OP_AND:
+	case OP_OR:
+		return replace_with_pseudo(insn, arg);
+
+	case OP_AND_BOOL:
+	case OP_OR_BOOL:
+		// simplification is correct only if the operands
+		// have already been compared against zero which
+		// is not enforced.
+		break;
+
+	default:
+		break;
+	}
+
+	return 0;
+}
+
 static int simplify_binop(struct instruction *insn)
 {
 	if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
@@ -499,6 +532,8 @@ static int simplify_binop(struct instruction *insn)
 	}
 	if (constant(insn->src2))
 		return simplify_constant_rightside(insn);
+	if (insn->src1 == insn->src2)
+		return simplify_binop_same_args(insn, insn->src1);
 	return 0;
 }
 
diff --git a/validation/optim/binops-same-args.c b/validation/optim/binops-same-args.c
new file mode 100644
index 00000000..9285655d
--- /dev/null
+++ b/validation/optim/binops-same-args.c
@@ -0,0 +1,49 @@
+typedef unsigned int u32;
+
+int ssub(int a) { return a - a; }
+u32 usub(u32 a) { return a - a; }
+
+int sdiv(int a) { return a / a; }
+u32 udiv(u32 a) { return a / a; }
+int smod(int a) { return a % a; }
+u32 umod(u32 a) { return a % a; }
+
+int seq(int a) { return a == a; }
+int sne(int a) { return a != a; }
+int slt(int a) { return a < a; }
+int sgt(int a) { return a > a; }
+int sle(int a) { return a <= a; }
+int sge(int a) { return a >= a; }
+
+u32 ueq(u32 a) { return a == a; }
+u32 une(u32 a) { return a != a; }
+u32 ult(u32 a) { return a < a; }
+u32 ugt(u32 a) { return a > a; }
+u32 ule(u32 a) { return a <= a; }
+u32 uge(u32 a) { return a >= a; }
+
+u32 xor(u32 a) { return a ^ a; }
+
+u32 ior(u32 a) { return a | a; }
+u32 and(u32 a) { return a & a; }
+
+/*
+ * check-name: double-unop
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: sub\\.
+ * check-output-contains: divs\\.
+ * check-output-contains: divu\\.
+ * check-output-contains: mods\\.
+ * check-output-contains: modu\\.
+ * check-output-excludes: seteq\\.
+ * check-output-excludes: setne\\.
+ * check-output-excludes: set[gl]t\\.
+ * check-output-excludes: set[gl]e\\.
+ * check-output-excludes: set[ab]\\.
+ * check-output-excludes: set[ab]e\\.
+ * check-output-excludes: xor\\.
+ * check-output-excludes: or\\.
+ * check-output-excludes: and\\.
+ */
-- 
2.10.2

[PATCH 2/2] add warning option '-Wtautological-compare'

[Luc Van Oostenryck]

Now that we optimize away expressions like 'x == x' or 'x < x',
also add a warning for it (but disabled by default).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 lib.c                             |  2 ++
 lib.h                             |  1 +
 simplify.c                        |  4 ++++
 validation/tautological-compare.c | 35 +++++++++++++++++++++++++++++++++++
 4 files changed, 42 insertions(+)
 create mode 100644 validation/tautological-compare.c

diff --git a/lib.c b/lib.c
index e5b0bb63..6b7a0817 100644
--- a/lib.c
+++ b/lib.c
@@ -236,6 +236,7 @@ int Wptr_subtraction_blows = 0;
 int Wreturn_void = 0;
 int Wshadow = 0;
 int Wsizeof_bool = 0;
+int Wtautological_compare = 0;
 int Wtransparent_union = 0;
 int Wtypesign = 0;
 int Wundef = 0;
@@ -471,6 +472,7 @@ static const struct warning {
 	{ "return-void", &Wreturn_void },
 	{ "shadow", &Wshadow },
 	{ "sizeof-bool", &Wsizeof_bool },
+	{ "tautological-compare", &Wtautological_compare },
 	{ "transparent-union", &Wtransparent_union },
 	{ "typesign", &Wtypesign },
 	{ "undef", &Wundef },
diff --git a/lib.h b/lib.h
index 15b69fa2..130e5b6c 100644
--- a/lib.h
+++ b/lib.h
@@ -122,6 +122,7 @@ extern int Wptr_subtraction_blows;
 extern int Wreturn_void;
 extern int Wshadow;
 extern int Wsizeof_bool;
+extern int Wtautological_compare;
 extern int Wtransparent_union;
 extern int Wtypesign;
 extern int Wundef;
diff --git a/simplify.c b/simplify.c
index fde72f0a..b29b3ebb 100644
--- a/simplify.c
+++ b/simplify.c
@@ -494,6 +494,8 @@ static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
 	case OP_SET_NE:
 	case OP_SET_LT: case OP_SET_GT:
 	case OP_SET_B:  case OP_SET_A:
+		if (Wtautological_compare)
+			warning(insn->pos, "self-comparison always evaluates to false");
 	case OP_SUB:
 	case OP_XOR:
 		return replace_with_pseudo(insn, value_pseudo(0));
@@ -501,6 +503,8 @@ static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
 	case OP_SET_EQ:
 	case OP_SET_LE: case OP_SET_GE:
 	case OP_SET_BE: case OP_SET_AE:
+		if (Wtautological_compare)
+			warning(insn->pos, "self-comparison always evaluates to true");
 		return replace_with_pseudo(insn, value_pseudo(1));
 
 	case OP_AND:
diff --git a/validation/tautological-compare.c b/validation/tautological-compare.c
new file mode 100644
index 00000000..55a2b463
--- /dev/null
+++ b/validation/tautological-compare.c
@@ -0,0 +1,35 @@
+typedef unsigned int u32;
+
+int seq(int a) { return a == a; }
+int sne(int a) { return a != a; }
+int slt(int a) { return a < a; }
+int sgt(int a) { return a > a; }
+int sle(int a) { return a <= a; }
+int sge(int a) { return a >= a; }
+
+u32 ueq(u32 a) { return a == a; }
+u32 une(u32 a) { return a != a; }
+u32 ult(u32 a) { return a < a; }
+u32 ugt(u32 a) { return a > a; }
+u32 ule(u32 a) { return a <= a; }
+u32 uge(u32 a) { return a >= a; }
+
+/*
+ * check-name: tautological-compare
+ * check-command: sparse -Wno-decl -Wtautological-compare $file
+ *
+ * check-error-start
+tautological-compare.c:3:30: warning: self-comparison always evaluates to true
+tautological-compare.c:4:30: warning: self-comparison always evaluates to false
+tautological-compare.c:5:29: warning: self-comparison always evaluates to false
+tautological-compare.c:6:29: warning: self-comparison always evaluates to false
+tautological-compare.c:7:30: warning: self-comparison always evaluates to true
+tautological-compare.c:8:30: warning: self-comparison always evaluates to true
+tautological-compare.c:10:30: warning: self-comparison always evaluates to true
+tautological-compare.c:11:30: warning: self-comparison always evaluates to false
+tautological-compare.c:12:29: warning: self-comparison always evaluates to false
+tautological-compare.c:13:29: warning: self-comparison always evaluates to false
+tautological-compare.c:14:30: warning: self-comparison always evaluates to true
+tautological-compare.c:15:30: warning: self-comparison always evaluates to true
+ * check-error-end
+ */
-- 
2.10.2