🚀 go-pugleaf

In article <5351@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> 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.

(Note that I have demonstrated in another article that Mike is wrong.)

> 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]

That's exactly what I'm talking about! The i's and j's and other
integers used to index the arrays are *added* together. The program
could have x[i + j - 17] and lots of other weird expressions, all
evaluated conditionally through the control structure of the program.
But I didn't need even this in my undecidability proof: all I needed was
x[0], x[1], and control flow.

  [ Jim waxes prolific: ]
> 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

I simply don't understand where you and Mike are getting this ridiculous
assertions from. What problems are you fantasizing you've solved here?
Where are your purported proofs?

> 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.

Good point. All the problems, reappear, though, as soon as you have more
than one addition. In x[i + 1], do you precompute *x + 1? Or *x + i? Or
the whole thing? Or maybe *x + j, because x[j] is referenced a lot more?

---Dan