Chapter 5

Overview of Navigator

The first part of this dissertation has presented debugging problems arising from a wide variety of optimizations and has suggested several solution techniques.  The second part restricts its view to two particular optimizations and describes a practical application of the solution techniques to a real programming environment.
Navigator is a prototype implementation of an interactive source-level debugger for control-flow optimized programs.  Navigator was developed in the Cedar programming environment at the Xerox Palo Alto Research Center; it consists of modified versions of the Cedar compiler and the Cedar debugger.  Navigator's objective is to validate the ideas and solution techniques presented in the first part of this dissertation.
This chapter presents the highlights of the Navigator system: its goals and results, the environment in which it was implemented, a brief description of the operation of the Navigator compiler and debugger for simple cases (including examples), and some discussion of the tradeoffs inherent in its methods.  Readers who are more interested in the basic ideas than in the complications and the performance analysis can read this chapter and skip the remaining Navigator chapters.
5.1 The problem
This section defines the problem that Navigator was intended to solve; it examines Navigator's goals and motivations in detail.  The high-level goal was to select a few optimizations and to design and implement an effective and efficient interactive source-level debugger for them.  If possible, the debugger should provide expected behavior for the selected optimizations, but in no case would less than truthful behavior be permitted.  I also had specific desires about the solution techniques: I wanted to concentrate on adding static and dynamic information and on adding debugger algorithms to use the new information.  These goals drove the selection of the remaining parts of the problem to be attacked (most importantly, the choice of particular optimizations and debugging functions).  Figure 5-1 summarizes the important parameters of the problem that Navigator addresses.
I chose to modify an existing optimizing compiler and its debugger rather than designing and implementing a new optimizing compiler and a new associated interactive debugger with expected behavior.  There were two reasons for this choice.  First, it kept the implementation work to a manageable size by concentrating the effort on those compiler and debugger portions that affect debugging optimized programs.  (Note that a manageable-sized real implementation has more depth, while a manageable-sized design or toy implementation has more breadth.)  Second, the practical value of an idea is more easily seen from a real implementation: the implementation details expose design problems that might otherwise be missed.  This choice also sheds light on the ease of retrofitting other existing optimizing compilers to provide improved debugger behavior.
The following discussion considers the goals presented in Figure 5-1 more closely.
5.1.1 The two selected optimizations
Two optimizations were chosen as the focus for the Navigator work: inline procedure expansion (replacing a procedure call by a copy of its component statements) and cross-jumping (merging identical tails of code paths that join; so named because it inserts branches that jump across from one code path to another).
Recall from Chapter 3 that inline procedure expansion and cross-jumping are control-flow optimizations.  They preserve the order of execution of instructions that are meaningful to the programmer, but they create complicated mappings between the source text and the object code.  Inline procedure expansion is a copying optimization; it creates a one-to-many source-to-object mapping.  It saves execution time only.  Cross-jumping is a merging optimization; it creates a many-to-one source-to-object mapping.  It saves execution space only.  The debugging difficulties that arise from these optimizations were described in Section 3.2.2.2.  Many current compilers perform simple optimizations like these, while relatively few perform the more complicated and more expensive global optimizations.

							              
1. The two optimizations:
Inline procedure expansion
Cross-jumping

2. The primary debugging functions:
Setting breakpoints at program statements
Determining the current execution location
Reporting the procedure traceback
  The secondary debugging functions (considered less thoroughly):
Setting breakpoints at procedure entry and exit
Calling procedures from the debugger
Single-stepping
Displaying the values of variables

3. The desired user-visible behavior:
Expected behavior, where possible without violating other constraints
Never less than truthful behavior

4. The desired solution techniques:
Collect static information in the compiler.
Collect dynamic information in the debugger.
Use new debugger algorithms to process the additional information.

5. The desired performance and efficiency:
An optimized program that can be debugged must not be larger or slower than the unoptimized version of the same program.
If possible, the ability to debug should cost execution space and time only when debugging is active.
Optimized programs should require no recompilation to debug.
The modified compiler and debugger must still perform efficiently.
In the compiler: if possible, the same level of information that is used to perform an optimization should be collected to allow for its debugging.

Figure 5-1.  Summary of the problem addressed by Navigator.
							              

Finding an optimizing compiler and associated interactive debugger that could reasonably be modified was not trivial.  Optimizing compilers are not yet widely available; an optimizing compiler whose source files are available for modification is rarer.  The Cedar environment has both an optimizing compiler and a good interactive debugger.  However, inline procedure expansion and cross-jumping are the only substantive optimizations implemented by the Cedar compiler.  These two control-flow optimizations are simple enough that a debugger with expected behavior seemed possible, but they are difficult enough to cause real debugging problems in practice.  [See Section 5.5 for an account of an actual Cedar debugging session that was complicated by inadequate treatment of these optimizations.]  The Cedar compiler also implements a few very simple object code optimizations that have a small effect on debugging.  Navigator ignores the direct effects of these other optimizations, but it does address the interactions between them and the solutions for inline procedure expansion and cross-jumping [see Section 6.4.2].
5.1.2 The debugging functions
Navigator concentrates on providing three location- and history-oriented debugging functions: setting breakpoints at program statements, determining the current execution location, and reporting the procedure traceback.
These primary debugging functions were selected for three reasons.  First, these functions are more heavily affected by inline procedure expansion and cross-jumping than the secondary debugging functions discussed below.  Control-flow optimizations primarily affect the location and history aspects of a program's execution, rather than its data aspects [see Section 2.1.1].  That is, they affect the ability to determine current and past execution locations, but do not significantly affect the ability to display current values of variables.  Second, these functions are among the basic debugging functions mentioned in Section 2.2.1.1: almost every debugger implements them, and they are frequently the basis for the implementation of more advanced debugging functions.  Third, Hennessy had already examined some of the problems of displaying the values of variables for optimized programs [Hennessy82]; the remaining basic debugging functions deserved attention also.  Furthermore, displaying the values of variables is dependent upon knowing the current source location.
Other secondary debugging functions were considered less thoroughly, including: displaying the values of variables, setting breakpoints at procedure entry and exit, calling procedures from the debugger, and single-stepping.  These are the remaining common debugging functions that are affected by inline procedure expansion and cross-jumping.  Although displaying the values of variables is one of the basic debugging functions, it is not seriously impaired by inline procedure expansion and cross-jumping; therefore, it received less attention.
5.1.3 The desired debugger behavior
My goal was to provide expected debugger behavior for the selected optimizations.  Wherever I discovered that expected behavior was impossible or inefficient, I planned to fall back to providing truthful behavior.  Less than truthful behavior would not be permitted.
A debugger with expected behavior is more easily used than a debugger with truthful behavior, because the debugger (and the compiler) shoulder the responsibility for translating user queries and responses between the original source program and its executing optimized version.  A minimum goal of truthful behavior is necessary because a debugger that has neither expected nor truthful behavior will give confusing responses to queries about an optimized program's execution.  For example, if inline procedure expansion has been applied, the debugger might not place a copy of a breakpoint in each copy of the code.  If cross-jumping has been applied, the debugger might report an incorrect source location when a breakpoint or error is encountered.  The unmodified Cedar debugger exhibits these problems.  [See Section 2.4.1 for further discussion of expected and truthful behavior.]
5.1.4 The desired solution techniques
Of the six solution techniques applicable to providing expected debugger behavior, I chose to focus upon three:
9	adding static information (collected by the compiler during the optimization phase),
9	adding dynamic information (collected by the debugger during program execution), and
9	adding debugger algorithms to process the new information.
These three techniques are the workhorse techniques.  Three auxiliary techniques, used if the first three cannot provide the desired behavior, are: restricting optimizations, restricting debugging functions, and recompiling a (small) portion of the program to temporarily disable troublesome optimizations.  Restricting optimizations and/or debugging functions were not suitable because the selected optimizations and debugging functions were already limited.  Recompilation was rejected primarily because it had already been partially explored: Feiler's compilation-based interactive programming environment LOIPE allows optimization of any program fragment that does not include a debugging statement [Feiler82].  Recompilation is a good method, but such systems usually cannot continue a suspended execution after the user inserts new debugging statements near the suspension point.  Navigator investigates whether effective and efficient debugging can be provided without recompilation of any kind.
5.1.5 Performance and efficiency constraints
To be useful, the completed debugging system must also be reasonably efficient.  First, a debuggable optimized program must not be larger or slower than the unoptimized version of the same program.  If possible, the ability to debug should cost execution space and time only when debugging is active.  Second, optimized programs should require no recompilation to debug.  Third, the modified compiler and debugger must still perform efficiently.
If optimized Cedar programs cannot be debugged at any time, without recompilation, no real benefit would be gained: programmers could recompile with optimizations disabled as easily as recompiling with debugging enabled.  The key to achieving this goal is efficiency, both for the executing user program and for the compiler and debugger.  Furthermore, if effective debuggability is inexpensive enough, inline procedure expansion and cross-jumping can be applied to every program during every compilation, so that the space and speed benefits of optimization can be realized over the entire life of the program.  The compile-time performance and efficiency goals can also be expressed in terms of "appropriate technology": the expense of fixing up a relatively simple optimization, especially in a compiler that does not implement more complex optimizations, should not vastly exceed the expense of doing the optimization in the first place.  In particular, the cross-jumping optimization is implemented in the Cedar compiler as a local optimization: it does not require global flow analysis.  However, it does require knowledge of local control flow (that is, which instructions can execute before or after a given instruction).  If possible, the same level of information that is used to perform an optimization should be collected to allow for its debugging, rather than requiring a more expensive information-gathering mechanism.


