Re: [PATCH] flatten switch-stmt into if-else chain for -Os

[Bernhard Fischer <rep dot dot dot nop at gmail dot com>]

On Sun, Apr 15, 2007 at 02:01:09PM -0700, Mark Mitchell wrote:
>Bernhard Fischer wrote:
>
>> 2007-04-15  Bernhard Fischer  <..>
>> 
>> 	* stmt.c (expand_case): Do not create a complex binary tree when
>> 	optimizing for size but rather use the simple ordered list.
>> 	(emit_case_nodes): do not emit jumps to the default_label when
>> 	optimizing for size.
>> 
>> Not regtested so far.
>> Comments?
>
>I think this is a good idea.  In general, I'm sure that we could better
>tune -Os, without adding much to the compiler, just by making these
>kinds of adjustments.  So, I'm happy to see you doing that.
>
>Obviously, you need to do full testing.

Yes, of course, I will have to do that..

>> +	  /* When optimizing for size, we want a straight list to avoid
>> +	     jumps as much as possible. This basically creates an if-else
>> +	     chain.  */
>> +	  if (!optimize_size)
>> +	    balance_case_nodes (&case_list, NULL);
>
>Perhaps the comment could be better written as:
>
>/* When optimizing for speed, we build a binary tree, so that the number
>of tests executed to determine which case applies is minimized.  The
>binary tree method introduces additional tests, corresponding to
>interior nodes in the tree.  Therefore, when optimizing for space, we
>just emit a linear series of tests; while the program is likely to
>execute more tests, we avoid consuming generating code for the
>interior-node tests.  */

That's better. Thanks!
>
>Have you by any chance tried running CSiBE with this patch, with -Os
>turned on, to see what kind of different it makes?  I think that it
>would be good to get some benchmark data (CSiBE, GCC itself, some other
>application of interest) to make sure that this change actually does
>seem to consistently help across more than just a small test case.

targeted at arm-linux-uclibc, the resulting compiler (4.2.0 release)
gave, for CSiBE (just totals):

Plain -Os, no other flags:
arm926t-orig.csv:       3404962
arm926t-00.csv:         3404498

some flags in addition to Os:
arm926t-orig-.csv:      3391234
arm926t-00-.csv:        3391086

Not too much..

Real world example, e.g. busybox:
   text    data     bss     dec     hex filename
 636890    2372   10580  649842   9ea72 _bb-combine.oorig
 636230    2372   10580  649182   9e7de _bb-combine.flatten
 638266    2368   10580  651214   9efce _bb.oorig
 637606    2368   10580  650554   9ed3a _bb.flatten

Not much either, but at least it helps a little bit.

Another common case where we do not generate good code is for this case,
taken from busybox's diff.c. The 'switch' is the original version and the
'if' is something that is supposed to do the same thing but is much
smaller:
#if 0
        switch (ch) {
        case 'c':
            fetch(ixold, lowa, a - 1, f1, ' ');
            fetch(ixold, a, b, f1, '-');
            fetch(ixnew, c, d, f2, '+');
            break;
        case 'd':
            fetch(ixold, lowa, a - 1, f1, ' ');
            fetch(ixold, a, b, f1, '-');
            break;
        case 'a':
            fetch(ixnew, lowc, c - 1, f2, ' ');
            fetch(ixnew, c, d, f2, '+');
            break;
        }
#else
        if (ch == 'c' || ch == 'd') {
            fetch(ixold, lowa, a - 1, f1, ' ');
            fetch(ixold, a, b, f1, '-');
        }
        if (ch == 'a')
            fetch(ixnew, lowc, c - 1, f2, ' ');
        if (ch == 'c' || ch == 'a')
            fetch(ixnew, c, d, f2, '+');
#endif

In an ideal world the exact same code that is created by the 'if' should
be emitted for the normal switch statement, and one wouldn't have to do
all these by hand.. And in an ideal world -frtl-abstract-sequences
wouldn't ICE as often as it does today, too ;)