REGISTER  |  SIGN IN
United States Patent6721941
Morshed , ; et al.April 13, 2004
Title
Collection of timing and coverage data through a debugging interface
Abstract
Techniques for gathering execution information about an application, such as a distributed application, are described. Key communication points in cross execution context calls, such as remote procedure calls, are determined and control is transferred to instrumentation routines to insert and extract execution information. Outgoing remote procedure calls are intercepted on a client that inserts call origin information into the request sent to a server system. Messages received by a server are intercepted. The server system extracts the call origin information and additionally inserts other information in a response sent to the client system upon completion of a remote procedure call. In turn, the client system intercepts the response and extracts other performance information. On each client and server system, information is gathered by a reader and forwarded to a local collector. This information may be further forwarded to and correlated by a client collector from one or more remote server collectors in accordance with processes of each distributed application. Various statistics for a distributed application may be determined in addition to per process statistics. These include wire time, code coverage as related to the distributed application, remote procedure call tracing, and performance profiling. A variety of techniques are described to obtain program execution information in connection with an executing application including instrumentation techniques and use of a debugger interface to obtain profiling and other execution information. All of the program execution data may be collected and correlated at one or more particular points using other techniques described to represent coordinated application monitoring.
Inventors:Morshed; Farokh (Amherst, NH), Meagher; Robert  (Milford, NH)
Assignee:Compuware Corporation (Farmington Hills, MI)
Appl. No.:644000
Filed:August 22, 2000
Current U.S. Class:717/127 717/128 717/129 717/130 717/131 719/328 709/217 714/38 717/124 717/126 
Current International Class:G06F 11/36 (20060101)
Field of Search:717/124,127,128,129,130,131,136 714/38 709/217,328
U.S. Patent Documents
3707725December 1972Dellheim
5210874May 1993Karger
5430876July 1995Schreiber et al.
5432795July 1995Robinson
5528753June 1996Fortin
5560009September 1996Lenkov et al.
5581696December 1996Kolawa et al.
5613063March 1997Eustace et al.
5664191September 1997Davidson et al.
5732273March 1998Srivastava et al.
5734908March 1998Chan et al.
5790858August 1998Vogel
5815653September 1998You et al.
5958010September 1999Agarwal et al.
5968188October 1999Rana
5987249November 1999Grossman et al.
6049666April 2000Bennett et al.
6115741September 2000Domenikos et al.
6126329October 2000Bennett et al.
6158045December 2000You
6282701August 2001Wygodny et al.
6324683November 2001Fuh et al.
6345383February 2002Ueki
6353923March 2002Bogle et al.
6412106June 2002Leask et al.
Other References
Title: Execution Monitoring and Debugging Tool for ADA using Relational Algebra, ACM, author: Maio, 1985.
Primary Examiner: Das; Chameli Chaudhuri
Attorney, Agent or Firm:Choate, Hall & Stewart
Parent Case Text


CROSS REFERENCE TO RELATED APPLICATIONS

This application is a continuation-in-part of U.S. patent application Ser. No. 09/250,626 filed on Feb. 16, 1999 which is a continuation-in-part of pending U.S. patent application Ser. No. 09/066,988 filed on Apr. 23, 1998 now U.S. Pat. No. 6,186,677, which is based on U.S. Provisional Patent Application No. 60/045,018 filed on Apr. 28, 1997 and which is also a continuation-in-part of issued U.S. patent application Ser. No. 08/916,125, filed on Aug. 21, 1997 (now issued U.S. Pat. No. 5,987,249 on Nov. 16, 1999), which is based on U.S. Provisional Patent Applications Nos. 60/024,624 and 60/036,250 filed on Aug. 27, 1996 and Jan. 24, 1997, respectively.
Claims

What is claimed is:
1. A method for monitoring execution of an application comprising: reporting debugging information to a program monitor using an application debugging interface, said program monitor executing within address space of said application; gathering program execution information using the debugging information to monitor execution of the application, wherein said debugging information includes a character offset position associated with a source file; building a line table associated with the source file, the line table including beginning and ending character offsets corresponding to a source line of the source file; and determining a source line number for said character offset position;, wherein said character offset position is included in the debugging information and the source line number is included in the program execution information.

2. The method of claim 1 further comprising: deriving a portion of the program execution information from data reported using the application debugging interface.

3. The method of claim 1, wherein said application debugging interface is used in connection with debugging the application.

4. The method of claim 1, wherein the program execution information includes one of: performance profiling data, code coverage data, program tracing data.

5. The method of claim 4, wherein the program execution information includes cross execution context call information from a first execution context call to a second execution context call, said first execution context call being associated with a calling function and said second execution context call being associated with a called function.

6. The method of claim 5, wherein the application is a distributed application.

7. The method of claim 6, wherein the cross execution context call is a remote procedure call.

8. The method of claim 7, further comprising: executing the calling function in a client system; executing the called function in a server system; and correlating information about the remote procedure call at the client system.

9. The method of claim 8, further comprising: reporting program execution information from the server to the client system using in correlating information about the remote procedure call.

10. The method of claim 9, wherein said program execution information includes program trace data for understanding execution of said distributed application.

11. The method of claim 1, further comprising: gathering program execution information associated with a portion of the application being monitored without using a pre-execution instrumentation technique.

12. The method of claim 11, wherein said portion is produced using one of: VBScript code and JavaScript code.

13. The method of claim 1, further comprising: producing a portion of the application is using a non-generative translation technique.

14. The method of claim 1, further comprising: producing a portion of the application is a generative translation technique.

15. The method of claim 1, further comprising: registering the program monitor as a debugger.

16. The method of claim 1, further comprising: transforming debug information into program execution information.

17. The method of claim 16, wherein the program execution information includes function entry information, and the method further comprising: determining a source line included in the function entry information using function information stored in a line table.

18. The method of claim 17, wherein said program execution information includes fiction exit information, and the method further comprises: detecting end of processing by detecting a predetermined period of execution inactivity associated with a portion of code.

19. The method of claim 18, further comprising: transferring control, by address patching, to monitoring software upon detection of end of processing of a portion of code.

20. The method of claim 16, wherein said program execution information includes execution information associated with execution of a line of code.

21. The method of claim 20, further comprising: transferring control to the program monitor when executing in single step mode; recording first data after executing a first instruction about said first instruction and about a next subsequent instruction.

22. The method of claim 21, further comprising: recording second data after executing said next subsequent instruction; and determining a processing time associated with the next subsequent instruction using said first and second data.

23. The method of claim 16, wherein said program execution information includes tracing information used in connection with code coverage information.

24. The method of claim 1, further comprising: transferring control to the program monitor after executing a line of code; and recording in the line table code coverage information associated with the line of code.

25. The method of claim 4, further comprising: communicating the program execution information from a server to a client.

26. A computer program product for monitoring execution of an application comprising: machine executable code for reporting debugging information to a program monitor using an application debugging interface, said program monitor executing within address space of said application; machine executable code for gathering program execution information using the debugging information to monitor execution of the application, wherein said debugging information includes a character offset position associated with a source file; machine executable code for building a line table associated with the source file, the line table including beginning and ending character offsets, corresponding to a source line of the source file; and machine executable code for determining a source line number for said character offset position, wherein said character offset position is included in the debugging information and the source line number is included in the program execution information.

27. The computer program product of claim 26, further comprising: machine executable code for deriving a portion of the program execution information from data reported using the application debugging interface.

28. The computer program product of claim 26, wherein said application debugging interface is used in connection with debugging the application.

29. The computer program product of claim 26, wherein the program execution information includes one of: profiling data, performance data, code coverage data, program tracing data.

30. The computer program product of claim 29, wherein the program execution information includes cross execution context call information from a first execution context call to a second execution context call, said first execution context call being associated with a calling function and said second execution context call being associated with a called function.

31. The computer program product of claim 30, wherein the application is a distributed application.

32. The computer program product of claim 31, wherein the cross execution context call is a remote procedure call.

33. The computer program product of claim 32, further comprising: machine executable code for executing the calling function in a client system; machine executable code for executing the called function in a server system; and machine executable code for correlating information about the remote procedure call at the client system.

34. The computer program product of claim 33, further comprising: machine executable code for reporting program execution information from the server to the client system using in correlating information about the remote procedure call.

35. The computer program product of claim 34, wherein said program execution information includes program trace data for understanding execution of said distributed application.

36. The computer program product of claim 26, further comprising: machine executable code for gathering program execution information associated with a portion of the application being monitored without using a pre-execution instrumentation technique.

37. The computer program product of claim 36, wherein said portion is produced using one of: VBScript code and JavaScript code.

38. The computer program product of claim 26, further comprising: machine executable code for producing a portion of the application using a non-generative translation technique.

39. The computer program product of claim 26, further comprising: machine executable code for producing a portion of the application using a generative translation technique.

40. The computer program product of claim 26, further comprising: machine executable code for registering the program monitor as a debugger.

41. The computer program product of claim 26, further comprising: machine executable code for transforming debug information into program execution information.

42. The computer program product of claim 41, wherein the program execution information includes function entry information, and the computer program product further comprising: machine executable code for determining a source line included in the function entry information using function information stored in a line table.

43. The computer program product of claim 42, wherein said program execution information includes function exit information, and the computer program product further comprises: machine executable code for detecting end of processing by detecting a predetermined period of execution inactivity associated with a portion of code.

44. The computer program product of claim 43, further comprising: machine executable code for transferring control, by address patching, to monitoring software upon detection of end of processing of a portion of code.

45. The computer program product of claim 41, wherein said program execution information includes execution information associated with execution of a line of code.

46. The computer program product of claim 5, further comprising: machine executable code for transferring control to the program monitor when executing in single step mode; and machine executable code for recording first data after executing a first instruction about said first instruction and about a next subsequent instruction.

