Path: utzoo!attcan!uunet!lll-winken!sun-barr!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!unmvax!ariel.unm.edu!nmsu!opus!ted From: ted@nmsu.edu (Ted Dunning) Newsgroups: comp.lang.misc Subject: Re: Aggressive optimization Message-ID: Date: 26 Oct 90 18:46:14 GMT References: <65697@lanl.gov> <1458@exodus.Eng.Sun.COM> <13405:Oct1800:22:5690@kramden.acf.nyu.edu> <2301@wn1.sci.kun.nl> Sender: news@NMSU.Edu Organization: NMSU Computer Science Lines: 69 In-reply-to: eerke@cs.kun.nl's message of 18 Oct 90 09:38:29 GMT 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