* [SPARSE 0/4] fix/improve canonicalization of signed compares
@ 2021-04-18 15:32 Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 1/4] canonicalize constant signed compares toward zero Luc Van Oostenryck
` (3 more replies)
0 siblings, 4 replies; 5+ messages in thread
From: Luc Van Oostenryck @ 2021-04-18 15:32 UTC (permalink / raw)
To: linux-sparse; +Cc: Linus Torvalds, Luc Van Oostenryck
This series contains the following:
1) signed compares against a constant are now canonicalized towards 0
so that (x >= 0) doesn't become (x > -1)
2) a signed compare like (x >= 0 && x <= C) is simplified into the
unsigned compare: (x <= C)
This series is also available for review and testing at:
git://git.kernel.org/pub/scm/devel/sparse/sparse.git optim-and-cmp
Luc Van Oostenryck (4):
canonicalize constant signed compares toward zero
add testcases for AND(x > 0, x <= C) --> x u<= C
add helper is_positive()
simplify AND(x >= 0, x < C) --> (unsigned)x < C
linearize.h | 5 ++
simplify.c | 45 +++++++++++++---
validation/optim/canonical-cmp-zero.c | 74 +++++++++++++++++++++++++++
validation/optim/range-check1.c | 16 ++++++
validation/optim/range-check2.c | 14 +++++
5 files changed, 148 insertions(+), 6 deletions(-)
create mode 100644 validation/optim/canonical-cmp-zero.c
create mode 100644 validation/optim/range-check1.c
create mode 100644 validation/optim/range-check2.c
base-commit: eb4cdd21b7d0cedbbeff7f70e24473706ccce5a6
--
2.31.1
^ permalink raw reply [flat|nested] 5+ messages in thread
* [SPARSE 1/4] canonicalize constant signed compares toward zero
2021-04-18 15:32 [SPARSE 0/4] fix/improve canonicalization of signed compares Luc Van Oostenryck
@ 2021-04-18 15:32 ` Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 2/4] add testcases for AND(x > 0, x <= C) --> x u<= C Luc Van Oostenryck
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: Luc Van Oostenryck @ 2021-04-18 15:32 UTC (permalink / raw)
To: linux-sparse; +Cc: Linus Torvalds, Luc Van Oostenryck
Currently, signed compares against a constant are canonicalized
toward the smallest possible constant. So, the following
canonicalization are done:
x < 256 --> x <= 255
x < -2047 --> x <= -2048
This has two advantages:
1) it maximalizes the number of constants possible for a given bit size.
2) it allows to remove all < and all >=
But it has also a serious disadvantages: a simple comparison against
zero, like:
x >= 0
is canonicalized into:
x > -1
Which can be more costly for some architectures if translated as such ,
is also less readable than the version using 0 and is also sometimes
quite more complicated to match in some simplification patterns.
So, canonicalize it using 'towards 0' / using the smallest constant
in absolute value.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 34 +++++++++---
validation/optim/canonical-cmp-zero.c | 74 +++++++++++++++++++++++++++
2 files changed, 102 insertions(+), 6 deletions(-)
create mode 100644 validation/optim/canonical-cmp-zero.c
diff --git a/simplify.c b/simplify.c
index 9e3514d838a9..e0e4f9ebcba9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1178,38 +1178,52 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
switch (insn->opcode) {
case OP_SET_LT:
+ if (!value)
+ break;
if (value == sign_bit(size)) // (x < SMIN) --> 0
return replace_with_pseudo(insn, value_pseudo(0));
if (value == sign_mask(size)) // (x < SMAX) --> (x != SMAX)
return replace_opcode(insn, OP_SET_NE);
if (value == sign_bit(size) + 1)// (x < SMIN + 1) --> (x == SMIN)
return replace_binop_value(insn, OP_SET_EQ, sign_bit(size));
- changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
+ if (!(value & sign_bit(size)))
+ changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
break;
case OP_SET_LE:
+ if (!value)
+ break;
if (value == sign_mask(size)) // (x <= SMAX) --> 1
return replace_with_pseudo(insn, value_pseudo(1));
if (value == sign_bit(size)) // (x <= SMIN) --> (x == SMIN)
return replace_opcode(insn, OP_SET_EQ);
if (value == sign_mask(size) - 1) // (x <= SMAX - 1) --> (x != SMAX)
return replace_binop_value(insn, OP_SET_NE, sign_mask(size));
+ if (value & sign_bit(size))
+ changed |= replace_binop_value(insn, OP_SET_LT, (value + 1) & bits);
break;
case OP_SET_GE:
+ if (!value)
+ break;
if (value == sign_bit(size)) // (x >= SMIN) --> 1
return replace_with_pseudo(insn, value_pseudo(1));
if (value == sign_mask(size)) // (x >= SMAX) --> (x == SMAX)
return replace_opcode(insn, OP_SET_EQ);
if (value == sign_bit(size) + 1)// (x >= SMIN + 1) --> (x != SMIN)
return replace_binop_value(insn, OP_SET_NE, sign_bit(size));
- changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
+ if (!(value & sign_bit(size)))
+ changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
break;
case OP_SET_GT:
+ if (!value)
+ break;
if (value == sign_mask(size)) // (x > SMAX) --> 0
return replace_with_pseudo(insn, value_pseudo(0));
if (value == sign_bit(size)) // (x > SMIN) --> (x != SMIN)
return replace_opcode(insn, OP_SET_NE);
if (value == sign_mask(size) - 1) // (x > SMAX - 1) --> (x == SMAX)
return replace_binop_value(insn, OP_SET_EQ, sign_mask(size));
+ if (value & sign_bit(size))
+ changed |= replace_binop_value(insn, OP_SET_GE, (value + 1) & bits);
break;
case OP_SET_B:
@@ -1271,8 +1285,10 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
if ((value & bits) != value)
return replace_with_value(insn, 1);
break;
- case OP_SET_LE:
+ case OP_SET_LE: case OP_SET_LT:
value = sign_extend(value, def->size);
+ if (insn->opcode == OP_SET_LT)
+ value -= 1;
if (bits & sign_bit(def->size))
break;
if (value < 0)
@@ -1282,8 +1298,10 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
if (value == 0)
return replace_opcode(insn, OP_SET_EQ);
break;
- case OP_SET_GT:
+ case OP_SET_GT: case OP_SET_GE:
value = sign_extend(value, def->size);
+ if (insn->opcode == OP_SET_GE)
+ value -= 1;
if (bits & sign_bit(def->size))
break;
if (value < 0)
@@ -1340,16 +1358,20 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
if (bits >= value)
return replace_with_value(insn, 1);
break;
+ case OP_SET_LT:
+ value -= 1;
case OP_SET_LE:
- value = sign_extend(value, def->size);
if (bits & sign_bit(def->size)) {
+ value = sign_extend(value, def->size);
if (value >= -1)
return replace_with_value(insn, 1);
}
break;
+ case OP_SET_GE:
+ value -= 1;
case OP_SET_GT:
- value = sign_extend(value, def->size);
if (bits & sign_bit(def->size)) {
+ value = sign_extend(value, def->size);
if (value >= -1)
return replace_with_value(insn, 0);
}
diff --git a/validation/optim/canonical-cmp-zero.c b/validation/optim/canonical-cmp-zero.c
new file mode 100644
index 000000000000..e01a00e637b6
--- /dev/null
+++ b/validation/optim/canonical-cmp-zero.c
@@ -0,0 +1,74 @@
+int f00(int x) { return x >= 0; }
+int f01(int x) { return x > -1; }
+int f02(int x) { return x < 1; }
+int f03(int x) { return x <= 0; }
+
+int f10(int x) { return x < 16; }
+int f11(int x) { return x <= 15; }
+
+int f20(int x) { return x > -9; }
+int f21(int x) { return x >= -8; }
+
+/*
+ * check-name: canonical-cmp-zero
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+f00:
+.L0:
+ <entry-point>
+ setge.32 %r2 <- %arg1, $0
+ ret.32 %r2
+
+
+f01:
+.L2:
+ <entry-point>
+ setge.32 %r5 <- %arg1, $0
+ ret.32 %r5
+
+
+f02:
+.L4:
+ <entry-point>
+ setle.32 %r8 <- %arg1, $0
+ ret.32 %r8
+
+
+f03:
+.L6:
+ <entry-point>
+ setle.32 %r11 <- %arg1, $0
+ ret.32 %r11
+
+
+f10:
+.L8:
+ <entry-point>
+ setle.32 %r14 <- %arg1, $15
+ ret.32 %r14
+
+
+f11:
+.L10:
+ <entry-point>
+ setle.32 %r17 <- %arg1, $15
+ ret.32 %r17
+
+
+f20:
+.L12:
+ <entry-point>
+ setge.32 %r20 <- %arg1, $0xfffffff8
+ ret.32 %r20
+
+
+f21:
+.L14:
+ <entry-point>
+ setge.32 %r23 <- %arg1, $0xfffffff8
+ ret.32 %r23
+
+
+ * check-output-end
+ */
--
2.31.1
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [SPARSE 2/4] add testcases for AND(x > 0, x <= C) --> x u<= C
2021-04-18 15:32 [SPARSE 0/4] fix/improve canonicalization of signed compares Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 1/4] canonicalize constant signed compares toward zero Luc Van Oostenryck
@ 2021-04-18 15:32 ` Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 3/4] add helper is_positive() Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 4/4] simplify AND(x >= 0, x < C) --> (unsigned)x < C Luc Van Oostenryck
3 siblings, 0 replies; 5+ messages in thread
From: Luc Van Oostenryck @ 2021-04-18 15:32 UTC (permalink / raw)
To: linux-sparse; +Cc: Linus Torvalds, Luc Van Oostenryck
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
validation/optim/range-check1.c | 17 +++++++++++++++++
validation/optim/range-check2.c | 15 +++++++++++++++
2 files changed, 32 insertions(+)
create mode 100644 validation/optim/range-check1.c
create mode 100644 validation/optim/range-check2.c
diff --git a/validation/optim/range-check1.c b/validation/optim/range-check1.c
new file mode 100644
index 000000000000..82b939917da4
--- /dev/null
+++ b/validation/optim/range-check1.c
@@ -0,0 +1,17 @@
+#define N 1024
+
+_Bool check_ok(long i)
+{
+ return i >= 0 && i < N;
+}
+
+/*
+ * check-name: range-check1
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: setbe\\..*0x3ff
+ * check-output-excludes: set[lga][te]\\.
+ * check-output-excludes: set[ab]\\.
+ */
diff --git a/validation/optim/range-check2.c b/validation/optim/range-check2.c
new file mode 100644
index 000000000000..f565b84ea9db
--- /dev/null
+++ b/validation/optim/range-check2.c
@@ -0,0 +1,15 @@
+#define N 1024
+
+_Bool check_ok(int i)
+{
+ return (i >= 0 && i < N) == (((unsigned int)i) < N);
+}
+
+/*
+ * check-name: range-check2
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
--
2.31.1
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [SPARSE 3/4] add helper is_positive()
2021-04-18 15:32 [SPARSE 0/4] fix/improve canonicalization of signed compares Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 1/4] canonicalize constant signed compares toward zero Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 2/4] add testcases for AND(x > 0, x <= C) --> x u<= C Luc Van Oostenryck
@ 2021-04-18 15:32 ` Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 4/4] simplify AND(x >= 0, x < C) --> (unsigned)x < C Luc Van Oostenryck
3 siblings, 0 replies; 5+ messages in thread
From: Luc Van Oostenryck @ 2021-04-18 15:32 UTC (permalink / raw)
To: linux-sparse; +Cc: Linus Torvalds, Luc Van Oostenryck
Add a small helper to test if a pseudo is a positive (= non-negative)
constant (for a given bitsize).
It's meant to make some conditions more readable.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
linearize.h | 5 +++++
1 file changed, 5 insertions(+)
diff --git a/linearize.h b/linearize.h
index 7909b01f29c5..65f54c28a7d6 100644
--- a/linearize.h
+++ b/linearize.h
@@ -58,6 +58,11 @@ static inline bool is_nonzero(pseudo_t pseudo)
return pseudo->type == PSEUDO_VAL && pseudo->value != 0;
}
+static inline bool is_positive(pseudo_t pseudo, unsigned size)
+{
+ return pseudo->type == PSEUDO_VAL && !(pseudo->value & sign_bit(size));
+}
+
struct multijmp {
struct basic_block *target;
--
2.31.1
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [SPARSE 4/4] simplify AND(x >= 0, x < C) --> (unsigned)x < C
2021-04-18 15:32 [SPARSE 0/4] fix/improve canonicalization of signed compares Luc Van Oostenryck
` (2 preceding siblings ...)
2021-04-18 15:32 ` [SPARSE 3/4] add helper is_positive() Luc Van Oostenryck
@ 2021-04-18 15:32 ` Luc Van Oostenryck
3 siblings, 0 replies; 5+ messages in thread
From: Luc Van Oostenryck @ 2021-04-18 15:32 UTC (permalink / raw)
To: linux-sparse; +Cc: Linus Torvalds, Luc Van Oostenryck
Such compares with a signed value are relatively common and can be
easily be simplified into a single unsigned compare. So, do it.
Note: This simplification triggers only 27 times in a x86-64 defconfig
kernel. I expected more but I suppose it's because most checks
aren't done against a constant or are done with unsigned values.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 11 +++++++++++
validation/optim/range-check1.c | 1 -
validation/optim/range-check2.c | 1 -
3 files changed, 11 insertions(+), 2 deletions(-)
diff --git a/simplify.c b/simplify.c
index e0e4f9ebcba9..0a29db189b55 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1920,6 +1920,17 @@ static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
if (def->src1 == defr->src1 && def->src2 == defr->src2)
return replace_with_value(insn, 0);
}
+ if (def->opcode == OP_SET_GE && is_zero(def->src2)) {
+ switch (DEF_OPCODE(defr, *p2)) {
+ case OP_SET_LE:
+ if (!is_positive(defr->src2, defr->itype->bit_size))
+ break;
+ // (x >= 0) && (x <= C) --> (x u<= C)
+ insn->itype = defr->itype;
+ replace_binop(insn, OP_SET_BE, &insn->src1, defr->src1, &insn->src2, defr->src2);
+ return REPEAT_CSE;
+ }
+ }
break;
case OP_OR:
if (DEF_OPCODE(defr, *p2) == OP_OR) {
diff --git a/validation/optim/range-check1.c b/validation/optim/range-check1.c
index 82b939917da4..358da045c456 100644
--- a/validation/optim/range-check1.c
+++ b/validation/optim/range-check1.c
@@ -8,7 +8,6 @@ _Bool check_ok(long i)
/*
* check-name: range-check1
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
*
* check-output-ignore
* check-output-contains: setbe\\..*0x3ff
diff --git a/validation/optim/range-check2.c b/validation/optim/range-check2.c
index f565b84ea9db..69c01b9d36d5 100644
--- a/validation/optim/range-check2.c
+++ b/validation/optim/range-check2.c
@@ -8,7 +8,6 @@ _Bool check_ok(int i)
/*
* check-name: range-check2
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
*
* check-output-ignore
* check-output-returns: 1
--
2.31.1
^ permalink raw reply related [flat|nested] 5+ messages in thread
end of thread, other threads:[~2021-04-18 15:32 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-04-18 15:32 [SPARSE 0/4] fix/improve canonicalization of signed compares Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 1/4] canonicalize constant signed compares toward zero Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 2/4] add testcases for AND(x > 0, x <= C) --> x u<= C Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 3/4] add helper is_positive() Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 4/4] simplify AND(x >= 0, x < C) --> (unsigned)x < C Luc Van Oostenryck
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).