47. The computer program product of claim 46, further comprising: machine executable code for recording second data after executing said next subsequent instruction; and machine executable code for determining a processing time associated with the next subsequent instruction using said first and second data.

48. The computer program product of claim 41, wherein said program execution information includes tracing information used in connection with code coverage information.

49. The computer program product of claim 26, further comprising: machine executable code for transferring control to the program monitor after executing a line of code; and machine executable code for recording in the line table code coverage information associated with the line of code.

50. The computer program product of claim 49, further comprising: machine executable code for communicating the program execution information from a server to a client.
Description
BACKGROUND

This application generally relates to computer systems, and more particularly to monitoring a computer program executing in a computer system.

As part of software development, it may be useful to obtain execution information about a software application, such as information regarding program performance and execution coverage. This information gathering may be performed by monitoring the software application as it executes in a computer system. In particular, there exists manual and automated techniques for gathering execution information about a software application. This information may include profiling, coverage, and program tracing data to enable a software developer, for example, to identify performance bottlenecks, testing coverage performed for a particular application, monitor memory accesses, and the like.

Machine executable code that comprises a software application may be executed in a computer system. The machine executable code may be produced using one of two basic approaches of translation of input, such as source code. One approach may be referred to as a generative approach, and the second approach may be referred to as a single-stage translation approach. Both approaches may be characterized in the process by which output, such as machine executable code, may be produced given an input, such as source code.

The generative approach to translation may be characterized generally as a two-stage process of translation and then execution. For example, a source language program may be translated, as by compilation and linking, to produce a machine language program. This machine language program may then be executed with a set of data to produce output execution results. Generally, translation and execution may be characterized as distinct conceptual phases. Translation may precede execution by some arbitrary amount of time. The production of a machine language program allows for subsequent executions of the machine language program with additional input data sets without repeating translation.

In contrast, the single-stage translation approach may be characterized as a single stage process in which the source language program, for example, may be translated into actions that directly result in the production of output data. Generally, a machine language or other intermediate form of the program may not be produced. Translation and execution are intimately linked in a single stage. In other words, translation time is deferred until execution time and the source language program is translated each time it is executed.

Generally, software application monitoring techniques exist, for example, such as in connection with gathering test coverage and profiling information using the generative approach and the single-stage translation approach. To collect execution information in connection with monitoring a software application produced using either the generative approach or the single-stage translation approach, existing techniques may include instrumenting source code. Instrumenting source code may include, for example, manually modifying source code to gather and output additional information at various points in program execution, such using one or more special application programming interface (API) routines.

Automated techniques may be used in connection with the generative approach. For example, intermediate code and object code as may be produced using a compiler may be instrumented to generate and gather profiling data at various points in program execution.

Drawbacks with instrumenting source code may include manually modifying the source code and then, subsequently recompiling or reinterpreting the modified source code. A drawback with the foregoing automated instrumentation technique is that pre-execution instrumentation may be required, for example, such as instructing the compiler to generate code used in connection with program monitoring, and the like.

One technique that may be used with both the generative and the one-stage translation approaches involves special hooks as may be provided by a particular translator. For example, a particular translator may provide a mechanism, such as callbacks, for notification and transfer of control to monitoring software upon the occurrence of certain events. Using this technique, control may be transferred at particular points, such as when certain runtime functions or subroutines are invoked, to special monitoring routines that may inject and/or extract information prior to executing the actual code associated with a routine. Use of this technique may alleviate the need to modify and then recompile or reinterpret the modified source code. However, there is a dependency upon a vendor of the generative translator or one-stage approach translator to provide these hooks.

A problem may exist when no such hooks are provided. With a generative translator, other techniques may be used to gather execution data, such as patching an address of an actual runtime routine or modifying symbol resolution during linking, to transfer control to a "dummy" routine. The dummy routine may perform monitoring tasks and then subsequently transfer control to the actual routine. However, this technique when used with a generative translator may have drawbacks, such as requiring a modification to the linking procedure to produce an object file.

When no hooks are provided in connection with a one-stage approach translator, there may be no way of instrumenting the application to generate and gather program execution data in connection with program monitoring, for example, due to the single combined process of translation and execution. JavaScript and VBScript are examples of two commercially available languages that use the one-stage approach and do not provide these "hooks". Thus, it is difficult to obtain execution information, such as may be desired with program behavior monitoring, in connection with code written in JavaScript and VBScript, for example.

Thus, it may be useful to provide an efficient technique for gathering execution information about an application without requiring instrumentation or hooking capabilities.

SUMMARY OF THE INVENTION

In accordance with principles of the invention are a method and computer program product for monitoring execution of an application in a computer system. Debugging information is reported to a program monitor using an application debugging interface. Program execution information is gathered using the debugging information to monitor execution of the application.

BRIEF DESCRIPTION OF THE DRAWINGS

Features and advantages of the present invention will become more apparent from the following detailed description of exemplary embodiments thereof taken in conjunction with the accompanying drawings in which:

FIG. 1 shows a computer system that may be used to implement IR code instrumentation;

FIG. 2 is a data flow diagram illustrating a compiler operating in conjunction with IR code instrumentation;

FIG. 3 is a data flow diagram illustrating interaction between various stages of the compiler and the IR code instrumentation according to the present invention;

FIG. 4 is a data flow diagram illustrating in detail operation of the software for IR instrumentation;

FIG. 5 illustrates a tree data structure corresponding IR code operators and operands;

FIG. 6 is a flowchart illustrating steps used to construct the tree data structure of FIG. 5;

FIG. 7 is a flowchart illustrating instrumentation of the tree data structure of FIG. 5;

FIG. 8 is a flowchart illustrating construction of an effective scope table used in connection with instrumenting the tree data structure of FIG. 5;

FIGS. 9A and 9B are flowcharts illustrating scope optimization used in connection with instrumenting the tree data structure of FIG. 5;

FIG. 10 is a flowchart illustrating in detail a portion of the flowchart of FIG. 7 where nodes are selected for instrumentation;

FIGS. 11A-11C illustrate insertion of nodes in connection with instrumentation of the tree data structure of FIG. 5;

FIG. 12 is a data flow diagram illustrating instrumentation of byte code;

FIG. 13 is a flowchart illustrating steps for instrumenting byte code and executing the instrumented byte code;

FIG. 14 is a flowchart illustrating instrumenting a method of a class;

FIG. 15 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 14;

FIG. 16 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 14;

FIG. 17 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 14;

FIG. 18 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 14;

FIG. 19 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 14;

FIG. 20 is a flowchart illustrating instrumenting a class;

FIG. 21 is a flowchart illustrating passing data collected by instrumentation;

FIG. 22 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 21;

FIG. 23 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 22;

FIG. 24 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 22;

FIG. 25 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 24;

FIG. 26 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 25;

FIG. 27 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 25;

FIG. 28 is a flowchart illustrating in more detail a portion of the flowchart of FIG. 24;

FIG. 29 is an example of an embodiment of a computer system;

FIG. 30 is an example of an embodiment of software that may reside in a client system and a server system;

FIGS. 31 and 32 are example of embodiments of client and server software;

FIGS. 33 and 34 include an example of an alternative embodiment of client-server software;

FIG. 34A is an example of a representation of an embodiment of method steps for establishing a local monitor process to collector connection;

FIG. 35 is an example of an embodiment of a distributed software application;

FIG. 36 is an example of an alternate embodiment of a distributed application with multiple server processes and a single client process;

FIG. 36A is an example of a representation 1340 depicting method steps of one embodiment for establishing connections and transmitting execution data between a client and server system;

FIG. 37 is an example of an embodiment of the messages that may be exchanged between a client and a server system with regard to remote procedure calls;

FIG. 38 is an example of an embodiment of the portions of data that may be added in a request from a client to a server system;

FIG. 39 is an example of an embodiment of the data that may be included in a response sent from a server to a client system;

FIG. 40 is a flowchart of the method steps of one embodiment of a technique for gathering and recording information in a client and server distributed application;

FIG. 41 is a flowchart of an example of an embodiment of method steps as may be performed by the collector of a client upon termination of a distributed application;

FIG. 42 is an example of an embodiment of calculating wire time as may be performed by a client collector in the computer system;

FIG. 42A is a representation of the time components that may be used to calculate wire time;

FIG. 43 is a flowchart of an example of an embodiment of a method of the steps performed by the distributed application software and the software gathering data about the distributed application;

FIG. 43A is an example of a representation of a graphical display of a process;

FIG. 43B is an example of an embodiment of a session data file;

FIG. 44 is an example of an embodiment of classes of methods that may be used by software included in the computer system 1000;

FIG. 45 is an example of an embodiment of a portion of the collector interfaces;

FIG. 46 is an example of an embodiment of a portion of client software in connection with a debugging interface technique;

FIG. 47 is an example of an embodiment of a portion of client software in connection with a debugging interface technique as updated from FIG. 46;

FIG. 48 is an example of an embodiment of a portion of server software in connection with a debugging interface technique;

FIG. 49 is an example of an embodiment of a portion of server software in connection with a debugging interface as updated from FIG. 48;

FIG. 50 is a flowchart of method steps performed in connection with obtaining execution information in a client using debugging techniques;

FIG. 51 is a flowchart of method steps performed in connection with obtaining execution information in a server using debugging techniques;

FIG. 52 is an example of more detailed processing and cooperation between the various components as may be included in a client and/or server software using debugging techniques;

FIG. 53 is a flowchart of method steps of one embodiment performed by the components of FIG. 52;

FIG. 54 is an example of an embodiment of a line table;

FIG. 55 is an example of an embodiment of a computer system;

FIG. 56 is an example of an embodiment of a monitor process gathering information from a test program;

FIG. 57 is an example of another embodiment of a monitor process gathering information from a machine executable program;

FIG. 58 is an example of an embodiment of a monitor process interacting with a database and other tools using information stored to the database;

