[PATCH] Sequence abstraction

["Akos Kiss" <akiss at rgai dot hu>]

Hi,

as Gabor Loki mentioned in an earlier mail
(http://gcc.gnu.org/ml/gcc-patches/2004-03/msg01907.html) we have developed
a powerful algorithm especially targeted for size reduction.

Let's see the results first:
arm-elf: 2.785%
i386-elf: 1.356%
i686-linux: 1.448%
m68k-elf: 2.312%

(Measured on the CSiBE benchmark with -Os. The figures represent code size
reduction compared to the mainline.)

The patch was bootstrapped on i686-linux and regtested on
{arm,i386,m68k}-elf and i686-linux with no new failures.

The idea behind the algorithm:
We look for identical sequences of RTL insns and try to keep only one
representative instance of them. We delete all the other sequences and
transform the CFG to transfer control to the kept representative. We have to
mimic a call/return mechanism somehow to know where the execution shall
continue after the representative has been executed.

Below is an example on how the algorithm works. The boxes are basic blocks,
A, B, C, D, E, F and G are sequences of RTLs, while c and r are inserted
instructions responsible for the call/return mechanism.

Before:
+-+  +-+
|A|  |E|  +-+
|B|  |B|  |F|
|C|  |C|  |C|
|D|  |D|  |G|
+-+  +-+  +-+

After:
+-+  +-+
|A|  |E|
|c|  |c|
+-+  +-+
 |    |
 +----+
      |
      v   +-+
     +-+  |F|
     |B|  |c|
     +-+  +-+
      |    |
      +----+
      |
      v
     +-+
     |C|
     |r|
     +-+
      |
 +----+----+
 |    |    |
 v    v    v
+-+  +-+  +-+
|D|  |D|  |G|
+-+  +-+  +-+

There is one known problem though: the current call/return mechanism does
not work on the {mips,ppc}-elf targets. We have unrecognized insn errors on
those targets. Of course we will investigate the issue.

So, what do you think about this algorithm?

Regards,
  Akos Kiss



2004-03-22 Akos Kiss <akiss@inf.u-szeged.hu>

 * seqabstr.c: New file.
 * seqabstr.h: New file.
 * Makefile.in: Add new make target seqabstr.o.
 * cfgcleanup.c (outgoing_edges_match): Add extra checks.
 * common.opt: New option.
 * opts.c (common_handle_option): Handle it.
 * passes.c (rest_of_handle_seqabstr): New function.
 * passes.c (rest_of_compilation): Call it.
 * timevar.def (TV_SEQABSTR): New constant..
 * toplev.c (flag_sequence_abstraction): New variable.
 * toplev.h (flag_sequence_abstraction): Declare it.

Attachment: seqabstr.patch
Description: Binary data