Automatic scheduling of instructions to reduce code size

Claim 3

The method of claim 1 wherein step (d) comprises the substeps of: 1) selecting instructions that do not conflict prior to selecting instructions that do conflict.

Claim 4

The method of claim 2 wherein substep (1) of step (d) comprises: scheduling instructions in an order which maximizes concurrent execution of instructions.

Claim 5

The method of claim 2 wherein substep (1) of step (d) comprises: selecting instructions that do not define physical registers prior to selecting instructions that define physical registers.

Claim 6

The method of claim 2, wherein substep (1) of step (d) comprises: selecting instructions that use physical registers, where instructions are selected according to the number of physical registers used.

Claim 7

The method of claim 1, wherein the method further comprises the step of: iteratively repeating steps (d), (e), (f), (g), and (h) as a first loop until the ready list is empty.

Claim 8

The method of claim 6, wherein when the ready list is empty the portion of the computer program has a second code size, wherein the second code size is smaller than the first code size.

Claim 9

The method of claim 1 repeating steps (a), (b), (c), (d), (e), (f), (g), and (h) as a second loop.

Claim 10

The method of claim 1 wherein step (b) is iteratively repeated for all COPY instructions which do not copy a first physical register to a second physical register.

Claim 11

The method of claim 1, wherein the first portion is a basic block.

Claim 12

The method of claim 1, wherein step (f) comprises: inserting a second COPY instruction to move a value in a physical register to a virtual register.

Claim 13

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.

Claim 14

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.

Claim 15

The computer program compiler of claim 12, wherein the first set of instructions includes steps for coalescing a second COPY instruction in the computer program.

Claim 16

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).

Claim 17

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).

Claim 18

The computer program product of claim 14, wherein: the computer readable medium is a floppy disk.

Claim 19

The computer program product of claim 14: wherein the computer readable medium is a compact disk.

Claim 20

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.

Claim 21

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.

Claim 22

The computer program product of claim 17, wherein the computer readable medium is a memory on a data processor.

Claim 23

The computer program product of claim 17, wherein the computer readable medium is a memory storage unit.