Methods and apparatus to reduce a control flow graph using points-to information

• US 20060047681A1
• Filed: 08/27/2004
• Published: 03/02/2006
• Est. Priority Date: 08/27/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Cox, Robert J., Sehr, David C., Ghiya, Rakesh
• Granted Patent: US 7,634,765 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis

Abstract

Methods and apparatus for reducing a control flow graph are disclosed. A disclosed method comprises: creating a points-to set associated with a function in a computer program; determining if a control flow edge between: (1) a call-site associated with a restore and return instruction and (2) a successor block following the call-site is removable from a control flow graph representing the computer program; and removing the control flow edge if it is determined that the control flow edge is removable.

Claims

1. A method comprising:

creating a points-to set associated with a function in a computer program;

determining if a control flow edge between;

(1) a call-site associated with a restore and return instruction and (2) a successor block following the call-site is removable from a control flow graph representing the computer program; and

removing the control flow edge between the call-site and the successor block if it is determined that the control flow edge is removable.

2. A method as defined in claim 1 wherein creating a points-to set comprises:

creating a first points-to set associated with a first function in the computer program, the first points-to set comprising a first runtime environment, wherein the first runtime environment is associated with a restore and return instruction in the first function; and

updating the first points-to set to include a second runtime environment associated with a non-restore and return instruction.

3. A method as defined in claim 2, wherein the first runtime environment comprises at least one of a variable value, an object value, a stack pointer value, or a register values.

4. A method as defined in claim 2, wherein the restore and return instruction is a longjmp instruction.

5. A method as defined in claim 4, wherein a pointer to a setjmp buffer storing the first runtime environment is an argument to the longjmp instruction.

6. A method as defined in claim 2, wherein the restore and return instruction is configured to restore the first runtime environment and to return control to a block following a predetermined instruction.

7. A method as defined in claim 6, wherein the predetermined instruction is configured to save the first runtime environment.

8. A method as defined in claim 6, wherein the predetermined instruction is a setjmp instruction.

9. A method as defined in claim 8, wherein a pointer to a setjmp buffer is an argument to the setjmp instruction.

10. A method as defined in claim 1, wherein determining if the control flow edge may be removed comprises:

creating an intersection set comprising an intersection of a points-to set associated with a function called by the call-site and a runtime environment associated with the restore and return instruction associated with the call-site; and

(b) determining if the intersection set satisfies a predetermined condition.

11. A method as defined in claim 10, wherein the predetermined condition is the intersection set is an empty set.

12. An apparatus comprising:

a points-to set creator to create a points-to set associated with a function in a computer program;

an application phase module to determine if a control flow edge between;

(1) a call-site associated with a restore and return instruction and (2) a successor block following the call-site is removable from a control flow graph representing the computer program; and

a control flow graph module responsive to the application phase module to remove the control flow edge between the call-site and the successor block.

13. An apparatus as defined in claim 12 wherein the points-to set creator comprises:

a summary phase module to create a first points-to set associated with a first function in the computer program, the first points-to set comprising a first runtime environment, wherein the first runtime environment is associated with a restore and return instruction in the first function; and

a propagation phase module to update the first points-to set to include a second runtime environment associated with a non-restore and return instruction.

14. An apparatus as defined in claim 13, wherein the first runtime environment comprises at least one of a variable value, an object value, a stack pointer value, or a register values.

15. An apparatus as defined in claim 13, wherein the restore and return instruction is a longjmp instruction.

16. An apparatus as defined in claim 15, wherein a pointer to a setjmp buffer storing the first runtime environment is an argument to the longjmp instruction.

17. An apparatus as defined in claim 13, wherein the restore and return instruction is configured to restore the first runtime environment and to return control to a block following a predetermined instruction.

18. An apparatus as defined in claim 17, wherein the predetermined instruction is configured to save the first runtime environment.

19. An apparatus as defined in claim 17, wherein the predetermined instruction is a setjmp instruction.

20. An apparatus as defined in claim 19, wherein a pointer to a setjmp buffer is an argument to the setjmp instruction.

21. An apparatus as defined in claim 12, wherein the application phase module determines if the control flow edge between the call-site and the successor block following the call-site may be deleted from the control flow graph by:

(a) creating an intersection set comprising an intersection of a points-to set associated with a function called by the call-site and a runtime environment associated with the restore and return instruction associated with the call-site, and (b) determining if the intersection set satisfies a predetermined condition.

22. An apparatus as defined in claim 21, wherein the predetermined condition is the intersection set is an empty set.

23. A machine accessible medium storing machine executable instructions which, when executed, cause a machine to:

create a points-to set associated with a function in a computer program;

determine if a control flow edge between;

(1) a call-site associated with a restore and return instruction and (2) a successor block following the call-site may be removed from a control flow graph representing the computer program; and

remove the control flow edge between the call-site and the successor block if it is determined that the control flow edge is removable.

24. A machine accessible medium as defined in claim 23 wherein the machine executable instructions cause the machine to create a points-to set by:

creating a first points-to set associated with a first function in the computer program, the first points-to set comprising a first runtime environment, wherein the first runtime environment is associated with a restore and return instruction in the first function; and

updating the first points-to set to include a second runtime environment associated with a non-restore and return instruction.

25. A machine accessible medium as defined in claim 23, wherein the machine executable instructions cause the machine to determine if the control flow edge is removable by:

creating an intersection set comprising an intersection of a points-to set associated with a function called by the call-site and a runtime environment associated with the restore and return instruction associated with the call-site; and

(b) determining if the intersection set satisfies a predetermined condition.

26. A machine accessible medium as defined in claim 25, wherein the predetermined condition is the intersection set is an empty set.

27. A system comprising:

a memory storing a computer program; and

a processor to execute the computer program to create a points-to set associated with a function in a computer program;

determine if a control flow edge between;

(1) a call-site associated with a restore and return instruction and (2) a successor block following the call-site is removable from a control flow graph representing the computer program; and

to remove the control flow edge between the call-site and the successor block if it is determined that the control flow edge is removable.

28. A system as defined in claim 27 wherein the memory comprises SRAM.