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: <5351@lanl.gov> Date: 8 Nov 90 19:59:15 GMT References: Organization: Los Alamos Natl Lab, Los Alamos, N.M. Lines: 40 From article , 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