Method for collapsing the prolog and epilog of software pipelined loops

• US 20020112228A1
• Filed: 12/07/2000
• Published: 08/15/2002
• Est. Priority Date: 12/29/1999
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Ward, Alan S., Stotzer, Eric J., Granston, Elana D., Zbiciak, Joseph
• Granted Patent: US 6,754,893 B2
• Time in Patent Office: Days
• US Class Current: 717/155
• CPC Class Codes: G06F 8/4452 Software pipelining

Abstract

A method for reducing a code size of a software pipelined loop, the software pipelined loop having a kernel and an epilog. The method includes first evaluating a stage of the epilog. This includes selecting a stage of the epilog to evaluate (504) and evaluating an instruction in a reference stage. This includes identifying an instruction in the reference stage that is not present in the selected stage of the epilog (506) and determining if the identified instruction can be speculated (508). If the identified instruction can be speculated, such is noted. If the instruction cannot be speculated, it is determined whether the identified instruction can be predicated (512). If the instruction can be predicated, it is marked as needing predication (514). Next, it is determined if another instruction in the reference stage is not present in the selected stage of the epilog (510). If there is, the instruction evaluation is repeated. If there is another stage of the epilog to evaluate, the evaluation is repeated (518).

Claims

1. A method for reducing a code size of a software pipelined loop having a kernel and an epilog, comprising:

evaluating at least one stage of the epilog, comprising;

selecting a stage of the epilog to evaluate;

evaluating at least one instruction in a reference stage, comprising identifying an instruction in the reference stage that is not present in the selected stage of the epilog;

determining if the identified instruction can be speculated;

noting that the identified instruction can be speculated responsive to a determination that the identified instruction can be speculated;

determining if the identified instruction can be predicated responsive to a determination that the identified instruction cannot be speculated;

marking the identified instruction as needing predication responsive to a determination that the identified instruction can be predicated;

determining if another instruction in the reference stage is not present in the selected stage of the epilog;

repeating the instruction evaluation responsive to a determination that there is another instruction in the reference stage not present in the selected stage of the epilog;

determining if there is another stage of the epilog to evaluate; and

repeating the evaluation of the stage responsive to a determination that there is another instruction in the reference stage not present in the selected stage of the epilog.

2. The method of claim 1, wherein the reference stage is the kernel.

3. The method of claim 1, wherein the reference stage is a previously evaluated stage.

4. The method of claim 1, further comprising:

collapsing the epilog.

5. The method of claim 1, further comprising:

collapsing the selected stage of the epilog responsive to a determination that there is not another instruction in the reference stage not present in the selected stage of the epilog.

6. The method of claim 1, further comprising:

speculating the instructions noted as capable of being speculated; and

predicating the instructions marked as being capable of being predicated.

7. The method of claim 1, further comprising:

speculating the instructions noted as capable of being speculated; and

predicating the instructions marked as being capable of being predicated.

8. A method for reducing a code size of a software pipelined loop having a prolog and a kernel, comprising:

evaluating at least one stage of the prolog, comprising;

selecting a stage of the prolog to evaluate;

evaluating at least one instruction in a reference stage, comprising

identifying an instruction in the reference stage that is not present in the selected stage of the prolog;

determining if the identified instruction can be speculated;

noting that the identified instruction can be speculated responsive to a determination that the identified instruction can be speculated;

determining if the identified instruction can be predicated responsive to a determination that the identified instruction cannot be speculated;

marking the identified instruction as needing predication responsive to a determination that the identified instruction can be predicated;

determining if another instruction in the reference stage is not present in the selected stage of the prolog;

repeating the instruction evaluation responsive to a determination that there is another instruction in the reference stage not present in the selected stage of the prolog;

determining if there is another stage of the prolog to evaluate; and

repeating the evaluation of the stage responsive to a determination that there is another instruction in the reference stage not present in the selected stage of the prolog.

9. The method of claim 8 wherein the reference stage is the kernel.

10. The method of claim 8 wherein the reference stage is a previously evaluated stage.

11. The method of claim 8, further comprising:

collapsing the prolog.

12. The method of claim 8, further comprising:

collapsing the selected stage of the prolog responsive to a determination that there is not another instruction in the reference stage not present in the selected stage of the prolog.

13. The method of claim 8, further comprising:

speculating the instructions noted as capable of being speculated; and

predicating the instructions marked as being capable of being predicated.

14. The method of claim 8, further comprising:

speculating the instructions noted as capable of being speculated; and

predicating the instructions marked as being capable of being predicated.

16. The method of claim 15, further comprising:

determining if the selected innermost unprocessed cycle is the innermost cycle of the candidate stage.

17. The method of claim 16, further comprising

unmarking all marked instructions in the selected innermost unprocessed cycle responsive to a determination that the selected innermost unprocessed cycle is not the innermost cycle of the candidate stage;

determining if a branch can be inserted so that it occurs before the selected innermost unprocessed cycle;

partially collapsing the candidate stage responsive to a determination that a branch can be inserted; and

selecting a next innermost cycle and repeating the determination of whether the selected innermost unprocessed cycle is the innermost cycle of the candidate stage responsive to a determination that the selected innermost unprocessed cycle is not the innermost cycle for the candidate stage.

18. The method of claim 15 wherein the reference stage is the kernel.

19. The method of claim 15 wherein the reference stage is a previously evaluated stage.

20. The method of claim 15, further comprising:

speculating the instructions noted as capable of being speculated; and

predicating the instructions marked for predication.

15. A method for reducing a code size of a software pipelined loop having a prolog and a kernel, said kernel having a plurality of cycles, comprising:

evaluating at least one stage of the prolog, comprising;

selecting a candidate stage of the prolog to evaluate;

evaluating at least one cycle of the prolog, comprising;

selecting an innermost unprocessed cycle of the selected stage to evaluate, comprising;

evaluating at least one instruction in a reference stage, comprising

identifying an instruction in a cycle of the reference stage that is not present in a corresponding cycle of the candidate stage;

determining if the identified instruction can be speculated;

noting that the identified instruction can be speculated responsive to a determination that the identified instruction can be speculated;

determining if the identified instruction can be predicated responsive to a determination that the identified instruction cannot be speculated;

marking the identified instruction as predicated responsive to a determination that the identified instruction can be predicated;

determining if another instruction in the reference stage is not present in the selected cycle of the prolog;

repeating the instruction evaluation responsive to a determination that there is another instruction in the reference stage not present in the corresponding cycle of the prolog;

determining if there is another cycle of the candidate stage of the prolog to evaluate;

repeating the cycle evaluation responsive to a determination that there is another cycle to evaluate;

determining if there is another stage of the prolog to evaluate; and

repeating the evaluation of the stage responsive to a determination that there is another stage of the prolog to evaluate.