Load-reuse analysis: design and evaluation
Load-reuse analysis: design and evaluation
复制标题
负载重用分析：设计和评估
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
M. Soffa
中科院分区：
文献类型：
--
作者：
Rastislav Bodík;Rajiv Gupta;M. Soffa
加载-重用分析查找重复访问同一内存位置的指令。可以将该位置提升为寄存器，通过重用先前存储器访问的结果来消除冗余负载。本文开发了一种负载重用分析，并设计了一种评估其精度的方法。在设计该分析时，我们追求完备性-目标是揭示通过后续程序转换可以获得的所有重用。对于寄存器提升，合适的转换是部分冗余消除(PRE)。为了接近预完成的理想目标，加载-重用分析被表述为路径敏感的程序表示上的数据流问题，因为它即使在每个控制流路径上起源于不同的指令时也会检测到重用。此外，分析是全面的，因为它统一处理基于标量、数组和指针的负载。在评估分析时，我们将其与理想分析进行了比较。通过观察内存引用的运行时流，我们收集了所有预先可利用的重用，并将其视为理想的分析性能。为了比较(静态)负载重用分析和(动态)理想重用，我们使用了一种估计器算法，该算法在给定数据流解决方案和程序配置文件的情况下，计算分析检测到的动态重用性。我们开发了一系列不同的估计器，它们在约束边缘轮廓固有的轮廓误差方面存在差异。通过误差的界，估计器提供了一种精确而实用的方法来确定运行时的优化收益。我们的实验表明，在spec95中执行的大约55%的负载表现出了重用。其中，我们的分析揭露了大约80%。
Load-reuse analysis finds instructions that repeatedly access the same memory location. This location can be promoted to a register, eliminating redundant loads by reusing the results of prior memory accesses. This paper develops a load-reuse analysis and designs a method for evaluating its precision.In designing the analysis, we aspire for completeness---the goal of exposing all reuse that can be harvested by a subsequent program transformation. For register promotion, a suitable transformation is partial redundancy elimination (PRE). To approach the ideal goal of PRE-completeness, the load-reuse analysis is phrased as a data-flow problem on a program representation that is path-sensitive, as it detects reuse even when it originates in a different instruction along each control flow path. Furthermore, the analysis is comprehensive, as it treats scalar, array and pointer-based loads uniformly.In evaluating the analysis, we compare it with an ideal analysis. By observing the run-time stream of memory references, we collect all PRE-exploitable reuse and treat it as the ideal analysis performance. To compare the (static) load-reuse analysis with the (dynamic) ideal reuse, we use an estimator algorithm that computes, given a data-flow solution and a program profile, the dynamic amount of reuse detected by the analysis. We developed a family of estimators that differ in how well they bound the profiling error inherent in the edge profile. By bounding the error, the estimators offer a precise and practical method for determining the run-time optimization benefit.Our experiments show that about 55% of loads executed in Spec95 exhibit reuse. Of those, our analysis exposes about 80%.