This page classifies 2LBB programs that are trapped in a hang cycle where the Program Pointer (PP) traverses the same path each time. These hangs are called Periodic as each cycle requires the same amount of execution steps.
There are different types of Periodic Hangs. They can be classified considering the following three features.
First, does the data change while the program is in the periodic loop? Three types can be distinguished:
Second, how often is each instruction visited within each loop? Two types can be distinguished:
Third, does the data pointer (DP) move? Three types can be distinguished:
Awareness of these features is required to be able to reliably detect all periodic hangs. If, for example, the detection algorithm assumes that each instruction is executed once every cycle, it will not detect Non-Uniform Periodic Hangs. The algorithm should also not assume that each cycle the same values are changed, as it will then not be able to detect Travelling Periodic Hangs.
Periodic hangs can become quite complex. Figure 7 shows a fairly complex Periodic Hang on a 5×5 grid. Figure 8 shows an even more complex Periodic Hang on a 6×6 grid. It takes 410 steps before the program enters the periodic loop. The hang period is 82 steps. It generates the following data sequence: ... -2 4 2 -2 4 2 -1 3 2 -2 3 1 -1 3 2 0. Every period it extends the sequence with three cells. Inside the periodic loop DP visits the last nine values, leaving -2 4 2 in its wake.
My search program is able to detect all the hangs shown on this page.