Natural Loop Discovery Changes

Natural loop is a maximal (in inclusion) set of basic blocks such that it contains a special one (header) that dominates all of them and is backreachable from them. Predecessors of header inside loop are called latches. If there is a single predecessor of header outside the loop, we call it a preheader.

Natural loop discovery code (based on ...) was provided by Michael Hayes (but it was not used in loop optimizer yet); we only had to adapt it for a new loop infrastructure. In following paragraphs we address some issues concerning the change.

As mentioned earlier, our data structure does not support loops with more than one latch basic block. This is not a great problem, as such loops are somewhat nonstandard and we would have to bring them into a canonical shape anyway. Loop with more latches can occur from the following reasons:

• Presence of the inner loop with the shared header. The correct way to eliminate this case is to create a new empty header for the outer loop.

• Several branches inside loop ending in the header; we eliminate this by creating a new empty latch.

It is relatively hard to distinguish these cases (but they are not too common anyway, so it is not too important). If we have profile information, we can differ between them; while in the latter case frequencies of the latch edges are similar, in the former case latch edge of inner loop tends to be much more frequent. Otherwise we simply use the second way.

In addition, we have also provided some functions to bring loops into even more canonical shape (creating preheaders; forcing preheaders/latches to have only a single outgoing edge to the loop header) in that it is much easier to keep the loop structure up to date during transformations like loop copying etc.