As more fully described in [1], the goals of this Berkeley Pascal system are:
The Pascal execution profiler, hereafter referred to simply as pxp , results from the second design goal. The system, however, would benefit greatly from a more complete debugging facility. A design for an interactive and post-mortem debugger pdb for the system exists [6], but has not been implemented as of this writing.
Execution profiling is quite simple in concept. One merely places counters at a sufficient number of points in the program to allow the determination of the number of times each statement has been executed. Knuth, in [7], gives an algorithm for determining the minimum number of counters necessary to gather complete information.
Berkeley Pascal code is interpreted. Thus the addition of statement counters does not tend to have a significant degrading effect on the speed of execution. Even in heavily travelled loops, a statement counter is of low enough execution cost that techniques for, e.g., moving counters out of for loops were determined to be unnecessary. More complicated techniques such as determining the number of calls on a procedure or function by adding together the call counts for all calling sites would not materially decrease the time in execution and would add significantly to the complexity of the post-processing. It was thus decided not to do any counting optimization of this type.
A more subtle consideration involved non-local goto statements. Without global analysis, which was not available in the one-pass compiler scheme being used, there is always the possibility that an arbitrary procedure or function call will not return to the calling site. To maintain accurate counts and a simple scheme when non-local goto statements are allowed would likely involve the placement of a counter after each such procedure or function call. The presence of these extra counters could easily multiply the number of counters required for typical programs by a factor of 5 or more.
As goto statements which cut across levels of control tend to be used only in infrequently occurring error situations, it was decided not to place counters to allow for non-local goto statements. Counters are not placed after each procedure and function call so, if a call fails to return, the counts will be inaccurate to the next sampling point.
An option to allow for correct counts in the presence of non-local goto statements was considered, but rejected. It was felt that such an option would rarely, or never, be used. It is the author's belief that summary data flow information indicating possible non-local control transfers would be necessary if the placement of counters were to be done appropriately.
Thus, it was decided to place counters at the following program points:
The counts are made completely accurate in the presence of local goto statements by placing an extra counter after each if , repeat , while and for statement which contains a goto . If there is no goto statement in such a statement, the count after the statement is taken to be the count before the statement. .PP It was later suggested to the author that one could count the frequency of each individual label in a case statement, rather than keeping one count for each group. This might provide useful information for some programs, but has not been implemented as an option.
A final consideration related to the placement of counters over parts of the program only. This would surely be desirable if gathering profile data were expensive. In this case a user might be able to restrict his cost by specifying which parts of his code were to be counted. After it was decided that the profile listing would be constructed by reparsing the source text of the program and combining it with the profile data, it seemed clear that the savings from such partial counting would not materially affect the overall cost of producing a profile. It was therefore decided to allow selectivity of profile output in pxp rather than selectivity of count gathering at compile or execute time.
Given the collected data in the form of an array of statement counts, one then wishes to produce a listing of all or part of the program with the count information appended in an easily understandable form. It seems clear that a system which presents the count information to the user with associated source text from his program will be superior to one which merely produces a table of counts for identified points in the program.
Satterthwaite's ALGOL W debugging system [8] produced such a listing by unparsing a saved internal form of the source program. In his system this internal form was also used to provide symbolic flow-trace information at run time. As we did not propose to do symbolic statement tracing in our debugger design [6], there was no need for an internal form of the source program to be available at run time. Given the fact that our operating system is primarily disk-space limited, it was decided that reparsing the source text of the program to produce the execution profile was a reasonable approach. This allows the profiler to use the existing source text of the program without requiring a potentially large intermediate form. This also allowed the profiler to use the existing parser and to receive as its input a well defined parse tree as described in [1].
Thus the execution of a program normally produces a file named pmon.out which contains an array of counters. The code generated need contain only the instructions required to prepare these counts. This solution is very conservative of disk storage resources.
In cases where the execution of a Pascal program terminates abnormally, or has to be terminated due to apparent infinite looping, it is often desirable to obtain a profile to help discern the cause of the error. The Pascal runtime system will create the pmon.out file in these cases, and profiling is still possible.* It should be noted that, in general, the information so gathered is not as usable as that which could be garnered easily by using a debugger such as pdb [6], since variable values are not available.
* If the Pascal runtime system terminates due to a fault, either because of a bug in the runtime system, a severe misuse of pointers, or an untested out-of-range subscript, a core-image file will be produced. It is possible, using a pxp option, to extract the profile information from this core image, allowing profiling in this case also.
A final point to be noted is that the counts are inaccurate near the suspended control points whenever the program terminates abnormally. This is explained more fully in [3]. The complete debugging system design included the marking in the profile of the point of abnormal termination in a fashion similar to that used by Satterthwaite [9], but this has not yet been implemented.
As already noted, easy comprehension by the user of the the profile produced by pxp requires that the profile be in a readable form. One possibility would be an annotated source listing, using the form of the original source text. This has the advantage that the listing is in a form familiar to the user. A major disadvantage in this approach is the fact that the format of the source may not leave room for easy placement of all of the profile information.
There have been a number of systems designed or constructed which provide automatically restructured listings of programs [10] [11] [12] [13]. Such programs have often been called ``pretty printers.'' It is not hard to see that the production of a readable profile from a well-structured listing would not be difficult given the framework of a pretty printer. It was therefore decided to produce such a restructured listing and to annotate it with the profile information. An option to use the execution profiler as a pretty printer was also provided.
One problem with the evolving approach was the treatment of comments. The interface from the parser to the semantic routines in the compiler, which was the available and highly suitable framework, had no provision for the placement of comment text anywhere in the parse tree. For the purposes of profiling this could be easily tolerated. An effort can be made when profiling to suppress output which is not absolutely necessary in the profile. In particular, comments, declarations, and the bodies of unexecuted procedures and functions could be normally suppressed. In fact, early versions of pxp suppressed all of these. In the current implementation, however, the default is that only the bodies of unexecuted functions and procedures are suppressed. All such suppression is controllable through options as described in [3].
The design of the comment formatting facility for pxp is presented in section 3. The author feels that significantly better approaches to program maintenance and formatting are possible in future systems. Some possibilities are discussed in section 4.
Many different formats for presenting Pascal structure are possible. The author's personal programming style largely determined the structure of programs produced by pxp. In particular, the author was bothered by one feature of other ``pretty printers.'' Many other pretty printers present a ``bushy'' if-then-else construct in a fashion similar to the following:
if condition1
then statement1
else if condition2
then statement2
else ...
This could be termed ``wandering across the page.''
In structured programs, especially in a language which contains no return or other escape statement, it is easy to get ``buried'' in many levels of conditions. While the merits of escape-less programming are debatable, it seems important to present the structure of the above construct as clearly as possible. The author feels that a more appropriate way to present this statement is often the following:
if condition1 then
statement1
else if condition2 then
statement2
else
...
Another aspect of modern programming languages which are not well-bracketed is the presence of begin-end pairs, which, if mismatched, can cause problems, especially if they escape detection at compile time. With an automatically reformatted listing, the user no longer needs to worry that his listing may textually represent the structure of the program in a way different from the true structure. Given this situation, the author feels that the words begin and end convey no information to the user that is not already reflected in a more convenient form by the textual indentation.
Thus in considering how to represent the ``bushy'' if-then-else when statement1 and statement2 are begin-end blocks and choosing between:
if condition1 then
begin
statement list 1
end
else if condition2 then
begin
statement list 2
end
and
if condition1 then begin
statement list 1
end else if condition2 then begin
statement list 2
end
the author chose the latter, which he prefers.
It should be noted that this is essentially the syntax of the language ALGOL 68 [14], and is similar to Wirth's MODULA [15], e.g.:
if condition then
statement list 1
elsif condition2 then
statement list 2
fi
Another issue of style arises in choosing how many spaces to indent each structured statement of the source text. While 8 spaces per level is very convenient since one level then corresponds to one ASCII tab character, 4 spaces seemed to work best with the execution profile when using an adaptation of the format of Satterthwaite [8]. Thus, options were provided to allow a level to be defined as any small number of column positions, with 4 columns the default.
The printing of expressions presented yet another problem. It was felt that a format which reflected the true structure of an expression was best. For this reason, a fully parenthesized expression format was first tried. This turned out to be a very poor choice as it made complicated expressions very hard to read. The author then implemented a minimal-parenthesis format as the default with full parenthesization as an option.
It is probably true that many users would prefer to have their parenthesization preserved even when the parentheses deleted are, in fact, unnecessary. This would be even more true in a language which had a large number of precedence levels with a large number of operators. It is not as necessary in Pascal since there are only a small number of levels here, but such an option would have been useful in any case. This option is not, however, included in the current pxp.
It was decided that procedure and function definitions which are nested within one another would be indented one structured statement level by default to improve readability. An option was included to omit this indenting if desired.
The end keyword of each procedure and function is labelled with the name of the procedure or function. This is done also for the opening begin if any nested procedure or function definitions occur within the procedure or function.
When first designing the statement formats, the author felt that the statements in a case statement should be formatted so that cases with one and cases with more than one statement would line up for easy readability. At the time, 8 spaces per level was the default format and the choice was between:
case ch of
' ':
col := col + 1;
tab:
col := (col + 8) mod 8;
'*':
begin
tok := star;
tokval := line
end
end
and
case ch of
' ':
col := col + 1;
tab:
col := (col + 8) mod 8;
'*':
begin
tok := star;
tokval := line
end
end
With the eventual choice of 4 spaces per structured level as the default indentation, the difference between the corresponding formats is slight. In retrospect, this was not necessarily sufficiently valuable to justify the amount of time spent on the case statement format, as different strategies were needed for each indenting option, and the format was optimized to be ``pretty'' in each case subject to the alignment constraint. Thus the current pxp uses only the simpler first strategy.
Labels are place on a separate line, aligned with the header line of the containing program, procedure or function. Placed this way, they are easy to locate.
In general, the text editing facilities on the UNIX system are geared toward line oriented editing. Thus it is extremely convenient to have statements on single lines. For this reason the format of the programs produced by the pretty printer gives section keywords like var and type alone on a line. In this way deleting the first declaration of such a section is made easier - there is no need to split the keyword away from the first declaration.
Other options, such as an option to underline all of the keywords in the program, are provided by pxp . These are detailed more fully in [3].
In summary, the profiler format reflects the taste of the author in Pascal formatting at the time this program was written. It largely succeeds in producing readable Pascal texts.
Treatment of long statements and placement of multiple statements per line are desirable additions and a design for some of these is described in section 2. They were omitted from the original design only because the author was not initially sure of a reasonable way to proceed in these areas, and felt that these were more important in the context of a pretty printer. pxp was intended primarily as an execution profiler. Even without the features of section 3, earlier versions of pxp were useful in showing students who had trouble formatting their programs one acceptable way of writing Pascal.
The basic format for the profile is essentially that of Satterthwaite [8] [9]. Examples are given in [3]. The following pieces of information are included with the profile in addition to the basic count information.
This information serves to identify uniquely the program involved.
The algorithm for count interpretation is given in [3] and is essentially the same as that given by Satterthwaite in [9].
Two options for compressing profile data are available. One gives a table of the procedures and functions with their activation counts. This requires only a very small amount of data even for large programs.
More easily readable than a simple table are profiles of parts of a program. These can be obtained without modifying the source text. One can give a list of procedure or function names on the command line, and profiles will be enabled for these and their contained procedures and functions only.
This ability to extract selective information and to be able to do it without modifying the source code is critical. Editing the source code (at least twice!) for each profiling pass would not only be tedious, but could easily be done incorrectly. The command line syntax is simple and relatively foolproof. This feature is fully described in [3].