cse: move to next comparable instruction

Let's suppose we have a few instructions: A, B, C & D,
all congruent insn_compare()

The current way the CSE is done is:
  The first try will be try_to_cse(A,B). If this succeeds,
  A & B have been merged (AB) and the next try will be done
  with the next instruction:
	try_to_cse(AB,C).
  That's good. However, if it fails, the next try will be:
	try_to_cse(A,C).
  If this one also fails, the next one will be:
	try_to_cse(A,D)
  And if this one also fails, nothing else is done.
In other words, all attempts are done with A. If it happens that
A can't be eliminated (because it doesn't dominate B, C & D and
is not dominated by them), no eliminations are done because the
other pairs, not involving A are never tried.

Ideally, we should try all possible pairs: A-B, A-C & A-D but
also B-C, B-D & C-D. However this is quadratic and can be a bit
costly. An easy & cheap way to improve the current situation is,
in case of failure, to not reuse the original first instruction
but the other one. So instead of testing:
	A-B, A-C, A-D, ...
we will test:
	A-B, B-C, C-D, ...
with the result that an 'bad' instruction can't block anymore
the following pairs.

So, when try_to_cse() fails, do not retry by keeping the first
instructions, but retry using the second one.

In practice, this seems to work fairly well.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

1 files changed, 2 insertions, 0 deletions

diff --git a/cse.c b/cse.c
index 231b7e86..33cc40dc 100644
--- a/cse.c
+++ b/cse.c
@@ -361,6 +361,8 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
 		i1 = cse_one_instruction(i2, i1);
 		remove_instruction(&b1->insns, i1, 1);
 		add_instruction_to_end(i1, common);
+	} else {
+		i1 = i2;
 	}
 
 	return i1;