跳至主要內容

中间代码生成 (IR Generation)

西风逍遥游大约 5 分钟

中间代码生成 (IR Generation)

中间代码生成是编译器前端的重要阶段,表示我们已经完成了语法检查和语义检查,我们内存中已经获取到了完整的代码结构信息,接下来我们可以将代码转换为内部的标准形式,这样就可以方便我们接下来进行优化、转换,或者使用虚拟机执行等操作。

三地址码

三地址码是一种非常简单的中间代码形式,它的每条指令最多只有三个操作数,这样的指令非常容易转换为汇编代码,也非常容易进行优化。

例如,对于以下C语言代码:

a = b * -c + b * -c;

它会被转换为如下的三地址码:

t1 = -c
t2 = b * t1
t3 = -c
t4 = b * t3
t5 = t2 + t4
a = t5

在这个例子中:

  1. 每条指令最多包含一个运算符
  2. 使用临时变量(t1, t2等)来存储中间结果
  3. 指令格式通常为:结果 = 操作数1 运算符 操作数2
  4. 这种形式便于后续的代码优化和目标代码生成

字节码表示

字节码表示也是另一种常见的中间代码,它的特点是不使用寄存器,而是一个抽象的栈来表示计算,使用Push,Pop将变量进行移动到栈顶,计算后的结果也是处于栈顶。这种表示法的操作表示特别小,往往能做到一个Byte内表示,所以又叫字节码。典型代表如Java语言的字节码就是这种表示方法。

例如,对于同样的C语言代码:

a = b * -c + b * -c;

它会被转换为如下的字节码指令序列:

push c        // 将c压入栈
neg          // 取负
push b       // 将b压入栈
mul          // 栈顶两个数相乘
push c       // 将c压入栈
neg          // 取负
push b       // 将b压入栈
mul          // 栈顶两个数相乘
add          // 栈顶两个数相加
pop a        // 将结果存入a

在这个例子中:

  1. 所有操作都是基于栈的
  2. 每个操作码(如push、neg、mul等)通常只需要一个字节表示
  3. 操作数(如变量名)作为操作码的参数
  4. 计算过程完全通过栈操作完成,不需要显式的临时变量

三地址码与字节码的相互转换

其实三地址码与字节码的相互转换是非常容易的,只需要模拟一个栈的运行,就可以轻松的将三地址码转换为字节码。

三地址码转字节码

转换算法如下:

  1. 维护一个变量到栈位置的映射表(用于记录变量在栈中的位置)
  2. 对于每个三地址码指令:
    • 如果是赋值操作 x = y
      push y
      pop x
      
    • 如果是二元运算 x = y op z
      push y
      push z
      op    // 对应的操作码(add/mul/sub/div等)
      pop x
      
    • 如果是一元运算 x = op y
      push y
      op    // 对应的操作码(neg/not等)
      pop x
      

字节码转三地址码

转换算法如下:

  1. 维护一个栈,用于模拟字节码的执行
  2. 维护一个临时变量计数器
  3. 对于每个字节码指令:
    • 如果是 push x
      • 将x压入栈
    • 如果是 pop x
      • 将栈顶元素弹出并赋值给x
    • 如果是二元操作(如add/mul等):
      • 弹出栈顶两个元素
      • 生成新的临时变量
      • 生成三地址码:临时变量 = 操作数1 运算符 操作数2
      • 将结果压入栈
    • 如果是一元操作(如neg/not等):
      • 弹出栈顶元素
      • 生成新的临时变量
      • 生成三地址码:临时变量 = 运算符 操作数
      • 将结果压入栈

栈顶缓存技术

早期的栈式虚拟机,每次push、pop操作都需要从内存中读取数据,这样会导致性能下降。 试想,如果执行一个简单的加法操作: push x // 内存拷贝 push y // 内存拷贝 add // 栈顶两个数相加,结果压回栈

如果每次都从内存中读取数据,这样就会导致性能下降。栈顶缓存技术(Top of Stack Caching)是一种优化技术,用于提高字节码执行的效率。它通过将栈顶的值缓存到寄存器中(或高速缓存中),从而减少栈操作的次数,提高执行速度。

例如对于一段java代码: int result = a + b * c;

步骤Java字节码不使用栈顶缓存使用栈顶缓存说明
1iload_1读 b,压到栈顶 (读写)r0 = load(local[1])读取b (读)
2iload_2读 c,压到栈顶 (读写)r1 = load(local[2])读取c (读)
3imul弹出b和c,相乘,压回栈 (读2写1)r0 = r0 * r1计算b*c
4iload_0读 a,压到栈顶 (读写)r1 = load(local[0])读取a (读)
5iadd弹出a和(b*c),相加,压回栈 (读2写1)r0 = r0 + r1计算a+(b*c)
6istore_3从栈顶弹出结果,写到局部变量表 (读写)store(local[3], r0)存储结果 (写)

从表格中可以看出:

  1. 每个Java字节码指令都有对应的栈操作和寄存器操作
  2. 不使用栈顶缓存时,每个操作都需要多次内存读写
  3. 使用栈顶缓存后,大部分操作都在寄存器中完成
  4. 使用栈顶缓存显著减少了内存访问次数,提高了执行效率