METHOD AND SYSTEM FOR PROGRAM TRANSFORMATION USING FLOW-SENSITIVE TYPE CONSTRAINT ANALYSIS

• US 20090094588A1
• Filed: 12/11/2008
• Published: 04/09/2009
• Est. Priority Date: 09/25/2003
• Status: Active Grant

• Current Assignee: Lantronix Incorporated
• Original Assignee: Lantronix Incorporated
• Inventors: CHIPMAN, TIMOTHY
• Granted Patent: US 8,141,064 B2
• Time in Patent Office: Days
• US Class Current: 717/141
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 9/4488 Object-oriented

Abstract

A method for analyzing a program is provided. The method includes, determining an object type that may exist at an execution point of the program, wherein this enables determination of possible virtual functions that may be called; creating a call graph at a main entry point of the program; and recording an outgoing function call within a main function. The method also includes analyzing possible object types that may occur at any given instruction from any call path for virtual calls, wherein possible object types are determined by tracking object types as they pass through plural constructs; and calling into functions generically for handling specialized native runtime type information.

Claims

1. A method for analyzing a program, comprising:

determining a set of functions required by the program by performing local type constraint analysis at intermediate language instruction level; and

a call path that may reach a function containing such instruction.

2. The method of claim 1, further comprising:

analyzing a program instruction that accesses an object field, wherein the analysis is performed locally to an object instantiation.

3. The method of claim 1, further comprising:

analyzing a program instruction that accesses an array element locally to an array instantiation.

4. The method of claim 1, further comprising:

analyzing a program instruction that accesses runtime information for a local runtime symbol usage.

5. The method of claim 1, further comprising:

analyzing a program instruction within an exception handler performed locally to an exception instruction.

6. The method of claim 1, further comprising:

declaring possible return types of native functions, where a type analysis of intermediate language instruction is not possible.

7. The method of claim 6, wherein the set of functions may be in a single program image.

31. The method of claim 1, wherein the program runs in a managed runtime environment.

8. A computer-readable medium storing computer-executable process steps of a process for analyzing a program, comprising:

determining a set of functions required by the program by performing local type constraint analysis at intermediate language instruction level and a call path that may reach a function containing such instruction.

9. The computer readable medium of claim 8, further comprising:

analyzing a program instruction that accesses an object field, wherein the analysis is performed locally to an object instantiation.

10. The computer readable medium of claim 8, further comprising:

analyzing a program instruction that accesses an array element locally to an array instantiation.

11. The computer readable medium of claim 8, further comprising:

analyzing a program instruction that accesses runtime information for a local runtime symbol usage.

12. The computer readable medium of claim 8, further comprising:

analyzing a program instruction within an exception handler performed locally to an exception instruction.

13. The computer readable medium of claim 8, further comprising:

declaring possible return types of native functions, where a type analysis of intermediate language instruction is not possible.

14. The computer readable medium of claim 13, wherein the set of functions may be in a single program image.

32. The computer readable medium of claim 8, wherein the program ruins in a managed runtime environment.

15. A method for analyzing a program, comprising:

determining an object type that may exist at an execution point of the program and evaluating all possible object types that are created at every instruction of a program and carrying the object types through a stack evaluation, wherein this enables determination of a possible virtual function that may be called.

16. The method of claim 15, further comprising:

creating a call graph at a main entry point of the program; and

recording an outgoing function call within a main function.

17. The method of claim 16, further comprising:

analyzing possible object types that may occur at any given instruction from any call path for a virtual call.

18. The method of claim 17, wherein possible object types are determined by tracking object types as they pass through plural constructs.

19. The method of claim 15, further comprising:

calling into function generically for handling specialized native runtime type information.

33. The method of claim 15, wherein the program ruins in a managed runtime environment.

20. A computer-readable medium storing computer-executable process steps of a process

for analyzing a program, comprising:

determining an object type that may exist at an execution point of the program, wherein this enables determination of possible virtual functions that may be called.

21. The computer readable medium of claim 20, further comprising:

creating a call graph at a main entry point of the program; and

recording an outgoing function call within a main function.

22. The computer readable medium of claim 21 further comprising:

analyzing possible object types that may occur at any given instruction from a call path for virtual calls.

23. The computer readable medium of claim 22, wherein possible object types are determined by tracking object types as they pass through plural constructs.

24. The computer readable medium of claim 20, further comprising:

calling into functions generically for handling specialized native runtime type information.

34. The computer readable medium of claim 20, wherein the program runs in a managed runtime environment.

25. A method for building an application, comprising:

receiving source code instruction;

determining optimum code requirement; and

compiling native processor image.

26. The method of claim 25, wherein the optimum code is determined by performing a flow-sensitive analysis that determines possible types of objects that may exist at any instruction of a program.

27. The method of claim 26, wherein based on a set of constraints, virtual functions that have the potential of being executed are determined.

35. The method of claim 25, wherein the program runs in a managed runtime environment.

28. A computer-readable medium storing computer-executable process steps of a process for building an application, comprising:

receiving source code instruction;

determining optimum code requirement; and

compiling native processor.

29. The computer readable medium of claim 28, wherein the optimum code is determined by performing a flow-sensitive analysis that determines possible types of objects that may exist at any instruction of a program.

30. The computer readable medium of claim 29, wherein based on a set of constraints, virtual functions that have the potential of being executed are determined.

36. The computer readable medium of claim 28, wherein the program runs in a managed runtime environment.

37. A method for determining variable size in a program, comprising:

tracking variable size; and

reducing variable size for program execution.

38. The method of claim 37, wherein if a variable is discrete, then it is hard coded to a single value.

39. The method of claim 37, wherein if a first variable is assigned to a second variable, then a size constraint of the first variable is merged into a size constraint of the second variable.

40. A computer-readable medium storing computer-executable process steps of a process for determining variable size in a program, comprising:

analyzing program function calls recursively and tracking variable size; and

reducing variable size of program function calls for program execution.

41. The computer readable medium of claim 40, wherein if a variable is discrete, then it is hard coded to a single value.

42. The computer readable medium of claim 40, wherein if a first variable is assigned to a second variable, then a size constraint of the first variable is merged into a size constraint of the second variable.

43. A method for reducing empty function calls in a program, comprising:

determining if a call is made to an empty function; and

removing a call that is made to an empty function.

44. A computer-readable medium storing computer-executable process steps of a process for reducing empty function calls in a program, comprising:

determining if a call is made to an empty function;

removing a call that is made to an empty function.

45. A method for reducing throw instruction without exception handlers in a program, comprising:

determining if there are any throw instructions without exception handlers;

removing throw instructions without exception handlers.

46. A computer-readable medium storing computer-executable process steps of a process for reducing throw instruction without exception handlers in a program, comprising:

determining if there are any throw instructions without exception handlers; and

removing throw instructions without exception handlers.

47. A method for discarding comparison instructions in a program, comprising:

determining if there are any comparison instructions with discrete values in the program;

discarding a comparison instruction with a discrete value.

48. A computer-readable medium storing computer-executable process steps of a process for discarding comparison instructions in a program, comprising:

determining if there are any comparison instructions with discrete values in the program;

discarding a comparison instruction with a discrete value.