Automatic scheduling of instructions to reduce code size
First Claim
1. A method for scheduling instructions for a first portion of a computer program, the first portion of the computer program having a plurality of instructions, the first portion of the computer program having a first code size, the method comprising the steps of:
- (a) building a def-use chain for the portion of the computer program, wherein the def-use chain defines an input arc and an output arc for each COPY instruction;
(b) coalescing a first COPY instruction, where the first COPY instruction is part of the portion of the computer program, wherein coalescing the first COPY instruction combines the input and output arcs of the first COPY instruction;
(c) listing a first subset of the first portion in a ready list, the ready list for listing instructions available for scheduling;
(d) selecting a next instruction from the first subset listed in the ready list;
(e) determining if the next instruction has at least one liveness conflict;
(f) resolving the at least one liveness conflict, if the next instruction has at least one liveness conflict;
(g) scheduling the next instruction; and
(h) updating the ready list after completing step (g).
4 Assignments
0 Petitions
Accused Products
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.
122 Citations
19 Claims
-
1. A method for scheduling instructions for a first portion of a computer program, the first portion of the computer program having a plurality of instructions, the first portion of the computer program having a first code size, the method comprising the steps of:
-
(a) building a def-use chain for the portion of the computer program, wherein the def-use chain defines an input arc and an output arc for each COPY instruction; (b) coalescing a first COPY instruction, where the first COPY instruction is part of the portion of the computer program, wherein coalescing the first COPY instruction combines the input and output arcs of the first COPY instruction; (c) listing a first subset of the first portion in a ready list, the ready list for listing instructions available for scheduling; (d) selecting a next instruction from the first subset listed in the ready list; (e) determining if the next instruction has at least one liveness conflict; (f) resolving the at least one liveness conflict, if the next instruction has at least one liveness conflict; (g) scheduling the next instruction; and (h) updating the ready list after completing step (g). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A computer program compiler for translating human readable computer program code into computer readable program code, the computer program compiler comprising:
-
a first set of instructions which coalesces COPY instructions in a computer program; a second set of instructions which lists instructions of the computer program in a ready list; a third set of instructions which selects a next instruction from the ready list; a fourth set of instructions which determines liveness conflicts for the next instruction; a fifth set of instructions which resolves liveness conflicts for the next instruction; a sixth set of instructions which schedules the next instruction, wherein instructions that do not conflict are selected prior to selecting instructions that do conflict, wherein instructions that do not define physical registers are selected prior to selecting instructions that define physical registers; and a seventh set of instructions which determines if the ready list is empty. - View Dependent Claims (13)
-
-
14. A computer program product encoded in a computer readable medium, the computer program product comprising at least a first plurality of instructions executable on a computer system, said computer program product being compiled according to a method for scheduling instructions, the method comprising:
-
(a) building a def-use chain for the portion of the computer program, wherein the def-use chain defines an input arc and an output arc for each COPY instruction; (b) coalescing a first COPY instruction, where the first COPY instruction is part of the portion of the computer program, wherein coalescing the first COPY instruction combines the input and output arcs of the first COPY instruction; (c) listing a first subset of the instructions in a ready list, the ready list for listing instructions available for scheduling; (d) selecting a next instruction from the first subset listed in the ready list; (e) determining if the next instruction has at least one liveness conflict; (f) resolving the at least one liveness conflict, if the next instruction has at least one liveness conflict; (g) scheduling the next instruction; and (h) updating the ready list after completing step (g). - View Dependent Claims (15, 16)
-
-
17. A computer program product encoded in a computer readable medium, the computer program product being compiled by a computer program compiler, the computer program compiler for translating human readable computer program code into computer readable code, the compiler, the computer program compiler, comprising:
-
a first set of instructions which coalesces a first COPY instruction in the computer program product; a second set of instructions which lists listing instructions in a ready list; a third set of instructions which selects a next instruction from the ready list; a fourth set of instructions which determines liveness conflicts for the next instruction; a fifth set of instructions which resolves liveness conflicts for the next instruction; a sixth set of instructions which schedules instructions in the ready list, wherein instructions that do not conflict are scheduled prior to scheduling instructions that do conflict, wherein instructions that do not define physical registers are scheduled prior to scheduling instructions that define physical registers; and a seventh set of instructions which determines if the ready list is empty. - View Dependent Claims (18, 19)
-
Specification