.NH 2 Loop detection .PP Loops are detected by using the loop construction algorithm of. .[~[ aho compiler design .], section 13.1.] This algorithm uses \fIback edges\fR. A back edge is an edge from B to C in the CFG, whose head (C) dominates its tail (B). The loop associated with this back edge consists of C plus all nodes in the CFG that can reach B without going through C. .PP As an example of how the algorithm works, consider the piece of program of Fig. 4.1. First just look at the program and try to see what part of the code constitutes the loop. .DS loop if cond then 1 -- lots of simple -- assignment -- statements 2 3 exit; -- exit loop else S; -- one statement end if; end loop; Fig. 4.1 A misleading loop .DE Although a human being may be easily deceived by the brackets "loop" and "end loop", the loop detection algorithm will correctly reply that only the test for "cond" and the single statement in the false-part of the if statement are part of the loop! The statements in the true-part only get executed once, so there really is no reason at all to say they're part of the loop too. The CFG contains one back edge, "3->1". As node 3 cannot be reached from node 2, the latter node is not part of the loop. .PP A source of problems with the algorithm is the fact that different back edges may result in the same loop. Such an ill-structured loop is called a \fImessy\fR loop. After a loop has been constructed, it is checked if it is really a new loop. .PP Loops can partly overlap, without one being nested inside the other. This is the case in the program of Fig. 4.2. .DS 1: 1 S1; 2: S2; 2 if cond then goto 4; S3; 3 4 goto 1; 4: S4; goto 1; Fig. 4.2 Partly overlapping loops .DE There are two back edges "3->1" and "4->1", resulting in the loops {1,2,3} and {1,2,4}. With every basic block we associate a set of all loops it is part of. It is not sufficient just to record its most enclosing loop. .PP After all loops of a procedure are detected, we determine the nesting level of every loop. Finally, we find all strong and firm blocks of the loop. If the loop has only one back edge (i.e. it is not messy), the set of firm blocks consists of the head of this back edge and its dominators in the loop (including the loop entry block). A firm block is also strong if it is not a successor of a block that may exit the loop; a block may exit a loop if it has an (immediate) successor that is not part of the loop. For messy loops we do not determine the strong and firm blocks. These loops are expected to occur very rarely.