检索结果-内蒙古大学图书馆

Algorithms for computing the static single assignment form

JOURNAL OF THE ACM 2003年第3期50卷 375-425页

作者： Bilardi, G Pingali, K Univ Padua Dipartimento Ingn Informaz I-35131 Padua Italy Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

The static single assignment (SSA) form is a program representation used in many optimizing compilers. The key step in converting a program to SSA form is called phi-placement. Many algorithms for phi-placement have been proposed in the literature, but the relationships between these algorithms are not well understood. In this article, we propose a framework within which we systematically derive (i) properties of the SSA form and (ii) phi-placement algorithms. This framework is based on a new relation called merge which captures succinctly the structure of a program's control flow graph that is relevant to its SSA form. The phi-placement algorithms we derive include most of the ones described in the literature, as well as several new ones. We also evaluate experimentally the performance of some of these algorithms on the SPEC92 benchmarks. Some of the algorithms described here are optimal for a single variable. However, their repeated application is not necessarily optimal for multiple variables. We conclude the article by describing such an optimal algorithm, based on the transitive reduction of the merge relation, for multi-variable phi-placement in structured programs. The problem for general programs remains open.

关键词： algorithms languages theory control dependence optimizing compilers program optimization program transformation static single assignment form

来源：评论

学校读者我要写书评

暂无评论

Java bytecode verification via static single assignment form

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2008年第4期30卷 1–21页

作者： Gal, Andreas Probst, Christian W. Franz, Michael Univ Calif Irvine Irvine CA 92717 USA Tech Univ Denmark Kongens Lyngby Denmark

Java Virtual Machines (JVMs) traditionally perform bytecode verification by way of an iterative dataflow analysis. Bytecode verification is necessary to ensure type safety because temporary variables in the JVM are not statically typed. We present an alternative verification mechanism that transforms JVM bytecode into static single assignment form (SSA) and thereby propagates definitions directly to uses. Type checking at control flow merge points can then be performed in a single pass. Our prototype implementation of the new algorithm is faster than the standard JVM bytecode verifier. It has the additional benefit of generating SSA as a side effect, which may be immediately useful for a subsequent dynamic compilation stage.

关键词： algorithms design experimentation languages performance security verification Java bytecode verification static single assignment form dataflow analysis

来源：评论

学校读者我要写书评

暂无评论

Practical improvements to the construction and destruction of static single assignment form

引用

SOFTWARE-PRACTICE & EXPERIENCE 1998年第8期28卷 859-881页

作者： Briggs, P Cooper, KD Harvey, TJ Simpson, LT Tera Comp Co Seattle WA 98102 USA Rice Univ Dept Comp Sci Houston TX 77005 USA Tril Dev Grp Austin TX 78730 USA

static single assignment (SSA) form is a program representation that is becoming increasingly popular for compiler-based code optimization. In this paper, we address three problems that have arisen in our use of SSA form. Two are variations to the SSA construction algorithms presented by Cytron et al,(1) The first variation is a version of SSA form that we call 'semi-pruned' SSA, It offers an attractive trade-off between the cost of global data-how analysis required to build 'pruned' SSA and the large number of unused phi-functions found in minimal SSA, The second variation speeds up the program renaming process by efficiently manipulating the stacks of names used during renaming. Our improvement reduces the number of pushes performed, in addition to more efficiently locating the stacks that should be popped. To convert code in SSA form back into an executable form, the compiler must use an algorithm that replaces phi-functions with appropriately-placed copy instructions. The algorithm given by Cytron et al, for inserting copies produces incorrect results in some situations;particularly in cases like instruction scheduling, where the compiler may not be able to split 'critical edges', and in the aftermath of optimizations that aggressively rewrite the name space, like some forms of global value numbering.(2) We present a new algorithm for inserting copy instructions to replace phi-functions. It fixes the problems that we have encountered with the original copy insertion algorithm. We present experimental results that demonstrate the effectiveness of the first two improvements not only during the construction of SSA form, but also in the time saved by subsequent optimization passes that use a smaller representation of the program. (C) 1998 John Wiley & Sons, Ltd.

关键词： compilers code optimization data-flow analysis static single assignment form lost-copy problem swap problem

来源：评论

学校读者我要写书评

暂无评论

Anticipation-based partial redundancy elimination for static single assignment form

引用

SOFTWARE-PRACTICE & EXPERIENCE 2004年第15期34卷 1413-1439页

作者： VanDrunen, T Hosking, AL Wheaton Coll Dept Math & Comp Sci Wheaton IL 60187 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

