[PATCH 0/3] fix cast to bool

[PATCH 0/3] fix cast to bool

[Luc Van Oostenryck]

This serie fix casting to bool (patch 1) and add two simplifications
which couldn't be done without the fix.

Luc Van Oostenryck (3):
  fix cast to bool
  simplify comparisons followed by an equality test against 0 or 1
  simplify '(x || x)' and '(x && x)'

 evaluate.c                        | 32 +++++++++++++++++
 simplify.c                        | 73 ++++++++++++++++++++++++++++++++++++---
 validation/bool-cast-bad.c        | 27 +++++++++++++++
 validation/bool-cast-explicit.c   | 26 ++++++++++++++
 validation/bool-cast-implicit.c   | 28 +++++++++++++++
 validation/optim/bool-same-args.c | 12 +++++++
 validation/optim/setcc-setcc.c    | 19 ++++++++++
 validation/optim/setcc-seteq.c    | 13 +++++++
 validation/optim/setcc-setne.c    | 13 +++++++
 9 files changed, 239 insertions(+), 4 deletions(-)
 create mode 100644 validation/bool-cast-bad.c
 create mode 100644 validation/bool-cast-explicit.c
 create mode 100644 validation/bool-cast-implicit.c
 create mode 100644 validation/optim/bool-same-args.c
 create mode 100644 validation/optim/setcc-setcc.c
 create mode 100644 validation/optim/setcc-seteq.c
 create mode 100644 validation/optim/setcc-setne.c

-- 
2.10.2

[PATCH 1/3] fix cast to bool

[Luc Van Oostenryck]

Section 6.3.1.2 of the C standard requires that cast to bool
to be done differently than casting to others integer types:
    The casted value need to be compared against '0',
    if it compares equal the result is 0, otherwise the result is 1.

But currently, it's treated as the others integer casts: the value is
truncated, keeping only the least significant bit.

For example, when using test-linearize on the following code:
	_Bool foo(int a) { return (_Bool) a; }

this instruction is emitted:
	scast.1     %r2 <- (32) %arg1
while the correct one is:
	setne.1     %r2 <- %arg1, $0

Fix this for explicit and implicit casts.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 evaluate.c                      | 32 ++++++++++++++++++++++++++++++++
 validation/bool-cast-bad.c      | 27 +++++++++++++++++++++++++++
 validation/bool-cast-explicit.c | 26 ++++++++++++++++++++++++++
 validation/bool-cast-implicit.c | 28 ++++++++++++++++++++++++++++
 4 files changed, 113 insertions(+)
 create mode 100644 validation/bool-cast-bad.c
 create mode 100644 validation/bool-cast-explicit.c
 create mode 100644 validation/bool-cast-implicit.c

diff --git a/evaluate.c b/evaluate.c
index e350c0c0..61fc8f06 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -273,6 +273,8 @@ warn_for_different_enum_types (struct position pos,
 	}
 }
 
