Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think.com!snorkelwacker!ai-lab!ai.mit.edu!misha From: misha@ai.mit.edu (Mike Bolotski) Newsgroups: comp.lang.misc Subject: Re: Aggressive optimization Message-ID: <11840@life.ai.mit.edu> Date: 13 Nov 90 14:29:46 GMT References: <5351@lanl.gov> <24232:Nov905:50:0690@kramden.acf.nyu.edu> Sender: news@ai.mit.edu Reply-To: misha@ai.mit.edu Organization: MIT Artificial Intelligence Laboratory Lines: 30 In article <24232:Nov905:50:0690@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: |> In article <5351@lanl.gov> jlg@lanl.gov (Jim Giles) writes: |> |> (Note that I have demonstrated in another article that Mike is wrong.) Yeah, right. |> [ 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? Read a book, Dan. You've chosen to ignore Jim's suggestion of the Aho, Sethi, and Ullman text, *in the very article you quote.* Chapters 9 and 10 should clear up your confusion about reducible flow graphs, conservative vs non-conservative optimizations, and various aspects of aliasing. (Although the rest of the books is also quite informative and would probably save this newsgroup several megabytes of explanations. -- Mike Bolotski Artificial Intelligence Laboratory, MIT misha@ai.mit.edu Cambridge, MA