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

Proceedings of the acm sigplan conference on programming language design and implementation (pldi) 1999年 204-214页

作者： Leung, Allen George, Lal New York Univ New York NY United States

Static Single Assignment (SSA) is an effective intermediate representation in optimizing compilers. However, traditional SSA form and optimizations are not applicable to programs represented as native machine instructions because the use of dedicated registers imposed by calling conventions, the runtime system, and target architecture must be made explicit. We present a simple scheme for converting between programs in machine code and in SSA, such that references to dedicated physical registers in machine code are preserved. Our scheme ignores all output- and anti-dependences imposed by physical registers while a program is in SSA form, but inserts compensation code during machine code reconstruction if any naming requirements have been violated. By resolving all mismatches between the two representations in separate phases, we are able to utilize existing SSA algorithms unaltered to perform machine code optimizations.

关键词： Object oriented programming

来源：评论

学校读者我要写书评

暂无评论

Implicitly heterogeneous multi-stage programming 05

Implicitly heterogeneous multi-stage programming

引用

4th International conference on Generative programming and Component Engineering

作者： Eckhardt, J Kaiabachev, R Pasalic, E Swadi, K Taha, W Rice Univ Houston TX 77005 USA

ISBN: (纸本)3540291385

Previous work on semantics-based multi-stage programming (MSP) language design focused on homogeneous designs, where the generating and the generated languages are the same. Homogeneous designs simply add a hygienic quasi-quotation and evaluation mechanism to a base language. An apparent disadvantage of this approach is that the programmer is bound to both the expressivity and performance characteristics of the base language. This paper proposes a practical means to avoid this by providing specialized translations from subsets of the base language to different target languages. This approach preserves the homogeneous "look" of multi-stage programs, and, more importantly, the static guarantees about the generated code. In addition, compared to an explicitly heterogeneous approach, it promotes reuse of generator source code and systematic exploration of the performance characteristics of the target languages. To illustrate the proposed approach, we design and implement a translation to a subset of C suitable for numerical computation, and show that it preserves static typing. The translation is implemented, and evaluated with several benchmarks. The implementation is available in the online distribution of MetaOCaml.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Program structure tree. Computing control regions in linear time

Program structure tree. Computing control regions in linear ...

引用

Proceedings of the acm sigplan'94 conference on programming language design and implementation (pldi)

作者： Johnson, Richard Pearson, David Pingali, Keshav Cornell Univ Ithaca United States

ISBN: (纸本)089791662X