+static struct symbol *cast_to_bool(struct expression *expr);
+
 /*
  * This gets called for implicit casts in assignments and
  * integer promotion. We often want to try to move the
@@ -327,6 +329,10 @@ static struct expression * cast_to(struct expression *old, struct symbol *type)
 	expr->ctype = type;
 	expr->cast_type = type;
 	expr->cast_expression = old;
+
+	if (is_bool_type(type))
+		cast_to_bool(expr);
+
 	return expr;
 }
 
@@ -2686,6 +2692,28 @@ static void evaluate_initializer(struct symbol *ctype, struct expression **ep)
 		expression_error(*ep, "invalid initializer");
 }
 
+static struct symbol *cast_to_bool(struct expression *expr)
+{
+	struct expression *old = expr->cast_expression;
+	struct expression *zero;
+	struct symbol *otype;
+	int oclass = classify_type(degenerate(old), &otype);
+	struct symbol *ctype;
+
+	if (oclass & TYPE_COMPOUND)
+		return NULL;
+
+	zero = alloc_const_expression(expr->pos, 0);
+	expr->op = SPECIAL_NOTEQUAL;
+	ctype = usual_conversions(expr->op, old, zero,
+			oclass, TYPE_NUM, otype, zero->ctype);
+	expr->type = EXPR_COMPARE;
+	expr->left = cast_to(old, ctype);
+	expr->right = cast_to(zero, ctype);
+
+	return expr->ctype;
+}
+
 static struct symbol *evaluate_cast(struct expression *expr)
 {
 	struct expression *target = expr->cast_expression;
@@ -2814,6 +2842,10 @@ static struct symbol *evaluate_cast(struct expression *expr)
 			}
 		}
 	}
+
+	if (t1 == &bool_ctype)
+		cast_to_bool(expr);
+
 out:
 	return ctype;
 }
diff --git a/validation/bool-cast-bad.c b/validation/bool-cast-bad.c
new file mode 100644
index 00000000..b7e7c058
--- /dev/null
+++ b/validation/bool-cast-bad.c
@@ -0,0 +1,27 @@
+typedef unsigned short __attribute__((bitwise)) le16;
+struct s {
+	int a:2;
+	int b:2;
+	int c:2;
+};
+
+static _Bool fresi(le16 a)     { return a; }
+static _Bool frese(le16 a)     { return (_Bool)a; }
+static _Bool fstsi(struct s a) { return a; }
+static _Bool fstse(struct s a) { return (_Bool)a; }
+
+/*
+ * check-name: bool-cast-bad.c
+ * check-command: sparse $file
+ *
+ * check-error-start
+bool-cast-bad.c:8:41: warning: incorrect type in return expression (different base types)
+bool-cast-bad.c:8:41:    expected bool
+bool-cast-bad.c:8:41:    got restricted le16 [usertype] a
+bool-cast-bad.c:9:42: warning: cast from restricted le16
+bool-cast-bad.c:10:41: warning: incorrect type in return expression (different base types)
+bool-cast-bad.c:10:41:    expected bool
+bool-cast-bad.c:10:41:    got struct s a
+bool-cast-bad.c:11:42: warning: cast from non-scalar
+ * check-error-end
+ */
diff --git a/validation/bool-cast-explicit.c b/validation/bool-cast-explicit.c
new file mode 100644
index 00000000..6f9c4d46
--- /dev/null
+++ b/validation/bool-cast-explicit.c
@@ -0,0 +1,26 @@
+typedef unsigned int	u32;
+typedef          int	s32;
+typedef void *vdp;
+typedef int  *sip;
+typedef double dbl;
+typedef unsigned short __attribute__((bitwise)) le16;
+
+static _Bool fs32(s32 a) { return (_Bool)a; }
+static _Bool fu32(u32 a) { return (_Bool)a; }
+static _Bool fvdp(vdp a) { return (_Bool)a; }
+static _Bool fsip(sip a) { return (_Bool)a; }
+static _Bool fdbl(dbl a) { return (_Bool)a; }
+static _Bool ffun(void)  { return (_Bool)ffun; }
+
+static _Bool fres(le16 a) { return (_Bool)a; }
+
+/*
+ * check-name: bool-cast-explicit
+ * check-command: test-linearize $file
+ * check-output-ignore
+ * check-output-excludes: cast\\.
+ *
+ * check-error-start
+bool-cast-explicit.c:15:37: warning: cast from restricted le16
+ * check-error-end
+ */
diff --git a/validation/bool-cast-implicit.c b/validation/bool-cast-implicit.c
new file mode 100644
index 00000000..0e0e69a4
--- /dev/null
+++ b/validation/bool-cast-implicit.c
@@ -0,0 +1,28 @@
+typedef unsigned int	u32;
+typedef          int	s32;
+typedef void *vdp;
+typedef int  *sip;
+typedef double dbl;
+typedef unsigned short __attribute__((bitwise)) le16;
+
+static _Bool fs32(s32 a) { return a; }
+static _Bool fu32(u32 a) { return a; }
+static _Bool fvdp(vdp a) { return a; }
+static _Bool fsip(sip a) { return a; }
+static _Bool fdbl(dbl a) { return a; }
+static _Bool ffun(void)  { return ffun; }
+
+static _Bool fres(le16 a) { return a; }
+
+/*
+ * check-name: bool-cast-implicit
+ * check-command: test-linearize $file
+ * check-output-ignore
+ * check-output-excludes: cast\\.
+ *
+ * check-error-start
+bool-cast-implicit.c:15:36: warning: incorrect type in return expression (different base types)
+bool-cast-implicit.c:15:36:    expected bool
+bool-cast-implicit.c:15:36:    got restricted le16 [usertype] a
+ * check-error-end
+ */
-- 
2.10.2

