Method and apparatus for improving performance of out of sequence load operations in a computer system

• US 5,542,075 A
• Filed: 10/07/1994
• Issued: 07/30/1996
• Est. Priority Date: 05/06/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kronstadt, Eric P., Kumar, Manoj, Ebcioglu, Mahmut K.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Richey, Michael T.
• Application Number:
  US08/320,111
• Time in Patent Office: 662 Days
• Field of Search: 395/650, 395/700, 395/800
• US Class Current: 717/151
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency

Abstract

The invention provides for improved performance of out of sequence load operations. The system has an improved compiler, with an optimizer, an improved CPU with four new instructions in its instruction set, and an address compare unit (ACU). During compilation, the improved compiler identifies load operations that can be move out of sequence ahead of associated store operations and moves those load operations out of sequence and flags them as such. The associated store operations are also flagged. During processor execution of a compiled and optimized program, the address of operands fetched by the out of sequence load operations are saved to the new associative memory. On request, the ACU compares the addresses saved to the addresses generated by the associated store operations. If a comparison results in an identity between the address of a store operation and an address of the out of sequence load operation, a recovery code is run to correct the problem, if not the system continues to execute the program in its compiled order. The system also has the ability to work in a multiprogramming or multitasking environment.

Claims

1. A method for improving the execution performance of out of sequence load operations with the use of a processor and a dedicated address compare unit (ACU) for comparing a memory address against a stored set of addresses, which method comprises:

(a) executing a compiled optimized program with the processor, said complied optimized program having a load operation identified and out of sequence ahead of a store operation, said store operation being identified and preceding said load operation in an uncompiled form of said compiled optimized program, said load operation being out of sequence ahead of said store operation in said compiled optimized program so as to optimize execution performance;

(b) saving to the ACU during said executing step (a) an address of an operand fetched by the out of sequence load operation and comparing the saved address with an address generated by the store operation during compiled optimized program execution;

(c) if the addresses are different, completing the store operation and continuing said executing step (a) of the compiled optimized program;

(d) if the addresses are identical, aborting the store operation and providing for recovery of the program; and

wherein execution of said compiled optimized program produces a same output as an execution of said program in a compiled unoptimized form having said load operation in sequence and following said store operation.

2. The method of claim 1, further including the step of clearing the saved address in the ACU after the saved address is compared with the address generated by the associated store operation.

3. The method of claim 1, wherein the step of providing for recovery of the program comprises the steps of completing the aborted store operation, then executing the load operation, and executing any operations which follow the load operation in an unoptimized form of the program, depend on the load operation and were moved ahead of the store operation as a result of the optimization.

4. The method of claim 3, further comprising the step of resuming the execution of the optimized program immediately after the aborted store operation upon completion of execution of the recovery program.

5. The method of claim 1, further including the step of providing said program having a plurality of load operations and a plurality of store operations, and wherein said steps (a), (b), (c) and (d) are repeated for each load operation of said plurality of load operations and are repeated for each store operation of said plurality of store operations.

6. The method of claim 3, further including the step of providing said program having a plurality of load operations and a plurality of store operations, and wherein said steps (a), (b), (c) and (d) are repeated for each load operation of said plurality of load operations and are repeated for each store operation of said plurality of store operations.

7. The method of claim 1, further comprising the steps of:

transferring the address saved during the load operation from the ACU to a different memory location to facilitate execution of a different program, and then, at a later time, returning the transferred address to the ACU to resume execution of the compiled optimized program.

8. The method of claim 6, applied to a multi-programming environment further comprising the steps of:

transferring addresses saved during load operations from original memory locations in the ACU to different memory locations to facilitate execution of a different program, and then, at a later time, returning the transferred addresses to the original memory locations in the ACU to resume execution of the compiled optimized program.

9. The method of claim 1, wherein:

the step of identifying the load operation moved out of sequence comprises changing a load instruction to a load-save instruction;

the step of identifying the store operation comprises changing a store instruction to a store-check instruction;

the saving step is implemented in response to the load-save instruction; and

said comparing step is implemented in response to the store-check instruction.

10. The method of claim 6, wherein:

identifying each load operation moved out of sequence comprises changing a load instruction to a load-save instruction;

identifying each store operation comprises changing a store instruction to a store-check instruction;

the saving step is implemented in response to each load-save instruction; and

