From 1cac46932aa290e4192ed178a26b0da6486d8cd3 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Wed, 6 Jan 2021 22:43:42 +0100
Subject: cmps: make clearer we're using the operands' size

When handling compares of an {zero,sign}-extended value, the
size of these extended values are used but this size is just
the operands' size of the compares.

Make this clearer by using a single variable 'size' for it.

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

diff --git a/simplify.c b/simplify.c
index bf6397df..2f6f41c2 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1162,7 +1162,8 @@ 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;
@@ -1217,7 +1218,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);
@@ -1263,13 +1264,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);
-- 
cgit 1.2.3-korg


From 33fda43cf26ce3e312e6cb4882821117b68056a2 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Wed, 6 Jan 2021 22:43:42 +0100
Subject: cmps: fix simplification of sext(x) + signed compare of {SMAX,SMIN}

Commit a1c1b9236d5d ("cmp: simplify sext(x) cmps {SMAX,SMIN}")
had a double error (wrong size and wrong compare direction) which
was hidden because of too narrow testcases.

So, fix the simplification and extend the testcases.

Fixes: a1c1b9236d5d4af1681a45ced26f8350bd7721c2
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                       |  4 ++--
 validation/optim/cmp-sext-simm.c | 46 ++++++++++++++++++++++++++++++----------
 2 files changed, 37 insertions(+), 13 deletions(-)

diff --git a/simplify.c b/simplify.c
index 2f6f41c2..9a24058f 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1239,13 +1239,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);
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
-- 
cgit 1.2.3-korg


From d7af8d6cc223559ece17c435dcdbd04f9ef74d3d Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Tue, 26 Jan 2021 00:24:13 +0100
Subject: cmpu: fix canonicalization of unsigned (x {<,>=} C) --> (x {<=,>}
 C-1)

In Sparse, the PSEUDO_VALUEs are required to be truncated at their
effective size. For example, for a 32-bit instruction and Sparse using
64-bit integers, a pseudo of -1 must contain the value 0x00000000ffffffff,
not 0xffffffffffffffff.

Add the missing truncation in the canonicalization here.

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

diff --git a/simplify.c b/simplify.c
index 9a24058f..a306828c 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1178,7 +1178,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
@@ -1188,7 +1188,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)
-- 
cgit 1.2.3-korg


From 5db6d62e83623808fc29f6a6da636ddf5c658110 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Tue, 5 Jan 2021 23:31:10 +0100
Subject: cmps: add testcases for simplification of signed compares

Signed compares miss some simplifications/canonicalizations.
Add some testcases for them.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/canonical-abs.c         | 12 ++++++++++++
 validation/optim/canonical-cmpe-minmax.c | 17 +++++++++++++++++
 validation/optim/canonical-cmps-minmax.c | 17 +++++++++++++++++
 validation/optim/canonical-cmps-sel.c    | 26 ++++++++++++++++++++++++++
 validation/optim/canonical-cmps.c        | 17 +++++++++++++++++
 validation/optim/cmps-minmax.c           | 17 +++++++++++++++++
 6 files changed, 106 insertions(+)
 create mode 100644 validation/optim/canonical-abs.c
 create mode 100644 validation/optim/canonical-cmpe-minmax.c
 create mode 100644 validation/optim/canonical-cmps-minmax.c
 create mode 100644 validation/optim/canonical-cmps-sel.c
 create mode 100644 validation/optim/canonical-cmps.c
 create mode 100644 validation/optim/cmps-minmax.c

diff --git a/validation/optim/canonical-abs.c b/validation/optim/canonical-abs.c
new file mode 100644
index 00000000..0809a52d
--- /dev/null
+++ b/validation/optim/canonical-abs.c
@@ -0,0 +1,12 @@
+_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-known-to-fail
+ *
+ * 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..c7281924
--- /dev/null
+++ b/validation/optim/canonical-cmpe-minmax.c
@@ -0,0 +1,17 @@
+#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-known-to-fail
+ *
+ * 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..bab09282
--- /dev/null
+++ b/validation/optim/canonical-cmps-minmax.c
@@ -0,0 +1,17 @@
+#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-known-to-fail
+ *
+ * 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..f0a0effc
--- /dev/null
+++ b/validation/optim/canonical-cmps-sel.c
@@ -0,0 +1,26 @@
+_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-known-to-fail
+ *
+ * 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..f42664b2
--- /dev/null
+++ b/validation/optim/canonical-cmps.c
@@ -0,0 +1,17 @@
+_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-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmps-minmax.c b/validation/optim/cmps-minmax.c
new file mode 100644
index 00000000..ded3286c
--- /dev/null
+++ b/validation/optim/cmps-minmax.c
@@ -0,0 +1,17 @@
+#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-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
-- 
cgit 1.2.3-korg


