Automatic scheduling of instructions to reduce code size

Details Automatic scheduling of instructions to reduce code size Automatic scheduling of instructions to reduce code size

1997-03-17

2000-05-09

Hafiz, Tariq R.

Data processing: software development, installation, and managem

Software program development tool

Translation of code

717 8, G06F 945

Patent

active

060598409

ABSTRACT:
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.

REFERENCES:
patent: 4571678 (1986-02-01), Chaitin
patent: 5367651 (1994-11-01), Smith et al.
patent: 5367696 (1994-11-01), Abe
patent: 5396631 (1995-03-01), Hayashi et al.
patent: 5491823 (1996-02-01), Ruttenberg
patent: 5530866 (1996-06-01), Koblenz et al.
patent: 5761514 (1998-06-01), Aizikowitz et al.
patent: 5784066 (1998-07-01), Aizikowitz et al.
patent: 5790866 (1998-08-01), Robison
patent: 5790867 (1998-07-01), Schmidt et al.
patent: 5835776 (1998-11-01), Tirumalai et al.
patent: 5878261 (1999-03-01), Holler et al.
patent: 5901317 (1999-05-01), Geobel
patent: 5903761 (1999-05-01), Tyma
patent: 5923883 (1999-07-01), Tanaka et al.
patent: 5930507 (1999-07-01), Nakahira et al.
patent: 5937196 (1999-08-01), Schmidt et al.
patent: 5940621 (1999-08-01), Caldwell
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-490.

Affiliated with

Also associated with

Rating

Automatic scheduling of instructions to reduce code size does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Automatic scheduling of instructions to reduce code size, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic scheduling of instructions to reduce code size will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1060266