Program Execution Analysis

To detect hang if a program hangs, its execution is analyzed. A critical part is loop detection. Once loops are detected, program execution can be summarized into Run Blocks. With that, nested loops can be detected. Finally, loops may need to be analyzed in detail to proof that a program hangs.

Detecting a loop

Programs can contain one or more loops. Inside a loop, the same set of instructions is repeatedly executed. During search, whenever a 2LBB program finishes execution of a program block, a loop detection algorithm is performed.

When the program is not yet executing a (detected) loop, the detection algorithm checks if it executed the same sequence of program blocks twice. This can be checked for in lineair time by using the Z-Function. If a repetition is found, the state is updated to reflect that the program is looping.

Example: Assume the program just finished executed the following sequence of program blocks "ABACDECDE". At that moment, it detects it is executing a loop, consisting of three program blocks: C, D and E.

When the program is executing a loop, the detection algorithm checks after each program block if it is still inside the loop. The moment the next program block deviates from the expected one, a loop exit is detected.

Example: Assume the program just finished executed the following sequence of program blocks "ABCABCAD". Here execution of Program Block D marks the end of the loop.

Run Summary

To facilitate hang detection, the execution of a program summarized into a Run Summary. A Run Summary consists of a sequence of Run Blocks, each consisting of one or more Program Blocks. There are two types of Run Blocks:

Loops represent the repeated execution of a sequence of Program Blocks. They are characterized by this repeated sequence and the number of Program Blocks that were executed in this instance.
Transitions are sequences that are not part of loop, nor contain any loops. They are characterized by the sequence of Program Block that were executed.

Example: Assume the following sequence of Program Blocks was executed: "ABCBABCBCBABADBABABAA". This is then summarized into four Run Blocks:

Sequence	Type
ABCBA	Transition
[BC]BCB	Loop
ABAD	Transition
[BA]BABA	Loop
A	?

The trailing "A" is pending classification. It could be the start of either a Transition or a Loop.

Meta-run summaries

More advanced programs can contain nested loops. These can be detected using the same loop detection algorithm, but with different input. Instead of using Program Blocks as input, the meta-loop detection algorithm takes Run Blocks as input and groups these into Meta-Run Blocks.

Example: Assume the following sequence of Program Blocks was executed: "ABCBACACBCBACACACBCBACACACAC". This is then summarized into the following Run Blocks:

Sequence	Type	Identifier
ABCB	Transition	P
[AC]AC	Loop	Q
BCB	Transition	R
[AC]ACAC	Loop	Q
BCB	Transition	R
[AC]ACACAC	Loop	Q

Here each Run Block is given an identifier. Run Blocks that are the same are assigned the same identifier. For loops to be considered the same their repeating sequence must match. The number of loop iterations may differ.

This then results in the following sequence of Run Blocks: "PQRQRQ", which can be summarized into two Meta-Run Blocks:

Sequence	Type	Identifier
P	Transition	X
[QR]QRQ	Loop	Y

So this program is not trapped in a loop at the lowest level. It executes Loop Q repeatedly, but always exits this loop. At a meta-level, however, it may be trapped in Loop Y. This program may hang.

Analyzing loops

To determine if a program is hanging, its loops need to be analyzed more closely. What is the program doing when it executes the loop, and what are the possible ways that the loop can be exited?

Loop types

A key feature of a loop is whether DP moves when the loop executes a single iteration. When DP does not move across loop iterations, it is a Stationary Loop, otherwise it is a Travelling Loop. The next table shows some examples.

	Stationary	Travelling
Minimal loops	`0: INC 1 => -/0`	`0: SHR 1 => -/0`
Larger loops	`0: INC 1 => -/1 1: SHR 1 => -/2 2: INC 2 => -/3 3: SHL 1 => -/0`	`0: INC 1 => -/1 1: SHR 1 => -/2 2: INC 2 => -/3 3: SHL 2 => -/0`

Note that DP can still move in stationary loops. Nevertheless, these loops are easier to analyse than travelling loops. Within a stationary loop, the data cell that a specific Program Block checks in its branch condition remains fixed. In contrast, travelling loops let DP travel across the data tape. This makes it harder to check when/if the loop will exit, as it depends on the values of all data cells that the loop consumes.

Loop exit windows

