Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!rutgers!topaz!klinzhai!webber
From: webber@klinzhai.RUTGERS.EDU (Webber)
Newsgroups: comp.arch
Subject: Re: Optimization vs. the programmer
Message-ID: <184@brandx.klinzhai.RUTGERS.EDU>
Date: Mon, 20-Apr-87 23:10:56 EST
Article-I.D.: brandx.184
Posted: Mon Apr 20 23:10:56 1987
Date-Received: Wed, 22-Apr-87 00:02:03 EST
References: <479@danews.ATT.COM> <3300004@uiucdcsm>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 35
Summary: actually you are both sort of right

In article <3300004@uiucdcsm>, grunwald@uiucdcsm.cs.uiuc.edu writes:
> ...
> As for my definition of ``reduction in strength'' -- this is the defn. as
> put forth in the Dragon book. Then example they give is the PL/I-ish
> 
> 	length(S1 || S2)	-> length(s1) + length(s2)
> 
> In the case where an expression involving a loop iterand is being reduced in
> strength, I think that the term is really induction variable expansion and
> elimination.

``Reduction in strength'' is fairly simple optimization technique named in
the Dragon book (i.e., Aho, Sethi, and Ullman 's ``Compilers:
Principles, Techniques, and Tools'', 1986.  A much more interesting
notion that predates both the Dragon books is ``strength reduction''
(cf., David Gries' text on Compiler Construction).  Here the idea is
to make transformations like:
       for(i=0;i<10;i++) {printf("%d\n",10*i);}
into
       for(j=i=0;i<10;i++,j+=10) {printf("%d\n",j);}
These kinds of things are very important when the program does alot
of multidimensional array accesses, because there is alot of this
sort of thing being generated that the programer is often unaware of
(i.e., it dates back to early efforts to optimize fortran code, such
as the classic fortran H compiler).  It turns out that in section 10.2
of the AhoSethiUllman text, the notion of reduction in strength (that
was originally defined in section 9.9 in the manner of replacements
like  ``x * 2'' becomes ``x + x'') is extended to the for-loop style
optimization that other people study under the name ``strength
reduction''.  Thus, by the end of the book, ``reduction in strength''
means both kinds of optimizations; however, the earlier notion of
``strength reduction'' was generally only applied to the loop-type
optimization.  Hope this clarified things.

-------------- BOB (webber@aramis.rutgers.edu ; BACKBONE!topaz!webber)