Note: Descriptions are shown in the official language in which they were submitted.
CA 02355839 2001-06-18
WO 00/4388b PCT/US00101034
INSTRUMENTATION OF CALLS TO ROUTINES FOR WHICH SOURCE CODE IS UNAVAILABLE
TECI3NICAL FIELD
s The invention relates to a method and system for instrumentation
of a computer program for testing and debugging, and more particularly, to
instrumenting computer programming code modules whose corresponding source
code is unavailable for instrumentation.
BACKGROUND OF THE INVENTION
to The software development process typically consists of the
production of numerous source code modules that collectively constitute a
complete computer program. One or more of the source code modules may
invoke the execution of a programming code module, such as those provided as
invocable functions in a library file. A programming code module comprises
is either object code or executable code that has typically been provided by a
third
party. A library f Ie contains a collection of programming code modules that
may be invoked by a computer program. Each programming code module within
a library has a unique name and performs a different task from the other
programming code modules. A library typically contains only the object code
for
2o a collection of programming code modules. Invoking a programming code
module provided by a library simplifies the production of new computer
programs by freeing the programmer from having to re-write programming
instructions to perform the same task provided by a programming code module in
a library.
2s To form an executable computer program, the programmer
compiles his source code modules to produce object code and then links his
object code together with any programming code modules invoked by the source
code. Since mulriple programmers on separate computing machines may have
CA 02355839 2001-06-18
WO 00/43886 PCTIUS00101034
2
written one or more of the source code modules, the source code modules or the
compiled code modules typically need to be transferred to a single computer
for
linking together to form an executable computer program. Once the executable
computer program has been generated, the programmer can test and debug the
s computer program using conventional testing and debugging techniques.
The sheer number of source code modules in a computer program
often renders the resulting computer program extremely complex. Testing and
then debugging computer programs are important steps in any software
development process, and these steps become even more important for complex
to computer programs. indeed, debugging (i.e., correcting any errors) may even
constitute a contractual requirement before acceptance of the computer program
by its intended users. Nat surprisingly, the difficulty of testing and
debugging
computer programs generally increases as complexity increases. In addition,
the
difficulty in testing a complex computer program also increases as the number
of
is programmers increases and with the number of invoked programming code
modules, typically in the form of library functions.
When testing a computer program, a programmer must typically
ensure that each source code module performs its intended function correctly
and
that the entire computer program (including any invoked programming code
2o modules) also performs its intended functions correctly. To properly debug
a
computer program, a programmer typically needs to trace the program's
execution. An execution trace indicates exactly which steps in the computer
program have been executed and the order of their execution.
Instrumenting a program's source code modules provides a means
2s for generating an execution trace. Source code instrumentation
conventionally
consists of inserting an executable tagging variable assignment statement, or
"tag," into the source code modules of a computer program at various tagging
points during or prior to compiling the source code module. Tagging points are
places of interest in the source code module, such as the alternative branches
of a
3o selection statement and execution of a loop statement, where a programmer
may
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
3
want to know the state of the computer program as it executes. At each tagging
point, the tagging variable assignment statement conventionally assigns a
unique
value to a tagging variable. An instrumentation database ("IDB") holds data
regarding the tagging point, such as the tagging value assigned to the tagging
s variable at each tagging point and information about the source code module
at
the tagging point.
A programmer can then execute the instrumented computer
program and monitor the values assigned to the tagging variable in order to
trace
the execution of the computer program. The tagging values produced during the
to computer program's execution can be saved to provide an execution trace of
the
computer program. Following execution of the computer program, these tagging
values provide references for identifying the tagging points in the computer
program. Thus, the tags serve as a means for indicating execution of a
particular
fragment of the computer program.
is Instrumentation can typically be accomplished using the "by
address" or "by value" schemes. The instrumentation by value scheme has been
described above. In the instrumentation by value scheme, different tagging
values are written to a single memory location, and the tagging value written
to
that location corresponds to a particular tagging point in the computer
program.
2o In an instrumentation by address scheme, a tagging instrumenter sets aside
a
unique memory location having a unique address for each tagging point and the
tagging variable assignment statement stores a tagging value in the unique
location. For example, a single tagging value can be used, and if this tagging
value is written to a unique location, then the programmer can infer that a
2s corresponding tagging point in the computer program has been executed.
Specialized probes typically intercept the tagging values used in both schemes
and write them to a flle which can be examined by the programmer and used as a
tool for debugging the computer program.
Table 1 provides an example of a source code module prior to its
3o instrumentation with tags. Source Code Module l, shown in Table 1, contains
CA 02355839 2001-06-18
W0 00/43886 PCT/USOOJ01034
4
pseudocode for two variable assignment statements to variable "A" (ln. 4 and
ln.
8), a "while" loop (In. S), programming code module invocations (lns. 8 and
17),
and an "if then-else" statement {lils. 10-I6). The programming code module
invocations at lines 8 and 17 are function calls to third-party provided
library
s functions, 3rd Party Lib1() and 3rd Party Lib2n. Source Code Module 1
contains no tags, and its executable code will not emit tagging values (i. e.,
execute tagging variable assignment statements). Accordingly, non-instrumented
Source Code Module 1 will not provide the programmer with a reference table of
emitted tagging values to verify, for example, which branch of the if then-
else
to statement (lns. 10-16) has been executed.
1. Saurce Code Module 1 (A. B)
2.
3.
15 a. A=0:
5. while A_>0
6.
r. A=A+B:
s. 3rd Party Lib1(A.B):
2Q 9. }
lo. if A>10
11. then
12.
13. }
25 la. el se
15.
16. B = A/B: '
1. A = 3rd_Party~Lib2(X.Y.Z)+ A + ((C + D)/12):
18. }
30 19.
20.
21.
22. }
TABLE I
35 Table 2 shows Source Code Module I following its instrumentation
with tags in an instrumentation by value scheme. A tagging instrumenter has
inserted a declaration for a tagging variable, "AMC Control Port" (ln. 2), in
Source Code Module i. (In an instrumentation by address scheme, the
instrumenter typically inserts declarations far multiple tagging variables.)
The
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
tagging instrumenter has also inserted tagging variable assignment statements
at
various tagging points (lns. 7, 11, 15, 19, 23, and 27) within the Source Code
Module 1.
5 1. Instrumented Source Code Module 1
(A. B)
2, external volatile unsigned long AMC~Control
Port:
3. {
4. A=0:
s. while (A>0)
AMC_Control Port=0:
e. A=A+B:
9. 3rd_Party_Libl(A.B)
lo. }
1511. AMC Control_Port=1:
12. if (A>10)
ls. then
14. {
15. AMC Controt_Port=2:
2016.
1. e1 se
la. {
19. AMC_Control_Port=3:
20. B=A/B:
2521. 3rd Party Libl(X.Y,Z):
22. }
2s. AMC_Control_Port=4:
24. .
25.
302fi.
2~. AMC_Control_Port=9:
2s. }
TABLE 2
An executable computer program containing instrumented Source
3s Code Module 1 will emit tags during execution. Thus, the programmer may
examine a table of emitted tagging values to determine which steps from Source
Code Module 1 have been executed. For example; a programmer may ascertain
whether "A = A + B" (ln. 8) in Source Code Module I has been reached during
execution by determining whether a tagging variable having a value of "0" (ln.
7)
4o has been stored in a table of emitted tagging values. If a "0" has been
stored,
then the programmer may infer that the executing program reached the statement
"A = A + B," and if a "0" has not been stored, then the programmer may infer
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
6
that the executing program did not reach the statement "A = A + B." A
programmer using the tagging instrumenter may incrementally improve upon the
efficiency and robustness of his computer program through the use of tagging
variable assignment statements. Using a tagging instrumentation system, the
s programmer may eliminate or correct weaknesses in the source code to make
the
resulting computer program execute as efficiently as possible.
The programmer cannot instrument programming code modules
that do not have source code available for instrumentation, such as that
provided
by the "3rd Party-Libl" function in line 21, because the programmer typically
to receives only the object code for a library function and not its source
code.
Because a tagging instrunnenter inserts tags into source code, the tagging
instrumenter cannot instrument library functions or any other form of
programming code module. Thus, the programmer cannot easily gauge the
efficiency of a programming code module or determine when he should either
is contact a programming code module's supplier to request a more efficient
programming code module or abandon use of the programming code module
altogether and compose a more efficient replacement. Accordingly,
programmers would benefit from the ability to determine the efficiency of
programming code modules invoked by their computer programs that do not have
2o source code available for instrumentation.
SUMMARY ~F THE INVENTION
The invention provides a method and apparatus for testing and
debugging a computer program that includes one or more programming code
modules without source code available for instrumentation with tags. A
2s programmer indicates to a tagging instrumenter which programming code
modules should be instrumented by directing the tagging instrumenter to the
declaration statements for the set of programming code modules to be
instrumented. The tagging instrumenter assigns a unique programming code
module identifier to each indicated programming code module and records the
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
7
programming code module's name for subsequent identification during
instrumentation of the computer program's source code.
The tagging instrumenter then inserts a tagging variable assignment
statement before and after each invocation of a selected programming code
s module in the computer program's source code. The tagging instrumenter
assigns a value to an entry tagging variable assignment statement comprising
an
entry code and the programming code module's unique identifier. The tagging
instrumenter assigns a value to an exit tagging variable assignment statement
equal to an exit code and the programming code module's unique identifier. The
to tagging instrumenter may utilize the same pair of values at each invocation
of a
given programming code module in the source code. By assigning the same
tagging values for a given programming code module, the tagging instrumenter
may group tagging variable assignment statements so that invocations of the
same programming code module at different points in the computer program may
is be identified in terms of a specific programming code module rather than
merely
in terms of a programming code module invocation.
During execution of the instrumented computer program, a data
reduction processor retrieves the tagging variable assignment statement value
pairs associated with invocations of the instrumented programming code
zo modules. Analysis of the tagging variable assignment statement value pairs
provides data related to the efficiency of each instrumented programming code
module, including the cumulative time expended during execution of each
instrumented programming code module.
BRIEF DESCRIPTION OF THE DRAWINGS
2s Aspects of the invention will be described below relative to the
following figures. Note that similar elements and steps in the figures have
the
same reference number.
Figure 1 illustrates a tagging instrumenter associated with the
invention.
CA 02355839 2001-06-18
WO 00/43886 PCTIUS00/01034
8
Figure 2 illustrates an instrumentation monitoring system
associated with a tagging instrumentation system shown in Figure 1.
Figure 3 shows an example source code module containing
invocations of third-party programming code modules.
s Figure 4 shows an example tagging value format associated with
the invention.
Figure S shows the computer program depicted in Figure 3
following the insertion of tagging variable assignment statements around the
programming code module invocations.
to Figure 6 illustrates sample IDBs associated with the invention.
Figure 7 is a flowchart of the programming code module
instrumentation software and procedure, according to one embodiment of the
invention.
Figure 8 illustrates the instrumentation and compilation of source
is code modules on multiple computing machines.
DETAILED DESCRIPTION OF THE INVENTION
The disclosed embodiment of the invention provides an
instrumentation tagging method and apparatus that instruments programming
code modules whose source code may not be available for instivmentation.
2o When the tagging instrumenter encounters an invocation statement in the
computer program for a programming code module whose corresponding source
code is unavailable for instrumentation, such as the source code for a third-
party
library function, the tagging instrumenter inserts tagging variable assignment
statements around the invocation statement and remembers the tagging value
2s assigned to the invoked programming code module for subsequent invocations.
When the tagging instrumenter re-encounters an invocation statement for a
programming code module, the tagging instrumenter assigns the same value to
the tagging variable assignment statement that the tagging instrumenter
assigned
to previous invocations of the programming code module. The tagging
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
9
instrumenter utilized in the invention directly instruments available source
code
in the conventional manner by inserting tagging variable assignment statements
into the source code prior to or during the compiling procedure.
The tagging instrumenter could insert tagging variable assignment
s statements around all programming code module invocation statements within
the computer program; however, this approach suffers from two problems. First,
a large computer program typically contains a plethora of programming code
module invocation statements, including those whose source code is available
for
instrumentation. In fact, the computer program may contain many more
to programming code module invocation statements than a program tester would
care to instrument or even that the tagging instrumenter would be functionally
capable of instrumenting. Thus, the tagging instrumenter generally requires a
mechanism for directing it to the set of programming code module invocation
statements that should be instrumented. Second, even if the tagging
instrumenter
is could instrument all the programming code module invocations, the tagging
instrumenter should nevertheless tag invocation statements for the same
programming code module in the same manner regardless of where in the
computer program invokes the programming code module. A program tester
generally receives more useful information about a programming code module by
2o knowing the cumulative amount of time spent executing the programming code
module than by knowing that the programming code module was invoked at a
specific point in the computer program. Accordingly, an appropriate solution
entails assigning the same value in a tagging variable assignment statement
for
the same programming code module in order to provide a mechanism for
2s determining how often and for how long the computer program executes a
specific programming code module, such as a third-party provided library
function.
The tagging instrumenter still requires a mechanism for tagging
only those programming code modules of interest to the program tester. All
3o third-party supplied programming code modules must be identified to the
CA 02355839 2001-06-18
WO 00143886 PCT/US00/01034
computer program in order for the computer program to direct its execution to
the specific programming code modules. Header files provided with third-party
library code provides a mechanism for readily selecting third-party provided
functions of interest. For example, in programming languages such as C and
C++,
s a header file is provided that includes declaration statements for the
function
calls within a library. Vendors of particular software products and peripheral
equipment may also provide programming code modules specific to their
products which may be invoked by a computer program.
The program tester directs the tagging instrumenter's attention to
to specific programming code modules by indicating which header files include
programming code module declarations whose progrannming code module
invocations should be instrumented around. Once the tagging instrumenter
knows which programming code module invocations should be instrumented,
through the mechanism of the header file, then the tagging instrumenter
inserts a
is unique pair of tagging variable assignment statements around each
invocation of
the programming code modules declared within the header file. The tagging
instrumenter makes a notation in an instrumentation database ("IDB") to tag
around all programming code module invocations that occur with regard to the
programming code modules declared in each selected header file. Thus, the
2o tagging instrumenter first examines the indicated header files to look for
programming code module declarations. The IDB remembers the header file
information and provides the header file information to the tagging
instrumenter
as the tagging instrumenter parses the source code looking for places in which
to
insert tagging variable assignment statements. The IDB also retains an
indication
2s as to whether a particular programming code module has been encountered in
the
computer program and the value assigned to the tagging variable assignment
statement for that programming code module.
The tagging instrumenter and method is particularly applicable to
the languages C, C++, Java and Ada. In an otherwise conventional tagging
3o system, the programmer or program tester merely indicates to the tagging
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
11
instrumenter which header files, such as a library.h file, contain programming
code modules of interest. Of course, the inventive concept is applicable to
almost any programming language because in order for a computer program to
utilize programming code modules provided by a third party, such as a library
s function, the program must include some mechanism for identifying the
programming code modules, their location and their arguments and return
values,
if any. The manner of informing the computer program about the programming
code modules may be used as a mechanism for directing the tagging instrumenter
to instrument around invocations of the programming code modules. Of course,
to some languages such as Ada, for example, do not utilize header files but
rather
incorporate such information using a slightly different mechanism.
.Nevertheless,
the techniques are equally applicable to these languages.
Figure 1 illustrates one embodiment of a tagging instrumenter in
accordance with the invention. A source code instrumentation system 100
as includes a compiler 101 and a tagging instrumenter 102. The source code
instrumentation system 100 receives source code 103 and instruments the source
code 103 by inserting executable tagging variable assignment statements into
the
source code 103 at various locations of interest prior to or during the
process of
compiling the source code 103 in the compiler 101. The compiler 101
2o communicates with the tagging instrumenter 102, which, in turn,
communicates
with an instrumentation database ("IDB") 104. The IDB 104 holds data
regarding tagging points, such as the tagging value assigned to the tagging
variable at each of the tagging points and information about the source code
module at the tagging points. If the program tester needs to receive
information
2s regarding the efficiency of third-party provided programming code modules
106,
the program tester may direct the tagging instrumenter 102 to insert tagging
variable assignment statements around invocations of the programming code
modules I06 within the source code 103 which will be detected during execution
of instrumented executable code 107. This same process may be used to
3o instrument other portions of the source code 103 in the conventional
manner.
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
12
The instrumentation system 100 produces instrumented object code 105
following the instrumentation procedure. The instrumented object code 105 and
the programming code modules 106 are linked together to form the instrumented
object code 107.
s An executable tagging variable assignment statement assigns a
value to the tagging variable, with the value having a precise meaning that
identifies a particular action occurring in a computer program. As previously
discussed, the programming code modules 106 are typically provided by a third
party only in the form of object code or executable code. Accordingly, the
1o tagging instrumenter 102 may not instrument source code for the programming
code modules 106. However, the tagging instrumenter 102 may instrument
around invocations of the programming code modules 106 within the source code
103.
The tagging instrumenter 102 will insert tagging variable
is assignment statements assigning the same value at each invocation of an
identified programming code module. This procedure provides better statistical
information than the conventional instrumentation process, which assigns a
unique value to each tagging variable assignment statement, because, in the
case
of programming code module invocation statements, determining the cumulative
2o execution time period for a programming code module provides more helpful
information than merely knowing that the programming code module has been
invoked a given number of times. For example, regarding invocations of a
programming code module named "Character," a program tester receives more
helpful information knowing that five percent of the total execution time for
a
2s computer program involves execution of "Character" than merely knowing that
"Character" has been invoked six times by the computer program, although the
program tester will receive this information as well. Interpreting the
information
regarding the "Character" programming code module would be more complicated
if unique tagging values were used at each invocation of "Character" than by
so using the same tagging value pairs at each invocation. Following execution
of an
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
13
instrumented computer program, a data reduction processor will have
information regarding how many times each selected programming code module
has been invoked and the amount of execution time expended on the
programming code module.
s Figure 2 illustrates an instrumentation monitoring system
associated with a tagging instrumentation system shown in Figure 1. Once a
computer program has been instrumented with tagging variable assignment
statements, specialized testing equipment monitors execution of the computer
program. As the computer program executes within CPU 200, specialized
to hardware 203 detects writes to particular locations in memory 202. One
example
of suitable specialized hardware 203 is disclosed in U. S. Patent Application
No. 08/526,709, "Method and Apparatus for Analyzing Software Executed in
Embedded Systems," naw U.S. Fatent No: 5,748,878 to Rees et al. which is
assigned to Applied Microsystems, Inc., and which is incorporated herein by
is reference. In the instrumentation by value scheme, the specialized hardware
knows the address of the tagging variable. As the computer program executes,
data passes between the CPU 200 and the memory 202 through address/data bus
201. Probe 205 monitors the address bus 201 and looks for occurrences of the
writing of data to the tagging variable address location. When the probe 205
2o detects a write to the tagging variable, the probe 205 copies the tagging
value
using a data bus connection 204. The probe 205 then appends a time stamp to
the tagging value before passing the tagging value to a data reduction
processor
207 through connection 206. The data reduction processor 20? identifies
certain
tagging points as requiring additional processing. For example, the data
2s reduction processor 207 pairs programming code module entry and exit
tagging
values so that the difference in time stamps may be calculated to determine
the
amount of time spent during the execution of the respective programming code
module. As previously discussed, the tagging instrumenter inserts programming
code module entry and exit tagging statements around specified programming
so code module invocation statements rather than within the programming code
CA 02355839 2001-06-18
WO 00!43886 PCT/US00l01034
14
module itself. The data reduction processor 207 then prepares a report that
includes a list of tagging values and their respective time stamps, a list of
executed programming code modules identified by tagging values along with
"performance" statistics, and a compressed list of executed tagging values to
s indicate their execution, (e.g., a "coverage map"). The report may also
contain
other information.
The data reduction processor 207 forwards this report to a
workstation which provides the report to a graphical user interface ("GUI")
208.
The GUI 208 identifies the tagging points corresponding to the tagging values,
to found in the report from the data reduction processor 207, using the data
stored
in the IDB 104. The GUI 208 then prepares any of several reports, which may
include additional information besides the identification of the tagging
points to
indicate the flow of execution. Additional information appended to each
reported tagging point may include the name of the programming code module
is from which the tagging variable assignment statement has been executed, the
line
numbers for the programming code module invocation, and other information
identifying the nature of the tagging point. A programmer monitors the
execution trace report from the workstation GUI 208 to determine whether the
computer program operates within expected parameters.
20 The instrumentation monitoring system does not necessarily
require that the probe 205 be a hardware probe in order to detect tagging
values
produced during execution of the computer program. Detecting executed tagging
variable assignment statements essentially requires an ability to capture data
that
is written outside of the CPU 200. Suitable probes for this purpose include
2s hardware probes, as well as performance of a write operation to a disk
file, a
write operation to local memory, or a function call accessing
telecommunications
software outside of the CPU 100. A suitable probe includes any process by
which tagging values persist subsequent to the execution of the. computer
program.
CA 02355839 2001-06-18
WO 00/43886 PCTIUS00/01034
In order for a computer program to emit tagging values during
execution, the computer program must first be fitted with tagging variable
assignriient statements, as discussed above. A tagging instrumenter typically
inserts tagging variable assignment statements into the source code modules of
a
s computer program during an instrumentation pass, which occurs either before
or
during compilation of the source code modules, such as shown Figure 1.
Figure 3 shows an example source code module containing
invocations of third-party programming code modules. As previously discussed,
the source code for programming code modules is not available to the tagging
to instrumenter. Accordingly, the tagging instrumenter "instruments around"
programming statements that invoke programming code modules. In addition,
the tagging instrumenter preferably uses the same entry and exit tagging
values
for a given programming code module, for the reasons previously discussed. In
"Pgm-One," a programming code module 3rd Party Lib 1 310 is invoked on
is lines 14, 30, 100, and 120. A 3rd Party Lib2 programming code module 320 is
invoked on line 21, and a 3rd Party Libl programming code module 330 is
invoked on line 41. The tagging instrumenter inserts an entry tag 301 at
points
preceding the invocation of the 3rd Party Libl programming code module 310
and an exit tag 302 at points following the invocation of this programming
code
2o module. Similarly, the tagging instrumenter inserts an entry tag 303 before
invocation of the 3rd PartyrLib2 programming code module 320 and an exit tag
304 following this programming code module. The tagging instrumenter inserts
an entry tag 305 before the invocation of the 3rd Party~Lib3 programming code
module 330 and a corresponding exit tag 306 following the invocation of this
2s programming code module. As shown in Figure 3, the tagging instrumenter
inserts the same programming code module entry and exit tags 301 and 302
before all invocations of the 3rd Parly_Lib 1 programming code module 310.
Utilizing the same pair of tagging values allows the data reduction processor
207
to determine the cumulative amount of program execution time utilized in each
30 of these programming code modules.
CA 02355839 2001-06-18
WO 00/43886 PCTIUS00101034
16
When using a tagging by value scheme, the tagging variable
assignment statement normally has a simple form such as "AMC control_port =
0x12345678" where the monitored tagging variable "AMC control~ort" is
assigned a unique tagging value "Ox 12345678." Figure 4 shows an example
s tagging value format associated with the invention. In this example, the
tagging
variable value is a 32-bit integer. The example tagging variable value format
401
comprises an entry code or an exit code 402 and a programming code module
identifier 403. The same entry code and exit code may be utilized for all
entry
and exit tagging variable assignment statements and comprises a minimal number
to of bits in the value of the 32-bit tagging integer. The programming code
module
identif er 403 comprises most of the 32-bit tagging variable value format 401
and
uniquely identifies each of the programming code modules that will be tagged
by
the tagging instrumenter. During instrumentation, the tagging instrumenter
records the programming code module identifier 403 associated with each
is programming code module in the IDB 104 while examining the declaration
statement for the programming code module in the source code (e.g., the header
file) and subsequently recalls the recorded programming code module identifier
403 when the tagging instrumenter encounters an invocation of the programming
code module during instrumentation of the computer program's source code.
2o Programming code module declarations may be found throughout the source
code for the computer program but are typically found in a header file
referenced
by the computer program.
Figure 5 shows the computer program depicted in Figure 3
following the insertion of tagging variable assignment statements around the
2s programming code module invocations. As previously discussed, invocations
of
the same programming code modules receive the same tagging values.
Accordingly, the tagging variable assignment statements inserted before the
3rd Party Lib 1 programming code module 310 on lines 13, 29, 99, and 119 have
the same value ("Lib 1 Entry_Value"). The tagging instrumenter has inserted
so tagging variable assignment statements having the value "Lib 1 Exit Value"
CA 02355839 2001-06-18
WO 00143886 PCT/US00/01034
17
following invocation of the 3rd_Party Lib I programming code module 310 at
Iines 15, 31, 101, and I21: A tagging variable assignment statement having the
value "Lib2 Entry Value" has been inserted before invocation of the
3rd Party Lib2 function 320, and the tagging instrumenter has also inserted a
s tagging variable assignment statement having the value "Lib2 Exit Value"
following the invocations of this programming code module. Similarly, the
tagging instrumenter has inserted a tagging variable assignment statement
having
the value "Lib3 Entry Value" preceding the invocation of the 3rd Party Lib3
programnung code module 330 and has inserted a tagging variable assignment
to statement having the value "Lib3 Exit Value" following the invocation of
this
programming code module. As previously noted, each tagging variable
assignment statement receives a unique value with respect to the instrumented
programming code modules.
As described above, the probe 205 monitors the address to which
is tagging variable values are written. For example, if a particular tag
represents
entry into the 3rd Party Lib i programming code module 310, then at run-time
when the computer program emits the unique tagging value assigned to this tag,
the program tester can deduce that the computer program has executed the
tagging variable assignment statement at the entry to the 3rd Party Libl
2o programn;iing code module 310. Similarly, if at run time, the computer
program
emits the unique tagging value assigned to the exiting of the 3rd Party Libl
programming code module 310 then the program tester rnay also deduce that the
computer program has executed the tagging variable assignment statement at the
exit of the programming code module 3rd PariyTLib 1 programming code module
25 3I0. Moreover, comparison of the time stamps associated with each of these
entry and exit tags reveals the amount of execution time expended in the
3rd Party Lib 1 programming code module 3 I0. The data reduction processor
207 may add together all of the execution times for executions of the
3rd Party Lib 1 programming code module 310 to determine a cumulative
CA 02355839 2001-06-18
WO 00/43886 PCTIUS00/01034
18
amount of execution time expended by invocations of this programming code
module during the operation of the computer program.
Figure 6 illustrates sample IDBs associated with the invention.
IDBs 601, 602, and 603 contain the tagging values and other program
s information provided by the tagging instrumenter. Each IDB may represent one
source code module and may have been produced during source code
instrumentation on separate computers. The IDB 601 contains data representing
programming code module invocation entry values and exit values for the
programming code modules invoked in Figure 5. For example, data recorded in
to the IDB 601 includes the values for the Libl'Entry Value and the
Lib 1 Exit Value assigned to the tagging variable assignment statement as
shown
in Figure 5. The IDB 602 and the IDB 603 respectively contain entry and exit
values for programming code modules invoked within other source code modules
of the computer program.
is Figure 7 is a flowchart of the programming code module
instrumentation softwaxe and procedure, according to one embodiment of the
invention. The instrumenter selects each source code module of the computer
program, inserts the declaration statements and tagging variable assignment
statements into the selected source code module, and stores instrumentation
20 tagging data in an IDB. First, the instrumenter examines any include files
associated with the computer program and adds all of the programming code
modules listed in the include files to a programming code modules names list
(step 703). The tagging instrumenter then determines whether any more source
code modules of the computer program require instrumentation (step 705).
2s When no more source code modules remain to be instrumented, the tagging
instrumentation process terminates {step 707). However, if there are still
source
code modules requiring instrumentation, the tagging instrumenter selects the
next
source code module to be instrumented (step 709). The tagging instrumenter
updates the IDB to record information regarding the next source code module to
3o be instrumented (step 711). If the user has selected a relocatable tagging
CA 02355839 2001-06-18
WO 00143886 PCT/US00/01034
19
mechanism, then each source code module may result in the opening of a new
IDB and the selection of a name for the new IDB. A method and system for
relocatabie instrumentation tags is described in U.S. Patent Application
No. 09/015,256, "Relocatable Instrumentation Tags for Testing and Debugging a
s Computer Program," filed on January 29, 1998, which is assigned to a common
assignee, and hereby incorporated by reference. The tagging instrumenter then
begins examining the source code module (steps 713-717). The tagging
instrumenter inserts a declaration for the tagging variable into the source
code
module (step 713). The tagging.instrumenter then inserts the tagging variable
to assignment statements into the source code (steps 715-717). The tagging
instrumenter determines if tagging points remain in the source code module
(step
715). If tagging points remain, the tagging instrumenter locates the next
tagging
point within the source code module. These tagging points may be tagging
points other than programming code module invocation statements. Upon
is locating a programming code module invocation on the programming code
modules names list, the tagging instrumenter inserts tagging variable
assignment
statements into the source code both before and after the invocation statement
and makes an appropriate entry in the IDB (step 717). The tagging variable
assignment statements will be assigned a tagging value equal to the
appropriate
2o entry or exit value for the programming code module, such as the value
shown in
Figure 4. As discussed with regard to Figure 4, the tagging variable
assignment
statement typically has a form such as:
AMC_Control Port - (entry code or exit code) and
2s ~ (programming code module identifier)
The statement may have any form that allows the tag value to be suitably
communicated, including via a function call, e.g., "AMC Record Tag (<tag>)."
The tagging instrumenter then loops (to step 715) to process any
so remaining tagging points. After instrumenting the source code module, the
IDB
for this source code module is closed (step 718). The tagging instrumenter
then
CA 02355839 2001-06-18
WO 00l4388b PCT/US00101034
loops (to step 703) to determine whether there are other source code modules
to
be instrumented. The tagging instrumenter stores the data for the tagging
points
and the library function values in the IDB.
Once the tagging instrumenter has completed instrumenting the
s source code modules for the computer program, then the tagging instrumenter
terminates and allows the compiler to produce object code for the computer
program. The object code may be linked together with other object code and the
programming code modules to form an executable computer program that
contains~executable tagging variable assignment statements.
to In a tagging "by address" instrumentation scheme, the invention
could be implemented by assigning a unique pair of tagging variables to each
programming code module listed in the include files. The tagging instrumenter
would still insert tagging variable assignment statements around each
invocation
of selected programming code modules. However, instead of assigning a unique
is value to the tagging variable, the tagging instrumenter would insert a
unique
tagging variable pair associated with the programming module and then assigned
to that tagging variable pair a constant value appropriate for a tagging by
address
scheme, e.g., the same value for all tagging variable assignment statements.
Table 3 illustrates an instrumented source code module. As shown
2o at the top of the pseudocode representing Instrurnented Source Code Module
I in
Table 3, the tagging instrumenter has inserted a declaration statement for the
tagging variable, which in this example is an external volatile unsigned long
variable named "AMC Control Port" (ln. 3). The tagging instrumenter has
examined the source code module shown in Table 3 and inserted tagging variable
2s assignment statements around all of the programming code module invocation
statements such as at lines 9 and I I. In an actual tagging assignment
procedure,
the tagging instrumenter also inserts tagging variable assignment statements
around other programming points of interest such as the "while" statement at
line
7; however, for simplicity these tagging variable assignment statements have
not
CA 02355839 2001-06-18
WO 00/43886 PCT/USOO101034
2I
been illustrated here. Execution of the particular tagging variable assignment
1. Instrumented Source Code Module 1
2.
3. external volatile unsigned long AMC Control Port:
4. int. A,B.C.D.X.Y.Z.dummy:
5, {
6. A=0:
7. while (A>0)
_
e. f
AMC Control Port=<libl tag entry value>:
lo. 3rd Party
Libl(A.B):
11. _
AMC_Control Port=<iib2 tag
exit value>:
i5 12. ~
A=A+B:
13. }
14.
15. if (A>10)
ls. then
17. {
la. AMC Control Port=<lib2 tag entry value>:
19. 3rd Party Lib2(A.C.X.Y):
20. AMC Control Port=<lib2 tag exit value>:
n.
2z. ~ else
23. {
24. AMC Control Port=<libl tag entry value>:
25. 3rd Party Libl(X.Y):
zs. AMC
Control Port=<libl
tag exit
value>:
27. '
~
~
28.
29. A = (AMC Control Port = <lib2 tag entry value>.
3o. dummy = 3rd Party Lib2(X.Y.Z). AMC
Controi Port =
31. ~
<lib2
tag exit
value>. dummy) + A +
32. _
_
((G + D)/12):
33.
34. AMC Control Port=<lib3
tag entry value>:
35. ~
3rd Party Lib3(A.Z):
3s. AMC_Control Port=<lib3 tag exit value>::
37.
TABLE 3
statements inserted at lines 9 and 11 will alert the program tester of the
invocation and execution of the 3rd Party Lib 1 (line 10). As previously
discussed, the same tagging values will be assigned to the tagging variable
4s assignment statements inserted around each invocation of the same
progranuning
code module. For example, 3rd Party Lib 1 is invoked at lines 10 and 25. The
CA 02355839 2001-06-18
WO 00/43886 PCTlUS00/01034
22
value assigned to the tagging variable inserted before both invocation
statements
is the same, e.g., Libl Tag Entry Value. The corresponding tagging variable
assignment statements inserted after the invocation of 3rd Party Lib 1 also
have
the same value (Lib 1 Tag_Exit Value), as shown on lines 11 and 26. By
s utilizing the same tagging values around each invocation of a programming
code
module, the data reduction processor can easily determine the cumulative
amount
of execution time for a particular programming code module and the average
amount of time spent during each invocation of the programming code module.
The tagging instrumenter assigns different tagging values to
to different programming code modules, e.g., 3rd PartyLib2 and 3rd Party_Lib3.
Information passed into the IDB during the instrumentation procedure includes
the line and column numbers of the programming code module declaration in the
header file.
The tagging instrumenter may also tag around programming code
is module invocations occurnng within an expression. For example, as shown in
line 29, the tagging instrumenter has inserted tags around the invocation of
the
3rd Party Lib2 programming code module that is contained in a longer
expression. In order for the value returned by the 3rd Party_Lib2 programming
code module to be retained for computation by the expression, the instrumenter
2o inserts a "dummy" variable that is added into the expression "A+(C+D)/12."
The
"dummy" variable receives the value returned from the 3rd Party Lib2 which
may be then added into the expression so that the complete statement will
compute the same value that it would if instrumentation was not performed. The
tagging instrumenter utilizes the programming code module's declaration
2s statement to determine what type of value (e.g., integer or real) will be
returned
by the 3rd Party-Lib2 , function and inserts a declaration statement at the
beginning of the source code module that provides an appropriate declaration
for
the variable "dummy."
CA 02355839 2001-06-18
WO 00/43886 PCT1US00/01034
23
1. InstrumentedSource Code Module 2(A,B)
2.
3. external atile unsigned long AMC Control
vol Port:
_ _
4. ~
s. AMC_ControlPort=<Module 2 entry code>:
6. 1=12X8:
7. if (iz43)
s. then
9.
l0 10. Pgm Moduie 42(A,B>:
11.
12.el se
13.
la. AMC Control Port=<lib3 tag
entry value>:
ls. 3rd Party Lib3(A,B):
ls. AMC Control Port=<lib3 tag
exit
value>:
1. AMC~Controll_
_
Port=<Modulew2 exit code>:
ls. }
TABLE 4
- 20 - Likewise, Instrumented Source Code Module 2, as shown in
Table 4, also includes the declaration statement for the tagging variable,
"AMC Control Port" (ln. 3). Table 4 represents three different modes of
treating the tagging of functions in a computer program. Where the source code
for a function is available for instrumentation, the tagging instrumenter
inserts
2s tagging variable assignment statements within the source code module itself
(at
lines 5 and 17). When the source code is not available for instrumentation and
the tagging instrumenter has not been directed towards a declaration for a
particular programming code module, then invocations of the programming mode
module will not be instrumented around (line 10). In contrast, when a
so programming code module does not have available source code but the tagging
instrumenter has been directed towards a header file including the programming
code module, the tagging instrumenter will insert control tags around
invocations
of the programming code module (lines 14 and 16).
For example, the tagging instrumenter has inserted tagging variable
3s assignment statements within Instrumented Source Code Module 2 indicative
of
the kind of tagging variable assignment statements that may be inserted within
invoked functions whose source code is available for instrumentation.
CA 02355839 2001-06-18
WO 00/43886 PCT/US00/01034
24
Accordingly, the tagging instrumenter has inserted function entry tags at
lines 5
and 14 and function exit tags at lines 16 and i7. Again, the tagging
instrumenter
has inserted tags at a number of points of interest within source code module
2;
however, Table 4, like Table 3, only shows the tags inserted with regard to
s programming code module entry and exit. The programming code module
"PGM Module 42" represents a programming code module whose source code
is not available for instrumentation and whose header file has not been
indicated
to the tagging instrumenter as containing programming code of interest for
instrumentation. Accordingly, the tagging instrumenter has not inserted
tagging
to variable assignment statements around the function "PGM Module 42." In
contrast, the "3rd Party Lib3" programming code module represents a function
contained within a header file to which the tagging instrumenter has been
directed to tag. Accordingly, the tagging instrumenter has inserted tagging
variabie assignment statements appropriate to both the entry and exit of the
is "3rd Party Lib3" programming code module around the entry to and exit from
this function.
As previously stated, a computer program may contain multiple
source code modules such as the source code modules shown in Tables 3 and 4.
These source code modules may be separately compiled and linked together to
2o form an executable computer program. This process supports the
instrumentation of huge computer programs involving thousands of source code
modules that may be instrumented and compiled in parallel, saving enormous
amounts of time. A method and system for further facilitating the compilation
and linking of instrumented source code is described in U.S. Patent
Application
2s No. 09/0/5,256, "Relocatable Instrumentation Tags for Testing and Debugging
a
Computer Program," filed on January 29, 1998, which is assigned to a common
assignee, and which has been previously incorporated by reference herein.
Figure 8 illustrates the instrumentation and compilation of source
code modules on multiple computing machines. A source code module 1 801a is
3o instrumented with tagging statements to produce instrumented source code
802a
CA 02355839 2001-06-18
WO 00/43886 PCT/USOO/OI034
and a corresponding IDB 1 804a. The instrumented source code is then compiled
to produce compiled code 805a. This process may occur entirely on Comnutina
Machine 1 800a. Similarly, the instrumentation and, compiling of other source
code modules may occur on other computing machines, e.g., Computing
s Machine 2 800b and Computing Machine 3 800c. The compiled instrumented
code (e.g., compiled code 805a, 805b, and 805c) and invoked programming code
modules 820 may be linked by a linker 810 on a Computing Machine N 806 to
produce executable code 811. The IDBs from the various computing machines
may also be compiled into a master IDB 809. The entries in the master IDB 809
to will correspond to the executable tagging variable assignment statements in
the
executable code 8I 1.
The following provides an example of the invention in operation.
Suppose that a programmer experiences difficulty in improving the performance
of computer programming code used in the operation of a computerized widget.
Is The programmer has instrumented his own source code and has eliminated or
corrected all the weaknesses in the code in order to make the computer program
operate as efficiently as possible. However, the programmer's program also
uses
a programming tool in its computerized widget has been provided to the
programmer by the computerized widget's manufacturer in the form of various
20 library functions. The source code for these programming code modules is
not
available for source code instrumentation. Accordingly, the programmer has no
ability to determine the efficiency of these third-parley library functions.
Utilizing the instrumenter described herein, the programmer instruments around
all of the program's invocations of functions associated with the computerized
2s widget. The programmer then determines by operation of the instrumented
computer program that an inordinate amount of execution time is expended in
processing invocation statements for particular functions in the libraries
provided
by the computerized widget manufacturer. Armed with this information,
including precise examples of frequency and time, the programmer may then
contact the computerized widget manufacturer and tell him which specific
CA 02355839 2001-06-18
wo oai43ss6
26
PCT/US00/01034
functions in the library code operate too slowly. In addition to contacting
the
computerized widget manufacturer, the programmer may also write alternative
functions that operate in a more.efficient manner.
From the foregoing it will be appreciated that, although specific
s aspects of the invention have been described herein for purposes of
illustration,
various modifications may be made without deviating from the spirit and scope
of the invention. For example, the tagging instrumenter may alternatively
assign
a value to the programming code .modules that is the same for both entry and
exit, with the data reduction processor keeping track of whether a received
io tagging value can be paired with a previously received value for the same
programming code module. When a tagging value is received, the data reduction
processor software makes an indication that this value relates to an entry,
and
when the same tagging value is received again, the data reduction processor
makes another indication that this value corresponds to an exit from the
l.s programming code module.
In this embodiment, a greater number of programming code
modules may be instrumented because no space in the tagging variable will be
occupied by an entry code or exit code. Similarly, the tagging instrumenter
may
utilize a greater or smaller value for the tagging assignment variable than
has
2o been provided herein for illustrative purposes (e.g., a 16-bit or 64-bit
value).
Also, the term "module" refers to any portion of a computer program, which may
include a complete source code file, a portion of a source code file, a
function, a
procedure, or some other collection of statements that form the computer
program. The present invention is operable in systems using a standard
compiler
2s that operates in conjunction with a tagging instrumenter as well as in a
system
whose compiler has incorporated an instrumenter.
Accordingly, the invention is not limited except as by the appended
claims.
