技术笔记

Java 代码优化

目标：想要优化掉一些只用一次的临时变量
例子：

1
2
3
//b = a;
temp = a;
b = temp;

优化方法：基于基本块的DAG(有向无环图)删除无用代码

  • 基本块是满足下列条件的最大的连续 三地址指令序列：

    • 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令
    • 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机

  • 基本块的 DAG 表示

    • 对于每一个直接出现在基本块中的变量，定义其为input value，对应一个节点
    • 对于每条语句，对应一个node
    • 如果语句S1使用了语句S2 … Sn定义的变量，则分别有边从S2 … Sn指向S1
    • 对于在基本块中没有再次使用的变量，定义为output value

    例子：基本块：

1
2
3
4
a = b + c
b = a - d
c = b + c
d = a - d

DAG：

DAG示意图

在DAG中，如果一个output value（即根结点）在之后不会使用到（需要用到基本块间的关系），则该值的计算是没有意义的，可以去除计算该值的语句，该过程需要递归进行。
示例：如果d，或者c在之后不会被用到，则分别可以进行如下的消除。

死代码消除

示例2：

DAG建图过程

四元式对应的 DAG 结点形式

四元式对应的 DAG 结点形式

回到最初的问题：temp = a; b = temp 如何优化？

A: 都是赋值语句（都为0型语句），DAG中只有一个结点，无边(即最简单情况的DAG化简)

graph TB
x["a(=temp)=b"]

P.S. 看到小站可以正常支持mermaid 开心一下

参考文档

Reference1
Reference2
Reference3