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.
Constraint logic programming (CLP) is a generalization of logic programming where unification is replaced by constraint solving as the basic operation of the language. The combination of constraint solving and nondete...
详细信息
ISBN:
(纸本)089791662X
Constraint logic programming (CLP) is a generalization of logic programming where unification is replaced by constraint solving as the basic operation of the language. The combination of constraint solving and nondeterminism (approximated by backtracking) makes these languages appealing for a variety of combinatorial search problems. Existing CLP languages support backtracking by generalizing traditional Prolog implementations: modifications to the constraint system are trailed and restored on backtracking. Although simple and efficient, trailing may be very demanding in memory space, since the constraint system may potentially be saved at each choice point. This paper proposes a fundamentally new implementation scheme for backtracking in CLP languages over linear (rational or real) arithmetic. The new scheme, called semantic backtracking, does not use trailing but rather exploits the semantics of the constraints to undo the effect of newly added constraints. Semantic backtracking reduces the space complexity by an order of magnitude compared to implementations based on trailing and makes space complexity essentially independent of the number of choice points. In addition, semantic backtracking introduces negligible space and time overhead on deterministic programs. The price for this improvement is an increase in backtracking time, although constraint-solving time may actually decrease. The scheme has been implemented as part of a complete CLP system CLP (RLin) and compared analytically and experimentally with an optimized trailing implementation. Experimental results indicate that semantic backtracking produces significant reduction in memory space, while keeping the time overhead reasonably small.
The array update problem in the implementation of a purely functional language is the following: once an array is updated, both the original array and the newly updated one must be preserved to maintain referential tr...
详细信息
ISBN:
(纸本)0897916433
The array update problem in the implementation of a purely functional language is the following: once an array is updated, both the original array and the newly updated one must be preserved to maintain referential transparency. Previous approaches have mainly based on the detection or enforcement of single-threaded accesses to an aggregate, by means of compiler-time analyses or language restrictions. These approaches cannot deal with aggregates which are updated in a multi-threaded manner. Baker's shallow binding scheme can be used to implement multi-threaded functional arrays. His scheme, however, can be very expensive if there are repeated alternations between long binding paths. We design a scheme that fragments binding paths randomly. The randomization scheme is on-line, simple to implement, and its expected performance comparable to that of the optimal off-line solutions. All this is achieved without using compiler-time analyses, and without restricting the languages. The expected performance of the randomization scheme is analyzed in details, and some preliminary results are shown. Applications of the randomization technique to other functional aggregates, as well as its implications, are briefly outlined.
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 algorit...
详细信息
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.
This conference proceedings contains 29 papers on the design, development, implementation and use of programminglanguages, with emphasis on experimental results and practical experience. Topics discussed include the ...
详细信息
ISBN:
(纸本)0897915984
This conference proceedings contains 29 papers on the design, development, implementation and use of programminglanguages, with emphasis on experimental results and practical experience. Topics discussed include the design and implementation of data breakpoints, isolation and analysis of optimization errors, accommodation of may-alias information in static single assignment form, abstract debugging of higher-order imperative languages, a practical data flow framework for array reference analysis, global optimizations for parallelism and data locality, communication optimization and code generation for distributed memory machines, programmable syntax macros, compiling real-time programs into schedulable code, improving the cache locality of memory allocation, using lifetime predictors to improve memory allocation performance, the implementation of type classes, the theory of compilation with continuations, register allocation with instruction scheduling, lifetime-sensitive modulo scheduling, load/store range analysis for global register allocation, and balanced instruction scheduling in the case of uncertain memory latency.
We present a new programming paradigm called Communicating Reactive Processes or CRP that unifies the capabilities of asynchronous and synchronous concurrent programminglanguages. Asynchronous languages such as CSP, ...
详细信息
ISBN:
(纸本)0897915607
We present a new programming paradigm called Communicating Reactive Processes or CRP that unifies the capabilities of asynchronous and synchronous concurrent programminglanguages. Asynchronous languages such as CSP, OCCAM, or ADA are well-suited for distributed algorithms;their processes are loosely coupled and communication takes time. The ESTEREL synchronous language is dedicated to reactive systems;its processes are tightly coupled and deterministic, communication being realized by instantaneous broadcasting. Complex applications such as process or robot control require to couple both forms of concurrency, which is the object of CRP. A CRP program consists of independent locally reactive ESTEREL nodes that communicate with each other by CSP rendezvous. CRP faithfully extends both ESTEREL and CSP and adds new possibilities such as precise local watchdogs on rendezvous. We present the design of CRP, its semantics, a translation into classical process calculi for program verification, an application example, and implementation issues.
We describe Charm++, an object oriented portable parallel programminglanguage based on C++. Its design philosophy, implementation, sample applications and their performance on various parallel machines are described....
详细信息
The conference materials contain 33 papers. The topics covered include experience with functional programming applications, theory and implementation of types, storage reclamation, semantics analysis of imperative ext...
详细信息
ISBN:
(纸本)089791595X
The conference materials contain 33 papers. The topics covered include experience with functional programming applications, theory and implementation of types, storage reclamation, semantics analysis of imperative extensions, compiling and performance evaluation, languagedesign, compiler optimization, static analysis, functional algorithms and partial evaluation.
暂无评论