[PATCH 2/3] simplify comparisons followed by an equality test against 0 or 1

[Luc Van Oostenryck]

Expressions involving equality testing against zero are ubiquitious
and can often be simplified with previous comparisons.

For example, when using test-linearize on the following code:
	_Bool foo(int a) { return !(a < 3); }
the following was emitted:
	setlt.32    %r2 <- %arg1, $3
	seteq.32    %r3 <- %r2, $0
	setne.1     %r4 <- %r3, $0
	ret.1       %r4

but this can be simplified into:
	setge.1     %r4 <- %arg1, $3
	ret.1       %r4

Implement this simplification and add associated test cases.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                     | 65 ++++++++++++++++++++++++++++++++++++++++++
 validation/optim/setcc-setcc.c | 19 ++++++++++++
 validation/optim/setcc-seteq.c | 13 +++++++++
 validation/optim/setcc-setne.c | 13 +++++++++
 4 files changed, 110 insertions(+)
 create mode 100644 validation/optim/setcc-setcc.c
 create mode 100644 validation/optim/setcc-seteq.c
 create mode 100644 validation/optim/setcc-setne.c

diff --git a/simplify.c b/simplify.c
index b29b3ebb..d076ebb5 100644
--- a/simplify.c
+++ b/simplify.c
@@ -310,6 +310,67 @@ static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long val
 	return 0;
 }
 
+static int compare_opcode(int opcode, int inverse)
+{
+	if (!inverse)
+		return opcode;
+
+	switch (opcode) {
+	case OP_SET_EQ:	return OP_SET_NE;
+	case OP_SET_NE:	return OP_SET_EQ;
+
+	case OP_SET_LT:	return OP_SET_GE;
+	case OP_SET_LE:	return OP_SET_GT;
+	case OP_SET_GT:	return OP_SET_LE;
+	case OP_SET_GE:	return OP_SET_LT;
+
+	case OP_SET_A:	return OP_SET_BE;
+	case OP_SET_AE:	return OP_SET_B;
+	case OP_SET_B:	return OP_SET_AE;
+	case OP_SET_BE:	return OP_SET_A;
+
+	default:
+		return opcode;
+	}
+}
+
+static int simplify_seteq_setne(struct instruction *insn, long long value)
+{
+	struct instruction *def = insn->src1->def;
+	pseudo_t src1, src2;
+	int inverse;
+	int opcode;
+
+	if (value != 0 && value != 1)
+		return 0;
+
+	if (!def)
+		return 0;
+
+	inverse = (insn->opcode == OP_SET_NE) == value;
+	opcode = def->opcode;
+	switch (opcode) {
+	case OP_BINCMP ... OP_BINCMP_END:
+		// Convert:
+		//	setcc.n	%t <- %a, %b
+		//	setne.m %r <- %t, $0
+		// into:
+		//	setcc.n	%t <- %a, %b
+		//	setcc.m %r <- %a, $b
+		// and similar for setne/eq ... 0/1
+		src1 = def->src1;
+		src2 = def->src2;
+		remove_usage(insn->src1, &insn->src1);
+		insn->opcode = compare_opcode(opcode, inverse);
+		use_pseudo(insn, src1, &insn->src1);
+		use_pseudo(insn, src2, &insn->src2);
+		return REPEAT_CSE;
+
+	default:
+		return 0;
+	}
+}
+
 static int simplify_constant_rightside(struct instruction *insn)
 {
 	long long value = insn->src2->value;
@@ -342,6 +403,10 @@ static int simplify_constant_rightside(struct instruction *insn)
 		if (!value)
 			return replace_with_pseudo(insn, insn->src2);
 		return 0;
+
+	case OP_SET_NE:
+	case OP_SET_EQ:
+		return simplify_seteq_setne(insn, value);
 	}
 	return 0;
 }
