Generating storage reference instructions in an optimizing compiler

• US 4,656,582 A
• Filed: 02/04/1985
• Issued: 04/07/1987
• Est. Priority Date: 02/04/1985
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hopkins, Martin E., Warren, Henry S. Jr., Markstein, Peter W., Chaitin, Gregory J.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/697,675
• Time in Patent Office: 792 Days
• Field of Search: 364/300
• US Class Current: 717/153
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

A method for improving the quality of code generated by a compiler in terms of execution time, object code space, or both. The method is applicable to computers that have a redundancy of instructions, in that the same operation exists in forms that operate between registers, between main storage locations, and between registers and main storage. The method selects the best form of each such instruction to use, for the context in which the instruction lies.

Claims

1. A method for use in an optimizing compiler for generating code for subsequent machine execution which is more efficient in terms of storage references, said method comprising,

first generating intermediate code that completely avoids the SR, RS and SS instructions for arithmetic-like data, said code referring to main memory only via "load" and "store" instructions, and wherein all computations are done in registers (register ops) using symbolic RR instructions, optimizing the program by standard techniques including commoning, code motion out of loops, strength reduction, dead code elimination, and

locating predetermined patterns in the code, comprising a `load` op followed by a `register` op or a `store` op referring to the same object(s) and replacing these patterns with a shorter instruction sequence of SR, RS or SS instructions if said predetermined patterns exist.

2. A method for use during the instruction selection phase of an optimizing compiler after the intermediate language generation phase in which all arithmetic operations are defined in terms of symbolic register ops and in which all memory operations are defined in terms of load and store ops and combined with necessary register ops, said method comprising;

sequentially accessing the intermediate code instructions and processing the same as follows;

determining if an instruction is a label, if so obtaining the next instruction, if not,

determining if it is a load instruction, if not, obtaining the next instruction, if so,

determining first if it and the following instructions corresponds to a first pattern of a load operation followed by a register operation followed by a store operation all involving the same objects, if so,

replacing the store operation by the RS form of the operation and deleting the load operation and the register operation and accessing the next instruction,

if the operation sequence did not follow the pattern,

determining second if the following instructions correspond to a second pattern of a load operation followed by a register operation, if so,

replacing the register operation by its SR form and deleting the load operation, and if the operation sequence did not follow this pattern,

determining third if the following instructions correspond to a third pattern of a load operation followed by a store operation, if so,

replacing the store instruction by an SS move instruction and deleting the load instruction and obtaining the next instruction, if none of the three patterns specified are present, obtaining the next instruction in the sequence.

3. A method as set forth in claim 2 wherein an additional test is made for all three patterns whereby the replacement procedure is modified to retain any operand or result in a register if it is determined that it will be used again in the instruction sequence.

4. A method as set forth in claim 2 wherein, before the specified program alterations are made responsive to a successful search for the first pattern, including the further step of,

determining if the following criteria are met:

(a) no stores nor subroutine calls between the load operation and store operation,

(b) no sets of corresponding `index` or `base` registers between the load operation and store operation,

(c) no use of r1 between the load operation and store operation, including index and base registers in the store operation itself,

(d) no sets of r2 between the register operation and store operation,

(e) r1 is last used at the store operation, and

(f) register operation has an equivalent RS format instruction "op_-- rs,"

(where r1 and r2 are register operands) and,

proceeding to the next step in the sequence if not all of the above criteria are met.

5. A method as set forth in claim 2 wherein, before the specified program alterations are made responsive to a successful search for the second pattern, including the further step of,

determining if the following criteria are met:

(a) no stores nor subroutine calls between the load operation and register operation,

(b) no sets of corresponding `index` or `base` registers between the load operation and register operation,

(c) no use of r1 between the load operation and register operation,

(d) r1 is last used at the register operation, and

(e) the register operation has an equivalent SR format instruction "op_-- sr,"

(where r1 is a register operand) and,

proceeding to the next step in the sequence if not all of the above criteria are met.

6. A method as set forth in claim 2 wherein, before the specified program alterations are made responsive to a successful search for the third pattern, including the further step of, determining if the following criteria are met:

(a) no stores nor subroutine calls between the load operation and store operation,

(b) no sets of corresponding `index` or `base` registers between the load operation and store operation,

(c) no use of r1 between the load operation and store operation,

(d) r1 is last used at the store operation, and

(e) the load/store pair has an equivalent storage-to-storage move instruction that is preferable to the load/store pair,

(where r1 is a register operand) and,

obtaining the next instruction in the sequence if not all of the above criteria are met.

7. A method for use in an optimizing compiler for generating code for subsequent machine execution which is more efficient in terms of storage references, said method comprising,

first generating intermediate code that completely avoids the SR, RS and SS instructions for arithmetic-like data, said code referring to main memory only via "load" and "store" instructions, and wherein all computations are done in registers (register ops) using symbolic RR instructions,

optimizing the program by standard techniques including commoning, code motion out of loops, strength reduction, dead code elimination,

locating predetermined patterns in the code, comprising a `load` op followed by a `register` op or a `store` op referring to the same object and replacing these patterns with a different pattern of SR, RS or SS instructions if said predetermined patterns exist,

assigning real registers to each instruction by replacing each symbolic register with a real machine register, and generating "spill" code where necessary and again,

locating said predetermined patterns in the code produced by the previous step and replacing these patterns with a different pattern of SR, RS or SS instructions if said predetermined patterns exist and,

generating machine code from the intermediate code produced by said previous step.