Uninformed: Informative Information for the Uninformed

Vol 1» 2005.May


Problems with Natural Loop Detection

There is a very big problem with natural loops. The problem is with the natural loop definition which is ``a single entry point whose header dominates all the nodes in the loop''. Natural loop detection does not deal with irreducible loops, as defined previously. This problem can be demonstrated in Figure 2 [*]

Figure 2: An example of an irreducible loop

As the reader can see both B and D are entry points into C. Also neither D nor B dominates C. This throws a huge wrench into the algorithm and makes it only able to pick up loops that fall under the specification of a natural loop or reducible loop3.5.