doc/ego/cf/cf4

   1 .NH 2
   2 Loop detection
   3 .PP
   4 Loops are detected by using the loop construction
   5 algorithm of.
   6 .[~[
   7 aho compiler design
   8 .], section 13.1.]
   9 This algorithm uses \fIback edges\fR.
  10 A back edge is an edge from B to C in the CFG,
  11 whose head (C) dominates its tail (B).
  12 The loop associated with this back edge
  13 consists of C plus all nodes in the CFG
  14 that can reach B without going through C.
  15 .PP
  16 As an example of how the algorithm works,
  17 consider the piece of program of Fig. 4.1.
  18 First just look at the program and try to
  19 see what part of the code constitutes the loop.
  20 .DS
  21 loop
  22    if cond then                       1
  23       -- lots of simple
  24       -- assignment
  25       -- statements              2          3
  26       exit; -- exit loop
  27    else
  28       S; -- one statement
  29    end if;
  30 end loop;
  31
  32 Fig. 4.1 A misleading loop
  33 .DE
  34 Although a human being may be easily deceived
  35 by the brackets "loop" and "end loop",
  36 the loop detection algorithm will correctly
  37 reply that only the test for "cond" and
  38 the single statement in the false-part
  39 of the if statement are part of the loop!
  40 The statements in the true-part only get
  41 executed once, so there really is no reason at all
  42 to say they're part of the loop too.
  43 The CFG contains one back edge, "3->1".
  44 As node 3 cannot be reached from node 2,
  45 the latter node is not part of the loop.
  46 .PP
  47 A source of problems with the algorithm is the fact
  48 that different back edges may result in
  49 the same loop.
  50 Such an ill-structured loop is
  51 called a \fImessy\fR loop.
  52 After a loop has been constructed, it is checked
  53 if it is really a new loop.
  54 .PP
  55 Loops can partly overlap, without one being nested
  56 inside the other.
  57 This is the case in the program of Fig. 4.2.
  58 .DS
  59 1:                              1
  60    S1;
  61 2:
  62    S2;                          2
  63    if cond then
  64       goto 4;
  65    S3;                     3         4
  66    goto 1;
  67 4:
  68    S4;
  69    goto 1;
  70
  71 Fig. 4.2 Partly overlapping loops
  72 .DE
  73 There are two back edges "3->1" and "4->1",
  74 resulting in the loops {1,2,3} and {1,2,4}.
  75 With every basic block we associate a set of
  76 all loops it is part of.
  77 It is not sufficient just to record its
  78 most enclosing loop.
  79 .PP
  80 After all loops of a procedure are detected, we determine
  81 the nesting level of every loop.
  82 Finally, we find all strong and firm blocks of the loop.
  83 If the loop has only one back edge (i.e. it is not messy),
  84 the set of firm blocks consists of the
  85 head of this back edge and its dominators
  86 in the loop (including the loop entry block).
  87 A firm block is also strong if it is not a
  88 successor of a block that may exit the loop;
  89 a block may exit a loop if it has an (immediate) successor
  90 that is not part of the loop.
  91 For messy loops we do not determine the strong
  92 and firm blocks. These loops are expected
  93 to occur very rarely.