To show that the compiler's path determination algorithm works correctly, we must prove that the following properties hold:

Two lemmas will be useful:

To show that the debugger's path determination algorithm works correctly, we must prove that:

This section analyzes the runtime storage requirements and execution speed for merged regions that consist of several identical paths that are all the same length. The execution speed analysis applies equally to the remaining two cases, successively longer merges and successively shorter merges, which are considered in subsequent sections.

Consider the program schema in Figure 7-3: four joining paths are merged in successively shorter order. Again, for simplicity, each path has one external sentry of the unoptimized region. As before, three successive merges are required to completely collapse the region. When the paths are merged in successively shorter order, the cross-jumping algorithm needs a total of

This case has very pleasant properties: an instruction that was merged in the jth merge becomes the single sentry of one of the merging sequences in the j+1st merge. As a result, only the minimum number of path determiner assignments are inserted, each marking a different object

Furthermore, this case causes only the minimum number of determiner uses in the object table. If p is the number of paths in the unoptimized subregion in which a given instruction group appeared and s is the number of determiner uses on each source alternative in the group, the number of determiner uses in the object table for the instruction group is

At first glance (and in the two examples), the total number of determiner uses for successively shorter paths is smaller than the total number of determiner uses for paths of the same length. This is primarily because the unoptimized region has fewer instructions in the successively shorter case. However, the number of determiner uses could actually be larger for the successively shorter case because the different lengths of the merges can introduce additional subregion boundaries (that is, some of the subregions might contain only a portion of a source statement).

Figures 7-4a and 7-4b illustrate the application of cross-jumping to a program schema in which successively longer paths join. This schema is really the same schema as Figure 7-3, but cross-jumping is applied in the opposite order (which, as this section shows, is extremely unfortunate). This time, six successive merges are required to completely collapse the region: the first merge of each instruction creates a label immediately preceding the instruction; subsequent merges must stop at that label because a merging sequence cannot contain an embedded label. When successively longer paths are merged, the cross-jumping algorithm uses a total of

The successively longer case has terrible properties: it causes many determiner assignments to be inserted, frequently on the same object locations. Each stage merges p paths of the same length, where p decreases from one stage to the next (p = n—s+1). Therefore the analysis of Section 7.2.1 applies to each stage. This example has sixteen determiner assignments.

In addition, this case creates many instances of indirect determiner uses on the determiner assignments. A layer of identical instructions become internal sentries in one stage and get determiner assignments. In the next stage, these instructions are merged to form a single internal sentry; indirect determiner uses on the merged list of determiner assignments distinguish among the merged sentries. By contrast, in the successively shorter ordering described in the preceding section, instructions are merged first and become internal sentries of a new subregion later. This example has fourteen indirect determiner uses. Together with the sixteen determiner assignments, thirty units of determiner storage are used in the determiner table.

We now consider the merging of n successively longer paths from a theoretical standpoint. Since each stage s is an instance of merging ps paths of equal length, the idealized analysis of Section 7.2.1 applies: to distinguish among the ps paths, stage s should create ps distinct determiner assignments and ps determiner uses per instruction group. If the next stage s+1 were to combine the identical sentries minimally, only ps—1=ps+1 indirect determiner uses would be needed to distinguish among them. At a primary breakpoint, the determiner with the most recent timestamp value among the p alternatives would indicate the correct source alternative. Figure 7-5 shows the idealized view of cross-jumping n successively longer paths.

For the successively shorter case, the total storage used when the longest path has n—1 instructions is

If the same region were merged using the idealized successively longer ordering, the total storage used would be

Surprisingly, when n is five or greater, the idealized successively longer ordering uses less total storage. However, the idealized successively longer case does require more merges (as well as an as-yet-unspecified minimization step; see Section 7.4): 1/2 n2 — 1/2 n as opposed to n—1. Both cases activate the same number of determining breakpoints for a given primary breakpoint, and both cases examine the same number of timestamp values at a given primary breakpoint.

