[PATCH, middle-end] Switch initializations conversion (take four.1)

[Roger Sayle]

>>  +/*
>>  +     Switch initialization conversion
>>  +
>>  +The following pass changes simple initializations of scalars in a 
>> switch
>>  +statement into initializations from a static array.  Obviously, the 
>> values must
>>  +be constant and known at compile time and a default branch must be
>>  +provided.  For example, the following code:
>>  +
>>  +        int a,b;
>>  +
>>  +        switch (argc)
>>  +       {
>>  +         case 1:
>>  +         case 2:
>>  +                a_1 = 8;
>>  +                b_1 = 6;
>>  +                break;
>>  +         case 3:
>>  +                a_2 = 9;
>>  +                b_2 = 5;
>>  +                break;
>>  +         case 12:
>>  +                a_3 = 10;
>>  +                b_3 = 4;
>>  +                break;
>>  +         default:
>>  +                a_4 = 16;
>>  +                b_4 = 1;
>>  +        }
>>  +       a_5 = PHI <a_1, a_2, a_3, a_4>
>>  +       b_5 = PHI <b_1, b_2, b_3, b_4>
>>  +
>>  +
>>  +is changed into:
>>  +
>>  +        static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 
>> 1, 4};
>>  +        static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 
>> 16, 16,
>>  +                                 16, 16, 10};
>>  +
>>  +        if (((unsigned) argc) - 1 < 11)
>>  +          {
>>  +           a_6 = CSWTCH02[argc - 1];
>>  +            b_6 = CSWTCH01[argc - 1];
>>  +         }
>>  +       else
>>  +         {
>>  +           a_7 = 16;
>>  +           b_7 = 1;
>>  +          }
>>  +         a_5 = PHI <a_6, a_7>
>>  +         b_b = PHI <b_6, b_7>
>>  +
>>  +There are further constraints.  Specifically, the range of values 
>> across all
>>  +case labels must not be bigger than CSWTCH_BRANCH_RATIO (default eight) 
>> times
>>  +the number of the actual switch branches.
>>  +*/

By a strange coincidence, one of the switch statement transformations that 
I'll
describe at the GCC summit this year is called "index mapping" which is used
to improve the density/space requirements of sparse switch statements.  When
combined with "switch initialization converstion" and lower bound 
elimination,
the resulting code would look like:

  static const char map[13] = { 0,  1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 };
  static const int CSWITCH_a[4] = { 16, 8, 9, 10 };
  static const int CSWITCH_b[4] = {   1, 6, 5, 4   };
  int i;
  // This is potentially a conditional move instruction
  // even if a,b are floating point or BLKmode types.
  if ((unsigned) argc) <= 12)
    i = map[argc];
  else i = 0;
  a = CSWITCH01[i];
  b = CSWITCH02[i];

You'll notice that the resulting code scales better for sparse tables
and also for more (and more complex) assignments.  The indexes can
even be permuted based upon frequency such that the hot case
values map to consecutive indexes.

More in Ottawa,

Roger
--