canonicalize constant signed compares toward zero

Currently, signed compares against a constant are canonicalized
toward the smallest possible constant. So, the following
canonicalization are done:
	x < 256		--> x <= 255
	x < -2047	--> x <= -2048

This has two advantages:
1) it maximalizes the number of constants possible for a given bit size.
2) it allows to remove all < and all >=

But it has also a serious disadvantages: a simple comparison against
zero, like:
	x >= 0
is canonicalized into:
	x > -1

Which can be more costly for some architectures if translated as such ,
is also less readable than the version using 0 and is also sometimes
quite more complicated to match in some simplification patterns.

So, canonicalize it using 'towards 0' / using the smallest constant
in absolute value.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

2 files changed, 102 insertions, 6 deletions

diff --git a/simplify.c b/simplify.c
index 9e3514d8..e0e4f9eb 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1178,38 +1178,52 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 
 	switch (insn->opcode) {
 	case OP_SET_LT:
+		if (!value)
+			break;
 		if (value == sign_bit(size))	// (x <  SMIN) --> 0
 			return replace_with_pseudo(insn, value_pseudo(0));
 		if (value == sign_mask(size))	// (x <  SMAX) --> (x != SMAX)
 			return replace_opcode(insn, OP_SET_NE);
 		if (value == sign_bit(size) + 1)// (x < SMIN + 1) --> (x == SMIN)
 			return replace_binop_value(insn, OP_SET_EQ, sign_bit(size));
-		changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
+		if (!(value & sign_bit(size)))
+			changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
 		break;
 	case OP_SET_LE:
+		if (!value)
+			break;
 		if (value == sign_mask(size))	// (x <= SMAX) --> 1
 			return replace_with_pseudo(insn, value_pseudo(1));
 		if (value == sign_bit(size))	// (x <= SMIN) --> (x == SMIN)
 			return replace_opcode(insn, OP_SET_EQ);
 		if (value == sign_mask(size) - 1) // (x <= SMAX - 1) --> (x != SMAX)
 			return replace_binop_value(insn, OP_SET_NE, sign_mask(size));
+		if (value & sign_bit(size))
+			changed |= replace_binop_value(insn, OP_SET_LT, (value + 1) & bits);
 		break;
 	case OP_SET_GE:
+		if (!value)
+			break;
 		if (value == sign_bit(size))	// (x >= SMIN) --> 1
 			return replace_with_pseudo(insn, value_pseudo(1));
 		if (value == sign_mask(size))	// (x >= SMAX) --> (x == SMAX)
 			return replace_opcode(insn, OP_SET_EQ);
 		if (value == sign_bit(size) + 1)// (x >= SMIN + 1) --> (x != SMIN)
 			return replace_binop_value(insn, OP_SET_NE, sign_bit(size));
-		changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
+		if (!(value & sign_bit(size)))
+			changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
 		break;
 	case OP_SET_GT:
+		if (!value)
+			break;
 		if (value == sign_mask(size))	// (x >  SMAX) --> 0
 			return replace_with_pseudo(insn, value_pseudo(0));
 		if (value == sign_bit(size))	// (x >  SMIN) --> (x != SMIN)
 			return replace_opcode(insn, OP_SET_NE);
 		if (value == sign_mask(size) - 1) // (x > SMAX - 1) --> (x == SMAX)
 			return replace_binop_value(insn, OP_SET_EQ, sign_mask(size));
+		if (value & sign_bit(size))
+			changed |= replace_binop_value(insn, OP_SET_GE, (value + 1) & bits);
 		break;
 
 	case OP_SET_B:
@@ -1271,8 +1285,10 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			if ((value & bits) != value)
 				return replace_with_value(insn, 1);
 			break;
-		case OP_SET_LE:
+		case OP_SET_LE: case OP_SET_LT:
 			value = sign_extend(value, def->size);
+			if (insn->opcode == OP_SET_LT)
+				value -= 1;
 			if (bits & sign_bit(def->size))
 				break;
 			if (value < 0)
@@ -1282,8 +1298,10 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			if (value == 0)
 				return replace_opcode(insn, OP_SET_EQ);
 			break;
-		case OP_SET_GT:
+		case OP_SET_GT: case OP_SET_GE:
 			value = sign_extend(value, def->size);
+			if (insn->opcode == OP_SET_GE)
+				value -= 1;
 			if (bits & sign_bit(def->size))
 				break;
 			if (value < 0)
@@ -1340,16 +1358,20 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			if (bits >= value)
 				return replace_with_value(insn, 1);
 			break;
+		case OP_SET_LT:
+			value -= 1;
 		case OP_SET_LE:
-			value = sign_extend(value, def->size);
 			if (bits & sign_bit(def->size)) {
+				value = sign_extend(value, def->size);
 				if (value >= -1)
 					return replace_with_value(insn, 1);
 			}
 			break;
+		case OP_SET_GE:
+			value -= 1;
 		case OP_SET_GT:
-			value = sign_extend(value, def->size);
 			if (bits & sign_bit(def->size)) {
+				value = sign_extend(value, def->size);
 				if (value >= -1)
 					return replace_with_value(insn, 0);
 			}
diff --git a/validation/optim/canonical-cmp-zero.c b/validation/optim/canonical-cmp-zero.c
new file mode 100644
index 00000000..e01a00e6
--- /dev/null
+++ b/validation/optim/canonical-cmp-zero.c
@@ -0,0 +1,74 @@
+int f00(int x) { return x >= 0; }
+int f01(int x) { return x > -1; }
+int f02(int x) { return x <  1; }
+int f03(int x) { return x <= 0; }
+
+int f10(int x) { return x <  16; }
+int f11(int x) { return x <= 15; }
+
+int f20(int x) { return x >  -9; }
+int f21(int x) { return x >= -8; }
+
+/*
+ * check-name: canonical-cmp-zero
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+f00:
+.L0:
+	<entry-point>
+	setge.32    %r2 <- %arg1, $0
+	ret.32      %r2
+
+
+f01:
+.L2:
+	<entry-point>
+	setge.32    %r5 <- %arg1, $0
+	ret.32      %r5
+
+
+f02:
+.L4:
+	<entry-point>
+	setle.32    %r8 <- %arg1, $0
+	ret.32      %r8
+
+
+f03:
+.L6:
+	<entry-point>
+	setle.32    %r11 <- %arg1, $0
+	ret.32      %r11
+
+
+f10:
+.L8:
+	<entry-point>
+	setle.32    %r14 <- %arg1, $15
+	ret.32      %r14
+
+
+f11:
+.L10:
+	<entry-point>
+	setle.32    %r17 <- %arg1, $15
+	ret.32      %r17
+
+
+f20:
+.L12:
+	<entry-point>
+	setge.32    %r20 <- %arg1, $0xfffffff8
+	ret.32      %r20
+
+
+f21:
+.L14:
+	<entry-point>
+	setge.32    %r23 <- %arg1, $0xfffffff8
+	ret.32      %r23
+
+
+ * check-output-end
+ */