compilation - x86 中的基本 block 和控制流

Question

Red-Dragon 书包含第 529 页的算法 9.1 和将汇编代码划分为基本 block 的算法。该算法本质上是:

输入:程序集，作为指令列表。
输出:基本指令 block 列表

第 1 阶段:标记领导者。 (程序的)第一个声明是一个领导者。任何作为分支目标的语句都是领导者。紧跟在分支之后的任何语句都是领导者。

第 2 阶段:组装积木。要创建一个基本 block ，请向该 block 添加一个领导者和所有语句，直到遇到另一个领导者。这样做直到没有语句被留下。

结束并返回 block 。

然后，后来，他们使用这个 block 结构来开发控制流分析。开发的基本结构是一个控制流图；它是通过将基本 block 视为图中的节点并在 Bi 以跳转到 Bj 结束时创建从 block Bi 到 Bj 的有向边来实现的。

Cooper、Harvey 和 Waterman(在从预定代码构建控制流图)指出，如果跳转到内存地址或寄存器中保存的位置，则这种用于创建控制流图的算法是不够的。

这带来了几个问题。程序集何时可以包含指向内存中某个位置的分支？什么是预定码？从 x86 构建控制流图时，还有其他应注意的问题吗？直接从 x86 构建控制流图的最著名算法/实现是什么？

Answer 1

有几种情况下，对寄存器的内容(或变量内容，就此而言)执行分支

1. 开关的跳转表，其中要跳转到的地址是使用一些地址/偏移量表和寄存器的值计算的。
2. 函数指针，例如回调函数，其中要调用的函数作为参数提供给调用者，或存储在某个变量中。
3. C++ 中的虚函数表，其中要调用的函数在编译时未知，并且可能在运行时更改。

这是函数指针调用的示例(64 位 Mac OS):

C 代码

int fptr_call( int (*ptr)(int) ) {
    return (*ptr)( 3 ); 
}

程序集

_fptr_call:
0000000100000e70        pushq   %rbp
0000000100000e71        movq    %rsp, %rbp
0000000100000e74        subq    $0x10, %rsp
0000000100000e78        movl    $0x3, %eax
0000000100000e7d        movq    %rdi, 0xfffffffffffffff8(%rbp)
0000000100000e81        movl    %eax, %edi
; Call based on %rbp, copied from %rdi which is ptr
0000000100000e83        callq   *0xfffffffffffffff8(%rbp) 
0000000100000e86        addq    $0x10, %rsp
0000000100000e8a        popq    %rbp
0000000100000e8b        ret
0000000100000e8c        nopl    (%rax)