[SPARSE 0/4] fix/improve canonicalization of signed compares

linux-sparse.vger.kernel.org archive mirror
 help / color / mirror / Atom feed

* [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).