Complete removal of redundant expressions
Complete removal of redundant expressions
复制标题
彻底去除多余的表达
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
M. Soffa
中科院分区：
文献类型：
--
作者：
Rastislav Bodík;R. Gupta;M. Soffa
部分冗余消除（PRE），最重要的组成部分，全球优化，推广了消除共同的子表达式和循环不变的计算。因为现有的PRE实现是基于代码移动的，所以它们不能完全去除冗余。事实上，我们观察到73%的循环不变语句不能单独通过代码移动从循环中消除。在动态方面，传统的PRE仅消除了严格部分冗余的一半。为了实现完整的PRE，必须应用控制流重构。然而，由此产生的代码重复可能会导致代码大小爆炸。本文的重点是实现一个完整的PRE，同时招致一个可接受的代码增长。首先，我们提出了一个算法，完全消除部分冗余，基于代码运动和控制流重组的集成。与现有的完整技术相比，我们诉诸重组只是为了消除代码运动的障碍，而不是进行实际的优化。通过配置文件指导优化，通过选择那些成本合理的重复，可以进一步减少代码增长足够的执行时间收益。本文提出了两种确定程序区域重构优化效益的方法，一种是基于路径剖面的方法，另一种是基于数据流频率分析的方法。此外，新的PRE算法的抽象基础，使一个简单的公式化的投机代码运动保证有积极的动态改进。最后，我们将展示如何平衡这三个转换（代码运动，重组和投机），以实现一个几乎完整的PRE与很少的代码增长。我们还提出了算法，有效地计算动态效益。特别是，使用消除式的数据流框架，我们得到了一个需求驱动的频率分析仪，其成本可以通过允许在解决方案中的保守不精确度有界的程度进行控制。
Partial redundancy elimination (PRE), the most important component of global optimizers, generalizes the removal of common subexpressions and loop-invariant computations. Because existing PRE implementations are based on code motion, they fail to completely remove the redundancies. In fact, we observed that 73% of loop-invariant statements cannot be eliminated from loops by code motion alone. In dynamic terms, traditional PRE eliminates only half of redundancies that are strictly partial. To achieve a complete PRE, control flow restructuring must be applied. However, the resulting code duplication may cause code size explosion.This paper focuses on achieving a complete PRE while incurring an acceptable code growth. First, we present an algorithm for complete removal of partial redundancies, based on the integration of code motion and control flow restructuring. In contrast to existing complete techniques, we resort to restructuring merely to remove obstacles to code motion, rather than to carry out the actual optimization.Guiding the optimization with a profile enables additional code growth reduction through selecting those duplications whose cost is justified by sufficient execution-time gains. The paper develops two methods for determining the optimization benefit of restructuring a program region, one based on path-profiles and the other on data-flow frequency analysis. Furthermore, the abstraction underlying the new PRE algorithm enables a simple formulation of speculative code motion guaranteed to have positive dynamic improvements. Finally, we show how to balance the three transformations (code motion, restructuring, and speculation) to achieve a near-complete PRE with very little code growth.We also present algorithms for efficiently computing dynamic benefits. In particular, using an elimination-style data-flow framework, we derive a demand-driven frequency analyzer whose cost can be controlled by permitting a bounded degree of conservative imprecision in the solution.