The cross-jumping algorithm considers labels for cross-jumping in successive linear passes through the abstract code stream. Therefore, the successively longer merge ordering can be doubly expensive: the first merge of each stage creates a new label, which prevents later applications of cross-jumping from merging longer paths. Furthermore, that new label is most often inserted earlier in the abstract code stream than the label currently being cross-jumped, so that another pass through the code stream is necessary. Therefore, each stage of the merge typically requires a separate pass through the entire code stream. Of course, a more complicated cross-jumping algorithm could maintain a list of labels to be considered so that an entire extra pass would not be needed.

The equal length case of repeated cross-jumping [described in Section 7.2.1] uses more storage than is theoretically necessary because every time an instruction belongs to a merging sequence, every source descriptor for that instruction gets a determiner use for the sequence's determiner. Furthermore, the determiner assignments grow similarly: each merging sequence for a given merge gets a new determiner assignment at its sentry, regardless of whether that sentry was already guarding that exact instruction sequence. This explosion of the number of determiner uses and determiner assignments can be prevented by modifying the path determination algorithm as follows: Each source descriptor gets a determiner use for (only) the path determiner for the first merging sequence to which it belongs. Similarly, when a path determining instruction appears in a merging sequence, its determiner assignment(s) get an indirect determiner use (only) for the first merging sequence that contains it. As a result, when a path has been merged before, the algorithm relies upon the original determiner assignments (as well as possible chains of indirect determiner uses) to distinguish among the source alternatives and path determiner assignments. Figure 7-6 shows the application of this version of the algorithm, called the First Crossing Marks algorithm, to the successively longer paths of Figure 7-4.

This change saves storage for determiner uses in the object table directly: each source alternative contains exactly one determiner use. It also saves storage in the path determiner table (as well as processing time at a primary breakpoint) indirectly: a determiner for a merging sequence that included only previously-merged instructions (and no sentries) will not be used by any instructions nor any determiner assignments. Therefore, all assignments of that determiner can be deleted from the determiner table. [Actually, the condition under which a determiner assignment can be deleted is a bit more complicated: no source descriptor uses it, and no sentry descriptor uses it or its opposite. This distinction between source and sentry descriptors arises because it is possible that only one of two merging instructions has a sentry descriptor, but both instructions must have a source descriptor. Therefore a determiner use for each merging sequence will automatically be created for source descriptors, while it may not be for sentry descriptors.] For the equal length and the successively shorter cases, this algorithm uses only n distinct determiner assignments for n paths. Determiner assignments mark only the external sentries.

However, there is a problem with this improvement. Debugger correctness property D2 [setting a breakpoint when the execution point is already inside a merged region never causes incorrect behavior; see Section 7.1.2] may fail. If a merged region has unmarked internal sentries and each primary breakpoint activates only the determiners needed to distinguish among paths to it at runtime, then the timestamp cells can give incorrect information when multiple breakpoints are placed in a repeatedly merged region. Consider the following program fragment, in which three paths have been merged using the improved algorithm and the successively shorter ordering. As a result, control flow can enter the region through a currently inactive external sentry s. If s is still inactive when the primary breakpoint is reached, the debugger can detect this unusual condition and report the source alternative corresponding to s also. But if s is activated between the time that control entered the region and the time that the primary breakpoint is reached, the debugger can be fooled into giving an incorrect response.

Referring to the program fragment, one possible faulty scenario proceeds as follows: Before starting the program, the user sets breakpoint 1 inside procedure P and breakpoint 2 at statement 21. Breakpoint 2 activates path determiners 1 and 2. After execution begins, control enters the merged region through determiner assignment 1 at time t1. The primary breakpoint for breakpoint 2 is reached (control is not passed to the user), breakpoint 1 inside P is reached, and then control leaves the merged region. Later, the merged region is entered through determiner 4 (which has not yet been activated) at time t2, and breakpoint 1 inside P is reached again. While at breakpoint 1, the user requests breakpoint 3 at statement 34, activating path determiner 4, and proceeds. (Note that procedure P has no knowledge of any determiners active in its caller.) Upon arrival at the primary breakpoint for breakpoint 3, the timestamp cells indicate that statement 34 is executing (timestamp4 = 0, timestamp2 = 0, and timestamp1 = t1). Therefore, although statement 12 is actually executing, the debugger relinquishes control to the user, saying that breakpoint 3 at statement 34 has been reached.

