Loop scheduler

• US 5,491,823 A
• Filed: 01/25/1994
• Issued: 02/13/1996
• Est. Priority Date: 01/25/1994
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Ruttenberg, John C.
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US08/186,268
• Time in Patent Office: 749 Days
• Field of Search: 395/650, 395/700
• US Class Current: 717/161
• CPC Class Codes: G06F 8/452 Loops

Abstract

A loop scheduler in a software compiler system for generating a schedule for executing in a target computer loops of instructions contained in a computer program is described. The loop scheduler operates by searching for an optimal loop schedule for executing a particular instruction loop in the target computer. The loop scheduler then identifies loop overhead instructions and non-loop overhead instructions in the particular instruction loop. A replicated loop schedule is generated by the loop scheduler by replicating the non-loop overhead instructions in the loop schedule by a replication factor such that overlap of each operation instance in the optimal loop schedule with itself is prevented. The loop scheduler inserts the loop overhead instructions into the replicated loop schedule to generate a modified loop schedule, and then allocates registers of the target computer to the modified loop schedule.

Claims

1. A method of generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising the steps of:

(1) searching for an optimal loop schedule for executing a particular instruction loop in the target computer;

(2) identifying loop overhead instructions and non-loop overhead instructions in said particular instruction loop;

(3) generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented;

(4) inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule; and

(5) allocating registers of the target computer to said modified loop schedule.

2. The method of claim 1, wherein step (4) comprises the steps of:

using loop overhead information and an iteration number of a memory reference operation in said optimal loop schedule to calculate effective address information of said memory reference operation; and

inserting said effective address information into said replicated loop schedule.

3. The method of claim 2, wherein step (4) further comprises the steps of:

generating first scheduling information pertaining to scheduling operations of said particular instruction loop which operate to increment induction variables;

generating second scheduling information pertaining to scheduling operations of said particular instruction loop which operate to exit conditional loops; and

inserting said first and second scheduling information into said replicated loop schedule.

4. The method of claim 1, wherein step (1) comprises the steps of:

enumerating all possible schedules of said particular instruction loop using a predetermined exponential search procedure;

ordering said all possible schedules in a search list according to complexity of operation scheduling; and

pruning said predetermined exponential search procedure to expedite back searching in said search list.

5. The method of claim 1, wherein step (2) comprises the steps of:

classifying an instruction of said particular instruction loop as a loop overhead instruction if said instruction operates to increment an induction variable; and

classifying said instruction as a loop overhead instruction if said instruction operates to perform a logical test of an induction variable.

6. The method of claim 1, wherein step (3) comprises the steps of:

determining a total number of instructions value corresponding to the number of instructions in said particular instruction loop;

determining a lifetime of each operation instance in said optimal loop schedule;

generating a set of potential replication factors, each element of said set being equal to a lifetime value for an operation instance divided by said total number of instructions value; and

setting said replication factor equal to a maximum value in said set.

7. The method of claim 1, wherein step (5) comprises the steps of:

calculating an applicable executable range of clock cycles for an operation instance of said modified loop schedule according to any scheduled data predecessors and any scheduled data successors of said operation instance;

performing a forward search of said modified loop schedule to schedule any unscheduled data predecessors of said operation instance; and

performing a backward search of said modified loop schedule to schedule any unscheduled data successors of said operation instance.

8. A method of generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising the steps of:

(1) searching for an optimal loop schedule for executing a particular instruction loop in the target computer, said search including;

enumerating all possible schedules of said particular instruction loop using a predetermined exponential search procedure;

ordering said all possible schedules in a search list according to complexity of operation scheduling; and

pruning said predetermined exponential search procedure to expedite back searching in said search list;

(2) identifying loop overhead instructions and non-loop overhead-instructions in said particular instruction loop, said identifying including;

classifying an instruction of said particular instruction loop as a loop overhead instruction if said instruction operates to increment an induction variable; and

classifying said instruction as a loop overhead instruction if said instruction operates to perform a logical test of an induction variable;

(3) generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented, said generating including;

determining a total number of instructions value corresponding to the number of instructions in said particular instruction loop;

determining a lifetime of each operation instance in said optimal loop schedule;

generating a set of potential replication factors, each element of said set being equal to a lifetime value for an operation instance divided by said total number of instructions value; and

setting said replication factor equal to a maximum value in said set;

(4) inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule, said inserting including;

using loop overhead information and an iteration number of a memory reference operation in said optimal loop schedule to calculate effective address information of said memory reference operation; and

inserting said effective address information into said replicated loop schedule; and