In this paper, we describe the program structure tree (PST), a hierarchical representation of program structure based on single entry single exit (SESE) regions of the control flow graph. We give a linear-time algorithm for finding SESE regions and for building the PST of arbitrary control flow graphs (including irreducible ones). Next, we establish a connection between SESE regions and control dependence equivalence classes, and show how to use the algorithm to find control regions in linear time. Finally, we discuss some applications of the PST. Many control flow algorithms, such as construction of Static Single Assignment form, can be speeded up by applying the algorithms in a divide-and-conquer style to each SESE region on its own. The PST is also used to speed up data flow analysis by exploiting `sparsity'. Experimental results from the Perfect Club and SPEC89 benchmarks confirm that the PST approach finds and exploits program structure.

关键词： Structured programming

来源：评论

学校读者我要写书评

暂无评论

Rematerialization

Rematerialization

引用

acm sigplan '92 conference on programming language design and implementation, pldi 1992

作者： Briggs, Preston Cooper, Keith D. Torczon, Linda Rice Univ Houston TX United States

ISBN: (纸本)0897914759

This paper examines a problem that arises during global register allocation - rematerialization. If a value cannot be kept in a register, the allocator should recognize when it is cheaper to recompute the value (rematerialize it) than to store and reload it. Chaitin's original graph-coloring allocator handled simple instances of this problem correctly. This paper details a general solution to the problem and presents experimental evidence that shows its importance. Our approach is to tag individual values in the procedure's SSA graph with information specifying how it should be spilled. We use a variant of Wegman and Zadeck's sparse simple constant algorithm to propagate tags throughout the graph. The allocator then splits live ranges into values with different tags. This isolates those values that can be easily rematerialized from values that require general spilling. We modify the base allocator to use this information when estimating spill costs and introducing spill code. Our presentation focuses on rematerialization in the context of Chaitin's allocator;however, the problem arises in any global allocator. We believe that our approach will work in other allocators - while the details of implementation will vary, the key insights should carry over directly.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Context-Free language Reachability via Skewed Tabulation

引用

PROCEEDINGS OF THE acm ON programming languageS-PacmPL 2024年第PLDI期8卷 1830-1853页

作者： Lei, Yuxiang Bossut, Camille Sui, Yulei Zhang, Qirun Univ New South Wales Sydney NSW Australia Georgia Inst Technol Atlanta GA USA

Context-free language reachability (CFL-reachability) is a prominent model for formulating program analysis problems. Almost all CFL-reachability algorithms are based on the Reps-Horwitz-Sagiv (RHS) tabulation. In essence, the RHS tabulation, based on normalized context-free grammars, is similar to the CYK algorithm for CFL-parsing. Consider a normalized rule S ::= A B and a CFL-reachability problem instance of computing S-edges in the input graph. The RHS tabulation obtains all summary edges (i.e., S-, A-, and B-edges) based on the grammar rules. However, many A- and B-edges are wasted because only a subset of those edges eventually contributes to generating S-edges in the input graph. This paper proposes a new tabulation strategy for speeding up CFL-reachability by eliminating wasted and unnecessary summary edges. We particularly focus on recursive nonterminals. Our key technical insight is that the wasted edge generations and insertions caused by recursive nonterminals can be avoided by modifying the parse trees either statically (by transforming the grammar) or dynamically (using a specialized online CFL-reachability solver). For example, if a recursive nonterminal B, generated by a rule B ::= B X, appears on the right-hand side of a rule S ::= A B, we can make S recursive (by introducing a new rule S ::= S X) and eliminate the original recursive rule (B ::= B X). Due to the rule S ::= S X, the shapes of the parse trees associated with the left-hand-side nonterminal S become more "skewed". Thus, we name our approach skewed tabulation for CFL-reachability. Skewed tabulation can significantly improve the scalability of CFL-reachability by reducing wasted and unnecessary summary edges. We have implemented skewed tabulation and applied the corresponding CFL-reachability algorithm to an alias analysis, a value-flow analysis, and a taint analysis. Our extensive evaluation based on SPEC 2017 benchmarks yields promising results. For the three client analyses, CFL-reacha

关键词： CFL-reachability tabulation schemes performance

来源：评论

学校读者我要写书评

暂无评论

Pointer analysis for programs with structures and casting

Proceedings of the ACM SIGPLAN Conference on Programming Lan...

引用

Proceedings of the acm sigplan conference on programming language design and implementation (pldi) 1999年 91-103页

作者： Yong, Suan Hsi Horwitz, Susan Reps, Thomas Univ of Wisconsin-Madison Madison WI United States

Type casting allows a program to access an object as if it had a type different from its declared type. This complicates the design of a pointer-analysis algorithm that treats structure fields as separate objects;therefore, some previous pointer-analysis algorithms `collapse' a structure into a single variable. The disadvantage of this approach is that it can lead to very imprecise points-to information. Other algorithms treat each field as a separate object based on its offset and size. While this approach leads to more precise results, the results are not portable because the memory layout of structures is implementation dependent. This paper first describes the complications introduced by type casting, then presents a tunable pointer-analysis framework for handling structures in the presence of casting. Different instances of this framework produce algorithms with different levels of precision, portability, and efficiency. Experimental results from running our implementations of four instances of this framework show that (i) it is important to distinguish fields of structures in pointer analysis, but (ii) making conservative approximations when casting is involved usually does not cost much in terms of time, space, or the precision of the results.

关键词： Computer programming languages

来源：评论

学校读者我要写书评

暂无评论

Abstractions for recursive pointer data structures. Improving the analysis and transformation of imperative programs

Abstractions for recursive pointer data structures. Improvin...

引用

acm sigplan '92 conference on programming language design and implementation, pldi 1992

作者： Hendren, Laurie J. Hummel, Joseph Nicolau, Alexandru McGill Univ

ISBN: (纸本)0897914759

