Code generation using tree matching and dynamic programming

ABSTRACT

Compiler-component generators, such as lexical analyzer generators and parser generators, have long been used to facilitate the construction of compilers. A tree-manipulation language called twig has been developed to help construct efficient code generators. Twig transforms a tree-translation scheme into a code generator that combines a fast top-down tree-pattern matching algorithm with dynamic programming. Twig has been used to specify and construct code generators for several experimental compilers targeted for different machines.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
	2	Alfred V. Aho , Mahadevan Ganapathi, Efficient tree pattern matching (extended abstract): an aid to code generation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.334-340, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318663]
	3	A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
	4	A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
	5	A. V. Aho , S. C. Johnson , J. D. Ullman, Code-generation for machines with multiregister operations, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512953]
	6	A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975 [doi>10.1145/360933.360969]
	7	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	8	Philippe Aigrain , Susan L. Graham , Robert R. Henry , Marshall Kirk McKusick , Eduardo Pelegri-Llopart, Experience with a Graham-Glanville style code generator, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.13-24, June 17-22, 1984, Montreal, Canada
	9	APPEL, A.W. Concise specifications of locally optimal code generators. Tech. Rep. CS-TR-080- 87, Dept. of Computer Science, Princeton University, Princeton, N.J., Feb. 1987.
	10	John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976 [doi>10.1145/321958.321971]
	11	R. G. Cattell, Automatic Derivation of Code Generators from Machine Descriptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.173-190, April 1980 [doi>10.1145/357094.357097]
	12	CHOW, P., AND HOROWITZ, M. The MIPS-X microprocessor. In Proceedings of Wescon 1985 (San Francisco, Nov. 19-21, 1985). IEEE, New York, sec. 6-1, pp. 1-6.
	13	Jack W. Davidson , Christopher W. Fraser, Code selection through object code optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.505-526, Oct. 1984 [doi>10.1145/1780.1783]
	14	Peter Dencker , Karl Dürre , Johannes Heuft, Optimization of parser tables for portable compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.546-572, Oct. 1984 [doi>10.1145/1780.1802]
	15	Christopher Warwick Fraser, Automatic generation of code generators., 1977
	16	Christopher W. Fraser , Alan L. Wendt, Integrating code generation and optimization, ACM SIGPLAN Notices, v.21 n.7, p.242-248, July 1986
	17	Mahadevan Ganapathi , Charles N. Fischer, Affix grammar driven code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.560-599, Oct. 1985 [doi>10.1145/4472.4486]
	18	Mahadevan Ganapathi , Charles N. Fischer, Attributed linear intermediate representations for retargetable code generators, Software—Practice & Experience, v.14 n.4, p.347-364, April 1984 [doi>10.1002/spe.4380140406]
	19	Mahadevan Ganapathi , Charles N. Fischer, Description-driven code generation using attribute grammars, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.108-119, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582165]
	20	M. Ganapathi , C. N. Fischer, Integrating code generation and peephole optimization, Acta Informatica, v.25 n.1, p.85-109, January 1988 [doi>10.1007/BF00268846]
	21	Mahadevan Ganapathi , Charles N. Fischer , John L. Hennessy, Retargetable Compiler Code Generation, ACM Computing Surveys (CSUR), v.14 n.4, p.573-592, Dec. 1982 [doi>10.1145/356893.356897]
	22	Robert Steven Glanville, A machine independent algorithm for code generation and its use in retargetable compilers., 1977
	23	R. Steven Glanville , Susan L. Graham, A new method for compiler code generation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.231-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512785]
	24	Ingrid Glasner , Ulrich Möncke , Reinhard Wilhelm, OPTRAN, a Language for the Specification of Program Transformations, Programmiersprachen und Programmentwicklung, 6. Fachtagung des Fachausschusses Programmiersprachen der GI, p.125-142, March 11-12, 1980
	25	GRAHAM, S.L. Table-driven code generation. IEEE Comput. 13, 8 (Aug. 1980), 25-34.
	26	Susan L. Graham , Robert R. Henry , Robert A. Schulman, An experiment in table driven code generation, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.32-43, June 23-25, 1982, Boston, Massachusetts, United States
	27	Philip J. Hatcher , Thomas W. Christopher, High-quality code generation via bottom-up tree pattern matching, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.119-130, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512655]
	28	Thomas W. Christopher , Philip J. Hatcher , Ronald C. Kukuk, Using dynamic programming to generate optimized code in a Graham-Glanville style code generator, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.25-36, June 17-22, 1984, Montreal, Canada
	29	Robert Rettig Henry, Graham/glanville code generators (compiler, parser, programming language), 1984
	30	Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
	31	HUET, G., AND LEVY, J.-J. Call by need computations ill non-ambiguous linear term rewriting systems. Tech. Rep. 359, IRIA Laboria, LeChesnay, France, 1979.
	32	S. C. Johnson, A portable compiler: theory and practice, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-104, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512771]
	33	K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
	34	K. Keutzer , W. Wolf, Anatomy of a hardware compiler, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.95-104, June 20-24, 1988, Atlanta, Georgia, United States
	35	Hans Hermann Kron, Tree templates and subtree transformational grammars., 1975
	36	LANG, H.-W., SCHIMMLER, M., AND SCHMECK, H. Me tching tree patterns sublinear on the average. Tech. Rep. Dept. of Informatik, University of Kisl, Kiel, West Germany, 1980.
	37	LUNELL, H. Code Generator Writing Systems. Software Systems Research Center, S-58183, Linkoping, Sweden, 1983.
	38	E. Pelegrí-Llopart , S. L. Graham, Optimal code generation for expression trees: an application BURS theory, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.294-308, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73586]
	39	RIPKEN, K. Formale Beschreibun von Maschinen, Implementierungen und Optimierender Maschinen-codeerzeugung aus Attributierten Programml,~raphe. Tech. Rep. TUM-INFO-7731, Institut fur Informatik, Technische Universitat Munchen, Munich, West Germany, July 1977.
	40	Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
	41	SNYDER, L. Recognition and selection of idioms for code optimization. Acta Inf. 17 (1982), 327-348.
	42	TJIANG, S. W. K. Twig reference manual. Computing Science Tech. Rep. 120, AT&T Bell Laboratories, Murray Hill, N.J., 1985.
	43	Stephen Gibbs Wasilew, A compiler writing system with optimization capabilities for complex object order structures, 1972
	44	Steven William Weingart, An efficient and systematic method of compiler code-generation., 1973
	45	WULF, W.A. PQCC: A machine-relative compiler technology. In Proceedings of the IEEE 4th International COMPSAC Conference. IEEE, New York, 1980, pp. 24-36.
	46	WULF, W., LEVERETT, B., CATTELL, R., HOBBS, S., NEV~ COMER, J., REINER, A., AND SCHATZ, B. An overview of the production quality compiler-compiler project. IEEE Comput. 13, 8 (Aug. 1980), 38-49.