All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH 00/16] simplify & canonicalize compares
@ 2020-11-08  1:19 Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 01/16] cmp: adapt testcase for compares' canonicalization Luc Van Oostenryck
                   ` (9 more replies)
  0 siblings, 10 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

This series contains a series of simplifications and
canonicalizations, mainly ones involving sign or zero extension.

Luc Van Oostenryck (16):
  cmp: adapt testcase for compares' canonicalization
  cmp: add testcases for the simplification of compares
  cmp: add signed/unsigned to opcode table
  cmp: move some code in a separate function: simplify_compare_constant()
  cmp: use a few helpers for the simplification of compares
  cmp: canonicalize unsigned (x {<,>=} C) --> (x {<=,>} C-1)
  cmp: simplify unsigned (x {<=,>} UMAX) into {1,0}
  cmp: canonicalize unsigned compare with UMAX or UMAX-1
  cmp: canonicalize unsigned (x {<=,>} SMAX)
  cmp: simplify sext(x) cmp C --> x cmp C
  cmp: simplify zext(x) cmp C --> x cmp C
  cmp: simplify sext(x) cmps {SMAX,SMIN}
  cmp: canonicalize sext(x) cmpu C (with C >= SMAX)
  cmp: simplify zext(x) cmps C
  cmp: simplify zext(x) cmpu C
  cmp: simplify compares and sign/zero extend

 opcode.c                          |   3 +-
 opcode.def                        | 164 ++++++++++----------
 opcode.h                          |   8 +-
 simplify.c                        | 240 +++++++++++++++++++++++++-----
 validation/optim/canonical-cmp.c  | 125 ++--------------
 validation/optim/canonical-cmpu.c |  15 ++
 validation/optim/cmp-sext-sext.c  |  17 +++
 validation/optim/cmp-sext-simm.c  |  29 ++++
 validation/optim/cmp-sext-uimm.c  |  25 ++++
 validation/optim/cmp-sext.c       |  23 +++
 validation/optim/cmp-zext-simm.c  |  23 +++
 validation/optim/cmp-zext-uimm0.c |  21 +++
 validation/optim/cmp-zext-uimm1.c |  15 ++
 validation/optim/cmp-zext-uimm2.c |  29 ++++
 validation/optim/cmp-zext-zext.c  |  17 +++
 validation/optim/cmp-zext.c       |  17 +++
 validation/optim/set-uimm1.c      |  10 ++
 validation/optim/set-uimm2.c      |  12 ++
 validation/optim/set-uimm3.c      |  10 ++
 validation/optim/zext-cmpu.c      |  16 ++
 20 files changed, 582 insertions(+), 237 deletions(-)
 create mode 100644 validation/optim/canonical-cmpu.c
 create mode 100644 validation/optim/cmp-sext-sext.c
 create mode 100644 validation/optim/cmp-sext-simm.c
 create mode 100644 validation/optim/cmp-sext-uimm.c
 create mode 100644 validation/optim/cmp-sext.c
 create mode 100644 validation/optim/cmp-zext-simm.c
 create mode 100644 validation/optim/cmp-zext-uimm0.c
 create mode 100644 validation/optim/cmp-zext-uimm1.c
 create mode 100644 validation/optim/cmp-zext-uimm2.c
 create mode 100644 validation/optim/cmp-zext-zext.c
 create mode 100644 validation/optim/cmp-zext.c
 create mode 100644 validation/optim/set-uimm1.c
 create mode 100644 validation/optim/set-uimm2.c
 create mode 100644 validation/optim/set-uimm3.c
 create mode 100644 validation/optim/zext-cmpu.c

-- 
2.29.2


^ permalink raw reply	[flat|nested] 17+ messages in thread
* [PATCH 01/16] cmp: adapt testcase for compares' canonicalization
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 02/16] cmp: add testcases for the simplification of compares Luc Van Oostenryck
                   ` (8 subsequent siblings)
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

The current testcase, because it's just checking test-linearize's
output as-is, is very sensitive to small simplification changes.

Fix this by changing the tests into equivalent tests and then just
checking that these tests return '1'. This allows to test only what
really matters for canonicalization and make these tests very robust.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/canonical-cmp.c | 125 ++++---------------------------
 1 file changed, 14 insertions(+), 111 deletions(-)

diff --git a/validation/optim/canonical-cmp.c b/validation/optim/canonical-cmp.c
index e0ca7db36368..9b930b1cbeaa 100644
--- a/validation/optim/canonical-cmp.c
+++ b/validation/optim/canonical-cmp.c
@@ -1,124 +1,27 @@
 typedef	  signed int	sint;
 typedef	unsigned int	uint;
 
-sint seq(sint p, sint a) { return (123 == p) ? a : 0; }
-sint sne(sint p, sint a) { return (123 != p) ? a : 0; }
+sint seq(sint p, sint a) { return (123 == p) == (p == 123); }
+sint sne(sint p, sint a) { return (123 != p) == (p != 123); }
 
-sint slt(sint p, sint a) { return (123 >  p) ? a : 0; }
-sint sle(sint p, sint a) { return (123 >= p) ? a : 0; }
-sint sge(sint p, sint a) { return (123 <= p) ? a : 0; }
-sint sgt(sint p, sint a) { return (123 <  p) ? a : 0; }
+sint slt(sint p, sint a) { return (123 >  p) == (p <  123); }
+sint sle(sint p, sint a) { return (123 >= p) == (p <= 123); }
+sint sge(sint p, sint a) { return (123 <= p) == (p >= 123); }
+sint sgt(sint p, sint a) { return (123 <  p) == (p >  123); }
 
-uint ueq(uint p, uint a) { return (123 == p) ? a : 0; }
-uint une(uint p, uint a) { return (123 != p) ? a : 0; }
+uint ueq(uint p, uint a) { return (123 == p) == (p == 123); }
+uint une(uint p, uint a) { return (123 != p) == (p != 123); }
 
