Automatic scheduling of instructions to reduce code size
Patent 6059840 Issued on May 9, 2000. Estimated Expiration Date: March 17, 2017. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
Scheduling instructions by eliminating COPY instructions to reduce code size and increase performance in a computer program compiler. According to one embodiment of the present invention COPY instructions are coalesced prior to preparing a ready list. The ready list is polled and instructions selected for scheduling. After selection of a next instruction, liveness conflicts are determined, where a live register contains a valid value that is needed at a later step. Conflicts are then resolved and instruction scheduling continues. The process is continued until the ready list is empty.
Other References
Park, J.; Moon, S.-M.; "Optimistic Register Coalescing"; Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques; pp. 196-204, Oct. 1998
George, L.; Appel, A.; "Iterated Register Coalescing"; ACM Transactions on Programming Languages and Systems; vol. 18, No. 3, pp. 300-324, Mar. 1996
Chow, F.; "Minimizing Register Usage Penalty at Procedure Calls"; Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation; pp. 85-94, Jun. 1998
Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman "Compilers Principles, Techniques,and Tools", Addison-Wesley Chapter 10, Mar. 1988
Gregory J. Chaitin, et al, "Register Allocation Via Coloring", IBM T. J. Watson Research Center, RC 8395 (#36543) Aug. 4, 1980, Computer Science, pp. 1-12
Frederick Chow, et al., "Register Allocation by Priority-based Coloring", Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction SIGPLAN Notices, vol. 19,No. 6, Jun. 1984, pp. 222-232
Preston Briggs, Dissertation "Register Allocation via Graph Coloring", Rice University, Houston, Texas, Apr. 1992, pp. 1-142
Monica Lam, "Software Pipelining: An Effective Scheduling Techique for VLIW Machines", Proceedings of SIGPLAN '88 Conf. on Programming Language Design/Implementation, Atlanta, GA, Jun. 22-24, 1988, pp. 318-327
Phillip B. Gibbons, et al., "Efficient Instruction Scheduling for a Pipelined Architecture", Proceedings of SIGPLAN '88 Conf. on Compiler Construction SIGPLAN Notices 21(7), Jul.,1988,pp. 1-3
John Hennessy, et al., "Postpass Code Optimization of Pipeline Constraints", ACM Transaction on Programming Languages and Systems, vol. 5, No. 3, Jul. 1983, pp. 422-448
Joseph A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction", IEEE Transactions on Computers, vol. C-30., No. 7, Jul. 1981, pp. 478-49
March 17, 2017. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
