David B. Loveman
Abstract
The use of source-to-source program transformations has proved valuable in improving program performance. The concept of program manipulation is elucidated by describing its role in both conventional optimization and high level modification of conditional, looping, and procedure structures. An example program fragment written in an Algol-like language is greatly improved by transformations enabled by a user-provided assertion about a data array. A compilation model based on the use of source-to-source program transformations is used to provide a framework for discussing issues of code generation, compilation of high level languages such as APL, and eliminating overhead commonly associated with modular structured programming. Application of the compilation model to several different languages is discussed.
- 1 ABRAMS, P An APL machine, SU-SEL-70-017, Stanford Electron Lab Stanford, Cahf, Feb. 1970Google Scholar
- 2 ACM SIGPLAN Symposmm on very high level languages SIGPLAN Nouces (ACM) 9, 4 (April 1974)Google Scholar
- 3 ACM SIGPLAN. Proceedings of a symposmm on compder optimization. SIGPLAN Nouces (ACM) 5, 7 (July 1970)Google Scholar
- 4 ALLEN, F.E., AND COCKE, J A catalogue of opUmlzlng transformations In Destgn and Opttmtzatton of Compilers, R Rustm, Ed , Prentice-Hall, Englewood Cliffs, N J , 1972, pp 1-30Google Scholar
- 5 BeatRisro, D, ANO SArrERLY, K BETA laboratory Final Rep CADD-7312-3111, Mass Computer Associates, Inc, Wakefield, Mass., Dec 1973Google Scholar
- 6 BURSTALL, R M, AND DARLINGTON, J A transformation system for developing recurswe programs J ACM 24, 1 (Jan 1977), 44-67 (this issue) Google Scholar
- 7 CARTER, J L A case study of a new compdlng code generation techmque RC 5666, IBM Thomas J Watson Res Ctr, Yorktown Heights, N Y, Oct 1975Google Scholar
- 8 CItEATHAM, T.E., AND TOWNLEY. J A Symbohc evaluation of programs-a look at loop analysis Proc 1976 ACM Syrup on Symbohc and Algebraic Comput, Aug 1976, pp 90-96 Google Scholar
- 9 CHEATHAM, T E, Arid WEGaREIT, B A laboratory for the study of automatic programming Proc. AFIPS 1972 SJCC, Vol 40, AFIPS Press, Montvale, N J , pp 11-21.Google Scholar
- 10 Gt~RHARr, S L Correctness-preserving program transformations Conf. Rec Second ACM Syrup on Principles of Programming Languages, Jan 1975. pp 54-66. Google Scholar
- 11 GESCHKE, C M Global program optlmlzauons Ph D Th , Comptr Scl Dep , Carnegie-Mellon U , Pittsburgh, Pa, 1972Google Scholar
- 12 HOARd, C A R Hints on programming language design STAN-CS-73-403, Comptr Sc~ Dep, Stanford U, Stanford, Cahf, Dec 1973 Google Scholar
- 13 I~GALLS. D The execution tame profile as a programming tool In Design and Optzmzzatton of Comptlers, R Rustm, Ed , Prent,ce-Hall, Englewood Chffs, N J , 1972, pp. 107-128Google Scholar
- 14 KARR~ M Gathering mformat~on about programs CA-7507-1411, Mass Computer Associates, Inc, Wakefield, Mass , July 1975Google Scholar
- 15 KAttR, M On affine relationships among variables of a program Acta InformaOca 6, 2 (1976), 133-152Google Scholar
- 16 KNuxH, D Structured programming with goto statements Computing Surveys 6, 4 (Dec 1974), 261- 301 Google Scholar
- 17 LAMPORT, L Parallel execution on array and vector computers Proc 1975 Sagamore Conf. on Parallel Processing, Syracuse U , Aug 1975, pp 187-191Google Scholar
- 18 LA~POt~a~, L The parallel execution of DO loops. Comm A CM 17, 2 (Feb 1974), 83-93 Google Scholar
- 19 LOVEMAN, D An ATE language processing system Autotestcon 76 Formally Automat,c Support Systems for Advanced Mamtamabd~ty, IEEE, New York, 1976, pp 1-9Google Scholar
- 20 LOVEMAN, D , AND FANEUF, R Program optimization--theory and practice Proc Conf. on Programmmg Languages and Compilers for Parallel and Vector Machines SIGPLAN Nouces (ACM) 10, 3 (March I975), 97-102 Google Scholar
- 21 PRESBERG, D , AND JOHNSON, N The paralyzer IVTRAN's parallehsm analyzer and synthesizer Proc Conf on Programming Languages and Compilers for Parallel and Vector Machines. SIGPLAN Notices (ACM) 10, 3 (March 1975), 9-16 Google Scholar
- 22 SCHAEFER, M A Mathematical Theory of Global Program Opttmtzatton Prentice-Hall, Englewood Cliffs, N J , 1973 Google Scholar
- 23 SCHNECK, P B , AND ANGEL, E A FORTRAN to FORTRAN optimizing compiler Computer J 16, 4 (Nov 1973), 322-330Google Scholar
- 24 SHAPIRO, R M , AND SAINT, H The representation of algorithms Final Tech. Rep RADC-TR-69-313, Applied Data Research, Inc , Vol II, Rome Air Develop Ctr., Sept 1969Google Scholar
- 25 STANDISH, T A, I-tARRIMAN, D C, KIBLER, D F, AND NEIGHBORS, J M Improving and refimng programs by program manipulation Proceedings 1976 ACM Annual Cont , Oct. 20-22, 1976, pp 509- 516 Google Scholar
- 26 STANOISH, T, HARRIMAN, D, KIBLER, D, AND NEIGHBORS, J The Irvlne program transformation catalogue Dep Inform and Cornptr Scl , U of California at Irvlne, Irvlne, Cahf, Jan 1976Google Scholar
- 27 VANTASSEL, D Program Style, Design Efficmncy, Debugging and Testing Prentice-Hall, Englewood Chffs. N J , 1974Google Scholar
- 28 WEGBREIT, B Goal-directed program transformation IEEE Trans on Software Eng SE-2, 2 (June 1976), 69-80Google Scholar
- 29 WEGBREIT, B Property extraction in well-founded property sets IEEE Trans on Software Eng SE-1, 3 (Sept. I975), 270-285 Google Scholar
- 30 WEGBRE1T, B The ECL programming system Proc AFIPS FJCC, Vol 39, AFIPS Press, Montvale, N J, 253-262 Google Scholar
- 31 WULF, W.A , RUSSELL, D.B , AND HABERMANN, A M BLISS a language for systems programming Comm ACM 14, 12 (Dec 1971), 780-790 Google Scholar
Index Terms
- Program Improvement by Source-to-Source Transformation
Recommendations
Program improvement by source to source transformation
POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languagesWe treat a program as an object of manipulation, determine items of program constancy, and simplify the program based on the constancy. Some motivation for program manipulation is presented, along with two examples of “higher level optimization” written ...
Source-to-Source Compilation via Submodules
ELS2016: Proceedings of the 9th European Lisp Symposium on European Lisp SymposiumRacket's macro system enables language extension and definition primarily for programs that are run on the Racket virtual machine, but macro facilities are also useful for implementing languages and compilers that target different platforms. Even when ...
Mixing source and bytecode: a case for compilation by normalization
Language extensions increase programmer productivity by providing concise, often domain-specific syntax, and support for static verification of correctness, security, and style constraints. Language extensions can often be realized through translation ...
Comments