FIG. 59 is an example of an embodiment of a data representation of information stored in the database of FIG. 58;

FIG. 60 is an example of the module object as included in the database schema;

FIG. 61 is an example of an embodiment of the system configuration information object that may be included in the representation of a database schema;

FIG. 62 is an example of an embodiment of the project object that may be included in the representation of the database schema;

FIG. 63 is an example of an embodiment of the session object that may be included in the representation of the database schema;

FIG. 64 is an example of an embodiment of a bug report object that may be included in the representation of the database schema;

FIG. 65 is a flowchart of an example of an embodiment of how testing data is recorded and used by the monitor process tool;

FIG. 66 is a flowchart of an example of embodiment of a method of how data is gathered for one or more testing sessions;

FIG. 67 is an example of an embodiment of the different types of data operations that may be performed with regard to recorded session data in the database;

FIGS. 68-72 are examples of embodiments of flowcharts associated with processing operations upon data recorded in the database to assess one or more testing characteristics; and

FIGS. 73-74 are examples of embodiments of flowcharts associated with processing operations to determine a matching platform in accordance with a target platform in an embodiment.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENT(S)

Referring to FIG. 1, a computer system 20 includes a processor 22, a display unit 24, a keyboard 26 and (optionally) a mouse input device 28. The user provides input to the processor 22 via the keyboard 26 and the mouse 28 and views output from the processor 22 via the display unit 24. The computer system may be a model P5-166 manufactured by Gateway Computer of Sioux City, S.Dak.

The computer system 20 may include a connection 30 to a conventional computer network (not shown), such as the Microsoft NT network. The computer system 20 may receive data and/or other network services, in a conventional manner, through the connection 30 to the network. The processor 22 may include conventional local storage or may use conventional storage available on the network wherein the processor 22 sends and receives data to and from the network via the network connection 30. The computer system 20 may use a combination of local storage and network storage in a conventional manner. In the discussion that follows, no specific reference is made to the type of storage device (i.e., local, network, or a combination thereof) since the system described herein does not depend on the type of computer data storage used.

Referring to FIG. 2, a data flow diagram 40, illustrates relationships between various executable code and data segments stored using the storage device of the processor 22. A software compiler 42 includes executable code that converts data representing computer source code 44 into data representing computer object code 46. The compiler 42 may be any one of a variety of conventional, commercially available, software compilers, such as the Microsoft C++ compiler manufactured by Microsoft Corporation of Redmond, Wash. If the compiler 42 is a C++ compiler, then the source code 42 represents C++ source code information entered by a user in a conventional manner such as, for example, entering the C++ source code statements into a text file in the computer system 20 using the keyboard 26 and mouse 28. The source code 44 may also be generated by any one of a variety of alternative techniques, such as other conventional, commercially available software that automatically generates the source code 44.

The object code 46 includes low-level code that is executable on a target processor (not shown). Accordingly, the object code 46 is target-specific. Note that the target processor may be the same type of processor as the processor 22 used in the computer system 20 or, alternatively, the target processor may be a different processor. The object code 46 is provided by the compiler 42 in a conventional manner.

In the course of compiling the source code 44 into object code 46, the compiler 42 may generate a plurality of transitional representations 48 that correspond to intermediate stages of the compile process. The transitional representations 48 may include a plurality of (usually temporary) data files that are created and accessed by the compiler 42. Each stage of the compiler 42 may access and/or create a particular one of the transitional representations that is provided by the previous stage of the compiler 42. Features of some of the transitional representations 48 are described in more detail hereinafter.

Code instrumentation software 50, that executes on the processor 22, accesses the transitional representations 48 and adds instrumentation instructions that ultimately provide instrumentation functionality to the object code 46. When the object code 46 is executed, the thus-added instrumentation functionality facilitates debugging in a manner described in more detail hereinafter.

Referring to FIG. 3, the data flow diagram 40 of FIG. 2 is illustrated with additional details included for the compiler 42 and for the transitional representation 48. The compiler 42 is shown herein as having four stages 52-55 that each perform a different phase in the process of transforming the source code 44 into the object code 46. The transitional representations 48 are shown as including various data elements that are created and/or accessed by the compiler 42. Note that other compilers may have more or less stages and that portions of the transitional representations 48 may be stored in a file, a computer memory, a combination thereof, or a variety of other means for maintaining computer data.

For the embodiment illustrated herein, the first stage 52 of the compiler 42 accesses the source code 44 and, in a conventional manner, converts the source code into tokens stored in a token stream data element 62. The token stream data element
62 contains symbols that represent individual source code statements. The symbols may be ordered according to the order of source code statements in the source code 44. The token stream 62 is provided to the second stage 53 of the compiler 42, which, in a conventional manner, converts the tokens from the token stream data element 62 into data stored in a parse tree data element 63. The parse tree data element 63 is a tree-like data structure that is constructed in a conventional manner using nodes corresponding to tokens from the token stream data element 62 that are interconnected in a directed graph according to entry and exit points of portions of the source code.

The parse tree data element 63 is provided to the third stage 54 of the compiler 42 which uses the data from the parse tree data element 63 to produce Intermediate Representation (IR) data that is stored in an IR data element 64. As described in more detail hereinafter, the IR data element 64 contains an intermediate representation of the program that is independent of the particular language used for the source code 44 and is also independent of the target processor on which the object code 46
will execute.

The fourth stage 55 of the compiler 42 converts IR data from the IR data element 64 into the object code 46. Without the code instrumentation unit 50, the fourth stage 55 of the compiler 42 could access the IR data element 64 (as indicated by the dashed line connecting the IR data element 64 to the fourth stage 55) and convert IR data from the IR data element 64 into the object code 46. However, in the system described herein, the IR data element 64 is provided to the code instrumentation 50
which, in a manner described in more detail below, instruments the IR data element 64 to provide an instrumented IR data element 65. In the system described herein, the fourth stage 55 of the compiler 42 accesses the instrumented IR data element 65 to provide the object code 46. Note that since the IR data element 64 and the instrumented IR data element 65 have the same basic structure, it is virtually transparent to the fourth stage 55 of the compiler 42 that the instrumented IR data element 65, instead of the IR data element 64, is being accessed to create the object code 46.

The IR data element 64 and the instrumented-IR data element 65 contain conventional IR data that is both source and destination independent. The IR data represents the logical flow and operation of the program independent of the particular source code that is used in the source program to describe the logical flow and operation. In addition, the IR data is independent of the specific form of the object code (i.e., the specific target processor). Such IR data is well known in the prior art and will not be described in detail herein except as necessary to describe the invention.

Referring to FIG. 4, the code instrumentation 50 includes tree construction software 62 for constructing an IR tree, instrumentation software 63 for instrumenting both the IR tree and other IR data, and tree deconstruction software 70 for converting the thus-instrumented IR tree and other IR data into the instrumented IR data element 65. The tree construction software 62 receives input from the IR data element 64 and, in a manner described in more detail below, constructs an IR tree to provide to an IR tree data element 66. The instrumentation software 63 uses the IR tree data element 66 and other IR data from the IR data element 64 to provide an instrumented IR tree 67 and other IR data 68.

The instrumentation software 63 may also be provided with instrumentation data from an instrumentation data element 69. The instrumentation data element 69 may contain run time instrumentation routines and other IR data that is inserted by the instrumentation software 63 into the instrumented IR tree data element 67, the other IR data 68, or a combination thereof. The instrumentation software 63 and the instrumentation data element 69 are described in more detail hereinafter. The tree deconstruction software 70 uses the instrumented IR tree data element 67 and the other IR data 68 to create the instrumented IR data element 65. The tree deconstruction software 70 is described in more detail hereinafter.

The IR data consists of a plurality of operations and operands that correspond to the logic of the underlying source computer program. Note that the terms "operation" and "operand" may be defined broadly in this instance to include any type of statements found within IR data, including program transition statements such as call and goto, and static information such as line numbers. An operand can be a simple operand (e.g., a single variable or constant) or can be a complex operand (e.g., an expression) that corresponds to additional suboperations and operands. For example, IR data may indicate that the left side of an expression is to be set equal to the right side of an expression. The left side of the equation could be a single variable (i.e., a simple operand). The right side of the equation could also be simple operand (e.g., a constant) or could be a complex operand (e.g., an expression) that must be further evaluated in the context of additional operators and operands (e.g., addition of two variables).

Note that the IR data is both source language independent and target machine independent so that, for example, a source code statement written in a first source language could generate IR data that is identical to a programatically equivalent source language statement in a second source language if the underlying operations are identical. Similarly, a particular set of IR data can be converted by a compiler into many different object codes depending on the target machine. Although a specific IR representation may be particular to a specific compiler manufacturer, IR data and IR representations are generally known in the art. See, for example, a section titled "Graphical Representations" at pages 464-465 of Aho, Seth & Ullman, Compilers, Principles, Techniques, and Tools, published by Addison-Wesley of Reading Mass., 1986.

Referring to FIG. 5, a tree 80 corresponds to the IR tree data element 66 provided by the tree construction software 62 shown in FIG. 4 and discussed above. The tree 80 includes a plurality of nodes 82-104. The nodes 82-104 have different types and are labeled according to type as follows:

T: terminal node

U: unary node

B: binary node

3: ternary node

C: combination node

E: end of list indicator node

X: indeterminate node, one of the above listed types of nodes

The terminal nodes 88, 90, 93, 99, 102-104 are nodes of the tree 80 having no children. The unary nodes 86, 92, 95 have only one child. The binary nodes 89, 91 have two children. The ternary node 100 has three children. The combination nodes
82, 94 have two children wherein one of the children is a list terminated by the end of list nodes 87, 98. The indeterminate nodes 83-85, 96, 97 represent nodes that could be any one of the other types of nodes and have been included in the tree 80 to facilitate illustration of the structure of the tree 80.