From b5a4f039a159ade2f01af7b10cd7615cbc42ba35 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Tue, 5 Jan 2021 00:01:08 +0100
Subject: cmps: simplify signed compares with SMIN or SMAX

Simplify away signed compares with SMIN or SMAX which can be
statically be determined to be always true or always false.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                     | 17 +++++++++++++++++
 validation/optim/cmps-minmax.c |  1 -
 2 files changed, 17 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index a306828c..096742d5 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1170,6 +1170,23 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 	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));
+		break;
+	case OP_SET_LE:
+		if (value == sign_mask(size))	// (x <= SMAX) --> 1
+			return replace_with_pseudo(insn, value_pseudo(1));
+		break;
+	case OP_SET_GE:
+		if (value == sign_bit(size))	// (x >= SMIN) --> 1
+			return replace_with_pseudo(insn, value_pseudo(1));
+		break;
+	case OP_SET_GT:
+		if (value == sign_mask(size))	// (x >  SMAX) --> 0
+			return replace_with_pseudo(insn, value_pseudo(0));
+		break;
+
 	case OP_SET_B:
 		if (!value)			// (x < 0) --> 0
 			return replace_with_pseudo(insn, value_pseudo(0));
diff --git a/validation/optim/cmps-minmax.c b/validation/optim/cmps-minmax.c
index ded3286c..5802cdbc 100644
--- a/validation/optim/cmps-minmax.c
+++ b/validation/optim/cmps-minmax.c
@@ -10,7 +10,6 @@ int gt_smax(int a) { return (a >  SMAX) == 0; }
 /*
  * check-name: cmps-minmax
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
cgit 1.2.3-korg


From 61010b15b6074fcfee4256b848b1123a57d61947 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Wed, 6 Jan 2021 00:16:08 +0100
Subject: cmps: canonicalize signed compares with SMIN/SMAX

The remaining compares with SMIN or SMAX are equivalent to an
equality testing. For example, (x < SMAX) is the same as (x != SMAX).

Canonicalize these to the equality testing since these are usually
simpler to handle.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                               | 8 ++++++++
 validation/optim/canonical-cmps-minmax.c | 1 -
 2 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 096742d5..f7c6c68d 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1173,18 +1173,26 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 	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);
 		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);
 		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);
 		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);
 		break;
 
 	case OP_SET_B:
diff --git a/validation/optim/canonical-cmps-minmax.c b/validation/optim/canonical-cmps-minmax.c
index bab09282..48927f49 100644
--- a/validation/optim/canonical-cmps-minmax.c
+++ b/validation/optim/canonical-cmps-minmax.c
@@ -10,7 +10,6 @@ int gt_smin(int a) { return (a >  SMIN) == (a != SMIN); }
 /*
  * check-name: canonical-cmps-minmax
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
cgit 1.2.3-korg


From 7b1d4ca6b5ad28ccf8e489c58fe99c00b1436bfb Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Wed, 13 Jan 2021 00:49:16 +0100
Subject: cmps: canonicalize SMIN/SMAX +- 1 --> EQ/NE

Compares with SMIN  + 1 or SMAX - 1 are equivalent to an equality
testing. For example, (x < SMIN + 1) is the same as (x == SMIN).

Canonicalize these to the equality testing since these are usually
simpler to handle.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                               | 8 ++++++++
 validation/optim/canonical-cmpe-minmax.c | 1 -
 2 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index f7c6c68d..ad3adb11 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1175,24 +1175,32 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			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));
 		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));
 		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:
diff --git a/validation/optim/canonical-cmpe-minmax.c b/validation/optim/canonical-cmpe-minmax.c
index c7281924..32b27243 100644
--- a/validation/optim/canonical-cmpe-minmax.c
+++ b/validation/optim/canonical-cmpe-minmax.c
@@ -10,7 +10,6 @@ int ge_smin(int a) { return (a >= (SMIN + 1)) == (a != SMIN); }
 /*
  * check-name: canonical-cmpe-minmax
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
cgit 1.2.3-korg


From 54b6c78979c2a131a55c5439937e5e6bd8584b06 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Tue, 5 Jan 2021 00:01:08 +0100
Subject: cmps: canonicalize signed compares with constant

Modify the constants to canonicalize (x < C) to (x <= (C-1)) and
(x <= C) to (x > (C-1)). This choice is partially arbitrary but
1) it's the one with the smallest positive constants,
2) it eliminates all OP_SET_LT & OP_SET_GE with a constant.
A disadvantage of this choice is that we lost some compares with 0:
(x < 0) is now canonicalized into (x <= -1).

Note: Another good choice would be to canonicalize using the
      smallest absolute constants. This would keep compares with 0
      but would also keep the 4 kinds of comparison.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                        | 2 ++
 validation/optim/canonical-cmps.c | 1 -
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index ad3adb11..b29f5d5b 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1177,6 +1177,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			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
@@ -1193,6 +1194,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			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
diff --git a/validation/optim/canonical-cmps.c b/validation/optim/canonical-cmps.c
index f42664b2..42801cdc 100644
--- a/validation/optim/canonical-cmps.c
+++ b/validation/optim/canonical-cmps.c
@@ -10,7 +10,6 @@ _Bool ge_x(int a) { return (a >= 1234) == (a > 1233); }
 /*
  * check-name: canonical-cmps
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
cgit 1.2.3-korg


From a5a61b2e345bac65ef1c256daeb7842539ab1262 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Fri, 22 Jan 2021 23:56:05 +0100
Subject: cmps: canonicalize SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a)

Both compares and OP_SELECT are anti-symmetrical: swapping
the arguments is equivalent to inversing the condition.
As consequence, when combined, they're symmetrical:
swapping the arguments of the compare (or equivalently reversing
the direction of the compare) and swapping the operand of the
OP_SELECT is a no-op, both forms are equivalent.

So, canonicalize these to always use OP_GT or OP_GE.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                            | 7 +++++++
 validation/optim/canonical-cmps-sel.c | 1 -
 2 files changed, 7 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index b29f5d5b..10cdf50d 100644
--- a/simplify.c
+++ b/simplify.c
@@ -2301,6 +2301,13 @@ 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_SEL:
 		if (constant(def->src2) && constant(def->src3)) {
 			// Is the def of the conditional another select?
diff --git a/validation/optim/canonical-cmps-sel.c b/validation/optim/canonical-cmps-sel.c
index f0a0effc..bba5e5c8 100644
--- a/validation/optim/canonical-cmps-sel.c
+++ b/validation/optim/canonical-cmps-sel.c
@@ -19,7 +19,6 @@ _Bool sel_leu(unsigned int a, unsigned int b, int x, int y)
 /*
  * check-name: canonical-cmps-sel
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
cgit 1.2.3-korg


From 95827edfcb2daa42fa18ce555f2c30910fdc2493 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Fri, 22 Jan 2021 23:56:32 +0100
Subject: cmps: canonicalize SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a)

When computing the absolute value using an expression like:
	(a > 0) ? a : -a
it's irrelevant to use '>' or '>=', both will give the same
result since 0 is its own negation.

Canonicalize these equivalent expressions, such that OP_GE
is always used.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                       | 14 ++++++++++++++
 validation/optim/canonical-abs.c |  1 -
 2 files changed, 14 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 10cdf50d..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
@@ -2308,6 +2315,13 @@ static int simplify_select(struct instruction *insn)
 		// 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
index 0809a52d..1bd6d89a 100644
--- a/validation/optim/canonical-abs.c
+++ b/validation/optim/canonical-abs.c
@@ -5,7 +5,6 @@ _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-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
cgit 1.2.3-korg