🚀 go-pugleaf

In article <2301@wn1.sci.kun.nl> eerke@cs.kun.nl (Eerke Boiten) writes:

   In article <13405:Oct1800:22:5690@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
   >I do not remember ever making a mistake in hand optimization by the most
   >fundamental standard technique: adding variable x to keep track of some
   >intermediate quantity, and eliminating redundant variables given x. What
   >optimizer can do this for any but the most primitive intermediate
   >expressions? (Introducing a pointer to traverse an array, and
   >eliminating the index that it replaces, is the simplest example.)

   A useful technique, indeed (called "strength reduction" in optimising
   compilers, "finite differencing" in transformational programming).

if you compile the following code on a sun3 with -O4,

int a[100];

foo()
{
    int i;
    int sum;
    int max;

    sum = 0;
    max = a[0];
    for (i=0;i<100;i++) {
	sum += a[i];
	if (max < a[i]) max = a[i];
    }
    printf("%d %d\n", sum, max);
}
    
you get the following code:

	.text
	.globl	_foo
_foo:
|#PROLOGUE# 0
	link	a6,#-20
	moveml	#8432,sp@
|#PROLOGUE# 1
	moveq	#0,d5
	movl	_a,d4
	moveq	#0,d6
	movl	#_a,a5
L77003:
	movl	a5@,d7
	addl	d7,d5
	cmpl	d7,d4
	jge	L77005
	movl	d7,d4
L77005:
	addql	#1,d6		<--- increment i
	addqw	#4,a5		<--- increment a magic pointer
	moveq	#100,d7
	cmpl	d7,d6
	jlt	L77003
	movl	d4,sp@-
	movl	d5,sp@-
	pea	L25
	jbsr	_printf
|#PROLOGUE# 2
	moveml	a6@(-20),#8432
	unlk	a6
|#PROLOGUE# 3
	rts
--
I don't think the stories are "apocryphal".  I did it :-)  .. jthomas@nmsu.edu