There are two solutions to this problem that retain the improved path determination algorithm.

One solution is to record the time that each determining breakpoint was set. The algorithm for fielding a primary breakpoint at an instruction b becomes more complicated. One pass through the determiners discovers the time t of the most recent recorded sentry of the merged region from the determination timestamps. A second pass identifies the set of possible determiners, which are all determiners referenced in the source alternatives for b that (1) have a determination timestamp equal to t, (2) have at least one assignment whose determining breakpoint was set more recently than t, or (3) have not yet been activated. When debugging is active, this solution uses more debugger storage and requires additional processing at each arrival at a primary breakpoint.

The other solution is to create equivalence classes of determiners, clustering all determiners that cover a given (possibly complex) merged region together. Then all determiners for a given region would always be activated at the same time. These equivalence classes could be created during the cross-jumping optimization or in a single post-pass through the statement map and the determiner table. This solution requires a small amount of additional compilation time to discover the equivalence classes and extra debugging table space to store them. These increases are likely to be more than offset by the reduction in compilation time (for creating and managing the path determiner structures) and path determiner storage that this version of the algorithm permits.

The successively longer case of repeated cross-jumping (described in Section 7.2.3) is much worse than the equal length or successively shorter cases because many more applications of cross-jumping (which insert more determiner uses and assignments) are needed to collapse the region completely. The additional applications of cross-jumping are necessary because the first merge of each stage inserts a new label, thereby preventing later applications of cross-jumping from merging longer paths. If merging sequences were permitted to contain embedded labels, the later applications of cross-jumping could match the full length of the identical tails at once, and would require a total of

Very few changes to the cross-jumping and path determination algorithms are required to permit embedded labels. The cross-jumping instruction matching routine is altered to skip over embedded labels in either merging sequence. As before, the path determination algorithm gives all sentries of a merging sequence a path determiner assignment for that sequence. However, some of the sentries may now be immediate dynamic predecessors of an instruction other than the top instruction in the sequence.

