Expanding a software program by insertion of statements

• US 7,207,032 B1
• Filed: 03/28/2003
• Issued: 04/17/2007
• Est. Priority Date: 03/28/2003
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Applied Micro Circuits Corporation (MACOM Technology Solutions Holdings, Inc.)
• Inventors: Verbitsky, George
• Primary Examiner(s): NGUYEN BA, HOANG VU A
• Application Number:
  US10/402,663
• Time in Patent Office: 1,481 Days
• Field of Search: None
• US Class Current: 717/106
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

Every function that is called (“called function”) is expanded by insertion of several statements at the entry and exit thereof. Moreover, a calling function may also be expanded, by insertion of statements prior to and/or subsequent to a statement in which a called function is invoked. Many of the statements that are inserted contain new variables (called “synthetic variables”) to which registers are allocated during register allocation; the synthetic variables are not part of the originally-written software but are introduced during expansion, e.g. to transfer arguments to and return value from the called functions. Statements that are inserted can be either statements that are translated into assembly code in the normal manner, or alternatively dummy statements that contain instructions which are never translated into assembly code (i.e. ignored by the assembler. Use of dummy statements ensures that a web is established for new variables. After expansion, register allocation is performed.

Claims

1. A computer-implemented method for expanding a software program by insertion of statements, the method comprising:

inserting at entry of a function (“

called function”

) a label;

inserting at entry of the called function a first statement to define at least a new variable (“

argument variable”

), if the called function receives at least an argument;

automatically replacing each return statement in the called function with at least a statement that assigns to another new variable (“

return value variable”

) a value to be returned to a calling function, if the called function returns a value; and

inserting at the end of the called function, a second statement to use the return value variable, provided the called function returns a value;

wherein said software program comprises said called function and said calling function.

2. The method of claim 1 further comprising:

substituting, in the calling function, each statement that contains a call to the called function, with a jump instruction to the label inserted at entry of called function.

3. The method of claim 1 further comprising:

inserting a place holder statement at end of called function, after the last executable statement in the called function;

replacing, in called function, each return statement that is not at end of the called function, with at least a jump to the place holder statement; and

replacing the place holder statement with at least a statement to transfer control to the calling function.

4. The method of claim 1 further comprising, if the called function has an argument:

inserting at least one statement to define a variable (“

argument variable”

) to hold an argument value being passed to a called function; and

inserting after a statement that invokes the called function, yet another statement to use the argument variable.

5. The method of claim 1 further comprising, if the called function returns a value:

inserting after a statement that invokes the called function, yet another statement to define a variable that holds the value being returned.

6. The method of claim 1 wherein:

each of said first statement and said second statement is a dummy statement that is not to be executed.

7. The method of claim 1 further comprising, after said inserting of second statement:

allocating registers to a plurality of variables in the software program;

wherein said plurality of variables comprises said argument variable and return value variable.

8. A computer programmed to expand a software program by insertion of statements, the computer comprising:

means for inserting at entry of a function (“

called function”

) a label;

means for inserting at entry of the called function a dummy statement to define at least a new variable (“

argument variable”

), if the called function receives at least an argument;

means for replacing each return statement in the called function with a statement that assigns to another new variable (“

return value variable”

) a value to be returned to a calling function, if the called function returns a value; and

means for inserting at the end of the called function, another dummy statement to use the return value variable, provided the called function returns a value;

wherein said software program comprises said called function and said calling function.

9. The computer of claim 8 further comprising:

means for substituting, in the calling function, each statement that contains a call to the called function, with a jump instruction to the label inserted at entry of called function.

10. The computer of claim 8 further comprising:

means for inserting a place holder statement at end of called function, after the last executable statement in the called function;

means for replacing, in called function, each return statement that is not at end of the called function, with a jump to the place holder statement; and

means for replacing the place holder statement with a statement to transfer control to the calling function.

11. The computer of claim 8 further comprising:

means for checking if the called function has an argument;

means for inserting at least one statement to define a variable (“

argument variable”

) to hold an argument value being passed to a called function; and

means for inserting after a statement that invokes the called function, yet another dummy statement to use the argument variable.

12. The computer of claim 8 further comprising:

means for checking if the called function returns a value; and

means for inserting after a statement that invokes the called function, yet another dummy statement to define a variable that holds the value being returned.

13. The computer of claim 8 further comprising:

means for allocating registers to a plurality of variables in the software program;

wherein said plurality of variables comprises said argument variable and return value variable.

14. The computer of claim 8 wherein:

said statement is a dummy statement that is never translated into assembly code.