IR code instrumentation

• US 6,332,213 B1
• Filed: 09/15/1999
• Issued: 12/18/2001
• Est. Priority Date: 08/27/1996
• Status: Expired due to Term

• Current Assignee: Borland Software Corporation (Open Text Corporation)
• Original Assignee: Compuware Corporation (KKR & Co., Inc.)
• Inventors: Grossman, Franklin C., Angel, David C., Seidel, David A.
• Primary Examiner(s): DAM, TUAN QUANG
• Application Number:
  US09/396,852
• Time in Patent Office: 825 Days
• Field of Search: 717/4, 717/7, 717/8, 714/35, 714/38, 714/45
• US Class Current: 717/130
• CPC Class Codes: G06F 11/3644 by instrumenting at runtime

Abstract

Instrumenting a computer program includes examining an initial intermediate representation of the program, selecting portions of the initial intermediate representation for instrumentation, and instrumenting the portions. Selecting the portions may include choosing portions of the initial intermediate representation corresponding to pointer arithmetic operations, operations that reads memory locations, operations that change memory locations, and/or operations that causes program variables to become defined or undefined within the program. Instrumenting the portions may include adding run time code that provides a user with an indication when a run time error occurs.

Claims

1. A method of instrumenting a computer program, comprising:

(a) examining an initial intermediate representation of the program, wherein the initial intermediate representation is independent of source language for the program;

(b) selecting portions of the initial intermediate representation for instrumentation;

(c) instrumenting the portions; and

(d) creating an intermediate representation tree of nodes corresponding to intermediate representation operations and operands of the initial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands, wherein instrumenting the portions includes modifying the intermediate representation tree;

wherein said creating an intermediate represenation further imcluding;

interconnecting the nodes so that children nodes of an operator are operands thereof; and

placing the children nodes on a local stack and then popping the children nodes off the local stack to connect the children nodes to parents thereof.

2. A method according to claim 1, wherein selecting the portions includes choosing portions of the initial intermediate representation corresponding to at least one of:

pointer arithmetic operations, operations that reads memory locations, operations that change memory locations, and operations that causes program variables to become defined or undefined within the program.

3. A method according to claim 2, wherein instrumenting the portions includes adding run time code that provides a user with an indication when a run time error occurs.

4. A method according to claim 1, further comprising:

(e) following instrumenting the portions by modifying the intermediate representation tree, transforming the tree into an instrumented intermediate representation that is structurally equivalent to the initial intermediate representation.

5. A method of instrumenting a computer program, comprising:

(a) examining an initial intermediate representation of the program, wherein the initial intermediate representation is independent of source languagefor the program;

(b) selecting portions of the initial intermediate representation for instruction;

(c) instrumenting the portions;

(d) creating an effective scope table that correlates a unique scope identifier for each block of intermediate representation code contained within the intial intermediate representation to an effective scope identifier that indicates whether new program variables are defined within a each block of intermediate representation code; and

(e) in reponse to a first block of the intermediate representation code having a first effective scope identifier not equal to a second effective scope identifier of a second block of the intermediate represenation code that precedes the first block of the intermediate representation code, selecting for instrumentation a portion of the intermediate representation code corresponding to a transition between the first and second blocks.

6. The method of claim 5, wherein selecting the portions includes choosing portions of the initial intermediate representation corresponding to at least one of:

pointer arithmetic operations, operations that read memory locations, operations that change memory locations, and operations that cause program variables to become defined or undefined within the program.

7. The method of claim 6, wherein instrumenting the portions includes adding run time code that provides a user with an indication when a run time error occurs.

8. The method of claim 5, further comprising:

(f) creating an intermediate representation tree of nodes corresponding to intermediate representation operations and operands of the initial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands, wherein instrumenting the portions includes modifying the intermediate representation tree.

9. The method of claim 8, further comprising:

(g) following instrumenting the portions by modifying the intermediate representation tree, transforming the tree into an instrumented intermediate representation that is structurally equivalent to the initial intermediate representation.

10. The method of claim 8, wherein creating the intermediate representation tree includes interconnecting the nodes so that the children nodes of an operator are operands thereof.

11. The method of claim 10, wherein creating the intermediate representation tree includes placing the children nodes on a local stack and the popping the children nodes off the local stack to connect the children nodes to parents thereof.

12. A method of instrumenting a computer program, comprising:

(a) examining an initial intermediate representation of the program, wherein the initial intermediate representation is independent of source languagefor the program;

(b) selecting portions of the initial intermediate representation for instruction;

(c) instrumenting the portions;

(d) creating an effective scope table that correlates a unique scope identifier for each block of intermediate representation code contained within the intial intermediate representation to an effective scope identifier that indicates whether new program variables are defined within a each block of intermediate representation code; and

