全局值编号的局部冗余消除技术

78 浏览量更新于2024-07-14 收藏 699KB PDF 举报

"Partial Redundancy Elimination for Global Value Numbering 是一种优化技术，常用于编译器设计，旨在提升程序性能。该技术由Thomas John VanDrunen在他的博士论文中探讨，于2004年在普渡大学提交。论文指导老师是Tony Hosking，其他如Jens Palsberg、Jan Vitek和Zhiyuan Li也为作者的研究提供了帮助。" 在全球值编号（Global Value Numbering, GVN）中，部分冗余消除（Partial Redundancy Elimination, PRE）是一种关键的优化策略。全球值编号是一种编译器分析技术，它的目标是识别出程序中具有相同计算结果的表达式，并将它们替换为一个共享的常量或变量，从而减少重复计算，提高代码效率。在PRE的过程中，编译器不仅关注整个基本块（Basic Block）内的冗余，还考虑跨越基本块的冗余表达式。论文可能详细讨论了以下几点： 1. **全局分析**：GVN需要对整个程序进行分析，以识别在不同控制流路径上的等价表达式。这涉及到了数据流分析，包括定义-使用链（Definition-Use Chains）和反向数据流分析。 2. **等价类**：在GVN中，表达式被视为“值”，如果两个表达式的计算结果总是相同的，那么它们被认为是等价的。这些等价类可以是常量、变量或更复杂的表达式。 3. **部分冗余**：PRE扩展了GVN的概念，处理那些只在部分控制流路径上冗余的表达式。例如，如果一个表达式在某个循环的迭代中多次计算，但在循环外部没有使用，那么这个表达式就可以被消除。 4. **优化挑战**：PRE的实施需要解决一些挑战，比如如何有效地跟踪和更新等价类，如何处理副作用，以及如何避免在消除冗余时引入新的错误。 5. **实现方法**：论文可能提出了具体的算法和数据结构，用于在编译器中实现PRE和GVN，包括哈希表来存储和比较表达式，以及控制流图（Control Flow Graph, CFG）来表示程序的结构。 6. **实验与评估**：通常，这样的研究会包含对实际代码的实验，以验证优化的效果。这些实验可能对比优化前后的代码大小、运行时间和资源消耗，以证明PRE在优化编译器输出方面的作用。 7. **应用与影响**：PRE和GVN优化技术广泛应用于现代编译器中，对于提高软件性能，尤其是对于那些计算密集型的应用，效果显著。通过这部分摘要信息，我们可以推测论文深入探讨了PRE在GVN框架下的理论和实践，为编译器设计者提供了一种提高程序执行效率的有效工具。然而，具体的细节和技术实现，包括如何处理复杂的数据依赖和控制依赖，以及在具体编程语言中的适应性等，需要阅读完整的论文才能获取。

two computations match exactly, including with respect to variable names, they are

lexically equivalent, as in the case of the two computations of d + e in our example.

Note, however, that even though a + b and d + a are not lexically equivalent, they

still compute the same value on any run of the program. This is an example of a

value equivalence. Analyses that consider value equivalences are stronger than those

that restrict themselves to lexical equivalences.

Previous work on this problem has fallen typically into two categories. Global

value numbering (GVN) analyzes programs to group expressions into classes, all of

which have the same value in a static view of the program. Partial redundancy

elimination (PRE) hoists computations to make partially redundant computations

fully redundant and thus removable.

1.1.2 Thesis statement

This dissertation concerns the removal of value-equivalent computations. By

presenting algorithms to this end, it seeks to demonstrate that

Practical, complete, and eﬀective analyses for availability and anticipa-

tion allow transformations to remove full and partial value-equivalent

redundancies.

The algorithms presented here are practical in that they can be implemented

simply, incorporate easily into the optimization sequence of existing compilers, have

a reasonable cost, and represent an advancement over previous work in this area from

a software engineering perspective. They are complete in that they subsume other

algorithms with similar goals. They are eﬀective in that they produce a performance

gain on some benchmarks. Finally, they consider not only lexically equivalent but

also value equivalent computations and remove not only full redundancies but also

partial redundancies.

In particular, we present three algorithms. The ﬁrst is a PRE algorithm for an

IR property that is particularly useful for GVN. The second is a complete hybrid of

PRE and GVN. The third uses GVN to perform PRE on object and array references.

An additional contribution of this dissertation is the framework we use to discuss

programs and values for the purpose of optimizing analyses and transformations.

1.1.3 Outline

The remainder of this chapter explains preliminary matters relevant to all parts

