×

Automatic scheduling of instructions to reduce code size

  • US 6,059,840 A
  • Filed: 03/17/1997
  • Issued: 05/09/2000
  • Est. Priority Date: 03/17/1997
  • Status: Expired due to Fees
First Claim
Patent Images

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 all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×