Hardware supported software pipelined loop prologue optimization

• US 20020133813A1
• Filed: 10/04/2001
• Published: 09/19/2002
• Est. Priority Date: 02/17/1999
• Status: Active Grant

• Current Assignee: Elbrus International Limited
• Original Assignee: Elbrus International Limited
• Inventors: Ostanevich, Alexander Y.
• Granted Patent: US 6,954,927 B2
• Time in Patent Office: Days
• US Class Current: 717/150
• 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;

(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 number of peeled loop operations equals (Tld+IN−

1)/IN.

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

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

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

9. 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;

(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.