Eliminating store/restores within hot function prolog/epilogs using volatile registers

• US 7,017,154 B2
• Filed: 03/14/2002
• Issued: 03/21/2006
• Est. Priority Date: 03/23/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haber, Gad, Klausner, Moshe, Eisenberg, Vadim
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): Kiss, Eric B.
• Application Number:
  US10/096,827
• Publication Number:
  US 20020196678A1
• Time in Patent Office: 1,468 Days
• Field of Search: 717/151, 717/159, 717/158
• US Class Current: 717/159
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 9/4486 Formation of subprogram jump address

Abstract

A post-link optimization method for renaming non-volatile registers with unused volatile registers, then removing the non-volatile register store/restore instructions from a function prolog/epilog. The volatile registers are saved before each function call and restored immediately afterwards. The optimization method is worthwhile if all of the call instructions are rarely invoked relative to the function prolog/epilog. The method requires that the hot function be disassembled, but does not require the full control flow graph.

Claims

1. A computer-implemented method for code optimization, comprising:

disassembling object code that has been compiled and linked;

analyzing the disassembled code so as to identify a first function in the code, the first function including store and restore instructions with respect to one or more non-volatile registers and further including a call instruction to a second function, which second function is performed infrequently when the first function is run;

identifying one or more volatile registers unused in the first function; and

modifying the code so as to replace each reference in the first function to at least one of the non-volatile registers with a reference to a corresponding one of the identified volatile registers, and so as to eliminate at least one pair of the store and restore instructions in the first function with respect to the at least one of the non-volatile registers while storing the corresponding one of the identified volatile registers before the call instruction to the second function and restoring the corresponding one of the identified volatile registers after the call instruction to the second function, whereby a number of the store and restore instructions is reduced in the first function and increased in the second function.

2. A method according to claim 1, wherein analyzing the disassembled code comprises profiling the code so as to determine a frequency of calls made by the first function, including the call instruction to the second function, and wherein modifying the code comprises modifying the first function only if the frequency of the calls is less than one call each time the first function is run.

3. A method according to claim 1, wherein modifying the code comprises replacing the call instruction with a branch to a wrapper code that contains the call instruction, together with store and restore instructions with respect to the corresponding one of the volatile registers.

4. A method according to claim 3, wherein the object code comprises a fixed sequence of code instructions ending with a last instruction, and wherein the wrapper code is added to the code after the last instruction, and wherein replacing the call instruction comprises replacing the instruction with the branch to the wrapper code without altering the fixed sequence within the code.

5. A method according to claim 3, wherein analyzing the code comprises identifying a further one of the non-volatile registers to which there is no reference made in the first function, and modifying the code comprises eliminating at least one pair of the store and restore instructions in the first function with respect to the further one of the non-volatile registers, while adding store and restore instructions to the wrapper code with respect to the further one of the non-volatile registers.

6. A method according to claim 1, wherein the function comprises a fixed sequence of code instructions, and modifying the code comprises replacing the at least one pair of the store and restore instructions with NOP instructions.

7. A method according to claim 1, wherein modifying the code to eliminate the at least one pair of the store and restore instructions comprises reordering the instructions so as to make the store instruction a first instruction in the first function, and further modifying control transfers to the first function in the code so as to skip over the store instruction.

8. A method according to claim 1, wherein the first function comprises a final instruction to transfer control upon completion of the first function, and wherein modifying the code to eliminate the at least one pair of the store and restore instructions comprises reordering the instructions so as to make the restore instruction a last instruction in the first function before the instruction to transfer control, and further replacing the restore instruction with the control transfer instruction.

9. A method according to claim 1, wherein the at least one pair of the store and restore instructions comprises a single instruction that acts upon a plurality of registers, and wherein modifying the code to eliminate the at least one pair of the store and restore instructions comprises modifying the single instruction to act upon a subset of the plurality of registers.

10. A method according to claim 1, wherein modifying the code comprises recompiling the object code.

11. A method according to claim 1, wherein storing the corresponding one of the volatile registers comprises saving a value of the corresponding one of the volatile registers to a memory location reserved on a program stack for the at least one of the non-volatile registers.

12. An apparatus for code optimization, comprising a code processor, which is arranged to disassemble object code that has been compiled and linked, to analyze the disassembled code so as to identify a first function in the code, the first function including store and restore instructions with respect to one or more non-volatile registers and further including a call instruction to a second function, which second function is performed infrequently when the first function is run, to identify one or more volatile registers unused in the first function, and to modify the code so as to replace each reference in the first function to at least one of the non-volatile registers with a reference to a corresponding one of the identified volatile registers, and so as to eliminate at least one pair of the store and restore instructions in the first function with respect to the at least one of the non-volatile registers while storing the corresponding one of the identified volatile registers before the call instruction to the second function and restoring the corresponding one of the identified volatile registers after the call instruction to the second function, whereby a number of the store and restore instructions is reduced in the first function and increased in the second function.

13. An apparatus according to claim 12, wherein the code processor is arranged to profile the code so as to determine a frequency of calls made by the first function, including the call instruction to the second function, and wherein the code processor is arranged to modify the code only if the frequency of the calls is less than one call each time the first function is run.

