Register economy heuristic for a cycle driven multiple issue instruction scheduler

• US 20020013937A1
• Filed: 12/21/2000
• Published: 01/31/2002
• Est. Priority Date: 02/17/1999
• Status: Active Grant

• Current Assignee: Elbrus International Limited
• Original Assignee: Elbrus International Limited
• Inventors: Ostanevich, Alexander Y., Volkonsky, Vladimir Y.
• Granted Patent: US 6,718,541 B2
• Time in Patent Office: Days
• US Class Current: 717/160
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

A method for scheduling operations utilized by an optimizing compiler to reduce register pressure on a target hardware platform assigns register economy priority (REP) values to each operation in a basic block. For each time slot, operations are scheduled in order of their lowest REP values.

Claims

1. A method for scheduling operations in a basic block comprising the acts of:

ordering operations in the block into a data dependency graph (DFG) showing predecessors and successors of each operations;

scheduling time slots for each level of the DFG;

assigning a number of predecessors value to each operation node in the DFG indicating the number of predecessors that an operation depends on;

setting a counter value equal to a first value;

assigning the first value to a last operation node having the greatest number of predecessors;

for each operation in the DFG preceding the last operation node, incrementing the counter to obtain an incremented counter value, and, for binary nodes having multiple predecessors, assigning the incremented counter value as an economy priority value to the immediate predecessor having a lower number of dominating predecessors;

subsequent to assigning a counter value to an operation having a minimum number of dominating predecessors, returning to the binary operation node and assigning the incremented counter value as an economy priority value to the immediate predecessor having the next lowest number of dominating predecessors;

for a first time slot, listing all ready operations having no unresolved dependencies which may be scheduled to execute in a fixed number of arithmetic/logic channels (ALCs);

scheduling the fixed number of ready operations in the first time slot having the lowest economy priority values;

for the second time slot listing all unscheduled ready operations having no unresolved dependencies which may be scheduled to execute in the fixed number of ALCs;

scheduling the fixed number of ready operations in the second time slot having the lowest economy priority values;

for all subsequent time slots, listing all unscheduled ready operations having no unresolved dependencies which may be scheduled to execute in the fixed number of ALCs until all operations in the block are scheduled; and

scheduling the fixed number of ready operations in the subsequent time slots having the lowest economy priority values.

2. A method for scheduling operations in a basic block comprising the acts of:

ordering operations in the block into a data dependency graph (DFG);

scheduling time slots for each level of the DFG;

for each node, calculating a number of dominating predecessors (NDPs), including node itself;

NDP=1+NDP(p1)+ . . . +NDP(pm) where p1, . . . , pm are immediate predecessors to the node and where for nodes without predecessors NDP=1;

for last operation of the DFG having a greatest value of NDP, assigning a minimum value of a register priority (REP) value;

assigning the minimum REP value to a temporary counter CNT;

walking up through DFG from each operation to its predecessors, incrementing CNT, and assigning an REP(node)=CNT;

for two or more immediate predecessors the first immediate predecessor having the greatest NDP is visited first;

for a first time slot, listing all ready operations having no unresolved dependencies which may be scheduled to execute in a fixed number of arithmetic/logic channels (ALCs);

scheduling the fixed number of ready operations in the first time slot having the lowest REP values;

for the second time slot listing all unscheduled ready operations having no unresolved dependencies which may be scheduled to execute in the fixed number of ALCs;

scheduling the fixed number of ready operations in the second time slot having the lowest REP values;

for all subsequent time slots, listing all unscheduled ready operations having no unresolved dependencies which may be scheduled to execute in the fixed number of ALCs until all operations in the block are scheduled; and

scheduling the fixed number of ready operations in the subsequent time slots having the lowest REP values;

3. A method, implemented by an optimizing compiler, for scheduling a group of operations, said method comprising the steps of:

ordering the operations based on data dependencies;

assigning a number of predecessors value to ordered operations based on the number of predecessors on which the ordered operation depends;

assigning an economy priority value to each operation, starting with the operation having the most predecessors, by traversing the ordered list in order of number of predecessors values and incrementing the economy priority value assigned to each operation;

forming a ready list having a plurality of time slots with ready operations scheduled in each time slots ordered by economy priority values;

scheduling operations in each time slot in order of economy priority to a fixed number of arithmetic-logic resources.

4. The method of claim 3 further comprising the steps of:

for binary operations having more than one predecessor, traversing to the predecessor having the largest number of predecessor values; and

for operations having no predecessor, resuming traversing at the binary operation and traversing to the immediate predecessor not previously traversed.

5. The method of claim 3 further comprising the step of:

for binary operations having more than one immediate predecessor, each predecessor having same number of dominating predecessor value, traversing to first one of immediate predecessors; and

for operations having no predecessor, resuming traversing at the binary operation and traversing to the immediate predecessor not previously traversed.

6. A computer program product comprising:

a computer readable medium having program code embodied therein for implementing compiler techniques for scheduling a group of operations, said program code comprising;

program code executable by a computer for ordering the operations based on data dependencies;

program code executable by a computer for assigning a number of predecessors value to ordered operations based on the number of predecessors on which the ordered operation depends;

program code executable by a computer for assigning an economy priority value to each operation, starting with the operation having the most predecessors, by traversing the ordered list in order of number of predecessors values and incrementing the economy priority value assigned to each operation;

program code executable by a computer for forming a ready list having a plurality of time slots with ready operations scheduled in each time slots ordered by economy priority values; and

program code executable by a computer for scheduling operations in each time slot in order of economy priority to a fixed number of arithmetic-logic resources.