Re: Loop invariance of externals.

davidm@Rational.COM (David Moore) writes:


> Consider the following C code fragment:
> extern int i;
> extern int j;
> ...
> while (something)
> i=i+a[j];
> ...
> It seems automatic to say that j is invariant around this loop.
> BUT WAIT!. Suppose i and j happen to be the same address.


Can't happen. i and j have been declared as int's, not as
pointers-to-int's or int-reference's.




> Or, slightly less bizarre, j might be bound to an input register
> of an external device. In this case we don't even need to assign
> to a potentially conflicting extern to get j non-invariant.


This is a programmer-bug. The programmer should have used "volatile".
      [Seems to me that this is exactly what volatile was invented for. -John]


So my compiler takes the aggressive approach here, because there is
no possible conflict. In the following code, the compiler has to be
conservative:


    int foo( int &i, int &j ) {
        a = malloc(1zillion); /* no chance a aliases i or j */
        while( something )
            i += a[j];
        return i;
    }


Here the code is translated internally to something that looks like:


    int foo( int *i, int *j ) {
        a = malloc(1zillion); /* no chance a aliases i or j */
        while( something )
            *i += a[*j]; /* possible alias of i & j is obvious */
        return *i;
    }


Now the possible alias is made explicit. Some Day Real Soon Now the
compiler could do a run-time test & clone the procedure:


    int foo( int *i, int *j ) {
        a = malloc(1zillion); /* no chance a aliases i or j */
        int tmp0 = *i; /* original value of *i, hoisted to a register */
        if( i == j ) { /* determine alias vs no-alias */
            while( something )
                tmp0 += a[tmp0]; /* load & increment. a[tmp0] is NOT loop-invar */
        } else { /* The NO-ALIAS version */
            int tmp1 = a[*j]; /* loop invariant is hoisted */
            while( something )
                tmp0 += tmp1; /* Increment by loop-invariant */
        }
        *i = tmp0; /* store back *i */
        return tmp0;
    }


Don't hold your breath,
Cliff


Cliff Click Compiler Research Scientist
Cambridge Research Office, Hewlett-Packard Laboratories
One Main Street, 10th Floor, Cambridge, MA 02142
(617) 225-4915 Work (617) 225-4930 Fax
cliffc@hpl.hp.com http://bellona.cs.rice.edu/MSCP/cliff.html
--

Return to the comp.compilers page.
Search the comp.compilers archives again.