the comparing step is implemented in response to each store-check instruction.

11. A system for improving performance of out of sequence load operations comprising:

compiling means for during compilation and optimization of a program having a first output corresponding to an execution of a compiled unoptimized form of said program;

identifying a load operation that can be moved out of sequence ahead of a store operation,

storing the identified load operation out of sequence, ahead of said store operation in a compiled optimized program, so as to improve execution performance,

and identifying the store operation before which the load operation has been moved in the compiled optimized program;

processor means for execution of the compiled optimized program to produce said first output;

dedicated means for saving during said execution of the compiled optimized program an address of an operand fetched by the load operation moved out of sequence;

dedicated means for comparing the saved address with an address generated by the store operation during said execution of the compiled optimized program;

means for completing the store operation and continuing execution of the compiled optimized program in sequence if the compared addresses are different; and

means for aborting the store operation and providing for recovery of the program if the compared addresses are identical.

12. The apparatus of claim 11, further comprising means for clearing the saved address after the saved address is compared with the address assigned to the store operation.

13. The apparatus of claim 11, wherein the means for providing for recovery of the program comprises means for completing the aborted store operation, then executing the load operation, and executing any operations which follow the load operation in an unoptimized form of the program, depend on the load operation and were affected by moving the load operation ahead of the store operation as a result of the optimization of the compiled optimized program.

14. The apparatus of claim 13, further comprising means for resuming the execution of the compiled optimized program immediately after the aborted store operation upon completion of the recovery of the compiled optimized program.

15. The apparatus of claim 11, wherein said compiling means, said processor means, said dedicated means for saving, said dedicated means for comparing, said means for completing and said means for aborting further comprise means for performing a plurality of load operations and a plurality of store operations.

16. The apparatus of claim 13, wherein said compiling means, said processor means, said dedicated means for saving, said dedicated means for comparing, said means for completing and said means for aborting further comprise means for performing a plurality of load operations and a plurality of store operations.

17. The apparatus of claim 11, further comprising means for:

transferring the saved address from an ACU to a different memory location to facilitate execution of a different program, and then, at a later time, returning the saved address to the ACU to resume execution of the compiled optimized program.

18. The apparatus of claim 16, further comprising means for transferring a plurality of addresses saved during the load operations from an ACU to a different memory to facilitate execution of a different program, and then, at a later time, returning the plurality of addresses to the ACU to resume execution of the compiled and optimized program.

19. The apparatus of claim 11, wherein the means for identifying the load operation moved out of sequence comprises means to change a load instruction to a load-save instruction;

the means for identifying the store operation comprises means to change a store instruction to a store-check instruction; and

the means for saving and the means for comparing perform these steps in response to the load-save instruction and the store-check instruction, respectively.

20. The apparatus of claim 16, wherein the means for identifying each load operation moved out of sequence comprises means for changing a load instruction to a load-save instruction;

the means for identifying each store operation comprises means for changing a store instruction to a store-check instruction; and

the means for saving and means for comparing perform these steps in response to each load-save operation and each store-check operation, respectively.

21. An improved apparatus comprising a programmed processor for compiling and optimizing an uncompiled computer program for execution by a processor having an address compare unit (ACU), said uncompiled computer program having a first output corresponding to an execution of a compiled unoptimized form of said uncompiled computer program, said programmed processor comprising:

means to identify and flag a load operation of said uncompiled computer program which can be moved ahead of a store operation, said store operation having preceded the load operation in said uncompiled computer program;

means to store and flag the store operation in a compiled optimized program; and

means to store the identified and flagged load operation ahead of the store operation in the compiled optimized program to facilitate execution of said compiled optimized program to produce said first output, whereby during said execution of said compiled optimized program by said processor having said ACU, said store operation facilitates a comparison by said ACU of an address referenced by said load operation with an address referenced by said store operation.

22. An improved compiler as claimed in claim 21, further comprising means for inserting a recovery sequence in the compiled optimized program to be used during execution of the compiled optimized program if an address of an operand fetched by the load operation is identical to an address generated by the store operation during execution of the compiled optimized program.

23. The improved compiler of claim 21, further comprising means for adding to the compiled optimized program a clear instruction to clear an address saved during the load operation after comparison of the saved address with an address generated by the store operation during execution of the compiled optimized program.

24. The improved compiler of claim 21, wherein the means to flag the load operation comprises means for changing the load operation to a load-save operation.

