Path: utzoo!attcan!uunet!fernwood!apple!bionet!agate!shelby!rutgers!cmcl2!kramden.acf.nyu.edu!brnstnd From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.lang.misc Subject: Whether cc after f2c can optimize arrays as well as f77 can Message-ID: <2779:Nov608:20:1990@kramden.acf.nyu.edu> Date: 6 Nov 90 08:20:19 GMT References: <1990Nov2.183359.6761@maths.nott.ac.uk> <4869@lanl.gov> Organization: IR Lines: 110 In article <4869@lanl.gov> jlg@lanl.gov (Jim Giles) writes: > From article <1990Nov2.183359.6761@maths.nott.ac.uk>, by anw@maths.nott.ac.uk (Dr A. N. Walker): > > [...stuff that shows that _sombody_ finally understands what I'm saying...] As you know, I've said the same things before in e-mail, so you don't have to act so amazingly relieved. The crux of this side issue is whether the compiler can optimize possibly aliased functions without asking the programmer. Below I quote an e-mail message from me to you in June, with interpretations for comp.lang.misc readers (who are missing the extensive context of the message). > Exactly the problem I kept trying to point out to someone via private > email (and the reason I don't deal with that person over email any > more - he ignored the point and kept claiming that the compiler by > itself could do all). I admire your productive attitude. ---Dan : From brnstnd Wed Jun 13 00:23:57 1990 : Return-Path: : Received: by stealth.acf.nyu.edu (5.51/25-eef) : id AA00647; Wed, 13 Jun 90 00:23:54 CDT : Date: Wed, 13 Jun 90 00:23:54 CDT : From: Dan Bernstein : Full-Name: Dan Bernstein : Message-Id: <9006130523.AA00647@stealth.acf.nyu.edu> : To: dan, jlg%woodsy@lanl.gov : Subject: Re: aliasing again ... : Status: O : : Gaaaargh. This was after your repeated insistence that proper aliasing analysis could not be performed by the compiler. : [ file1: int a; int b; main() { ... sub(&a); ... } ] : [ file2: extern int a; sub(x) int *x; { ... } ] : [ file3: extern int b; sub(x) int *x; { ... } ] You had just said something like ``file2 and file3 are symmetric with respect to global variables a and b, so aliasing analysis is impossible!'' : The compiler expands file2's sub() into two functions: : : subf(x) int *x; /* possibly */ aliased global, x; { ... } : subg(x) int *x; /* no aliasing allowed */ { ... } : : Similarly for file3. : : The compiler compiles file1's main() into two functions, only one of : which will be used: : : main() /* no aliasing allowed */ { ... subf(x) ... } : : Must I keep explaining? I was getting a little ticked at having to explain the same thing to you so many times, particularly when TCMITS understood exactly what I was saying. Do any readers understand what's going on here? Walker assumed that without outside help, the compiler cannot easily test for interference at run time (let alone compile time), and hence cannot decide which version of the compiled code to execute. But here I'm showing you exactly how it can be done, for the case you care about (array manipulations as in Fortran). : Hopefully this will elicit an ``Oh, now I understand!'' from you. : Presumably you'll continue with ``But it's making the wrong decision for : file3, because file3 can't see a!'' I repeat my original claim: The : compiler can trivially perform a sufficiently good aliasing analysis : that the translation of a Fortran program without aliasing will end up : with the unaliased compiled C code. That's what you're looking for, right? C array manipulations optimized as effectively as those in Fortran? Indeed, in the simplified model above, file3 has to account for aliasing where that aliasing cannot in fact exist. But that can never happen in the translation of a Fortran program. And see below. : To do a better job, of course, you can add more levels between ``all : variables may be aliased'' and ``no variables are aliased.'' For : example: ``Any parameter may be aliased with a.'' ``Any parameter may be : aliased with b.'' And so on. You made some incorrect statements in : comp.lang.misc about the nature of the combinatorial explosion if you : enumerate *all* possibilities; it's actually quite feasible for normal : code. : : The most flexible (and arguably the best) solution is to let the : programmer assert the lack of aliasing between any variables at any : time. Q provides sufficiently general mechanisms for this. As does Nemesis, as you then told me. But that has nothing to do with current real-world languages like C. I still claim that a C compiler can detect and avoid the aliasing problems of a Fortran-converted piece of code at compile time. Please do not pervert my claim into the following: ``A C compiler can detect and avoid all aliasing problems at compile time with no help from the programmer.'' That simply isn't true: pointers in general are much more flexible than Fortran arrays, and some tests simply have to be performed at run time. I agree entirely (and in fact told you in several messages) that the compiler has to get assertions from the programmer if it wants to deal with general aliasing problems properly. ---Dan