diff --git a/validation/optim/setcc-setcc.c b/validation/optim/setcc-setcc.c
new file mode 100644
index 00000000..fac7520e
--- /dev/null
+++ b/validation/optim/setcc-setcc.c
@@ -0,0 +1,19 @@
+static _Bool blt(int a, int b)	{ return  (a <  b); }
+static _Bool bnge(int a, int b)	{ return !(a >= b); }
+static _Bool bgt(int a, int b)	{ return  (a >  b); }
+static _Bool bnle(int a, int b)	{ return !(a <= b); }
+static _Bool ble(int a, int b)	{ return  (a <= b); }
+static _Bool bngt(int a, int b)	{ return !(a >  b); }
+static _Bool bge(int a, int b)	{ return  (a >= b); }
+static _Bool bnlt(int a, int b)	{ return !(a <  b); }
+
+/*
+ * check-name: optim/setcc-setcc
+ * check-command: test-linearize $file
+ * check-output-ignore
+ *
+ * check-output-excludes: set..\\.32
+ * check-output-excludes: setne\\.1
+ * check-output-excludes: seteq\\.1
+ * check-output-contains: set[gt][te]\\.1
+ */
diff --git a/validation/optim/setcc-seteq.c b/validation/optim/setcc-seteq.c
new file mode 100644
index 00000000..d8765fe1
--- /dev/null
+++ b/validation/optim/setcc-seteq.c
@@ -0,0 +1,13 @@
+static _Bool beq0(int a)	{ return  (a == 0); }
+static _Bool bnotneq0(int a)	{ return !(a != 0); }
+static _Bool bnot(int a)	{ return !a; }
+
+/*
+ * check-name: optim/setcc-seteq
+ * check-command: test-linearize $file
+ * check-output-ignore
+ *
+ * check-output-excludes: set..\\.32
+ * check-output-excludes: setne\\.1
+ * check-output-contains: seteq\\.1
+ */
diff --git a/validation/optim/setcc-setne.c b/validation/optim/setcc-setne.c
new file mode 100644
index 00000000..f982eb34
--- /dev/null
+++ b/validation/optim/setcc-setne.c
@@ -0,0 +1,13 @@
+static _Bool bnoteq0(int a)	{ return !(a == 0); }
+static _Bool bne0(int a)	{ return  (a != 0); }
+static _Bool bnotnot(int a)	{ return !!a; }
+
+/*
+ * check-name: optim/setcc-setne
+ * check-command: test-linearize $file
+ * check-output-ignore
+ *
+ * check-output-excludes: set..\\.32
+ * check-output-excludes: seteq\\.1
+ * check-output-contains: setne\\.1
+ */
-- 
2.10.2

[PATCH 3/3] simplify '(x || x)' and '(x && x)'

[Luc Van Oostenryck]

The operators '||' and '&&' being idempotent, the expressions
'(x || x)' and '(x && x)' can be simplified to a test against zero.

Note: they could even be replaced by 'x' itself but only if 'x' is
already a boolean expression/has already been tested against zero.
If it is the case, the redundant test this will be optimized away
in further steps.

For example, test-linearize on the following code:
	int ior(int a) { return a || a; }
emitted the following instructions:
	or-bool.32  %r3 <- %arg1, %arg1
after the patch, it now emits:
	setne.32    %r3 <- %arg1, $0
which is easier to combine with others simplifications.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                        |  8 ++++----
 validation/optim/bool-same-args.c | 12 ++++++++++++
 2 files changed, 16 insertions(+), 4 deletions(-)
 create mode 100644 validation/optim/bool-same-args.c

diff --git a/simplify.c b/simplify.c
index d076ebb5..169561fd 100644
--- a/simplify.c
+++ b/simplify.c
@@ -578,10 +578,10 @@ static int simplify_binop_same_args(struct instruction *insn, pseudo_t 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;
+		remove_usage(arg, &insn->src2);
+		insn->src2 = value_pseudo(0);
+		insn->opcode = OP_SET_NE;
+		return REPEAT_CSE;
 
 	default:
 		break;
diff --git a/validation/optim/bool-same-args.c b/validation/optim/bool-same-args.c
new file mode 100644
index 00000000..0ae4684e
--- /dev/null
+++ b/validation/optim/bool-same-args.c
@@ -0,0 +1,12 @@
+static int ior(int a) { return a || a; }
+static int and(int a) { return a && a; }
+
+/*
+ * check-name: bool-same-args
+ * check-command: test-linearize $file
+ * check-output-ignore
+ *
+ * check-output-excludes: or-bool\\.
+ * check-output-excludes: and-bool\\.
+ * check-output-contains: setne\\.
+ */
-- 
2.10.2