25. The improved compiler of claim 21, wherein the means to flag the store operation comprises means to change the store operation to a store-check operation.

26. The improved compiler of claim 21, wherein a plurality of load operations which can be moved ahead of store operations are identified, flagged and so moved in the compiled optimized program, and a plurality of store operations before which the load operations are moved are flagged in the compiled optimized program.

27. The improved compiler of claim 26, wherein the means to flag load operations moved ahead of store operations comprises means for changing a load instruction for each load operation to a load-save instruction.

28. The improved compiler of claim 26, wherein the means to flag each store operation which has a load operation moved ahead of it comprises means to change a store instruction related to each store operation to a store-check instruction.

29. The improved compiler of claim 23 further comprising means for adding, during compilation of the program, the clear instruction to a target of a branch operation if the out of sequence load has been moved ahead of said branch operation.

30. A method for optimizing a computer program during program compilation with a programmed processor, said computer program for execution by a processor having an address compare unit (ACU), said computer program having a first output corresponding to an execution of a compiled unoptimized form of said computer program, said method comprising:

identifying and flagging a load operation which can be moved ahead of a store operation, said store operation having preceded the load operation in an uncompiled form of the program;

flagging the store operation; and

storing said identified and flagged load operation ahead of the store operation in a compiled optimized program to facilitate execution of said compiled optimized program to produce said first output, whereby during said execution of said compiled optimized program by said processor having said ACU, said store operation facilitates a comparison by said ACU of an address referenced by said load operation with an address referenced by said store operation.

31. The method of claim 30, further comprising the step of inserting a recovery sequence in the compiled optimized program, during compilation of the computer program to be used during execution of the compiled optimized program if an address of an operand fetched by the load operation is identical to an address generated by the store operation during execution of the compiled optimized program.

32. The method of claim 30, further comprising the step of adding to the compiled optimized program during compilation an instruction to clear any address saved during the load operation after comparison of that saved address with an address assigned to the associated store operation during execution of the compiled optimized program.

33. The method of claim 30, wherein the step of flagging the load operation is accomplished by changing a load instruction to a load-save instruction.

34. The method of claim 30, wherein the step of flagging the store operation comprises changing a store instruction to a store-check instruction.

35. The method of claim 30 further comprising the steps of identifying and flagging a plurality of load operations which can be moved ahead of a plurality of store operations and so moving the plurality of load operations and flagging the plurality of store operations before which the plurality of load operations have been moved in the compiled optimized program.

36. The method of claim 35, wherein the step of flagging load operations moved ahead of store operations comprises changing a load instruction to a load-save instruction for each load moved ahead of a store operation.

37. The method of claim 35, wherein the step of flagging said store operations comprises changing a store instruction to a store-check instruction for each associated store operation.

38. The method of claim 32 further comprising the step of adding, during compilation of the program, the clear instruction to a target of a branch instruction if the load operation has been moved ahead of said branch operation.

39. A system for performing out of sequence load operations of a compiled optimized program, said compiled optimized program having a flagged load operation moved out of sequence ahead of a flagged store operation, said system comprising:

a processor and associated address compare unit (ACU);

the processor comprising;

means for executing the compiled program having said flagged load operation moved out of sequence ahead of said flagged store operation, means for recognizing the flagged load operation and saving to the ACU an address of an operand fetched by the load operation, and means for recognizing the flagged store operation and generating an address by the store operation;

the ACU comprising means to compare the saved address with the address generated by the store operation; and

wherein the ACU facilitates said executing said compiled optimized program to produce a same output as an executing of a compiled unoptimized form of said compiled optimized program, said compiled unoptimized form having said load operation in sequence and following said store operation.

40. The system of claim 39, wherein the ACU further comprises means for sending a signal to the processor when the address saved during the out of sequence load operation is identical to the address generated by the store operation;

and the processor further comprises means for implementing a recovery routine in response to said signal.

41. The system of claim 39, further comprising means to clear the address saved during the load operation after it has been compared with the address generated by the associated store operation.

42. The system of claim 39, wherein the flagged load operation comprises a load-save instruction and the means for recognizing and saving to the ACU the address of an operand fetched by the load operation comprises means for executing the load-save instruction.

