[Bug rtl-optimization/11832] Optimization of common code in switch statements

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[christophe dot jaillet at wanadoo dot fr]

------- Comment #2 from christophe dot jaillet at wanadoo dot fr  2006-07-14 21:11 -------
I tried to compile it on my cygwin box and had a strange (and certainly
unrelated) behaviour :

gcc -O3 test.c -S
Version 3.4.4 (must be the latest version available on cygwin :()

Description : the case 1 is tested in two times. First <=2 then == 1. I think
that it is useless and that if 
        cmpl    $2, %ebx
        jle     L9
was turned into
        cmpl    $1,%ebx
        je      L9
the second test after L9: would be useless.

See code below.

        .file   "test.c"
        .def    ___main;        .scl    2;      .type   32;     .endef
        .text
        .p2align 4,,15
.globl _main
        .def    _main;  .scl    2;      .type   32;     .endef
_main:
        pushl   %ebp
        movl    $16, %eax
        movl    %esp, %ebp
        pushl   %ebx
        subl    $4, %esp
        andl    $-16, %esp
        call    __alloca
        call    ___main
        cmpl    $2, %ebx
        je      L4
        cmpl    $2, %ebx
        jle     L9                   ==> every thing <= 2
        cmpl    $3, %ebx
        je      L10
L6:
        movb    $13, (%ebx)
        xorl    %eax, %eax
        movb    $13, 1(%ebx)
        movb    $13, 2(%ebx)
        movb    $13, 3(%ebx)
        movl    -4(%ebp), %ebx
        leave
        ret
        .p2align 4,,7
L9:
        cmpl    $1, %ebx             ==> Now comparaison against 1 is done !
        jne     L6
        movb    $13, (%ebx)
        xorl    %eax, %eax
        movl    -4(%ebp), %ebx
        leave
        ret
        .p2align 4,,7
L4:
        movb    $13, (%ebx)
        xorl    %eax, %eax
        movb    $13, 1(%ebx)
        movl    -4(%ebp), %ebx
        leave
        ret
        .p2align 4,,7
L10:
        movb    $13, (%ebx)
        xorl    %eax, %eax
        movb    $13, 1(%ebx)
        movb    $13, 2(%ebx)
        movl    -4(%ebp), %ebx
        leave
        ret


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[aldot at gcc dot gnu dot org]

-- 

aldot at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |aldot at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-12-07 04:15:54         |2007-08-17 07:17:48
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[steven at gcc dot gnu dot org]

------- Comment #3 from steven at gcc dot gnu dot org  2007-08-18 14:13 -------
This is really a case of missed code hoisting.  There are several ways to
resolve this bug.


The first thing I would do, is to experiment with the existing code hoisting
pass in gcse.c.  This pass is only enabled with -Os because this supposedly is
not useful.  Quoting gcse.c:

      /* It does not make sense to run code hoisting unless we are optimizing
         for code size -- it rarely makes programs faster, and can make
         them bigger if we did partial redundancy elimination (when optimizing
         for space, we don't run the partial redundancy algorithms).  */

In the case of this bug, it may make sense to run code hoisting.  A patch for
gcse.c to enable hoisting for experimental purposes should be trivial.



Another way would be to do as the patch that was posted to gcc-patches, see:
http://gcc.gnu.org/ml/gcc/2007-08/msg00279.html.  But as posted, this patch
basically re-invents a third implementation of value numbering by cloning parts
of tree-ssa-dom.c, where GCC should actually try to use the value numbering
interface of tree-vn.c.  This pass also only implements hoisting out of switch
blocks.  Finally, the algorithm posted is O(n_stmts_in_bb**2) worst case, i.e.
quadratic.  This will probably show in the bootstrap times (e.g. in the compile
time of insn-attrtab.c with its many large switch blocks).



Finally, a more generic and perhaps more interesting approach would be to
implement code hoisting within the current value numbering framework (i.e. what
is also used by the GVN-PRE and FRE passes).

A hoisting pass in the PRE/FRE framework would run before PRE/FRE.  The hoist
pass itself would work as follows:

1. Find candidate values for hoisting.  Make intersections of the ANTIC sets of
successor basic blocks.  Values that are ANTIC_IN in all successors of a basic
block B can be hoisted into B.

2. Rank and sort the candidate values with a cost function (which could take
into account such things as register pressure, block frequency, etc.)

3. Perform the hoisting of the most suitable candidates.  This is done by
inserting an expression representing the value into the block where the value
can be hoisted to, and updating the AVAIL_OUT information of the affected basic
blocks.

4. Let PRE/FRE eliminate the now fully redundant original expressions.

Note, this algorithm would work values instead of expressions, re-uses the
existing value numbering framework, and takes advantage of the existing PRE/FRE
passes to do the elimination work.
Implementing this idea would fix PR23286, and most of this bug in the process.

Cool, no?



Of course, to really get the best code for the test case for this bug, you'd
have to re-organize the case labels, as Gabor already pointed out.  You'd want
to transform the original test case:

--- c example ---
int a, b, e;
unsigned char *c;
void foo()
{
  int d = 13;
  b = -1;   
  switch (e) {
    case 1:
      b++; c[b] = (unsigned char)d;
      break;
    case 2:
      b++; c[b] = (unsigned char)d;
      b++; c[b] = (unsigned char)d;
      break;
    case 3:
      b++; c[b] = (unsigned char)d;
      b++; c[b] = (unsigned char)d;
      b++; c[b] = (unsigned char)d;
      break;
    default:
      a = 1;
      b++; c[b] = (unsigned char)d;
      b++; c[b] = (unsigned char)d;
      b++; c[b] = (unsigned char)d;
      b++; c[b] = (unsigned char)d;
  }
}
-----------------

into this:

--- c example ---
int a, b, e;
unsigned char *c;
void foo()
{
  int d = 13;
  b = -1;   
  switch (e) {
    default:
      a = 1;
      b++; c[b] = (unsigned char)d;
    case 3:
      b++; c[b] = (unsigned char)d;
    case 2:
      b++; c[b] = (unsigned char)d;
    case 1:
      b++; c[b] = (unsigned char)d;
  }
}
-----------------

I have never seen an algorithm that could do this kind of transformation, and I
wonder whether code sequences of this kind occur frequently enough in practice
to invent a new algorithm for this by yourself.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |23286


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[aldot at gcc dot gnu dot org]

------- Comment #4 from aldot at gcc dot gnu dot org  2007-08-22 20:07 -------
I'll try to find the time to thing about VN / PRE. Thanks, stevenb, for your
comment.
Please feel free to ping or take this if i time out (as usual)..


-- 

aldot at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|aldot at gcc dot gnu dot org|unassigned at gcc dot gnu
                   |                            |dot org
             Status|ASSIGNED                    |NEW


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[aldot at gcc dot gnu dot org]

------- Comment #5 from aldot at gcc dot gnu dot org  2007-12-30 10:47 -------
Created an attachment (id=14842)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14842&action=view)
rough, half-finished, disfunctional thought; not a patch