Partial redundancy elimination (PRE) is a program transformation that identifies and eliminates expressions that are redundant on at least one (but not necessarily all) execution paths of a program without increasing any path length. Chow, Kennedy and co-workers devised an algorithm (SSAPRE) for performing partial redundancy elimination on intermediate representations in static single assignment (SSA) form. The practicality of that algorithm is limited by the following concerns: (1) it makes assumptions about the namespace that are stronger than those of SSA form and that may not be valid if other optimizations have already been performed on the program;(2) if redundancies occur in nested expressions, the algorithm may expose but not eliminate them (requiring a second pass of the algorithm);(3) it misses cases covered by the state of the art in PRE;and (4) it is difficult to understand and implement. We present an algorithm (A-SSAPRE) structurally similar to SSAPRE that uses anticipation rather than availability;this algorithm is simpler than SSAPRE, covers more cases, eliminates nested redundancies on a single pass, and makes no assumptions about the namespace. Copyright (C) 2004 John Wiley Sons, Ltd.

关键词： partial redundancy elimination static single assignment form machine-independent program transformations

来源：评论

学校读者我要写书评

暂无评论

Practical improvements to the construction and destruction of static single assignment form

引用

Software: Practice and Experience 1999年第8期28卷

作者： Preston Briggs Keith D. Cooper Timothy J. Harvey L. Taylor Simpson Tera Computer Company 2815 Eastlake Ave. East Seattle WA 98102 USA Department of Computer Science Rice University 6100 S. Main - MS 132 Houston TX 77005 USA Trilogy Development Group 6034 W. Courtyard Dr. Austin TX 78730 USA

static single assignment (SSA) form is a program representation that is becoming increasingly popular for compiler-based code optimization. In this paper, we address three problems that have arisen in our use of SSA form. Two are variations to the SSA construction algorithms presented by Cytron et al . 1 The first variation is a version of SSA form that we call ‘semi-pruned’ SSA. It offers an attractive trade-off between the cost of global data-flow analysis required to build ‘pruned’ SSA and the large number of unused ϕ-functions found in minimal SSA. The second variation speeds up the program renaming process by efficiently manipulating the stacks of names used during renaming. Our improvement reduces the number of pushes performed, in addition to more efficiently locating the stacks that should be popped. To convert code in SSA form back into an executable form, the compiler must use an algorithm that replaces ϕ-functions with appropriately-placed copy instructions. The algorithm given by Cytron et al . for inserting copies produces incorrect results in some situations; particularly in cases like instruction scheduling, where the compiler may not be able to split ‘critical edges’, and in the aftermath of optimizations that aggressively rewrite the name space, like some forms of global value numbering. 2 We present a new algorithm for inserting copy instructions to replace ϕ-functions. It fixes the problems that we have encountered with the original copy insertion algorithm. We present experimental results that demonstrate the effectiveness of the first two improvements not only during the construction of SSA form, but also in the time saved by subsequent optimization passes that use a smaller representation of the program. © 1998 John Wiley & Sons, Ltd.

关键词： compilers code optimization data-flow analysis static single assignment form lost-copy problem swap problem

来源：评论

学校读者我要写书评

暂无评论

Comparison and evaluation of back-translation algorithms for static single assignment forms

引用

COMPUTER LANGUAGES SYSTEMS & STRUCTURES 2009年第2期35卷 173-195页

作者： Sassa, Masataka Ito, Yo Kohama, Masaki Tokyo Inst Technol Dept Math & Comp Sci Meguro Ku Tokyo 1528552 Japan

The static single assignment form (SSA form) is a popular intermediate representation in compilers. In the SSA form, the definition of each variable textually appears only once in the program by using a hypothetical function called a phi-function. Because these functions are nonexecutable, it is necessary to delete the phi-functions and return the SSA form to the normal form before code generation. This conversion is called SSA back-translation. Two major algorithms exist for SSA back-translation. One by Briggs et al., the other by Sreedhar et al. To date, there has been almost no research that compares these SSA back-translation algorithms. In this paper, we clarify the merits and demerits of these algorithms. We also propose an improvement to Briggs' algorithm. We then compare the three methods through experiments using the SPEC benchmarks. Our experiments show that in most cases, Sreedhar's method is the more favorable. The efficiency of its object code is better than that from Briggs' method by a few percent in general, up to a maximum of 28%. The experiments have also clarified several characteristic features of these methods. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： static single assignment form Back-translation Intermediate language Machine-independent program transformation Compiler

来源：评论

学校读者我要写书评

暂无评论

Studying Optimal Spilling in the Light of SSA

引用

ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION 2014年第4期11卷 1–26页

作者： Colombet, Quentin Brandner, Florian Darte, Alain UCB Lyon ENS Lyon CNRS LIPUMR 5668INRIACompsys Lyon France ENSTA ParisTech U2IS Comp Sci & Syst Engn Dept Paris France

Recent developments in register allocation, mostly linked to static single assignment (SSA) form, have shown the benefits of decoupling the problem in two phases: a first spilling phase places load and store instructions so that the register pressure at all program points is small enough, and a second assignment and coalescing phase maps the variables to physical registers and reduces the number of move instructions among registers. This article focuses on the first phase, for which many open questions remain: in particular, we study the notion of optimal spilling (what can be expressed?) and the impact of SSA form (does it help?). To identify the important features for optimal spilling on load-store architectures, we develop a new integer linear programming formulation, more accurate and expressive than previous approaches. Among other features, we can express SSA phi-functions, memory-to-memory copies, and the fact that a value can be stored simultaneously in a register and inmemory. Based on this formulation, we present a thorough analysis of the results obtained for the SPECINT 2000 and EEMBC 1.1 benchmarks, from which we draw, among others, the following conclusions: (1) rematerialization is extremely important;(2) SSA complicates the formulation of optimal spilling, especially because of memory coalescing when the code is not in conventional SSA (CSSA);(3) microarchitectural features are significant and thus have to be accounted for;and (4) significant savings can be obtained in terms of static spill costs, cache miss rates, and dynamic instruction counts.

