[PATCH 0/4] CSE improvements

[PATCH 0/4] CSE improvements

[Luc Van Oostenryck]

This serie aims at improving CSE by
- recognize commutative instructions as equivalent
- avoid to hash instructions that are already eliminated
- slight optimization of hash of non-commutative instructions

Luc Van Oostenryck (4):
  CSE: add test cases for comparisons duality
  CSE: use commutativity to identify equivalent instructions
  CSE: avoid hashing removed instructions
  CSE: improve hashing of non-commutative binops

 cse.c                                | 50 +++++++++++++++++++++---------------
 validation/optim/cse-commutativity.c | 22 ++++++++++++++++
 validation/optim/cse-dual-compare.c  | 34 ++++++++++++++++++++++++
 3 files changed, 86 insertions(+), 20 deletions(-)
 create mode 100644 validation/optim/cse-commutativity.c
 create mode 100644 validation/optim/cse-dual-compare.c

-- 
2.11.0

[PATCH 1/4] CSE: add test cases for comparisons duality

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/cse-dual-compare.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
 create mode 100644 validation/optim/cse-dual-compare.c

diff --git a/validation/optim/cse-dual-compare.c b/validation/optim/cse-dual-compare.c
new file mode 100644
index 000000000..b43cf7899
--- /dev/null
+++ b/validation/optim/cse-dual-compare.c
@@ -0,0 +1,34 @@
+static int eqeq(int a, int b) { return (a == b) == (b == a); }
+static int nene(int a, int b) { return (a != b) == (b != a); }
+
+static int ltgt(int a, int b) { return (a <  b) == (b >  a); }
+static int lege(int a, int b) { return (a <= b) == (b >= a); }
+static int gele(int a, int b) { return (a >= b) == (b <= a); }
+static int gtlt(int a, int b) { return (a >  b) == (b <  a); }
+
+static int eneqne(int a, int b) { return (a == b) == !(b != a); }
+static int enneeq(int a, int b) { return (a != b) == !(b == a); }
+
+static int enltle(int a, int b) { return (a <  b) == !(b <= a); }
+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-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.11.0

[PATCH 2/4] CSE: use commutativity to identify equivalent instructions

[Luc Van Oostenryck]

By definition a commutative operation give the same result if its
operands are exchanged.
CSE can use this property when comparing instructions to find
more equivalent instructions and thus eliminate more of them..

Implement this by special-casing commutative ops in insn_compare().

Note: this come for free when all instructions are properly
canonicalized, which is not yet the case.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c                                | 22 ++++++++++++++--------
 validation/optim/cse-commutativity.c | 22 ++++++++++++++++++++++
 2 files changed, 36 insertions(+), 8 deletions(-)
 create mode 100644 validation/optim/cse-commutativity.c

