Postpass Code Optimization of Pipeline Constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Postpass Code Optimization of Pipeline Constraints

Full text

Pdf (1.67 MB)

Source

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

Pages: 422 - 448

Year of Publication: 1983

ISSN:0164-0925

Authors

John L. Hennessy	Computer Systems Laboratory, Departments of Electrical Engineering and Computer Science, Stanford University, Stanford, CA
Thomas Gross	Computer Systems Laboratory, Departments of Electrical Engineering and Computer Science, Stanford University, Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 62, Citation Count: 81

Additional Information:

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/2166.357217 What is a DOI?

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	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]
	2	Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
	3	ALLEN, F.E., AND COCKE, J. A catalogue of optimizing transformations, in Design and Optimization of Compilers, R. Rustin (Ed.). Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 1-30.
	4	ANDERSON, D.W., SPARACIO, F.J., AND TOMASULO, R.M. The IBM System/360 Model 91: Machine philosophy and instruction handling. IBM J. Res. Dev. 11, 1 (Jan. 1967), 8-24.
	5	Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
	6	BASKETT, F. Puzzle: An informal compute bound benchmark. Unpublished.
	7	James C. Beatty, An axiomatic approach to code optimization for expressions, Journal of the ACM (JACM), v.19 n.4, p.613-640, Oct. 1972 [doi>10.1145/321724.321728]
	8	DAVIDSON, S., LANDSKOV, D., SHRIVER, B.D., AND MALLETT, P.W. Some experiments in local microcode compaction for horizontal machines. IEEE Trans. Comput. C-30, 7 (July 1981), 460-477.
	9	DAVIES, K., ANO RIs, F. Real-time signal processor support software. IBM J. Res. Dev. 26, 4 (July 1982), 431-439.
	10	Peter J. Denning, ACM president's letter: computer architecture: some old ideas that haven't quite made it yet, Communications of the ACM, v.24 n.9, p.553-554, Sept. 1981 [doi>10.1145/358746.358747]
	11	FISHER, J.A. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7 (July 1981), 478-490.
	12	FISHER, J.A. The optimization of horizontal microcode within and beyond basic blocks. Tech. Rep. COO-3077-161, Courant Mathematics and Computing Laboratory, New York Univ., New York, Oct. 1979.
	13	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	14	John Hennessy, Symbolic Debugging of Optimized Code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.323-344, July 1982 [doi>10.1145/357172.357173]
	15	John L. Hennessy , Thomas R. Gross, Code generation and reorganization in the presence of pipeline constraints, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.120-127, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582166]
	16	HENNESSY, J.L., JouPPI, N., GILL, J., BASKETT, F., STRONG, A., GROSS, T.R., ROWEN, C., AND LEONARD, J. The MIPS machine. In Proceedings, IEEE Compcon, San Francisco, Feb. 1982, pp. 2-7.
	17	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]
	18	KOGGE, P.M. The Architecture of Pipelined Computers. McGraw-Hill, New York, 1981.
	19	LAMPSON, B.W., MCDANIEL, G.A., AND ORNSTEIN, S.M. An instruction fetch unit for a high performance personal computer. Tech. Rep. CSL-81-1, Xerox PARC, Palo Alto, Calif., Jan. 1981.
	20	David A. Patterson , David R. Ditzel, The case for the reduced instruction set computer, ACM SIGARCH Computer Architecture News, v.8 n.6, p.25-33, October 1980 [doi>10.1145/641914.641917]
	21	David A. Patterson , Carlo H. Sequin, RISC I: A Reduced Instruction Set VLSI Computer, Proceedings of the 8th annual symposium on Computer Architecture, p.443-457, May 12-14, 1981, Minneapolis, Minnesota, United States
	22	George Radin, The 801 minicomputer, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.39-47, March 01-03, 1982, Palo Alto, California, United States
	23	James W. Rymarczyk, Coding guidelines for pipelined processors, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.12-19, March 01-03, 1982, Palo Alto, California, United States
	24	SITES, R. Instruction ordering for the Cray-1 computer. Tech. Rep. 78-CS-023, Dept. of Computer Science, Univ. of California, San Diego, July 1978.
	25	TOKORO, M., TAMURA, E., AND TAKIZUKA, T. Optimization of microprograms. IEEE Trans. Comput. C-30, 7 (July 1981), 491-504.
	26	ULLMAN, J.D. Complexity of sequencing problems. In Computer and Job-Shop Scheduling Theory, E.G. Coffman, Jr. (Ed.). Wiley, New York, 1976, pp. 139-164.
	27	ULLMAN, J.D. NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 3 (June 1975), 384-393.
	28	Steven R. Vegdahl, Phase coupling and constant generation in an optimizing microcode compiler, Proceedings of the 15th annual workshop on Microprogramming, p.125-133, October 05-07, 1982, Palo Alto, California, United States
	29	WIDOOES, L.C. The S-1 project: Developing high performance digital computers. In Proceedings, IEEE Compcon, San Francisco, Feb. 1980, pp. 282-291.
	30	WULF, W.A. Compilers and computer architecture. Computer 14, 7 (July 1981), 41-48.

