[PATCH 0/2] extend canonical order

[PATCH 0/2] extend canonical order

[Luc Van Oostenryck]

After linearization, operands of binops of binops are
maintained in a 'canonical' order but this order is only:
	anything > symbols > integer literals
but there is some value to impose a more complete order
as this creates more opportunities for CSE and help to
limit the number of patterns that need to be checked
at simplification of even during code generation.

This is what is done by this (almost single patch) series.

This series is available at:
	git://github.com/lucvoo/sparse.git base-file
based on commit:
	c9585071d02590f40175ea90c395d15ef70e9a1e (cset-setfval)
up to commit:
	462a61a21b1e3bb17abce88fb1bdbc93d9653245


Luc Van Oostenryck (2):
  CSE: split optim/cse-dual-compare.c in two files
  CSE: extend canonical_order()

 linearize.h                                        |  4 +--
 simplify.c                                         | 29 +++++++++++-----
 validation/call-inlined.c                          |  2 +-
 .../optim/{cse-dual-compare.c => cse-dual-cmpeq.c} | 11 +-----
 validation/optim/cse-dual-cmpne.c                  | 40 ++++++++++++++++++++++
 5 files changed, 65 insertions(+), 21 deletions(-)
 rename validation/optim/{cse-dual-compare.c => cse-dual-cmpeq.c} (68%)
 create mode 100644 validation/optim/cse-dual-cmpne.c

-- 
2.12.0

[PATCH 1/2] CSE: split optim/cse-dual-compare.c in two files

[Luc Van Oostenryck]

This is a preparatory step for the nex patch
(half of the tests will succeed).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 .../optim/{cse-dual-compare.c => cse-dual-cmpeq.c} | 10 +-----
 validation/optim/cse-dual-cmpne.c                  | 40 ++++++++++++++++++++++
 2 files changed, 41 insertions(+), 9 deletions(-)
 rename validation/optim/{cse-dual-compare.c => cse-dual-cmpeq.c} (69%)
 create mode 100644 validation/optim/cse-dual-cmpne.c

diff --git a/validation/optim/cse-dual-compare.c b/validation/optim/cse-dual-cmpeq.c
similarity index 69%
rename from validation/optim/cse-dual-compare.c
rename to validation/optim/cse-dual-cmpeq.c
index b43cf7899..45ceee12d 100644
--- a/validation/optim/cse-dual-compare.c
+++ b/validation/optim/cse-dual-cmpeq.c
@@ -14,16 +14,8 @@ static int enlelt(int a, int b) { return (a <= b) == !(b <  a); }
 static int engegt(int a, int b) { return (a >= b) == !(b >  a); }
 static int engtge(int a, int b) { return (a >  b) == !(b >= a); }
 
-static int neeqne(int a, int b) { return (a == b) != (b != a); }
-static int neneeq(int a, int b) { return (a != b) != (b == a); }
-
-static int neltle(int a, int b) { return (a <  b) != (b <= a); }
-static int nelelt(int a, int b) { return (a <= b) != (b <  a); }
-static int negegt(int a, int b) { return (a >= b) != (b >  a); }
-static int negtge(int a, int b) { return (a >  b) != (b >= a); }
-
 /*
- * check-name: cse-dual-compare
+ * check-name: cse-dual-cmpeq
  * check-command: test-linearize $file
  * check-output-ignore
  * check-known-to-fail
diff --git a/validation/optim/cse-dual-cmpne.c b/validation/optim/cse-dual-cmpne.c
new file mode 100644
index 000000000..489150c32
--- /dev/null
+++ b/validation/optim/cse-dual-cmpne.c
@@ -0,0 +1,40 @@
+int eqeqnea(int a, int b) { return (a == b) == (a != b); }
+int eqneeqa(int a, int b) { return (a != b) == (a == b); }
+int eqeqneb(int a, int b) { return (a == b) == (b != a); }
+int eqneeqb(int a, int b) { return (a != b) == (b == a); }
+
+int eqltlea(int a, int b) { return (a <  b) == (a >= b); }
+int eqlelta(int a, int b) { return (a <= b) == (a >  b); }
+int eqgegta(int a, int b) { return (a >= b) == (a <  b); }
+int eqgtgea(int a, int b) { return (a >  b) == (a <= b); }
+
+int eqltleb(int a, int b) { return (a <  b) == (b <= a); }
+int eqleltb(int a, int b) { return (a <= b) == (b <  a); }
+int eqgegtb(int a, int b) { return (a >= b) == (b >  a); }
+int eqgtgeb(int a, int b) { return (a >  b) == (b >= a); }
+
+int neeqnea(int a, int b) { return (a == b) != (a != b); }
+int neneeqa(int a, int b) { return (a != b) != (a == b); }
+int neeqneb(int a, int b) { return (a == b) != (b != a); }
+int neneeqb(int a, int b) { return (a != b) != (b == a); }
+
+int neltlea(int a, int b) { return (a <  b) != (a >= b); }
+int nelelta(int a, int b) { return (a <= b) != (a >  b); }
+int negegta(int a, int b) { return (a >= b) != (a <  b); }
+int negtgea(int a, int b) { return (a >  b) != (a <= b); }
+
+int neltleb(int a, int b) { return (a <  b) != (b <= a); }
+int neleltb(int a, int b) { return (a <= b) != (b <  a); }
+int negegtb(int a, int b) { return (a >= b) != (b >  a); }
+int negtgeb(int a, int b) { return (a >  b) != (b >= a); }
+
+/*
+ * check-name: cse-dual-cmpne
+ * check-command: test-linearize $file
+ * check-output-ignore
+ * check-known-to-fail
+ *
+ * check-output-excludes: set[gl][et]\\.
+ * check-output-excludes: seteq\\.
+ * check-output-excludes: setne\\.
+ */
-- 
2.12.0

