cf4 2.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293
  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. Fig. 4.1 A misleading loop
  32. .DE
  33. Although a human being may be easily deceived
  34. by the brackets "loop" and "end loop",
  35. the loop detection algorithm will correctly
  36. reply that only the test for "cond" and
  37. the single statement in the false-part
  38. of the if statement are part of the loop!
  39. The statements in the true-part only get
  40. executed once, so there really is no reason at all
  41. to say they're part of the loop too.
  42. The CFG contains one back edge, "3->1".
  43. As node 3 cannot be reached from node 2,
  44. the latter node is not part of the loop.
  45. .PP
  46. A source of problems with the algorithm is the fact
  47. that different back edges may result in
  48. the same loop.
  49. Such an ill-structured loop is
  50. called a \fImessy\fR loop.
  51. After a loop has been constructed, it is checked
  52. if it is really a new loop.
  53. .PP
  54. Loops can partly overlap, without one being nested
  55. inside the other.
  56. This is the case in the program of Fig. 4.2.
  57. .DS
  58. 1: 1
  59. S1;
  60. 2:
  61. S2; 2
  62. if cond then
  63. goto 4;
  64. S3; 3 4
  65. goto 1;
  66. 4:
  67. S4;
  68. goto 1;
  69. Fig. 4.2 Partly overlapping loops
  70. .DE
  71. There are two back edges "3->1" and "4->1",
  72. resulting in the loops {1,2,3} and {1,2,4}.
  73. With every basic block we associate a set of
  74. all loops it is part of.
  75. It is not sufficient just to record its
  76. most enclosing loop.
  77. .PP
  78. After all loops of a procedure are detected, we determine
  79. the nesting level of every loop.
  80. Finally, we find all strong and firm blocks of the loop.
  81. If the loop has only one back edge (i.e. it is not messy),
  82. the set of firm blocks consists of the
  83. head of this back edge and its dominators
  84. in the loop (including the loop entry block).
  85. A firm block is also strong if it is not a
  86. successor of a block that may exit the loop;
  87. a block may exit a loop if it has an (immediate) successor
  88. that is not part of the loop.
  89. For messy loops we do not determine the strong
  90. and firm blocks. These loops are expected
  91. to occur very rarely.