pmontgom@MATH.UCLA.EDU (Peter Montgomery) (07/04/89)
/*
In the main program, gcc -O calls rand() whenever any of r1, r2, r3
is mentioned, apparently treating the const declaration as a macro.
Since rand() produces a different value each time it is called,
the loop fails (I had intended that gcc call rand() once and
use that value consistently thereafter). Even if rand() did
return consistent values, generation of procedure calls
does not seem an optimization.
Likewise, in function SHELL_SORT, gcc re-evaluates *pari
everywhere arrayj is mentioned in the loop body (though not in
loop termination), even though the pointer pari changes.
Consequently the array does not sort completely.
Here is the GCC code for SHELL_SORT (very good overall):
link a6,#0
moveml #0x3f00,sp@-
movel a6@(8),a1 a1 = array
movel a6@(12),d6 d6 = lng
movel d6,d1
addql #1,d1 d1 = lng+1
jra L16
L13:
movel d1,d0 d0 = j = incr
cmpl d0,d6
jle L14 Branch if lng <= j
movel d1,d2
negl d2 d2 = -incr
movel d1,d3
asll #2,d3 d3 = 4*incr
movel a1,d5
addl d3,d5 d5 = pari_bnd = &array[incr]
L12:
lea a1@(d0:l:4),a0 a0 = pari = &array[j]
movel a0@,d4 d4 = arrayj
L8:
movel a0@(d2:l:4),d7 d7 = pari[-incr]
cmpl a0@,d7 Compare *pari to pari[-incr] **** ERROR ****
*** SHOULD cmpl d4,d7 ***
jle L9
movel a0@(d2:l:4),a0@ *pari = pari[-incr] *** WHY NOT USE d7? ***
subl d3,a0 pari -= incr
cmpl a0,d5 Compare pari to pari_bnd
jls L8
L9:
movel d4,a0@ *pari = arrayj
addql #1,d0 j++
cmpl d0,d6 Compare j to lng
jgt L12
L14:
L16:
moveq #3,d7
divsl d7,d1 d1 = incr = incr/3 or (lng+1)/3
tstl d1
jgt L13
moveml a6@(-24),#0xfc
unlk a6
rts
The problems exist only if -O is used.
We have GCC 1.34 on a SUN 3/50 and SUN 3/280.
I don't know how it was built.
G++ version 1.34.2 works OK, with or without -O.
Peter Montgomery pmontgom@math.ucla.edu
*/
void SHELL_SORT(int* const array, const int lng)
{ /* Sort an array into ascending order */
register int incr;
for (incr = (lng+1)/3; incr > 0; incr /= 3) {
register int j;
register int* const pari_bnd = &array[incr];
for (j = incr; j < lng; j++) {
register int *pari = &array[j];
register const int arrayj = *pari; /* Repeatedly evaluated */
do {
if (pari[-incr] <= arrayj)
break;
*pari = pari[-incr];
pari -= incr;
} while (pari >= pari_bnd);
*pari = arrayj;
}
}
}
#define SORT_LNG 13
void main()
{
int i;
int sort_data[SORT_LNG];
for (i = 0; i < 10; i++) {
const int r1 = rand();
const int r2 = r1; /* multiple calls to rand() generated */
const int r3 = r1;
if (r2 != r3) {
printf("r1, r2, r3 different %d %d %d \n", r1, r2, r3);
}
}
for (i = 0; i < SORT_LNG; i++) sort_data[i] = (i*i*i*i*i) % SORT_LNG;
SHELL_SORT(sort_data, SORT_LNG);
printf(" Sorted data: "); /* Expect 0 1 2 3 4 5 6 7 8 9 10 11 12 */
for(i = 0; i < SORT_LNG; i++) printf(" %d ", sort_data[i]);
printf("\n");
exit(0);
}