Loop Analysis

Programs that hang are stuck in a loop of one form or another. In more complex hangs, the main loop typically contains several other loops. An important part of hang detection is therefore to analyze these loops 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 => -/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 => -/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`

Analyzing meta-loops

When a loop is detected in the meta-run summary, the program exhibits meta-periodic behavior. To check if this may be a meta-periodic hang, each loops inside the meta-loop is analyzed.

Loop iteration change

First, the execution history is analyzed to see for each loop how its number of iterations changes over time. The following types of behavior are distinguised:

Constant, the number of iterations does not change
Linear increase, the number of iterations increases linearly
Non-linear increase, the number of iterations increases non-linearly. This is only supported for stationary loops.
Irregular, the number of iterations changes irregularly and can even decrease. This is only supported for travelling loops and happens when: the number of iterations decreased (at most once in succession), or the increase is not linear.

Any other behavior is unsupported. An example is when the number of iterations decreased for a stationary loop. There is no need to support this, as this never results in a hang; hang analysis can be aborted immediately.

Loop meta-movement

Second, the execution history is analyzed to see which part of the data tape the loop traverses each time the loop runs. The following types of loops are distinguished:

Meta-stationary, a stationary loop that starts at the same part of the data tape each time it runs.
Glider, a stationary loop that starts at a different location each time the loop runs. It "glides" across the data tape. It typically does this by decreasing one counter, while increasing another counter. It consumes a different counter each time the loop runs.
Anchored sweep, a travelling loop that always starts or ends at the same place.
Double sweep, a travelling loop that extends its end points at both ends of the sweep. Note, it is not necessary that every execution of the loop extends the sweep. It may take multiple iterations of the sweep loop before it extends the sweep.

Glider hangs always contain a Glider loop. Sweep hangs contain at least two sweep loops but possibly more.

Meta-loop types

Based on the classification of each of the loops it contains, the meta-loop execution behavior is classified. Three types are distinguished, ordered from simple to more complex:

Periodic, the iteration change for each loop is constant.
Regular, the iteration change for each loop may also increase linearly. For stationary loops, non-linear increase is also allowed.
Irregular is like Regular except that for travelling loops an irregular iteration change is allowed.

The classification of a meta-loop can vary depending on what is considered the period of the meta-loop. The behavior of the meta-loop can become simpler when increasing the loop period. Two examples are given in Figure 1 and 2.