CITED BY 81

	Pohua P. Chang , William Y. Chen , Scott A. Mahlke , Wen-mei W. Hwu, Comparing static and dynamic code scheduling for multiple-instruction-issue processors, Proceedings of the 24th annual international symposium on Microarchitecture, p.25-33, September 1991, Albuquerque, New Mexico, Puerto Rico
	David W. Wall, Experience with a software-defined machine architecture, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.3, p.299-338, July 1992
	P. P. Chang , W. W. Hwu, Trace selection for compiling large C application programs to microcode, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.21-29, November 28-December 02, 1988, San Diego, California, United States
	Krishna Palem , Barbara Simons, Scheduling time-critical instructions on RISC machines, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.270-280, December 1989, San Francisco, California, United States
	Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, ACM SIGPLAN Notices, v.19 n.6, p.37-47, June 1984
	Pritpal S. Ahuja , Douglas W. Clark , Anne Rogers, The performance impact of incomplete bypassing in processor pipelines, Proceedings of the 28th annual international symposium on Microarchitecture, p.36-45, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	P.-H. Chang , W.-M. W. Hwu, Forward semantic: a compiler-assisted instruction fetch method for heavily pipelined processors, ACM SIGMICRO Newsletter, v.20 n.3, p.188-198, Sep. 1989
	Ing-Jer Huang, Co-synthesis of pipelined structures and instruction reordering constraints for instruction set processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.1, p.93-121, Jan. 2001
	Steven M. Kurlander , Todd A. Proebsting , Charles N. Fischer, Efficient instruction scheduling for delayed-load architectures, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.5, p.740-776, Sept. 1995
	Wei-Kai Cheng , Youn-Long Lin, Code generation of nested loops for DSP processors with heterogeneous registers and structural pipelining, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.231-256, July 1999
	Jack W. Davidson, A retargetable instruction reorganizer, ACM SIGPLAN Notices, v.21 n.7, p.234-241, July 1986
	David Bernstein , Doron Cohen , Hugo Krawczyk, Code duplication: an assist for global instruction scheduling, Proceedings of the 24th annual international symposium on Microarchitecture, p.103-113, September 1991, Albuquerque, New Mexico, Puerto Rico
	Philip B. Gibbons , Steven S. Muchnick, Efficient instruction scheduling for a pipelined architecture, ACM SIGPLAN Notices, v.21 n.7, p.11-16, July 1986
	J.-J. Shieh , C. Papachristou, On reordering instruction streams for pipelined computers, ACM SIGMICRO Newsletter, v.20 n.3, p.199-206, Sep. 1989
	W. W. Hwu , P. P. Chang, Exploiting parallel microprocessor microarchitectures with a compiler code generator, ACM SIGARCH Computer Architecture News, v.16 n.2, p.45-53, May 1988
	Qi Ning , Guang R. Gao, A novel framework of register allocation for software pipelining, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.29-42, March 1993, Charleston, South Carolina, United States
	J. R. Goodman , W.-C. Hsu, Code scheduling and register allocation in large basic blocks, Proceedings of the 2nd international conference on Supercomputing, p.442-452, June 1988, St. Malo, France
	Jack L. Lo , Susan J. Eggers, Improving balanced scheduling with compiler optimizations that increase instruction-level parallelism, ACM SIGPLAN Notices, v.30 n.6, p.151-162, June 1995
	C. Chekuri , R. Motwani , B. Natarajan , C. Stien, Approximation techniques for average completion time scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.609-618, January 05-07, 1997, New Orleans, Louisiana, United States
	Ing-Jer Huang , Alvin M. Despain, Hardware/software resolution of pipeline hazards in pipeline synthesis of instruction set processors, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.594-599, November 07-11, 1993, Santa Clara, California, United States
	A. R. Pleszkun , J. R. Goodman , W. C. Hsu , R. T. Joersz , G. Bier , P. Woest , P. B. Schechter, WISQ: a restartable architecture using queues, Proceedings of the 14th annual international symposium on Computer architecture, p.290-299, June 02-05, 1987, Pittsburgh, Pennsylvania, United States
	Jong-Jiann Shieh , Christos A. Papachristou, An instruction reoderer for pipelined computers, Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, p.135-142, November 27-29, 1990, Orlando, Florida, United States
	Suneel Jain, Circular scheduling: a new technique to perform software pipelining, ACM SIGPLAN Notices, v.26 n.6, p.219-228, June 1991
	L. Wang , C. L. Wu, I-NET mechanism for issuing multiple instructions, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.88-95, November 12-17, 1988, Orlando, Florida, United States
	Allen Leung , Krishna V. Palem , Amir Pnueli, Scheduling time-constrained instructions on pipelined processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.73-103, Jan. 2001
	A. Agarwal, Performance Tradeoffs in Multithreaded Processors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.525-539, September 1992
	P. Chow , M. Horowitz, Architectural tradeoffs in the design of MIPS-X, Proceedings of the 14th annual international symposium on Computer architecture, p.300-308, June 02-05, 1987, Pittsburgh, Pennsylvania, United States
	Peter L. Bird , Uwe F. Pleban, A semantics-directed partitioning of a processor architecture, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.702-709, November 18-22, 1991, Albuquerque, New Mexico, United States
	David G. Bradlee , Robert R. Henry , Susan J. Eggers, The Marion system for retargetable instruction scheduling, ACM SIGPLAN Notices, v.26 n.6, p.229-240, June 1991
	David G. Bradlee , Susan J. Eggers , Robert R. Henry, Integrating register allocation and instruction scheduling for RISCs, ACM SIGARCH Computer Architecture News, v.19 n.2, p.122-131, Apr. 1991
	Cindy Norris , Lori L. Pollock, An experimental study of several cooperative register allocation and instruction scheduling strategies, Proceedings of the 28th annual international symposium on Microarchitecture, p.169-179, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	David Bernstein , Izidor Gertner, Scheduling expressions on a pipelined processor with a maximal delay of one cycle, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.57-66, Jan. 1989
	Val Popescu , Merle Schultz , John Spracklen , Gary Gibson , Bruce Lightner , David Isaman, The Metaflow Architecture, IEEE Micro, v.11 n.3, p.10-13, 63-73, May 1991
	Todd A. Proebsting , Charles N. Fischer, Linear-time, optimal code scheduling for delayed-load architectures, ACM SIGPLAN Notices, v.26 n.6, p.256-267, June 1991
	Vivek Sarkar , Barbara Simons, Anticipatory instruction scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.119-130, June 24-26, 1996, Padua, Italy
	Krishna V. Palem , Barbara B. Simons, Scheduling time-critical instructions on RISC machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.4, p.632-658, Sept. 1993
	Mark Smotherman , Sanjay Krishnamurthy , P. S. Aravind , David Hunnicutt, Efficient DAG construction and heuristic calculation for instruction scheduling, Proceedings of the 24th annual international symposium on Microarchitecture, p.93-102, September 1991, Albuquerque, New Mexico, Puerto Rico
	Shlomit S. Pinter, Register allocation with instruction scheduling, ACM SIGPLAN Notices, v.28 n.6, p.248-257, June 1993
	Anant Agarwal , Beng-Hong Lim , David Kranz , John Kubiatowicz, APRIL: a processor architecture for multiprocessing, ACM SIGARCH Computer Architecture News, v.18 n.3a, p.104-114, June 1990
	W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, ACM SIGARCH Computer Architecture News, v.17 n.3, p.242-251, June 1989
	S. McFarling , J. Hennesey, Reducing the cost of branches, ACM SIGARCH Computer Architecture News, v.14 n.2, p.396-403, June 1986
	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
	Rajiv Gupta, The fuzzy barrier: a mechanism for high speed synchronization of processors, ACM SIGARCH Computer Architecture News, v.17 n.2, p.54-63, April 1989
	Ing-Jer Huang , Alvin M. Despain, An extended classification of inter-instruction dependency and its application in automatic synthesis of pipelined processors, Proceedings of the 26th annual international symposium on Microarchitecture, p.236-246, December 01-03, 1993, Austin, Texas, United States
	Christoph Keßler , Andrzej Bednarski, A Dynamic Programming Approach to Optimal Integrated Code Generation, ACM SIGPLAN Notices, v.36 n.8, p.165-174, Aug. 2001
	Gregory M. Papadopoulos , Kenneth R. Traub, Multithreading: a revisionist view of dataflow architectures, ACM SIGARCH Computer Architecture News, v.19 n.3, p.342-351, May 1991
	Feipei Lai , Hung-Chang Lee , Chun-Luh Lee, Optimization on instruction reorganization, Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, p.143-148, November 27-29, 1990, Orlando, Florida, United States
	David Bernstein , Michael Rodeh, Global instruction scheduling for superscalar machines, ACM SIGPLAN Notices, v.26 n.6, p.241-255, June 1991
	Anne Rogers , Kai Li, Software support for speculative loads, ACM SIGPLAN Notices, v.27 n.9, p.38-50, Sept. 1992
	K. D. Wilken, An Optimal Graph-Construction Approach to Placing Program Signatures for Signature Monitoring, IEEE Transactions on Computers, v.42 n.11, p.1372-1381, November 1993
	Stephan Murer , Philipp Färber, Code Generation for Multi-Threaded Architectures from Dataflow Graphs, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.77-90, January 20-22, 1993
	Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Sunah Lee , Rajiv Gupta, Executing loops on a fine-grained MIMD architecture, Proceedings of the 24th annual international symposium on Microarchitecture, p.199-205, September 1991, Albuquerque, New Mexico, Puerto Rico
	Jack W. Davidson , David B. Whalley, Reducing the cost of branches by using registers, ACM SIGARCH Computer Architecture News, v.18 n.3a, p.182-191, June 1990
	David Bernstein , Doron Cohen , Yuval Lavon , Vladimir Rainish, Performance evaluation of instruction scheduling on the IBM RISC System/6000, ACM SIGMICRO Newsletter, v.23 n.1-2, p.226-235, Dec. 1992
	Mark S. Johnson , Terrence C. Miller, Effectiveness of a machine-level, global optimizer, ACM SIGPLAN Notices, v.21 n.7, p.99-108, July 1986
	C. Norris , L. L. Pollock, A schedular-sensitive global register allocator, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.804-813, December 1993, Portland, Oregon, United States
	Daniel M. Lavery , Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, The Importance of Prepass Code Scheduling for Superscalar and Superpipelined Processors, IEEE Transactions on Computers, v.44 n.3, p.353-370, March 1995
	Steven S. Muchnick , Phillip B. Gibbons, Efficient instruction scheduling for a pipelined architecture, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Cindy Norris , Lori L. Pollock, Experiences with Cooperating Register Allocation and Instruction Scheduling, International Journal of Parallel Programming, v.26 n.3, p.241-283, June 1998
	Rajiv Gupta , Mary Lou Soffa, Region Scheduling: An Approach for Detecting and Redistributing Parallelism, IEEE Transactions on Software Engineering, v.16 n.4, p.421-431, April 1990
	Wei-Chung Hsu , Charles N. Fisher , James R. Goodman, On the Minimization of Loads/Stores in Local Register Allocation, IEEE Transactions on Software Engineering, v.15 n.10, p.1252-1260, October 1989
	Steven S. Muchnick , Phillip B. Gibbons, Efficient instruction scheduling for a pipelined architecture, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Christian W. Probst , Andreas Gal , Michael Franz, Average case vs. worst case: margins of safety in system design, Proceedings of the 2005 workshop on New security paradigms, September 20-23, 2005, Lake Arrowhead, California
	Cindy Norris , Lori L. Pollock, Register allocation sensitive region scheduling, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.1-10, June 27-29, 1995, Limassol, Cyprus
	Chung-Chi Jim Li , Shyh-Kwei Chen , W. Kent Fuchs , Wen-Mei W. Hwu, Compiler-Based Multiple Instruction Retry, IEEE Transactions on Computers, v.44 n.1, p.35-46, January 1995
	John Sanguinetti, Program optimization for a pipelined machine a case study, ACM SIGMETRICS Performance Evaluation Review, v.12 n.3, p.88-95, August 1984
	Mark Heffernan , Kent Wilken, Data-Dependency Graph Transformations for Instruction Scheduling, Journal of Scheduling, v.8 n.5, p.427-451, October 2005
	John Regehr , Alastair Reid, HOIST: a system for automatically deriving static analyzers for embedded systems, ACM SIGOPS Operating Systems Review, v.38 n.5, December 2004
	Qi Ning, Register allocation for optimal loop scheduling, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: distributed computing, October 24-28, 1993, Toronto, Ontario, Canada
	Hong-Chich Chou , Chung-Ping Chung, An Optimal Instruction Scheduler for Superscalar Processor, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.303-313, March 1995
	David Bernstein , Michael Rodeh , Izidor Gertner, On the Complexity of Scheduling Problems for Parallel/Pipelined Machines, IEEE Transactions on Computers, v.38 n.9, p.1308-1313, September 1989
	Ghassan Shobaki , Kent Wilken, Optimal Superblock Scheduling Using Enumeration, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.283-293, December 04-08, 2004, Portland, Oregon
	Thomas R. Gross , John L. Hennessy , Steven A. Przybylski , Christopher Rowen, Measurement and evaluation of the MIPS architecture and processor, ACM Transactions on Computer Systems (TOCS), v.6 n.3, p.229-257, Aug. 1988
	Matthew J. Bridges , Neil Vachharajani , Guilherme Ottoni , David I. August, Automatic instruction scheduler retargeting by reverse-engineering, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Sanjay M. Krishamurthy, A brief survey of papers on scheduling for pipelined processors, ACM SIGPLAN Notices, v.25 n.7, p.97-106, July 1990
	Henry G. Baker, Precise instruction scheduling without a precise machine model, ACM SIGARCH Computer Architecture News, v.19 n.6, p.4-8, Dec. 1991
	Ivan D. Baev , Waleed M. Meleis , Santosh G. Abraham, Backtracking-Based Instruction Scheduling to Fill Branch Delay Slots, International Journal of Parallel Programming, v.30 n.6, p.397-418, December 2002
	E. H. Debaere, Instruction-path coprocessing to solve some RISC problems, ACM SIGARCH Computer Architecture News, v.17 n.5, p.83-94, Sep. 1989
	Martin Charles Golumbic , Vladimir Rainish, Instruction Scheduling Across Control Flow, Scientific Programming, v.2 n.3, p.1-5, August 1993
	Ghassan Shobaki , Kent Wilken , Mark Heffernan, Optimal trace scheduling using enumeration, ACM Transactions on Architecture and Code Optimization (TACO), v.5 n.4, p.1-32, March 2009