diff options
| author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2017-06-13 15:44:27 +0200 |
|---|---|---|
| committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-06-26 09:15:29 +0200 |
| commit | c3e9c9bb6a40429aa6088a47bb7e4fa6314800ca (patch) | |
| tree | 9c6d299106a1fd14d70d5c6494fccea2c91b137b /validation/optim | |
| parent | 1091da3a64c840d813fb4d035e8b90ca126f8114 (diff) | |
| download | sparse-dev-c3e9c9bb6a40429aa6088a47bb7e4fa6314800ca.tar.gz | |
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>
Diffstat (limited to 'validation/optim')
| -rw-r--r-- | validation/optim/cse-cmp-next.c | 1 |
1 files changed, 0 insertions, 1 deletions
diff --git a/validation/optim/cse-cmp-next.c b/validation/optim/cse-cmp-next.c index e7cf1623..50fdbac0 100644 --- a/validation/optim/cse-cmp-next.c +++ b/validation/optim/cse-cmp-next.c @@ -9,7 +9,6 @@ void foo(int p, int i, int f, int *ref, int *dst, int *src) /* * check-name: cse-cmp-next * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-pattern(1,2): mul\\. |