초록 ▼

Improved scheduling of instructions within a loop for execution by a computer system having hardware lookahead is provided. A dependence graph is constructed which contains all the nodes of a dependence graph corresponding to the loop, but which only contains loop-independent dependence edges. A sta

Improved scheduling of instructions within a loop for execution by a computer system having hardware lookahead is provided. A dependence graph is constructed which contains all the nodes of a dependence graph corresponding to the loop, but which only contains loop-independent dependence edges. A start node simulating a previous iteration of the loop may be added to the dependence graph, and an end node simulating a next iteration of the loop may also added to the dependence graph. A loop-independent edge between a source node and the start node is added to the dependence graph, and a loop-independent edge between a sink node and the end node is added to the dependence graph. Loop-carried edges which satisfy a computed lower bound on the time required for a single loop iteration are eliminated from a dependence graph, and loop-carried edges which do not satisfy the computed lower bound are replaced by a pair of loop-independent edges. Instructions may be scheduled for execution based on the dependence graph.

대표청구항 ▼

[ We claim:] [1.] A method of scheduling a plurality of instructions of a loop for execution by a processor having a lookahead buffer, said method comprising the steps of:constructing a dependence graph comprising nodes and edges corresponding to the loop;constructing a loop-independent dependence g

[ We claim:] [1.] A method of scheduling a plurality of instructions of a loop for execution by a processor having a lookahead buffer, said method comprising the steps of:constructing a dependence graph comprising nodes and edges corresponding to the loop;constructing a loop-independent dependence graph by removing a loop-carried edge from the dependence graph; andscheduling the instructions for execution based on the loop-independent dependence graph.