preston@titan.rice.edu (Preston Briggs) (04/12/90)
In article <14326@lambda.UUCP> jlg@lambda.UUCP (Jim Giles) writes: >But, I don't see >how you can to interprocedural analysis where separate compilation is >involved. Separate compilation implies that the compiler is completely >unaware of the content of procedures other than the one currently >being compiled. Well, the scheme proposed by Cooper, Kennedy, and Torczon bends your definition of separate compilation a little and I expect the new ideas won't make everyone happy. The hope is that the ends justify the means. The local doctrine is something like this: Interprocedural analysis is divided into 3 parts, 1) a local summary analysis of each procedure 2) a global pass, constructing the call graph and solving the various data flow problems over the call graph 3) local compilation and optimization, using the results of 2 The division of labor is such that (1) is run once per change. That is, when a procedure has been edited and we do a make, then we need to examine the changed procedure but no others. (2) is re-run if any procedure changes, but is able to run without examining the code for the procedures. Instead, it uses the local information produced by (1). (3) needs to run on a procedure if it has been changed, or if the interprocedural information used by an earlier (3) has been invalidated. (For example, an earlier analysis might have determined there was no aliasing for a procedure zap. If aliases are introduced somewhere up the call chain, zap must be recompiled. On the other hand, if the aliases are later removed, zap need not be recompiled to remain correct. The recompilation question is interesting and complex and will be covered in a forthcoming TOPLAS paper.) The information supplied to (3) includes: at a procedure entrance, for each argument, all arguments and globals that might be aliased at a call site, a list of all the variables that might be modified, and a list of all variables that might be referenced. Implementing all this is interesting. A minimalist approach might use 3 tools as described above, all controlled by make. At Rice, we've built a programming environment incorporating these ideas. The function of (1) is incorporated into the editor which spies upon the user as he types, and records information about variables referenced and modified and about procedure calls. It also does scanning, parsing, and error checking. (2) works about as described. (3) is invoked by (2) when necessary and most resembles a normal optimizing compiler, though with a simplified front-end (no scanning, parsing, or error reporting). A big consequence is that the system needs access to all the source. Object libraries might be difficult, though interprocedural summary information could be provided and used effectively. It isn't necessary that (3) be done with a special compiler; in fact, we used f77 for years and still use it on occasion. So, ... Not totally convenient and not totally suitable for all uses, but still a way to accomplish interprocedural analysis in a timely fashion while allowing (some sort of) separate compilation. -- Preston Briggs looking for the great leap forward preston@titan.rice.edu
jlg@lambda.UUCP (Jim Giles) (04/12/90)
From article <6563@brazos.Rice.edu>, by preston@titan.rice.edu (Preston Briggs): > [...] > A big consequence is that the system needs access to all the source. That could be the major problem. Vendors are not usually keen to give out source code. They are perfectly willing to give out relocatable libraries but not source. This means that your steps 2&3 need to be done by the end user. How does this differ from having the loader do it? J. Giles
preston@titan.rice.edu (Preston Briggs) (04/12/90)
In article <14337@lambda.UUCP> jlg@lambda.UUCP (Jim Giles) writes: >From article <6563@brazos.Rice.edu>, by preston@titan.rice.edu (Preston Briggs): >> A big consequence is that the system needs access to all the source. >That could be the major problem. Vendors are not usually keen to give out >source code. They are perfectly willing to give out relocatable libraries >but not source. This means that your steps 2&3 need to be done by the >end user. How does this differ from having the loader do it? Actually, Floating Point Systems has taken the very polite step of releasing all the source to all their math libraries, I believe for free and with minimal liscencing. Additionally, there's all the linpack and blas source avaliable. Perhaps it's not such a big problem. At any rate, I can imagine a few ad-hoc solutions. Vendors could supply object libraries that were compiled using no interprocedural info. If they included the necessary summary info for each routine, then step 2 (the interprocedural analysis) and step 3 (the compilations) could proceed normally and with respectable levels of optimization. With no aliasing, this is better than current practise. Adiitionally, the analysis could detect aliasing violations in the source. If we care to allow aliasing, then they might provide 2 versions, one assuming no aliasing and one assuming the worst. Then step 2 could determine which version needs to be linked in. A more practical solution (perhaps) would be to provide the libraries in an intermediate form, rather than source or object. Then we could use step 3 to finish the compilation, using the interprocedural info to produce a properly optimized version. Regarding the load time question, I barely remember the original posting. It suggested this was a scheme that Tera was planning to use. I expect the rumor is a distortion, and the likely truth is that Tera will use a scheme similar to what I outlined in my earlier posting. Why? Some of their compiler people contributed to this work while at Rice and I would expect them to continue in the same vein. Why? They want to build fast machines and good optimization is important to them. Naturally, being the vendor, they won't have troubles with source restrictions! Cray's compilers already produce a lot of the required information for other reasons. It's not that much work to take the extra steps. Convex is supposed to be building such a compiler. Push on your vendor; the necessary theory has been provided and examples have been built. It's time to see some better compilers:-) -- Preston Briggs looking for the great leap forward preston@titan.rice.edu