Hardware supported software pipelined loop prologue optimization

• US 6,954,927 B2
• Filed: 10/04/2001
• Issued: 10/11/2005
• Est. Priority Date: 02/17/1999
• Status: Expired due to Term

• Current Assignee: Elbrus International Limited
• Original Assignee: Elbrus International Limited
• Inventors: Ostanevich, Alexander Y.
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): Kendall, Chuck
• Application Number:
  US09/972,337
• Publication Number:
  US 20020133813A1
• Time in Patent Office: 1,468 Days
• Field of Search: 717136-160, 712/4, 712/8, 712/241
• US Class Current: 717/160
• CPC Class Codes: G06F 8/452 Loops
• CPC Class Codes: G06F 9/3824 Operand accessing

Abstract

A method for optimizing a software pipelineable loop in a software code is provided. The loop comprises one or more pipelined stages and one or more loop operations. The method comprises evaluating an initiation interval time (IN) for a pipelined stage of the loop. A loop operation time latency (Tld) and a number of loop operations (Np) from the pipelined stages to peel based on IN and Tld is then determined. The loop operation is peeled Np times and copied before the loop in the software code. A vector of registers is allocated and the results of the peeled loop operations and a result of an original loop operation is assigned to the vector of registers. Memory addresses for the results of the peeled loop operations and original loop operation are also assigned.

Claims

1. A method for optimizing a software pipelineable loop in a software code, wherein the loop comprises one or more pipelined stages and one or more loop operations, the method comprising:

(a) evaluating an initiation interval time (IN) for a pipelined stage of the loop;

(b) determining a loop operation time latency (Tld);

(c) determining a number of loop operations (Np) from the pipelined stages to peel based on IN and Tld;

(d) peeling Np copies of the loop operation, wherein the number of peeled loop operations equals (Tld+IN−

1)/IN;

(e) copying the peeled loop operations before the loop in the software code;

(f) allocating a vector of registers;

(g) assigning results of the peeled loop operations and a result of an original loop operation to the vector of registers; and

(h) assigning memory addresses to the results of the peeled loop operations and original loop operation.

2. The method of claim 1, wherein the initiation interval time comprises a number clock cycles for a number of stages required to execute a loop kernel.

3. The method of claim 1, wherein the one or more loop operations comprises one or more load operations.

4. The method of claim 3, wherein steps (d)-(h) are repeated for every load operation.

5. The method of claim 1, wherein the vector of registers is a length of Np+1.

6. The method of claim 1, further comprising generating a software code based on the optimization.

7. The method of claim 1, wherein allocating a vector of registers comprises allocating a vector of registers with a rotating Base.

8. An apparatus for optimizing a software pipelineable loop in a software code, wherein the loop comprises one or more pipelined stages and one or more loop operations, the apparatus comprising:

(a) instructions for evaluating an initiation interval time (IN) for a pipelined stage of the loop;

(b) instructions for determining a loop operation time latency (Tld);

(c) instructions for determining a number of loop operations from the pipelined stages to peel (Np) based on the IN and Tld;

(d) instructions for peeling Np copies of the loop operation, wherein the number of peeled loop operations equals (Tld+IN−

1)/IN;

(e) instructions for copying the peeled loop operations before the loop in the software code;

(f) instructions for allocating a vector of registers;

(g) instructions for assigning results of the peeled loop operations and a result of an original loop operation to the vector of registers; and

(h) instructions for assigning memory addresses to the results of the peeled loop operations and original loop operation.

9. The apparatus of claim 8, wherein the initiation interval time comprises a number clock cycles for a number of stages required to execute a loop kernel.

10. The apparatus of claim 8, wherein the one or more loop operations comprises one or more load operations.

11. The apparatus of claim 10, wherein steps (d)-(h) are repeated for every load operation.

12. The apparatus of claim 8, wherein the vector of registers is a length of Np+1.

13. The apparatus of claim 8, further comprising instructions for generating a software code based on the optimization.

14. The apparatus of claim 8, wherein the instructions for allocating a vector of registers comprises instructions for allocating a vector of registers with a rotating Base.

15. A method for optimizing a software pipelineable loop in a software code, wherein the loop comprises one or more pipelined stages and one or more loop operations, the method comprising:

(a) evaluating an initiation interval time (IN) for a pipelined stage of the loop;

(b) determining a loop operation time latency (Tld);

(c) determining a number of loop operations (Np) from the pipelined stages to peel based on IN and Tld;

(d) peeling Np copies of the loop operation;

(e) copying the peeled loop operations before the loop in the software code;

(f) allocating a vector of registers, wherein the vector of registers is a length of Np+1;

(g) assigning results of the peeled loop operations and a result of an original loop operation to the vector of registers; and

(h) assigning memory addresses to the results of the peeled loop operations and original loop operation.

16. The method of claim 15, wherein the initiation interval time comprises a number clock cycles for a number of stages required to execute a loop kernel.

17. The method of claim 15, wherein the one or more loop operations comprises one or more load operations.

18. The method of claim 17, wherein steps (d)-(h) are repeated for every load operation.

19. The method of claim 15, wherein the number of peeled loop operations equals (Tld+IN−

1)/IN.

20. The method of claim 15, further comprising generating a software code based on the optimization.

21. The method of claim 15, wherein allocating a vector of registers comprises allocating a vector of registers with a rotating Base.

22. An apparatus for optimizing a software pipelineable loop in a software code, wherein the loop comprises one or more pipelined stages and one or more loop operations, the method comprising:

(a) instructions for evaluating an initiation interval time (IN) for a pipelined stage of the loop;

(b) instructions for determining a loop operation time latency (Tld);

(c) instructions for determining a number of loop operations (Np) from the pipelined stages to peel based on IN and Tld;

(d) instructions for peeling Np copies of the loop operation;

(e) instructions for copying the peeled loop operations before the loop in the software code;

(f) instructions for allocating a vector of registers, wherein the vector of registers is a length of Np+1;

(g) instructions for assigning results of the peeled loop operations and a result of an original loop operation to the vector of registers; and

(h) instructions for assigning memory addresses to the results of the peeled loop operations and original loop operation.

23. The apparatus of claim 22, wherein the initiation interval time comprises a number clock cycles for a number of stages required to execute a loop kernel.

24. The apparatus of claim 22, wherein the one or more loop operations comprises one or more load operations.

25. The apparatus of claim 24, wherein steps (d)-(h) are repeated for every load operation.

26. The apparatus of claim 22, wherein the number of peeled loop operations equals (Tld+IN−

1)/IN.

27. The apparatus of claim 22, further comprising instructions for generating a software code based on the optimization.

28. The apparatus of claim 22, wherein the instructions for allocating a vector of registers comprises instructions for allocating a vector of registers with a rotating Base.