A dominator tree can be used to compute natural loops. For every node H in a post-order traversal of the dominator tree (or the original CFG), find all predecessors that are dominated by H. This identifies all back edges. Each back edge T->H identifies a natural loop with H as the header. Perform a flood fill starting from T in the reversed dominator tree (from exiting block to header) All visited nodes reachable from the root belong to the natural loop associated with the back edge. These no...
