Merge branch 'optim-cmps'

* simplify and canonicalize signed compares

8 files changed, 200 insertions, 19 deletions

diff --git a/simplify.c b/simplify.c
index bf6397df..584078dd 100644
--- a/simplify.c
+++ b/simplify.c
@@ -454,6 +454,13 @@ static inline pseudo_t is_same_op(pseudo_t src, int op, unsigned osize)
 	return def->src;
 }
 
+static bool is_negate_of(pseudo_t p, pseudo_t ref)
+{
+	struct instruction *def;
+
+	return (DEF_OPCODE(def, p) == OP_NEG) && (def->src == ref);
+}
+
 ///
 // replace the operand of an instruction
 // @insn: the instruction
@@ -1162,13 +1169,49 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 
 static int simplify_compare_constant(struct instruction *insn, long long value)
 {
-	unsigned long long bits = bits_mask(insn->itype->bit_size);
+	unsigned size = insn->itype->bit_size;
+	unsigned long long bits = bits_mask(size);
 	struct instruction *def;
 	pseudo_t src1, src2;
 	unsigned int osize;
 	int changed = 0;
 
 	switch (insn->opcode) {
+	case OP_SET_LT:
+		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);
+		break;
+	case OP_SET_LE:
+		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));
+		break;
+	case OP_SET_GE:
+		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);
+		break;
+	case OP_SET_GT:
+		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));
+		break;
+
 	case OP_SET_B:
 		if (!value)			// (x < 0) --> 0
 			return replace_with_pseudo(insn, value_pseudo(0));
@@ -1177,7 +1220,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 		else if (value == bits)		// (x < ~0) --> (x != ~0)
 			return replace_binop_value(insn, OP_SET_NE, value);
 		else				// (x < y) --> (x <= (y-1))
-			changed |= replace_binop_value(insn, OP_SET_BE, value - 1);
+			changed |= replace_binop_value(insn, OP_SET_BE, (value - 1) & bits);
 		break;
 	case OP_SET_AE:
 		if (!value)			// (x >= 0) --> 1
@@ -1187,7 +1230,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 		else if (value == bits)		// (x >= ~0) --> (x == ~0)
 			return replace_binop_value(insn, OP_SET_EQ, value);
 		else				// (x >= y) --> (x > (y-1)
-			changed |= replace_binop_value(insn, OP_SET_A, value - 1);
+			changed |= replace_binop_value(insn, OP_SET_A, (value - 1) & bits);
 		break;
 	case OP_SET_BE:
 		if (!value)			// (x <= 0) --> (x == 0)