For additional efficiency, two more changes are made to allow paths with internal control flow, in the form of embedded forward jumps (an IF-THEN-ELSE structure), to be matched in a single application of cross-jumping. First, the cross-jumping instruction matching routine is altered to permit embedded jumps in either merging sequence. Two unconditional jumps match if they have the same jump destination. Two conditional jumps match if they have the same opcode, the same operand(s), and the same jump destination. [Note that conditional jumps are only permitted strictly inside a merging sequence (that is, they are still not permitted as link cells).] Second, when the backward comparison scan encounters an embedded label in the to-delete sequence, it immediately redirects each jump to that label to the corresponding point in the to-remain sequence, inserting a new label there if necessary. This "instant branch chaining" step means that two "congruent" forward jumps will become identical by the time that the backward comparison scan reaches them. It does not provide a general flowgraph-structural match for jumps, however: two "congruent" backward jumps will never match. Note that these internal jumps are not sentries of the merging sequence: a sentry of a sequence is always outside that sequence. [A sentry occurring inside its sequence would overwrite its determiner's timestamp value.] When the backward match and merge occur in one backward sweep, the sentries for each embedded label receive a determiner assignment for the label's path determiner when the label is encountered. When a forward jump to such a label is encountered later in the same backward sweep, it has a determiner assignment equal to the determiner for that sequence. This determiner assignment is removed.

As shown in Figure 7-8, this improved version of the algorithm can merge the successively longer paths of Figure 7-4 in three successive applications of cross-jumping, rather than six. It can merge the complicated nested example of Figure 6-11 [see page 162] in three merges rather than four.

Two problems can arise from this improvement. The first problem is the introduction of nonessential ambiguity. That is, a single sentry z might dynamically precede a different instruction in each merging sequence, as illustrated in Figure 7-7. As a result, z is given determiner assignments for both merging sequences—whenever the merged region is entered through z, the values of the determination cells do not distinguish between the two regions. This situation is particularly unfortunate because it is possible to place more determiner assignments in this region so the source alternatives can be distinguished. If c were merged alone, followed by merging a and b as a unit, the resulting four determiners can distinguish between the two source alternatives for c.

The second problem is worse: incorrect path determination might result. This situation arises when an instruction inside a merging sequence is an immediate dynamic predecessor of an instruction in both merging sequences. This situation, depicted in Figure 7-9, can arise when conditional jumps and labels are permitted inside merging sequences. For instance, the dynamic control flow information collected at the two determiner assignments do not determine which of statements 12 and 32 are executing at instruction b.

The most satisfactory solution for these problems is to detect them during the application of cross-jumping and disallow embedded labels for their particular cases.

The two improvements to the cross-jumping and the path determination algorithms can be combined to create an algorithm that merges paths in fewer iterations and uses only one determiner use per source or sentry descriptor. This algorithm, called the Combined algorithm, has the problems of the preceding two algorithms plus a few of its own. [This is the algorithm reported in my previous paper on Navigator [Zellweger83].] For comparison with the previous algorithms, Figure 7-10 shows the application of the Combined algorithm to the successively longer paths of Figure 7-4.

This combined version causes additional problems for repeated nested merging: that is, for cases in which each of two identical sequences has internal identical sequences. Because of the "first crossing marks" property, the Combined algorithm works only when the inner merge occurs first; the inner determiner assignments then depend upon the outer determiner assignments. When the outer merge occurs first, the Combined algorithm creates ambiguity (i.e., only truthful behavior). These problems do not occur for the First Crossing Marks version because embedded labels are necessary to create nested regions. Note that for either "determiner use list" version (i.e., the original cross-jumping algorithm or the Embedded Label version), it is more desirable to merge the outer region first because then the region can be merged completely with only two merges rather than three.

To solve the problems with the Combined algorithm in general, some sort of recursive cross-jumping algorithm could be used to ensure that inner merges always occur first. Another possibility is to identify these problem cases and fall back to one of the previous algorithms when one of them is discovered.

The following cases demonstrate situations in which the outer merge occurs first. These problems can be created in actual Cedar programs: the juxtaposed case can arise in SELECT statements, while the backward jump nested case can arise in loops containing conditionals. Special-case solutions are identified for each case.

Juxtaposed case (four paths to the merging label). Suppose that two paths to the merging label have identical tails and are statically juxtaposed; they thereby form one "double" sequence. Suppose further that this sequence matches an identical "double" sequence. These two "double" sequences therefore have opportunities for either two or three merges, depending on the merging order. The merging order that causes difficulty is the one in which the "double" sequences are merged first and the internal merge occurs second; Figure 7-11 illustrates the difficulty. These "double" sequences are legal merging sequences for the Combined algorithm because it permits embedded labels and unconditional jumps. In this situation, the first merge gives all of the source descriptors determiner uses for its two determiners. The second merge includes only previously-merged instructions. Since the Combined algorithm never marks such instructions, the two determiners for the second merge are neither activated nor examined to distinguish between the two inner paths—in fact, they are deleted. The final result is that the instructions that participated in the second merge can only be reported as lists of two source alternatives.

As a special-case solution for the juxtaposed case, we can disallow embedded jumps to the current merging label.

Backward jump nested case (two paths to the merging label). Suppose that two identical sequences with internal cross-jumping opportunities (as a result of internal control flow) each end in a backward jump to the merging label. [This situation is similar to the nested cross-jumping depicted in Figure 6-11, page 162.] Because the merging label appears earlier in the codestream than either sequence, the outer sequences are considered for cross-jumping before the inner sequences. As in the juxtaposed case, performing the outer merge first when each source descriptor can only have one determiner use means that the path determiners of the inner merge are never used. The inner statements cannot be distinguished by the resulting path determiner structures.

As a special-case solution for the backward jump nested case, we can delay the application of cross-jumping. Rather than trigger cross-jumping on a label as soon as that label is encountered during the codestream scan, trigger it upon encountering the latest item among the label and all jumps to it. To detect this condition, a "seen-this-codestream-pass" flag can be added to each jump and label. Each successive cross-jumping pass would toggle the flag.