![](https://csdnimg.cn/release/download_crawler_static/88745297/bg4.jpg)
A. Saabas
,
T.Uustalu/
理论计算机科学电子笔记
190
(
2007
)
103
(l
,
store
x)∈c n∈ Z
store
(l
,
load
x)∈ c
load
c
<$
(l
,
n::
zs
,
σ)→(l+ 1
,
zs
,
σ[x
<$→
n]) c
<
$(l
,
zs
,
σ)→(l+ 1
,
σ(x)::
zs
,
σ)
(
l
,
push
n
)∈
c
push
(
l
,
add)∈
c n
0
,
n
1
∈
Z
加
c
<$
(
l
,
zs
,
σ
)
→
(
l
+
1
,
n
::zs
,
σ
)
c
<
$
(
l
,
n
0
::
n
1
::zs
,
σ
)
→
(
l
+
1
,
n
0
+
n
1
::
zs
,
σ
)
(l
,
pop
)∈c
pop
(l
,
dup
)∈c
dup
c
<$
(
l
,
z
::zs
,
σ
)
→
(l+
1
,
zs
,
σ
)
c
<
$
(
l
,
z
::zs
,
σ
)
→
(l+
1
,
z
::
z
::zs
,
σ
)
(
l
,
goto
m
)∈
c
goto
c
<$
(
l
,
zs
,
σ
)
→
(
m
,
zs
,
σ
)
(
l
,
gotoF
m
)∈
c
gotoF
tt
(
l
,
gotoF
m
)∈
c
gotoF
<$
c
<$
(l
,
tt
::zs
,
σ
)
→
(l
+ 1
,
zs
,
σ
)
c
<
$(l
,
tt
::zs
,
σ
)
→
(
m
,
zs
,
σ
)
Fig. 1.
小步语义规则
删除赋值后立即死亡的变量。在基于堆栈的代码中,表达式不是显式的(相关指令
也不一定相邻),删除死代码并不那么简单。例如,程序x
:=
z
+
y可以编译成
0
,
加载
z 1
,
加
载 y 2
,
添加
3
、
店铺x
四
,
如果分析表明x是死的,那么在中间代码中,赋值 x可以删除。然而,在基于堆栈
的代码中,不仅第3行上的存储指令,而且第0-2行也应该被删除。
将基于堆栈的代码优化与中间语言中的优化分开的另一个问题是语句和表达式可
以跨越几个基本块(或者,换句话说,基本块不一定进入空堆栈或从空堆栈退
出)。这种代码的一个简单示例是以下基于堆栈的低级别 等效代码
ifbthenx
:
=
zelsey
:=
z
,其中
z
仅加载一次,并且在两个分支中,仅应用store指令
0
,
loadz
1
,
loadb
2
,
gotoF
5 3
,
storex 4
,
goto 6 5
,
storey 6
,
如果活变量分析显示变量x是死的,则不能简单地移除第3行的存储指令,因为如果
采用真分支,则变量
x
的未赋值将在退出分支后留在栈上。 第0行上的加载指令也不
能被删除,因为当它被死存储使用时,它也被假分支中的活存储使用。 在这种情况
下,如果没有移动指令,最好的办法是用弹出命令替换指令3
我们分两个阶段来消除死代码。在第一阶段(我们称之为死存储消除),所有死
存储,添加和条件跳转指令都被替换为弹出指令(以便优化不会在任何标签处改变
堆栈高度)基于标准活变量分析的模拟。 在第二阶段中,如果可能的话,消除具
有相应的先前加载/推入指令的弹出指令,并且注意保持栈高度