systems programming language C.
is very similar to that of the Pascal translator
was, until recently, a conditional compilation of
uses the same parser and scanner as
these are described in [1].
The major changes to the compiler in writing
were the rewriting of the
semantic routines of the compiler and the addition of three
one for the production of the restructured program listing,
and one for the processing of comments.
are written with local data bases, are largely
independent of the other parts of the program, and consist
of a large number of small, related routines.
By structuring the program in this way, functional
independence is obtained.
Clusters are organized separately
from the rest of the program, and accessed through a high-level and abstract
The concrete implementation of a cluster is not fixed by these
external specifications, and could be changed without the need to
part of the program provided that the routines then implemented
a suitable interpretation of the same abstraction.
This organization provides a powerful and convenient decomposition
of the profiling process.
The print cluster routines are kept in the file
Their basic function is to provide
an interface to a high-level
printing automaton, with primitives such as
Information about the macro- and micro-structure of the output is passed to
the routines implicitly by calling the appropriate entry points.
Thus, after a statement is processed, the routines are informed that an
``item'' is finished so that an intelligent decision can be made about
where to place the statement.
Similarly, when processing a list of items such as a constant type
declaration, the print cluster is given information as to where
the ``left bracket,'' i.e. `(' occurs, where each ``separator,'' i.e. `,'
occurs, and, when the final `)' occurs, this is noted as a ``right bracket.''
With this information, an implementation of the printing cluster can be
provided which sensibly divides long structured constructs even though it has
no knowledge of the high-level language structure of its input.
The profile cluster, which is kept in the file
has a number of related functions.
Initially, it deals with the problem of extracting the count information
from the profile data file.
If the execution of the interpreter terminated abnormally, then the data must
There is an image of the profile data file in the
need only determine the offset of this image in the file.
After extracting the data from the file, the profile cluster provides
operations to return successive counters from the count buffer.
builds the data structure for storing the information used to print
the optional table summarizing
Other functions provided include
saving and restoring counts before
and after structured statements,
determining when embedded
statements will have caused extra counts to be generated,
generating pseudo-counters for the
and controlling when the counts are to be printed in the listing
by keeping track of whether each count has been printed.
All manipulation of counts and counters is handled by these routines,
and focuses on a single counter structure called
which contains the current count.
In section 2.1 the profile data format and
the process of getting the data from the profile
Section 2.2 gives the data and control structures of the profiling
and printing clusters, and section 2.3 describes the tree walk
at the function level, and at illustrative parts of the statement
The implementation description concludes in section 2.4 with
a note on the handling of multi-file programs.
The following sections deal with the recovery of the profile data.
The simplest case, that of normal termination, is dealt with in section 2.1.1.
The remaining sections deal with the handling of
These are likely to be of interest to
Format of the profile data file
is normally written by the Pascal system at the end of profiling
The record structure of the header at the beginning of the file is as
\*bint\fP magic; /* 0426 */
\*bint\fP magic2; /* 0 */
\*blong\fP proftime; /* Time profiled */
\*bint\fP cnt; /* # statement cntrs */
\*bint\fP pfcnt; /* # procedures+functions + 1 */
Each counter is a long integer so the rest of the file is essentially
\*blong\fP counts[header\*b.\fPcnt];
first insures that the first word is 0426
If this is true, and the size of the remainder of the file is the size of
array as implied by the number
If not, then the specified profile data file has a bad format, and
extract the profile information from the
This is greatly simplified by the fact that there is, in the core image,
file which would have been written at normal termination.
In order to extract the profile data, it is only necessary
The first 1024 bytes of the core image file is a copy of
the system's per-user data for the process, including the registers
as they were at the time of the fault.
The remainder of the file represents the actual contents of the user's
core area when the core image was written.
If the text segment of the process was write-protected and shared,
it will not be present; otherwise the entire address space will have
for the text image of a program to be shared by all of the persons
The instructions will be write protected, and each process which
text will have only a data area, sharing one
Thus, when such a process is swapped out, only its data area need
The text space can always be abandoned and read in from external
storage when needed, as it cannot have changed.
When a core image is dumped,
the text space is not dumped if the process was running as shared text.
This is the situation with the installed version of
The disadvantage of shared text is that breakpoint debugging
is impossible in this case.
It is desirable, therefore, to have
to extract data correctly in either case.
The important fact here, which allows a number of simplifications
to the extraction method, is that
the non-stack data space of the process
is dumped immediately after the system area.
If the text space was not ``shared,'' then the first word dumped will
have been location 0 in the process address space, otherwise it will
have been the first data word, as the text of the process appears
first in the process space.
The structure needed to navigate in the
information structure\u\s-2\*(dg\s0\d, which has the following format:
hence the name of this structure
pointer here points to the image of
in core, and is a memory address.
gives the size of this image,
and is not currently used by
as the size is determined from information in the image itself.
gathering profile data in the execution which abnormally terminated.
To locate this structure, the runtime start up routine for the interpreter
was modified from the standard C start up to be as given in the following
This runtime start up is structured so that it is possible to determine,
from the first three words after the system area, whether
the process was executed as shared text, and the offset of the
If the second word here is a 0, then this can only be a non-pure
core image; if it is a 1 then this can only be a pure core image.
If it is neither then this is not a
If the core image is pure, the first word dumped of the process
was not at location 0 in the process data space.
In this case, however, the runtime start up is set up so the
first word contains its address in memory.
Thus it is possible to can convert the third core image word, which is the index
into memory, into an index into the core image by subtracting
was not gathering profile data and an appropriate diagnostic will
pointer is offset by subtracting the first word
after the system area in the
image if the process was pure,
implied location and a routine common to the
profile data gathering routines
The only notable difference is that after calling
checks that all the data on the file is
This is not done when reading a
If any of this seeking or reading terminates abnormally
The following data items are kept internally after being read from
They are available only by using the routines in the cluster in the file
gives the total number of counters, the integer
the total number of procedures and functions.
is (effectively) a dynamic array of long integers
representing the profile counts.
In addition, the external variable
representation of the time the profile was made.
Profile cluster data structures
There are two major profile cluster structures.
The first structure is the primitive unit for storing a piece
of count information and is given by:
is the actual count data.
gives a unique identifying tag to this structure,
is the number of gotos which had been encountered when this counter
is actually a Boolean value indicating
whether the counter is considered to have been printed for
the purposes of the profile.
may actually be an index into the array of
or it may be a negative number indicating
that it is a counter which was generated by calculations, e.g. for
Other uses of this structure will be described below.
The other major structure which records information
for the summary table. Its format is:
gives the invocation count for each routine,
is the approximate source program line number for the routine,
points to the character string name of the routine, and
gives the nesting level of the routine so it is possible to print
the table with nesting indicating structure.
is actually a dynamic array holding these counters.
The profile cluster primitives
The following are the primitive operations of the profile cluster
They deal in particular with one special counter structure
which holds the current count information as processing progresses.
.HP "\*blong\fP nowcnt()"
Returns a \*blong\fP integer which is the current count.
Returns an integer uniquely identifying the current counter.
.IP "\*blong\fP cntof(pxc)"
.HP "\*bstruct\fP pxcnt *pxc;"
Returns the \*blong\fP integer
associated with the structure addressed by
Makes the current counter have count
A new, unique counter is generated for this purpose.
This is used, e.g., to assign counts to
.HP "\*bstruct\fP pxcnt *pxc;"
Saves the information associated with the current count
.HP "\*bstruct\fP pxcnt *pxc;"
from the given structure.
also returns non-zero exactly when there were embedded gotos.
Takes the next counter from the
data and places it and associated information into
The fact that there are less counters in the file than
required by the supplied program is diagnosed as a
``Counter mismatch'' here.
Records the current count as being that of a
procedures and functions are also counted
here so they can be checked for consistency at the end of processing.
Profile-printing cluster interface
The following routines, which are part of the
cluster, interface to the printing cluster, and are used
to control the annotation of the program listing with
Causes the current counter to become logically ``unprinted''
so that it will be printed again.
Used, e.g., after restoring a count saved before a loop
to force it to be printed again.
Turns the printing of the bar `|' in the profile off.
Returns an integer indicating the type of annotation of the
current line which is desired.
A return value of 0 indicates that only the bar `|' is to
be printed, a value of 1 that the current count and the
bar `|' are to be printed, and a value of -1 indicates that
only white space is to be printed.
A flag set by the routines
If the bar `|' to be printed is printed, it is noted that the
current counter was printed so the count will not be printed again.
contains the cluster which performs the nitty-gritty business
of preparing the output to be printed.
It was the author's intention, when he wrote the program, to
pass sufficient information to this cluster to allow it to do
the job of breaking up long statements and of placing multiple
This has not been implemented yet.
The description of how the routines of this cluster
work together to produce the profile is deferred to a later, higher level
This cluster currently has a very minimal set of data structures.
These structures would expand greatly if the statement folding and
multiple statement placement were implemented.
the input is interpreted only in a very simpleminded way.
For this purpose it is only noted whether anything is being printed
at all, indicated by the flag
which if non-zero indicates that no printing is to occur, and some information
about the way in which the listing is to be indented.
This is contained in an array giving the indenting in spaces for
each of three levels, i.e.:
These levels have rough interpretations as follows.
The white space generated at the very left by the indenting
declarations is assigned to
the white space generated in declaration parts by structured declarations
such as records to DECL, and the white space generated by indenting
of structured statements to STAT.
The white space is dispersed on the line, separating the left margin,
labels, the profile information, and the program text graphically
line# PRFN label: STAT 999.---| DECL text
Thus by indenting in the DECL part deeper text nesting can be shown
without the bar wandering to the right, and when indenting in the
STAT part the bar is moved over.
Similarly, the option to indent nested procedures and functions
is trivially handled by indenting in PRFN.
Printing cluster primitives
There are two kinds of routines in the printing cluster.
One kind deals with printing the various kinds of tokens in
Pascal programs, e.g. keywords, strings, etc.
The other set of routines deals with the specifics of printing
the profile, i.e. turning printing on and off, indenting, and
the nasty details like the placement of labels.
Prints the character string representing the keyword.
Underlining and overstriking of keywords is also handled.
This routine facilitate the suppression of blank lines at the beginning
setting a flag the first time it prints a keyword.
Since any solid output always begins with a keyword,
refuses to print a newline until a keyword is printed.
is null because of a syntax error.
Prints strings, dealing with doubling of the string metacharacter.
are used to indicate the recursive structure of the input
at the microscopic level.
Thus, when printing out the argument list to a
the opening `(' would be printed with
This would, conceivably, allow this cluster to break the output sensibly
to conform with the nature of the output medium without having
to deal with the passed-through data at a more difficult macroscopic
These routines are all used to put separation into the output stream.
In the initial design, the difference between the routines
would always force a new-line, while
separated major units such as statements, but didn't require the
following statement to start on a new line, leaving the possibility
that it be placed on the same line.
In the current implementation, however, both
force the output to be on a new line.
Note that forcing the output to a new line does not force the
leading white space to be printed!
The utility routines which don't deal directly with
the printing of the actual program text follow.
Is called at the beginning of each
body and examines the global environment and option flags
to decide whether that routine should be printed in the profile.
If profiling is notoccuring, a summary table is desired
then this actually turns the printing off!
If neither profiling or a summary table is being producd,
then this call has no effect.
Turns the printing of the profile off.
to print the line number.
If producing a profile (rather than just a pretty-print)
pplev[PRFN] + pplev[STAT]
spaces, and then, depending on the result of a call to
print either a count, some dashes and a bar, just a bar,
Spaces over an amount determined by the indenting level using
Actually advance the indent by
it is safe to optimize the output by producing tabs,
otherwise spaces must be used.
Prints the line number if required.
Indents for a label print,
These routines each take one of PRFN, STAT or DECL and increase
or decrease the indentation at that level respectively.
It should be obvious from the discussion above, that little
difference can be discerned at the top level between producing
a profile and prettyprinting.
When prettyprinting, a large
number of routine calls return without doing any real work.
The production of the profile is discussed at each of four levels.
The first level is the main routine and option processing.
This is discussed only to give an outline of the work done here.
The second level is the level of procedures and functions and
involves such considerations as the
command line option with list of
names, forward declarations, and the recording, saving and
restoring of count information.
The third level is that of individual statements, and the final
level is that of expressions. These levels are illustrated
with actual code to make the discussion more concrete.
Main routine and option processing
The main routine sets up the default options such as setting
the indenting to 4 spaces and turning on nested
It then examines the arguments and,
importantly, sets the variable
if producing a table of procedure and function counts.
names is given it is saved as referenced by the variables
for examination by the routine
which is called by routines at
After processing all the options, the main routine makes a call
cluster to get the profile data if appropriate.
It sets up the input and does some special processing for processing
files as described further in section 2.4 below.
It finally calls the parser which completes the processing of the profile.
Procedure and function level processing
level processing routines are contained in the file
The routines here and their functions are:
Called with a tree node representing the initial declaration
of a function or procedure, e.g.:
\*bfunction\fP sine(a: angle): \*breal\fP;
this routine first determines if the routine is in the list
of procedures and functions given on the command line.
option value is saved on a stack,
It then gets the counter associated with the procedure header
and calls a routine in the print cluster to determine whether this
routine should be printed or not.
It then saves the count information for this routine at its level
This counter will be restored later when the body of the routine
The printing of the header is also processed here, but this is
similar to other processing to be described later.
This printed header is indented if nested definitions are being indented,
to be unindented after completing the printing of the header.
This routine prints the keyword
indented an appropriate amount.
This routine, called when the actual, resolving declaration of
is encountered, indents if the indent nested procedures option
is set, and increments the structured statement level, returning
This routine sets up for all of the actual work in printing the body
of procedures and functions.
It restores the count saved by
the count to force it to come out again if there
were any nested procedures or functions, (if the last block number in the
is not the current block number)
and then prints the body of the procedure or function.
and if there were nested sections prints
the name of this routine in a comment.
It then goes in a level in DECL (without shifting the bar over!)
and prints the statement list given by the parameter
This is an appropriate place to note the following important fact:
When a routine is called to put out an item at the statement level,
is usually at the end of the previous line, and if the routine
wants to print on a clean line, then it calls
If it is willing to print on the same line then it can call
It also turns out that this structure is critical for the processing
of comments which is described in section 3.
the new line character allows the comment processing to function
are called and the keyword
is printed followed by the routine name in a comment and a final
Finally unwind from any indenting that may have been done due
to the indent nested sections option occurs, and the
option stack is popped if this routine was in the command line
The statement level processing is done by the routines in the file
and for case statements by the code in the file
As noted above, the cursor for each statement is generally left
on the previous line so that a statement will ask for the cursor
to be advanced to the next line if so desired.
This is also necessary to make the placement of
The basic loop for processing a group of statements is as follows:
\*bregister\fP \*bint\fP *sl;
A pointer to a tree structure is received, treated as an array
The first word of each such node is a magic number giving the
kind of node, the second word points to a statement and the third
word links to the next such node, or NIL if this is the last node
in the statement list. This is more fully described in [1],
the nodes here being of type T_LISTPP.
To illustrate the processing for statements in general,
a subset of the code from the
statements, assignment statements and
This is illustrative of the work here in general.
receives as argument a pointer to a tree node.
For the purposes of this discussion, assume that this node is either of type
The node type T_IFEL was added to the parser because
of the problematic case of empty
When these empty clauses are present, it is impossible
to present the data for both
parts in the one T_IF structure.
part looks the same as an
This is a problem because
does not realize that the discarding of such empty
parts can affect the matching of outer
parts and alter the meaning of the program!
is a NIL pointer, \fInull\fR is printed,
a call on a built-in procedure that does nothing.
is done here indicates that it does not matter if this is on the same line
If the argument pointer is not NIL a switch is done based
on which type of statement is involved.
For assignments, as for the \fInull\fR above,
the statement can appear on the same line with something else.
To print an assignment first an
must be printed, separated by a `:='.
This is as simple as knowing which fields to pass to
here takes two arguments.
The second argument is a flag indicating whether the
expression is to be surrounded by parentheses if
Since no ambiguity can possibly result, no parenthesis are required here.
statement appear on a separate line by calling
\*bif\fP <expression> \*bthen\fP_
where the `_' will be used to represent the invisible output cursor.
The expression here also need not be parenthesized.
then saves the count before the statement by calling
and gets the count for the
part of the statement by calling
block, it can be started on this line.
Thus, in this case, the routine
It is also passed STAT, indicating that the indent it will do
is to be reflected in the position of the bars on the left.
statements among others, the bars do not move over
and does the indent discussed above, but does not put out a newline.
That is up to the routine
is not put out yet because the counter for the
part belongs on the line with
part and that count has not been set up yet.
block then the processing here is much simpler;
it is only necessary to indent a level in the STAT part as a block,
and then unindent the level. Thus a typical
position after this part is completed for a
part which is a block would be:
\*bif\fP <expression> \*bthen\fP \*bbegin\fP
with the cursor convention as before.
statement does not have an
part the rest of the processing is simple.
The count saved before the statement is restored, doing a
if there were one or more
statements in the body of the
statement to get the count after the statement.
is called to put the keyword
indented on a new line with the restored count.
This finishes the processing in this case.
part then the count for this part must first be calculated.
This is done by taking the
the saved structure from before the
statement and subtracting the current count which is that of the
This becomes the new counter generated for the
part is then finished either by printing a
as above, followed by a space,
or by forcing a new line in the output and calling
is printed in the output and followed with a space.
is called so that the count for an
part prints not only with the
but also on the statement in the
This significantly improves the readability of bushy if-then-elses.
The special case of an empty statement in the
part is caught and a null statement is put out in this case.
Otherwise a check is made to see if the
part is a block, and if so, handled in a manner identical to the processing
statements are then caught, and are recursive call is made without
This accomplishes the goal of not ``wandering across the page''
in if-then-else statements.
Noting that normal statements are treated as before,
part has been successfully completed except for some cleanup.
This cleanup involves restoration of the count and printing of the
statement count must be unprinted whenever an
This is because of the way
parts are printed, lined up with the
parts and obstructing their counts.
The final part of the profiling process to be discussed
is the printing of expressions. This is quite simple,
actually, with the only interesting code being that which
determines what parenthesization to do. This happens as follows.
Whenever a binary operator is encountered each of its operands
The following cases are from the
and indicates the code for processing binary operators.
rvalue(al, prec(al) < prec(r) || opt('f'));
\*bif\fP (alph(opname[0]))
rvalue(al, prec(al) <= prec(r) || opt('f'));
returns an integer representing the precedence of the
\*bregister\fP \*bint\fP *r;
Thus, with a binary operator,
parentheses are needed around the left operand if it is non-atomic
and its operator has lower
than the current operator.
Parentheses are needed around the right operand if it is non-atomic
and its operator has fewer or the same
This equality condition reflects Pascal associativity.
has the capability of handling
may be split into many pieces, they may be so split and then
In addition a capability for pretty printing of one piece of
a program has been included in
is pretty printing and the file being pretty printed
into the source stream before the first line of the file
In this way, if the contents of the
corresponds to a global declaration part and/or
a group of procedures and functions, the pretty print
can proceed without modifications to the source text.
This is the only case in which the pretty printer will
take anything other than a complete Pascal program.
suppresses printing back out the inserted and appended lines
does not normally process
directives but rather prints them back out as includes.
An option to eliminate the includes is also available.