Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!mailrus!shadooby!accuvax.nwu.edu!tank!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: Yet Another Silly Question
Message-ID: <17934@mimsy.UUCP>
Date: 7 Jun 89 04:59:37 GMT
References: <6458@sdcsvax.UCSD.Edu] <2550091@hpisod2.HP.COM] <18229@unix.cis.pittsburgh.edu>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 42

[context:	int a[MAX], *p; for (p = &a[0]; p < &a[MAX]; p++) ...]

In article <18229@unix.cis.pittsburgh.edu> jcbst3@unix.cis.pittsburgh.edu
(James C. Benz) writes:
>The machine still has to dereference &a[MAX] on each iteration of the
>loop, doesn't it?  It has to perform the test on each iteration to see
>if p is < &a[MAX], and unless the optimizer is really on top of things,
>it has no way of generating the comparison address as a constant.

No: on a typical machine, with a stack pointer (and without alloca(),
or with a frame pointer and optionally with alloca()), the `for' loop
generates code of the form:

		lea	sp@(-8),a2	| compute &a[MAX]
		lea	sp@(-100),a3	| p = &a[0];
	loop:	cmp	a3,a2		| p < [constant]
		jcc	out		| no, exit loop
		...
		jbr	loop
	out:

`a' is not a modifiable lvalue (although it is not `constant', since
the array is local to some function), and MAX is a constant, so &a[MAX]
cannot change during any iteration of the loop.

Actually, many machines have a `count down to zero' loop form which
may be still more efficient, and an optimising compiler (such as
`gcc -O -fstrength-reduce') may change the loop to

	for (p = &a[0], temp = sizeof a/sizeof *a; --temp >= 0; p++)
		... use *p ...

which contains both a strength reduction and a variable substitution
over the original

	for (i = 0; i < MAX; i++) ... use a[i] ...

but does require that `i' not be used for anything except the subscript
calculation.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris