US 5,491,823 A · Loop scheduler

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.

Claims16

Dependent claims

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.

3 more elements

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.

22 more elements

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.

3 more elements

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.

22 more elements

Dependencies are inferred from the claim text.

Loop scheduler

Life of this patent

Loop scheduler

Life of this patent

Abstract

Claims16