oz@yunexus.UUCP (Ozan Yigit) (04/12/90)
In article <14319@lambda.UUCP> jlg@lambda.UUCP (Jim Giles) writes: >.......... Arrays can be optimized as well as pointers >can, but the reverse is not true without expensive (and rare) global >data flow analysis on the interprocedural level. So what ? There exists C compilers that will match, in optimization power, anything else out there. [Dec, had in fact, published a comparison with BLISS few years back.] The so called "expensive" optimizations are not even outside the realm of publicly available, free compilers. What matters in practice may or may not be related at all to your latest pet issue, or your straw-man. > >The only implementation >so far proposed (on the net anyway) which does interprocedual data >flow analysis in this way has the _loader_ do code generation. Phew. Required reading from a recently posted biblio (the whole thing is too large to post again): Alias Detection [ ] B. Alpern, M. Wegman, and F. Zadeck,, "Detecting equality of variables in programs," in Fifteenth POPL, January 1988. [ ] Keith D. Cooper, "Analyzing Aliases of Reference Formal Parame- ters," Conference Record of the Twelfth POPL, ACM SIGACT SIG- PLAN, January 1985, pp. 281-290. [ ] S. Horwitz, P. Pfeiffer, and T. Reps, "Dependence Analysis for Pointer Variables," Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, 21-23 June 1989, pp. 28-40. In ACM SIGPLAN Notices 24:7 (July 1989). [ ] Anne Denise Neyrinck, "Static Analysis of Aliases and Side Effects in Higher-Order Languages," 88-896, Cornell University, Department of Computer Science, Ithaca, NY 14853-7501, February 1988. Ph.D. Thesis. January 1988 is also given as a date.. [ ] W. Weihl, "Interprocedural Data Flow Analysis in the Presence of Pointers, Procedure Variables, and Label Variables," Proceedings of the 7th Symposium on Principles of Programming Languages, January 1980, pp. 83-94. Interprocedural Optimization [ ] F. E. Allen, "Interprocedural Data Flow Analysis," Proceedins of IFIP Congress 74, North-Holland (1974), pp. 398-402. [ ] J. Ball, "Predicting the effects of optimization on a procedure body," in SIGPLAN Compiler Construction Conference, August 1979. [ ] M. Burke and R. Cytron, "Interprocedural Dependence Analysis and Parallelization," Proceedings of the SIGPLAN'86 Symposium on Compiler Construction, ACM, Jul 1986, pp. 162-175. [ ] Michael Burke, "An Interval-Based Approach to Exhaustive and Incremental Interprocedural Data Flow Analysis," 12702 (#56865), Computer Science Department, IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, 1 September 1987. [ ] D. Callahan, K. D. Cooper,, K. Kennedy, and L. Torczon, "Inter- procedural Constant Propagation," pp. 152-161 in ACM SIGPLAN 86 Symposium on Compiler Construction, June 1986. [ ] D. Callahan and K. Kennedy,, "Analysis of Interprocedural Side Effects in a Parallel Programming Environment," in Proceedings of the First International Conference on Supercomputing, 1987. [ ] K. D. Cooper, K. Kennedy, and L. Torczon, "The Impact of Inter- procedural Analysis and Optimization on the Design of a Software Development Environment," Proceedings of the ACM SIG- PLAN 85 Symposium on Language Issues in Programming Environ- ments, Seattle, Washington, 25-28 June 1985. In ACM SIGPLAN Notices 20:7 (July 1985). [ ] K. D. Cooper, K. Kennedy, and L. Torczon, "Interprocedural Optimization: Eliminating Unnecessary Recompilation," Proceed- ing of the SIGPLAN '86 Symposium on Compiler Construction, 25- 27 June 1986, pp. 58-67. In ACM SIGPLAN Notices 21:7 (July 1986). [ ] K. Cooper and K. Kennedy, "Efficient Computation of Flow Insen- sitive Interprocedural Summary Information," pp. 247-258 in ACM SIGPLAN 84 Symposium on Compiler Construction, June 1984. [ ] K. Cooper, K. Kennedy, and L. Torczon, "The Impact of Interpro- cedure Analysis and Optimization in the Rn Programming Environ- ment," ACM TOPLAS 8:4 (October 1986), pp. 491-523. [ ] Keith D. Cooper and Ken Kennedy, "Interprocedural Side-Effect Analysis in Linear Time," SIGPLAN Notices: Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Imple- mentation 23:7, ACM (July 1988), pp. 57-66. [ ] Susan Horwitz, Thomas Reps, and David Binkley, "Interprocedural Slicing Using Dependence Graphs," SIGPLAN Notices: Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation 23:7, ACM (July 1988), pp. 35-46. [ ] Christopher Alan Huson, "An In-Line Subroutine Expander for Parafrase," Rpt. No. 82-1118, Univ. of Illinois at Urbana- Champaign, Dept. of Computer Sci., Dec., 1982. [ ] Zhiyuan Li and Pen-Chung Yew, "Interprocedural Analysis and Program Restructuring for Parallel Programs," CSRD Report No. 720, Univ. of Illinois at Urbana-Champaign, Center for Super- computing Res. & Dev.. [ ] Zhiyuan Li and Pen-Chung Yew, "Interprocedural Analysis for Parallel Programs," Proc. of 1988 Int'l. Conf. on Parallel Pro- cessing, St. Charles, IL, August 1988. [ ] Zhiyuan Li and Pen-Chung Yew, "Efficient Interprocedural Analysis for Program Parallelization and Restructuring.," SIG- PLAN Notices 23:9, ACM Press (September 1988), pp. 85-99. Proceedings of the ACM/SIGPLAN PPEALS 1988, July 19-21 1988. [ ] Etienne Morel and Claude Renvoise, "Interprocedural Elimination of Partial Redundancies," pp. 160-188 in Program Flow Analysis, ed. Neil D. Jones, Prentice Hall, 1981. [ ] S. Richardson and M. Ganapathi, "Interprocedural Analysis - A Bibliography," ACM SIGPLAN Notices 22:6 (June 1987), pp. 12-17. [ ] S. Richardson and M. Ganapathi , "Code Optimization Across Procedures ," Computer 22:2 (February 1989), pp. 42-50 . [ ] Barbara G. Ryder, "A Survey of Interprocedural Data Flow Analysis Techniques," DCS-TR-85, Rutgers, Dec 1979. [ ] R. Scheifler, "An analysis of inline substitution for a struc- tured programming language," CACM 20:9 (Sept. 1977.). [ ] Micha Sharir and Amir Pnueli, "Two Approaches to Interpro- cedural Data Flow Analysis," pp. 189-233 in Program Flow Analysis, ed. Neil D. Jones, Prentice Hall, 1981. [ ] Remi Triolet, "Interprocedural Analysis for Program Restructur- ing with Parafrase," CSRD Rpt. No. 538, Univ. of Illinois at Urbana-Champaign, Center for Supercomputing Res. & Dev., Aug., 1986. Register Allocation [ ] J. C. Beatty, "Register Assignment Algorithm for Generation of Highly Optimized Object Code," IBM J. Res. Devel, , pp. 20-39. [ ] J. C. Beatty, "A Global Register Assigment Algorithm," pp. 65- 68 in Design and Optimization of Compilers, ed. R. Rustin, Prentice-Hall, 1972. [ ] D. Bernstein, M. Golumbic, Y. Mansour, R. Pinter, D. Goldin, H. Drawczyk, and I. Nahshon, "Spill Code Minimization Techniques for Optimizing Compilers," Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, 21-23 June 1989, pp. 258-263. In ACM SIGPLAN Notices 24:7 (July 1989). [ ] P. Briggs, K. D. Cooper, K. Kennedy, and L. Torczon, "Coloring Heuristics for Register Allocation," Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementa- tion, 21-23 June 1989, pp. 275-284. In ACM SIGPLAN Notices 24:7 (July 1989). [ ] C.-H. Chi and H. Dietz, "Unified Management of Registers and Cache Using Liveness and Cache Bypass," Proceedings of the SIG- PLAN '89 Conference on Programming Language Design and Imple- mentation, 21-23 June 1989, pp. 344-355. In ACM SIGPLAN Notices 24:7 (July 1989). [ ] Fred C. Chow, "Minimizing Register Usage Penalty at Procedure Calls," SIGPLAN Notices: Proceedings of the SIGPLAN'88 Confer- ence on Programming Language Design and Implementation 23:7, ACM (July 1988). [ ] R. Gupta, M. L. Soffa, and T. Steele, "Register Allocation Via Clique Separators," Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, 21-23 June 1989, pp. 264-274. In ACM SIGPLAN Notices 24:7 (July 1989). [ ] W. C. Hsu, C. N. Fischer, and J. R. Goodman, "On the Minimiza- tion of Loads and Stores in Local Register Allocation," IEEE Transactions on Software Engineering 15:10 (October 1989), pp. 1252-1260. [ ] P. A. Karger, "Using Registers to Optimize Cross-Domain Call Performance," Proceedings of the Third International Conference on Architectural Support for Programming Languages and Operat- ing Systems (ASPLOS III), 3-6 April 1989, pp. 194-204. [ ] D. Wall, "Global register allocation at link time," in SIGPLAN Compiler Construction Conf, June 1986.. -- The king: If there's no meaning Interned: oz@nexus.yorku.ca in it, that saves a world of trouble ......!uunet!utai!yunexus!oz you know, as we needn't try to find any. Bitnet: oz@[yulibra|yuyetti] Lewis Carroll (Alice in Wonderland)