* [PATCH 1/2] CSE: split optim/cse-dual-compare.c in two files
2017-04-12 12:59 [PATCH 0/2] extend canonical order Luc Van Oostenryck
@ 2017-04-12 12:59 ` Luc Van Oostenryck
2017-04-12 12:59 ` [PATCH 2/2] CSE: extend canonical_order() Luc Van Oostenryck
2017-04-12 13:08 ` [PATCH 0/2] extend canonical order Luc Van Oostenryck
2 siblings, 0 replies; 4+ messages in thread
From: Luc Van Oostenryck @ 2017-04-12 12:59 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, 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
^ permalink raw reply related [flat|nested] 4+ messages in thread* [PATCH 2/2] CSE: extend canonical_order()
2017-04-12 12:59 [PATCH 0/2] extend canonical order Luc Van Oostenryck
2017-04-12 12:59 ` [PATCH 1/2] CSE: split optim/cse-dual-compare.c in two files Luc Van Oostenryck
@ 2017-04-12 12:59 ` Luc Van Oostenryck
2017-04-12 13:08 ` [PATCH 0/2] extend canonical order Luc Van Oostenryck
2 siblings, 0 replies; 4+ messages in thread
From: Luc Van Oostenryck @ 2017-04-12 12:59 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, 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
^ permalink raw reply related [flat|nested] 4+ messages in thread* Re: [PATCH 0/2] extend canonical order
2017-04-12 12:59 [PATCH 0/2] extend canonical order Luc Van Oostenryck
2017-04-12 12:59 ` [PATCH 1/2] CSE: split optim/cse-dual-compare.c in two files Luc Van Oostenryck
2017-04-12 12:59 ` [PATCH 2/2] CSE: extend canonical_order() Luc Van Oostenryck
@ 2017-04-12 13:08 ` Luc Van Oostenryck
2 siblings, 0 replies; 4+ messages in thread
From: Luc Van Oostenryck @ 2017-04-12 13:08 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li
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
^ permalink raw reply [flat|nested] 4+ messages in thread