Many interesting problems that were identified in earlier chapters of this dissertation do not apply to Navigator.  The rest of the dissertation concentrates on debugging with expected behavior for inline procedure expansion and cross-jumping, rather than such topics as:
9	Truthful debugging: how to intelligibly present a changed version of the source program to programmers.
9	Truthful debugging for computation-reordering optimizations: how to implement syntactic and semantic mappings between source and object locations, and how to clarify their use to programmers.
9	Expected debugging for computation-reordering optimizations: how to display (i.e., reconstruct) the expected values of variables.
5.2 Overview of the results
Navigator solution techniques.  To handle inline procedure expansion, the Navigator compiler collects additional static information about "deleted" procedure calls in the statement maps and in a special-purpose inline table.  New debugger algorithms process the additional static information.  To handle cross-jumping, the Navigator compiler collects additional static information in the statement maps and in a special-purpose path determiner table.  In response to debugging requests, the Navigator debugger collects dynamic control-flow information.  New debugger algorithms process the additional static and dynamic information.  A few relatively minor complications necessitate restricting the cross-jumping optimization under some circumstances (the compiler does this automatically when necessary) and adding a new debugging command for cross-jumped regions under others.
Navigator debugger behavior for inline procedure expansion.  Navigator achieves expected behavior for all of the primary debugging functions: setting breakpoints at program statements, determining the current execution location, and reporting the procedure traceback.
Navigator debugger behavior for cross-jumping.  Navigator achieves expected behavior for breakpoints (preplanned debugging activity).  For procedure tracebacks and for determining the current execution location at a user interrupt or a program exception (unplanned debugging activity), Navigator can guarantee only truthful behavior because the dynamic information collection must be triggered in advance.  In these cases, a forewarned user can use the new SUSPECT debugging command to convert truthful behavior to expected behavior over a chosen program region [see Section 5.8].  For some unusual source programs (programs with ambiguous control flow and cross-jumped regions with embedded exception handlers [see Section 6.3.3]), Navigator can achieve only truthful behavior.  In these cases, the compiler can restrict optimizations slightly to allow expected behavior.
Navigator performance and efficiency.  The Navigator compiler generates exactly the same object code as the unmodified Cedar compiler (except under the rare circumstances when the compiler restricts the cross-jumping optimization); only the debugging tables are enlarged.  An optimized program compiled by the Navigator compiler will execute precisely as fast as an optimized program compiled by the unmodified Cedar compiler, as long as no debugging requests have been made.  The larger debugging tables can be kept in secondary storage until debugging activity requires them.  Optimized programs can be debugged at any time, without recompilation.  The runtime cost of debugging activity is proportional to the number and merging complexity of merged regions that have breakpoints set inside them.  [Chapter 7 discusses the runtime costs in more detail.]
5.3 What were the difficult areas?
Although the effects of inline procedure expansion on debugging had not been considered before, providing expected debugging for inline procedure expansion was straightforward.  In contrast, despite the purported algorithm for cross-jumping devised by Teeple and Anderson, providing expected debugging for cross-jumping was quite difficult.  In order of increasing difficulty, these were the hard spots:  
9	applying cross-jumping to an expanded inline procedure [see Section 6.4.1]
9	handling a variety of complications, ranging from multiple processes or recursion inside a merged region to programs with ambiguous control flow [see Section 6.3.3]
9	applying other object code optimizations to a cross-jumped region [see Section 6.4.2]
9	applying cross-jumping to a previously cross-jumped region [see Section 6.3.4]
9	attempts to reduce the amount of static and dynamic information needed for cross-jumping [see Chapter 7]
5.4 Expected debugging of inline procedure expansion and cross-jumping
Before we begin the discussion of how Navigator provides expected debugging for programs that have been affected by inline procedure expansion and cross-jumping, let's take a closer look at these optimizations and decide what the expected behavior should be for the selected primary debugging functions.  We can then reason backward from the desired response to the information that must be available for any debugger to provide that response.
5.4.1 A review of inline procedure expansion and cross-jumping
As described in Chapter 3, control-flow optimizations rearrange the object code for a program either by copying code sequences, which makes the program faster, or by merging identical code sequences, which makes the program smaller.  These optimizations create problems for interactive high-level debugging, even though they do not alter the order of execution of instructions that are meaningful to the programmer.
Inline procedure expansion is a copying optimization.  It replaces a call to a procedure by an instance of the actual code of the procedure in order to save the execution time associated with procedure linkage (saving and restoring registers, stack manipulations, etc.).  Inline procedure expansion may also provide opportunities for further optimizations, thereby tailoring the called procedure to a specific callsite.  Inline procedure expansion causes each source statement in the inline procedure's declaration to correspond to many separate sections of object code, as shown below.
fig51a.press  leftMargin: 1.9375 in,  topMargin: 3.625 in,  width: 2.9375 in,  height: 1.45 in
Cross-jumping is a merging optimization that examines code sequences that join, such as the two branches of an IF-THEN-ELSE statement or the multiple branches of a SELECT statement.  A code sequence is one or more statically adjacent instructions in a linear codestream.  If the tail portions of any two of the sequences are identical, cross-jumping moves the join point for those two sequences from its original location backward to the earliest identical point and deletes one copy of the identical code.  In the optimized form, one sequence merely jumps to the other path to perform the identical tail of the sequence.  Cross-jumping is often performed as an object code

optimization, but it can also be performed on intermediate representations of the program (such as flowgraphs or quads [Aho+77]).  Cross-jumping causes two or more source statements to correspond to a single section of object code, as shown below.
fig51b.press  leftMargin: 3.0625 in,  topMargin: 3.5 in,  width: 2.9375 in,  height: 1.3875 in
We now discuss the implications of inline procedure expansion and cross-jumping for the primary debugging functions: setting a breakpoint, determining the execution location, and providing a procedure traceback.
5.4.2 Setting a breakpoint
Setting a breakpoint on a statement relies upon the mapping from source statements to object locations.  Each source statement has one breakpoint location: the first object code instruction for that statement.  [We restrict our attention to debuggers with statement granularity and before-statement breakpoints].
Inline procedure expansion.  When a user requests a breakpoint inside an inline procedure, the debugger should place a copy of the breakpoint at every object location that corresponds to the start of execution of a copy of the statement.  (The resulting breakpoints will mirror the behavior for a non-inline procedure.)  To permit multiple breakpoints, the debugger must have a correct one-to-many source-to-object mapping for the start of each statement.
Cross-jumping.  When a user requests a breakpoint on a statement that has been merged by cross-jumping, the debugger should place the breakpoint at the object location that corresponds to the start of execution of that statement (even though that object location executes on behalf of more than one statement).  When the breakpoint actually occurs, the debugger should determine whether to honor it.  Consequently, the debugger must have a correct many-to-one source-to-object mapping for the start of each statement.  Furthermore, the debugger should be able to place multiple breakpoints (possibly with different activation conditions) at the same object location.

