Partial redundancy elimination with a fixed number of temporaries

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.

What is claimed is: 
     
       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.