Optimizing code by exploiting speculation and predication with a cost-benefit data flow analysis based on path profiling information

• US 5,999,736 A
• Filed: 05/09/1997
• Issued: 12/07/1999
• Est. Priority Date: 05/09/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gupta, Rajiv, Berson, David A., Fang, Jesse Z.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): ZHEN, WEI Y
• Application Number:
  US08/853,275
• Time in Patent Office: 942 Days
• Field of Search: 395/709
• US Class Current: 717/158
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

A method and apparatus for optimizing execution of code is disclosed. The code is executed to generate path profiling information. At least one location is identified for relocating at least one of the plurality of instructions in the code, where the at least one location is enabled by one of predication and speculation. A cost and a benefit are calculated for relocating the at least one of the plurality of instructions to the at least one location, the cost and the benefit based on the path profiling information. The at least one of the plurality of instructions is moved to the at least one location when the benefit exceeds the cost, and one of predication and speculation is performed on the one of the plurality of instructions. The code is then reexecuted.

Claims

1. A computer implemented method for optimizing execution of code, said code including a plurality of instructions, said method comprising:

executing said code to generate path profiling information;

identifying at least one location for relocating at least one of said plurality of instructions, said at least one location enabled by one of predication and speculation;

calculating a cost and a benefit for relocating said at least one of said plurality of instructions to said at least one location, said cost and said benefit based on said path profiling information;

moving said at least one of said plurality of instructions to said at least one location when said benefit exceeds said cost;

performing one of said speculation and said predication on said at least one of said plurality of instructions; and

re-executing said code.

2. The computer implemented method as claimed in claim 1 wherein moving said at least one of said plurality of instructions includes hoisting said at least one of said plurality of instructions and performing performs speculation.

3. The computer implemented method as claimed in claim 1 wherein moving said at least one of said plurality of instructions includes sinking said one of said plurality of instructions and performing performs predication.

4. The computer implemented method as claimed in claim 1 wherein identifying said at least one location for relocating said at least one of said plurality of instructions includes identifying at least one location for relocating more than one of said plurality of instructions.

5. The computer implemented method as claimed in claim 1 wherein identifying said at least one location for relocating said at least one of said plurality of instructions includes identifying more than one of said at least one location for relocating said at least one of said plurality of instructions.

6. A computer implemented method for eliminating a partially redundant instruction in a program, said program including a plurality of paths, said method comprising:

identifying at least one location for relocating said partially redundant instruction, said at least one location enabled by speculation;

examining path profile information for each of said plurality of paths;

generating cost-benefit data for each of said plurality of paths, said cost-benefit data being based on said path profile information;

hoisting said partially redundant instruction to said at least one location based on said cost-benefit data;

performing said speculation on said partially redundant instruction.

7. A computer implemented method for eliminating a partially dead instruction in a program, said program including a plurality of paths, said method comprising:

identifying at least one location for relocating said partially dead instruction, said at least one location enabled by predication;

examining path profile information for each of said plurality of paths;

generating cost-benefit data for each of said plurality of paths, said cost-benefit data being based on said path profile information;

sinking said partially dead instruction to a pre-determined location based on said cost-benefit data; and

performing said predication on said partially dead instruction.

8. A machine readable medium having stored thereon data representing sequences of instructions, which when executed by a computer system, cause said computer system to perform the steps of:

executing said code to generate path profiling information;

identifying at least one location for relocating at least one of a plurality of instructions in code, said at least one location enabled by one of predication and speculation;

calculating a cost and a benefit for relocating said at least one of said plurality of instructions to said at least one location, said cost and said benefit based on said path profiling information;

moving said at least one of said plurality of instructions to said at least one location when said benefit exceeds said cost;

performing one of said speculation and said predication on said at least one of said plurality of instructions; and

re-executing said code.

9. The machine readable medium according to claim 8 wherein said step of moving said at least one of said plurality of instructions includes hoisting said at least one of said plurality of instructions and said step of performing performs speculation.

10. The machine readable medium according to claim 8 wherein said step of moving said at least one of said plurality of instructions includes sinking said one of said plurality of instructions and said step of performing performs predication.

11. The machine readable medium according to claim 8 wherein said step of identifying said at least one location for relocating said at least one of said plurality of instructions includes the step of identifying at least one location for relocating more than one of said plurality of instructions.

12. The machine readable medium according to claim 8 wherein said step of identifying said at least one location for relocating said at least one of said plurality of instructions includes the step of identifying more than one of said at least one location for relocating said at least one of said plurality of instructions.

13. A machine readable medium having stored thereon data representing sequences of instructions, which when executed by a computer system, cause said computer system to perform the steps of:

identifying at least one location for relocating a partially redundant instruction in a program having a plurality of paths, said at least one location enabled by speculation;

examining path profile information for each of said plurality of paths;

generating cost-benefit data for each of said plurality of paths, said cost-benefit data being based on said path profile information;

hoisting said partially redundant instruction to said at least one location based on said cost-benefit data;

performing said speculation on said partially redundant instruction.

14. A machine readable medium having stored thereon data representing sequences of instructions, which when executed by a computer system, cause said computer system to perform the steps of:

identifying at least one location for relocating a partially dead instruction in a program having a plurality of paths, said at least one location enabled by predication;

examining path profile information for each of said plurality of paths;

generating cost-benefit data for each of said plurality of paths, said cost-benefit data being based on said path profile information;

sinking said partially dead instruction to a pre-determined location based on said cost-benefit data; and

performing said predication on said partially dead instruction.