Each of the nodes 82-104 represents an IR operation and/or an IR operand within the IR data. For any particular one of the nodes 82-104, the children thereof represent the operators and the operands used to evaluate the parent. For example, the binary node 89 could represent an operation having two operands corresponding to the two children of the binary node 89: the terminal node 90 and the binary node 91. The terminal node 90 does not have any children and thus may correspond to a simple operand (e.g., a constant). The binary node 91 is a complex operand having children (the unary node 92 and the combination node 94) which are evaluated in order to evaluate the complex operand represented by the binary node 91.

For the combination nodes 82, 94, the attached list elements are shown as being linked together so that, for example, the node 83 is shown being linked to the node 84 and the node 84 is shown as being linked to the node 85. Another possible way to construct the list is to have the combination node 82 point to a separate list data structure 106 that contains pointers to the remaining nodes 83-87 that represent elements of the list. In that case, there would be no need for the connections between members of the list so that the node 83 would not contain a pointer to the node 84, nor would the node 84 contain pointers to the nodes 83, 85, nor would the node 85 contain a pointer to the node 84. The advantage of such a construction is that none of the nodes 83-87 would use extra storage space for pointers to the peers thereof. Of course, separately constructing the list 106 may add complexity and possibly additional processor time in connection with manipulating the combination node 82. Note that irrespective of whether the list nodes 83-87 are connected peer to peer or are simply pointed to by the separate list 106, the end of list may conveniently be indicated by the end of list node 87.

The tree 80 illustrates that the underlying program corresponding to the IR data can be represented as a list of root nodes of a plurality of subtrees. That is, the program may be represented by a list of nodes 82-87 that correspond to root nodes of a plurality of subtrees. Of course, some of these subtrees may simply have a root node without substructure while other subtrees, such as the subtree emanating from the node 86, may have a more involved structure. Note also that, in some embodiments, the tree 80 may represent a single function among a plurality of functions contained in the IR data element 64.

Referring to FIG. 6, a flowchart 120 illustrates operation of the tree construction software 62 of FIG. 4 that uses data from the IR data element 64 to provide the IR tree data element 66. The flowchart includes an entry point 122 and an exit point 124. A connector 126 labeled "TOP" is used to simplify the flowchart 120 by decreasing the number of flow lines thereon. All points on the flowchart labeled with the connector 126 represent the same logical point in the flow of the code.

The data that is read from the IR data element 64 and processed by the tree construction software 62 could be stored in a computer file. In other embodiments, data may be stored in computer memory or stored using any one of a variety of means sufficient for providing the IR data element 64. Each node may be represented by a variable length record having conventional type and size indicators. In the embodiment illustrated herein, it is assumed that the data is stored in a conventional computer file with the operands corresponding to a node being at an earlier point in the file than the node itself. For example, if a particular node representing the addition operation has two children representing the first and second operands that are being added, then the three nodes (parent and two children) may be stored in the file with the first and second operands being located sequentially prior to the node indicating the addition operation. Accordingly, for any tree or subtree, the root node may be located in the file following all of the children nodes. In a preferred embodiment, the data from the IR data element 64 is first read into a flat list (such as a linked list or an array). Then the flat list is processed to provide the tree
80. The nodes that are part of the flat list may be the same nodes stored in the tree 80 (i.e., the same data), with the tree 80 being constructed by simply adding links to the nodes in the flat list to form the tree 80. Alternatively, the flat list may be part of the IR data element 64.

Processing for the routine illustrated in FIG. 6 begins at a test step 130 which determines if there is more data to be processed. If not, then processing is complete and control passes to the exit point 124 to exit the tree construction software. Otherwise, control passes to a step 132 where the current node (CN) is read in. The CN represents the node that is processed by the remainder of the software. Note that if a separate flat list of nodes is used, then "reading in" CN may simply refer to examining the next node in the list. Otherwise, the CN may be read directly from the IR data element 64.

Following the step 132 is a step 134 where the node type of the CN is determined. Note that there are many conventional techniques known in the art for associating a type with a portion of data such as, for example, using a unique numeric code to differentiate between types. Once the node type is determined at the step 134, control passes to one of a plurality of code branches that process the particular node type.

If it is determined at the step 134 that the CN is a terminal node, then control passes from the step 134 to a step 136 where the CN is pushed onto a stack. As discussed in more detail below, the tree construction software 62 uses a local stack to construct the tree 80. Following with step 136, control passes back to the beginning of the routine (as indicated by the connector 126) to the steps 130, 132 (discussed above) that check to see if there is more data to be processed and, if so, then read that data into the CN.

If it is determined at the step 134 that the CN is a unary node (i.e., a node with one child), then control passes from the step 134 to a step 140 where the child (CH) of the unary node is popped off the local stack. Note that the child of the unary node would have been read in previously, per the convention adopted for storing the IR data, discussed above. Following the step 140 is a step 142 where the child of the unary node (i.e., the child of the CN) is linked to the CN. Following the step 142 is a step 144 where the CN is pushed onto the local stack. Note that the CN may be a child of another node that will be subsequently read in. Following the step 144, control passes back to the beginning of the routine, as indicated by the connector 126.

If it is determined at the step 134 that the CN is a binary node (i.e., a node having two children), then control passes from the step 134 to a step 150 where the left child (LC) and the right child (RC) of the CN are popped off the local stack. Following the step 150 is a step 152 where the left child and right child are linked to the CN. Following the step 152 is a step 154 where the CN is pushed onto the local stack. Following step 154, control transfers back to the beginning of the routine, as indicated by the connector 126.

If it is determined at the step 134 that the CN is a ternary node, then control transfers from the step 134 to a step 160 where the three children of the ternary node, the left child (LC), middle child (MC), and right child (RC), are popped off the local stack. Following the step 160 is a step 162 where the left child, middle child, and right child are linked to the CN. Following the step 162 is a step 164 where the CN is pushed onto the local stack. Following the step 164, control transfers back to the beginning of the routine, as indicated by the connector 126.

If it is determined at the step 134 that the CN is a combination node, then control transfers from the step 134 to a step 170 where the child node (CH) is popped off the local stack. As discussed above in connection with FIG. 5, a combination node has two children where the first child is a single node and the second child is a list of nodes. In terms of storage of the IR data associated with a combination node, the first child may be stored prior to the combination node but the second child (the list elements) may be stored immediately after the combination node. Note also that, as discussed above, the end of the list is indicated by an end of list node.

Following the step 170 is a step 172 where the child node is linked to the CN. Following the step 172 is a step 174 where the routine is recursively called to process the elements of the list to be attached to the CN. As discussed in detail below, the return from the recursive call to the routine occurs when the end of list indicator is reached. Also, by convention, the routine may return a list containing items remaining on the local stack used by the routine.

Following the step 174 is a step 176 where the list returned by the call to the routine at the step 174 is linked to the CN to become the attached list of the combination node. Note that the call to the routine at step 174 causes each of the elements of the list for the combination node to be processed and placed on the local stack. Accordingly, the list of local stack elements may be returned upon returning from the call to the routine at the step 174. Following the step 176 is a step 178
where the CN (i.e., the combination node) is pushed onto the stack. Following step 178, control passes back to the beginning of the routine, as indicated by the connector 126.

If it is determined at the step 134 that the CN is an end of list indicator node, then control passes from the step 134 to a step 180 where the CN is pushed onto the local stack. Following the step 180, control passes back to the step 124 to return from the routine. Note that, in many instances, the return from the routine at this point is a return from a previous recursive call to the routine that was made when the corresponding combination node (the parent for the current list) was first encountered, as described above in connection with the steps 174, 176.

As discussed above, the instrumentation software 63 shown in FIG. 4 operates on the IR tree data element 66 to provide the instrumented IR tree data element 67. The instrumentation software 63 also uses data from the other instrumentation data element 69 which, as discussed in detail below, includes a plurality of run time instrumentation routines that may be added to the IR tree to facilitate run time debugging. In addition, as discussed in more detail below, the instrumentation software 63
instruments other IR data to provide the other IR data element 68 that includes instrumented versions of IR data. Once the instrumentation software 63 has provided the instrumented IR tree data element 67, the tree deconstruction routine 70 uses the instrumented IR tree data element 67 and the other IR data element 68 to provide the instrumented IR data element 65.

Referring to FIG. 7, a flowchart 200 illustrates operation of the instrumentation software 63 of FIG. 4. The instrumentation software 63 examines data found within the IR data element 64 and, in a manner discussed in more detail below, provides instrumentation. Processing begins at a test step 202 where it is determined if there is more data (i.e., more nodes) to examine. Note that the data that is processed could be either directly from the IR data element 64 or could be from the flat list of IR nodes, discussed above, that may be created in connection with creating the IR tree 80. If it is determined at the test step 202 that there is no more data to process (i.e., the end of the list or the end of the file containing the data has been reached), then processing is complete and the routine of FIG. 7 is exited.

If it is determined at the test step 202 that there is more data to be processed, then control passes from the test step 202 to a step 204 where the current node (CN) is obtained. In a manner similar to that discussed above in connection with construction of the IR tree 80, obtaining the CN may include reading the CN directly from the IR data element 64 or simply obtaining the next node in the flat list of nodes that may have been constructed prior to building the IR tree 80.

Following the step 204 is a test step 206 where it is determined if the CN is a node of interest. As discussed in more detail below, a node of interest includes any node that is to be instrumented or which indicates that instrumentation is appropriate. Identifying which nodes are nodes of interest at the test step 206 is discussed in more detail hereinafter.

If it is determined at the test step 206 that the CN is not a node of interest, then control passes from the test step 206 back up to the step 202 where it is determined if there is more data to be processed, as discussed above. Otherwise, if it is determined at the test step 206 that the CN is a node of interest, then control passes from the test step 206 to a step 208 where a portion of the IR tree 80 is instrumented, either by replacing the CN and/or adding additional nodes the near location of the CN in the tree 80. Following the step 208 is a step 210 where other IR data is modified, as appropriate. Following the step 210, control passes back to the step 202 to determine if there is more data to be processed.