(e) in reponse to a first block of the intermediate representation code containing a label and having associated a therewith a first effective scope identifier not equal to a second effective scope identifier of a second block of the intermediate represenation code containing a control flow instruction to the label, selecting for instrumentation a portion of the Intermediate representation code corresponding to a transition between the control flow instruction and the label.

13. The method of claim 12, wherein selecting the portions includes choosing portions of the initial intermediate representation corresponding to at least one of:

pointer arithmetic operation, operation that reads memory locations, operation that changes memory location, and operation that causes program variables to become defined or undefined within the program.

14. The method of claim 13, wherein instrumenting the portions includes adding run time code that provides a user with an indication when a run time error occurs.

15. The method of claim 12, further comprising:

(f) creating an intermediate representation tree of nodes corresponding to intermediate representation operations and operands of the initial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands, wherein instrumenting the portions includes modifying the intermediate representation tree.

16. The method of claim 15, further comprising:

(g) following instrumenting the portions by modifying the intermediate representation tree, transforming the tree into an instrumented intermediate representation that is structurally equivalent to the initial intermediate representation.

17. The method of claim 15, wherein creating the intermediate representation tree includes interconnecting the nodes so that children nodes of an operator are operands thereof.

18. The method of claim 17, wherein creating the intermediate representation tree includes placing the children nodes on a local stack and then popping the children nodes off the local stack to connect the children nodes to parents thereof.

19. A method of instrumenting a computer program, comprising:

(a) examining an initial intermediate representation of the program;

(a) creating an intermediate representation tree of nodes corresponding to intermediate representation operations and operands of the intial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands;

(c) selecting portions of the initial intermediate representation for instrumentation; and

(d) instrumenting the portions by modifying the intermediate representation tree,

wherein creating the intermediate representation tree further including;

interconnecting the nodes so that children nodes of an operator are operands thereof; and

placing the children nodes on a local stack and then popping the children nodes off the local stack to connect the children nodes to parents thereof.

20. A method according to claim 19, wherein selecting the portions includes choosing portions of the initial intermediate representation corresponding to at least one of:

pointer arithmetic operations, operations that reads memory locations, operations that change memory locations, and operations that causes program variables to become defined or undefined within the program.

21. A method of intsrumenting a computer program, comprising:

(a) examining an initial intermediate representation of the program;

(b) creating an intermediate representation tree of nodes corresponding to intermediate representation operations and operands of the initial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands;

(c) selecting portions of the initial intermediate representation for instrumentation; and

(d) instrumenting the portions by modifying the intermediate representation tree;

(e) creating an effective scope table that correlates a unique scope identifier for each block of intermediate representation code contained within the initial intermediate representation to an effective scope identifier that indicates whether new program variables are defined with a each block of intermediate representation code; and

(f) in response to a first block of intermediate representation code having a first effective scope identifier not equal to a second effective scope identifier of a second block of intermediate representation code that precedes the first block of intermediate representation code, selecting for instructmentation a portion of the intermediate representation code corresponding to a transition between the first and second blocks.

22. The method of claim 21, wherein selecting the portions includes choosing portions of the initial intermediate representation corresponding to at least one of:

pointer arithmetic operations, operations that read memory locations, operations that change memory locations, and operations that cause program variables to become defined or undefined within the program.

23. The method of claim 21, wherein creating the intermediate representation tree includes interconnecting the nodes so that children nodes of an operator are operands thereof.

24. The method of claim 23, wherein creating the intermediate representation tree includes placing the children nodes on a local stack and then popping the children nodes off the local stack to connect the children nodes to parents thereof.

25. A method of instrumenting a computer program, comprising:

(a) examining an initial intermediate representation of the program;

(b) creating an intermediate representation tree of nodes corresponding to intermediate representation operations and operands of the initial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands;

(c) selecting portions of the initial intermediate representation for instrumentation; and

(d) instrumenting the portions by modifying the intermediate representation tree;

(e) creating an effective scope table that correlates a unique scope identifier for each block of intermediate representation code contained within the initial intermediate representation to an effective scope identifier that indicates whether new program variables are defined within a each block of intermediate representation code; and

(f) in response to a first block of the intermediate representation code containing a label and having associated therewith a first effective scope identifier not equal to a second effive scope Identifier of a second block of the intermediate representation code containing a control flow instruction to the label, selecting for instrumentation a portion of the intermediate representation code corresponding to a transition between the control flow instruction and the label.

26. The method of claim 25, wherein selecting the portions includes choosing portions of the initial intermediate representation corresponding to at least one of:

pointer arithmetic operations, operations that read memory locations, operations that change memory locations, and operations that cause program variables to become defined or undefined within the program.