of the dissertation: deﬁnitions for the IR and other details of our framework (Section

1.2.1), the cost model and standards we use to make claims of our algorithms’ worth

(Section 1.2.2), an overview of our experimental infrastructure (Section 1.2.3), and

a list of prior publications of the material presented here (Section 1.2.4). Chapter 2

traces the development of other approaches to this and similar problems. As implied

earlier, there are two major strains in the evolution, motivating the hybrid approach

which is the cornerstone of this dissertation.

Chapter 3 presents the ASSAPRE algorithm. Chow, Kennedy, et al introduced

SSAPRE [1, 2], an algorithm for PRE on IRs with a property called static sin-

gle assignment (SSA) form. We critique this algorithm in three areas. First, it is

fundamentally weak in that it is completely lexical in its outlook and ignores re-

dundancies involving secondary eﬀects. Second, it actually makes requirements on

the IR that are more strict than SSA, as it is usually understood, and if applied

to a non-conforming program will perform erroneous transformations. Finally, it is

diﬃcult to understand and implement. ASSAPRE is an improvement in these areas.

It reduces lexical restrictions on the expressions it considers, and it uses an antici-

pation analysis. Since SSA is useful for GVN, this algorithm illuminates how PRE,

which is typically lexical, can be extended for use with GVN, thereby considering

values-based equivalence.

Chapter 4 presents the GVNPRE algorithm. This is the chief contribution of

the dissertation and is a novel hybrid of earlier GVN and PRE approaches. It uses a

clean way of partitioning expressions into values that is an extension of a simple hash-

based GVN, uses a system of ﬂow equations to calculate availability and anticipation

and to determine insertion points, and removes full and partial redundancies.

Chapter 5 presents the LEPRE algorithm. GVNPRE considers only scalar op-

erations, not, for example, loads from objects and arrays. We show that it is im-

possible to extend GVNPRE to cover loads completely. Fink et al. introduced an

algorithm for eliminating loads that are fully redundant [3]. Although not itself a

GVN scheme, it relies on GVN as input to its analysis. However, that algorithm

does not consider partial redundancies. As an approximate solution to the problem

of extending GVNPRE for loads, we extend Fink et al’s algorithm to use GVNPRE’s

analysis for doing PRE. We also sketch a diﬀerent approach to cross-breeding GVN

and PRE that would be more amenable to the removal of loads.

We compare each algorithm to related approaches, describe an implementation,

and report on static and performance results. Chapter 6 concludes by considering

future work in this area.

1.2 Preliminaries

1.2.1 IR deﬁnitions and assumptions

We assume input programs represented as control ﬂow graphs (CFGs) over basic

blocks [4]. A basic block is a code segment that has no unconditional jump or

conditional branch statements except for possibly the last statement, and none of its

statements, except for possibly the ﬁrst, is a target of any jump or branch statement.

A CFG is a graph representation of a procedure that has basic blocks for nodes and

whose edges represent the possible execution paths determined by jump and branch

statements. Blocks are identiﬁed by numbers; paths in the graph (including edges)

are identiﬁed by a parenthesized list of block numbers. We deﬁne succ(b) to be the set

of successors to basic block b in the CFG, and similarly pred(b) the set of predecessors.

(When these sets contain only one element, we use this notation to stand for that

element for convenience.) We also deﬁne dom(b) to be the dominator of b, the nearest

剩余151页未读，继续阅读

weixin_38651468

粉丝: 5
资源: 896

全局值编号的局部冗余消除技术

Gauss-Elimination-With-Partial-Pivoting-And-Complete-Pivoting-Python-Code:我的GitHub个人资料的配置文件

Mitochondrial partial DNA sequences analysis of the Chi-lin fish from Tai Mountain: implication for its systematics and evolution

Integrating local and partial network view for routing on scale-free networks

Allocation Removal by Partial Evaluation in a Tracing JIT - 2010 (bolz-allocation-removal)-计算机科学

Memory-Efficient Search Trees for Database Management Systems - Feb 2020 - Thesis (CMU-CS-20-101)-计算机科学

Practical Data Compression for Modern Memory Hierarchies - July 2016 - CMU-CS-16-116 (1609.02067)-计算机科学

Gauss-Jordan Elimination with Partial Pivoting:Gauss-Jordan Elimination with Partial Pivoting-matlab开发

Lower Bound Techniques for Data Structures-计算机科学

ARIES - A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging (1992)-计算机科学

html-partial-task-manager-with-grunt

最新资源