14. An apparatus according to claim 12, wherein the code processor is arranged to replace the existing call instruction with a branch to a wrapper code that contains the call instruction, together with store and restore instructions with respect to the corresponding one of the volatile registers.

15. An apparatus according to claim 14, wherein the object code comprises a fixed sequence of code instructions ending with a last instruction, and wherein the code processor is arranged to add the wrapper code after the last instruction, and to replace the call instruction with the branch to the wrapper code without altering the fixed sequence within the code.

16. An apparatus according to claim 14, wherein the code processor is arranged to identify a further one of the non-volatile registers to which there is no reference made in the first function, to eliminate at least one pair of the store and restore instructions in the first function with respect to the further one of the non-volatile registers, and to add store and restore instructions to the wrapper code with respect to the further non-volatile registers.

17. An apparatus according to claim 12, wherein the code processor is arranged to modify the code so as to replace the at least one pair of the store and restore instructions with NOP instructions.

18. An apparatus according to claim 12, wherein the code processor is arranged to modify the code by reordering the instructions so as to make the store instruction a first instruction in the first function, and by modifying control transfers to the first function in the code so as to skip over the store instruction.

19. An apparatus according to claim 12, wherein the first function comprises a final instruction to transfer control upon completion of the first function, and wherein the code processor is arranged to reorder the instructions so as to make the restore instruction a last instruction in the first function before the instruction to transfer control, and further by replacing the restore instruction with the control transfer instruction.

20. An apparatus according to claim 12, wherein the at least one pair of the store and restore instructions comprises a single instruction that acts upon a plurality of registers, and wherein the code processor is arranged to eliminate the at least one pair of the store and restore instructions by modifying the single instruction to act upon a subset of the plurality of registers.

21. An apparatus according to claim 12, wherein the code processor is arranged to modify the code by recompiling the object code.

22. An apparatus according to claim 12, wherein the code processor is arranged to modify the code so that a value of the corresponding one of the volatile registers is saved to a memory location reserved on a program stack for the at least one of the non-volatile registers.

23. A computer software product, comprising a computer-readable medium in which software is stored, which software, when read by a computer, causes the computer to disassemble object code that has been compiled and linked, to analyze the disassembled code so as to identify a first function in the code, the first function including store and restore instructions with respect to one or more non-volatile registers and further including a call instruction to a second function, which second function is performed infrequently when the first function is run, to identify one or more volatile registers unused in the first function, and to modify the code so as to replace each reference in the first function to at least one of the non-volatile registers with a reference to a corresponding one of the identified volatile registers, and so as to eliminate at least one pair of the store and restore instructions in the first function with respect to the at least one of the non-volatile registers while storing the corresponding one of the identified volatile registers before the call instruction to the second function and restoring the corresponding one of the identified volatile registers after the call instruction to the second function, whereby a number of the store and restore instructions is reduced in the first function and increased in the second function.

24. A product according to claim 23, wherein the software causes the computer to profile the code so as to determine a frequency of calls made by the first function, including the call instruction to the second function, and wherein the software causes the computer to modify the code only if the frequency of calls is less than one call each time the first function is run.

25. A product according to claim 23, wherein the software causes the computer to replace the call instruction with a branch to a wrapper code that contains the call instruction, together with store and restore instructions with respect to the corresponding one of the volatile registers.

26. A product according to claim 25, wherein the object code comprises a fixed sequence of code instructions ending with a last instruction, and wherein the software causes the computer to add the wrapper code after the last instruction, and to replace the call instruction with the branch to the wrapper code without altering the fixed sequence within the code.

27. A product according to claim 25, wherein the software causes the computer to identify a further one of the non-volatile registers to which there is no reference made in the first function, to eliminate at least one pair of the store and restore instructions in the first function with respect to the further one of the non-volatile registers, and to add store and restore instructions to the wrapper code with respect to the further one of the non-volatile registers.

28. A product according to claim 23, wherein the software causes the computer to modify the code so as to replace the at least one pair of the store and restore instructions with NOP instructions.

29. A product according to claim 23, wherein the software causes the computer to modify the code by reordering the instructions so as to make the store instruction a first instruction in the first function, and by modifying control transfers to the first function in the code so as to skip over the store instruction.

30. A product according to claim 23, wherein the first function comprises a final instruction to transfer control upon completion of the first function, and wherein the software causes the computer to reorder the instructions so as to make the restore instruction a last instruction in the first function before the instruction to transfer control, and further to replace the restore instruction with the control transfer instruction.

31. A product according to claim 23, wherein the at least one pair of the store and restore instructions comprises a single instruction that acts upon a plurality of registers, and wherein the software causes the computer to eliminate the at least one pair of the store and restore instructions by modifying the single instruction to act upon a subset of the plurality of registers.

32. A product according to claim 23, wherein the software causes the computer to modify the code by causing a recompilation of the object code.

33. A product according to claim 23, wherein the software causes the computer to modify the code so that a value of the corresponding one of the volatile registers is saved to a memory location reserved on a program stack for the at least one of the non-volatile registers.