Generally, it is possible to instrument any one or any subset of a variety of the nodes found in the IR tree 80. In many instances, however it is useful to instrument memory access instructions in order to detect illegal memory operations at run time. In addition, for many higher-level languages, variables that may be defined locally within a particular code block (such as a function) become undefined once that code block is exited. Accordingly, monitoring the variables of a program that access memory may necessitate monitoring exiting and entering blocks of code where variables become defined and undefined. For instance, a pointer variable may be defined within a particular block of code and used to allocate memory from the heap. If that block of code is exited before the memory is released, this would, in many instances, constitute an error since there would be no way to free the memory allocated using the (subsequently undefined) pointer variable.

In a preferred embodiment, the system described herein determines nodes of interest at the test step 206 by determining if the CN corresponds to one of: a pointer arithmetic operation that compares pointers or does pointer arithmetic, an operation that reads memory locations, an operation that changes memory locations, or an operation that causes variables to become defined or undefined, such as a scope change, a goto statement, a function call or a return from a function call. In the case of memory variable operations, whenever a variable is used to read memory, the run time instrumentation routines determine if the variable corresponds to memory that has been allocated and initialized. Similarly, if a variable is being used to write memory, the run time instrumentation routines determine if the variable corresponds to memory that has been allocated. Pointer comparisons are instrumented since it is often not proper to compare pointers that point to blocks of memory allocated by separate calls to the allocation routine(s). Operations that read or write to memory locations are instrumented to ensure that the memory variable(s) being used point to the memory allocated for the variable(s) during the read or write operation (e.g., an array index does not cause an access to an array to point beyond the end of the array).

Function calls and returns may be instrumented for a variety of purposes, including keeping track of variables becoming defined or undefined in connection with function calls and returns. In addition, note that it is possible to pass a variable pointer to a function and have that pointer be assigned to another variable within the function. These types of operations are instrumented since, even if a local variable is used to allocate memory, if that local variable corresponds to a passed variable, then it may not be improper to return from the function before freeing the memory allocated using the local variable.

Each block of code has a particular "scope" associated therewith. Transition from a block of code having one scope to a block of code having another scope is called a "scope change". One reason scope changing instructions are instrumented is to detect memory leaks (i.e., allocating memory that is not subsequently freed). As discussed above, it is an error to allocate memory to a local variable and then return or exit out of the scope which defines the local variable without first freeing the memory or copying a pointer for the memory to a variable that is not going out of scope. Another reason that scope changes are instrumented is to detect read accesses to unitialized variables. Note that associating blocks of code with particular scopes is known in the art. See, for example, a section titled "Representing Scope Information" at pages 438-440 of Aho, Seth & Ullman, Compilers, Principles, Techniques, and Tools, published by Addison-Wesley of Reading Mass., 1986.

One possible optimization is to not instrument scope changes that have minimal effect on monitoring variable operations. This optimization may be performed by first determining the scope of each portion of the IR code and then setting an effective scope of appropriate portions of the code to the effective scope of the immediately preceding block of code. In some instances, the block of code that immediately precedes the current block of code is the "parent" block of code. A preceding block of code is said to have a "preceding scope" relative to the current scope. For instance, in some higher level languages, a FOR loop will cause a scope change in connection with transition from the head of the loop to the body of the code that is executed within the loop. Thus, the scope of the head of the FOR loop is the preceding scope of the body of the FOR loop.

An effective scope table indicates the effective scope of each block of IR code. As discussed in more detail below, the effective scope of a portion of IR code is deemed to be the scope of that portion for purposes of instrumenting operations that use program variables. The effective scope table creates a mapping between the actual scope and the effective scope of blocks of the IR code.

Referring to FIG. 8, a flowchart 220 illustrates using the IR code to construct the effective scope table. Processing begins at a test step 222 which determines if there is more data to be processed, in a manner similar to that discussed above in connection with other processing. If it is determined at the test step 222 that there is no more data, then processing is complete. Otherwise, control passes from the test step 222 to a test step 224 which determines if the data that has been read in and is being processed indicates a scope change. Note that, depending on the specific IR implementation, a scope change may be indicated explicitly within the IR data or may be indicated implicitly, in which case the processing at the test step 224
would use conventional means for detecting a scope change, such as examining the data for the type of instructions that cause a scope change.

If it is determined at the test step 224 that there is no scope change, then control passes back to the test step 222 to determine if there is more data to be processed. Otherwise, if a scope change is detected at the test step 224, then control passes from the step 224 to a step 226 where a unique scope identifier is defined and assigned to the code block being processed. Construction of the effective scope table includes providing a unique scope identifier for each block of IR code having the same scope. Accordingly, one of the entries in the effective scope table is the unique scope identifier associated with each of the IR code blocks.

Following the step 226 is a test step 228 which determines if new variables are being defined within the block of code corresponding to the current scope. The variable definitions may be stored in the IR tree 80 or may be stored elsewhere, depending upon the specific implementation of the IR. If no new variables are defined within the current scope, then, for purposes of instrumenting memory variable accesses, it is not necessary to instrument the scope change. Accordingly, if it is determined at the test step 228 that no new variables are defined within the block of code corresponding to the current scope, then control passes from the step 228 to a step 230 where the effective scope of the current block of code is set equal to the effective scope of to the preceding block of code by associating the effective scope of the preceding block with the current scope. Note that setting the effective scope of the current block of code to the effective scope of the preceding block of code indicates that the scope change from the preceding block of code to the current block of code is not especially significant for purposes of instrumenting variable accesses. Note also that the effective scope of a preceding block may have been previously set to the effective scope of the preceding block of the preceding block. In this way, many scopes may be set to the same effective scope.

If it is determined at the test step 228 that new variables are defined within the current block of IR code, then control passes from the step 228 to a step 232 where the effective scope table is modified to indicate that the effective scope of the current block of code is equal to the actual scope assigned to that block of code. Following either the step 230 or the step 232, control passes back to the beginning of the routine. The thus-constructed effective scope table may be used to provide instrumentation optimizations, as discussed below.

Referring to FIG. 9A, a flowchart 240 illustrates code for identifying labels and jumps to labels within the IR code. Note that, in many conventional IR implementations, symbolic labels are used to identify locations within the code so that control flow instructions within the IR code may jump to those labels. In some instances, a jump to a label could cause a scope change and, therefore, could be instrumented if the jump causes program variables to become defined or become undefined. However, a possible optimization includes identifying labels that do not require instrumentation either because there are no jumps to those labels or because all jumps to those labels are from code having the same effective scope as the code corresponding to the label.

Processing begins at a test step 242 which determines if there is more data to be processed in a manner similar to that discussed above. If there is no more data, then processing is complete. Otherwise, control passes from the test step 242 to a test step 244 which determines if the current IR node being processed is a label for a block of IR code. If so, then control passes from the test step 244 to a step 246 where the label is added to a label table that is used by follow on processing, as discussed in more detail below.

If it is determined at the test step 244 that the data being processed is not a label, then control passes from the step 244 to a test step 248 which determines if the current data being processed includes IR code that jumps to a label. If not, then control passes from the test step 248 back to the step 242 to process additional data. Otherwise, if it is determined at the test step 248 that the current data being processed includes IR code that jumps to a label, then control passes from the step 248 to a step 250, where an entry is made to the label table. Following the step 250, control passes back to the beginning of the routine to process additional data. The processing illustrated in the flowchart 240 creates the label table to identify all labels and all jumps to labels within the IR code. Note that the term "table", as used herein, should be understood in its broader sense to include other equivalent data structures such as linked lists, storage in a temporary file, etc., familiar to one of ordinary skill in the art.

Referring to FIG. 9B, a flowchart 260 illustrates optimization operations that use the label table. Each label that is identified in the label table is examined to determine if there are any jumps to that label or if any of the jumps to the label are from IR code blocks having a different effective scope. Processing begins at a test step 262 which, in a manner similar to that discussed above, determines if there is more data to be processed. Note that, in this instance, the test for more data at the test step 262 is directed to processing each of the label entries in the label table.

If it is determined at the step 262 that there is no more data (i.e., there are no more labels to be processed), then processing is complete. Otherwise, if there are more labels to be processed, then control passes from the test step 262 to a test step 264 which examines the label table to determine if there are any jumps to the current label being processed. Note that, generally, it is possible for the compiler to generate IR code having labels that are ultimately not used (i.e., there is no IR code that jumps to the labels). Accordingly, if such labels exist, they are detected at the test step 264 and control passes to a step 266 where the label is marked (in a conventional manner) to indicate that the label is not to be instrumented. Following the step 266, control passes back to the beginning of the routine.

If, on the other hand, it is determined at the test step 264 that there are jumps to the label being processed, then control passes from the step 264 to a test step 268 where it is determined if any of the jumps to the label are from IR code having a different effective scope than that of the label. Note that at the steps 246, 250 of FIG. 9A, the label table entries may be made to include the effective scope (from the effective scope table) of IR code corresponding to the labels and the jumps to the labels. Accordingly, at the step 268, the effective scope of the IR code corresponding to the label is compared with the effective scopes of all of the code containing jumps to the label. If it is determined at the step 268 that none of the jumps to the label are from IR code having a different effective scope than the code associated with the label, then control passes from the step 268 to the step 266, where the label is marked to indicate that the label is not to be instrumented. Since the effective scope tracks variables becoming defined and undefined within a code block and between different code blocks, then marking certain labels at the step 266 provides a worthwhile optimization when instrumenting code in connection with run time variable accesses.