diff --git a/cse.c b/cse.c
index 048a3eb79..5380f4ccd 100644
--- a/cse.c
+++ b/cse.c
@@ -174,30 +174,36 @@ static int insn_compare(const void *_i1, const void *_i2)
 		return i1->opcode < i2->opcode ? -1 : 1;
 
 	switch (i1->opcode) {
+
+	/* commutative binop */
+	case OP_ADD:
+	case OP_MULU: case OP_MULS:
+	case OP_AND_BOOL: case OP_OR_BOOL:
+	case OP_AND: case OP_OR:
+	case OP_XOR:
+	case OP_SET_EQ: case OP_SET_NE:
+		if (i1->src1 == i2->src2 && i1->src2 == i2->src1)
+			return 0;
+		goto case_binops;
+
 	case OP_SEL:
 		if (i1->src3 != i2->src3)
 			return i1->src3 < i2->src3 ? -1 : 1;
 		/* Fall-through to binops */
 
 	/* Binary arithmetic */
-	case OP_ADD: case OP_SUB:
-	case OP_MULU: case OP_MULS:
+	case OP_SUB:
 	case OP_DIVU: case OP_DIVS:
 	case OP_MODU: case OP_MODS:
 	case OP_SHL:
 	case OP_LSR: case OP_ASR:
-	case OP_AND: case OP_OR:
-
-	/* Binary logical */
-	case OP_XOR: case OP_AND_BOOL:
-	case OP_OR_BOOL:
 
 	/* Binary comparison */
-	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:
+	case_binops:
 		if (i1->src2 != i2->src2)
 			return i1->src2 < i2->src2 ? -1 : 1;
 		/* Fall through to unops */
diff --git a/validation/optim/cse-commutativity.c b/validation/optim/cse-commutativity.c
new file mode 100644
index 000000000..826034781
--- /dev/null
+++ b/validation/optim/cse-commutativity.c
@@ -0,0 +1,22 @@
+static int add(int a, int b) { return (a + b) == (b + a); }
+static int mul(int a, int b) { return (a * b) == (b * a); }
+static int and(int a, int b) { return (a & b) == (b & a); }
+static int ior(int a, int b) { return (a | b) == (b | a); }
+static int xor(int a, int b) { return (a ^ b) == (b ^ a); }
+static int  eq(int a, int b) { return (a == b) == (b == a); }
+static int  ne(int a, int b) { return (a != b) == (b != a); }
+
+
+/*
+ * check-name: cse-commutativity
+ * check-command: test-linearize $file
+ * check-output-ignore
+ *
+ * check-output-excludes: add\\.
+ * check-output-excludes: muls\\.
+ * check-output-excludes: and\\.
+ * check-output-excludes: or\\.
+ * check-output-excludes: xor\\.
+ * check-output-excludes: seteq\\.
+ * check-output-excludes: setne\\.
+ */
-- 
2.11.0

[PATCH 3/4] CSE: avoid hashing removed instructions

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/cse.c b/cse.c
index 5380f4ccd..0d3815c5a 100644
--- a/cse.c
+++ b/cse.c
@@ -43,6 +43,8 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
 		return;
 	assert(insn->bb == bb);
 	repeat_phase |= simplify_instruction(insn);
+	if (!insn->bb)
+		return;
 	hash = (insn->opcode << 3) + (insn->size >> 3);
 	switch (insn->opcode) {
 	case OP_SEL:
-- 
2.11.0

[PATCH 4/4] CSE: improve hashing of non-commutative binops

[Luc Van Oostenryck]

During CSE equivalent instructions should hash to the same value
but we should also try to *not* hash to the same value instructions
that cannot be equivalent.
For commutative ops this means that the hash function should itself
be commutative/symmetrical regarding the exchange of its operands.
This is already the case but the current hash function is symmetrical
for all binops, not only the commutative ones. Thus expressions like
'a - b' and 'b - a' hash to the same value while it should be the case
only when 'a == b'.

Fix this by changing the hashing of non-commutative binops so that it
is anti-symmetrical regarding the exchange of operands while keeping
commutative ones symmetrical.

This change have no functional effects (in the sense that it shoudl
CSE exactly the same instructiosn as before), it should only improve
the efficiency of the hashing+comparing.

Note: on the 5000+ test set I'm using, I can't see any significant
  speedup which is quite normal since most of the functions therein
  have (much) less instructions than the size of the hash table.
  The effect of this patch should only be on much bigger functions.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c | 26 ++++++++++++++------------
 1 file changed, 14 insertions(+), 12 deletions(-)

diff --git a/cse.c b/cse.c
index 0d3815c5a..89812afae 100644
--- a/cse.c
+++ b/cse.c
@@ -51,28 +51,30 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
 		hash += hashval(insn->src3);
 		/* Fall through */	
 
-	/* Binary arithmetic */
-	case OP_ADD: case OP_SUB:
-	case OP_MULU: case OP_MULS:
+	/* non-commutative binops */
+	case OP_SUB:
 	case OP_DIVU: case OP_DIVS:
 	case OP_MODU: case OP_MODS:
 	case OP_SHL:
 	case OP_LSR: case OP_ASR:
-	case OP_AND: case OP_OR:
-
-	/* Binary logical */
-	case OP_XOR: case OP_AND_BOOL:
-	case OP_OR_BOOL:
-
-	/* Binary comparison */
-	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:
+		hash -= hashval(insn->src2);
+		hash += hashval(insn->src1);
+		break;
+
+	/* commutative binops */
+	case OP_SET_EQ: case OP_SET_NE:
+	case OP_ADD:
+	case OP_MULU: case OP_MULS:
+	case OP_AND_BOOL: case OP_OR_BOOL:
+	case OP_AND: case OP_OR:
+	case OP_XOR:
 		hash += hashval(insn->src2);
 		/* Fall through */
-	
+
 	/* Unary */
 	case OP_NOT: case OP_NEG:
 		hash += hashval(insn->src1);
-- 
2.11.0

Re: [PATCH 4/4] CSE: improve hashing of non-commutative binops

[Christopher Li]

On Fri, Feb 17, 2017 at 7:12 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> During CSE equivalent instructions should hash to the same value
> but we should also try to *not* hash to the same value instructions
> that cannot be equivalent.
> For commutative ops this means that the hash function should itself
> be commutative/symmetrical regarding the exchange of its operands.
> This is already the case but the current hash function is symmetrical
> for all binops, not only the commutative ones. Thus expressions like
> 'a - b' and 'b - a' hash to the same value while it should be the case
> only when 'a == b'.
>
> Fix this by changing the hashing of non-commutative binops so that it
> is anti-symmetrical regarding the exchange of operands while keeping
> commutative ones symmetrical.
>
> This change have no functional effects (in the sense that it shoudl
> CSE exactly the same instructiosn as before), it should only improve
> the efficiency of the hashing+comparing.
>
> Note: on the 5000+ test set I'm using, I can't see any significant
>   speedup which is quite normal since most of the functions therein
>   have (much) less instructions than the size of the hash table.
>   The effect of this patch should only be on much bigger functions.

I apply and push this series to sparse-next.

Just curious if there is test case can show the performance increase.
As far as I can tell, this patch has down side as well, it hash the non
commutative operation *twice*. If for most of the case this actually
is the higher cost we might want to keep the old behavior.

Chris

Re: [PATCH 4/4] CSE: improve hashing of non-commutative binops

[Luc Van Oostenryck]

On Thu, Feb 23, 2017 at 08:39:17PM +0800, Christopher Li wrote:
> On Fri, Feb 17, 2017 at 7:12 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > During CSE equivalent instructions should hash to the same value
> > but we should also try to *not* hash to the same value instructions
> > that cannot be equivalent.
> > For commutative ops this means that the hash function should itself
> > be commutative/symmetrical regarding the exchange of its operands.
> > This is already the case but the current hash function is symmetrical
> > for all binops, not only the commutative ones. Thus expressions like
> > 'a - b' and 'b - a' hash to the same value while it should be the case
> > only when 'a == b'.
> >
> > Fix this by changing the hashing of non-commutative binops so that it
> > is anti-symmetrical regarding the exchange of operands while keeping
> > commutative ones symmetrical.
> >
> > This change have no functional effects (in the sense that it shoudl
> > CSE exactly the same instructiosn as before), it should only improve
> > the efficiency of the hashing+comparing.
> >
> > Note: on the 5000+ test set I'm using, I can't see any significant
> >   speedup which is quite normal since most of the functions therein
> >   have (much) less instructions than the size of the hash table.
> >   The effect of this patch should only be on much bigger functions.
> 
> I apply and push this series to sparse-next.
I don't see them yet, but it's not important.

> Just curious if there is test case can show the performance increase.
I don't have such test case. To see any effect you would need a
function with a number of instructions quite large relatively to
the size of the hash table. It's even worse than that, it's the
number of pair of dual instructions (like 'a - b' / 'b - a') that
should be large (and to see a significant relative difference,
those pairs should also be a significant proportion of the total
numbers of instructions).

If needed I could try to build some artificial cases to determine
when a difference appears but ... (see below).

> As far as I can tell, this patch has down side as well, it hash the non
> commutative operation *twice*.
Sure it has some down fall but I it's not true that they are now
hashed twice. The number of operations is exactly the same as for
the commutative ones: each of src1 & src2 are 'hashed' together with
the opcode and the instruction size (and the hash() function is
essentially a no-op, not a costly thing anyway). The difference
between the two cases is that for commutative instructions src2
is first hashed and then there is a fall-through to the unary ops
to add src1's hash.
The down side is only a slight increase in code complexity.

> If for most of the case this actually
> is the higher cost we might want to keep the old behavior.
I can redo my tests and give the numbers but the measurements
I made didn't didn't showed any significant differences:
no speedup but also no slowdown.


That said, I completly agree that there is not much justification
to this patch. The only reason I made it was because when I modified
the code for the commutative case (which don't give a speedup but
eliminate more common expression) I took a look at the non-commutative
situation and said to myself something like: "Oh, they are hashed
symmetrically, like the commutative ones, that's not very logical".

So, I have absolutely no problems if this patch is dropped.
(much more interesting is the patch following this in the serie:
 "[RFC] CSE: relax type checking in hashing/compare").

Luc

Re: [PATCH 4/4] CSE: improve hashing of non-commutative binops

[Luc Van Oostenryck]

On Thu, Feb 23, 2017 at 03:13:14PM +0100, Luc Van Oostenryck wrote:
> 
> So, I have absolutely no problems if this patch is dropped.

After some more thoughts I'm convinced that this patch was
a bad idea, please drop it.

The rationale being that even if there is a lot of pair of
dual instructions ('Xi - Yi' / 'Yi - Xi'), their hashing
will still be spreaded relatively evenly because there
will be a lot of Xi & Yi but with the patch *every*
instruction like 'Xi - Xi' will give the same hash
indenpendently of the Xi.

Luc

Re: [PATCH 4/4] CSE: improve hashing of non-commutative binops

[Christopher Li]

On Thu, Feb 23, 2017 at 11:03 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Thu, Feb 23, 2017 at 03:13:14PM +0100, Luc Van Oostenryck wrote:
>>
>> So, I have absolutely no problems if this patch is dropped.
>
> After some more thoughts I'm convinced that this patch was
> a bad idea, please drop it.

OK. Patch dropped in the current sparse-next.

Chris