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

["steven at gcc dot gnu dot org" <gcc-bugzilla 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