Chaining Span-Dependent Jump Instructions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Chaining Span-Dependent Jump Instructions

Full text

Pdf (1.02 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 2 , Issue 3 (July 1980) table of contents

Pages: 274 - 289

Year of Publication: 1980

ISSN:0164-0925

Authors

Bruce W. Leverett	Carnegie-Mellon University, Pittsburgh, PA
Thomas G. Szymanski	Bell Laboratories, Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 37, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/357103.357105 What is a DOI?

ABSTRACT

The assembled length of a span-dependent jump instruction depends on the distance between the instruction and its target. Such instructions are found on many computers and typically have two forms, long and short. We consider the problem of minimizing object program length for such machines by chaining together jumps with the same target. Although the problem is NP-complete in its most general form, several mildly restricted forms of the problem exist that are of practical importance and have efficient solutions.

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 , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	GAREY, M.R., AND JOHNSON, D.S. Computers and Intractability. W. H. Freeman, San Francisco, Calif., 1979.
	3	KARP, R.M. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher (Eds.), Complexity of Computer Computations. Plenum Press, New York, 1972.
	4	REISER, J.F. Common instances of pathological span-dependent instructions. Internal Memo., Bell Labs., Holmdel, N.J.
	5	Edward L. Robertson, Code Generation and Storage Allocation for Machines with Span-Dependent Instructions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.71-83, July 1979 [doi>10.1145/357062.357067]
	6	Thomas G. Szymanski, Assembling code for machines with span-dependent instructions, Communications of the ACM, v.21 n.4, p.300-308, April 1978 [doi>10.1145/359460.359474]
	7	WILLIAMS, M.H. Long/short address optimization in assemblers. Softw. Pract. Exper. 9 (1979), 227-235.
	8	William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975

CITED BY 5

	Peter L. Bird, An implementation of a code generator specification language for table driven code generators, ACM SIGPLAN Notices, v.17 n.6, p.44-55, June 1982
	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
	Rodney A. Brooks , David B. Posner , James L. McDonald , Jon L. White , Eric Benson , Richard P. Gabriel, Design of an optimizing, dynamically retargetable compiler for common Lisp, Proceedings of the 1986 ACM conference on LISP and functional programming, p.67-85, August 1986, Cambridge, Massachusetts, United States
	Robert Giegerich, A Formal Framework for the Derivation of Machine-Specific Optimizers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.478-498, July 1983
	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