Partial redundancy elimination with a fixed number of temporaries

• US 10,223,089 B1
• Filed: 10/27/2017
• Issued: 03/05/2019
• Est. Priority Date: 08/30/2017
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Perron, Steven J.
• Primary Examiner(s): Dao, Thuy
• Application Number:
  US15/795,861
• Publication Number:
  US 20190065163A1
• Time in Patent Office: 494 Days
• CPC Class Codes: G06F 8/434 Pointers; Aliasing
• CPC Class Codes: G06F 8/4435 Detection or removal of dead or redundant code

Abstract

A method for partial redundancy elimination with a fixed number of temporaries includes determining local data values of program code that describe a temporary memory location, a set of registers, and a set of basic blocks. The method determines global data values of the program code based on the determined local data values of the program code. The method removes a first load of the temporary memory location in a first basic block in the program code. The method adds a second load on a first edge from a second basic block out of the set of basic blocks to a third basic block out of the set of basic blocks in the program code. The method performs a register move on a second edge from the third basic block to the second basic block in the program code.

Claims

1. A method comprising:

in a single pass through a program code divided into a plurality of basic blocks, identifying, by one or more processors, for each basic block, a set of local data values that includes;

a temporary memory location identifier, a register identifier of a set of registers, and a basic block identifier of the basic block;

for each basic block of the set of basic blocks, determining, by one or more processors, global register status values for the registers identified in the basic block, wherein the global register status values indicate whether a register is available, partially available, anticipatable, or partially anticipatable, and wherein the global register status values are determined based on machine operations on the identified registers across the plurality of basic blocks;

removing, by one or more processors, based on the determined global register status values meeting a first set of requirements, a first load of the temporary memory location into a second register, from a first basic block out of the plurality of basic blocks;

on a first edge from a second basic block out of the plurality of basic blocks to the first basic block, adding, by one or more processors, based on the determined global register status values meeting a second set of requirements, a second load of the temporary memory location into the second register; and

on a second edge from the first basic block to the second basic block, performing, by one or more processors, based on the determined global register status values meeting a third set of requirements, a register move, wherein the first register is moved into the second register.

2. The method of claim 1, wherein the first set of requirements includes:

the first basic block with the second register is locally anticipatable;

the second basic block is a predecessor block with the first register being partially available; and

a safety check for preventing new execution paths of the second basic block is present in the program code.

3. The method of claim 1, wherein the second set of requirements includes:

the second basic block with the first register is partially unavailable;

or

a safety check for preventing new execution paths of the second basic block is not present in the program code.

4. The method of claim 1, wherein the second set of requirements includes:

a safety check for preventing new execution paths of the first basic block is present in the code; and

the first basic block with the second register is partially anticipatable and locally available.

5. The method of claim 1, wherein the second set of requirements includes:

a safety check for preventing new execution paths of the second basic block is not present in the program code;

or

the second basic block with the first register is partially unavailable.

6. The method of claim 1, wherein the third set of requirements includes:

the second basic block with the first register is partially available and locally anticipatable.

7. The method of claim 1, wherein the second basic block is a predecessor block and the first basic block is a successor block.