5.4.3 Determining the execution location
Determining the execution location is the basis for reporting the execution location to the user (either the current execution location or as a part of a procedure traceback) and for fielding a breakpoint (that is, determining whether an object location is executing on behalf of a statement at which the user has requested a breakpoint).  This function relies upon the mapping from object locations to source statements; every object location (rather than just statement boundaries) must be mappable because program exceptions, user interrupts, or procedure calls can occur within a statement.
Inline procedure expansion.  The debugger should map an object location to the (single) statement number in the innermost expanded inline procedure.  The procedure name for that innermost procedure should also be available.  To accomplish this, the debugger must have a correct many-to-one object-to-source mapping for every object location, as well as a many-to-one object-to-procedure name mapping.
Cross-jumping.  To achieve truthful behavior, the debugger should map an object location to the list of all source statements on whose behalf the object location might be executing.  Therefore, the debugger needs a correct one-to-many object-to-source mapping for every object location.  To achieve expected behavior, the debugger should map an object location to the exact statement on whose behalf it is executing this time.  To do this, the debugger needs a correct one-to-many object-to-source mapping for every object location, plus more static and dynamic information.
If the debugger reports that the current execution location is one of a list of statement alternatives (that is, truthful behavior), the programmer can often use other debugging functions to discover which statement is really executing.  Frequently there are program variables that indicate which execution path has been taken; the programmer can examine these variables to figure it out.  However, even when such variables exist, this process can be tedious.  For breakpoints, if the uninteresting cases occur much more frequently during execution than the desired case does, the programmer must laboriously check each time to see whether the desired case has finally been reached.  Conditional breakpoints could be used here, if the debugger has them.  If all else fails, the programmer could recompile the program with cross-jumping disabled.
The preceding behavior is adequate, in that 1) it does not mislead the user and 2) it gives all of the alternatives.  But it would be nicer if the debugger provided expected behavior: that is, the (single) correct statement number.  
To understand one way to achieve expected behavior for cross-jumping, consider the following fragment of a program schema.  Different letters indicate different instructions.  The subscripted numbers refer to the statement numbers in the corresponding source program. 
fig51c.press  leftMargin: 4.375 in,  topMargin: 1.75 in,  width: 0.875 in,  height: 1.6375 in
There are two possible execution paths through this fragment:
     a1 b2 x3 y4 d8  and  a1 c5 x6 y7 d8.
     
Since the right and left flowgraph paths both end in the instruction sequence x y, cross-jumping can be applied.  After cross-jumping, the flowgraph fragment becomes:
fig51d.press  leftMargin: 4.375 in,  topMargin: 1.75 in,  width: 0.875 in,  height: 1.6375 in
There are also two possible execution paths through the cross-jumped fragment:
     a1 b2 x3,6 y4,7 d8  and  a1 c5 x3,6 y4,7 d8.
     