If it is determined at the step 268 that there are jumps to the label that cause a change in effective scope, then control passes from the test step 268 back to the beginning of the routine. Once all the labels have been thus marked, it is possible to perform the remainder of the processing indicated by the step 206 in FIG. 7 where the nodes of interest are identified for subsequent instrumentation. Note that it is possible to use a boolean variable to indicate whether a label node is to be instrumented.

Referring to FIG. 10, a flowchart 280 illustrates a portion of the processing at the step 206 of FIG. 7 that determines which nodes in the IR code are to be instrumented. Processing begins at a test step 284, which is reached from the step 204
of FIG. 7. At the test step 284, it is determined if the data being processed corresponds to a label in the IR code. If so, then control passes from the test step 284 to a test step 286 to determine if the label has been marked to indicate that the label is not to be instrumented, as discussed above in connection with FIGS. 9A and 9B. If it is determined at the test step 286 that the label being processed has been marked to indicate that the label is not to be instrumented, then control passes from the test step 286 to the step 202 of FIG. 7. Otherwise, if it is determined that the test step 286 that the label is to be instrumented, then control passes from the step 286 to the step 208 of FIG. 7 where the IR tree 80 is instrumented.

If it is determined at the test step 284 that the data being processed is not a label, then control passes from the step 284 to a step 288 where it is determined if the data being processed indicates a scope change. If so, then control passes from the step 288 to a test step 290 to determine if the old effective scope (i.e., the effective scope before the scope change) equals the new effective scope (i.e., the effective scope after the scope change). The effective scope is discussed above in connection with construction of the effective scope table. If it is determined that the scope changed detected at the test step 288 does not cause a change in the effective scope, then control passes from the test step 290 to the step 202 of FIG. 7. Otherwise, if it is determined at the test step 290 that the old effective scope does not equal the new effective scope, then control passes from the step 290 to the step 208 of FIG. 7 where the tree 80 is instrumented.

If it is determined at the step 288 that the data being processed does not cause a scope change, then control passes from the step 288 to a test step 292 where is determined if the data being processed is a function call. If so, then control passes from the test step 292 to the step 208 of FIG. 7. Otherwise, control passes from the test step 292 to a test step 294 which determines if the data being processed is a pointer operation. If so, then control passes from the test step 294 to the step 208 of FIG. 7. Otherwise, control passes from the test step 294 to a test step 296 where it is determined if the data being processed is a memory write operation (i.e. an operation with a program variable causing a write to memory). If so, then control passes from the test step 296 to the step 208 of FIG. 7. Otherwise, control passes from the step 296 to a test step 298 which determines if the data being processed relates to a memory read (i.e., is an operation with a program variable causing a read from memory). If so, then control passes from the test step 298 to the step 208 of FIG. 7. Otherwise, control transfers from the step 298 to the step 202 of FIG. 7.

FIG. 10 illustrates an embodiment of the invention where the instructions being instrumented relate to memory variable accesses and scope changes. In other embodiments of the invention, it is possible to instrument other types of IR instructions, depending upon which instructions are deemed appropriate for monitoring program operation at run time. For example, it may be possible to add instrumentation to monitor run time performance of the program. Other examples of possible uses of instrumentation include, but are not limited to, code coverage analysis and run time error handling.

Instrumenting memory variable accesses and scope changes, as disclosed herein, facilitates uncovering program errors relating to memory read and write operations that occurred during run time. Note that the specific IR operations, and the arguments thereof, vary depending upon the particular implementation of the IR. In addition, as discussed above, the choice of which operations to instrument varies depending upon the needs of the user of the instrumentation program.

The step 208 of instrumenting the IR tree, which is shown as FIG. 7, involves adding nodes to the tree that assist in the performance of the run time instrumentation. As discussed in more detail below, each of the specific run time instrumentation routines that is provided may include a function that is called to perform the instrumentation operation. Note that the instrumentation calls are added in a way that has no net effect on the underlying, uninstrumented, program. That is, the behavior of the IR code with the run time instrumentation routines added thereto has to be the same as the behavior of the original IR code without the instrumentation routines added. Thus, the instrumentation routines may add new variables, but do not change any of the program variables except in instances where the value of a program variable is undefined. The additional nodes, instrumentation function calls, etc. may be provided by the instrumentation data element 69 shown in FIG. 4.

Referring to FIG. 11A, a portion of an IR tree is shown containing a unary operation node 310 and a child node 312 thereof. The operation node 310 represents a node of interest that is to be instrumented. The child node 312 represents the sole child of the operation node 310. In order to instrument the operation node 310, a run time instrumentation node 314 is interjected between the operation node 310 and the child node 312. The run time instrumentation node 314 may be a function call to a run time instrumentation function that uses the child node 312 as one of the arguments and returns the value of the child node 312 from the function call to make the value available for the operation node 310. Interjecting the run time instrumentation node 314 between the operation node 310 and the child node 312 in this manner is virtually transparent to the operation node 310, since the value returned by the run time instrumentation node 314 is the value of the child node 312. Note that other arguments may be provided in a conventional manner to the function corresponding to the run time instrumentation node.

Refer to FIG. 11B, a binary operation node 320 has a left child 322, a right child 324, and a parent node 326. If the operation node 320 is a node of interest, then it may be instrumented by interjecting various nodes that are effectively transparent to the operation node 320 as well as effectively transparent to the left child 322, the right child 324 and the parent node 326.

Referring to FIG. 11C, the operation node 320 is instrumented by adding a variety of other nodes. One of the other nodes that is added is a temporary node 328 that is used to store the value of the left child 322. An assignment node 330 is used to assign the value that results from evaluating the left child 322 to the value of the temporary node 328. As discussed below, right subtree is evaluated before the left subtree. Thus, the operation that evaluates the value of the left child and assigns the value to the temporary node 328 will occur before other operations shown in FIG. 11C.

An instrumentation node 332 is represented in the sub-tree of FIG. 11C as a function having arguments that include the temporary node 328 and the right child 324. Since the arguments to the function that corresponds to the instrumentation node
332 are illustrated as a list, then a list end node 334 is shown at the end of the list. Other arguments to the instrumentation node 332, as well as arguments to the instrumentation node 314 of FIG. 11A may include a variety of other conventional compile time and run time parameters that facilitate debugging.

The function defined by the instrumentation node 332 returns the result of evaluating the right child 324. Thus, the next operation is the operation of the instrumented node 320, which receives the value of the temporary node 328 and the value of the instrumentation function 332. Note that, as discussed above, the value of the temporary node 328 is the value of the left child 322 and the value of the function defined by the instrumentation node 332 is the value of the right child 324. Thus, the operation node 320 is provided with values for children that are the same as those provided to the operation node 320 shown in FIG. 11B. The node labeled "C" 336 of FIG. 11C simply causes execution of the right sub-tree (in this case having a root node 330 that does the assignment of the value of the left child 322 to the temporary node 328) followed by the operation of the left sub-tree (in this case the operation being instrumented 320). The node labeled "C" 336 provides the value derived from the operation node 320 to the parent node 326. Thus, the parent node 326 in FIG. 11C receives the same value provided to the parent node 326 in the configuration show in FIG. 11B. Instrumentation of the binary node illustrated in FIGS. 11B and 11C is expandable to ternary and to nodes having even more children using this same basic methodology described herein.

The run time instrumentation code may be implemented by using a separate set of routines (such as a DLL under the Windows environment) that is linkable to the code being instrumented via the function calls provided to the IR code in the course of instrumentation. In a preferred embodiment, the function calls are performed by indirectly calling functions that are initially set to an initialization routine that initializes the run time instrumentation system. The initialization routine determines if an executable library corresponding to the run time instrumentation routine is available. If not, then the addresses of the functions that are called indirectly by the indirect function calls added by instrumentation are set to "stub" routines that simply return without executing anything. Accordingly, even if the user program has been instrumented, if the run time instrumentation program is not also available during run time, then the instrumented code will simply return from the instrumentation function calls.

If, on the other hand, the initialization routine determines that the executable library for providing instrumentation during run time is available, then the addresses of the functions that are called indirectly by the instrumentation nodes are set to the instrumentation routines. The run time instrumentation routines that are used depend on the nature of the IR code being instrumented. Generally, the instrumentation routines may be fairly conventional and test for run time error conditions such as memory leaks (i.e., a scope change that causes a pointer variable to become undefined prior to freeing the allocated memory associated with the pointed variable). Other detected errors may include memory write operations that use variables that do not point to memory that is allocated to the variable, memory read operations that use memory variables that do not point to memory that is either allocated for the variable or, if allocated, then is not initialized. In addition, modifications to pointer variables may be instrumented to ensure that the pointer variables point to the proper allocated block of memory. Other run time instrumentation routines may test and compare the size of variables in connection with a data read from one memory location into another, test for indirect calls to assure that the pointer used points to executable code, and test that pointers that are compared are allocated to the same block of memory.

Once the IR tree 80 has been instrumented in the manner discussed above to create the instrumented IR tree data element 67, the tree deconstruction software 70 of FIG. 4 collapses the IR tree stored in the instrumented IR tree data element 67 and uses the other IR data element 68 to provide the instrumental IR Data Element 65. Collapsing the IR tree back into a flat file is a simple matter of using the conventional post order traversal algorithm to first write the right child sub-tree of each node, then the left child sub-tree, then the actual node. For the combo node, after the child tree is written, the list is processed, treating each item in the list as a top-level node in its own tree. This process is essentially the inverse of the process used to construct the IR tree, discussed above.

The other IR data element 68 shown in FIG. 4 may include a global symbol table that contains locations of each function contained in the IR code. Note that since IR code is being supplemented (i.e., increased in size) by the instrumentation process, then generally, the location of each of the functions within the IR code is likely to move. The locations of each of the functions are stored in the other IR data element 68 and are written back to the other IR data element 68 as the IR tree 80
is collapsed into a flat list by the tree deconstruction software 70 shown in FIG. 4. Note that global function symbols within the global symbol table, and corresponding functions within the IR tree, may be correlated in a conventional manner by using symbol keys that cross-reference items between the IR code and the items in global symbols table.

