Method and system for detecting common bytecode sequences

• US 6,922,828 B1
• Filed: 09/09/1999
• Issued: 07/26/2005
• Est. Priority Date: 12/12/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Levine, Frank Eliot, Alexander, William Preston III, Urquhart, Robert J.
• Primary Examiner(s): Vo, Ted T.
• Application Number:
  US09/393,082
• Time in Patent Office: 2,147 Days
• Field of Search: 717/124, 717106-119, 717127-128, 717130-133, 717140-148, 717151-158
• US Class Current: 717/144
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 11/348 Circuit details, i.e. tracer hardware

Abstract

A method and system for detecting and counting bytecode sequences in a data processing system is provided. A bytecode tree data structure is used to represent sequences of bytecodes. A bytecode sequence is a subset of consecutive bytecodes within the set of bytecodes. The bytecode tree data structure contains a set of nodes in which each node represents a bytecode in a bytecode sequence or subsequence and in which a path through the bytecode tree data structure represents a bytecode sequence or subsequence. Each node of the bytecode tree data structure records one or more bytecode occurrence statistics for its corresponding bytecode in a set of bytecode sequences or subsequences. In order to determine the frequency of occurrence of common bytecode sequences and subsequences, a bytecode sequence tree data structure is generated from a set of bytecode sequences. The bytecode sequence tree data structure is then convolved into a bytecode subsequence occurrence tree data structure, which is a union of all subtrees of the bytecode sequence tree data structure.

Claims

1. A method in a data processing system, the method comprising the computer-implemented steps of:

generating a bytecode sequence tree data structure from a set of bytecode sequences; and

convolving the bytecode sequence tree data structure into a bytecode subsequence occurrence tree data structure.

2. The method of claim 1 wherein a bytecode sequence tree data structure comprises a set of nodes, wherein each node represents a bytecode in a bytecode sequence.

3. The method of claim 1 wherein a path through the bytecode sequence tree data structure represents a bytecode sequence unique to all paths in the bytecode sequence tree data structure.

4. The method of claim 1 wherein the step of generating a bytecode sequence tree data structure comprises:

determining whether a node in the bytecode sequence tree data structure represents a selected bytecode;

in response to a determination that the selected bytecode is not represented by a node in the bytecode sequence tree data structure, adding to the bytecode sequence tree data structure a new node representing the selected bytecode, wherein the new node is a child node descending from a parent node representing an immediately preceding bytecode in a bytecode sequence of the selected bytecode; and

incrementing, in the node in the bytecode sequence tree data structure representing the selected bytecode, a count of occurrences of the selected bytecode.

5. The method of claim 1 wherein the step of convolving the bytecode sequence tree data structure into a bytecode subsequence occurrence tree data structure comprises:

creating a root node for the bytecode subsequence occurrence tree data structure;

traversing the bytecode sequence tree data structure to visit each node of the bytecode sequence tree data structure, wherein each visited node determines a subtree data structure of the bytecode sequence tree data structure rooted at the visited node; and

for each visited node of the bytecode sequence tree data structure, adding the subtree data structure for the visited node to the bytecode subsequence occurrence tree data structure at a subtree rooted at a root node of the bytecode subsequence occurrence tree data structure.

6. The method of claim 1 wherein the bytecode subsequence occurrence tree data structure comprises a union of all subtree data structures of the bytecode sequence tree data structure.

7. The method of claim 1 wherein a path through the bytecode subsequence occurrence tree data structure represents a bytecode sequence unique to all paths in the bytecode subsequence occurrence tree data structure.

8. The method of claim 1 wherein the bytecodes are Java bytecodes.

9. The method of claim 1 wherein a bytecode sequence is a subset of consecutive bytecodes within a set of bytecodes.

10. The method of claim 9 wherein the set of bytecodes comprises demarcating bytecodes that may be interpreted as marking a boundary of a bytecode sequence.

11. A data processing system comprising:

generation means for generating a bytecode sequence tree data structure from a set of bytecode sequences; and