@@ -1217,7 +1260,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 	switch (DEF_OPCODE(def, src1)) {
 	case OP_SEXT:				// sext(x) cmp C --> x cmp trunc(C)
 		osize = def->orig_type->bit_size;
-		if (is_signed_constant(value, osize, def->size)) {
+		if (is_signed_constant(value, osize, size)) {
 			insn->itype = def->orig_type;
 			insn->src2 = value_pseudo(zero_extend(value, osize));
 			return replace_pseudo(insn, &insn->src1, def->src);
@@ -1238,13 +1281,13 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			}
 			break;
 		case OP_SET_LT: case OP_SET_LE:
-			if (value >= sign_bit(osize))
+			if (value < sign_bit(size))
 				return replace_with_value(insn, 1);
 			else
 				return replace_with_value(insn, 0);
 			break;
 		case OP_SET_GE: case OP_SET_GT:
-			if (value >= sign_bit(osize))
+			if (value < sign_bit(size))
 				return replace_with_value(insn, 0);
 			else
 				return replace_with_value(insn, 1);
@@ -1263,13 +1306,13 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 		}
 		switch (insn->opcode) {
 		case OP_SET_LT: case OP_SET_LE:
-			if (sign_extend(value, def->size) > (long long)bits)
+			if (sign_extend(value, size) > (long long)bits)
 				return replace_with_value(insn, 1);
 			else
 				return replace_with_value(insn, 0);
 			break;
 		case OP_SET_GE: case OP_SET_GT:
-			if (sign_extend(value, def->size) > (long long)bits)
+			if (sign_extend(value, size) > (long long)bits)
 				return replace_with_value(insn, 0);
 			else
 				return replace_with_value(insn, 1);
@@ -2265,6 +2308,20 @@ static int simplify_select(struct instruction *insn)
 		if (src2 == def->src1 && src1 == def->src2)
 			return replace_with_pseudo(insn, src1); // SEL(y!=x,x,y) --> x
 		break;
+	case OP_SET_LE: case OP_SET_LT:
+	case OP_SET_BE: case OP_SET_B:
+		if (!one_use(cond))
+			break;
+		// SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a)
+		def->opcode = opcode_negate(def->opcode);
+		return switch_pseudo(insn, &insn->src2, insn, &insn->src3);
+	case OP_SET_GT:
+		if (one_use(cond) && is_zero(def->src2)) {
+			if (is_negate_of(src2, src1))
+				// SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a)
+				return replace_opcode(def, OP_SET_GE);
+		}
+		break;
 	case OP_SEL:
 		if (constant(def->src2) && constant(def->src3)) {
 			// Is the def of the conditional another select?
diff --git a/validation/optim/canonical-abs.c b/validation/optim/canonical-abs.c
new file mode 100644
index 00000000..1bd6d89a
--- /dev/null
+++ b/validation/optim/canonical-abs.c
@@ -0,0 +1,11 @@
+_Bool abs0(int a) { return (a < 0 ? -a : a) == (a >= 0 ? a : -a); }
+_Bool abs1(int a) { return (a < 0 ? -a : a) == (a >  0 ? a : -a); }
+_Bool abs2(int a) { return (a < 0 ? -a : a) == (a <= 0 ? -a : a); }
+
+/*
+ * check-name: canonical-abs1
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/canonical-cmpe-minmax.c b/validation/optim/canonical-cmpe-minmax.c
new file mode 100644
index 00000000..32b27243
--- /dev/null
+++ b/validation/optim/canonical-cmpe-minmax.c
@@ -0,0 +1,16 @@
+#define SMAX __INT_MAX__
+#define SMIN (-__INT_MAX__-1)
+
+int le_smax(int a) { return (a <= (SMAX - 1)) == (a != SMAX); }
+int gt_smax(int a) { return (a >  (SMAX - 1)) == (a == SMAX); }
+
+int lt_smin(int a) { return (a <  (SMIN + 1)) == (a == SMIN); }
+int ge_smin(int a) { return (a >= (SMIN + 1)) == (a != SMIN); }
+
+/*
+ * check-name: canonical-cmpe-minmax
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/canonical-cmps-minmax.c b/validation/optim/canonical-cmps-minmax.c
new file mode 100644
index 00000000..48927f49
--- /dev/null
+++ b/validation/optim/canonical-cmps-minmax.c
@@ -0,0 +1,16 @@
+#define SMAX __INT_MAX__
+#define SMIN (-__INT_MAX__-1)
+
+int lt_smax(int a) { return (a <  SMAX) == (a != SMAX); }
+int ge_smax(int a) { return (a >= SMAX) == (a == SMAX); }
+
+int le_smin(int a) { return (a <= SMIN) == (a == SMIN); }
+int gt_smin(int a) { return (a >  SMIN) == (a != SMIN); }
+
+/*
+ * check-name: canonical-cmps-minmax
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/canonical-cmps-sel.c b/validation/optim/canonical-cmps-sel.c
new file mode 100644
index 00000000..bba5e5c8
--- /dev/null
+++ b/validation/optim/canonical-cmps-sel.c
@@ -0,0 +1,25 @@
+_Bool sel_lts(int a, int b, int x, int y)
+{
+	return ((a < b) ? x : y) == ((a >= b) ? y : x);
+}
+_Bool sel_les(int a, int b, int x, int y)
+{
+	return ((a <= b) ? x : y) == ((a > b) ? y : x);
+}
+
+_Bool sel_ltu(unsigned int a, unsigned int b, int x, int y)
+{
+	return ((a < b) ? x : y) == ((a >= b) ? y : x);
+}
+_Bool sel_leu(unsigned int a, unsigned int b, int x, int y)
+{
+	return ((a <= b) ? x : y) == ((a > b) ? y : x);
+}
+
+/*
+ * check-name: canonical-cmps-sel
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/canonical-cmps.c b/validation/optim/canonical-cmps.c
new file mode 100644
index 00000000..42801cdc
--- /dev/null
+++ b/validation/optim/canonical-cmps.c
@@ -0,0 +1,16 @@
+_Bool lt_p(int a) { return (a >  0) == (a >=  1); }
+_Bool ge_p(int a) { return (a <= 0) == (a <   1); }
+
+_Bool lt_m(int a) { return (a <  0) == (a <= -1); }
+_Bool ge_m(int a) { return (a >= 0) == (a >  -1); }
+
+_Bool lt_x(int a) { return (a <= 1234) == (a < 1235); }
+_Bool ge_x(int a) { return (a >= 1234) == (a > 1233); }
+
+/*
+ * check-name: canonical-cmps
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext-simm.c b/validation/optim/cmp-sext-simm.c
index a8b2a8f9..57a4df1d 100644
--- a/validation/optim/cmp-sext-simm.c
+++ b/validation/optim/cmp-sext-simm.c
@@ -4,21 +4,45 @@
 
 static int lt_ge0(int x) { return (sext(x) <  (POS + 0)) == 1; }
 static int lt_ge1(int x) { return (sext(x) <  (POS + 1)) == 1; }
+static int lt_ge2(int x) { return (sext(x) <  (POS + 2)) == 1; }
+static int lt_gex(int x) { return (sext(x) <  (POS<< 1)) == 1; }
+static int lt_gey(int x) { return (sext(x) <  (POS<< 3)) == 1; }
 static int le_ge0(int x) { return (sext(x) <= (POS + 0)) == 1; }
 static int le_ge1(int x) { return (sext(x) <= (POS + 1)) == 1; }
-static int lt_lt0(int x) { return (sext(x) <  (NEG - 0)) == 1; }
-static int lt_lt1(int x) { return (sext(x) <  (NEG - 1)) == 1; }
-static int le_lt0(int x) { return (sext(x) <= (NEG - 0)) == 1; }
-static int le_lt1(int x) { return (sext(x) <= (NEG - 1)) == 1; }
-
-static int gt_ge0(int x) { return (sext(x) >  (POS + 0)) == 0; }
-static int gt_ge1(int x) { return (sext(x) >  (POS + 1)) == 0; }
+static int le_ge2(int x) { return (sext(x) <= (POS + 2)) == 1; }
+static int le_gex(int x) { return (sext(x) <= (POS<< 1)) == 1; }
+static int le_gey(int x) { return (sext(x) <= (POS<< 3)) == 1; }
 static int ge_ge0(int x) { return (sext(x) >= (POS + 0)) == 0; }
 static int ge_ge1(int x) { return (sext(x) >= (POS + 1)) == 0; }
-static int gt_lt0(int x) { return (sext(x) >  (NEG - 0)) == 0; }
-static int gt_lt1(int x) { return (sext(x) >  (NEG - 1)) == 0; }
-static int ge_lt0(int x) { return (sext(x) >= (NEG - 0)) == 0; }
-static int ge_lt1(int x) { return (sext(x) >= (NEG - 1)) == 0; }
+static int ge_ge2(int x) { return (sext(x) >= (POS + 2)) == 0; }
+static int ge_gex(int x) { return (sext(x) >= (POS<< 1)) == 0; }
+static int ge_gey(int x) { return (sext(x) >= (POS<< 3)) == 0; }
+static int gt_ge0(int x) { return (sext(x) >  (POS + 0)) == 0; }
+static int gt_ge1(int x) { return (sext(x) >  (POS + 1)) == 0; }
+static int gt_ge2(int x) { return (sext(x) >  (POS + 2)) == 0; }
+static int gt_gex(int x) { return (sext(x) >  (POS<< 1)) == 0; }
+static int gt_gey(int x) { return (sext(x) >  (POS<< 3)) == 0; }
+
+static int lt_lt0(int x) { return (sext(x) <  (NEG - 0)) == 0; }
+static int lt_lt1(int x) { return (sext(x) <  (NEG - 1)) == 0; }
+static int lt_lt2(int x) { return (sext(x) <  (NEG - 2)) == 0; }
+static int lt_ltx(int x) { return (sext(x) <  (NEG<< 1)) == 0; }
+static int lt_lty(int x) { return (sext(x) <  (NEG<< 3)) == 0; }
+static int le_lt0(int x) { return (sext(x) <= (NEG - 0)) == 0; }
+static int le_lt1(int x) { return (sext(x) <= (NEG - 1)) == 0; }
+static int le_lt2(int x) { return (sext(x) <= (NEG - 2)) == 0; }
+static int le_ltx(int x) { return (sext(x) <= (NEG<< 1)) == 0; }
+static int le_lty(int x) { return (sext(x) <= (NEG<< 3)) == 0; }
+static int ge_lt0(int x) { return (sext(x) >= (NEG - 0)) == 1; }
+static int ge_lt1(int x) { return (sext(x) >= (NEG - 1)) == 1; }
+static int ge_lt2(int x) { return (sext(x) >= (NEG - 2)) == 1; }
+static int ge_ltx(int x) { return (sext(x) >= (NEG<< 1)) == 1; }
+static int ge_lty(int x) { return (sext(x) >= (NEG<< 3)) == 1; }
+static int gt_lt0(int x) { return (sext(x) >  (NEG - 0)) == 1; }
+static int gt_lt1(int x) { return (sext(x) >  (NEG - 1)) == 1; }
+static int gt_lt2(int x) { return (sext(x) >  (NEG - 2)) == 1; }
+static int gt_ltx(int x) { return (sext(x) >  (NEG<< 1)) == 1; }
+static int gt_lty(int x) { return (sext(x) >  (NEG<< 3)) == 1; }
 
 /*
  * check-name: cmp-sext-simm
diff --git a/validation/optim/cmps-minmax.c b/validation/optim/cmps-minmax.c
new file mode 100644
index 00000000..5802cdbc
--- /dev/null
+++ b/validation/optim/cmps-minmax.c
@@ -0,0 +1,16 @@
+#define SMAX __INT_MAX__
+#define SMIN (-__INT_MAX__-1)
+
+int lt_smin(int a) { return (a <  SMIN) == 0; }
+int le_smax(int a) { return (a <= SMAX) == 1; }
+
+int ge_smin(int a) { return (a >= SMIN) == 1; }
+int gt_smax(int a) { return (a >  SMAX) == 0; }
+
+/*
+ * check-name: cmps-minmax
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */