🚀 go-pugleaf

From article <MISHA.90Nov7191750@just-right.ai.mit.edu>, by misha@ai.mit.edu (Mike Bolotski):
> In article <7659:Nov620:58:5990@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>> pointers (arrays) are pre-indexed appropriately. 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?
> [...]
> Optimal addition is NP.  Halting problem is undecidable (ever).
> You can argue practicality, but not theory.

Besides, the problem under discussion originally wasn't the optimal
addition chain problem anyway.  The original question was whether
there were cases when a pointer _could_ be precomputed but a compiler
_couldn't_ find the same optimization.  So, the issue is this:

   p = expression + &x;         i = expression /* same as pointer version*/
   ...real far away...`         ...real far too...
   a=*p;                        a=x[i]

The only question is "can the compiler promote the add of the base
of array 'x' up to the point where 'i' is precomputed and therefore
get the same efficiency as the precomputed pointer?"  Turns out that
this problem is not even NP, it's O(N^2) for languages which permit
arbitrary GOTOs and it's O(N) for "structured" languages (where all
constructs are guaranteed to be properly nested, etc.).  In both
cases, the number N is the number of 'basic blocks' in the code
to be optimized.  The "liveness" analysis used is required anyway
in order to do compile-time error checking adequately.

Note: even a language with GOTOs can be analyzed in O(NlogN) if the
flow graph is "reducible".  See any good book on compiler construction.

Note2: having pointed out that the optimization is possible, I should
say that it's not always desireable.  If the array 'x' is statically
allocated, many mainframes and minis have address modes which would
do the add in the memory unit for free.  See Aho, Sethi and Ullman's
`dragon' book, chapter 9.  In chapter 10 of the same book, they
work an optimization example where this optimization is possible,
but they don't do it for this very reason.

J. Giles