第7章中所涉及的优化不论是简化计算,还是冗余删除,其目的都是试图通过优化算法提高代码执行效率。本小节将引领读者从另一个视角来思考有关优化的问题,那就是存储优化。所谓“存储优化”就是通过优化算法以改善目标程序在执行过程中对存储资源的耗费。在优化技术中,读者可能有机会接触到一个概念,即存储层次优化。注意,存储层次优化与这里所讨论的存储优化是两个完全不同的概念。存储层次优化主要是关注如何利用存储器的层次(例如,常见的三级存储结构)来提高代码执行效率的一种优化算法。而存储优化并不关注代码执行的效率,换句话说,它本身不会对代码执行效率产生任何影响。下面,通过一个简单的实例来看看存储优化的基本思想。
如图8-11所示,读者不必关注aa函数是怎样实现的,假设aa是一个非空函数即可。在这个实例中,i、j、k的作用域都是整个main函数体。显然,根据存储分配的原则,编译器必须分配三个存储单元用于分别存储i、j、k的值。不过,从程序逻辑本身的特点来说,不难发现,即使将i、j、k都分配在同一个存储单元中,也不会给程序执行结果带来任何影响。这种依赖于程序逻辑实现的存储共享策略就是存储分配的基本思想。
存储优化的成果就是提出一个存储分配的策略或者方案,其主要描述的就是哪些变量可以共享同一个存储单元。而存储分配算法就可以根据这份方案来完成实际的存储分配工作。
图8-11 存储优化引例
通用的存储优化算法是有一定难度的,由于篇幅所限,笔者并不打算深入讨论。这里,只针对编译器产生的临时变量进行分配优化,这是相对容易且有效的。在IR生成阶段,编译器始终没有关注如何避免临时变量冗余的问题。在很多情况下,即使是一个非常简单的源程序,其对应的目标程序所涉及的临时变量数目也是非常可观的,甚至可以用“庞大”二字来形容,这是用户不能接受的。笔者可以举一个简单的例子。(www.daowen.com)
例8-2 临时变量存储分配优化实例,见表8-2。
表8-2 临时变量存储分配优化
这样一个简单的程序,也需要耗用6个临时变量,如果编译一个实际的应用程序,消耗数千甚至更多的临时变量并不罕见。因此,寻找一种较优的分配策略是极其重要的。注意,本例中(c)列只是在(b)列的基础上做了常量传播、复写传播等优化后的结果。虽然代码的规模有所减小,但是临时变量的个数并没有任何变化。存储分配的优化并不会改善代码本身的形式,只是提出了一份较优的存储分配的策略。在这个例子中,优化算法提出的临时变量分配方案即为:_TO、_T2、_T3、_T4、_T5共享一个存储单元,_Tl独享一个存储单元。如果读者根据这个分配方案仔细推敲(c)列的IR,可以发现,程序依然是正确且安全的。然而,临时变量的使用数量却大大减少了,这是令人欣慰的。那么,为什么_Tl不能与其他临时变量共享同一个存储单元呢?这个问题非常简单,如果共享同一个存储单元,那么,第2行、第3行的定值将影响Tl本身的定值(即由第1行IR所置入的值)。然而,由于第4行中又存在Tl的引用点,此时,_Tl的值可能已经不是原来由第1行IR所确定的,而是由第3行所确定的,这显然与原始的语义不符。
至此,笔者通过一个实例简单介绍了存储优化的概念及其意义。存储优化的前提就是保证访问的安全性,而这也正是其算法的关键所在。实际上,本书讨论的存储优化模型与通用的存储优化算法的差异就在于冲突检测机制。讨论临时变量的冲突检测远比普通的用户变量容易得多。通常,冲突可以利用图或者网结构描述,如常见检测算法就是基于图着色思想实现的。在经典编译技术中,图着色更多应用于寄存器分配算法中,主要用于描述寄存器的使用冲突。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。