控制流程图：正确识别循环“条件”

Question

我有这个 C# 代码示例（但语言绝对不重要）：

 public static void NestedSimple(int[] a, int n)
    {
        for(int i = 0; i < n && i < 12; i++)
        {
            a[i] += 1;
        }
    }

编译后，我得到这个 IL :

IL_0000: nop
    IL_0001: ldc.i4.0
    IL_0002: stloc.0
    IL_0003: br.s IL_0017
    // loop start (head: IL_0017)
        IL_0005: nop
        IL_0006: ldarg.0
        IL_0007: ldloc.0
        IL_0008: ldelema [mscorlib]System.Int32
        IL_000d: dup
        IL_000e: ldind.i4
        IL_000f: ldc.i4.1
        IL_0010: add
        IL_0011: stind.i4
        IL_0012: nop
        IL_0013: ldloc.0
        IL_0014: ldc.i4.1
        IL_0015: add
        IL_0016: stloc.0

        IL_0017: ldloc.0
        IL_0018: ldarg.1
        IL_0019: bge.s IL_0022

        IL_001b: ldloc.0
        IL_001c: ldc.i4.s 12
        IL_001e: clt
        IL_0020: br.s IL_0023

        IL_0022: ldc.i4.0

        IL_0023: stloc.1
        IL_0024: ldloc.1
        IL_0025: brtrue.s IL_0005
    // end loop

    IL_0027: ret

可以用这个控制流图来表示（从 IL 重建，基本块被正确识别，并且由 Lengauer-Tarjan 计算支配关系）：

后沿是 IL_0005 -> IL_0017，因为 IL_0005 支配 IL_0017，这意味着循环头是 IL_0017。

如何识别 IL_0017 和 IL_0023 之间的每个块属于循环退出条件而不是普通体？

我的直觉是 IL_0005 是实际的主体，通往 IL_0005 的唯一边缘从 IL_0023 开始，这意味着 IL_0017 和 IL_0023 之间的所有块都是条件的一部分。

但是 -> 它不依赖于理论，而是依赖于 C# -> MSIL 编译器行为。

我可以实施一些可靠的东西吗？

到目前为止，我的代码看起来像：

// if back edge (n->d where d dominates n) then we have a loop
            if ((block.JumpTarget != null && block.JumpTarget.Dominates(block)) ||
                (block.Next != null && block.Next.Dominates(block)))
            {
                var header = block.JumpTarget != null ? block.JumpTarget : block.Next;
                var tail = block;
                var visited = new HashSet<BasicBlock> { header, tail};
                var stack = new Stack<BasicBlock>();
                
                // populate body
                stack.Push(block);
                while (stack.Any())
                {
                    var n = stack.Pop();
                    if(!visited.Contains(n))
                    {
                        visited.Add(n);
                        foreach(var p in n.Predecessors)
                        {
                            stack.Push(p);
                        }
                    }
                }
                var body = visited.OrderBy(b => b.Id).ToList();
           /// HERE : how can I identify loop condition ??

Answer 1

我不知道这是否能回答你的问题，但可以像下面这样展开循环（实际上“提取”布尔条件）

   IL_000
    |
   IL_0017
    |     \
   IL_001b  IL_0022
    |      /
 - IL_0023 ----------.
'   |                |
|  IL_0005           |
|   |                |
|  IL_0017           |
|   |     \          |
|  IL_001b  IL_0022  |
'  /       /         |
 \--------/          |
                     |
                    IL_0027

您会看到

(i < n && i <12)

被编码在

17

、

1b

、

22

和

if

中，由

23

块编码，成为循环的头部。

我的推理是

while

循环由下图编码

我不知道只有基本块的算法，反编译器通常会“简化”它们：在你的情况下，我提取的所有块都可以折叠成单个语句并合并到

IL_0023

。