* [PATCH 01/10] cmps: make clearer we're using the operands' size
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 02/10] cmps: fix simplification of sext(x) + signed compare of {SMAX,SMIN} Luc Van Oostenryck
` (9 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 02/10] cmps: fix simplification of sext(x) + signed compare of {SMAX,SMIN}
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 01/10] cmps: make clearer we're using the operands' size Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 03/10] cmpu: fix canonicalization of unsigned (x {<,>=} C) --> (x {<=,>} C-1) Luc Van Oostenryck
` (8 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 03/10] cmpu: fix canonicalization of unsigned (x {<,>=} C) --> (x {<=,>} C-1)
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 01/10] cmps: make clearer we're using the operands' size Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 02/10] cmps: fix simplification of sext(x) + signed compare of {SMAX,SMIN} Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 04/10] cmps: add testcases for simplification of signed compares Luc Van Oostenryck
` (7 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 04/10] cmps: add testcases for simplification of signed compares
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
` (2 preceding siblings ...)
2021-01-26 22:04 ` [PATCH 03/10] cmpu: fix canonicalization of unsigned (x {<,>=} C) --> (x {<=,>} C-1) Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 05/10] cmps: simplify signed compares with SMIN or SMAX Luc Van Oostenryck
` (6 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 05/10] cmps: simplify signed compares with SMIN or SMAX
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
` (3 preceding siblings ...)
2021-01-26 22:04 ` [PATCH 04/10] cmps: add testcases for simplification of signed compares Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 06/10] cmps: canonicalize signed compares with SMIN/SMAX Luc Van Oostenryck
` (5 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 06/10] cmps: canonicalize signed compares with SMIN/SMAX
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
` (4 preceding siblings ...)
2021-01-26 22:04 ` [PATCH 05/10] cmps: simplify signed compares with SMIN or SMAX Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 07/10] cmps: canonicalize SMIN/SMAX +- 1 --> EQ/NE Luc Van Oostenryck
` (4 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 07/10] cmps: canonicalize SMIN/SMAX +- 1 --> EQ/NE
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
` (5 preceding siblings ...)
2021-01-26 22:04 ` [PATCH 06/10] cmps: canonicalize signed compares with SMIN/SMAX Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 08/10] cmps: canonicalize signed compares with constant Luc Van Oostenryck
` (3 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 08/10] cmps: canonicalize signed compares with constant
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
` (6 preceding siblings ...)
2021-01-26 22:04 ` [PATCH 07/10] cmps: canonicalize SMIN/SMAX +- 1 --> EQ/NE Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 09/10] cmps: canonicalize SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a) Luc Van Oostenryck
` (2 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 09/10] cmps: canonicalize SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a)
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
` (7 preceding siblings ...)
2021-01-26 22:04 ` [PATCH 08/10] cmps: canonicalize signed compares with constant Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-01-26 22:04 ` [PATCH 10/10] cmps: canonicalize SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a) Luc Van Oostenryck
2021-04-17 17:16 ` [PATCH 00/10] simplify and canonicalize signed compares Linus Torvalds
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH 10/10] cmps: canonicalize SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a)
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
` (8 preceding siblings ...)
2021-01-26 22:04 ` [PATCH 09/10] cmps: canonicalize SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a) Luc Van Oostenryck
@ 2021-01-26 22:04 ` Luc Van Oostenryck
2021-04-17 17:16 ` [PATCH 00/10] simplify and canonicalize signed compares Linus Torvalds
10 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-01-26 22:04 UTC (permalink / raw)
To: linux-sparse; +Cc: 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
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH 00/10] simplify and canonicalize signed compares
2021-01-26 22:04 [PATCH 00/10] simplify and canonicalize signed compares Luc Van Oostenryck
` (9 preceding siblings ...)
2021-01-26 22:04 ` [PATCH 10/10] cmps: canonicalize SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a) Luc Van Oostenryck
@ 2021-04-17 17:16 ` Linus Torvalds
2021-04-17 18:20 ` Luc Van Oostenryck
10 siblings, 1 reply; 13+ messages in thread
From: Linus Torvalds @ 2021-04-17 17:16 UTC (permalink / raw)
To: Luc Van Oostenryck; +Cc: Sparse Mailing-list
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
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: [PATCH 00/10] simplify and canonicalize signed compares
2021-04-17 17:16 ` [PATCH 00/10] simplify and canonicalize signed compares Linus Torvalds
@ 2021-04-17 18:20 ` Luc Van Oostenryck
0 siblings, 0 replies; 13+ messages in thread
From: Luc Van Oostenryck @ 2021-04-17 18:20 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Sparse Mailing-list
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
^ permalink raw reply [flat|nested] 13+ messages in thread