Once the instrumented IR data element 65 is provided, then, as shown in FIG. 3, the compiler 42 may continue the compile process by accessing the instrumented IR data element 65 to provide the object code 46. Instrumenting the IR code in this way is virtually transparent to the compiler 42 since the IR data element 64 and the instrumented IR data element 65 have virtually the same structure. The thus-provided object code 46 contains the additional nodes added during instrumentation, including the run time function calls that call the run time debugging routines.

During execution of the object code, errors may be indicated by the run time debugging routines in any one of a variety of conventional manners, including providing an indication on the screen and stopping execution of the code when the error occurs, logging errors to a file, or any one of a variety of other ways for indicating to a user that a run time error condition, or a potential run time error condition, has occurred.

Other embodiments also exist. Described below are methods of automatically editing the executable byte code representation of a computer program or other methods for generating instrumented byte code. In one embodiment, the byte code is altered by the addition of new instructions and/or the deletion or modification of existing instructions.

Byte code is a generic term for a family of binary (i.e., non-textual) file formats for computer software programs created by compiling source code written in a computer programming language. Byte code is a format that is usually independent of the source language from which it was compiled, and which is intended to be independent of any computer hardware and/or operating system on which it might run. Byte code programs are executed by a software program sometimes referred to as a virtual machine, byte-code interpreter or p-code interpreter, a separate version of which must be implemented for each computer hardware and/or operating system. One type of byte code, Java byte code, may be provided by compiling a Java source language program. The Java byte code may then be run on a computer having an appropriate program for interpreting the Java byte code. A detailed description of this may be found, for example, in The Java Virtual Machine Specification, by Tim Lindholm and Frank Yellin and published by Addison Wesley, of Reading Mass., 1997, which is incorporated by reference herein.

One objective of the instrumentation process is to alter the program to facilitate the gathering of diagnostic and statistical information on the program when it is executed; i.e., dynamic analysis. This allows the program's internal state to be monitored for variety of purposes. These purposes include, but are not limited to: diagnosing error conditions that occur at run time, creating a record of the inner details of program execution, measuring program execution to provide code coverage analysis and performance profiling, or providing additional run time error or exception handling.

Another objective of the editing process is to examine the byte code according to various heuristics; i.e., static analysis. Through static analysis, several types of useful information may be derived. These include, but are not limited to: code metrics and complexity analysis, usage information (including library usage), and enhanced symbolic information for debugging.

Static analysis also makes it possible to detect some types of errors that might not be caught at runtime, since it is difficult to guarantee that all code will actually be executed under all circumstances. These errors include, but are not limited to: improper parameter lists passed to functions, methods or procedures, and use of uninitialized variables.

There are many different ways to instrument byte code. In one embodiment, the editing is performed automatically as a separate post-compile process before the byte code is executed. In another embodiment, the editing is performed automatically by the run time environment itself, which has been modified to alter the code before it is executed. In a third embodiment, the final stage 55 of the compiler 42 shown in FIG. 3 generates instrumented byte code from the instrumented IR data 65 rather than generating the object code 46, as described above.

Referring to FIG. 12, a data flow diagram 400 illustrates operation of a virtual machine (VM) runtime system that interprets and runs byte code, such as Java byte code. In the data flow diagram 400, the VM runtime system has been broken up into two modules, a class instantiator 402 and a VM runtime module 404. The class instantiator 402 may receive a class input from any one of a variety of possible sources, including a file, over a local area network, from the Internet, from a zip file, from a CAB file, from another program that dynamically generates a class, or by any one of another variety of sources for computer data.

The class instantiator 402 generates a class instance 406, which, in a preferred embodiment, is a memory image representing a class that can be accessed by the VM runtime module 404 to perform operations indicated by the class instance 406. Absent any instrumentation, the class instance 406 is provided as an input to the VM runtime module 404 which interprets and executes the executable steps of the class instance 406 as well as performing any other operations indicated thereby.

In many implementations, a user can supplement the byte code provided in the class instance 406 with separate native code that may be used in conjunction with the byte code. In the case of the VM runtime module provided by Microsoft Corporation of Redmond, Washington, one of the interfaces between byte code and native code is called the Raw Native Interface (RNI). In the case of the VM runtime module provided by Sun Corporation of Burlington, Mass., an interface between byte code and native code is called Java Native Interface (JNI).

The interface may be provided by allowing declarations of method names and parameters in the byte code and by having a special designator indicating that the executable portions corresponding to the declared methods are found in one or more blocks of native code 408 that are separate from the VM runtime module 404. The native code runtime mechanism is described in more detail hereinafter in connection with describing instrumentation of native code.

Byte code may be instrumented by instrumenting each class as the class is loaded by the VM runtime system. As shown in FIG. 12, the class instance 406 is provided to an instrumentation DLL 410 which instruments the byte code of the class instance 406 to provide an instrumented class instance 412. The instrumented class instance 412 is provided as an input to the VM runtime module 404 instead of the class instance 406. That is, the VM runtime module 404 uses the instrumented class instance 412 instead of the class instance 406. The mechanism for providing the instrumented class instance 412 to the VM runtime module 404 is described in more detail hereinafter.

The instrumented class instance 412 contains native calls to a monitoring DLL 414 which provides a message stream to a plurality of analyzers/viewers 416 that are used to view the results of the instrumentation. In some instances, the monitoring DLL 414 may make calls in to the VM runtime module 404 to obtain more information for the message stream. Also note that it is possible to optionally store the message stream data in a message data storage 417. Storage of data in the message data storage 417 may be in addition to, or alternative to, providing the data to the analyzers/viewers 416. The monitoring DLL 414, the analyzer/viewers 416, and the message data storage 417 are described in more detail hereinafter.

Referring to FIG. 13, a flowchart 420 illustrates basic operation of the instrumentation DLL 410. The instrumentation program 410 operates in cooperation with the VM runtime system and may take advantage of particular hooks or calls provided by the vendors of the VM runtime system.

The flowchart 420 shows a first step 422 where the instrumentation DLL 410 receives a pointer and a size value for the class instance 406, which allows the instrumentation DLL 410 to access the class instance 406 in connection with providing instrumentation. Following the step 422 is a step 424 where the instrumentation DLL 410 allocates space for providing the instrumented class instance 412. In some embodiments, this allocation may be performed using conventional memory allocation routines. In other instances, the vendor of a VM runtime system may provide specialized memory allocation routines to be used. Following the step 424 is a step 426 where the class is instrumented to provide the instrumented class instance 412. Instrumentation of the class is described in more detail hereinafter. Following the step 426 is a step 428 where a pointer to the space that was allocated at the step 424, as well as a size value, are passed back to the VM runtime system in order to allow the VM runtime module 404 to use the instrumented class instance 412.

In embodiments where a specialized space allocation routine is used at the step 424, processing may be complete after the step 428. In those cases, the VM runtime module 404, or other portions of the VM runtime system, handle deallocation of the space allocated at the step 424.

In other embodiments, the instrumentation DLL 410 waits for the VM runtime module 404 to use the instrumented class instance 412. This is represented by the test step 430 which shows the instrumentation DLL 410 waiting for the VM runtime module
404 to signal the VM routine module 404 is done with the instrumented class instance 412. Of course, this may be implemented in a conventional fashion by having the VM call a particular entry point in the instrumentation DLL 410 so that the instrumentation DLL 410 does not have to poll the VM runtime module 404. Following the step 430 is a step 432 where the instrumentation program 410 deallocates the space that was allocated at the step 424. As discussed above, the steps 430, 432 may not be necessary in instances where a specialized memory allocation routine is used at the step 424 and the VM runtime system handles deallocation of the allocated memory.

The hooks in to the VM for providing the capabilities described above are provided by each VM vendor. For example, for the VM provided by Microsoft, the hooks are provided in the Microsoft Software Development Kit (SDK) for Java, Version 3.0, which is freely available from the Internet at http://www.microsoft.com/java. The hook used to intercept Java classes as they get loaded into the VM is declared in a C++ header file called "jclshook.h". In an installed version of the SDK, this file resides in the include directory called "include/jclshook.h". The mechanism that is used to cause the instrumentation DLL to be loaded into the Microsoft VM is part of Microsoft's Java Language Profiler Interface, which is discussed in detail in the SDK documentation. The SDK documentation is shipped as HTML. Two main files that provide information about the hook mechanism are Docs/htm/jprf_nar.htm and Docs/htm/jprf_refhtm.

In a preferred embodiment, not all classes that are loaded are necessarily instrumented. As discussed in detail below, there are special cases of classes that are not instrumented at all. In addition, there are other special cases of classes that are only partially instrumented, as described in more detail below.

Referring to FIG. 14, a flowchart 440 illustrates in more detail the step of instrumenting the class 426 of FIG. 13. All methods of the class, both static and non-static, are instrumented, with a few exceptions set forth below. The flowchart
440 illustrates instrumentation of a method.

Processing begins at a step 442 where the entry of the method is instrumented. Instrumentation of the method entry point at the step 442 is described in more detail hereinafter. Following step 442 is a step 444 where the next byte code instruction of the method is examined. The step 444 represents reading through each byte code instruction of the method and thus, each time the step 444 is performed, the next instruction of the method byte code is examined.

Following the step 444 is a test step 446 where it is determined if the end of the method has been reached. If it is determined at the test step 446 that the end of the method has been reached, then control passes to a step 448 where the method is instrumented to catch any aborts that occur while the method is being executed. Instrumenting for aborts at the step 448 is described in more detail hereinafter. Following the step 448, processing is complete since the end of the method has been reached.

