This paper describes a method for compiling programs using interprocedural register allocation. A strategy for handling programs built from multiple modules is presented, as well as algorithms for global variable prom...
详细信息
ISBN:
(纸本)9780897913645
This paper describes a method for compiling programs using interprocedural register allocation. A strategy for handling programs built from multiple modules is presented, as well as algorithms for global variable promotion and register spill code motion. These algorithms attempt to address some of the shortcomings of previous interprocedural register allocation strategies. Results are given for an implementation on a single register file RISC-based architecture.
FNC-2 is a new attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. Its development at INRIA started in 1986, and a first running prototype is available since early ...
详细信息
ISBN:
(纸本)0897913647
FNC-2 is a new attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. Its development at INRIA started in 1986, and a first running prototype is available since early 1989. Its most important features are: efficient exhaustive and incremental visit-sequence-based evaluation of strongly (absolutely) non-circular AGs;extensive space optimizations;a specially-designed AG-description language, with provisions for true modularity;portability and versatility of the generated evaluators;complete environment for application development. This paper briefly describes the design and implementation of FNC-2 and its peripherals. Then preliminary experience with the system is reported.
The need for searching a space of solutions appears often. Many problems, such as iteration over a dynamically created domain, can be expressed most naturally using a generate-and-process style. Serial programming lan...
详细信息
ISBN:
(纸本)9780897913645
The need for searching a space of solutions appears often. Many problems, such as iteration over a dynamically created domain, can be expressed most naturally using a generate-and-process style. Serial programminglanguages typically support solutions of these problems by providing some form of generators or backtracking.A parallel programminglanguage is more demanding since it needs to be able to express parallel generation and processing of elements. Failure driven computation is no longer sufficient and neither is multiple-assignment to generated *** describe the replicator control operator used in the high level parallel programminglanguage ALLOY. The replicator control operator provides a new view of generators which deals with these problems.
While logic programminglanguages offer a great deal of scope for parallelism, there is usually some overhead associated with the execution of goals in parallel because of the work involved in task creation and schedu...
详细信息
ISBN:
(纸本)0897913647
While logic programminglanguages offer a great deal of scope for parallelism, there is usually some overhead associated with the execution of goals in parallel because of the work involved in task creation and scheduling. In practice, therefore, the 'granularity' of a goal, i.e. an estimate of the work available under it, should be taken into account when deciding whether or not to execute a goal concurrently as a separate task. This paper describes a method for estimating the granularity of a goal at compile time. The runtime overhead associated with our approach is usually quite small, and the performance improvements resulting from the incorporation of grainsize control can be quite good. This is shown by means of experimental results.
This paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. The primary objective of the positioning is to reduce the overhea...
详细信息
ISBN:
(纸本)0897913647
This paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. The primary objective of the positioning is to reduce the overhead of the instruction memory hierarchy. After initial investigation in the literature, we decided to implement two prototypes for the Hewlett-Packard Precision Architecture (PA-RISC). The first, built on top of the linker, positions code based on whole procedures. This prototype has the ability to move procedures into an order that is determined by a 'closest is best' strategy. The algorithms we implemented are described through examples in this paper. The performance improvements from our work are also summarized in various tables and charts.
We have designed and implemented a fast breakpoint facility. Breakpoints are usually thought of as a feature of an interactive debugger, in which case the breakpoints need not be particularly fast. In our environment ...
详细信息
ISBN:
(纸本)0897913647
We have designed and implemented a fast breakpoint facility. Breakpoints are usually thought of as a feature of an interactive debugger, in which case the breakpoints need not be particularly fast. In our environment breakpoints are often used for non-interactive information gathering;for example, procedure call count and statement execution count profiling. When used non-interactively, breakpoints should be as fast as possible, so as to perturb the execution of the program as little as possible. Even in interactive debuggers, a conditional breakpoint facility would benefit from breakpoints that could transfer to the evaluation of the condition rapidly, and continue expeditiously if the condition were not satisfied. Such conditional breakpoints could be used to check assertions, etc. Program advising could also make use of fast breakpoints. Examples of advising include tracing, timing, and even animation, all of which should be part of an advanced programming environment.
Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of...
详细信息
ISBN:
(纸本)0897913647
Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of any fixed precision. Hence the IEEE Standard for Binary Floating-Point Arithmetic does not require the result of such a conversion to be the best approximation. This paper presents an efficient algorithm that always finds the best approximation. The algorithm uses a few extra bits of precision to compute an IEEE-conforming approximation while testing an intermediate result to determine whether the approximation could be other than the best. If the approximation might not be the best, then the best approximation is determined by a few simple operations on multiple-precision integers, where the precision is determined by the input. When using 64 bits of precision to compute IEEE double precision results, the algorithm avoids higher-precision arithmetic over 99% of the time.
Several recent code generators [4,5,6,8] use dagrewriting rules to accomplish both code generation and peephole optimization, and they compile these rules into hard code to generate code quickly. The chop system [6], ...
详细信息
ISBN:
(纸本)0897913647
Several recent code generators [4,5,6,8] use dagrewriting rules to accomplish both code generation and peephole optimization, and they compile these rules into hard code to generate code quickly. The chop system [6], for example, runs twice as fast as both pcc and the GNU C compiler gcc on a Sun 3/50 system and generates comparable code. These figures are for entire compilers;the code generators themselves run about seven times faster than comparable code generators. This paper describes a new system, currently under development, that further increases the speed of automatically-generated retargetable code generation. It offers two principal advantages over its predecessors.
Program slices are useful in debugging, testing, maintenance, and understanding of programs. The conventional notion of a program slice, the static slice, is the set of all statements that might affect the value of a ...
详细信息
ISBN:
(纸本)0897913647
Program slices are useful in debugging, testing, maintenance, and understanding of programs. The conventional notion of a program slice, the static slice, is the set of all statements that might affect the value of a given variable occurrence. In this paper, we investigate the concept of the dynamic slice consisting of all statements that actually affect the value of a variable occurrence for a given program input. The sensitivity of dynamic slicing to particular program inputs makes it more useful in program debugging and testing than static slicing. Several approaches for computing dynamic slices are examined. The notion of a Dynamic Dependence Graph and its use in computing dynamic slices is discussed. The Dynamic Dependence Graph may be unbounded in length;therefore, we introduce the economical concept of a Reduced Dynamic Dependence Graph, which is proportional in size to the number of dynamic slices arising during the program execution.
This paper presents a type system for logic programs that supports parametric polymorphism and subtypes. This system follows most knowledge representation and object-oriented schemes in that subtyping is name-based, i...
详细信息
ISBN:
(纸本)9780897913645
This paper presents a type system for logic programs that supports parametric polymorphism and subtypes. This system follows most knowledge representation and object-oriented schemes in that subtyping is name-based, i.e., τ1 is considered to be a subtype of τ2 iff it is declared as such. We take this as a fundamental principle in the sense that type declarations have the form of subtype constraints. Types are assigned meaning by viewing such constraints as Horn clauses that, together with a few basic axioms, define a subtype predicate. This technique provides a (least) model for types and, at the same time, a sound and complete proof system for deriving subtypes. Using this proof system, we define well-typedness conditions which ensure that a logic program/query respects a set of predicate types. We prove that these conditions are consistent in the sense that every atom of every resolvent produced during the execution of a well-typed program is consistent with its type.
暂无评论