-uint ubt(uint p, uint a) { return (123 >  p) ? a : 0; }
-uint ube(uint p, uint a) { return (123 >= p) ? a : 0; }
-uint uae(uint p, uint a) { return (123 <= p) ? a : 0; }
-uint uat(uint p, uint a) { return (123 <  p) ? a : 0; }
+uint ubt(uint p, uint a) { return (123 >  p) == (p <  123); }
+uint ube(uint p, uint a) { return (123 >= p) == (p <= 123); }
+uint uae(uint p, uint a) { return (123 <= p) == (p >= 123); }
+uint uat(uint p, uint a) { return (123 <  p) == (p >  123); }
 
 /*
  * check-name: canonical-cmp
+ * check-description: check that constants move rightside
  * check-command: test-linearize -Wno-decl $file
  *
+ * check-output-ignore
  * check-output-excludes: \\$123,
- *
- * check-output-start
-seq:
-.L0:
-	<entry-point>
-	seteq.32    %r3 <- %arg1, $123
-	select.32   %r4 <- %r3, %arg2, $0
-	ret.32      %r4
-
-
-sne:
-.L2:
-	<entry-point>
-	setne.32    %r8 <- %arg1, $123
-	select.32   %r9 <- %r8, %arg2, $0
-	ret.32      %r9
-
-
-slt:
-.L4:
-	<entry-point>
-	setlt.32    %r13 <- %arg1, $123
-	select.32   %r14 <- %r13, %arg2, $0
-	ret.32      %r14
-
-
-sle:
-.L6:
-	<entry-point>
-	setle.32    %r18 <- %arg1, $123
-	select.32   %r19 <- %r18, %arg2, $0
-	ret.32      %r19
-
-
-sge:
-.L8:
-	<entry-point>
-	setge.32    %r23 <- %arg1, $123
-	select.32   %r24 <- %r23, %arg2, $0
-	ret.32      %r24
-
-
-sgt:
-.L10:
-	<entry-point>
-	setgt.32    %r28 <- %arg1, $123
-	select.32   %r29 <- %r28, %arg2, $0
-	ret.32      %r29
-
-
-ueq:
-.L12:
-	<entry-point>
-	seteq.32    %r33 <- %arg1, $123
-	select.32   %r34 <- %r33, %arg2, $0
-	ret.32      %r34
-
-
-une:
-.L14:
-	<entry-point>
-	setne.32    %r38 <- %arg1, $123
-	select.32   %r39 <- %r38, %arg2, $0
-	ret.32      %r39
-
-
-ubt:
-.L16:
-	<entry-point>
-	setb.32     %r43 <- %arg1, $123
-	select.32   %r44 <- %r43, %arg2, $0
-	ret.32      %r44
-
-
-ube:
-.L18:
-	<entry-point>
-	setbe.32    %r48 <- %arg1, $123
-	select.32   %r49 <- %r48, %arg2, $0
-	ret.32      %r49
-
-
-uae:
-.L20:
-	<entry-point>
-	setae.32    %r53 <- %arg1, $123
-	select.32   %r54 <- %r53, %arg2, $0
-	ret.32      %r54
-
-
-uat:
-.L22:
-	<entry-point>
-	seta.32     %r58 <- %arg1, $123
-	select.32   %r59 <- %r58, %arg2, $0
-	ret.32      %r59
-
-
- * check-output-end
  */
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 02/16] cmp: add testcases for the simplification of compares
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 01/16] cmp: adapt testcase for compares' canonicalization Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 03/16] cmp: add signed/unsigned to opcode table Luc Van Oostenryck
                   ` (7 subsequent siblings)
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/canonical-cmpu.c | 16 ++++++++++++++++
 validation/optim/cmp-sext-sext.c  | 18 ++++++++++++++++++
 validation/optim/cmp-sext-simm.c  | 30 ++++++++++++++++++++++++++++++
 validation/optim/cmp-sext-uimm.c  | 26 ++++++++++++++++++++++++++
 validation/optim/cmp-sext.c       | 24 ++++++++++++++++++++++++
 validation/optim/cmp-zext-simm.c  | 24 ++++++++++++++++++++++++
 validation/optim/cmp-zext-uimm0.c | 21 +++++++++++++++++++++
 validation/optim/cmp-zext-uimm1.c | 16 ++++++++++++++++
 validation/optim/cmp-zext-uimm2.c | 30 ++++++++++++++++++++++++++++++
 validation/optim/cmp-zext-zext.c  | 18 ++++++++++++++++++
 validation/optim/cmp-zext.c       | 18 ++++++++++++++++++
 validation/optim/set-uimm1.c      | 11 +++++++++++
 validation/optim/set-uimm2.c      | 13 +++++++++++++
 validation/optim/set-uimm3.c      | 11 +++++++++++
 validation/optim/zext-cmpu.c      | 17 +++++++++++++++++
 15 files changed, 293 insertions(+)
 create mode 100644 validation/optim/canonical-cmpu.c
 create mode 100644 validation/optim/cmp-sext-sext.c
 create mode 100644 validation/optim/cmp-sext-simm.c
 create mode 100644 validation/optim/cmp-sext-uimm.c
 create mode 100644 validation/optim/cmp-sext.c
 create mode 100644 validation/optim/cmp-zext-simm.c
 create mode 100644 validation/optim/cmp-zext-uimm0.c
 create mode 100644 validation/optim/cmp-zext-uimm1.c
 create mode 100644 validation/optim/cmp-zext-uimm2.c
 create mode 100644 validation/optim/cmp-zext-zext.c
 create mode 100644 validation/optim/cmp-zext.c
 create mode 100644 validation/optim/set-uimm1.c
 create mode 100644 validation/optim/set-uimm2.c
 create mode 100644 validation/optim/set-uimm3.c
 create mode 100644 validation/optim/zext-cmpu.c

diff --git a/validation/optim/canonical-cmpu.c b/validation/optim/canonical-cmpu.c
new file mode 100644
index 000000000000..482408aa90c1
--- /dev/null
+++ b/validation/optim/canonical-cmpu.c
@@ -0,0 +1,16 @@
+// canonicalize to == or !=
+int cmp_ltu_eq0(unsigned int x) { return (x <  1) == (x == 0); }
+int cmp_geu_ne0(unsigned int x) { return (x >= 1) == (x != 0); }
+
+// canonicalize to the smaller value
+int cmp_ltu(unsigned int x) { return (x <  256) == (x <= 255); }
+int cmp_geu(unsigned int x) { return (x >= 256) == (x >  255); }
+
+/*
+ * check-name: canonical-cmpu
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext-sext.c b/validation/optim/cmp-sext-sext.c
new file mode 100644
index 000000000000..ba6ed54e940c
--- /dev/null
+++ b/validation/optim/cmp-sext-sext.c
@@ -0,0 +1,18 @@
+#define T(TYPE)			__##TYPE##_TYPE__
+#define cmp(TYPE, X, OP, Y)	((T(TYPE)) X OP (T(TYPE)) Y)
+#define TEST(T1, T2, X, OP, Y)	cmp(T1, X, OP, Y) == cmp(T2, X, OP, Y)
+
+#define ARGS(TYPE)	T(TYPE) a, T(TYPE)b
+
+_Bool cmpe_sext_sext(ARGS(INT32)) { return TEST(UINT64, UINT32, a, ==, b); }
+_Bool cmps_sext_sext(ARGS(INT32)) { return TEST( INT64,  INT32, a, < , b); }
+_Bool cmpu_sext_sext(ARGS(INT32)) { return TEST(UINT64, UINT32, a, < , b); }
+
+/*
+ * check-name: cmp-sext-sext
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext-simm.c b/validation/optim/cmp-sext-simm.c
new file mode 100644
index 000000000000..c2099a6b8876
--- /dev/null
+++ b/validation/optim/cmp-sext-simm.c
@@ -0,0 +1,30 @@
+#define sext(X)	((long long) (X))
+#define POS	(1LL << 31)
+#define NEG	(-POS - 1)
+
+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 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 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; }
+
+/*
+ * check-name: cmp-sext-simm
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext-uimm.c b/validation/optim/cmp-sext-uimm.c
new file mode 100644
index 000000000000..cc89a80694a1
--- /dev/null
+++ b/validation/optim/cmp-sext-uimm.c
@@ -0,0 +1,26 @@
+#define sext(X)	((unsigned long long) (X))
+#define POS	(1ULL << 31)
+#define NEG	((unsigned long long) -POS)
+
+int sext_ltu_p2(int x) { return (sext(x) <  (POS + 2)) == (x >= 0); }
+int sext_ltu_p1(int x) { return (sext(x) <  (POS + 1)) == (x >= 0); }
+int sext_ltu_p0(int x) { return (sext(x) <  (POS + 0)) == (x >= 0); }
+
+int sext_leu_p1(int x) { return (sext(x) <= (POS + 1)) == (x >= 0); }
+int sext_leu_p0(int x) { return (sext(x) <= (POS + 0)) == (x >= 0); }
+
+int sext_geu_m1(int x) { return (sext(x) >= (NEG - 1)) == (x < 0); }
+int sext_geu_m2(int x) { return (sext(x) >= (NEG - 2)) == (x < 0); }
+
+int sext_gtu_m1(int x) { return (sext(x) > (NEG - 1)) == (x < 0); }
+int sext_gtu_m2(int x) { return (sext(x) > (NEG - 2)) == (x < 0); }
+int sext_gtu_m3(int x) { return (sext(x) > (NEG - 3)) == (x < 0); }
+
+/*
+ * check-name: cmp-sext-uimm
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-sext.c b/validation/optim/cmp-sext.c
new file mode 100644
index 000000000000..2dd60fff064c
--- /dev/null
+++ b/validation/optim/cmp-sext.c
@@ -0,0 +1,24 @@
+#define T(TYPE)			__##TYPE##_TYPE__
+#define cmp(TYPE, X, OP, Y)	((T(TYPE)) X OP (T(TYPE)) Y)
+#define TEST(T1, T2, X, OP, Y)	cmp(T1, X, OP, Y) == cmp(T2, X, OP, Y)
+
+#define ARGS(TYPE)	T(TYPE) a, T(TYPE)b
+
+_Bool cmpe_sextp(ARGS(INT32)) { return TEST(UINT64, UINT32, a, ==, 0x7fffffff); }
+_Bool cmps_sextp(ARGS(INT32)) { return TEST( INT64,  INT32, a, < , 0x7fffffff); }
+_Bool cmpu_sextp(ARGS(INT32)) { return TEST(UINT64, UINT32, a, < , 0x7fffffff); }
+_Bool cmpe_sextn(ARGS(INT32)) { return TEST(UINT64, UINT32, a, ==, -1); }
+_Bool cmps_sextn(ARGS(INT32)) { return TEST( INT64,  INT32, a, < , -1); }
+_Bool cmpu_sextn(ARGS(INT32)) { return TEST(UINT64, UINT32, a, < , -1); }
+
+_Bool cmpltu_sext(int a) { return (a <  0x80000000ULL) == (a >= 0); }
+_Bool cmpgtu_sext(int a) { return (a >= 0x80000000ULL) == (a <  0); }
+
+/*
+ * check-name: cmp-sext
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-simm.c b/validation/optim/cmp-zext-simm.c
new file mode 100644
index 000000000000..f89f8f8baa62
--- /dev/null
+++ b/validation/optim/cmp-zext-simm.c
@@ -0,0 +1,24 @@
+#define ZEXT(X)	((long long)(X))
+#define BITS	((long long)(~0U))
+
+int zext_ult(unsigned int x) { return (ZEXT(x) <  (BITS + 1)) == 1; }
+int zext_ule(unsigned int x) { return (ZEXT(x) <= (BITS + 0)) == 1; }
+int zext_uge(unsigned int x) { return (ZEXT(x) >= (BITS + 1)) == 0; }
+int zext_ugt(unsigned int x) { return (ZEXT(x) >  (BITS + 0)) == 0; }
+
+int zext_0le(unsigned int x) { return (ZEXT(x) <=  0) == (x == 0); }
+int zext_0ge(unsigned int x) { return (ZEXT(x) >   0) == (x != 0); }
+
+int zext_llt(unsigned int x) { return (ZEXT(x) <  -1) == 0; }
+int zext_lle(unsigned int x) { return (ZEXT(x) <= -1) == 0; }
+int zext_lge(unsigned int x) { return (ZEXT(x) >= -1) == 1; }
+int zext_lgt(unsigned int x) { return (ZEXT(x) >  -1) == 1; }
+
+/*
+ * check-name: cmp-zext-simm
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-uimm0.c b/validation/optim/cmp-zext-uimm0.c
new file mode 100644
index 000000000000..f7bec338ca8f
--- /dev/null
+++ b/validation/optim/cmp-zext-uimm0.c
@@ -0,0 +1,21 @@
+#define zext(X)	((unsigned long long) (X))
+#define MAX	(1ULL << 32)
+
+#define TEST(X,OP,VAL)	(zext(X) OP (VAL)) == (X OP (VAL))
+
+int zext_ltu_0(unsigned int x) { return TEST(x, < , MAX); }
+int zext_ltu_m(unsigned int x) { return TEST(x, < , MAX - 1); }
+int zext_lte_0(unsigned int x) { return TEST(x, <=, MAX); }
+int zext_lte_m(unsigned int x) { return TEST(x, <=, MAX - 1); }
+int zext_gte_0(unsigned int x) { return TEST(x, >=, MAX); }
+int zext_gte_m(unsigned int x) { return TEST(x, >=, MAX - 1); }
+int zext_gtu_0(unsigned int x) { return TEST(x, > , MAX); }
+int zext_gtu_m(unsigned int x) { return TEST(x, > , MAX - 1); }
+
+/*
+ * check-name: cmp-zext-uimm0
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-uimm1.c b/validation/optim/cmp-zext-uimm1.c
new file mode 100644
index 000000000000..ffcdaad5c1bd
--- /dev/null
+++ b/validation/optim/cmp-zext-uimm1.c
@@ -0,0 +1,16 @@
+#define zext(X)	((unsigned long long) (X))
+#define BITS	((1ULL << 32) - 1)
+
+int zext_lt_p(unsigned int x) { return (zext(x) <  (BITS + 1)) == 1; }
+int zext_le_p(unsigned int x) { return (zext(x) <= (BITS    )) == 1; }
+int zext_ge_p(unsigned int x) { return (zext(x) >= (BITS + 1)) == 0; }
+int zext_gt_p(unsigned int x) { return (zext(x) >  (BITS    )) == 0; }
+
+/*
+ * check-name: cmp-zext-uimm1
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-uimm2.c b/validation/optim/cmp-zext-uimm2.c
new file mode 100644
index 000000000000..64f30b9a3df5
--- /dev/null
+++ b/validation/optim/cmp-zext-uimm2.c
@@ -0,0 +1,30 @@
+#define zext(X)	((unsigned long long) (X))
+
+int zext_ltu_q(unsigned x) { return (zext(x) <  0x100000001UL) == 1; }
+int zext_ltu_p(unsigned x) { return (zext(x) <  0x100000000UL) == 1; }
+int zext_ltu_0(unsigned x) { return (zext(x) <  0x0ffffffffUL) == (x <  0xffffffff); }
+int zext_ltu_m(unsigned x) { return (zext(x) <  0x0fffffffeUL) == (x <  0xfffffffe); }
+
+int zext_leu_q(unsigned x) { return (zext(x) <= 0x100000001UL) == 1; }
+int zext_leu_p(unsigned x) { return (zext(x) <= 0x100000000UL) == 1; }
+int zext_leu_0(unsigned x) { return (zext(x) <= 0x0ffffffffUL) == 1; }
+int zext_leu_m(unsigned x) { return (zext(x) <= 0x0fffffffeUL) == (x <= 0xfffffffe); }
+
+int zext_geu_q(unsigned x) { return (zext(x) >= 0x100000001UL) == 0; }
+int zext_geu_p(unsigned x) { return (zext(x) >= 0x100000000UL) == 0; }
+int zext_geu_0(unsigned x) { return (zext(x) >= 0x0ffffffffUL) == (x >= 0xffffffff); }
+int zext_geu_m(unsigned x) { return (zext(x) >= 0x0fffffffeUL) == (x >= 0xfffffffe); }
+
+int zext_gtu_q(unsigned x) { return (zext(x) >  0x100000001UL) == 0; }
+int zext_gtu_p(unsigned x) { return (zext(x) >  0x100000000UL) == 0; }
+int zext_gtu_0(unsigned x) { return (zext(x) >  0x0ffffffffUL) == 0; }
+int zext_gtu_m(unsigned x) { return (zext(x) >  0x0fffffffeUL) == (x >  0xfffffffe); }
+
+/*
+ * check-name: cmp-zext-uimm2
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext-zext.c b/validation/optim/cmp-zext-zext.c
new file mode 100644
index 000000000000..9f188297e214
--- /dev/null
+++ b/validation/optim/cmp-zext-zext.c
@@ -0,0 +1,18 @@
+#define T(TYPE)			__##TYPE##_TYPE__
+#define cmp(TYPE, X, OP, Y)	((T(TYPE)) X OP (T(TYPE)) Y)
+#define TEST(T1, T2, X, OP, Y)	cmp(T1, X, OP, Y) == cmp(T2, X, OP, Y)
+
+#define ARGS(TYPE)	T(TYPE) a, T(TYPE)b
+
+_Bool cmpe_zext_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, ==, b); }
+_Bool cmps_zext_zext(ARGS(UINT32)) { return TEST( INT64, UINT32, a, < , b); }
+_Bool cmpu_zext_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, < , b); }
+
+/*
+ * check-name: cmp-zext-zext
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cmp-zext.c b/validation/optim/cmp-zext.c
new file mode 100644
index 000000000000..ecee6b5e9101
--- /dev/null
+++ b/validation/optim/cmp-zext.c
@@ -0,0 +1,18 @@
+#define T(TYPE)			__##TYPE##_TYPE__
+#define cmp(TYPE, X, OP, Y)	((T(TYPE)) X OP (T(TYPE)) Y)
+#define TEST(T1, T2, X, OP, Y)	cmp(T1, X, OP, Y) == cmp(T2, X, OP, Y)
+
+#define ARGS(TYPE)	T(TYPE) a, T(TYPE)b
+
+_Bool cmpe_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, ==, 0xffffffff); }
+_Bool cmps_zext(ARGS(UINT32)) { return TEST( INT64, UINT32, a, < , 0xffffffff); }
+_Bool cmpu_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, < , 0xffffffff); }
+
+/*
+ * check-name: cmp-zext
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/set-uimm1.c b/validation/optim/set-uimm1.c
new file mode 100644
index 000000000000..d6928f59d044
--- /dev/null
+++ b/validation/optim/set-uimm1.c
@@ -0,0 +1,11 @@
+static _Bool setle_umax(unsigned int a) { return (a <= ~0) == 1; }
+static _Bool setgt_umax(unsigned int a) { return (a >  ~0) == 0; }
+
+/*
+ * check-name: set-uimm1
+ * check-command: test-linearize $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/set-uimm2.c b/validation/optim/set-uimm2.c
new file mode 100644
index 000000000000..efa326f532ce
--- /dev/null
+++ b/validation/optim/set-uimm2.c
@@ -0,0 +1,13 @@
+static _Bool setlt_umax(unsigned int a) { return (a <  ~0) == (a != ~0); }
+static _Bool setle_umax(unsigned int a) { return (a <= ~1) == (a != ~0); }
+static _Bool setge_umax(unsigned int a) { return (a >= ~0) == (a == ~0); }
+static _Bool setgt_umax(unsigned int a) { return (a >  ~1) == (a == ~0); }
+
+/*
+ * check-name: set-uimm2
+ * check-command: test-linearize $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/set-uimm3.c b/validation/optim/set-uimm3.c
new file mode 100644
index 000000000000..b72ef8d6e819
--- /dev/null
+++ b/validation/optim/set-uimm3.c
@@ -0,0 +1,11 @@
+int le(int x) { return (x <= 0x7fffffffU) == (x >= 0); }
+int gt(int x) { return (x >  0x7fffffffU) == (x <  0); }
+
+/*
+ * check-name: set-uimm3
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/zext-cmpu.c b/validation/optim/zext-cmpu.c
new file mode 100644
index 000000000000..279ed70e0fda
--- /dev/null
+++ b/validation/optim/zext-cmpu.c
@@ -0,0 +1,17 @@
+int ltg(unsigned x) { return (((long long)x) <  0x100000000ULL) == 1; }
+int ltl(unsigned x) { return (((long long)x) <  0x0ffffffffULL) == (x <  0xffffffffU); }
+int leg(unsigned x) { return (((long long)x) <= 0x0ffffffffULL) == 1; }
+int lel(unsigned x) { return (((long long)x) <= 0x0fffffffeULL) == (x <= 0xfffffffeU); }
+int geg(unsigned x) { return (((long long)x) >= 0x100000000ULL) == 0; }
+int gel(unsigned x) { return (((long long)x) >= 0x0ffffffffULL) == (x >= 0xffffffffU); }
+int gtg(unsigned x) { return (((long long)x) >  0x0ffffffffULL) == 0; }
+int gtl(unsigned x) { return (((long long)x) >  0x0fffffffeULL) == (x >  0xfffffffeU); }
+
+/*
+ * check-name: zext-cmpu
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 03/16] cmp: add signed/unsigned to opcode table
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 01/16] cmp: adapt testcase for compares' canonicalization Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 02/16] cmp: add testcases for the simplification of compares Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 04/16] cmp: move some code in a separate function: simplify_compare_constant() Luc Van Oostenryck
                   ` (6 subsequent siblings)
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