If it is determined at the test step 446 that the end of the method has not been reached, then control passes from the test step 446 to a test step 450 where it is determined if a new line number has been reached. Note that, in many conventional byte code compilers, there is a switch allowing the user to obtain line number information correlating the source code line numbers with the byte code generated from that source code. The line number information may be provided in the form of a table. If line number information is available, then the test step 450 determines if the byte code being examined corresponds to a new line number in the source code by comparing the entries in the line number table with the byte code offset.

If it is determined at the test step 450 that byte code corresponding to a new source code line number has been reached, then control passes from the test step 450 to a step 452 where byte code is inserted into the method to cause a local line number variable to be set to the new line number when the method runs. The local line number variable, which is created at the method entry step 442, is described in more detail hereinafter.

Following the step 452 or the step 450 is a test step 454 where it is determined if a throw instruction has been reached. If so, then control passes from the test step 454 to a step 456 where the throw instruction is instrumented. Instrumenting the throw instruction at the step 456 is described in more detail hereinafter. Following the step 456, control passes back to the step 444 where the next byte code instruction is examined.

If it is determined at the test step 454 that a throw instruction has not been reached, then control passes from the test step 454 to a test step 458 where it is determined if an exit point for the method has been reached. An exit point for the method at the step 458 may be detected by, for example, detecting a return instruction in the byte code. If it is determined at the test step 458 that an exit point for the method has been reached, then control passes from the test step 458 to a step
460 where the exit point is instrumented. Instrumentation of the exit point at the step 460 is described in more detail hereinafter. Following the step 460, control passes back to the step 444 where the next byte code instruction of the method is examined.

If it is determined at the test step 458 that an exit point for the method has not been reached, then control passes from the test step 458 to a test step 462 where it is determined if the byte code instructions that are being examined correspond to a call to another method. If it is determined at the test step 462 that a method call has been reached, then control passes from the test step 462 to a step 464 where the line number of the current method is instrumented. Instrumenting the line number at the step 464 is described in more detail hereinafter. Following the step 464, control passes back to the step 444 where the next instruction is examined. The step 444 is also reached if it is determined at the step 462 that the byte code being examined does not correspond to a method call.

Referring to FIG. 15, a flowchart 470 illustrates in more detail the instrumentation of the method entry step 442 of FIG. 14. Processing begins at a first step 472 where a local line number variable for the method is created in a conventional manner by incrementing max_locals for the function and providing storage space for the local line number variable. The local line number variable is used during instrumentation to keep track of lines of source code that correspond to the byte code and is set during run time to correlate the byte code and the source code line numbers of the method being instrumented. The local line number is also used in connection with other instrumentation that is described elsewhere herein.

Following the step 472 is a test step 474 where it is determined if the method being instrumented is a static method. The indication as to whether or not a method is a static method is provided in the access_flags byte associated with the method. If it is determined at the test step 474 that the method being instrumented is not a static method, then control passes from the step 474 to a step 476 where byte code instructions are inserted to push the this pointer of the non-static method on to the stack. For non-static methods, the this pointer may be used to identify the object on which the method was invoked.

Note that parameters that are passed during instrumentation are passed in a conventional fashion using the stack. Thus, the parameters are pushed on to the stack prior to invocation of the monitoring function being called.

Following the step 476, or following the step 474 if the method being instrumented is a static method, is a step 478 where instructions are inserted to push the method parameters that were passed to the method when the method was invoked. Note that the number and type of parameters passed to the method when the method was invoked may vary. Thus, the instructions that are inserted to push the parameters at the step 478 may similarly vary.

Following the step 478 is a step 480 where the byte code is instrumented by inserting instructions that push method information. In a preferred embodiment, the method information is a record that includes a method identifier, information identifying the number and types of parameters of the method, the local line number, and the type of instrumentation being performed. The same monitoring function may be called for instrumenting enter, exit, and abort. Thus, the type of instrumentation information differentiates among the three types within a generic monitoring function that is called.

Following the step 480 is a step 482 where instructions are inserted to call the monitoring function. The result of the call to the monitoring function that is inserted at the step 482 is described in more detail hereinafter. Following the step
482, processing is complete.

Referring to FIG. 16, a flowchart 490 illustrates in more detail the instrumentation for an abort step 448 from the flowchart of FIG. 14. As discussed above, this instrumentation code is inserted at the end of the method being instrumented.

Processing begins at a first step 492 where the exception table is modified to indicate that the code being added in connection with instrumenting for abort is to be executed whenever an otherwise uncaught exception occurs. Following the step
492 is a step 494 where instructions are inserted to cause the object that is thrown in connection with the exception to be on the stack. Note that, in this instance, it is sufficient to duplicate (DUP) the item at the top of the stack since the thrown object is already at the top of the stack. In a preferred embodiment, both a pointer to the object, and what Microsoft refers to as the object's "hash code" are provided. The hash code is a unique identifier for an object. Use of the unique identifier is described in more detail hereinafter. Note that, unless indicated otherwise, all objects are pushed on to the stack along with the corresponding unique identifier (e.g., the hash code) therefor. For example, in instances where the this pointer is pushed on to the stack, a unique identifier (e.g., the hash code) for the this pointer is also pushed.

Following the step 494 is a test step 496 where it is determined if the method being instrumented is static and a step 498 for pushing the this pointer on to the stack. The steps 496, 498 are similar to the steps 474, 476, described above in connection with FIG. 15. Following either the step 496 or the step 498 is a step 500, which inserts instructions to push the method parameters on to the stack in a manner analogous to that discussed above in connection with the step 478. Following the step 500 is a step 502 that inserts instructions to push the method information on to the stack.

Following step 502 is a step 504 where byte code instructions are inserted to call the monitoring function. Following the step 504 is a step 506 where instructions are inserted to throw the object associated with the abort. Throwing the object in this manner causes execution of the code to be, more or less, the same as it would have been had the exception table not been modified at the step 492. Following step 506, processing is complete.

Referring to FIG. 17, a flowchart 510 illustrates in more detail the processing at the step 460 of FIG. 14 where the method exit is instrumented. Processing begins at a test step 512 where it is determined if the method being instrumented has a return value. The determination at the step 512 may be made in a conventional manner by examining the signature of the method, which is retrieved from the constant pool of the class instance that contains the method being instrumented. If it is determined at the test step 512 that the method being instrumented has a return value, then control passes from the test step 512 to a step 514 where instructions are inserted to cause a copy of the return value to be on the top of the stack. In this instance, it is sufficient to duplicate the value at the top of the stack since the return value of the method will already be at the top of the stack.

Following the step 514, or following the step 512 if the method does not have a return value is a test step 516 where it is determined if the method being instrumented is static and a step 518 for pushing the this pointer on to the stack. The steps 516, 518 are similar to the steps 474, 476, described above in connection with FIG. 15. Following step 518, or following the step 516 for static methods, control passes to a step 520 where instructions are inserted to push the method parameters in a manner analogous to that discussed above in connection with other instrumentation. Following the step 520 is a step 522 instruction are inserted to push the method information on to the stack. Following the step 522 is a step 524 where instructions are inserted to call the monitoring function. Following the step 524, processing is complete.

Referring to FIG. 18, a flowchart 530 illustrates in more detail the step 456 of FIG. 14 of instrumenting a throw instruction. Processing begins at a step 532 where instructions are inserted to cause the object being thrown to be on the top of the stack. In this instance, it is sufficient to duplicate the item at the top of the stack, which is the object being thrown. The step 532 is similar to the step 494 of FIG. 16, described above. Following step 532 is a step 534 where instructions are inserted to push the method identifier (not the method information discussed above in connection with FIGS. 15-17). Following step 534 is a step 536 where instructions are inserted to push the line number on to the stack. Following step 536 is a step
538 where instructions are inserted to call the monitoring function. Following step 538, processing is complete.

Referring to FIG. 19, a flowchart 550 illustrates in more detail the step 464 of FIG. 14 where the line number is instrumented. Processing begins at a first step 552 where instructions are inserted to push the line number. Following step 552 is a step 554 where instructions are inserted to call the monitoring function. Following the step 554, processing is complete.

Referring to FIG. 20, a flowchart 600 illustrates instrumenting the class 406 of FIG. 12 to provide the instrumented class 412. Processing begins at a test step 602 where it is determined if the class being instrumented is a special class. Special classes are particular classes that either are not instrumented or are instrumented in a special way. Examples include classes containing low level byte code methods provided by the VM vendor where instrumenting the methods would not provide useful information to the user. In most instances, deciding whether to instrument various methods is a design choice based on a variety of functional factors familiar to one of ordinary skill in the art. If the class being instrumented is a special class, control passes from the test step 602 to a step 604 where the special class is handled in a manner described in more detail below. Following the step 604, processing is complete.

If it is determined at the test step 602 that the class being instrumented is not a special class, then control passes from the test step 602 to a step 606 where an index of the class instance is created. The index of the class instance may be a table containing entries indicating the offsets, in the class instance, of various items in the class instance, such as the offsets of each of the methods in the class. The class index is a convenient mechanism that can be used in a conventional manner to assist in providing the functionality described hereinafter.

Following the step 606 is a test step 608, which represents iterating through the methods of the class to instrument each method. If it is determined at the test step 608 that there are more methods to instrument, control passes from the test step 608 to a test step 610 where it is determined if the method being processed is implemented in native code. As discussed above, different VM vendors provide different mechanisms for allowing native code to be called from byte code. In many instances, the interface involves declaring the native method in the source code and providing a specific identifier with the declaration indicating that the executable portion of the native function is provided in a routine external to the resulting byte code.

If it is determined at the test step 610 that the method is implemented in native code (by examining the access_flags in the class), control passes from the step 610 to a step 612 where instrumenting the native code is handled by, for example, adding a byte code wrapper to the method. The wrapper causes the VM (and the instrumentation softw