cfg 的反编译独立模式结构

问：

我正在尝试学习如何构建高级语言流结构，并偶然发现了一篇学术论文，该论文提出了一种在没有 s 的情况下构建 cfg 的新方法。goto

我有点难以理解一些基本的东西，即如何在当前过程中识别区域 cfg。 我的意思是在论文中给出了 R1、R2、R3 区域的示例：

通过找到标头 （c1） 的后缘节点 （c3） 很容易识别 R1 环路，但如何识别与环路相关的所有块？
如果我们只是迭代尾部块 （c3） 的前身，那么您将错过某些块，例如 n2 或 n1。

以 R2 为例，您将如何识别非环状区域？
我可以假设可以检查一个节点 （n7），其中包含 2 个由同一节点 （b1） 主导的前身（n5、n6），然后从尾部 （n7） 回到头 （b1） 并将所有前身收集到该区域，但我不确定这是否涵盖所有边缘情况。

我不确定有什么方法可以可靠地识别与区域相关的所有块，或者如何识别什么是区域？

我现在的假设是，由循环区域的标头主导的每个节点都必须在该区域内。我使用 DFS 后顺序遍历图形，这样我就可以找到区域 R3，然后即使 b1 在区域 R3 中占主导地位，我也可以隔离区域 R1，因为我已经创建了区域 R1。

这种方法的问题是，如果我假设一个循环区域由标头占主导地位的每个节点组成，我找不到子循环区域，例如子循环区域（c1，n1），如果我通过我描述的方法找到该区域的节点，子循环区域将具有较大区域 R1 的所有节点，所以它不够好。

我有另一种方法来查找循环区域节点：

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

使用这种方法，我尝试从尾部访问所有前辈以及后继者，只要它仍然由标头主导，问题是我仍然有未命中，使用此算法，我错过了像 n1 这样的节点，因为我不访问已经访问过的节点，其中一个是标头，所以我不能在我的区域中包含 n1。

编辑：我决定看看 llvm 识别区域的方法 但我仍然发现它不遵守区域的传统定义，其中区域标头主导所有节点，包括出口节点。

其算法的要点是：

• 以后顺序方式迭代优势树
• 对于每个节点，获取后优势节点，并将节点用作进入-退出对
• 根据方法测试该对是否为区域isRegion

现在对我来说，它分崩离析的地方是，如果我们测试这个算法，假设我们现在有节点作为入口节点，然后我们找到下一个后优势节点，即我们有这两个节点作为测试的入口-出口对。
该测试将在第一次检查时返回 true：n2n9isRegion

  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;
  }

由于 doesn't dominant 它将输入 if 语句，然后它将迭代 的 dominance 边界，即集合，然后它将继续检查集合中的每个节点是否不等于入口节点或出口节点，如果是，则返回 false（因为如果它不等于，则表示它是区域内的一个节点，在我的理解中， 所以它不是构成区域入口出口的一对）。 如果没有找到这样的节点，它将返回 true，但是对于进入-退出对示例，我们可以看到它将返回 true，从而将此对标记为一个区域，这与我对区域定义的理解不太吻合，所以我有点困惑并寻求澄清我的理解中缺少什么。n2n9n2{n9}n2n9

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 code isRegion