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.
In an earlier paper, the author discussed the use of Ada to implement the internal program representation for an Ada software reengineering system. While many of Ada's features were used to advantage in the implem...
详细信息
Object Oriented technology, especially Object Oriented programming (OOP), has recently become very popular in a number of contexts, and for various applications. However, there have been relatively few reports of usin...
详细信息
A way opinions and its embodiment as a rating algorithm for an end-user personnel qualification system is described. The system is tested for clerks cert@ing for the State Ministry and is customised for Nuclear Power ...
详细信息
The paper describes an APL2 soIution for a real life problem of a large eompauy. The problem is to make a decision on establishing a new fully automated warehouse for delive of business papers. Large scale of the proj...
详细信息
The proceedings contain 48 papers. The topics discussed include: Ada 9x tagged types and their implementation in GNAT;features of the Gnu Ada runtime library;working with Ada 9X classes;quality guidelines = designer m...
ISBN:
(纸本)0897916662
The proceedings contain 48 papers. The topics discussed include: Ada 9x tagged types and their implementation in GNAT;features of the Gnu Ada runtime library;working with Ada 9X classes;quality guidelines = designer metrics;run-time check elimination for Ada 9X;smart recompilation and the GNAT compiler;lessons learned in implementing a team review process;integrating GNAT into GCC;the GNAT compilation model;the GNAT project: a GNU-Ada 9X compiler;an object-oriented approach to software process modeling and definition;software project reporting: management, measurement, and process improvement;the STARS process engine: language and architecture to support process capture and multi-user execution;delegation: dynamic specialization;Ada-based programminglanguage course in Moscow State University;educating educators: lessons in adding Ada to a small school curriculum;profiling in an object-oriented design environment that supports Ada 9x and Ada 83 code generation;selecting a software development process;Easy-Sim: using Ada 9x in a graphics system software architecture;implementing internal program representations with Ada and Ada 9x;and design of GUIs from a programming perspective.
暂无评论