Software pipelining
View Patent ↗A software pipelining method for generating a schedule for executing a plurality of instructions on a processor, the plurality of instructions involving one or more variables, the processor having one or more physical registers, the method comprising the step of scheduling each of the plurality of instructions, determining whether there is a variable for which there is less than a threshold number of physical registers to which that variable may be allocated, and unscheduling a currently scheduled instruction when there is a variable for which there is less than the threshold number of a physical registers to which that that variable may be allocated.
1. A software pipelining method for generating a schedule for executing a plurality of instructions on a processor, the plurality of instructions involving one or more virtual registers, the processor having one or more physical registers, the method comprising the steps of:
scheduling each of the plurality of instructions;
determining, dynamically on an instruction by instruction basis for each of the instructions in the plurality of instructions, whether there is a virtual register for which there is less than a threshold number of physical registers to which the virtual register may be allocated in a currently scheduled instruction; and
unscheduling the currently scheduled instruction associated with the virtual register while leaving other instructions of the plurality of instructions as scheduled when there is less than the threshold number of physical registers to which that the virtual register may be allocated.
2. A method according to claim 1 , in which the step of determining whether there is the virtual register for which there is less than the threshold number of physical registers to which the virtual register may be allocated comprises determining whether there is no physical register to which the virtual register may be allocated.
3. A method according to claim 1 , in which the step of determining is performed each time an instruction is scheduled.
4. A method according to claim 1 , comprising the step of:
for each of the one or more virtual registers, storing an indicator associated with the virtual register, the indicator indicating which of the one or more physical registers the virtual register may be allocated to;
wherein the step of determining is dependent upon the indicator associated with each of the one or more virtual registers.
5. A method according to claim 4 , comprising the step of:
initializing the indicator associated with the virtual register to indicate that the virtual register may be allocated to a physical register only if, for each instruction involving that virtual register, that instruction may use the physical register for the virtual register.
6. A method according to claim 4 , comprising the step of:
updating the indicator associated with the virtual register in accordance with a constraint on the one or more physical registers to which the virtual register may be allocated, the constraint resulting from two or more instructions being scheduled for execution at a same time, at least one of the instructions involving the virtual register.
7. A method according to claim 6 , comprising the step of:
when an instruction is unscheduled, re-initializing the indicator associated with the virtual register and updating the indicator in accordance with the constraint on the one or more physical registers to which the virtual register may be allocated, the constraint resulting from two or more instructions being scheduled for execution at a same time, at least one of the instructions involving the virtual register.
8. A method according to claim 1 , comprising the steps of:
having generated a schedule, determining whether each of the one or more virtual registers may be allocated to a physical register to which no other virtual register is to be allocated; and
generating a different schedule when the virtual register cannot be allocated to the physical register to which no other virtual register is to be allocated.
9. A method according to claim 1 , in which the software pipelining method is performed in accordance with iterative modulo scheduling.
10. A method according to claim 9 , in which the iterative modulo scheduling comprises detecting whether there is a resource conflict between two or more instructions that have been scheduled and unscheduling the currently scheduled instruction when the resource conflict has been detected, wherein simulating the resource conflict when there is less than the threshold number of physical registers to which the virtual register may be allocated.
11. A non-transitory computer readable medium comprising a plurality of instructions to manipulate a processor, the plurality of instructions when executed by the processor cause the processor to perform the steps comprising:
scheduling each of a plurality of instructions;
determining, dynamically on an instruction by instruction basis for each of the instructions in the plurality of instructions, whether there is a virtual register for which there is less than a threshold number of physical registers to which the virtual register may be allocated in a currently scheduled instruction; and
unscheduling the currently scheduled instruction associated with the virtual register while leaving other instructions of the plurality of instructions as scheduled when there is less than the threshold number of physical registers to which that the virtual register may be allocated.
12. A method according to claim 2 , in which the step of determining is performed each time an instruction is scheduled.
13. A method according to claim 2 , comprising the step of:
for each of the one or more virtual registers, storing an indicator associated with the virtual register, the indicator indicating which of the one or more physical registers that the virtual register may be allocated to;
wherein the step of determining is dependent upon the indicator associated with each of the one or more virtual registers.
14. A method according to claim 3 , comprising the step of:
for each of the one or more virtual registers, storing an indicator associated with the virtual register, the indicator indicating which of the one or more physical registers that the virtual register may be allocated to;
wherein the step of determining is dependent upon the indicator associated with each of the one or more virtual registers.
15. A method according to claim 5 , comprising the step of:
updating the indicator associated with the virtual register in accordance with a constraint on the one or more physical registers to which the virtual register may be allocated, the constraint resulting from two or more instructions being scheduled for execution at a same time, at least one of the instructions involving the virtual register.
16. A method according to claim 2 , comprising the steps of:
having generated a schedule, determining whether each of the one or more virtual registers may be allocated to a physical register to which no other virtual register is to be allocated; and
generating a different schedule when the virtual register cannot be allocated to the physical register to which no other virtual register is to be allocated.
17. A method according to claim 3 , comprising the steps of:
having generated a schedule, determining whether each of the one or more virtual registers may be allocated to a physical register to which no other virtual register is to be allocated; and
generating a different schedule when the virtual register cannot be allocated to the physical register to which no other virtual register is to be allocated.
18. A method according to claim 4 , comprising the steps of:
having generated a schedule, determining whether each of the one or more virtual registers may be allocated to a physical register to which no other virtual register is to be allocated; and
generating a different schedule when the virtual register cannot be allocated to the physical register to which no other virtual register is to be allocated.
19. A method according to claim 2 , in which the software pipelining method is performed in accordance with iterative modulo scheduling.
20. A method according to claim 3 , in which the software pipelining method is performed in accordance with iterative modulo scheduling.