优化堆栈代码的类型系统：分析与算法
157 浏览量
更新于2024-06-17
收藏 784KB PDF 举报
"基于堆栈的代码优化的类型系统是一篇深入探讨在低级语言中，特别是针对堆栈为基础的字节码优化技术的学术论文。作者Ando Saabas和Tarmo Uustalu来自塔林理工大学控制论研究所，他们提出了一种统一的框架来优化和进行底层分析，特别关注于死存储指令、加载弹出对、复制加载指令以及存储加载对的操作。这些优化策略建立在双向分析的基础上，这种方法显著简化了优化过程，无需依赖高级源程序的具体结构，如基本块边界是否为空，也不需要预先验证堆栈安全性，从而使得优化更加灵活和可靠。
论文的核心贡献包括：
1. 双向分析：这是一种强大的分析技术，通过同时分析指令的前后关系，解决了由于表达式和语句不明确导致的优化难题。双向分析能够识别相关指令间的依赖关系，即使它们在代码中相隔很远，也能确保优化操作的准确性。
2. 堆栈操作优化：针对堆栈操作的特定优化，如消除加载-弹出对和存储-加载对，能够在基本块边界之间正确地消除指令对，降低了对输入代码的严格要求，使得优化更具普适性。
3. 可靠性证明和最强分析算法：论文提供了一种简单且统一的方法来实现可靠性证明和主类型推断，这对于确保优化过程的正确性和高效性至关重要。
4. 适用范围：这些优化技术不仅适用于Java这样的高级语言的字节码，而且对于移动设备环境下的即时编译器特别有价值，因为它们需要小尺寸的二进制文件，而提前优化在这种场景中尤为关键。
这篇论文为基于堆栈的代码优化提供了理论基础和技术手段，对于理解并改进现代编译器和虚拟机的性能优化具有重要的实践意义。"
106
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
我们分两个阶段来消除死代码。在第一阶段（我们称之为死存储消除），所有死
存储，添加和条件跳转指令都被替换为弹出指令（以便优化不会在任何标签处改变
堆栈高度）基于标准活变量分析的模拟。 在第二阶段中，如果可能的话，消除具
有相应的先前加载/推入指令的弹出指令，并且注意保持栈高度
剩余16页未读，继续阅读
2012-10-14 上传
2021-09-12 上传
2021-02-04 上传
2021-05-13 上传
2021-02-23 上传
2019-08-11 上传
2021-02-05 上传
2021-03-05 上传
2021-07-19 上传
cpongm
- 粉丝: 5
- 资源: 2万+
我的内容管理
展开
最新资源
- MATLAB新功能：Multi-frame ViewRGB制作彩色图阴影
- XKCD Substitutions 3-crx插件：创新的网页文字替换工具
- Python实现8位等离子效果开源项目plasma.py解读
- 维护商店移动应用：基于PhoneGap的移动API应用
- Laravel-Admin的Redis Manager扩展使用教程
- Jekyll代理主题使用指南及文件结构解析
- cPanel中PHP多版本插件的安装与配置指南
- 深入探讨React和Typescript在Alias kopio游戏中的应用
- node.js OSC服务器实现：Gibber消息转换技术解析
- 体验最新升级版的mdbootstrap pro 6.1.0组件库
- 超市盘点过机系统实现与delphi应用
- Boogle: 探索 Python 编程的 Boggle 仿制品
- C++实现的Physics2D简易2D物理模拟
- 傅里叶级数在分数阶微分积分计算中的应用与实现
- Windows Phone与PhoneGap应用隔离存储文件访问方法
- iso8601-interval-recurrence：掌握ISO8601日期范围与重复间隔检查
