switch index optimization

[Todd P. Whitesel]

Joe Buck <jbuck@synopsys.com> writes:

>If you're going to do that, it seems you could go one step further and
>propagate ranges (min and max values of expressions).  Constant
>propagation is then just a special case (min == max).  With this framework
>one could then implement efficient array bounds checking (omitting checks
>for expressions guaranteed to be within range).

But wait, there's more where that came from...

Given the min,max,signedness you can compute how many "information" bits
there are. This lets you draw conclusions about how the upper bits will
behave in certain circumstances (all examples 32 bit centric):

	(short) x
if x's value (x here means any expression) can be represented in a short,
nuke the cast. If your chip's register argument convention requires yucky
casts to pass char/short types correctly then this might be valuable.

A somewhat more complicated example:

	((x * 256) / 16)
easily becomes
	((x << 8) / 16)
but you want to do better than (x + (int) ( ((unsigned) (x >> 31)) >> 28)) >> 4
when x is signed or will be promoted to signed. If you can show that (x >= 0)
and (x <= 0x00FFFFFF) then you have (a) the divide collapses to unsigned >>
	((x << 8) >> 4)
and (b) the top bits in the danger zone are already zero.
	(x << 4)

I ran into this while tuning a customer benchmark once. It was plain C, but
with heavy macro use. Fairly quickly I realized I wanted a more generic pass,
but it never happened (at least not while I was there). BTW make sure CSE
doesn't yank (x*256) into a temp until after we've checked for this trick.
More fun:

typedef long LONGEST;
func(char *source1, char *source2, char *destination, int width)
{
    int i;
    LONGEST *p = (LONGEST *) source1;
    LONGEST *q = (LONGEST *) source2;
    LONGEST *r = (LONGEST *) destination;
    width /= sizeof(LONGEST);
    width *= sizeof(LONGEST);
    for (i = width; i >= 0; i -= sizeof(LONGEST)) {
        r[i/sizeof(LONGEST)] = p[i/sizeof(LONGEST)] & q[i/sizeof(LONGEST)];
    }
}

This is a slightly misguided attempt to get good bitmap code on machines like
sparc with reg+reg addressing. Here's what I got with a close-at-hand gcc:

func:
        !#PROLOGUE# 0
        !#PROLOGUE# 1
        andcc %o3,-4,%o3
        bl .LL3
        mov %o0,%o4
.LL5:
        and %o3,-4,%g2			# _we_ know this is a virtual NOP.
        ld [%o4+%g2],%g3
        ld [%o1+%g2],%o0
        addcc %o3,-4,%o3
        and %g3,%o0,%g3
        bpos .LL5
        st %g3,[%o2+%g2]
.LL3:
        retl
        nop
.LLfe1:
        .size    func,.LLfe1-func
        .ident  "GCC: (GNU) cygnus-2.7.2-960126"

Now this suggests tracking the low bits of an expression somehow (maybe we
don't care so much about making this go fast, but perhaps there are others
like it, especially the inline-C++ scenario that's been mentioned). Hmm:

	value = (stride * "N") + offset

Here "N" represents the integers in a number-theory sense, so we should
require (stride > 0) and (offset >= 0) and (stride > offset). In the
example above, we could get to the virtual NOP instruction and see that
it is clearing the bits; but when we get here stride=4,offset=0 so we
know those bits are already clear.

Seems like this might be a neat way to take analysis from the loop optimizer
and make it useful to other optimizations. By default an expression or lvalue
has stride=1,offset=0 and as you munge it we update as appropriate. When
things get too complicated we punt and drop back to the default.

Unfortunately I have a vague feeling of dread that this will turn out to be
too-expensive / not-enough-boost to make it attractive except as a "compile
all night, we're about to go to QA" O-level.

Todd Whitesel
toddpw @ ugcs.caltech.edu