The first step in determining when/if a loop exits, it determing all possible loop exits. For each Program Block in the loop it is checked if the loop can exit there. Three possible Exit Windows can be distinguished:

Never: the loop can never exit here
Bootstrap: the loop can only exit here while it is bootstrapping
Anytime: the loop can exit here after any number of iterations

Example:

0: INC 1 => -/0

Program Block 0 can exit after any number of iterations. When the loop starts on a data cell with value -x, where x is a positive value, it terminates after x iterations.

Example:

0: INC 1 => -/1
1: DEC 1 => -/0

This loop causes one data cell to oscillate between two values. The loop can exit at both program blocks. However, if this loop exits, it will do so at the first iteration. If it continues, it will loop endlessly. These exits are therefore bootstrap exits.

Example:
Loops can take multiple iterations before they are bootstrapped. The following loop is an example:

0: SHR 5 => -/1
1: SHL 4 => -/0

This is a Travelling Loop, where DP moves one position to the right each loop iteration. Both program blocks exit when their branch condition sees a zero value. The loop can exit at both program blocks. However, once the loop is fully bootstrapped, the loop can only exit at Program Block 0, as this will see new zeroes first. It takes four iterations before the loop is bootstrapped. Until these are completed, the loop can finish at Program Block 1.

Example:
Some Program Blocks can never cause a loop exit.

0: INC 1 => -/1
1: DEC 1 => -/2
2: INC 1 => -/0

Here the last Program Block can never cause the loop to exit. The zero value that cause an exit, would already have caused the loop to exit at Program Block 0 in the same iteration.

Loop exit conditions

Next, it is useful to determine exactly which conditions can cause the loop to exit. At the moment of loop exit, this is either a value equalling zero, or a value not equalling zero. However, it is more useful to determine what can cause this. What is the value before it is being consumed and possibly modified by the loop?

For stationary loops, the exit condition for each Program Block can cover a range of values, but these always refer to the same data cell.

Example - Stationary loop with single exit:
Consider the following simple loop.

0: DEC 3 => -/0

It terminates in the first iteration when D[DP] was 3 when the loop started. Here DP is the value of the Data Pointer on loop entry. The loop terminates in the next iteration when the D[DP] was 6 when the loop started. This can be summarized as follows, where n ≥ 0.

PB#	Window	Condition
0	Anytime	`D[DP] ≥ 3 + 3n`

Example - Stationary loop with multiple exits:

0: INC 1 => -/1
1: INC 2 => -/0

Here the exit conditions are:

PB#	Window	Condition
0	Anytime	`D[DP] ≤ -1 + 3n`
1	Anytime	`D[DP] ≤ -3 + 3n`

Example - Stationary loop with two bootstrap-only exits:

0: SHR 1 => -/1
1: INC 1 => -/2
2: SHL 1 => -/0

Here the exit conditions are:

PB#	Window	Condition
0	Bootstrap	`D[DP+1] = 0`
1	Anytime	`D[DP+1] ≤ -1 + n`
2	Bootstrap	`D[DP] = 0`

For Travelling loops, there is only a single value for each Program Block that can possibly cause an exit. However, this value can be at different positions on the data tape.

Example - Travelling loop with single exit:

0: SHR 1 => -/0

Here the exit condition is, with again n ≥ 0:

PB#	Window	Condition
0	Anytime	`D[DP+1+n] = 0`

Example - Travelling loop with multiple exits:

0: INC 1 => 0/1
1: SHR 1 => -/2
2: INC 1 => -/0

Here the exit conditions are:

PB#	Window	Condition
0	Anytime	`D[DP+1+n] = -2`
1	Anytime	`D[DP+1+n] = 0`
2	Anytime	`D[DP+1+n] = -1`

The "Anytime" conditions are expressed so that they are correct once the loop is fully bootstrapped. As the Program Block 0 is actually the last to consume new data values, it will exits when the loop consumes a -2 value.

Example - Travelling loop with bigger delta:

0: INC 1 => 0/1
1: SHR 1 => -/2
2: DEC 2 => -/3
3: SHR 2 => -/0

Here the exit conditions are:

PB#	Window	Condition
0	Anytime	`D[DP+3n] = -1`
1	Anytime	`D[DP+3n+1] = 0`
2	Anytime	`D[DP+3n+1] = 2`
3	Anytime	`D[DP+3n+3] = 0`