Computer system and a method for generating an optimized program code

Patent metadata

Field	Value
Publication number	US-9513922-B2
Application number	US-201214395103-A
Country	US
Kind code	B2
Filing date	Apr 20, 2012
Priority date	Apr 20, 2012
Publication date	Dec 6, 2016
Grant date	Dec 6, 2016

Abstract

A computer system for generating an optimized program code from a program code having a loop with an exit branch, wherein the computer system comprises a processing unit, wherein the processing unit is arranged to convert an exit instruction of the exit branch into a predicated exit instruction, wherein the processing unit is arranged to determine common dependencies within the loop, wherein the processing unit is arranged to generate modified dependencies by adding additional dependencies to the common dependencies, and wherein the processing unit is arranged to apply an algorithm that uses software pipelining for generating an optimized program code for the loop based on the modified dependencies.

First claim

The invention claimed is:

1. A computer system for generating an optimized program code from a program code having a loop with an exit branch, the computer system comprising:
a compiler program including an algorithm stored on a computer readable storage medium; and
a processing unit coupled to the computer readable storage medium to execute the compiler program to:
convert first and second non-predicated exit instructions of corresponding first and second exit branches of a program loop of program code for a target processor, each of the first and second exit branches to exit the program loop, into a corresponding first and second predicated exit instruction of the corresponding first and second exit branches, the first exit branch having a first destination;
determine common dependencies for dependencies between loop instructions within the program loop;
determine additional dependencies for dependencies between the first and second predicated exit instructions and the loop instructions within the program loop, the additional dependencies comprising:
a first group of dependencies including dependencies between the first predicated exit instruction and a prior loop instruction of the program loop that is a write memory instruction or a write register instruction, wherein a write register of the write register instruction is used outside of the program loop, and the prior loop instruction is either non-predicated or is predicated; and
a second group of dependencies comprising dependencies between the first predicated exit instruction and a following loop instruction that is a read memory instruction;

generate modified dependencies based on the common dependencies and the additional dependencies to exclude dependencies that are resolved by a load speculation scheme;
apply the algorithm to implement software pipelining for the program loop of the target processor based on the modified dependencies; and
convert the first predicated exit instruction of the first exit branch into a third non-predicated exit instruction of a third branch having a third destination that is different than the first destination of the first exit branch after the algorithm has been applied.

2. The computer system as claimed in claim 1 , wherein the additional dependencies comprise:
a third group of dependencies comprising dependencies between the predicated exit instruction and a following loop instruction that is a non-predicated write instruction.

3. The computer system as claimed in claim 2 ,
wherein the processing unit is arranged to replace a read instruction that is associated with the second group of dependencies by a non-faulting read instruction.

4. The computer system as claimed in claim 1 , wherein the processing unit is arranged to remove at least one of the modified dependencies based on a directive instruction that manually indicates an independency.

5. The computer system as claimed in claim 1 , wherein the processing unit is arranged to add at least one dependency to the modified dependencies based on a directive instruction that manually indicates a dependency.

6. The computer system as claimed in claim 1 , wherein the processing unit is arranged to generate a loop prolog, a loop kernel, and a loop epilog when the algorithm is completed.

7. The computer system as claimed in claim 1 , wherein the processing unit is arranged to apply further optimizing algorithms to the optimized program code.

8. The computer system as claimed in claim 1 ,
wherein the processing unit is arranged to check the program loop based on a test, and
wherein the processing unit is arranged to apply the algorithm to the program loop when the program loop passes the test.

9. The computer system as claimed in claim 1 , wherein the processing unit is arranged to apply the algorithm to the program loop based on a directive instruction that marks the program loop for applying the algorithm.

10. A method for generating comprising:
converting, by a compiler program including an algorithm stored on a computer readable storage medium executed by a processing unit coupled to the computer readable storage medium, first and second non-predicated exit instructions of corresponding first and second exit branches of a program loop of program code for a target processor, each of the first and second exit branches to exit the program loop, into a corresponding first and second predicated exit instruction of the corresponding first and second exit branches, the first exit branch having a first destination;
determining common dependencies for dependencies between loop instructions within the program loop;
determining additional dependencies for dependencies between the first and second predicated exit instructions and the loop instructions within the program loop, the additional dependencies comprising:
a first group of dependencies including dependencies between the first predicated exit instruction and a prior loop instruction of the program loop that is a write memory instruction or a write register instruction, wherein a write register of the write register instruction is used outside of the program loop, and the prior loop instruction is non-predicated or are predicated; and
a second group of dependencies comprising dependencies between the first predicated exit instruction and a following loop instruction that is a read memory instruction;

generating modified dependencies based on the common dependencies and the additional dependencies to exclude dependencies that are resolved by a load speculation scheme;
applying an algorithm to implement software pipelining for the program loop of the target processor based on the modified data dependencies; and
converting the first predicated exit instruction of the first exit branch into a third non-predicated exit instruction of a third branch having a third destination that is different than the first destination of the first exit branch.

11. A computer system comprising:
a compiler program including an algorithm stored on a computer readable storage medium; and
a processing unit coupled to the computer readable storage medium to:
execute the compiler program to:
convert first and second non-predicated exit instructions of corresponding first and second exit branches of a program loop of program code for a target processor, each of the first and second exit branches to exit the program loop, into a corresponding first and second predicated exit instruction of the corresponding first and second exit branches, the first exit branch having a first destination;
determine common dependencies for dependencies between loop instructions within the program loop;
determine additional dependencies for dependencies between the first and second predicated exit instructions and the loop instructions within the program loop, the additional dependencies comprising:
a first group of dependencies including dependencies between the first predicated exit instruction and a prior loop instruction of the program loop that is a write memory instruction or a write register instruction, wherein a write register of the write register instruction is used outside of the program loop, and the prior loop instruction is non-predicated or are predicated; and
a second group of dependencies comprising dependencies between the first predicated exit instruction and a following loop instruction that is a read memory instruction:

generate modified dependencies based on the common dependencies and the additional dependencies to exclude dependencies that are resolved by a load speculation scheme:
apply the algorithm to implement software pipelining for the program loop of the target processor based on the modifie

Assignees

• Palalau Rene Catalin
• Freescale Semiconductor Inc

Inventors

• Palalau Rene Catalin

Classifications

• G06F8/4441 Primary

  Reducing the execution time required by the program code · CPC title

• G06F9/3842 Primary

  Speculative instruction execution · CPC title

• G06F9/30072

  to perform conditional operations, e.g. using predicates or guards · CPC title

• G06F9/3858

  Result writeback, i.e. updating the architectural state or memory · CPC title

• G06F9/3836

  Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution · CPC title