The proceedings contain 28 papers. The topics discussed include: efficient building and placing of gating functions;avoiding conditional branches by code replication;accurate static branch prediction by value range pr...
ISBN:
(纸本)0897916972
The proceedings contain 28 papers. The topics discussed include: efficient building and placing of gating functions;avoiding conditional branches by code replication;accurate static branch prediction by value range propagation;improving balanced scheduling with compiler optimizations that increase instruction-level parallelism;selective specialization for object-oriented languages;corpus-based static branch prediction;flow-sensitive interprocedural constant propagation;efficient context-sensitive pointer analysis for c programs;simple and effective link-time optimization of modula-3 program;APT: a data structure for optimal control dependence computation;implementation of the data-flow synchronous language signal;scheduling and mapping: software pipelining in the presence of structural hazards;register allocation using lazy saves, eager restores, and greedy shuffling;context-insensitive alias analysis reconsidered;a type-based compiler for standard ML;unifying data and control transformations for distributed shared-memory machines;storage assignment to decrease code size;optimizing parallel programs with explicit synchronization;the LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization;and the power of assignment motion.
This paper presents the techniques used for the compilation of the data-flow, synchronous language SIGNAL. The key feature of the compiler is that it performs formal calculus on systems of boolean equations. The origi...
详细信息
Recent work on alias analysis in the presence of pointers has concentrated on context-sensitive interprocedural analyses, which treat multiple calls to a single procedure independently rather than constructing a singl...
详细信息
ISBN:
(纸本)9780897916974
Recent work on alias analysis in the presence of pointers has concentrated on context-sensitive interprocedural analyses, which treat multiple calls to a single procedure independently rather than constructing a single approximation to a procedure's effect on all of its callers. While context-sensitive modeling offers the potential for greater precision by considering only realizable call-return paths, its empirical benefits have yet to be measured. This paper compares the precision of a simple, efficient, context-insensitive points-to analysis for the C programminglanguage with that of a maximally context-sensitive version of the same analysis. We demonstrate that, for a number of pointer-intensive benchmark programs, context-insensitivity exerts little to no precision penalty. We also describe techniques for using the output of context-insensitive analysis to improve the efficiency of context-sensitive analysis without affecting precision.
This paper proposes an efficient technique for con-extsensitive pointer analysis that is applicable to real C programs. For efficiency, we summarize the effects of procedures using partial tran$er func(ions. A partial...
详细信息
Compile-time type information should be valuable in efficient compilation of statically typed functional languages such as Standard ML. But how should type-directed compilation work in real compilers, and how much per...
详细信息
Dynamic dispatching is a major source of run-time overhead in object-oriented languages, due both to the direct cost of method lookup and to the indirect effect of preventing other optimizations. To reduce this overhe...
详细信息
ISBN:
(纸本)9780897916974
Dynamic dispatching is a major source of run-time overhead in object-oriented languages, due both to the direct cost of method lookup and to the indirect effect of preventing other optimizations. To reduce this overhead, optimizing compilers for object-oriented languages analyze the classes of objects stored in program variables, with the goal of bounding the possible classes of message receivers enough so that the compiler can uniquely determine the target of a message send at compile time and replace the message send with a direct procedure call. Specialization is one important technique for improving the precision of this static class information: by compiling multiple versions of a method, each applicable to a subset of the possible argument classes of the method, more precise static information about the classes of the method's arguments is obtained. Previous specialization strategies have not been selective about where this technique is applied, and therefore tended to significantly increase compile time and code space usage, particularly for large applications. In this paper, we present a more general framework for specialization in object-oriented languages and describe a goal-directed specialization algorithm that makes selective decisions to apply specialization to those cases where;it provides the highest benefit. Our results show that our algorithm improves the performance of a group of sizeable programs by 65% to 275% while increasing compiled code space requirements by only 4% to 10%. Moreover, when compared to the previous state-of-the-art specialization scheme, our algorithm improves performance by 11% to 67% while simultaneously reducing code space requirements by 65% to 73%.
The proceedings contain 30 papers on programminglanguages. Topics include languagedesign, data structures, codes, mathemtical techniques, errors, error correction, computation theory, program compiling and program o...
详细信息
ISBN:
(纸本)089791662X
The proceedings contain 30 papers on programminglanguages. Topics include languagedesign, data structures, codes, mathemtical techniques, errors, error correction, computation theory, program compiling and program optimization.
Program slices have potential uses in many software engineering applications. Traditional slicing algorithms, however, do not work correctly on programs that contain explicit jump statements. Two similar algorithms we...
详细信息
ISBN:
(纸本)089791662X
Program slices have potential uses in many software engineering applications. Traditional slicing algorithms, however, do not work correctly on programs that contain explicit jump statements. Two similar algorithms were proposed recently to alleviate this problem. Both require the flowgraph and the program dependence graph of the program to be modified. In this paper, we propose an alternative algorithm that leaves these graphs intact and uses a separate graph to store the additional required information. We also show that this algorithm permits an extremely efficient, conservative adaptation for use with programs that contain only `structured' jump statements.
Object-oriented programs are difficult to optimize because they execute many dynamically-dispatched calls. These calls cannot easily be eliminated because the compiler does not know which callee will be invoked at run...
详细信息
ISBN:
(纸本)089791662X
Object-oriented programs are difficult to optimize because they execute many dynamically-dispatched calls. These calls cannot easily be eliminated because the compiler does not know which callee will be invoked at runtime. We have developed a simple technique that feeds back type information from the runtime system to the compiler. With this type feedback, the compiler can inline any dynamically-dispatched call. Our compiler drastically reduces the call frequency of a suite of large SELF applications (by a factor of 3.6) and improves performance by a factor of 1.7. We believe that type feedback could significantly reduce call frequencies and improve performance for most other object-oriented languages (statically-typed or not) as well as for languages with type-dependent operations such as generic arithmetic.
Type analysis of Prolog is of primary importance for high-performance compilers, since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates to name a...
详细信息
ISBN:
(纸本)089791662X
Type analysis of Prolog is of primary importance for high-performance compilers, since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates to name a few. However, these optimizations often require a sophisticated type inference system capable of inferring disjunctive and recursive types and hence expensive in computation time. The purpose of this paper is to describe a type analysis system for Prolog based on abstract interpretation and type graphs (i.e. disjunctive rational trees) with this functionality. The system (about 15,000 lines of C) consists of the combination of a generic fixpoint algorithm, a generic pattern domain, and a type graph domain. The main contribution of the paper is to show that this approach can be engineered to be practical for medium-sized programs without sacrificing accuracy. The main technical contributions to achieve this result are (1) a novel widening operator for type graphs which appears to be accurate and effective in keeping the sizes of the graphs, and hence the computation time, reasonably small;(2) the use of the generic pattern domain to obtain a compact representation of equality constraints between subterms and to factor out sure structural information.
暂无评论