27. The method of claim 25, wherein creating the intermediate representation tree includes interconnecting the nodes so that children nodes of an operator are operands thereof.

28. The method of claim 27, wherein creating the intermediate representation tree includes placing the children nodes on a local stack and then popping the children nodes off the local stack to connect the children nodes to parents thereof.

29. A computer program instrumenter, comprising:

(a) examining means for examining an initial intermediate representation of the program;

(b) creating means, coupled to the examining means, for creating an intermediate representation of tree nodes corresponding to intermediate representation operations and operands of the initial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands;

(c) selecting means, coupled to the examining means, for selecting portions of the initial intermediate representation for instrumentation; and

(d) instrumenting means, coupled to the creating means and the selecting means, for instrumenting the portions by modifying the intermediate representation tree,

wherein said creating means further including;

means for interconnecting the nodesso that children nodes of an operator are operands thereof; and

means for placing the children nodes on a local stack and then popping the children nodes off the local stack to connect the children nodes to parents thereof.

30. A computer program instrumenter, according to claim 29, wherein the portions that are selected by the selecting means includes intermediate representation code corresponding to at least one of:

pointer arithmetic operations, operations that reads memory locations, operations that change memory locations, and operations that causes program variables to become defined or undefined within the program.

31. A computer instrumenter, according to claim 29, wherein the nodes of the Intermediate representation tree are interconnected so that children nodes of an operator are operands thereof.

32. A computer program instrumenter, comprising:

(a) examining means for examining an initial intermediate representation of the program;

(b) creating means, coupled to the examining means, for creating an intermediate representation of tree nodes corresponding to intermediate representation operations and operands of the initial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands;

(c) selecting means, coupled to the examining means, for selecting portions of the initial intermediate representation for instrumentation;

(d) instrumenting means, coupled to the creating means and the selecting means, for instrumenting the portions by modifying the intermediate representation tree;

(e) means for creating an effective scope table that correlates a unique scope identifier for each block of intermediate representation code contained within the initial intermediate representation to an effective scope identifier that indicates whether new program variables are defined within each block of intermediate representation code; and

(f) means, operating in response to a first block of the intermediate representation code having a first effective scope identifier not equal to a second effective scope identifier of a second block of the intermediate representation code that precedes the first block of the intermediate representation code, for selecting for instrumentation a portion of the intermediate representation code corresponding to a transition between the first and second blocks.

33. The computer program instrumenter of claim 32, wherein said selecting means includes means for choosing portions of the initial intermediate representation corresponding to at least one of:

pointer arithmetic operations, operations that read memory locations, operations that change memory locations, and operations that cause program variables to become defined or undefined within the program.

34. The computer program instrumenter of claim 32, wherein said creating means includes means for connecting the nodes so that children nodes of an operator are operands thereof.

35. The computer program instrumenter of claim 34, wherein said creating means includes means for placing the children nodes on a local stack and then popping the children nodes off the local stack to connect the children nodes to parents thereof.

36. A computer program instrumenter, comprising:

(a) examining means for examining an initial intermediate representation of the program;

(b) creating means, coupled to the examining means, for creating an intermediate representation of tree nodes corresponding to intermediate representation operations and operands of the initial intermediate representation, the nodes being interconnected according to a logical relationship between the operators and the operands;

(c) selecting means, coupled to the examining means, for selecting portions of the initial intermediate representation for instrumentation;

(d) instrumenting means, coupled to the creating means and the selecting means, for instrumenting the portions by modifying the intermediate representation tree;

(e) means for creating an effective scope table that correlates a unique scope identifier for each block of intermediate representation code contained within the initial intermediate representation to an effective scope identifier that indicates whether new program variables are defined within each block of intermediate representation code; and

(f) means, operating in response to a first block of the intermediate representation code containing a label and having associated therewith a first effective scope identifier not equal to a second effective scope identifier of the intermediate representation code containing a control flow instruction to the label, for selecting for instrumentation a portion of the intermediate representation code corresponding to a transition between the control flow instruction and the label.

37. The computer program instrumenter of claim 36, wherein said selecting means includes means for choosing portions of the initial intermediate representation corresponding to at least one of:

pointer arithmetic operations, operations that read memory locations, operations that change memory locations, and operations that cause program variables to become defined or undefined within the program.

38. The computer program instrumenter of claim 36, wherein said creating means for creating an intermediate representation includes means for interconnecting the nodes so that children nodes of an operator are operands thereof.

39. The computer program instrumenter of claim 38, wherein said creating means for creating an intermediate representation includes means for placing the children nodes on a local stack and then popping the children nodes off the local stack to connect the children nodes to parents thereof.