43. The system of claim 39, wherein the flagged store operation comprises a store-check instruction and the means for recognizing the store operation and comparing the address generated by the store operation with the address saved during the load operation comprises means for executing the store-check instruction.

44. A method for performing, on a processor with a dedicated address compare unit, out of sequence load operations of a compiled optimized program, said compiled optimized program having a load operation moved out of sequence ahead of a store operation in said compiled optimized program, said method comprising the steps of:

executing the compiled optimized program including executing the out of sequence load operation on the processor;

during said executing;

recognizing the load operation and saving an address of an operand fetched by the load operation in said dedicated address compare unit and recognizing the store operation and generating an address by the store operation;

comparing in said dedicated address compare unit the saved address with the address generated by the store operation;

implementing a recovery routine when the comparing step indicates that the saved address is identical to the address generated by the store operation, said recovery routine including the step of resuming said executing the compiled optimized program and providing for proper executing of said load operation; and

wherein said executing said compiled optimized program produces a same output as an executing of a compiled unoptimized form of said compiled optimized program, said compiled and unoptimized form having said load operation in sequence and following said store operation.

45. The method of claim 44, further comprising the step of clearing the address saved during the load operation after it has been compared with the address generated by the store operation.

46. The method of claim 44, wherein the step of recognizing and saving the address of the operand fetched by the load operation is accomplished by execution of a load-save instruction.

47. The method of claim 44, wherein the steps of recognizing the store operation and comparing the address generated thereby with the address saved during the load operation comprises execution of a store-check instruction.

48. The method of claim 44, wherein the recited steps are repeated for each load operation of a plurality of load operations moved out of sequence and are repeated for each store operation of a plurality of store operations.

49. An address compare unit for use in a system for performing out of sequence load operations during execution of a compiled and optimized program, said compiled and optimized program having a load operation moved out of sequence ahead of a store operation, said address compare unit comprising:

means for saving an address of an operand fetched by the load operation, said load operation being stored out of sequence ahead of the store operation in the compiled and optimized program;

means for comparing the saved address with an address generated by the store operation during execution of the compiled and optimized program;

means for generating a signal when the compared saved address is identical to the address generated by the store operation; and

wherein said address compare unit facilitates execution of said compiled and optimized program producing a same output as an execution of a compiled and unoptimized form of said compiled and optimized program, said compiled and unoptimized form having said load operation in sequence and following said store operation.

50. The apparatus of claim 49, further comprising means for clearing the saved address after comparison with the address generated by the store operation.

51. The apparatus of claim 49, further comprising means for transferring the saved address to an external memory location prior to execution of a different program and means for recalling the transferred address from the external memory location prior to resumption of execution of the compiled and optimized program.

52. The apparatus of claim 49, wherein the means for saving comprises means for saving respective addresses of a plurality of operands fetched by a plurality of out of sequence load operations;

and the means for comparing comprises means for comparing said respective addresses with addresses generated by any store operations.

53. The address compare unit of claim 50 wherein the means for saving, clearing, comparing and generating a signal comprises a memory register, a valid bit location, and a control port which work together as a unit.

54. The address compare unit of claim 53 wherein there are a plurality of such units.

55. The address compare unit of claim 54 further comprising a decoder activating the units.

56. The apparatus of claim 52 wherein the means for saving comprises a plurality of memory registers;

the means for clearing comprises a plurality of valid bit locations; and

the means for transferring, comparing and generating a signal comprises a plurality of control ports.

57. The apparatus of claim 56 wherein the plurality of memory registers, valid bits and control units are grouped together into units comprising one memory register, one valid bit and one control port.

58. An improved processor having an instruction set including a load-save instruction and a store-check instruction comprising:

means for implementing the load-save instruction by performing a load operation and saving an address of an operand fetched by the load operation;

means for implementing the store-check instruction by generating an address for the store operation and initiating comparison of the generated address with the saved address;

dedicated means for comparing the generated address with the saved address; and

means for running a recovery sequence when said comparison indicates the generated address is identical to the saved address, wherein said recovery sequence is generated during compilation and optimization of a computer program containing said load-save instruction and said store-check instruction.

59. The improved processor of claim 58 further comprising means for running of a recovery sequence when said comparison indicates the generated address of the store operation is identical to the address saved during the load operation.

60. The apparatus of claim 58 further comprising means for initiating transfer and subsequent recall of the address saved during the load operation to accommodate a multi-programming application.