convolution means for convolving the bytecode sequence tree data structure into a bytecode subsequence occurrence tree data structure.

12. The data processing system of claim 11 wherein a bytecode sequence tree data structure comprises a set of nodes, wherein each node represents a bytecode in a bytecode sequence.

13. The data processing system of claim 11 wherein a path through the bytecode sequence tree data structure represents a bytecode sequence unique to all paths in the bytecode sequence tree data structure.

14. The data processing system of claim 11 wherein the generations means for generating a bytecode sequence tree data structure comprises:

determining means for determining whether a node in the bytecode sequence tree data structure represents a selected bytecode;

adding means for adding, in response to a determination that the selected bytecode is not represented by a node in the bytecode sequence tree data structure, to the bytecode sequence tree data structure a new node representing the selected bytecode, wherein the new node is a child node descending from a parent node representing an immediately preceding bytecode in a bytecode sequence of the selected bytecode; and

incrementing means for incrementing, in the node in the bytecode sequence tree data structure representing the selected bytecode, a count of occurrences of the selected bytecode.

15. The data processing system of claim 11 wherein the convolution means for convolving the bytecode sequence tree data structure into a bytecode subsequence occurrence tree data structure comprises:

creation means for creating a root node for the bytecode subsequence occurrence tree data structure;

traversing means for traversing the bytecode sequence tree data structure to visit each node of the bytecode sequence tree data structure, wherein each visited node determines a subtree data structure of the bytecode sequence tree data structure rooted at the visited node; and

adding means for adding, for each visited node of the bytecode sequence tree data structure, the subtree data structure for the visited node to the bytecode subsequence occurrence tree data structure.

16. The data processing system of claim 11 wherein the bytecode subsequence occurrence tree data structure comprises a union of all subtrees of the bytecode sequence tree data structure.

17. The data processing system of claim 11 wherein a path through the bytecode subsequence occurrence tree data structure represents a bytecode sequence unique to all paths in the bytecode subsequence occurrence tree data structure.

18. The data processing system of claim 11 wherein the bytecodes are Java bytecodes.

19. The data processing system of claim 11 wherein a bytecode sequence is a subset of consecutive bytecodes within a set of bytecodes.

20. The data processing system of claim 19 wherein the set of bytecodes comprises demarcating bytecodes that may be interpreted as marking a boundary of a bytecode sequence.

21. A computer program product in a computer-readable medium for use in a data processing system, the computer program product comprising:

first instructions for generating a bytecode sequence tree data structure from a set of bytecode sequences; and

second instructions for convolving the bytecode sequence tree data structure into a bytecode subsequence occurrence tree data structure.

22. The computer program product of claim 21 wherein the first instructions for generating a bytecode sequence tree data structure further comprise:

instructions for determining whether a node in the bytecode sequence tree data structure represents a selected bytecode;

instructions for adding, in response to a determination that the selected bytecode is not represented by a node in the bytecode sequence tree data structure, to the bytecode sequence tree data structure a new node representing the selected bytecode, wherein the new node is a child node descending from a parent node representing an immediately preceding bytecode in a bytecode sequence of the selected bytecode; and

instructions for incrementing, in the node in the bytecode sequence tree data structure representing the selected bytecode, a count of occurrences of the selected bytecode.

23. The computer program product of claim 21 wherein the second instructions for convolving the bytecode sequence tree data structure into a bytecode subsequence occurrence tree data structure comprises:

creating a root node for the bytecode subsequence occurrence tree data structure;

traversing the bytecode sequence tree data structure to visit each node of the bytecode sequence tree data structure, wherein each visited node determines a subtree data structure of the bytecode sequence tree data structure rooted at the visited node; and

for each visited node of the bytecode sequence tree, adding the subtree data structure for the visited node to the bytecode subsequence occurrence tree data structure.

24. The computer program product of claim 21 wherein the bytecode subsequence occurrence tree data structure comprises a union of all subtrees of the bytecode sequence tree data structure.