Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Aggressive optimization
Message-ID: <5094@lanl.gov>
Date: 6 Nov 90 22:09:45 GMT
References: <7659:Nov620:58:5990@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 22

From article <7659:Nov620:58:5990@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> [...]                                            Could one of you CS
> types please illustrate to Jim that finding optimal addition chains in a
> general computation is equivalent to solving the halting problem?

Could anyone in Dan's immediate neighborhood please go over to his
place and explain what a data dependency graph is?  This is one
of the most stable and reliable tools available in the compiler
generator's kit.  It allows one to trace the use of an array index
right back to the place where the index was calculated.  Or, failing
that, to the place where the index came into the present context
(a procedure argument, for example).  In either case, the compiler can
clearly place the add of the array base to that index at _exactly_
the place where the index becomes a "live" value.  Or, the compiler
can do the add of the array base at any intervening point in the
control flow graph (also an extremely stable and reliable part of
the compiler writer's art).  If the array index becomes a "live'
value before the array reference (that is, the index is precomputed),
then the whole reference address can be precomputed by the compiler
exactly there.

J. Giles