[patch] Local factoring algorithms

Gábor Lóki loki@inf.u-szeged.hu
Tue Mar 23 09:17:00 GMT 2004


Hi,
in my last mail I described some algorithms which we can use to save
some code size:
http://gcc.gnu.org/ml/gcc/2004-02/msg00981.html

The attached patch is a local factoring algorithm. This patch tries to
merge identical rtl insns by moving them to a point that pre- or
post-dominates all occurrences.

For example:
- "move rtl up":
    ***
     if (A) {B; C; D; E; F;}
     else   {G; D; B; H;}
    *** becomes ***
     B; D;
     if (A) {C; E; F;}
     else   {G; H;}
    ***
If and only if B and D insns can be moved from their original
blocks before the jump.
The same method is used for "move rtl down".

The algorithm is not restricted to 'if' cases, it works on any type of
cfg.

I have the following results with CSiBE:
-Os: arm-elf:0.15%, i386-elf:0.70%, i686-linux:0.69%, ppc-elf:0.17%
-O2: arm-elf:0.10%, i386-elf:0.81%, i686-linux:0.72%, ppc-elf:0.20%

The patch was bootstraped on i686-pc-linux-gnu. It was regtested on
{arm,i386,mips,ppc}-elf with no new failures.

On i686-linux I have some execution fail, because life_analysis deletes
some floating-point store. I don't know why. I just have noop moves for
that fstp insns. I will check this.

Although this patch is about code size it is also acceptable for
performance. Because it only moves and deletes insns.

What do you think about it?

Regards,
     GĂĄbor LĂłki

PS:
We will soon send a more powerful factoring patch. It saves more than
2% when optimizing size!



2004-03-23  GĂĄbor LĂłki <loki@inf.u-szeged.hu>

      * factoring.c: New file for local factoring
      * factoring.h: Same
      * Makefile.in: Add it
      * flags.h: Declare factoring flag
      * common.opt: Same
      * opts.c: Same
      * timevar.def: Same
      * toplev.c: Same
      * passes.c (rest_of_compilation, rest_of_factoring,
        dump_file_info, dump_file_index): Registring
        local factoring for dump files, add rest_of_factoring
        function decl. and call

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: localfactoring.patch
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20040323/5923dee6/attachment.ksh>


More information about the Gcc-patches mailing list