123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293 |
- .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.
|