1

基本块定义为以跳转(直接或间接)指令结尾的(非跳转)指令序列。跳转目标地址应该是另一个基本块的开始。考虑我有以下汇编代码:

106ac:       ba00000f        blt     106f0 <main+0xb8>
106b0:       e3099410        movw    r9, #37904      ; 0x9410
106b4:       e3409001        movt    r9, #1
106b8:       e79f9009        ldr     r9, [pc, r9]
106bc:       e3a06000        mov     r6, #0
106c0:       e1a0a008        mov     sl, r8
106c4:       e30993fc        movw    r9, #37884      ; 0x93fc
106c8:       e3409001        movt    r9, #1
106cc:       e79f9009        ldr     r9, [pc, r9]
106d0:       e5894000        str     r4, [r9]
106d4:       e7941105        ldr     r1, [r4, r5, lsl #2]
106d8:       e1a00007        mov     r0, r7
106dc:       e12fff31        blx     r1
106e0:       e0806006        add     r6, r0, r6
106e4:       e25aa001        subs    sl, sl, #1
106e8:       e287700d        add     r7, r7, #13
106ec:       1afffff4        bne     106c4 <main+0x8c>
106f0:       e30993d0        movw    r9, #37840      ; 0x93d0
106f4:       e3409001        movt    r9, #1

bb1

106a4:       ...
106ac:       ba00000f        blt     106f0 <main+0xb8>

第一个基本块 bb1 有一个目标地址,它是 bb4 的开始。

bb2

106b0:       e3099410        movw    r9, #37904      ; 0x9410
....        All other instructions
106c4:       e30993fc        movw    r9, #37884      ; 0x93fc
....        All other instructions
106d8:       e1a00007        mov     r0, r7
106dc:       e12fff31        blx     r1

第二个基本块 bb2 有一个间接分支,因此目标地址仅在运行时才知道。

bb3

106e0:       e0806006        add     r6, r0, r6
106e4:       e25aa001        subs    sl, sl, #1
106e8:       e287700d        add     r7, r7, #13
106ec:       1afffff4        bne     106c4 <main+0x8c>

第三个基本块有一个目标地址,它不是另一个基本块的开始,而是在 bb2 的中间。根据基本块的定义,这是不可能的。但是,在实践中,我在多个地方看到了这种行为(在基本块的中间跳跃)。如何解释这种行为?是否可以强制编译器(LLVM)生成除了基本块开头之外不会跳转到其他任何地方的代码?

bb4

106f0:       e30993d0        movw    r9, #37840      ; 0x93d0
106f4:       e3409001        movt    r9, #1
....
Ends with a branch (direct or indirect)

我正在使用工具(SPEDI)生成基本块,使用的编译器是 LLVM(CLANG 前端),目标架构是 ARM V7 Cortex-A9。

4

2 回答 2

3

基本块是控制流图中的节点,这意味着一旦控制进入块,除了运行整个块并退出它之外,它不能做任何其他事情。这并不意味着它们必须以跳转指令开始或结束。为了更好地理解,请参阅维基百科的摘录:

由于其构造过程,在 CFG 中,每条边 A→B 都具有以下性质:

出度(A) > 1 或入度(B) > 1(或两者兼有)。

因此,至少在概念上,CFG 可以通过从程序的(完整)流图(即每个节点代表一条单独指令的图)开始,并对每条伪造上述谓词的边执行边收缩,即收缩其源有一个出口且目的地有一个入口的每条边。

根据这个定义,我会以不同的方式分析 106b0 和 106ec 之间的代码:一个块 B1 从 106b0 到 106c0,一个块 B2 从 106c4 到 106ec。这段代码是一个循环,B1 是循环的设置部分,B2 是主体。

在 ARMbl中,例如 106dc 处的指令是函数调用,这意味着控制权将传递给被调用的函数,然后在bl. 因此,如果我们只为调用函数构建 CFG,我不会将此指令视为块边界。如果我们正在为整个程序进行 CFG,那么这里应该有一条朝向被调用函数的边,然后从被调用函数返回到下一条指令的另一条边。

于 2018-04-02T14:55:46.040 回答
0

正如塞缪尔的回答所解释的那样,基本块不包含分支目标。指令块的分支目标也是基本块之间的边界。

您正在使用编译器生成此代码,因此请使用clang -O3 -S foo.c分支目标上的标签获取编译器的 asm 输出。

一直编译到目标文件然后反汇编这意味着您需要一个反汇编程序将标签放回它在反汇编时找到的所有分支的目标上。 Agner Fog 的 x86 反汇编程序就是objconv这样做的。也许 ARM 也有类似的东西,但我认为 GNU binutils 没有这样objdump -d的选择。

我没有安装 ARM clang,但输出可能与 x86 非常相似。例如,一个非常简单的函数将使用分支进行编译:

int sa, sb;
void foo(int a, int b) {
    if (a>b) {
        sb = b;
    }
    sa = a;
}

在 Godbolt 编译器资源管理器上clang5.0 -O3为 x86编译,带有. (Godbolt 安装了 ARM-gcc,但没有安装 ARM-clang)

foo(int, int):                               # @foo(int, int)
        cmp     edi, esi
        jle     .LBB0_2
        mov     dword ptr [rip + sb], esi
.LBB0_2:
        mov     dword ptr [rip + sa], edi
        ret

这里有 3 个基本块:cmp/jle、第一个mov和第二个mov+ ret。第二个块没有标签,因为它在条件分支失败之后开始。

.LBB0_2标签名称是自动生成的。这.L意味着它是一个“本地”标签(目标文件的符号表中没有符号;仅在组装此文件时供内部使用)。 代表基本块BB 我认为BB0_2这意味着它是第一个函数中的基本块 #2(从 0 开始计数)。(复制具有不同名称的函数会给我们一个.LBB1_2标签。)在一个函数中,不同的标签有不同的最后一个数字。


Clang 甚至在注释中标记了所有基本块:

在 Godbolt 上,单击//按钮以禁用隐藏注释行。然后你得到:

foo(int, int):                               # @foo(int, int)
# BB#0:
        #DEBUG_VALUE: foo:a <- %EDI
        #DEBUG_VALUE: foo:b <- %ESI
        cmp     edi, esi
        jle     .LBB0_2
# BB#1:
        #DEBUG_VALUE: foo:b <- %ESI
        #DEBUG_VALUE: foo:a <- %EDI
        mov     dword ptr [rip + sb], esi
.LBB0_2:
        #DEBUG_VALUE: foo:b <- %ESI
        #DEBUG_VALUE: foo:a <- %EDI
        mov     dword ptr [rip + sa], edi
        ret

即不是分支目标的基本块得到一个注释来对它们进行定界+编号,而不是.L本地标签。它还显示了在进入 BB 时哪些 C 变量位于哪些寄存器中。

于 2018-04-05T21:30:59.710 回答