[PATCH 00/10] simplify and canonicalize signed compares

[PATCH 00/10] simplify and canonicalize signed compares

[Luc Van Oostenryck]

This series fixes and improves the simplification and the
canonicalization of signed compares.

Luc Van Oostenryck (10):
  cmps: make clearer we're using the operands' size
  cmps: fix simplification of sext(x) + signed compare of {SMAX,SMIN}
  cmpu: fix canonicalization of unsigned (x {<,>=} C) --> (x {<=,>} C-1)
  cmps: add testcases for simplification of signed compares
  cmps: simplify signed compares with SMIN or SMAX
  cmps: canonicalize signed compares with SMIN/SMAX
  cmps: canonicalize SMIN/SMAX +- 1 --> EQ/NE
  cmps: canonicalize signed compares with constant
  cmps: canonicalize SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a)
  cmps: canonicalize SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a)

 simplify.c                               | 73 +++++++++++++++++++++---
 validation/optim/canonical-abs.c         | 11 ++++
 validation/optim/canonical-cmpe-minmax.c | 16 ++++++
 validation/optim/canonical-cmps-minmax.c | 16 ++++++
 validation/optim/canonical-cmps-sel.c    | 25 ++++++++
 validation/optim/canonical-cmps.c        | 16 ++++++
 validation/optim/cmp-sext-simm.c         | 46 +++++++++++----
 validation/optim/cmps-minmax.c           | 16 ++++++
 8 files changed, 200 insertions(+), 19 deletions(-)
 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


base-commit: 0fb77bb6e5429575f52b5e26f06db031f93de057
-- 
2.30.0

[PATCH 01/10] cmps: make clearer we're using the operands' size

[Luc Van Oostenryck]

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 bf6397dfd582..2f6f41c249dc 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);
-- 
2.30.0

[PATCH 02/10] cmps: fix simplification of sext(x) + signed compare of {SMAX,SMIN}

[Luc Van Oostenryck]

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 2f6f41c249dc..9a24058f6e55 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 a8b2a8f9feff..57a4df1d57b1 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
-- 
2.30.0

[PATCH 03/10] cmpu: fix canonicalization of unsigned (x {<,>=} C) --> (x {<=,>} C-1)

[Luc Van Oostenryck]

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 9a24058f6e55..a306828c1c4b 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)
-- 
2.30.0

[PATCH 04/10] cmps: add testcases for simplification of signed compares

[Luc Van Oostenryck]

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 000000000000..0809a52d445b
--- /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 000000000000..c72819244b95
--- /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 000000000000..bab09282d241
--- /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 000000000000..f0a0effc7954
--- /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 000000000000..f42664b21e04
--- /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 000000000000..ded3286cf752
--- /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
+ */
-- 
2.30.0

[PATCH 05/10] cmps: simplify signed compares with SMIN or SMAX

[Luc Van Oostenryck]

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 a306828c1c4b..096742d51a16 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 ded3286cf752..5802cdbcafd1 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
-- 
2.30.0

[PATCH 06/10] cmps: canonicalize signed compares with SMIN/SMAX

[Luc Van Oostenryck]

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 096742d51a16..f7c6c68d4ce9 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 bab09282d241..48927f49db6e 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
-- 
2.30.0

[PATCH 07/10] cmps: canonicalize SMIN/SMAX +- 1 --> EQ/NE

[Luc Van Oostenryck]

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 f7c6c68d4ce9..ad3adb11595e 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 c72819244b95..32b272435fa2 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
-- 
2.30.0

[PATCH 08/10] cmps: canonicalize signed compares with constant

[Luc Van Oostenryck]

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 ad3adb11595e..b29f5d5b2444 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 f42664b21e04..42801cdce520 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
-- 
2.30.0

[PATCH 09/10] cmps: canonicalize SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a)

[Luc Van Oostenryck]

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 b29f5d5b2444..10cdf50dcbf1 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 f0a0effc7954..bba5e5c894f8 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
-- 
2.30.0

[PATCH 10/10] cmps: canonicalize SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a)

[Luc Van Oostenryck]

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 10cdf50dcbf1..584078ddca89 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 0809a52d445b..1bd6d89a3ad5 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
-- 
2.30.0

Re: [PATCH 00/10] simplify and canonicalize signed compares

[Linus Torvalds]

On Tue, Jan 26, 2021 at 7:45 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> This series fixes and improves the simplification and the
> canonicalization of signed compares.

Hmm. Sorry for not replying earlier, but I just checked the most
common simplification of signed compares, and it didn't work.

This:

    _Bool test(int a)
    {
        return a >=0 && a < 16;
    }

should simplify to be the same as

    _Bool test(int a)
    {
        return (unsigned)a < 16;
    }

but it doesn't. It generates the silly - but straightforward - "two
comparisons and a 'and' of the result".

In fact, the recent canonicalizations means that the compare against
zero is actually pessimised, and ">= 0" becomes "> 0xffffffff", which
is often a much more expensive operation.

This came up because I was looking at some kernel code that did
exactly that "check that a signed value is within proper bounds", and
the zero check is a very common bound.

               Linus

Re: [PATCH 00/10] simplify and canonicalize signed compares

[Luc Van Oostenryck]

On Sat, Apr 17, 2021 at 10:16:31AM -0700, Linus Torvalds wrote:
> On Tue, Jan 26, 2021 at 7:45 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > This series fixes and improves the simplification and the
> > canonicalization of signed compares.
> 
> Hmm. Sorry for not replying earlier, but I just checked the most
> common simplification of signed compares, and it didn't work.
> 
> This:
> 
>     _Bool test(int a)
>     {
>         return a >=0 && a < 16;
>     }
> 
> should simplify to be the same as
> 
>     _Bool test(int a)
>     {
>         return (unsigned)a < 16;
>     }
> 
> but it doesn't. It generates the silly - but straightforward - "two
> comparisons and a 'and' of the result".

Yes, I've a draft for this but I still needs to add some tests and such.

> In fact, the recent canonicalizations means that the compare against
> zero is actually pessimised, and ">= 0" becomes "> 0xffffffff", which
> is often a much more expensive operation.

Yes, I'm aware of the problem, more or less.
When I did the canonicalization, I wondered what was better:
* canonicalize toward 0
* canonicalize toward the smallest

I choose the later because at the moment it was somehow advantageous
because it reduced by 2 some patterns (it allows to eliminate all >=
and all <; when doing it toward 0 you can eliminate one set for positive
and the other one for negatives values so you need both sets). The
compare with -1 instead of with 0 didn't looked much problematic and
relatively rare. But in the following days I realized it was in fact
quite annoying.

So, yes, it's something I'll change very soon.

-- Luc