The opcode table allows to efficiently store some properties of
the IR instructions and the correspondence between some of them.

One of these correspondences the 'signed' / 'unsigned' version
of otherwise identical instructions. This is useful for some
transformation of compare instructions but is not present yet
in the table. So, add this now.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 opcode.c   |   3 +-
 opcode.def | 164 ++++++++++++++++++++++++++---------------------------
 opcode.h   |   8 ++-
 3 files changed, 90 insertions(+), 85 deletions(-)

diff --git a/opcode.c b/opcode.c
index 98ad768f8706..0cc7e435ed42 100644
--- a/opcode.c
+++ b/opcode.c
@@ -23,10 +23,11 @@
 #include "opcode.h"
 
 const struct opcode_table opcode_table[OP_LAST] = {
-#define OPCODE(OP,NG,SW,TF,N,FL)	\
+#define OPCODE(OP,NG,SW,SG,TF,N,FL)	\
 	[OP_##OP] = {			\
 		.negate   = OP_##NG,	\
 		.swap     = OP_##SW,	\
+		.sign     = OP_##SG,	\
 		.to_float = OP_##TF,	\
 		.arity    = N,		\
 		.flags    = FL,		\
diff --git a/opcode.def b/opcode.def
index c65722f0b9bb..2627abd4d894 100644
--- a/opcode.def
+++ b/opcode.def
@@ -1,114 +1,114 @@
-//      OPCODE          negated   swaped    float  arity, flags
+//     OPCODE        negated   swaped    sign   float  arity, flags
 
-OPCODE(BADOP,           BADOP,    BADOP,    BADOP, 0, OPF_NONE)
+OPCODE(BADOP,        BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
 
 /* Entry */
-OPCODE(ENTRY,           BADOP,    BADOP,    BADOP, 0, OPF_NONE)
+OPCODE(ENTRY,        BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
 
 /* Terminator */
-OPCODE(RET,             BADOP,    BADOP,    BADOP, 1, OPF_NONE)
-OPCODE(BR,              BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(CBR,             BADOP,    BADOP,    BADOP, 1, OPF_NONE)
-OPCODE(SWITCH,          BADOP,    BADOP,    BADOP, 1, OPF_NONE)
-OPCODE(UNREACH,         BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(COMPUTEDGOTO,    BADOP,    BADOP,    BADOP, 1, OPF_NONE)
+OPCODE(RET,          BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
+OPCODE(BR,           BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(CBR,          BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
+OPCODE(SWITCH,       BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
+OPCODE(UNREACH,      BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(COMPUTEDGOTO, BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
 OPCODE_RANGE(TERMINATOR, RET, COMPUTEDGOTO)
 
 /* Binary */
-OPCODE(ADD,             BADOP,    BADOP,    FADD,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
-OPCODE(MUL,             BADOP,    BADOP,    FMUL,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
-OPCODE(SUB,             BADOP,    BADOP,    FSUB,  2, OPF_TARGET|OPF_BINOP)
-OPCODE(DIVU,            BADOP,    BADOP,    FDIV,  2, OPF_TARGET|OPF_BINOP)
-OPCODE(DIVS,            BADOP,    BADOP,    FDIV,  2, OPF_TARGET|OPF_BINOP)
-OPCODE(MODU,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
-OPCODE(MODS,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
-OPCODE(SHL,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
-OPCODE(LSR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
-OPCODE(ASR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(ADD,          BADOP,    BADOP,    BADOP, FADD,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(MUL,          BADOP,    BADOP,    BADOP, FMUL,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(SUB,          BADOP,    BADOP,    BADOP, FSUB,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(DIVU,         BADOP,    BADOP,    DIVS,  FDIV,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(DIVS,         BADOP,    BADOP,    DIVU,  FDIV,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(MODU,         BADOP,    BADOP,    MODS,  BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(MODS,         BADOP,    BADOP,    MODU,  BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(LSR,          BADOP,    BADOP,    ASR,   BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(ASR,          BADOP,    BADOP,    LSR,   BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(SHL,          BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET|OPF_BINOP)
 
 /* Floating-point binops */
-OPCODE(FADD,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(FSUB,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(FMUL,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(FDIV,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
+OPCODE(FADD,         BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FSUB,         BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FMUL,         BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FDIV,         BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET)
 
 /* Logical */
-OPCODE(AND,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
-OPCODE(OR,              BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
-OPCODE(XOR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(AND,          BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(OR,           BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(XOR,          BADOP,    BADOP,    BADOP, BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
 OPCODE_RANGE(BINARY, ADD, XOR)
 
 /* floating-point comparison */
-OPCODE(FCMP_ORD,        FCMP_UNO, FCMP_ORD, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OEQ,        FCMP_UNE, FCMP_OEQ, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_ONE,        FCMP_UEQ, FCMP_ONE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UEQ,        FCMP_ONE, FCMP_UEQ, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UNE,        FCMP_OEQ, FCMP_UNE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OLT,        FCMP_UGE, FCMP_OGT, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OLE,        FCMP_UGT, FCMP_OGE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OGE,        FCMP_ULT, FCMP_OLE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_OGT,        FCMP_ULE, FCMP_OLT, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_ULT,        FCMP_OGE, FCMP_UGT, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_ULE,        FCMP_OGT, FCMP_UGE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UGE,        FCMP_OLT, FCMP_ULE, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UGT,        FCMP_OLE, FCMP_ULT, BADOP, 2, OPF_TARGET)
-OPCODE(FCMP_UNO,        FCMP_ORD, FCMP_UNO, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_ORD,     FCMP_UNO, FCMP_ORD, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OEQ,     FCMP_UNE, FCMP_OEQ, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_ONE,     FCMP_UEQ, FCMP_ONE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UEQ,     FCMP_ONE, FCMP_UEQ, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UNE,     FCMP_OEQ, FCMP_UNE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OLT,     FCMP_UGE, FCMP_OGT, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OLE,     FCMP_UGT, FCMP_OGE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OGE,     FCMP_ULT, FCMP_OLE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_OGT,     FCMP_ULE, FCMP_OLT, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_ULT,     FCMP_OGE, FCMP_UGT, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_ULE,     FCMP_OGT, FCMP_UGE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UGE,     FCMP_OLT, FCMP_ULE, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UGT,     FCMP_OLE, FCMP_ULT, BADOP, BADOP, 2, OPF_TARGET)
+OPCODE(FCMP_UNO,     FCMP_ORD, FCMP_UNO, BADOP, BADOP, 2, OPF_TARGET)
 OPCODE_RANGE(FPCMP, FCMP_ORD, FCMP_UNO)
 
 /* Binary comparison */
-OPCODE(SET_EQ,          SET_NE,   SET_EQ,   FCMP_OEQ, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
-OPCODE(SET_LT,          SET_GE,   SET_GT,   FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_LE,          SET_GT,   SET_GE,   FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_GE,          SET_LT,   SET_LE,   FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_GT,          SET_LE,   SET_LT,   FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_B,           SET_AE,   SET_A,    FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_BE,          SET_A,    SET_AE,   FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_AE,          SET_B,    SET_BE,   FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_A,           SET_BE,   SET_B,    FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
-OPCODE(SET_NE,          SET_EQ,   SET_NE,   FCMP_UNE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
+OPCODE(SET_EQ,       SET_NE,   SET_EQ,  SET_EQ, FCMP_OEQ, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
+OPCODE(SET_LT,       SET_GE,   SET_GT,  SET_B,  FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_SIGNED)
+OPCODE(SET_LE,       SET_GT,   SET_GE,  SET_BE, FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_SIGNED)
+OPCODE(SET_GE,       SET_LT,   SET_LE,  SET_AE, FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_SIGNED)
+OPCODE(SET_GT,       SET_LE,   SET_LT,  SET_A,  FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_SIGNED)
+OPCODE(SET_B,        SET_AE,   SET_A,   SET_LT, FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_UNSIGNED)
+OPCODE(SET_BE,       SET_A,    SET_AE,  SET_LE, FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_UNSIGNED)
+OPCODE(SET_AE,       SET_B,    SET_BE,  SET_GE, FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_UNSIGNED)
+OPCODE(SET_A,        SET_BE,   SET_B,   SET_GT, FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_UNSIGNED)
+OPCODE(SET_NE,       SET_EQ,   SET_NE,  SET_NE, FCMP_UNE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
 OPCODE_RANGE(BINCMP, SET_EQ, SET_NE)
 
 /* Uni */
-OPCODE(NOT,             BADOP,    BADOP,    BADOP, 1, OPF_TARGET|OPF_UNOP)
-OPCODE(NEG,             BADOP,    BADOP,    FNEG,  1, OPF_TARGET|OPF_UNOP)
-OPCODE(FNEG,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(TRUNC,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(ZEXT,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(SEXT,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(FCVTU,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(FCVTS,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(UCVTF,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(SCVTF,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(FCVTF,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(UTPTR,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(PTRTU,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(PTRCAST,         BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
+OPCODE(NOT,          BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET|OPF_UNOP)
+OPCODE(NEG,          BADOP,    BADOP,    BADOP, FNEG,  1, OPF_TARGET|OPF_UNOP)
+OPCODE(FNEG,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(TRUNC,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(ZEXT,         BADOP,    BADOP,    SEXT,  BADOP, 1, OPF_TARGET)
+OPCODE(SEXT,         BADOP,    BADOP,    ZEXT,  BADOP, 1, OPF_TARGET)
+OPCODE(FCVTU,        BADOP,    BADOP,    FCVTS, BADOP, 1, OPF_TARGET)
+OPCODE(FCVTS,        BADOP,    BADOP,    FCVTU, BADOP, 1, OPF_TARGET)
+OPCODE(UCVTF,        BADOP,    BADOP,    SCVTF, BADOP, 1, OPF_TARGET)
+OPCODE(SCVTF,        BADOP,    BADOP,    UCVTF, BADOP, 1, OPF_TARGET)
+OPCODE(FCVTF,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(UTPTR,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(PTRTU,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(PTRCAST,      BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
 OPCODE_RANGE(UNOP, NOT, PTRCAST)
-OPCODE(SYMADDR,         BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(SLICE,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
+OPCODE(SYMADDR,      BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(SLICE,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
 
 /* Select - three input values */
-OPCODE(SEL,             BADOP,    BADOP,    BADOP, 3, OPF_TARGET)
-OPCODE(FMADD,           BADOP,    BADOP,    BADOP, 3, OPF_TARGET)
+OPCODE(SEL,          BADOP,    BADOP,    BADOP, BADOP, 3, OPF_TARGET)
+OPCODE(FMADD,        BADOP,    BADOP,    BADOP, BADOP, 3, OPF_TARGET)
 
 /* Memory */
-OPCODE(LOAD,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(STORE,           BADOP,    BADOP,    BADOP, 1, OPF_NONE)
+OPCODE(LOAD,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(STORE,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
 
 /* Other */
-OPCODE(PHISOURCE,       BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(PHI,             BADOP,    BADOP,    BADOP, 0, OPF_TARGET)
-OPCODE(SETVAL,          BADOP,    BADOP,    BADOP, 0, OPF_TARGET)
-OPCODE(SETFVAL,         BADOP,    BADOP,    BADOP, 0, OPF_TARGET)
-OPCODE(CALL,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(INLINED_CALL,    BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(NOP,             BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(DEATHNOTE,       BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(ASM,             BADOP,    BADOP,    BADOP, 0, OPF_NONE)
+OPCODE(PHISOURCE,    BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(PHI,          BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
+OPCODE(SETVAL,       BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
+OPCODE(SETFVAL,      BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
+OPCODE(CALL,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
+OPCODE(INLINED_CALL, BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(NOP,          BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(DEATHNOTE,    BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(ASM,          BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
 
 /* Sparse tagging (line numbers, context, whatever) */
-OPCODE(CONTEXT,         BADOP,    BADOP,    BADOP, 0, OPF_NONE)
-OPCODE(RANGE,           BADOP,    BADOP,    BADOP, 3, OPF_NONE)
+OPCODE(CONTEXT,      BADOP,    BADOP,    BADOP, BADOP, 0, OPF_NONE)
+OPCODE(RANGE,        BADOP,    BADOP,    BADOP, BADOP, 3, OPF_NONE)
 
 /* Needed to translate SSA back to normal form */
-OPCODE(COPY,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
+OPCODE(COPY,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
diff --git a/opcode.h b/opcode.h
index bb94ec81c832..1524272f0320 100644
--- a/opcode.h
+++ b/opcode.h
@@ -4,7 +4,7 @@
 #include "symbol.h"
 
 enum opcode {
-#define OPCODE(OP,NG,SW,TF,N,FL)  OP_##OP,
+#define OPCODE(OP,NG,SW,SG,TF,N,FL)  OP_##OP,
 #define OPCODE_RANGE(OP,S,E)	OP_##OP = OP_##S, OP_##OP##_END = OP_##E,
 #include "opcode.def"
 #undef  OPCODE
@@ -15,9 +15,11 @@ enum opcode {
 extern const struct opcode_table {
 	int	negate:8;
 	int	swap:8;
+	int	sign:8;
 	int	to_float:8;
 	unsigned int arity:2;
-	unsigned int flags:6;
+	unsigned int :6;
+	unsigned int flags:8;
 #define			OPF_NONE	0
 #define			OPF_TARGET	(1 << 0)
 #define			OPF_COMMU	(1 << 1)
@@ -25,6 +27,8 @@ extern const struct opcode_table {
 #define			OPF_UNOP	(1 << 3)
 #define			OPF_BINOP	(1 << 4)
 #define			OPF_COMPARE	(1 << 5)
+#define			OPF_SIGNED	(1 << 6)
+#define			OPF_UNSIGNED	(1 << 7)
 } opcode_table[];
 
 
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 04/16] cmp: move some code in a separate function: simplify_compare_constant()
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
                   ` (2 preceding siblings ...)
  2020-11-08  1:19 ` [PATCH 03/16] cmp: add signed/unsigned to opcode table Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 05/16] cmp: use a few helpers for the simplification of compares Luc Van Oostenryck
                   ` (5 subsequent siblings)
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

simplify_constant_rightside() contains a few simplification
regarding unsigned compares but much more can be done for
unsigned and signed ones.

So, move the current simplification in a separate function.

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

diff --git a/simplify.c b/simplify.c
index f2aaa52de84b..3338b72e6845 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1057,6 +1057,43 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 	return 0;
 }
 
+static int simplify_compare_constant(struct instruction *insn, long long value)
+{
+	switch (insn->opcode) {
+	case OP_SET_B:
+		if (!value) {			// (x < 0) --> 0
+			return replace_with_pseudo(insn, value_pseudo(0));
+		} else if (value == 1) {	// (x < 1) --> (x == 0)
+			insn->src2 = value_pseudo(0);
+			insn->opcode = OP_SET_EQ;
+			return REPEAT_CSE;
+		}
+		break;
+	case OP_SET_AE:
+		if (!value) {			// (x >= 0) --> 1
+			return replace_with_pseudo(insn, value_pseudo(1));
+		} else if (value == 1) {	// (x >= 1) --> (x != 0)
+			insn->src2 = value_pseudo(0);
+			insn->opcode = OP_SET_NE;
+			return REPEAT_CSE;
+		}
+		break;
+	case OP_SET_BE:
+		if (!value) {			// (x <= 0) --> (x == 0)
+			insn->opcode = OP_SET_EQ;
+			return REPEAT_CSE;
+		}
+		break;
+	case OP_SET_A:
+		if (!value) {			// (x > 0) --> (x != 0)
+			insn->opcode = OP_SET_NE;
+			return REPEAT_CSE;
+		}
+		break;
+	}
+	return 0;
+}
+
 static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
 {
 	pseudo_t old = insn->src1;
@@ -1169,37 +1206,12 @@ static int simplify_constant_rightside(struct instruction *insn)
 
 	case OP_SET_NE:
 	case OP_SET_EQ:
-		return simplify_seteq_setne(insn, value);
-	case OP_SET_B:
-		if (!value) {			// (x < 0) --> 0
-			return replace_with_pseudo(insn, value_pseudo(0));
-		} else if (value == 1) {	// (x < 1) --> (x == 0)
-			insn->src2 = value_pseudo(0);
-			insn->opcode = OP_SET_EQ;
-			return REPEAT_CSE;
-		}
-		break;
-	case OP_SET_AE:
-		if (!value) {			// (x >= 0) --> 1
-			return replace_with_pseudo(insn, value_pseudo(1));
-		} else if (value == 1) {	// (x >= 1) --> (x != 0)
-			insn->src2 = value_pseudo(0);
-			insn->opcode = OP_SET_NE;
-			return REPEAT_CSE;
-		}
-		break;
-	case OP_SET_BE:
-		if (!value) {			// (x <= 0) --> (x == 0)
-			insn->opcode = OP_SET_EQ;
-			return REPEAT_CSE;
-		}
-		break;
-	case OP_SET_A:
-		if (!value) {			// (x > 0) --> (x != 0)
-			insn->opcode = OP_SET_NE;
-			return REPEAT_CSE;
-		}
-		break;
+		if ((changed = simplify_seteq_setne(insn, value)))
+			return changed;
+		/* fallthrough */
+	case OP_SET_LT: case OP_SET_LE: case OP_SET_GE: case OP_SET_GT:
+	case OP_SET_B:  case OP_SET_BE: case OP_SET_AE: case OP_SET_A:
+		return simplify_compare_constant(insn, value);
 	}
 	return 0;
 }
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 05/16] cmp: use a few helpers for the simplification of compares
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
                   ` (3 preceding siblings ...)
  2020-11-08  1:19 ` [PATCH 04/16] cmp: move some code in a separate function: simplify_compare_constant() Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 06/16] cmp: canonicalize unsigned (x {<,>=} C) --> (x {<=,>} C-1) Luc Van Oostenryck
                   ` (4 subsequent siblings)
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

The current code for the simplification of compares is quite
simple but also repetitive because everything must be done 4 times,
one for each operations (<,<=,>=,>).

So, add 2 helpers to factor out the details of the common parts.

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

diff --git a/simplify.c b/simplify.c
index 3338b72e6845..59e6d1eee291 100644
--- a/simplify.c
+++ b/simplify.c
@@ -470,6 +470,28 @@ static inline int replace_with_unop(struct instruction *insn, int op, pseudo_t s
 	return REPEAT_CSE;
 }
 
+///
+// replace rightside's value
+// @insn: the instruction to be replaced
+// @op: the instruction's new opcode
+// @src: the instruction's new operand
+// @return: REPEAT_CSE
+static inline int replace_binop_value(struct instruction *insn, int op, long long val)
+{
+	insn->opcode = op;
+	insn->src2 = value_pseudo(val);
+	return REPEAT_CSE;
+}
+
+///
+// replace the opcode of an instruction
+// @return: REPEAT_CSE
+static inline int replace_opcode(struct instruction *insn, int op)
+{
+	insn->opcode = op;
+	return REPEAT_CSE;
+}
+
 static inline int def_opcode(pseudo_t p)
 {
 	if (p->type != PSEUDO_REG)
@@ -1061,34 +1083,24 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 {
 	switch (insn->opcode) {
 	case OP_SET_B:
-		if (!value) {			// (x < 0) --> 0
+		if (!value)			// (x < 0) --> 0
 			return replace_with_pseudo(insn, value_pseudo(0));
-		} else if (value == 1) {	// (x < 1) --> (x == 0)
-			insn->src2 = value_pseudo(0);
-			insn->opcode = OP_SET_EQ;
-			return REPEAT_CSE;
-		}
+		if (value == 1)			// (x < 1) --> (x == 0)
+			return replace_binop_value(insn, OP_SET_EQ, 0);
 		break;
 	case OP_SET_AE:
-		if (!value) {			// (x >= 0) --> 1
+		if (!value)			// (x >= 0) --> 1
 			return replace_with_pseudo(insn, value_pseudo(1));
-		} else if (value == 1) {	// (x >= 1) --> (x != 0)
-			insn->src2 = value_pseudo(0);
-			insn->opcode = OP_SET_NE;
-			return REPEAT_CSE;
-		}
+		if (value == 1)			// (x >= 1) --> (x != 0)
+			return replace_binop_value(insn, OP_SET_NE, 0);
 		break;
 	case OP_SET_BE:
-		if (!value) {			// (x <= 0) --> (x == 0)
-			insn->opcode = OP_SET_EQ;
-			return REPEAT_CSE;
-		}
+		if (!value)			// (x <= 0) --> (x == 0)
+			return replace_opcode(insn, OP_SET_EQ);
 		break;
 	case OP_SET_A:
-		if (!value) {			// (x > 0) --> (x != 0)
-			insn->opcode = OP_SET_NE;
-			return REPEAT_CSE;
-		}
+		if (!value)			// (x > 0) --> (x != 0)
+			return replace_opcode(insn, OP_SET_NE);
 		break;
 	}
 	return 0;
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 06/16] cmp: canonicalize unsigned (x {<,>=} C) --> (x {<=,>} C-1)
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
                   ` (4 preceding siblings ...)
  2020-11-08  1:19 ` [PATCH 05/16] cmp: use a few helpers for the simplification of compares Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 07/16] cmp: simplify unsigned (x {<=,>} UMAX) into {1,0} Luc Van Oostenryck
                   ` (3 subsequent siblings)
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

An unsigned comparison like (x < 3) is equivalent to (x <= 2).
Canonicalize '<' & '>=' to '<=' & '>', such that the smallest
constant is used.

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

diff --git a/simplify.c b/simplify.c
index 59e6d1eee291..b8dfbad1f077 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1081,18 +1081,24 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 
 static int simplify_compare_constant(struct instruction *insn, long long value)
 {
+	int changed = 0;
+
 	switch (insn->opcode) {
 	case OP_SET_B:
 		if (!value)			// (x < 0) --> 0
 			return replace_with_pseudo(insn, value_pseudo(0));
 		if (value == 1)			// (x < 1) --> (x == 0)
 			return replace_binop_value(insn, OP_SET_EQ, 0);
+		else				// (x < y) --> (x <= (y-1))
+			changed |= replace_binop_value(insn, OP_SET_BE, value - 1);
 		break;
 	case OP_SET_AE:
 		if (!value)			// (x >= 0) --> 1
 			return replace_with_pseudo(insn, value_pseudo(1));
 		if (value == 1)			// (x >= 1) --> (x != 0)
 			return replace_binop_value(insn, OP_SET_NE, 0);
+		else				// (x >= y) --> (x > (y-1)
+			changed |= replace_binop_value(insn, OP_SET_A, value - 1);
 		break;
 	case OP_SET_BE:
 		if (!value)			// (x <= 0) --> (x == 0)
@@ -1103,7 +1109,7 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			return replace_opcode(insn, OP_SET_NE);
 		break;
 	}
-	return 0;
+	return changed;
 }
 
 static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
diff --git a/validation/optim/canonical-cmpu.c b/validation/optim/canonical-cmpu.c
index 482408aa90c1..29bbd0a8690a 100644
--- a/validation/optim/canonical-cmpu.c
+++ b/validation/optim/canonical-cmpu.c
@@ -9,7 +9,6 @@ int cmp_geu(unsigned int x) { return (x >= 256) == (x >  255); }
 /*
  * check-name: canonical-cmpu
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 07/16] cmp: simplify unsigned (x {<=,>} UMAX) into {1,0}
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
                   ` (5 preceding siblings ...)
  2020-11-08  1:19 ` [PATCH 06/16] cmp: canonicalize unsigned (x {<,>=} C) --> (x {<=,>} C-1) Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 08/16] cmp: canonicalize unsigned compare with UMAX or UMAX-1 Luc Van Oostenryck
                   ` (2 subsequent siblings)
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

These compares are always true or false, so simplify them.

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

diff --git a/simplify.c b/simplify.c
index b8dfbad1f077..160a6ab15e7f 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1081,6 +1081,7 @@ 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);
 	int changed = 0;
 
 	switch (insn->opcode) {
@@ -1103,10 +1104,14 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 	case OP_SET_BE:
 		if (!value)			// (x <= 0) --> (x == 0)
 			return replace_opcode(insn, OP_SET_EQ);
+		if (value == bits)		// (x <= ~0) --> 1
+			return replace_with_pseudo(insn, value_pseudo(1));
 		break;
 	case OP_SET_A:
 		if (!value)			// (x > 0) --> (x != 0)
 			return replace_opcode(insn, OP_SET_NE);
+		if (value == bits)		// (x > ~0) --> 0
+			return replace_with_pseudo(insn, value_pseudo(0));
 		break;
 	}
 	return changed;
diff --git a/validation/optim/set-uimm1.c b/validation/optim/set-uimm1.c
index d6928f59d044..aa9f54c3ff82 100644
--- a/validation/optim/set-uimm1.c
+++ b/validation/optim/set-uimm1.c
@@ -4,7 +4,6 @@ static _Bool setgt_umax(unsigned int a) { return (a >  ~0) == 0; }
 /*
  * check-name: set-uimm1
  * check-command: test-linearize $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 08/16] cmp: canonicalize unsigned compare with UMAX or UMAX-1
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
                   ` (6 preceding siblings ...)
  2020-11-08  1:19 ` [PATCH 07/16] cmp: simplify unsigned (x {<=,>} UMAX) into {1,0} Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:19 ` [PATCH 09/16] cmp: canonicalize unsigned (x {<=,>} SMAX) Luc Van Oostenryck
  2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

Unsigned compares with UMAX (or UMAX-1) are equivalent to
equality tests. These are preferable since it's easier to reason
about them in other simplifications.

So canonicalize these compares to equality tests.

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

diff --git a/simplify.c b/simplify.c
index 160a6ab15e7f..7921300f7280 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1090,6 +1090,8 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			return replace_with_pseudo(insn, value_pseudo(0));
 		if (value == 1)			// (x < 1) --> (x == 0)
 			return replace_binop_value(insn, OP_SET_EQ, 0);
+		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);
 		break;
@@ -1098,6 +1100,8 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			return replace_with_pseudo(insn, value_pseudo(1));
 		if (value == 1)			// (x >= 1) --> (x != 0)
 			return replace_binop_value(insn, OP_SET_NE, 0);
+		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);
 		break;
@@ -1106,12 +1110,16 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			return replace_opcode(insn, OP_SET_EQ);
 		if (value == bits)		// (x <= ~0) --> 1
 			return replace_with_pseudo(insn, value_pseudo(1));
+		if (value == (bits - 1))	// (x <= ~1) --> (x != ~0)
+			return replace_binop_value(insn, OP_SET_NE, bits);
 		break;
 	case OP_SET_A:
 		if (!value)			// (x > 0) --> (x != 0)
 			return replace_opcode(insn, OP_SET_NE);
 		if (value == bits)		// (x > ~0) --> 0
 			return replace_with_pseudo(insn, value_pseudo(0));
+		if (value == (bits - 1))	// (x > ~1) --> (x == ~0)
+			return replace_binop_value(insn, OP_SET_EQ, bits);
 		break;
 	}
 	return changed;
diff --git a/validation/optim/set-uimm2.c b/validation/optim/set-uimm2.c
index efa326f532ce..9138ae7276e7 100644
--- a/validation/optim/set-uimm2.c
+++ b/validation/optim/set-uimm2.c
@@ -6,7 +6,6 @@ static _Bool setgt_umax(unsigned int a) { return (a >  ~1) == (a == ~0); }
 /*
  * check-name: set-uimm2
  * check-command: test-linearize $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 09/16] cmp: canonicalize unsigned (x {<=,>} SMAX)
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
                   ` (7 preceding siblings ...)
  2020-11-08  1:19 ` [PATCH 08/16] cmp: canonicalize unsigned compare with UMAX or UMAX-1 Luc Van Oostenryck
@ 2020-11-08  1:19 ` Luc Van Oostenryck
  2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
  9 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:19 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

Unsigned <= or > against SMAX are equivalent to testing if the
value is positive or not (when interpreted as a signed number).

Canonicalize to this positive/negative test since it only needs
the constant 0 which make it easier to handle at later steps.

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

diff --git a/simplify.c b/simplify.c
index 7921300f7280..2176f90dc133 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1112,6 +1112,8 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			return replace_with_pseudo(insn, value_pseudo(1));
 		if (value == (bits - 1))	// (x <= ~1) --> (x != ~0)
 			return replace_binop_value(insn, OP_SET_NE, bits);
+		if (value == (bits >> 1))	// (x u<= SMAX) --> (x s>= 0)
+			changed |= replace_binop_value(insn, OP_SET_GE, 0);
 		break;
 	case OP_SET_A:
 		if (!value)			// (x > 0) --> (x != 0)
@@ -1120,6 +1122,8 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			return replace_with_pseudo(insn, value_pseudo(0));
 		if (value == (bits - 1))	// (x > ~1) --> (x == ~0)
 			return replace_binop_value(insn, OP_SET_EQ, bits);
+		if (value == (bits >> 1))	// (x u> SMAX) --> (x s< 0)
+			changed |= replace_binop_value(insn, OP_SET_LT, 0);
 		break;
 	}
 	return changed;
diff --git a/validation/optim/set-uimm3.c b/validation/optim/set-uimm3.c
index b72ef8d6e819..5160f741d85b 100644
--- a/validation/optim/set-uimm3.c
+++ b/validation/optim/set-uimm3.c
@@ -4,7 +4,6 @@ int gt(int x) { return (x >  0x7fffffffU) == (x <  0); }
 /*
  * check-name: set-uimm3
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C
  2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
                   ` (8 preceding siblings ...)
  2020-11-08  1:19 ` [PATCH 09/16] cmp: canonicalize unsigned (x {<=,>} SMAX) Luc Van Oostenryck
@ 2020-11-08  1:21 ` Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 11/16] cmp: simplify zext(x) " Luc Van Oostenryck
                     ` (5 more replies)
  9 siblings, 6 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:21 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

When doing a compare of a sign-extended value against a constant
the, sign-extension can be dropped and the comparison done on the
original type if the constant is within the original range.

Simplify away these sign-extensions.

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

diff --git a/simplify.c b/simplify.c
index 2176f90dc133..eb2c724f6307 100644
--- a/simplify.c
+++ b/simplify.c
@@ -415,6 +415,13 @@ static inline int constant(pseudo_t pseudo)
 	return pseudo->type == PSEUDO_VAL;
 }
 
+///
+// is this same signed value when interpreted with both size?
+static inline bool is_signed_constant(long long val, unsigned osize, unsigned nsize)
+{
+	return bits_extend(val, osize, 1) == bits_extend(val, nsize, 1);
+}
+
 ///
 // replace the operand of an instruction
 // @insn: the instruction
@@ -1082,6 +1089,9 @@ 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);
+	struct instruction *def;
+	pseudo_t src1, src2;
+	unsigned int osize;
 	int changed = 0;
 
 	switch (insn->opcode) {
@@ -1126,6 +1136,20 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			changed |= replace_binop_value(insn, OP_SET_LT, 0);
 		break;
 	}
+
+	src1 = insn->src1;
+	src2 = insn->src2;
+	value = src2->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)) {
+			insn->itype = def->orig_type;
+			insn->src2 = value_pseudo(zero_extend(value, osize));
+			return replace_pseudo(insn, &insn->src1, def->src);
+		}
+		break;
+	}
 	return changed;
 }
 
diff --git a/validation/optim/cmp-sext.c b/validation/optim/cmp-sext.c
index 2dd60fff064c..13f4fbdfad77 100644
--- a/validation/optim/cmp-sext.c
+++ b/validation/optim/cmp-sext.c
@@ -17,7 +17,6 @@ _Bool cmpgtu_sext(int a) { return (a >= 0x80000000ULL) == (a <  0); }
 /*
  * check-name: cmp-sext
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 11/16] cmp: simplify zext(x) cmp C --> x cmp C
  2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
@ 2020-11-08  1:21   ` Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 12/16] cmp: simplify sext(x) cmps {SMAX,SMIN} Luc Van Oostenryck
                     ` (4 subsequent siblings)
  5 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:21 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

When doing a compare of a zero-extended value against a constant,
this extension can be dropped and the comparison done on the
original type if the constant is within the original range and
signed compares become the corresponding unsigned one.

Simplify away these sign-extensions.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                        | 11 +++++++++++
 validation/optim/cmp-zext-uimm1.c |  1 -
 validation/optim/cmp-zext.c       |  1 -
 validation/optim/zext-cmpu.c      |  1 -
 4 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/simplify.c b/simplify.c
index eb2c724f6307..1cb5275b7a73 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1149,6 +1149,17 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			return replace_pseudo(insn, &insn->src1, def->src);
 		}
 		break;
+	case OP_ZEXT:
+		osize = def->orig_type->bit_size;
+		bits = bits_mask(osize);
+		if (value <= bits) {
+			const struct opcode_table *op = &opcode_table[insn->opcode];
+			if (op->flags & OPF_SIGNED)
+				insn->opcode = op->sign;
+			insn->itype = def->orig_type;
+			return replace_pseudo(insn, &insn->src1, def->src);
+		}
+		break;
 	}
 	return changed;
 }
diff --git a/validation/optim/cmp-zext-uimm1.c b/validation/optim/cmp-zext-uimm1.c
index ffcdaad5c1bd..c21780ea728d 100644
--- a/validation/optim/cmp-zext-uimm1.c
+++ b/validation/optim/cmp-zext-uimm1.c
@@ -9,7 +9,6 @@ int zext_gt_p(unsigned int x) { return (zext(x) >  (BITS    )) == 0; }
 /*
  * check-name: cmp-zext-uimm1
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
diff --git a/validation/optim/cmp-zext.c b/validation/optim/cmp-zext.c
index ecee6b5e9101..ac4847806251 100644
--- a/validation/optim/cmp-zext.c
+++ b/validation/optim/cmp-zext.c
@@ -11,7 +11,6 @@ _Bool cmpu_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, < , 0xffffffff);
 /*
  * check-name: cmp-zext
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
diff --git a/validation/optim/zext-cmpu.c b/validation/optim/zext-cmpu.c
index 279ed70e0fda..9758e0710d7b 100644
--- a/validation/optim/zext-cmpu.c
+++ b/validation/optim/zext-cmpu.c
@@ -10,7 +10,6 @@ int gtl(unsigned x) { return (((long long)x) >  0x0fffffffeULL) == (x >  0xfffff
 /*
  * check-name: zext-cmpu
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 12/16] cmp: simplify sext(x) cmps {SMAX,SMIN}
  2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 11/16] cmp: simplify zext(x) " Luc Van Oostenryck
@ 2020-11-08  1:21   ` Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 13/16] cmp: canonicalize sext(x) cmpu C (with C >= SMAX) Luc Van Oostenryck
                     ` (3 subsequent siblings)
  5 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:21 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

A signed compare of a sign-extended value against a constant
outside of the original range is statically known.

Simplify to the corresponding 0/1.

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

diff --git a/simplify.c b/simplify.c
index 1cb5275b7a73..a59918697762 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1148,6 +1148,20 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			insn->src2 = value_pseudo(zero_extend(value, osize));
 			return replace_pseudo(insn, &insn->src1, def->src);
 		}
+		switch (insn->opcode) {
+		case OP_SET_LT: case OP_SET_LE:
+			if (value >= sign_bit(osize))
+				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))
+				return replace_with_value(insn, 0);
+			else
+				return replace_with_value(insn, 1);
+			break;
+		}
 		break;
 	case OP_ZEXT:
 		osize = def->orig_type->bit_size;
diff --git a/validation/optim/cmp-sext-simm.c b/validation/optim/cmp-sext-simm.c
index c2099a6b8876..a8b2a8f9feff 100644
--- a/validation/optim/cmp-sext-simm.c
+++ b/validation/optim/cmp-sext-simm.c
@@ -23,7 +23,6 @@ static int ge_lt1(int x) { return (sext(x) >= (NEG - 1)) == 0; }
 /*
  * check-name: cmp-sext-simm
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 13/16] cmp: canonicalize sext(x) cmpu C (with C >= SMAX)
  2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 11/16] cmp: simplify zext(x) " Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 12/16] cmp: simplify sext(x) cmps {SMAX,SMIN} Luc Van Oostenryck
@ 2020-11-08  1:21   ` Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 14/16] cmp: simplify zext(x) cmps C Luc Van Oostenryck
                     ` (2 subsequent siblings)
  5 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:21 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

A unsigned compare of a sign-extended value against a value
bigger than the original SMAX is equivalent to a signed
compare against 0.

Canonicalize to the signed compare against 0.

Note: ultimately both forms are just a test of the sign bit.

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

diff --git a/simplify.c b/simplify.c
index a59918697762..8a8b39b81e20 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1149,6 +1149,18 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			return replace_pseudo(insn, &insn->src1, def->src);
 		}
 		switch (insn->opcode) {
+		case OP_SET_BE:
+			if (value >= sign_bit(osize)) {
+				replace_binop_value(insn, OP_SET_GE, 0);
+				return replace_pseudo(insn, &insn->src1, def->src);
+			}
+			break;
+		case OP_SET_A:
+			if (value >= sign_bit(osize)) {
+				replace_binop_value(insn, OP_SET_LT, 0);
+				return replace_pseudo(insn, &insn->src1, def->src);
+			}
+			break;
 		case OP_SET_LT: case OP_SET_LE:
 			if (value >= sign_bit(osize))
 				return replace_with_value(insn, 1);
diff --git a/validation/optim/cmp-sext-uimm.c b/validation/optim/cmp-sext-uimm.c
index cc89a80694a1..05da042f5030 100644
--- a/validation/optim/cmp-sext-uimm.c
+++ b/validation/optim/cmp-sext-uimm.c
@@ -19,7 +19,6 @@ int sext_gtu_m3(int x) { return (sext(x) > (NEG - 3)) == (x < 0); }
 /*
  * check-name: cmp-sext-uimm
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 14/16] cmp: simplify zext(x) cmps C
  2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
                     ` (2 preceding siblings ...)
  2020-11-08  1:21   ` [PATCH 13/16] cmp: canonicalize sext(x) cmpu C (with C >= SMAX) Luc Van Oostenryck
@ 2020-11-08  1:21   ` Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 15/16] cmp: simplify zext(x) cmpu C Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 16/16] cmp: simplify compares and sign/zero extend Luc Van Oostenryck
  5 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:21 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

A signed compare of a zero-extended value against a constant
outside of the original range is statically known.

Simplify to the corresponding 0/1.

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

diff --git a/simplify.c b/simplify.c
index 8a8b39b81e20..83ae763eac72 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1185,6 +1185,20 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			insn->itype = def->orig_type;
 			return replace_pseudo(insn, &insn->src1, def->src);
 		}
+		switch (insn->opcode) {
+		case OP_SET_LT: case OP_SET_LE:
+			if (sign_extend(value, def->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)
+				return replace_with_value(insn, 0);
+			else
+				return replace_with_value(insn, 1);
+			break;
+		}
 		break;
 	}
 	return changed;
diff --git a/validation/optim/cmp-zext-simm.c b/validation/optim/cmp-zext-simm.c
index f89f8f8baa62..dda237d7257f 100644
--- a/validation/optim/cmp-zext-simm.c
+++ b/validation/optim/cmp-zext-simm.c
@@ -17,7 +17,6 @@ int zext_lgt(unsigned int x) { return (ZEXT(x) >  -1) == 1; }
 /*
  * check-name: cmp-zext-simm
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 15/16] cmp: simplify zext(x) cmpu C
  2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
                     ` (3 preceding siblings ...)
  2020-11-08  1:21   ` [PATCH 14/16] cmp: simplify zext(x) cmps C Luc Van Oostenryck
@ 2020-11-08  1:21   ` Luc Van Oostenryck
  2020-11-08  1:21   ` [PATCH 16/16] cmp: simplify compares and sign/zero extend Luc Van Oostenryck
  5 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:21 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

An unsigned compare of a zero-extended value against a
constant outside of the original range is statically known.

Simplify to the corresponding 0/1.

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

diff --git a/simplify.c b/simplify.c
index 83ae763eac72..7538c9393b41 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1198,6 +1198,10 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
 			else
 				return replace_with_value(insn, 1);
 			break;
+		case OP_SET_B: case OP_SET_BE:
+			return replace_with_value(insn, 1);
+		case OP_SET_AE: case OP_SET_A:
+			return replace_with_value(insn, 0);
 		}
 		break;
 	}
diff --git a/validation/optim/cmp-zext-uimm2.c b/validation/optim/cmp-zext-uimm2.c
index 64f30b9a3df5..214bd96fb4ce 100644
--- a/validation/optim/cmp-zext-uimm2.c
+++ b/validation/optim/cmp-zext-uimm2.c
@@ -23,7 +23,6 @@ int zext_gtu_m(unsigned x) { return (zext(x) >  0x0fffffffeUL) == (x >  0xffffff
 /*
  * check-name: cmp-zext-uimm2
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
* [PATCH 16/16] cmp: simplify compares and sign/zero extend
  2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
                     ` (4 preceding siblings ...)
  2020-11-08  1:21   ` [PATCH 15/16] cmp: simplify zext(x) cmpu C Luc Van Oostenryck
@ 2020-11-08  1:21   ` Luc Van Oostenryck
  5 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2020-11-08  1:21 UTC (permalink / raw)
  To: linux-sparse; +Cc: Luc Van Oostenryck

Compare instructions with both operands sign or zero-extended
from the same original size are equivalent to a compare of
the original values. If the values were zero-extended, a signed
compare becomes an unsigned one.

Simplify away the sign/zero-extensions.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                       | 52 ++++++++++++++++++++++++++------
 validation/optim/cmp-sext-sext.c |  1 -
 validation/optim/cmp-zext-zext.c |  1 -
 3 files changed, 42 insertions(+), 12 deletions(-)

diff --git a/simplify.c b/simplify.c
index 7538c9393b41..d56d4c89a078 100644
--- a/simplify.c
+++ b/simplify.c
@@ -422,6 +422,22 @@ static inline bool is_signed_constant(long long val, unsigned osize, unsigned ns
 	return bits_extend(val, osize, 1) == bits_extend(val, nsize, 1);
 }
 
+///
+// is @src generated by an instruction with the given opcode and size?
+static inline pseudo_t is_same_op(pseudo_t src, int op, unsigned osize)
+{
+	struct instruction *def;
+
+	if (src->type != PSEUDO_REG)
+		return NULL;
+	def = src->def;
+	if (def->opcode != op)
+		return NULL;
+	if (def->orig_type->bit_size != osize)
+		return NULL;
+	return def->src;
+}
+
 ///
 // replace the operand of an instruction
 // @insn: the instruction
@@ -1570,6 +1586,30 @@ static int simplify_sub(struct instruction *insn)
 	return 0;
 }
 
+static int simplify_compare(struct instruction *insn)
+{
+	pseudo_t src1 = insn->src1;
+	pseudo_t src2 = insn->src2;
+	struct instruction *def;
+	unsigned int osize;
+	pseudo_t src;
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_SEXT: case OP_ZEXT:
+		osize = def->orig_type->bit_size;
+		if ((src = is_same_op(src2, def->opcode, osize))) {
+			const struct opcode_table *op = &opcode_table[insn->opcode];
+			if ((def->opcode == OP_ZEXT) && (op->flags & OPF_SIGNED))
+				insn->opcode = op->sign;
+			insn->itype = def->orig_type;
+			replace_pseudo(insn, &insn->src1, def->src);
+			return replace_pseudo(insn, &insn->src2, src);
+		}
+		break;
+	}
+	return 0;
+}
+
 static int simplify_constant_unop(struct instruction *insn)
 {
 	long long val = insn->src1->value;
@@ -2083,17 +2123,9 @@ int simplify_instruction(struct instruction *insn)
 	case OP_DIVS:
 	case OP_MODU:
 	case OP_MODS:
-	case OP_SET_EQ:
-	case OP_SET_NE:
-	case OP_SET_LE:
-	case OP_SET_GE:
-	case OP_SET_LT:
-	case OP_SET_GT:
-	case OP_SET_B:
-	case OP_SET_A:
-	case OP_SET_BE:
-	case OP_SET_AE:
 		break;
+	case OP_BINCMP ... OP_BINCMP_END:
+		return simplify_compare(insn);
 	case OP_LOAD:
 	case OP_STORE:
 		return simplify_memop(insn);
diff --git a/validation/optim/cmp-sext-sext.c b/validation/optim/cmp-sext-sext.c
index ba6ed54e940c..3bd22fb738ca 100644
--- a/validation/optim/cmp-sext-sext.c
+++ b/validation/optim/cmp-sext-sext.c
@@ -11,7 +11,6 @@ _Bool cmpu_sext_sext(ARGS(INT32)) { return TEST(UINT64, UINT32, a, < , b); }
 /*
  * check-name: cmp-sext-sext
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
diff --git a/validation/optim/cmp-zext-zext.c b/validation/optim/cmp-zext-zext.c
index 9f188297e214..88f9078f9480 100644
--- a/validation/optim/cmp-zext-zext.c
+++ b/validation/optim/cmp-zext-zext.c
@@ -11,7 +11,6 @@ _Bool cmpu_zext_zext(ARGS(UINT32)) { return TEST(UINT64, UINT32, a, < , b); }
 /*
  * check-name: cmp-zext-zext
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2


^ permalink raw reply related	[flat|nested] 17+ messages in thread
end of thread, other threads:[~2020-11-08  1:21 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-11-08  1:19 [PATCH 00/16] simplify & canonicalize compares Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 01/16] cmp: adapt testcase for compares' canonicalization Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 02/16] cmp: add testcases for the simplification of compares Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 03/16] cmp: add signed/unsigned to opcode table Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 04/16] cmp: move some code in a separate function: simplify_compare_constant() Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 05/16] cmp: use a few helpers for the simplification of compares Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 06/16] cmp: canonicalize unsigned (x {<,>=} C) --> (x {<=,>} C-1) Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 07/16] cmp: simplify unsigned (x {<=,>} UMAX) into {1,0} Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 08/16] cmp: canonicalize unsigned compare with UMAX or UMAX-1 Luc Van Oostenryck
2020-11-08  1:19 ` [PATCH 09/16] cmp: canonicalize unsigned (x {<=,>} SMAX) Luc Van Oostenryck
2020-11-08  1:21 ` [PATCH 10/16] cmp: simplify sext(x) cmp C --> x cmp C Luc Van Oostenryck
2020-11-08  1:21   ` [PATCH 11/16] cmp: simplify zext(x) " Luc Van Oostenryck
2020-11-08  1:21   ` [PATCH 12/16] cmp: simplify sext(x) cmps {SMAX,SMIN} Luc Van Oostenryck
2020-11-08  1:21   ` [PATCH 13/16] cmp: canonicalize sext(x) cmpu C (with C >= SMAX) Luc Van Oostenryck
2020-11-08  1:21   ` [PATCH 14/16] cmp: simplify zext(x) cmps C Luc Van Oostenryck
2020-11-08  1:21   ` [PATCH 15/16] cmp: simplify zext(x) cmpu C Luc Van Oostenryck
2020-11-08  1:21   ` [PATCH 16/16] cmp: simplify compares and sign/zero extend Luc Van Oostenryck

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.