The key insight is that we can distinguish between instruction x executing on behalf of source statement 3 and instruction x executing on behalf of source statement 6, based on which of instructions  b or c have executed more recently.  If instruction b has executed more recently, then instruction x is executing on behalf of source statement 3.  If instruction c has executed more recently, then instruction x is executing on behalf of source statement 6.  We can also distinguish between instruction y executing on behalf of source statement 4 and instruction y executing on behalf of source statement 7, based on the execution of the same two instructions  b and c.  [Note: multiple processes and recursion can complicate this process.  Therefore, we really need to know which of b or c have executed more recently in the current procedure invocation.  This method also requires some additional compile-time effort in the rare case that both entire paths are identical.  Section 6.3.3. discusses these and other problems.]
To prepare for actually making the distinction during execution, the compiler must identify path determining instructions such as b and c.  It must associate each path determining instruction with its corresponding statement numbers.  Finally, the debugger must collect history information at the path determining instructions during the program's execution.
The semantics of a path determining instruction is immaterial for this process.  What is important is that it executes before any instruction in the merged region does.  The cross-jumping optimization merges two identical code sequences.  A sentry of a code sequence is any instruction outside the sequence that can execute immediately before any instruction inside the sequence.  (Note that there may be more than one sentry for a single sequence.)  The set of sentries of each sequence is a good choice of path determining instructions for the instructions inside that sequence.
5.4.4 Providing a procedure traceback
Inline procedure expansion.  When the debugger provides a procedure traceback, it should report calls that were replaced by their text expansions as if they had actually occurred.  This means reporting the statement number in the callee (the inline procedure), the procedure name of the callee, the statement number of the call (in the caller), and the procedure name of the caller.  To allow this, the debugger must have a correct many-to-one object-to-callsite statement number mapping.  The statement number in the callee and the procedure name of the callee are available by the mechanism for determining the execution location.  The procedure name of the caller is available by the normal mechanism for non-inline procedures.
Cross-jumping.  Providing a procedure traceback is not directly affected by cross-jumping.  If a merged region contains a procedure call, the debugger should handle it as described in the previous section.
5.5 The Cedar programming environment
Although the ideas behind the algorithms described in this dissertation are general, their implementation depends on the specific source language, compiler, and debugger to which they are applied.  This section gives an overall view of the Cedar programming environment and briefly describes several of its aspects that affect the design and implementation of the Navigator system.  More details about the Cedar compiler appear in Chapter 6.
5.5.1 Cedar overview
The Cedar programming environment is a modern programming environment developed at the Xerox Palo Alto Research Center [Teitelman83].  It was intended to help researchers produce experimental programs efficiently [Deutsch+80].  Experimental programs are medium-scale software systems that can be used to test programming ideas.
The Cedar environment is based on a single Algol-like language, Cedar, although it does have facilities for communicating with programs written in other languages.  The Cedar language was the result of modifying Mesa [Mitchell79] to provide automatic storage deallocation (garbage collection) and facilities for delaying the binding of type information, without sacrificing complete type-checking in either case.
From a user's point of view, the Cedar environment consists of a text editor, a compiler, a binder for linking separately-compiled modules, and a debugger/interpreter.  Other facilities include a variety of program analysis tools, a mail system, a reminder system, and a document processor.  Cedar is a single-user system that runs on a high-performance personal computer with a large high-resolution bitmapped display and a mouse [Thacker+81, Lampson+80, Pier83].  The display's screen area is normally divided into multiple non-overlapping windows, called viewers, so that multiple programs can be active at once in a non-preemptive fashion [Swinehart74].
Primarily because the researchers wanted to be able to debug their experimental programs easily, the Cedar compiler performs only a few selected optimizations: inline procedure expansion, cross-jumping, and some less important object code optimizations that will be detailed later.  Furthermore, the application of both inline procedure expansion and cross-jumping can be controlled by the programmer.  Inline procedure expansion is enabled for a single procedure by declaring the procedure to be INLINE in the source text.  Every call to such a procedure will be expanded, rather than the expansion decision depending on the individual callsite.  Cross-jumping can be enabled or disabled for an entire source file via a compilation switch.
Inline procedure expansion and cross-jumping are particularly important for Cedar (and Mesa) programs.  The Cedar procedure call mechanism is quite general, to permit multiple processes and coroutine control transfers.  Therefore it is a bit expensive for very short procedures.  Also, Cedar's strong typing requires explicit source-level separation of statements that refer to different variants of a variant record.  This can lead to SELECT statements that do similar things in each branch, but the programmer is not permitted to coalesce the similar portions.  [A SELECT statement is the Cedar equivalent of Pascal's case statement.]  This is in addition to the cross-jumping opportunities ordinarily offered by large SELECT statements, such as those used to implement table-driven parsing, and by statement portions, such as addressing computations.  Furthermore, inline procedure expansion and cross-jumping interact.  Cross-jumping can merge expanded statements that are not visibly identical in the source program.
A note on the etymology of the name "Navigator":  The Cedar programming environment grew out of the Mesa development environment.  The operating system for the Mesa environment, which was used in the early days of the Cedar environment, is called Pilot [Redell+80].  Its debugger is called CoPilot.  It seemed only appropriate to have a Navigator to keep the CoPilot from going astray.
5.5.2 Relevant Cedar details
The details mentioned here impact the design of the Navigator system.  They are not necessarily the most important features of the subsystem being described.
The Cedar language: programming in the small.  The Cedar language is a strongly-typed language suitable for systems implementations.  Among its more sophisticated features are support for multiple processes (with monitor-based process synchronization) and coroutine control transfers.  The Cedar exception-handling mechanism provides an inexpensive way to check for exceptional conditions (as long as they occur infrequently).  All otherwise uncaught signals will be caught by the Cedar debugger, so that the programmer can examine the error state.  The Cedar language has only a restricted form of GOTO statement: GOTO statements can only jump forward in the program, and they can only jump out of a block, never into one.
The Cedar language: programming in the large.  A Cedar program can consist of multiple text files or modules.  Each module is compiled separately.  Definitions modules serve two purposes.  The first purpose is to describe interfaces between program modules so that the compiler can check all inter-module references for type agreement.  The second purpose is to define types and compile-time constants that are to be shared by other modules.  Compiling a definitions module produces only symbol table information, which will be used in compiling other modules.  Program modules contain actual data declarations and executable statements as well as type and constant definitions.  Compiling a program module produces an object module consisting of position-independent object code, symbol tables and statement maps, and data structures that allow for inter-module references.  A program module that defines a public item (an implementation module) exports it to a definitions module.  The definitions module specifies the type characteristics of the item.  For example, the type characteristics of a procedure are the procedure name and the names and types of its parameters and return values.  Other program modules that access the item (client modules) must import it from the definitions module.  However, the link from the client module to the implementation module is not created at compile-time.  This binding process occurs later, as the program is being packaged together or loaded.  The delay assists development by multiple programmers and allows flexibility in assembling a program from various implementations of the same interface.
The Cedar compiler.  As previously mentioned, the Cedar compiler applies only a few optimizations to a program.  All of the optimizations preserve the actual ordering of computations along any execution path, although the control flow may be altered.  The compiler performs inline procedure expansion on an abstract syntax tree representation of the program.  Later, it repeatedly performs several object code optimizations (including cross-jumping) on the generated abstract object code until the optimizations can no longer be applied.  The other optimizations in this iterative process are: reversing branch conditions, removing branch chains and jumps to the following location, and collapsing adjacent instructions into a more powerful single instruction.
The Cedar debugger.  The Cedar debugger allows interactive examination and control of a running Cedar program.  It can interpret most Cedar expressions (including procedure calls, which are handled by interpreting the parameters and invoking the compiled object code for the procedure, rather than by interpreting the procedure's source text).  The debugger operates as a separate process in the same address space as other programs (the entire Cedar environment uses a single address space), and is always loaded and running.  Because process switching is inexpensive, conditional breakpoints can be very fast.  The Cedar debugger is noninvasive: the compiler does not generate special object code to assist in debugging; instead, it generates tables.  The symbol table contains name, type, and data storage location information, while the statement map contains

source and object code location information.  Because the debugger is noninvasive and operates as a separate process, it can be applied to a program at any time, without prior arrangement.
The Cedar operating system.  A process switch, such as a trap to the debugger, costs about as much as a procedure call.  There is a simple process scheduler; there are multiple priority levels and round-robin scheduling.  There is a large virtual address space with demand paging from the disk [Redell+80].
The Cedar machine architecture.  The Cedar abstract machine is a fairly simple microcoded stack machine [Johnsson+82].  There are no general-purpose registers.  Most instructions are simple, with zero or one operands.  The instruction set has been carefully tuned to allow compact representation of programs [Sweet82].  The Cedar compiler generates Cedar machine instructions directly (rather than assembly code).  There is a special trap instruction for use in implementing breakpoints; the debugger is permitted to write into instruction pages.
5.6 Difficult Cedar debugging sessions
Although the Cedar compiler explicitly restricts optimizations in order to retain the ability to debug, and although inline procedure expansion and cross-jumping are relatively simple optimizations, debugging optimized Cedar programs can be frustrating.  The following description of an actual debugging session demonstrates the extent to which Cedar programmers experienced confusion.
5.6.1 An actual debugging session
The purpose of the following Cedar procedure skeleton is to get a number from a remote experimental device over the Ethernet [Metcalfe+76], using a low-level protocol.  After initializing some data, there are a series of nested loops.  The normal exit from the loops is in the middle of the inner loop at the statement GOTO stop.  At the label stop, GetNumber calls a cleanup procedure, EndNumber.

GetNumber: PROC [data: Data] =
       BEGIN
       StartNumber [data];
       DO  -- get digit --
           9  9  9
           DO  -- get retransmissions --
               9  9  9
               DO  -- get packet contents --
                   9  9  9
                   IF done THEN  GOTO stop;
                   9  9  9
               ENDLOOP;
           ENDLOOP;
       EXITS
           stop => {EndNumber [data]};
           9  9  9
       ENDLOOP;
       END;
Executing the program containing this procedure crashed the entire Cedar system.
The researcher working on the program, an experienced system implementor, suspected that the procedure was not correctly recognizing the end of a number.  To test this suspicion, he placed a breakpoint on the call to EndNumber and restarted the program.  The breakpoint was never reached, so he used the standard binary search technique of setting breakpoints in order to zero in on the failure point.  He soon discovered that program execution would reach a breakpoint at GOTO stop, but it would not reach a breakpoint at the call to EndNumber.
This was surprising behavior: execution was reaching a branch, but not the branch destination.  The programmer began to dream up complicated theories to explain this behavior.  Since his system was using low-level protocols, he hypothesized that buffer pointers were going astray and the input was being written on top of the code segment.  He spent an entire day investigating this and other possibilities without success.
What was the problem?  The compiler had applied inline procedure expansion to the call to EndNumber.  As previously mentioned, a Cedar programmer must explicitly specify in a procedure's declaration that all calls to it should be expanded.  However, the declaration of EndNumber was several pages away from this call to it (and furthermore, the procedure  EndNumber had been written by another programmer), so the problem was not immediately apparent.  The declaration of the procedure EndNumber appears below.

EndNumber: PROC [data: Data] = INLINE
       BEGIN  -- clean up --
       9  9  9
       IF data.buffer # NIL THEN
           ReleaseBuffer [data.buffer];
       END;
A colleague finally noticed that EndNumber was an inline procedure.  Since inline procedures were known to behave oddly with respect to breakpoints, the programmer set breakpoints elsewhere.  He discovered that the program was getting much farther than he had thought before it was failing; he found the bug a few minutes later.
The facts behind this debugging session
The Cedar debugger does not permit users to place breakpoints at the entry or exit points of inline procedures, nor does it permit breakpoints on statements inside inline procedures.  These breakpoint locations are disallowed because an inline procedure can be expanded in many different places within a program, causing multiple disjoint copies of the code for procedure entry, exit, and internal statements.  However, in this example, the breakpoint was placed on a call to an inline procedure, which has a single section of corresponding object code, rather than on a statement inside an expansion of a procedure. 
So why did this situation cause a debugging problem?  Because the compiler and debugger weren't designed to handle inline procedures correctly.  Several implementation details interacted poorly, causing a breakpoint on a call to an inline procedure to be placed at the start of the code for the last statement in the inline procedure (disregarding the statement hierarchy), rather than at the start of the code for the first statement, as a user expects.  In this example, the last statement in the inline procedure EndNumber was guarded by an IF statement.  The condition happened to be false, so the breakpoint on the call to EndNumber was never reached.
5.6.2 A possible debugging session
The cross-jumping optimization can cause similar debugging confusion.  The following procedure skeleton is intended to return a string of characters representing a legal name.  Two things can go wrong inside the procedure: either the name can fail to be legal, which could happen fairly frequently, or some disaster can occur when trying to process the name, such as the symbol table being full or inaccessible.  When cross-jumping is applied to this procedure, it merges statement 21 and statement 31 (because in Cedar, a RETURN statement is implemented as a branch to the actual return instruction at the end of the procedure; so both copies of name_NIL execute directly before the return instruction).  Suppose that the programmer, wanting to be notified in the rare event that the disaster condition arises, places a breakpoint at statement 31.  In the cross-jumped version of the program, that breakpoint is reached whenever statement 21 executesthat is, much more often than anticipated.  If the disaster condition is difficult to evaluate, the programmer will waste a lot of debugging time wondering why the disaster case was triggered, when in fact it was not triggered at all.
10 GetName: PROC RETURNS[name: ROPE] =     GetName: PROC RETURNS[name: ROPE] =
     BEGIN  -- get name		BEGIN
     9  9  9			9  9  9
20   IF NOT Legal[name] THEN                 IF NOT Legal[name] THEN
21       name _ NIL		    GO TO L;
     ELSE			ELSE
        {-- set up some stuff		   {
         9  9  9		    9  9  9
30       IF disaster THEN	                   IF disaster THEN
31          {name _ NIL;	               L:     {name _ NIL;
             RETURN};		        RETURN};
         -- set up some more stuff
         9  9  9		    9  9  9
        };			   };
     END;			END;
5.7 Overview of Navigator methods for improved debugger behavior
This section briefly presents the highlights of the changes needed to provide effective and efficient debugging for inline procedure expansion and cross-jumping.  The underlying ideas are quite simple, but many details and complex interactions must be considered in order to provide truthful or expected debugging.  The following chapters will explain the complications more fully.
Figure 5-2 diagrams the components that changed in creating the Navigator system from the original Cedar compiler and debugger.  Figure 5-7, at the end of the chapter, summarizes Navigator's improvements.

fig52.press  leftMargin: 2.125 in,  topMargin: 0.9375 in,  width: 4.5 in,  height: 8.5 in
Figure 5-2.  Relationship between Navigator system and Cedar system.
5.7.1 Inline procedure expansion
The compiler performs inline procedure expansion on an abstract syntax tree representation of the program.  To handle inline procedure expansion, the Navigator compiler collects additional static information about "deleted" procedure calls in the augmented statement maps and in a special-purpose inline table.  Navigator achieves expected behavior for all of the primary debugging functions.
5.7.1.1 Additional static information
Overview
Augmented statement maps.  The statement maps generated by the Cedar compiler were monotonically increasing in both source and object locations; that is, the object location for a given statement was never less than the object location for the preceding statement, and vice versa.  The Navigator compiler enlarges the statement map to allow one-to-many source-to-object mappings (for setting breakpoints as expected) and many-to-one object-to-source mappings (for determining the execution location as expected).  These two mappings are no longer precise inverses, so the statement map is split into a source table, which holds the source-to-object mapping, and an object table, which holds the object-to-source mapping.  Whenever the Navigator compiler expands a call to an inline procedure in the abstract syntax tree, it copies each original source reference along with the nodes for each copied source statement.
New inline table.  The inline table is the inline procedure analog of the runtime procedure call chain (which is managed by the runtime environment as part of procedure calls and returns).  The Navigator compiler gives each call to an inline procedure a unique inline call identifier.  As it expands that call, the compiler labels each expanded source reference in the abstract syntax tree with that inline call identifier.  It records the identifier, the procedure name of the callee (the expanded procedure), and the statement number of the procedure call (in the caller) in the inline table.
Examples
Figure 5-3 gives an idea of Navigator's operation for inline procedure expansion without descending to the object code level.  Readers should imagine that high-level statements are translated into appropriate sequences of object code instructions.

fig53.press  leftMargin: 1.5 in,  topMargin: -0.3125 in,  width: 6 in,  height: 8.5 in
Figure 5-3.  Inline procedure expansion example.
The program.  The source fragment appears on the left of the figure.  The procedure SetX isolates the implementation of the global variable x from the rest of the program, as well as collecting statistics about its use.  For efficiency, SetX is declared to be an inline procedure.  The procedure AdjustX contains two calls to SetX, at statements 52 and 55.  
The effects of inline procedure expansion.  A high-level view of the effects of the inline procedure expansion optimization is shown in the middle of the figure.  The calls to SetX are replaced.  Each calling statement evaluates the actual parameter; the expanded statements store the actual parameter into the formal parameter and perform the procedure's computations.  The italicized statement fragments (in brackets) show the separation between computations charged to the caller and those charged to the callee.  This separation allows program exceptions during the execution of the fragments to be reported at the correct locations.
Navigator debugging tables.  The debugging tables generated by the Navigator compiler appear on the right of the figure.  The object table is aligned with the optimized version of the program for ease of comprehension.  Inline table identifiers appear in the object table as superscripts on the expanded source references.  The alignment of the source table has no special significance.
5.7.1.2 New debugger algorithms
Overview
Set breakpoint.  To set a breakpoint at a source statement s inside an inline procedure, the debugger searches for s in the source table and sets a breakpoint at each of the corresponding (multiple) object locations.
Determine execution location.  To determine the source location from an object location x, the debugger searches for x in the object table and returns the corresponding statement number s.  If s has a nonempty inline call identifier i, the i th entry of the inline table records the name of the procedure containing x.
Provide procedure traceback.  The Navigator debugger uses the existing Cedar traceback mechanism to generate a chain of pairs (x, P) of object locations and corresponding ordinary (non-inline) procedure names, in reverse order of invocation.  For each pair in this list, the debugger searches P's object table to find x's corresponding statement number s.  If s has an empty inline call identifier, then s came from the ordinary procedure P, and the debugger reports (s,P).  But if s has a nonempty inline call identifier i, then s came from an expanded call to some inline procedure Q.  The information for the deleted call is reconstructed as follows: Q's name appears in the i th entry of the inline table, as well as the statement number t inside P.  So the debugger reports (s, Q) followed by (t, P).
Examples
Set breakpoint.  Suppose the user requests a breakpoint at statement 13.  Using the source table, the debugger maps source statement 13 to object locations 13 and 26 and places breakpoints at both locations.  For added user information (and because inline directives appear physically in the source of a Cedar program), the Navigator debugger tells the user how many breakpoints were set.
Determine execution location.  Suppose that execution is suspended at object location 23.  Using the source table, the debugger maps object location 23 to source statement 12.  The associated inline table identifier 2 points to the second entry of the inline table, where the inline name SetX is recorded.  The debugger responds:
 Execution suspended at statement 12 in procedure SetX.
Provide procedure traceback.  Continuing with the preceding example, the debugger provides the next step of the traceback by again looking in the second entry of the inline table, where the statement number of the call, 55, is recorded.  The existing Cedar traceback mechanism provides the name of the ordinary procedure corresponding to statement 55.  The debugger responds:
 Called from statement 55 in procedure AdjustX.
5.7.1.3 Complications
Chapter 6 describes the compiler and debugger inline procedure expansion algorithms in more detail.  Nested inline procedures, which are inline procedures that are called from other inline procedures, and imported inline procedures, which are inline procedures declared in other modules, require that the compiler save more information in the inline table.  Chapter 6 also discusses how to cross-jump statements from expanded inline procedures and how to handle the secondary debugging functions inside an expanded procedure.  The affected secondary debugging functions are: displaying the values of local variables or parameters of inline procedures, procedure-level breakpoints, calling an inline procedure from the debugger's interpreter, and single-stepping with coarse granularity.
5.7.2 Cross-jumping
The compiler performs cross-jumping on an abstract code stream representation of the program.  To handle cross-jumping, the Navigator compiler collects additional static information in the augmented statement maps and in a special-purpose path determiner table.  In response to debugging requests, the Navigator debugger collects dynamic control-flow information.  Navigator achieves expected behavior for preplanned debugging activity and truthful behavior for unplanned debugging activity.
5.7.2.1 Additional static information
Overview
Augmented statement maps.  Navigator's enlarged source and object tables also allow many-to-one source-to-object mappings (for setting breakpoints as expected) and one-to-many object-to-source mappings (for determining the execution location truthfully).  Before the Navigator compiler deletes an instruction in the abstract code stream via cross-jumping, it merges the source reference for that instruction with the source reference for the corresponding instruction in the matching code sequence.  The two source references are distinguished from each other by the path determiner identifiers described in the next paragraph.  During the compiler's output phase, these source references are collected to form the source and object tables.
New path determiner table.  Before the Navigator compiler merges two code sequences, it gives each sequence a unique path determiner identifier.  The path determiner identifier links the source reference for each instruction in a sequence to the sentry instructions of that sequence.  For a given sequence, its source references are marked with its path determiner identifier, and its sentries are marked as path determining instructions for its path determiner identifier.  During the compiler's output phase, each path determiner identifier and the object code locations of the sentries for its sequence are recorded in the path determiner table.  The set of all object locations for a given path determiner identifier is called a path determiner.  The debugger uses the path determiners, along with the dynamic control-flow information described below, to determine the execution location with expected behavior.  The link between the source references and the sentries for a given sequence is indirect, through the path determiner identifier, for two reasons: first, the final

object location of each instruction is not known during cross-jumping, and second, later transformations might alter the sentry relationshipsthe indirect link allows the sentries to move without requiring that the source references be updated.
Examples
As before, Figure 5-4 gives an idea of Navigator's operation for cross-jumping without descending to the object code level.
The program.  This program fragment, shown on the left of the figure, fills the even elements of the array x with the successive values of the index i, and the odd elements of x with twice the successive values of i.  Each element of the boolean array filled indicates whether the value of the corresponding element of x is valid.    
The effects of cross-jumping.  The cross-jumping optimization works by looking backward from a join point for two sequences of identical code.  Here the THEN and the ELSE clauses join at statement 37.  In this case, both clauses end with storing x[i] and setting filled[i] to TRUE.  The compiler replaces the first identical code sequence by a jump from the beginning of the first sequence to the beginning of the second sequence.  A high-level view of the effects of the cross-jumping optimization is shown in the middle of the figure.
Navigator debugging tables.  The debugging tables generated by the Navigator compiler appear on the right of the figure.  The object table is aligned with the optimized version of the program for ease of comprehension.  Path determiner identifiers appear in the object table as subscripts on the merged source references.  The source references in the first identical code sequencethe second half of statement 32 (the store to x[i]) and all of statement 33are marked with path determiner identifier 1.  The source references in the second identical code sequencethe second half of statement 35 and all of statement 36are marked with path determiner identifier 2.  The single sentry of sequence 1, which is the branch to the merged region in statement 32, is marked as a path determining instruction for path determiner 1.  The single sentry of sequence 2, which is the load of 2*i immediately preceding the merged region, is marked as a path determining instruction for path determiner 2.  During the compiler's output phase, the final object locations of these path determining instructions are recorded in the path determiner table.  Notice that cross-jumping can merge less than an entire statement.  As a result, the optimized program is not completely representable in the source language.  The italicized statement fragments (in brackets) represent abstract machine computations.
fig54.press  leftMargin: 1.375 in,  topMargin: -0.875 in,  width: 6 in,  height: 8.5 in
Figure 5-4.  Cross-jumping example.
5.7.2.2 Additional dynamic information
Overview
New history pool.  The Navigator debugger activates a path determiner p by 1) placing a determining breakpoint at every object location x corresponding to p in the path determiner table (that is, at every sentry for p's sequence) and 2) allocating a determination cell in the debugger-managed history pool for every x.  A determining breakpoint collects history information about the execution path taken to enter a merged region, thus allowing the debugger to distinguish among multiple source alternatives inside the merged region.  When a determining breakpoint is reached, the debugger stores a timestamp in the determination cell associated with the determining breakpoint's object location.  Determining breakpoints are invisible to the user: execution resumes automatically.  A fine point: this operation is a bit more complicated in the presence of recursion or multiple processes [see Section 6.3.3.3].
Example
New history pool.   To activate path determiner 1, the debugger consults the path determiner table and places a determining breakpoint at object location 9.  It allocates a determination cell associated with object location 9 in the history pool and initializes its timestamp value to 0.  Whenever execution reaches the determining breakpoint, the debugger stores a timestamp, which is a monotonically increasing counter value, in the determination cell and continues program execution.
5.7.2.3 New debugger algorithms
Overview
Set breakpoint.  To set a breakpoint at a source statement s inside a merged region, the debugger searches for s in the source table and sets a primary breakpoint at the corresponding (single) object location x.  For each primary breakpoint, the debugger records the source statement of the user's request.  It then consults the object table to create a list L of source alternatives for x; it activates every path determiner associated with the source alternatives in L.
Determine execution location.  To determine the source location from an object location x, the debugger searches for x in the object table and returns a list L of corresponding source alternatives.  If the path determiners mentioned in this list have been activated, the debugger examines the determination cell(s) associated with each determiner and returns the determiner d that owns the latest determination cell timestamp.  The source alternative associated with d is the one on whose behalf the object location is executing this time.  If the path determiners have not been activated, the debugger reports the entire list of source alternatives (thus achieving only truthful behavior).  This situation arises for unplanned debugging activities, such as program exceptions or interrupts.
Provide procedure traceback.  Providing the procedure traceback is not directly affected by cross-jumping, but it is another situation in which debugging activity in a particular region may be unplanned.  If a merged region calls a procedure, and the path determiners for that region are not activated, then procedure tracebacks that include that region can only (truthfully) list the source alternatives.
Examples
Set breakpoint.  Returning to Figure 5-4, suppose the user requests a breakpoint at statement 36 before starting the program's execution.  Using the source table, the debugger maps source statement 36 to object location 17 and places a primary breakpoint there.  It then consults the object table to create a list of source alternatives for object location 17.  The list contains 331 and 362.  Finally, it activates the two path determiners mentioned in this list: 1 and 2, which places determining breakpoints at object locations 9 and 10 and allocates two determination cells in the history pool.  When the program executes, i is 0 (which is even) the first time through the loop, so the determining breakpoint at object location 9 is reached.  At the determining breakpoint, the debugger stores the current debugger execution count (say, 138) in the determination cell for object location 9 and resumes execution of the program.
Determine execution location.  Continuing with the previous example, suppose that execution proceeds to the primary breakpoint at object location 17.  Using the object table, the debugger maps object location 17 to source statement list 331, 362.  The debugger looks up the two path determiners that appear in this list (1 and 2) in the path determiner table and finds the object locations associated with them (9 and 10).  It then looks in the history pool for determination cells for these object locations.  The determination cell for object location 9 has the later timestamp (138 versus 0).  In the path determiner table, object location 9 corresponds to path determiner 1; therefore, statement 33 is executing.  The breakpoint was requested at statement 36, so the debugger resumes program execution. 
The next time through the loop, i is 1 (which is odd), so the determining breakpoint at object location 10 is reached.  At the determining breakpoint, the debugger stores the current debugger execution count (say, 140) in the determination cell for object location 10 and resumes execution of the program.  Execution then proceeds to the primary breakpoint at object location 17.  As before, the debugger uses the object table and the path determiner table to find the appropriate determination cells.  Looking in the history pool, it discovers that the determination cell for object location 10 has the later timestamp (140 versus 138).  Object location 10 corresponds to path determiner 2, which means that statement 36 is executing.  The breakpoint was requested at statement 36, so the debugger gives control to the user.
Now consider a different scenario.  The user begins the execution of the program without setting any breakpoints.  This program fragment has a bug in it: the array x is declared to have indices ranging from 0 to 5, but the loop index i ranges from 0 to 6.  As a result, a program exception (array index out of bounds) will occur when the program attempts to store into x[i] (at object location 13) in the last loop iteration.  When the exception occurs, the debugger uses the object table to map object location 13 into the statement list 321, 352.  Because no path determiners have been activated, the debugger cannot determine the exact source location.  Therefore the debugger responds:
  Error in statement 32 or 35: array index (i) out of bounds.
In this case, the user could examine the value of i (which is 6) to discover that execution must be at statement 32.
5.7.2.4 Complications
Chapter 6 describes the compiler and debugger cross-jumping algorithms in more detail and gives solutions for several complications that arise.  With no further processing than that described here, Navigator can provide only truthful behavior for programs with ambiguous control flow.  To avoid incorrect debugger behavior, cross-jumped regions with embedded exception handlers require additional work during compilation, while multiple processes and/or recursion inside a merged region require additional work during debugging.  There are some efficiency issues associated with the allocation and de-allocation of determination cells.  Furthermore, repeated application of cross-jumping requires additional mechanisms during compilation and debugging.  Chapter 6 also explains how to cross-jump statements from expanded inline procedures, how to apply other object code optimizations to cross-jumped regions without disturbing the path determiners, and how to handle the secondary debugging functions (single-stepping and displaying the values of local variables) inside a merged region.
Chapter 7 discusses the correctness and the performance of the complete algorithms and describes some possible improvements.
5.8 Features and drawbacks of path determination
The path determination method usually provides expected debugging capabilities for control-flow optimized programs.  In addition, it has the practical properties that we desire.  Runtime path determination costs execution time or space (excluding space for the tables, which need not reside in main memory) only if a breakpoint has been placed in a merged region.  The cost is proportional to the number and merging complexity of merged regions that have breakpoints set inside them.
Of course, if determining breakpoints and/or primary breakpoints are placed inside loops that execute very frequently, the processing of determining breakpoints and undesired primary breakpoints could make the program execute significantly more slowly.  Luckily, in the Cedar environment, a trap to the debugger (with its associated process switch) costs only on the order of a procedure call.  Since compiling is relatively slow in the Cedar environment, even in these extreme cases it is likely to be faster to use the runtime path determination mechanism for long enough to discover the problem than to recompile the program with cross-jumping disabled.  Additional measurements need to be collected to determine how serious this drawback is.  The Navigator path determination technique would work in an environment with expensive process switches, but its performance would be less satisfactory.
The path determination method has another drawback.  Since path determiners generate no code, they must be activated to provide exact path determination.  If a runtime error or interrupt is encountered inside a merged region, Navigator can only list the source alternatives.  Similarly, if a merged region contains a procedure call, procedure tracebacks that include that area can only list the source alternatives.  In some cases, the user can inspect the values of variables to determine the exact path.  If this is not sufficient, the user must restart the execution with a breakpoint at the offending locationit is not necessary to recompile the program with cross-jumping disabled.  It would be useful in such instances to decouple path determiner activation from breakpoint insertion.  A new Navigator debugging command, SUSPECT, has been designed to explicitly activate all path determiners within a suspect procedure.
Furthermore, there are cross-jumped regions for which exact path determination is not possible.  If an entire path generates the same object code as some other joining path, both path determiners will mark the same instruction.  Section 6.3.3 describes this problem in more detail and discusses several possible solutions to it.  If expected behavior is essential, the compiler could use the lack of distinct places to put path determiners to prohibit later object code optimizations from merging two paths completely.  This solution would result in a slightly less optimized program.
The path determination algorithm was inspired by a method sketched by Teeple and Anderson in an unpublished manuscript [Teeple+80].  In their approach, determining breakpoints are placed at those n-1 entrances to an n-way merged region from which code was deleted; their determining breakpoints are also invisible to the user.  When control reaches a determining breakpoint, the debugger single-steps the program until the primary breakpoint is reached, at which time it is known that control flow came through that piece of deleted code.  If the primary breakpoint is reached when not single-stepping, control flow must have passed through the path without the determining breakpoint.  Since Teeple and Anderson's technique was never fully designed or implemented [Teeple81], its description is incomplete.  Among other things, they failed to realize that merging less than an entire statement still requires path determination, and they did not discover that repeated cross-jumping can cause nested determiners.
The use of single-stepping as a path determination mechanism is not very satisfactory.  When loop initialization and termination code are cross-jumped, the optimized program's control can pass either from the determining breakpoint into the merged region (and hence to the primary breakpoint), or from the determining breakpoint to some other portion of the program.  It can be difficult to determine when to terminate single-stepping in these cases.  Furthermore, single-stepping from the determining breakpoint is only applicable to control-flow optimizations, whereas doing something at an invisible breakpoint and then continuing can be used to handle other classes of optimization.
5.9 Other runtime path determination algorithms
A debugger could use the path determiner locations identified by the compiler in a different way to distinguish among source alternatives in a merged region at runtime.  The compiler could insert determination code at each determiner to load a compiler temporary with an indication that control flow came that way.  In fact, this is the natural method to think of for collecting runtime history information.  This method would always provide expected debugging, but it would increase object code size by at least n stores for every n-way merge, and it would also increase data space.  Furthermore, the determination code would inhibit later optimizations in that area.  It might also be difficult to insert determination code at the exact sentry of the merged region.  For example, the determination code might cause the runtime expression evaluation stack to overflow.  Not only is the object code optimization phase unprepared to spill the expression stack, but spilling would introduce still more object code.  However, the most compelling reasons to reject this method are that the determination code would probably consume more space than the cross-jumping algorithm saved, and the (supposedly) optimized program would run more slowly than the unoptimized version.
The space and speed penalties associated with determination code could be largely avoided if hardware for execution tracing were available.  The information gathered by the execution tracing hardware could be searched for the most recent appearance of a path determiner location.  However, any execution history recording mechanism that uses a fixed-size storage area could fail to distinguish among multiple paths in a merged region.  As an example, consider the program in Figure 5-5, and suppose that the statements inside Proc generate a large amount of history information.
							              
source program fragment	after cross-jumping
	
1 IF cond THEN	IF cond THEN
2   {Proc[a];		  {<load  a>;
3    Write["hi"]}	   <goto L>}
4 ELSE		ELSE
5   {Proc[b];		  {<load  b>;
		L: <call Proc>;
6    Write["hi"]};	   Write["hi"]};
Figure 5-5. Difficult case for hardware-supported execution-history mechanism.
							              
A second approach would utilize the values of user variables.  For each case in which many source statements correspond to one object location, the optimization process would construct a function from selected user variables to possible source alternatives.  When execution reaches the object location, the function would be evaluated to determine the exact source statement.  Figure 5-6a shows a sample cross-jumped program and some possible functions.  There are two drawbacks to this approach.  First, it is very difficult to choose appropriate user variables and construct such a function (in general it requires global data-flow analysis [Aho+77]).  Second, in many cases no such function exists.  In Figure 5-6b, by the time the call to Write is reached, the value that was used to decide which path to take has been destroyed and probably cannot be reconstructed.
							              
source program fragment	after cross-jumping

1 IF cond THEN	IF cond THEN
2    {a _ 1;		   {<load 1>;	
3     c _ 5}		    <goto L>}
4 ELSE		ELSE
5    {a _ 2;		   {<load 2>;
      		L:  <store a>;
6     c _ 5};		    c _ 5};	*
    		
at *, determining function: IF a = 1 THEN stmt 3 ELSE stmt 6
       alternate function: IF cond THEN stmt 3 ELSE stmt 6
	          (a)

1 IF F[x,y] THEN	IF F[x,y] THEN
2    {x _ G[x];	   {<load G[x]>;
3     print[x]}	    <goto L>}
4 ELSE		ELSE
5    {x _ H[x];	   {<load H[x]>;
		L:  <store x>;
6     Write[x]};	    Write[x]};  *
    
at *, determining function does not exist unless F, G, and H are very special
	          (b)
Figure 5-6.  Path determination by variable values.
							              
5.10 Navigator overview summary
Navigator has a running prototype.  The compiler modifications for Navigator comprise approximately 1500 lines of Cedar source code, or about 3% of the size of the original Cedar compiler.  Navigator's runtime routines add about 1000 lines of source code to the debugger.  Preliminary evaluation of the untuned system shows that the extra compilation and execution costs of using Navigator are small: the compiler is roughly 15% slower, and debugger responses are not noticeably altered.
To my knowledge, Navigator is the only working system for debugging optimized programs in a production environment.  In most cases, Navigator can provide expected debugging for control-flow optimized programs, in which the ordering of computations along any execution path is preserved.  When expected performance cannot be achieved, Navigator provides truthful debugging.  Navigator sacrifices expected performance for runtime errors, interrupts, and procedure calls inside merged regions in order to preserve the efficiency needed for routine use.  Figure 5-7 summarizes how Navigator achieves its improved debugger behavior.
To provide truthful behavior, the Navigator compiler builds augmented many-to-many statement maps.  The compiler keeps source references with their corresponding code during optimizations.  As a result, the Navigator debugger can set breakpoints and list source alternatives for an object location.
To provide expected behavior, the Navigator compiler adds the inline table and the path determining mechanism.  Using the inline table, the Navigator debugger can report "deleted" procedure calls in the procedure traceback as if they had occurred.  For the path determining mechanism, the compiler locates the path determiner locations, and the debugger collects history information when the determiner is active.  As a result, the debugger can determine the exact source statement at a breakpoint (but possibly not at an unplanned suspension point).
Except in rare instances, program execution space and speed are almost totally unaffected when no debugging requests are active.  When debugging is requested, Navigator provides its added functionality without noticeably degrading debugger response time for most programs.
Appendix A illustrates a sample Navigator debugging session via a series of screen snapshots.

							              
Inline procedure expansion
Collect static information in the compiler
1. Collect one-to-many source-to-object references in augmented statement map (SM).
    Debugging use: set breakpoints and determine execution location truthfully.
2. Collect callee names and statement numbers of calls to inlines in new inline table (IT).
   Associate IT entries with statement references in SM.
    Debugging use: display procedure traceback with expected behavior.
Use new debugger algorithms to process the information
1. Set breakpoint: use SM; set breakpoint at multiple associated object locations.
2. Determine execution location: use SM; report single source statement.
       Use IT reference in SM to get procedure name of callee.
3. Procedure traceback: use IT reference in SM to get statement number in caller.
       Use normal Cedar mechanism to get procedure name of caller.

Cross-jumping
Collect static information in the compiler
1. Collect many-to-one source-to-object references in augmented SM.
    Debugging use: set breakpoints expectedly, determine execution location truthfully.
2. Collect object locations of sentries of merging sequences in new path determiner table (PDT).
   Associate these path determiners (PDT entries) with statement references in SM.
    Debugging use: determine execution location with expected behavior.
Collect dynamic information in the debugger
1. When a path determiner is activated, the debugger collects execution history information (via
   invisible determining breakpoints) at sentries of merged regions in history pool (HP).
    Debugging use: determine execution location with expected behavior.
Use new debugger algorithms to process the information
1. Set breakpoint: use SM; set breakpoint at single associated object location.
       Use PDT references in SM; activate associated path determiners.
2. Determine execution location: use SM; get multiple source statements.
       Use PDT references in SM:
	If path determiners are active, use HP to determine exact location.
	If not, report the list of source alternatives.
3. Procedure traceback: (not affected).

Figure 5-7. Summary of the Navigator improvements.
							              
*CHAPTER 5:  OVERVIEW OF NAVIGATOR

�Ê
ò–
"thesis" style–9(firstPageNumber) 92 .def (firstHeadersAfterPage) 92 .def˜Iblock•MarkcenterHeaderšÐls
Ïs�
žœ
žœ
ž™!J™Ichapheadš
œ!˜!I
thesisbody˜ÈMš
œ£˜£M˜Þ
head˜M˜òMš
œÔ˜ÔM˜R˜$Mšœ�Ïiœ ˜ºMš
œ›˜›I	pagebreak˜Kš
Ïz˜
tblock˜Iindentš
œ˜Qš
œ˜—šœŸœ˜#Q˜)Q˜*Q˜!—šœŸ	œ2˜BQ˜/Q˜$Q˜Q˜#—˜%Q˜EQš
œ"˜"—˜#Q˜+Q˜,Q˜C—˜*	˜xQ˜e—Q˜<	˜BQ˜“
——Q˜I	bigcenterš
Ïb;˜;Kš
 ˜O˜Mšœ“žŠ
œ±žœ
˜â—š
œ˜Mš
œÛ
˜Û
MšœŸœÕžœˆžœª
˜³MšœŸ	œ’˜¡—š
œ#˜#Mš
œŠ˜ŠMšœ§žM˜ô—š
œ%˜%M˜oItenum2šÑmvx
œU˜VSš¢
œU˜VSš¢
œ;˜<Mšœ¿ž
œÿ
Ÿ!œ
˜ê—š
œ,˜,Mš
œ½˜½Mš
œ™˜™—M˜O˜˜�Sš¢
œh˜iSš¢
œÀ
˜Á
Sš¢
œ‚
˜ƒ
——˜MšŸœµ
ŸœÍ
Ÿœ­˜îMšŸ;œÐ
˜‹MšŸ.œ›žœbžœ„
žœŽ
˜èMšŸ%œüž7˜Ø—˜"M˜•Sš¢
œ8ž˜LSš¢
œ’
ž˜¦
Sš¢
œCž˜WSš¢
œ<ž˜PSš¢
œZž˜j—š
œF˜FMš
œ»˜»š
œ>˜>Mš
œŸ˜ŸMš
œÊ˜ÊIcenter•ArtworkClassIncludePressš
œ^˜^Mšœožœ)žœŸ
œÛ˜¡O˜Pšœwžœx˜÷
T–IncludePressš
œ^˜^—M˜Ó
˜MšœÓ
ždœ
˜¸MšŸœ¬˜ÇMšŸœŒ˜šO˜—˜(M˜ÒMšŸœõ˜�MšŸœ’Ÿ	œ•
˜¾M˜ÍMš
ώ
˜é
š
œŒ˜ŒT–IncludePressš
œ]˜]—˜=IprogexšœÏd
ϣ
ϣ
ϣ
ϣ
œÏtœ£
ϣ
ϣ
ϣ
ϣ
œ˜/—šœNÏfœU˜¦
T–IncludePressš
œ]˜]—˜NUšœ£
ϣ
ϣϣϣ
œ¤œ£
ϣ
ϣϣϣ
œ˜7—Pšœ?¥
œ;¥
œL¥
ϴ
œ.¥
œ.¥
œ?¥
œ.¥
œ\¥
œ;¥
œa¥
ϴ
œžqÐfs
ž¦
žì
˜‚Mšœ\Ÿœ¥
ϴ
œÝ
˜æMšœñ
Ÿœ'ŸœBŸœ×
˜Ä—˜%MšŸœ¿˜ÚMšŸœ¿
˜Í
——˜%M˜¹˜Mšœwž
œQžœf˜ÇMšœÙ
žœ·
˜œMšœ¯ž œ_ŸœNž
œ
˜‘MšœñžœŸœÒ
˜äMš	œ´žœzž8ÐszžœUžœ¦˜ýMšœý
žœy˜�—˜M˜�
MšŸ-œªžœžœh˜ÓMšŸ-œ8Ÿœ(Ÿœ‘Ÿ	œãŸœ	ŸœœŸœŸœŽ
Ÿœå
˜ëMšŸœæ˜øMšŸœÍ˜ßO˜Pš
œ¼
˜¼
MšŸ	œ
ŸœŒžœ
˜²MšŸ	œ
ŸœGž
œ¿
ž	œå
˜¢——˜&Mš
œ�˜�˜!Mšœ}ž
ϫ
¥
œ¥œ¥	œ¥	œ
˜�˜Uš%¦RÑfis¦Ñfms
¦©
¦©
¦¨¦©
¦©
¦©
¦¨¦©
¦©
¦©
¦@©
¦©
¦©
¦l©
¦©
¦©
¦˜Ò—Mš
œP˜PMšœÙ
¥	œö
¥
œ4¥
œ
˜¡Mš
œ§˜§Mš	œY¥
ϩ
¥œL¥œw¥
œ˜þ˜Uš	¦4¨¦©
¦©
¦©
¦U˜¦
—Mšœ ¥œ�˜È˜'MšœÔŸœwŸ	œ˜éMšœ§ŸœxŸœ[¥œžœQ¥œ˜�——˜"š	œ‹žœv¥œ
¥
œ
¥œ“˜¤	Uš+¦Z¨¦
©
¦©
¦©
¦©
¦©
¦©
¦‚
¨¦©
¦©
¦©
¦©
¦©
¦©
¦¬
¨¦
©
¦©
¦©
¦©
¦©
¦©
¦$˜Å———š
œ@˜@M˜ýM˜Ì
O˜T–IncludePressš
œY˜YRš
¡D˜D˜ Mš
œˆ˜ˆš
œ%˜%˜MšŸœÁŸœ3Ÿœï
˜”MšŸœô
Ÿœ·˜Ò—˜M˜÷
O˜T–IncludePressš
œV˜VRš
¡0˜0MšŸœH¥œ4¥
œ`¥œ7¥œ¥œ˜æMšŸ*œ†
¥œÉ˜ýMšŸœç˜‚——š
œ˜˜MšŸœ,Ÿ
œ7Ÿ
œd˜Ø
MšŸœ;Ÿ
œŸ
œDŸ
œŸ
œ'Ÿ
œŸ
ÏuœHŸ
œ
˜¾Mš0ŸœcŸ
œŸ
Ϣ
Ÿ
œŸ
œ"Ÿ
œŸ
œ+Ÿ
œ"Ÿ
œŸ
œ
ž
Ÿ
œŸ
œ'Ÿ
œŸ
œ5Ÿ
œEŸ
œŸ
ªœ<Ÿ
œŸ
œŸ
œŸ
œŸ
œ
Ÿœ˜¦—˜MšŸœõ˜„šŸœƒ¥œ%˜ÉUš
œ7˜7—šŸœÛ˜÷Uš
œ/˜/———š
œ˜Mš
œ’˜’——˜Mš
œë˜ëš
œ%˜%˜MšŸœË˜äMšŸœ[ŸœÎŸœÌ˜¸O˜Pš
ϙ
˜ô
—˜M˜{MšŸœ_¥
œ)¥
ϴ
œ%¥
œ%¥œ=¥
œ˜ÎMšŸœ|žœ	žœL¥œ
¥	œ¥œ€˜˜MšŸœ‘¥œê
ŸœÕ
¥œù˜í
T–IncludePressš
œW˜WRš
¡#˜#——š
œ&˜&˜MšŸœŸ	œŸ
œŸœŸ
œŸ
œ<Ÿ
œ!Ÿœ0Ÿ
œ¼žœ
˜�—˜MšŸœÕ˜æ——š
œ˜˜MšŸœ,Ÿ
œ3Ÿ
œ Ÿœ/Ÿ
ϥ
Ÿ
œŸ
œPŸ
œ
˜×MšŸœ;Ÿ
œŸ
œ(Ÿ
œ×
Ÿœ[Ÿ
œÃ˜—MšŸœù˜•—˜MšŸœï£
ϣ
ϓ
¥
œ¯˜£MšŸœÒ
£
ϣ
œ²˜§Mšœ ¥
œ˜˜¹šœ¤
¥
œE¥
Ϡ
¥œ¨
£
ϣ
œŽ
˜±Uš
œ=˜=—Pšœ2¥
œA˜t——š
œ˜Mš
œÀ˜ÀMš
œ|˜|———š
œ0˜0Mšœ³Ÿœ¬
˜ãMšœ‰Ÿœø˜ƒMšœ¼žœ[˜žM˜ÈMš	œwžœBŸœŸ
œ¤ž
ϔ
˜õM˜®—š
œ/˜/Mš	œÄ
Ÿœ«Ÿ
œŸ
œ·Ÿœ˜õ	MšœŽ¥œ0˜ÂKš
 ˜UšÑfps¦
«¦1¨	¦¨¦!¨	¦¨¦%˜å
Rš
¡N˜NKš
 ˜Mšœƒžœ\¥œz˜æKš
 ˜Uš ›
 @¦
¬¦
ž/Ðisž¨ž!­ž­	žÐps%ž®
ž®
ž®ž®ž
®ž®
ž®
ž®ž®˜ÝUš
Ðbp˜U˜Ušž4­ž¨ž#­ž­	ž#®8ž®ž®˜“Uš
¯˜Rš
¯3˜3Kš
 ˜—˜M˜çM˜óM˜ªM˜¦M˜�M˜]O˜Kš
 ˜š
¡˜š
Ÿ*˜*˜SQ˜O—˜”
Q˜F——š
Ÿ6˜6K˜RK˜‡
K˜”
——Istandard˜š
¡
˜
š
Ÿ*˜*˜CQ˜W—šœtŸœ/˜³
Q˜G——š
Ÿ+˜+šœŸ	œHŸœ5˜º
Q˜G——š
Ÿ6˜6Kš
œ–
˜–
Kš
ϧ
˜ß
K˜'V˜——Rš
¡2˜2Kš
 ˜——…—2l
@ˆ