(5) allocating registers of the target computer to said modified loop schedule, said allocating including;

calculating an applicable executable range of clock cycles for an operation instance of said modified loop schedule according to any scheduled data predecessors and any schedules data successors of said operation instance;

performing a forward search of said modified loop schedule to schedule any unscheduled data predecessors of said operation instance; and

performing a backward search of said modified loop schedule to schedule any unscheduled data successors of said operation instance.

9. A system for generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising:

optimal loop searching means for searching for an optimal loop schedule for executing a particular instruction loop in the target computer;

instruction identifying means for identifying loop overhead instructions and non-loop overhead instructions in said particular instruction loop;

replicating means for generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented;

loop overhead means for inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule; and

register allocating means for allocating registers of the target computer to said modified loop schedule.

10. The system of claim 9, wherein said loop overhead means comprises:

means for using loop overhead information and an iteration number of a memory reference operation in said optimal loop schedule to calculate effective address information of said memory reference operation; and

means for inserting said effective address information into said replicated loop schedule.

11. The system of claim 10, wherein said loop overhead means further comprises:

means for generating first scheduling information pertaining to scheduling operations of said particular instruction loop which operate to increment induction variables;

means for generating second scheduling information pertaining to scheduling operations of said particular instruction loop which operate to exit conditional loops; and

means for inserting said first and second scheduling information into said replicated loop schedule.

12. The system of claim 9, wherein said optimal loop searching means comprises:

means for enumerating all possible schedules of said particular instruction loop using a predetermined exponential search procedure;

means for ordering said all possible schedules in a search list according to complexity of operation scheduling; and

means for pruning said predetermined exponential search procedure to expedite back searching in said search list.

13. The system of claim 9, wherein said instruction identifying means comprises:

means for classifying an instruction of said particular instruction loop as a loop overhead instruction if said instruction operates to increment an induction variable; and

means for classifying said instruction as a loop overhead instruction if said instruction operates to perform a logical test of an induction variable.

14. The system of claim 9, wherein said replicating means comprises:

means for determining a total number of instructions value corresponding to the number of instructions in said particular instruction loop;

means for determining a lifetime of each operation instance in said optimal loop schedule;

means for generating a set of potential replication factors, each element of said set being equal to a lifetime value for an operation instance divided by said total number of instructions value; and

means for setting said replication factor equal to a maximum value in said set.

15. The system of claim 9, wherein said register allocating means comprises:

means for calculating an applicable executable range of clock cycles for an operation instance of said modified loop schedule according to any scheduled data predecessors and any scheduled data successors of said operation instance;

means for performing a forward search of said modified loop schedule to schedule any unscheduled data predecessors of said operation instance; and

means for performing a backward search of said modified loop schedule to schedule any unscheduled data successors of said operation instance.

16. A system for generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising:

optimal loop searching means for searching for an optimal loop schedule for executing a particular instruction loop in the target computer, wherein said optimal loop searching means includes;

means for enumerating all possible schedules of said particular instruction loop using a predetermined exponential searching procedure;

means for ordering said all possible schedules in a search list according to complexity of operating scheduling; and

means for pruning said predetermined exponential search procedure to expedite back searching in said search list;

instruction identifying means for identifying loop overhead instructions and non-loop overhead instructions in said particular instruction loop, wherein said instruction identifying means includes;

means for classifying an instruction of said particular instruction loop as a loop overhead instruction if said instruction operates to increment an induction variable; and

means for classifying said instruction as a loop overhead instruction if said instruction operates to perform a logical test of an induction variable;

replicating means for generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented, wherein said replicating means includes;

means for determining a total number of instructions value corresponding to the number of instructions in said particular instruction loop;

means for determining a lifetime of each operation instance in said optimal loop schedule;

means for generating a set of potential replication factors, each element of said set being equal to a lifetime value for an operation instance divided by said total number of instructions value; and

means for setting said replication factor equal to a maximum value in said set;

loop overhead means for inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule, wherein said loop overhead means includes;

means for using loop overhead information and an iteration number of a memory reference operation in said optimal loop schedule to calculate effective address information of said memory reference operation; and

means for inserting said effective address information into said replicated loop schedule; and

register allocating means for allocating registers of the target computer to said modified loop schedule, wherein said register allocating means comprises;

means for calculating an applicable executable range of clock cycles for an operation instance of said modified loop schedule according to any scheduled data predecessors and any scheduled data successors of said operation instance;

means for performing a forward search of said modified loop schedule to schedule any unscheduled data predecessors of said operation instance; and

means for performing a backward search of said modified loop schedule to schedule any unscheduled data successors of said operation instance.