[PATCH 2/2] CSE: extend canonical_order()

[Luc Van Oostenryck]

Impose an almost-total order between pseudos.
This creates more oppportunities for CSE and
make simplification slightly easier too.

Now the canonical order is:
	REG > PHI > ARG > SYM > VAL > VOID
and REGS, PHIs and ARGs are ordered following their
'->nr' field.
This order continues to put values at RHS and previous
results at LHS while still being quite cheap to check.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h                       |  4 ++--
 simplify.c                        | 29 +++++++++++++++++++++--------
 validation/call-inlined.c         |  2 +-
 validation/optim/cse-dual-cmpeq.c |  1 -
 4 files changed, 24 insertions(+), 12 deletions(-)

diff --git a/linearize.h b/linearize.h
index 6f4298f33..24cbcf94d 100644
--- a/linearize.h
+++ b/linearize.h
@@ -22,11 +22,11 @@ DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
 
 enum pseudo_type {
 	PSEUDO_VOID,
-	PSEUDO_REG,
-	PSEUDO_SYM,
 	PSEUDO_VAL,
+	PSEUDO_SYM,
 	PSEUDO_ARG,
 	PSEUDO_PHI,
+	PSEUDO_REG,
 };
 
 struct pseudo {
diff --git a/simplify.c b/simplify.c
index 5e3d57470..6d4ba4d69 100644
--- a/simplify.c
+++ b/simplify.c
@@ -709,16 +709,29 @@ static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instr
 	remove_usage(p2, pp2);
 }
 
+/*
+ * Test if the operands are in canonical order:
+ *	REG > PHI > ARG > SYM > VAL > VOID
+ *	%arg2 > %arg1, %r2 > %r1, %phi2 > %phi1
+ */
 static int canonical_order(pseudo_t p1, pseudo_t p2)
 {
-	/* symbol/constants on the right */
-	if (p1->type == PSEUDO_VAL)
-		return p2->type == PSEUDO_VAL;
-
-	if (p1->type == PSEUDO_SYM)
-		return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
-
-	return 1;
+	int t1 = p1->type;
+	int t2 = p2->type;
+
+	switch (t1) {
+	case PSEUDO_REG:
+	case PSEUDO_PHI:
+	case PSEUDO_ARG:
+		if (t1 == t2)
+			return p1->nr >= p2->nr;
+		/* fall-through */
+	case PSEUDO_SYM:
+	case PSEUDO_VAL:
+	case PSEUDO_VOID:
+	default:
+		return t1 >= t2;
+	}
 }
 
 static int canonicalize_commutative(struct instruction *insn)
diff --git a/validation/call-inlined.c b/validation/call-inlined.c
index b907ded60..80059f489 100644
--- a/validation/call-inlined.c
+++ b/validation/call-inlined.c
@@ -25,7 +25,7 @@ const char *qus(void) { return lstrip(messg); }
 foo:
 .L0:
 	<entry-point>
-	add.32      %r3 <- %arg1, %arg2
+	add.32      %r3 <- %arg2, %arg1
 	add.32      %r5 <- %r3, $1
 	ret.32      %r5
 
diff --git a/validation/optim/cse-dual-cmpeq.c b/validation/optim/cse-dual-cmpeq.c
index 45ceee12d..aade6e989 100644
--- a/validation/optim/cse-dual-cmpeq.c
+++ b/validation/optim/cse-dual-cmpeq.c
@@ -18,7 +18,6 @@ static int engtge(int a, int b) { return (a >  b) == !(b >= a); }
  * check-name: cse-dual-cmpeq
  * check-command: test-linearize $file
  * check-output-ignore
- * check-known-to-fail
  *
  * check-output-excludes: set[gl][et]\\.
  * check-output-excludes: seteq\\.
-- 
2.12.0

Re: [PATCH 0/2] extend canonical order

[Luc Van Oostenryck]

On Wed, Apr 12, 2017 at 02:59:10PM +0200, Luc Van Oostenryck wrote:
> After linearization, operands of binops of binops are
> maintained in a 'canonical' order but this order is only:
> 	anything > symbols > integer literals
> but there is some value to impose a more complete order
> as this creates more opportunities for CSE and help to
> limit the number of patterns that need to be checked
> at simplification of even during code generation.
> 
> This is what is done by this (almost single patch) series.
> 
> This series is available at:
> 	git://github.com/lucvoo/sparse.git base-file
> based on commit:
> 	c9585071d02590f40175ea90c395d15ef70e9a1e (cset-setfval)
> up to commit:
> 	462a61a21b1e3bb17abce88fb1bdbc93d9653245

Sorry, I forgot the completely edit my template.
This need to be read as:
	git://github.com/lucvoo/sparse.git cse-canonical

The SHA1 references are OK, though.

-- Luc