The attached thoughts do not yet insert/remove stmt candidates but just record
possible candidates in the corresponding bitmaps.

Unfortunately this prooves that the current SSA-SCCN-VN does not work for the
testcase in comment #1 since antic_in is empty (but it should contain ++i).

Nevertheless this will potentially help for PR23286 and PR5738 since for those
testcases the hoisting-candidates are found properly.

I intend to think about finishing this draft as described by stevenb soonish
but still, i will have to finish up the inefficient variant that only cares
about switch stmts (perhaps defaulting to on at -Os, just for my personal use)
until SSA-SCCN-VN recognizes the VN for the testcase of #1


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[aldot at gcc dot gnu dot org]

------- Comment #6 from aldot at gcc dot gnu dot org  2008-01-03 09:19 -------
Dummy sample that has a hoisting opportunity:

int bazoo (unsigned int in)
{
  int i = 0;
  if (in >= 0)
    ++i; /* hoist */
  if (in >= 1)
    ++i;
  if (in >= 2)
    ++i;
  if (in >= 3)
    ++i;
  if (in >= 4)
    ++i;
  return i;
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[danglin at gcc dot gnu dot org]

------- Comment #7 from danglin at gcc dot gnu dot org  2009-02-19 14:52 -------
Reconfirmed with trunk revision 144268.


-- 

danglin at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |danglin at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[aldot at gcc dot gnu dot org]

------- Comment #8 from aldot at gcc dot gnu dot org  2009-07-02 15:05 -------
Important reminder from steven from
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33828#c13

stevenb> GCC should not hoist up further than up to the first common dominator.

i.e. "..can be Hoisted to B" from #3
and _not_ to the def_stmt (iff the def_stmt is not in B of course, if it is
then it's obviously the correct spot to hoist to).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[steven at gcc dot gnu dot org]

------- Comment #9 from steven at gcc dot gnu dot org  2009-07-02 15:12 -------
Note I have various working patches for GVN-based hoisting.  All of them are
actually too aggressive, causing failures in the vectorizer test cases
(unrecognizable data dependency patterns).  But I still intend to post one of
the versions for inclusion in GCC 4.5.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832

[Bug rtl-optimization/11832] Optimization of common code in switch statements

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |16996
              nThis|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832