3
$\begingroup$

I am trying to understand the process of analyzing a control flow graph and building a tree of loops, both reducible (single entrypoint) and irreducible (multiple entrypoint), using the algorithm described in Nesting of Reducible and Irreducible Loops

Given the following control flow graph:

              ----> 3
             /     ^ \
            /     /   v
      0 -> 1     4 <-> 5
            \     ^   /
             \     \ v
              ----> 2

It seems to me that there are three ways you could define a loop nesting tree:

    • (0, 1)
      • (2, 3)
        • (4, 5)
    • (0, 1)
      • (2)
        • (3, 4, 5)
    • (0, 1)
      • (3)
        • (2, 4, 5)

I initially imagined nesting (1.), but it seems that nestings (2.) and (3.) may be valid as well. However, nestings (2.) and (3.) include an edge that "jumps" straight from the top-level code (at node 1) to the innermost loop (at node 3). Furthermore, taking nesting (2.) as an example, it seems odd to have the second loop have only a single entrypoint node (2), despite clearly being an irreducible loop with two entrypoints from node (1), because one of the entrypoints goes straight into it's inner loop at node (3).

Are all three of these nestings valid loop-trees for the given control flow graph, or only the first one? If they are all valid, is there any reason to prefer one over the others?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.