7.变量还原（2）寄存器分配与还原

对于编译器来说，变量分配是用最少的寄存器覆盖最多的变量。

在反编译中，这又有所不同

变量分配技术与SSA

熟悉汇编语言的都知道，编译后的二进制的变量最终都体现在寄存器、栈、堆、data段、bss段等的操作上（X86_64体系）。

当然，在这个系类文章中，反汇编器在还原的过程中是看不到寄存器，在这个阶段它的眼里都是SSA了。

那么如何将SSA中提取出实际的可读的变量，就是变量还原的算法的工作。

变量还原算法在不同的反编译器中实现方法不一样，总得来说有这么几种关联方式：

1. 在SSA翻译后插入phi语句的同时，将phi语句关联的变量进行关联。

2. 如果存在栈，那么可以直接分割栈结构标记并还原变量；即，函数栈可以看成一个巨大的结构体，对于栈变量的还原就是对结构体的偏移分割。

3. 在中间语句优化完成后，依照关联关系尝试进一步进行优化，整理出实际的变量。

编译器的寄存器分配

要知道反编译器的寄存器还原技术，需要先对编译器的寄存器分配算法有一定的了解。

寄存器分配算法的基本规则与目标：

1. 变量的数量可以是”无限“的，但CPU 寄存器的数量是有限

2. 尽量让变量的值或计算结果保留在寄存器中

（寄存器分配算法本身是个NP困难问题）

让我用一个教科书上的例子

https://pages.cs.wisc.edu/~horwitz/CS701-NOTES/5.REGISTER-ALLOCATION.html

int main()
{   
    int b;
    int a = getchar();
    int x = getchar();
    if (x > 0) {
        if (a > 0) {
            x = 10;
        } else {
            x = 20;
        }
    } else {
        a = 100;
        b = getchar();
        x = a * b;
        while (x > a + b) {
            x = x / 2;
        }
    }
    printf("%d", x);
    
    return 0;
}

画出上面代码的CFG图

计算变量的存活范围

Def of a at node (1), {1, 2, 3, 4}
Def of x at node (2), {2, 3}
Def of x at node (5), {5, 7}
Def of x at node (6), {6, 7}
Def of a at node (8), {8, 9, 10, 11, 12}
Def of b at node (9), {9, 10, 11, 12}
Def of x at node (10), {7, 10, 11, 12}
Def of x at node (12), {7, 11, 12}

最终结果为
( <a>, {1, 2, 3, 4} )
( <x>, {2, 3} )
( <x>, {5, 6, 7, 10, 11, 12} )
( <a>, {8, 9, 10, 11, 12} )
( <b>, {9, 10, 11, 12} )

即如下图所示

使用图着色算法，进行着色后就变成了下面这个样子，更加直观了

Live Range               Color (register)
======================== ================
x {5, 6, 7, 10, 11, 12}       R1
b {9, 10, 11, 12}             R2
a {8, 9, 10, 11, 12}          -- no color --
x {2, 3}                      R1
a {1, 2, 3, 4}		      R2

最终分配好寄存器

read(R2);
read(R1);
if (R1 > 0) {
    if (R2 > 0) R1 = 10;
    else (R1 = 20);
}
else {
    a = 100;
    read(R2);
    R1 = a * R2;
    while (R1 > A + R2) {
        R1 = R1 / 2;
    }
}
print(R1