Decompilation independent pattern structuring of cfg

Question

I'm trying to learn on how to structure high level language flow structures and stumbled uppon an academic paper presenting a new way to structure a cfg without gotos.

I'm in a bit of a struggle understanding something fundamental as to how to even identify regions in the current procedure cfg. What I mean by this is given the example R1, R2, R3 regions in the paper:

identifying the R1 loop is easy with finding a back-edge node (c3) to the header (c1) but then how do you identify all blocks related to the loop?
If we just iterate the predecessors of the tail block (c3) then you'll miss on certain blocks for example n2 or n1.

Taking R2 as an example, how would you identify an acyclic region it?
I can assume one can check for a node (n7) with 2 predecessors (n5, n6) that are dominated by the same node (b1) and then going from the tail (n7) back to the header (b1) and collecting all the predecessors into the region, but I'm not sure if this will cover all edge cases.

I'm not sure what would be the way to identify all blocks related to a region reliably or how to even identify what is a region?

My assumption right now is that every node that id dominated by a header of a cyclic region must be inside the region. I traverse the graph using DFS post-order so I could find the region R3 and then later even tho b1 dominates every node in region R3 I can isolate the region R1 since I've already created the region R1.

My problem with that approach is that if I assume a cyclic region consist of every node the header dominates I can't find sub cyclic regions, for example the sub cyclic region (c1, n1) if I find nodes for that region by the method I described the sub cyclic region will have all nodes of the bigger region R1 as-well so it's not good enough.

I have another approach to find cyclic region nodes:

def build_cyclic_region(procedure: Procedure, header: BasicBlock, tail: BasicBlock):
    loop = Region(header)
    work_list = set()

    if header != tail:
        loop.blocks.add(tail)
        work_list.add(tail)

    # dfs_post_order(set(), procedure.cfg, header.address, lambda block_addr: analyzer.basic_blocks[block_addr].dominators[header.id] and loop.blocks.add(analyzer.basic_blocks[block_addr]))

    while len(work_list):
        block: BasicBlock = work_list.pop()

        for pred in block.predecessor:
            if pred not in loop.blocks:
                loop.blocks.add(pred)
                work_list.add(pred)

        for succ in block.successor:
            if succ not in loop.blocks and succ.dominators[loop.header.id]:
                loop.blocks.add(succ)
                work_list.add(succ)

    return loop

With this approach I try to visit all predecessors from the tail as-well as successors as long as it is still dominated by the header, problem is I still have misses, with this algorithm I miss nodes like n1 since I don't visit already visited nodes which one of them is the header and so I can't include n1 in my region.

EDIT: I decided to take a look at llvm's approach of identifying a region but I still find it not to adhere the traditional definition of a region where a region header dominates all nodes including the exit node.

The gist of their algorithm is:

• iterate the dominance tree in post order manner
• for each node get the post dominance node and use the nodes as an entry-exit pair
• test that the pair is a region based on the isRegion method

Now where it falls apart for me is if we test this algorithm, say we're now have node n2 as an entry node and then we find the next post dominance node which is n9 we have these 2 nodes as an entry-exit pair for the isRegion test.
The test will return true on the very first check:

  using DST = typename DomFrontierT::DomSetType;
 
  DST *entrySuccs = &DF->find(entry)->second;
 
  // Exit is the header of a loop that contains the entry. In this case,
  // the dominance frontier must only contain the exit.
  if (!DT->dominates(entry, exit)) {
    for (BlockT *successor : *entrySuccs) {
      if (successor != exit && successor != entry)
        return false;
    }
 
    return true;
  }

since n2 doesn't dominate n9 it will enter the if statement, and then it'll iterate n2's dominance frontier which is the set {n9}, it will then proceed to check if each node in the set is not equal either to the entry node or to the exit node and if so return false (since if it doesn't equal it means it's a node inside the region in my understanding, so it's not a pair that makes up a region entry exit). and if no such node is found it returns true, but for the n2 n9 entry-exit pair example we can see that it'll return true and thus labeling this pair as a region which doesn't sit well with my understanding of the definition of a region so I'm a bit confused and looking for clarification on what am I missing from my understanding.

I also drew my self the dominance tree of the graph for convenience and I'm wondering why can I just take slices from the root successors which is the entry point and make each slice as a region since it looks like it lines up nicely, obviously its not proof that it will always work but looking at the dominance tree makes alot more sense that all the shenanigans of llvm's isRegion code