关键词： Algorithms Experimentation Performance Theory Register allocation spilling static single assignment form performance models

来源：评论

学校读者我要写书评

暂无评论

A practical and fast iterative algorithm for φ-function computation using DJ graphs

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2005年第3期27卷 426-440页

作者： Das, D Ramakrishna, U Hewlett Packard Corp India Software Operat Bangalore 560052 Karnataka India Colorado State Univ Ft Collins CO 80523 USA

We present a new and practical method of computing phi-function for all variables in a function for static single assignment (SSA) form. The new algorithm is based on computing the Merge set of each node in the control flow graph of a function (a node here represents a basic block and the terms will be used interchangeably). Merge set of a node n is the set of nodes N, where phi-functions may need to be placed if variables are defined in n. It is not necessary for n to have a definition of a variable in it. Thus, the merge set of n is dictated by the underlying structure of the CFG. The new method presented here precomputes the merge set of every node in the CFG using an iterative approach. Later, these merge sets are used to carry out the actual phi-function placement. The advantages are in examples where dense definitions of variables are present (i.e., original definitions of variables-user defined or otherwise, in a majority of basic blocks). Our experience with SSA in the High Level Optimizer (optimization levels +O3/+O4) shows that most examples from the Spec2000 benchmark suite require a high percentage of basic blocks to have their phi points computed. Previous methods of computing the same relied on the dominance frontier (DF) concept, first introduced by Cytron et al. The method presented in this paper gives a new effective iterative solution to the problem. Also, in cases, where the control flow graph does not change, our method does not require any additional computation for new definitions introduced as part of optimizations. We present implementation details with results from Spec2000 benchmarks. Our algorithm runs faster than the existing methods used.

关键词： static single assignment form dominance frontier DJ graph

来源：评论

学校读者我要写书评

暂无评论

Operator strength reduction

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2001年第5期23卷 603-625页

作者： Cooper, KD Simpson, LT Vick, CA Rice Univ Houston TX 77251 USA Sun Microsyst Inc Palo Alto CA 94303 USA

Operator strength reduction is a technique that improves compiler-generated code by reformulating certain costly computations in terms of less expensive ones. A common case arises in array addressing expressions used in loops. The compiler can replace the sequence of multiplies generated by a direct translation of the address expression with an equivalent sequence of additions. When combined with linear function test replacement, strength reduction can speed up the execution of loops containing array references. The improvement comes from two sources: a reduction in the number of operations needed to implement the loop and the use of less costly operations, This paper presents a new algorithm for operator strength reduction, called OSR. OSR improves upon an earlier algorithm of Allen, Cocke, and Kennedy [Allen et al. 1981]. OSR operates on the static single assignment (SSA) form of a procedure [Cytron et al. 1991]. By taking advantage of the properties Of SSA form, we have derived an algorithm that is simple to understand, quick to implement, and, in practice, fast to run. Its asymptotic complexity is, in the worst case, the same as the Allen, Cocke, and Kennedy algorithm (ACK). OSR achieves optimization results that are equivalent to those obtained with the ACK algorithm. OSR has been implemented in several research and production compilers.

关键词： algorithms languages loops strength reduction static single assignment form

来源：评论

学校读者我要写书评

暂无评论

Partial redundancy elimination in SSA form

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1999年第3期21卷 627-676页

作者： Kennedy, R Chan, S Liu, SM Lo, R Tu, P Chow, F Silicon Graph Inc Mt View CA 94043 USA

The SSAPRE algorithm for performing partial redundancy elimination based entirely on SSA form is presented. The algorithm is formulated based on a new conceptual framework, the factored redundancy graph, for analyzing redundancy, and represents the first sparse approach to the classical problem of partial redundancy elimination. At the same time, it provides new perspectives on the problem and on methods for its solution. With the algorithm description, theorems and their proofs are given showing that the algorithm produces the best possible code by the criteria of computational optimality and lifetime optimality of the introduced temporaries. In addition to the base algorithm, a practical implementation of SSAPRE that exhibits additional compile-time efficiencies is described. In closing, measurement statistics are provided that characterize the instances of the partial redundancy problem from a set of benchmark programs and compare optimization time spent by an implementation of SSAPRE against a classical partial redundancy elimination implementation. The data lend insight into the nature of partial redundancy elimination and demonstrate the expediency of this new approach.

关键词： algorithms measurement theory partial redundancy code motion static single assignment form common subexpressions data flow analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：