Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!cs.utexas.edu!uunet!mcsun!sunic!kullmar!pkmab!ske
From: ske@pkmab.se (Kristoffer Eriksson)
Newsgroups: comp.lang.misc
Subject: Re: Common subexpression optimization
Message-ID: <2844@pkmab.se>
Date: 9 Feb 90 23:56:00 GMT
References: <PCG.90Feb5183407@rupert.cs.aber.ac.uk> <14229@lambda.UUCP>
Organization: Peridot Konsult i Mellansverige AB, Oerebro, Sweden
Lines: 60

In article <14229@lambda.UUCP> jlg@lambda.UUCP (Jim Giles) writes:
>From article <PCG.90Feb5183407@rupert.cs.aber.ac.uk>, by pcg@rupert.cs.aber.ac.uk (Piercarlo Grandi):
>> [... array indexing within a loop - strength reduction ...]
>> In C this is done by stepping a pointer thru an array. ... The idea that C
>> pointer arithmetic is automatically scaled is another win.
>
>Consider the following two code fragments (side by side):
>
>      int a[200][2];                    int a[200][2]; int *p; int *q;
>      ...                               ...
>      ...                               p = &a; q = p+1;
>      for (i=0;i<200;i++){              for (i=0;i<200;i++){
>        a[i][0] = expr1(i);               *p = expr1(i);
>        a[i][1] = expr2(i);               *q = expr2(i);
>      };                                  p += 2; q += 2;
>                                        };
>
>The first is clearly more readible than the second.  Modern compilers
>can easily find the optimizations necessary to make the first run as
>fast as the second.  The first also has the important advantage of
>clearly stateing something that the second obscures: there are no
>dependencies between the two assignments!  The algorithm is stepping
>through two independent vectors.

Not that I necessarily agree with the first poster about always using
pointers for array loops, but why would you use *two* pointers? It
would be much more "natural" and less obscure this way:

int a[200][2]; int *p;
p = &a[0][0];			/* Start fromthe first int of a. */
for (i = 0; i < 200; i++) {
    *(p++) = expr1(i);
    *(p++) = expr2(i);
};

or this way:

int a[200][2];  /* Array of 200 arrays of two int. */
int (*p)[2];	/* Pointer to array of two int. */
p = a;		/* Start with the first array of two int of a. */
for (i = 0; i < 200; i++) {
    (*p)[0] = expr1(i);
    (*p)[1] = expr2(i);
    p++;	/* Note automatic scaling. */
}

>  (I know, I made the
>problem harder by looping on the first index instead of the second.

Did you? I'd rather think it would be the other index that would be
somewhat harder, and possibly could motivate use of two pointers.

>This is a case where your verbose approach actually decreases the
>information content

No need to be just that verbose...
-- 
Kristoffer Eriksson, Peridot Konsult AB, Hagagatan 6, S-703 40 Oerebro, Sweden
Phone: +46 19-13 03 60  !  e-mail: ske@pkmab.se
Fax:   +46 19-11 51 03  !  or ...!{uunet,mcvax}!sunic.sunet.se!kullmar!pkmab!ske