在编译器中优化代码后摆脱时间变量

Question

我正在按照经典书籍 Compilers 的说明创建一个编译器静态分析模块。 Ullman 等人的原则、技术和工具。

我将 AST 表示转换为三地址代码表示进行优化（现在基本上是死代码消除和复制传播），然后我转换为类似的三地址代码表示（更适合转换为字节码）。

为此，我必须创建时间变量，以便我的代码表示如下所示：

t = IntLit(0)
t1 = left < right
t2 = !t1
cjump if t2 to L0:
t3 = number[right]
v = t3
t4 = left - IntLit(1)
i = t4
j = right
cont01 = True()
L2:
t5 = !cont01
cjump if t5 to L3:
cont02 = True()
L4:
t6 = !cont02
cjump if t6 to L5:
t7 = i + IntLit(1)
i = t7
t8 = number[t7]
Removed dead code: aux03 = t8
t10 = t8 < v
t9 = !t10
t11 = !t9
cjump if t11 to L6:
cont02 = False()
jump L7:
L6:
cont02 = True()
L7:
jump L4:
L5:
cont02 = True()
L8:
t12 = !cont02
cjump if t12 to L9:
t13 = j - IntLit(1)
j = t13
t14 = number[t13]
Removed dead code: aux03 = t14
t16 = v < t14
t15 = !t16
t17 = !t15
cjump if t17 to L10:
cont02 = False()
jump L11:
L10:
cont02 = True()
L11:
jump L8:
L9:
t18 = number[i]
t = t18
t19 = number[j]
number[i] = t19
number[j] = t18
t21 = i + IntLit(1)
t20 = j < t21
t22 = !t20
cjump if t22 to L12:
cont01 = False()
jump L13:
L12:
cont01 = True()
L13:
jump L2:
L3:
t23 = number[i]
number[j] = t23
t24 = number[right]
number[i] = t24
number[right] = t
t25 = i - IntLit(1)
t26 = This().Sort(left,t25)
Removed dead code: nt = t26
t27 = i + IntLit(1)
t28 = This().Sort(t27,right)
Removed dead code: nt = t28
jump L1:
L0:
Removed dead code: nt = IntLit(0)
L1:
return IntLit(0)

我想摆脱代码生成的时间变量，但我看起来做不到。考虑以下方法：

  def printing() : Int = {
    var i : Int;
    var j : Int;
    var z : Int;

    i = this.printing1();
    z = i;
    println(z);

    return i;
  }

我得到以下代码：

t1 = This().printing1()
Removed dead code: i = t1
Removed dead code: z = t1
println(t1)
return t1

我正在做的删除时间变量的工作是提前传播它们的值。在正常情况下，我只需要提前一份。但是，对于复制传播，我可能需要多次执行。

这应该没问题，但结合代码消除，我不能保证方法调用被分配给非时间变量（查看上面的代码）。

因此，当时间变量存储方法调用结果只有一个提前出现时，我显然可以将方法调用复制到它并结束。如果没有，我可以使用 POP 指令从堆栈中删除结果。但是当出现不止一次时，我无法复制指令，因为我会接到多个电话。

我的结论是我需要保留时间变量。

是否有另一种策略可以帮助我获取时间变量的芦苇？

Answer 1

我不知道是否可以使用您当前的内部表示（即 AST）摆脱所有临时变量，但您可以使用寄存器分配算法减少它们的数量。

从你的代码来看，你每次都生成了一个新的时间变量。这类似于编译器假设（为简单起见）CPU 具有无限寄存器时的问题。然后它必须生成实际使用架构所拥有的有限数量寄存器的代码。为了从无限 registers/variables 减少到更小的有限集，使用了寄存器分配算法。

您可能会在 Engineering a Compiler by Keith Cooper 书中找到关于该主题的整章 (13)。

还有很多关于how this is done in real compilers like GCC.

的信息

我想到的是将变量视为寄存器，然后使用寄存器分配算法将其数量减少到最低限度。

这个想法显然只是我的十毛钱。设计编译器确实是一个非常复杂的问题，需要深入合作才能解决您的实际问题。

在编译器中优化代码后摆脱时间变量

Getting rid of temporal variables after optimizing code in compiler

compiler-construction

optimization