[comp.lang.c] Why the 4.3BSD C compiler seem to botch this ?

dan@rna.UUCP (Dan Ts'o) (04/18/88)

	The code below seems okay and does passed thru SUN's C compiler fine,
but the 4.3BSD C compiler misgenerates a label, causing an assembler error
messages and an unknown external (during loading). (Yes, I know that z is not
used. Its removal has no effect on the problem.)

/* Shellsort */
fsort(a, z, n)
register double *a;
register unsigned z, n;
{
	double w;
	register unsigned i, j, k;

	k = 1;
	n++;
	do {
		k = 3*k + 1;
	} while (k <= n);
	for (k /= 3; k > 0; k /= 3) {
		for (i = k; i < n; i++) {
			w = a[i];
			for (j = i - k; (j >= 0) && (a[j] > w); j -= k)
				a[j + k] = a[j];
			a[j] = w;
		}
	}
}

	Thanks.

chris@trantor.umd.edu (Chris Torek) (04/18/88)

In article <153@rna.UUCP> dan@rna.UUCP (Dan Ts'o) writes:
>	The code below seems okay and does passed thru SUN's C compiler fine,
>but the 4.3BSD C compiler misgenerates a label, causing an assembler error
>messages and an unknown external (during loading).

As you might guess, it is a bug in the compiler, or more precisely, a
bug in the optimiser, which goofs `tst' instructions that are not
followed by a branch.  Specifically:

>	register unsigned i, j, k;
[stuff deleted]
>			for (j = i - k; (j >= 0) && (a[j] > w); j -= k)

The test `j >= 0' is always true, so the compiler generates

	tstl	rJ	# is it < 0?
	cmpd	...	# no!, so do the other half of the && expression

Removing the `j >= 0' test from the source stops the optimiser from
botching its job, although the code is wrong either way.  Replacing
the loop with

	for (j = i - k; (int)j >= 0 && a[j] > w; j -= k)

also does the trick, and incidentally fixes the sort; alternatively,
declare j as `int' rather than `unsigned'.
-- 
In-Real-Life: Chris Torek, Univ of MD Computer Science, +1 301 454 7163
Domain: chris@mimsy.umd.edu		Path: ...!uunet!mimsy!chris