Even though impressive progress has been made in the area of optimizing and parallelizing programs with arrays, the application of similar techniques to programs with pointer data structures has remained difficult. In this paper we introduce a new approach that leads to improved analysis and transformation of programs with recursively-defined pointer data structures. Our approach is based on a mechanism for the Abstract Description of Data Structures (ADDS), which makes explicit the important properties, such as dimensionality, of pointer data structures. Numerous examples demonstrate that ADDS definitions are both natural to specify and flexible enough to describe complex, cyclic pointer data structures. We discuss how an abstract data structure description can improve program analysis by presenting an analysis approach that combines an alias analysis technique, path matrix analysis, with information available from an ADDS declaration. Given this improved alias analysis technique, we provide a concrete example of applying a software pipelining transformation to loops involving pointer data structures.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Adding trace matching with free variables to AspectJ

Adding trace matching with free variables to AspectJ

引用

OOPSLA'05 - 20th Annual acm conference on Object-Oriented programming, Systems, languages, and Applications

作者： Allan, Chris Avgustinov, Pavel Christensen, Aske Simon Hendren, Laurie Kuzins, Sascha Lhoták, Ondřej De Moor, Oege Sereni, Damien Sittampalam, Ganesh Tibble, Julian Programming Tools Group University of Oxford United Kingdom BRICS University of Aarhus Denmark Sable Research Group McGill University Montreal Canada

An aspect observes the execution of a base program;when certain actions occur, the aspect runs some extra code of its own. In the AspectJ language, the observations that an aspect can make are confined to the current action: it is not possible to directly observe the history of a computation. Recently, there have been several interesting proposals for new history-based language features, most notably by Douence et al. and by Walker and Viggers. In this paper, we present a new history-based language feature called tracematches that enables the programmer to trigger the execution of extra code by specifying a regular pattern of events in a computation trace, We have fully designed and implemented tracematches as a seamless extension of AspectJ. A key innovation in our tracematch approach is the introduction of free variables in the matching patterns. This enhancement enables a whole new class of applications in which events can be matched not only by the event kind, but also by the values associated with the free variables, We provide several examples of applications enabled by this feature. After introducing and motivating the idea of tracematches via examples, we present a detailed semantics of our language design, and we derive an implementation from that semantics. The implementation has been realised as an extension of the abc compiler for AspectJ. Copyright 2005 acm.

关键词： Formal languages

来源：评论

学校读者我要写书评

暂无评论

Inlining java native calls at runtime 05

Inlining java native calls at runtime

引用

First acm/USENIX International conference on Virual Execution Environments, VEE 05

作者： Stepanian, Levon Brown, Angela Demke Kielstra, Allan Koblents, Gita Stoodley, Kevin Dept. of Computer Science University of Toronto Toronto Ont.

ISBN: (纸本)1595930477

We introduce a strategy for inlining native functions into Java™ applications using a JIT compiler. We perform further optimizations to transform inlined callbacks into semantically equivalent lightweight operations. We show that this strategy can substantially reduce the overhead of performing JNI calls, while preserving the key safety and portability properties of the JNI. Our work leverages the ability to store statically-generated IL alongside native binaries, to facilitate native inlining at Java callsites at JIT compilation time. Preliminary results with our prototype implementation show speedups of up to 93X when inlining and callback transformation are combined. Copyright 2005 acm.

关键词： Java programming language

来源：评论

学校读者我要写书评

暂无评论

Relaxing SIMD control flow constraints using loop transformations

Relaxing SIMD control flow constraints using loop transforma...

引用

acm sigplan '92 conference on programming language design and implementation, pldi 1992

作者： Hanxleden, Reinhard v. Kennedy, Ken Rice Univ Houston TX United States

ISBN: (纸本)0897914759

Many loop nests in scientific codes contain a parallelizable outer loop but have an inner loop for which the number of iterations varies between different iterations of the outer loop. When running this kind of loop nest on a SIMD machine, the SIMD-inherent restriction to single program counter common to all processors will cause a performance degradation relative to comparable MIMD implementations. This problem is not due to limited parallelism or bad load balance, it is merely a problem of control flow. This paper presents a loop transformation, which we call loop flattening, that overcomes this limitation by letting each processor advance to the next loop iteration containing useful computation, if there is such an iteration for the given processor. We study a concrete example derived from a molecular dynamics code and compare performance results for flattened and unflattened versions of this kernel on two SIMD machines, the CM-2 and the DECmpp 12000. We then evaluate loop flattening from the compiler's perspective in terms of applicability, cost, profitability, and safety. We conclude with arguing that loop flattening, whether performed by the programmer or by the compiler, introduces negligible overhead and can significantly improve the performance of scientific codes for solving irregular problems.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：