Re: [PATCH] Implement switch statements with bit tests

[Roger Sayle <roger at www dot eyesopen dot com>]

On Fri, 24 Jan 2003, Richard Earnshaw wrote:
> When written as a 'C' like transformation, what you are doing is
> undefined, since you can end up with a shift that is more than the word
> size (consider calling foo with x=65536).

Hi Richard,

I think you missed it.  Look at the sequence of subtractions and
compares again:

> > 	t1 = x - MINVAL
> > 	if (t1 > RANGE)
> > 	  goto DEFAULT
> > 	t2 = 1 << t1

First we subtract MINVAL, so that the smallest shift we are
interested in is zero, then we test whether t1 is greater than
RANGE.  As I explained in the original post, we limit RANGE
to less than the number of bits in SImode, hence for typical
32-bit targets, RANGE is atmost 31.

This then means that we've always confirmed that the right
argument to the shift operation is between 0..31, so we've
restricted it to the defined range on all platforms.


I'm sorry for using the C analogy "if ((1<<x) & CST)" what
I should really have written it out in its fullest form as
"if ((x<=MAXVAL) && ((1<<(x-MINVAL)) & CST))", where the
subtraction and range comparison are shared by all the ifs.


You're right of course that some platforms, but not ARM nor
x86, have saturating shifts such that (1<<x) is zero if x
is greater than or equal to the word size.  And on such
platforms GCC could in theory generate a shorter sequence.
However, I'm unsure how to identify those targets and whether
there were enough of them to make the optimization worthwhile.

This is obviously fodder for a follow-up patch.  The current
code seems to have confused enough people as it is.

Roger
--