bluuebunny/crossref_metadata_2025 huggingface dataset:
Scrap your boilerplate
Authors: Lämmel Ralf , Jones Simon Peyton
Published: November 2005

We describe a design pattern for writing programs that traverse data structures built from rich mutually-recursive data types. Such programs often have a great deal of "boilerplate" code that simply walks the structure, hiding a small amount of "real" code that constitutes the reason for the traversal.Our technique allows most of this boilerplate to be written once and for all, or even generated mechanically, leaving the programmer free to concentrate on the important part of the algorithm. These generic programs are much more adaptive when faced with data structure evolution because they contain many fewer lines of type-specific code.Our approach is simple to understand, reasonably efficient, and it handles all the data types found in conventional functional programming languages. It makes essential use of rank-2 polymorphism, an extension found in some implementations of Haskell. Further it relies on a simple type-safe cast operator.
Deciding validity in a spatial logic for trees
Authors: Calcagno Cristiano , Cardelli Luca , Gordon Andrew D.
Published: November 2005

(MATH) We consider a propositional spatial logic for finite trees. The logic includes
A
???? Par
B
(tree composition),
A
????
B
(the implication induced by composition), and
O
(the unit of composition). We show that the satisfaction and validity problems are equivalent, and decidable. The crux of the argument is devising a finite enumeration of trees to consider when deciding whether a spatial implication is satisfied. We introduce a sequent calculus for the logic, and show it to be sound and complete with respect to an interpretation in terms of satisfaction. Finally, we describe a complete proof procedure for the sequent calculus. We envisage applications in the area of logic-based type systems for semistructured data. We describe a small programming language based on this idea.
The ergo attribute system
Authors: Nord Robert L. , Pfenning Frank
Published: November 2005

The Ergo Attribute System was designed to satisfy the requirements for attributes in a language-generic program derivation environment. It consists of three components: (1) an abstract data type of attributes that guarantees attribute consistency, (2) a Common Lisp implementation which combines demand-driven and incremental attribute evaluation in a novel way while allowing for attribute persistence over many generations of a program, and (3) an attribute-grammar compiler producing code based on this abstract data type from a high-level specification. Our experience with three major applications (one being the attribute-grammar compiler itself) confirms that the overhead in storing and accessing attributes incurred by our implementation scheme is more than offset by the gains from the demand-driven, incremental, and persistent nature of attribution.
TEAM: a support environment for testing, evaluation, and analysis
Authors: Clarke Lori A. , Richardson Debra J. , Zeil Steven J.
Published: November 2005

Current research indicates that software reliability needs to be achieved through the careful integration of a number of diverse testing and analysis techniques. To address this need, the TEAM environment has been designed to support the integration of and experimentation with an ever growing number of software testing and analysis tools. To achieve this flexibility, we exploit three design principles: component technology so that common underlying functionality is recognized; generic realizations so that these common functions can be instantiated as diversely as possible; and language independence so that tools can work on multiple languages, even allowing some tools to be applicable to different phases of the software lifecycle. The result is an environment that contains building blocks for easily constructing and experimenting with new testing and analysis techniques. Although the first prototype has just recently been implemented, we feel it demonstrates how modularity, genericity, and language independence further extensibility and integration.
A unifying model for consistent distributed software development environments
Authors: Walpole J. , Blair G. S. , Malik J. , Nicol J. R.
Published: November 2005

The increase in size and complexity of software projects over recent years has lead to the need for Software Development Environments (SDEs). SDEs are intended to provide assistance in the development of large software systems involving teams of people. It is generally agreed that SDE's should be built on a distributed base. However, the distribution of computer systems introduces several problems which make it very difficult to maintain the
consistency
of data.

To ensure that changes to data are made consistently the concept of atomic transactions is usually adopted. However, existing transaction mechanisms are unsuitable for use in a distributed SDE. Furthermore, transactions are not the only mechanism concerned with controlling changes to the SDE database. The control of change is also a task for version and configuration control mechanisms. Traditionally, the functions of version control, configuration control and transactions have been treated as separate, unrelated issues.

This paper presents a new model which unifies all three concepts in a distributed SDE. Mechanisms for supporting the new model are presented and the application of the model to the Cosmos Distributed SDE is discussed.
An overview of PCTE and PCTE+
Authors: Boudier Gerard , Gallo Ferdinando , Minot Regis , Thomas Ian
Published: November 2005

The PCTE project has defined a Public Tool Interface on which Software Engineering Environments can be constructed. The interface definition was put into the public domain in September 1986 and several implementations on several machines now exist. The PCTE+ project was set up to define a Public Tool Interface, based on the PCTE work, that could also serve for the development of defense and other high-security applications. This paper summarises the current status of PCTE activity, presents the principal concepts of PCTE and the evolutions that are being proposed in the PCTE+ project.
Automating comments
Authors: Robillard P.-N.
Published: November 2005

This paper addresses the problem of source code documentation. Source code documentation has two components: the description of the statement and the description of the steps required to go from the specifications in natural language to programming language statements. We propose a model that provides a different mechanism for each form of documentation. A tool is used to implement and automate this approach. Results show that this approach provides a systematic and coherent mechanism for source code documentation. Productivity is increased and maintenance effort is greatly reduced.
AUTO STAR—a software development system
Authors: Zhu M. Y.
Published: November 2005

This report summarizes the AUTO STAR project. AUTO STAR is a software development system which accepts the algebraic specification of a given software system and produces an Ada implementation of that system."In many applications, algorithms play almost no role, and certainly present almost no problem. The real problem is the mass of detailed requirements; and the only solution is the discovery or invention of general rules and abstractions which cover the many thousands of cases with as few exceptions as possible. This is what makes a program short, simple, and reliable, as compared with one which attempts to treat every case as a special case. But the discovery of such general rules and classifications demands at least the same inventive genius as that of a classificatory biologist, or the grammarian of a natural language, or even a theoretical physicist".
Next: the elimination of Goto-patches?
Authors: Jonsson D.
Published: November 2005

It is argued that the elimination of goto-statements within the context of structured programming has often been achieved through the introduction of 'goto-patches'. Seven common goto-patches are identified and exemplified. Finally, it is suggested that the control structures used in 'pancode' make it possible to eliminate goto-patches as well as goto-statements.
Concurrent object-oriented real-times systems research
Authors: Kafura D.
Published: November 2005

This research investigates how to build real-time systems using a concurrent object-oriented programming language based on the actor model [Agha86]. The close parallels between the characteristics of concurrent object oriented languages and real-time systems motivates this investigation. Successful use of the actor model in closely related problem domains [Bake78, Barr87, Atha87, Yone87, Dela88] also suggests that this a fruitful line of inquiry. The research is composed of three interrelated projects:• designing a concurrent object-oriented programming language, named ACT++, for real-time system applications.• using ACT++ in representative real-time applications.• constructing a distributed real-time kernel, named REACT, to support the execution of ACT++ applications.The language and the kernel are distinctive because they (1) use fine-medium grained concurrency, termed ultralight processes, (2) support the combination of inheritance with the actor model of computation, and (3) are based on automatic, distributed, incremental real-time garbage collection of concurrent objects - removing error-prone management concerns from developers and unifying process (time) and memory management. An extended "white paper" describing these projects is available from the author on request.
An integrated approach to parallel program debugging and performance analysis onlarge-scale multiprocessors
Authors: Fowler Robert J. , LeBlanc Thomas J. , Mellor-Crummey John M.
Published: November 2005

One of the most serious problems in the development cycle of large-scale parallel programs is the lack of tools for debugging and performance analysis. We are addressing the problem on large-scale, shared-memory multiprocessors. We have developed a dynamic, fine-grain characterization of parallel program executions based on a partial order of accesses to shared objects. This characterization forms the basis for an extensible, integrated toolkit for parallel program debugging and performance analysis. Tools in the toolkit include an interactive debugger, a graphical execution browser, performance analysis packages, and a programmable interface for user queries. Using our integrated toolkit approach, programmers can interactively analyze the behavior of parallel programs in much the same way interactive debuggers and profilers are used to analyze the behavior of sequential programs.
Partial orders for parallel debugging
Authors: Fidge C. J.
Published: November 2005

Parallel programs differ from sequential programs primarily in that the temporal relationships between events are only partially defined. However, for a given distributed computation, debugging utilities typically linearize the observed set of events into a total ordering, thus losing information and allowing potentially capturable temporal errors to escape detection. We explore use of the partially ordered relation “happened before” to augment both centralized and distributed parallel debuggers to ensure that such errors are always detected and that the results produced by the debugger are unaffected by the non-determinism inherent in the partial ordering. This greatly reduces the number of tests required during debugging. Assertions are based on time intervals, rather than treating events as dimensionless points.
Modified structured decision table and its complexity
Authors: Misra A. K. , Chaudhary B. D.
Published: November 2005

A modified structured decision table (MSDT) is introduced [7]
which is a modification of Structured decision Table (SDT) [6] to
document stages of the topdown program development. The level
definition of MSDT is kept such as to maintain conformation with
the top-down methodology of program construction. Further, the MSDT
besides functionally converting any flowchart, exposes the
construction of a program by considering one basic program
construct at a time.

In a Conventional Decision Tables (CDT) the conditions are
assumed to be independent of execution of action and the fact that
execution of an action may affect the outcome of a condition test
is not considered. It is also not taken into account that there may
be an action defining a variable without which condition test is
not possisble. But in case of MSDT such an assumption is not made
and the construction of a MSDT proceeds in such a way that these
facts are always taken into account.

Further in a CDT conditions can be tested in any sequence
independent of their occurences, where as in a MSDT conditions are
tested in a sequence totally dependent of their occurences, and
there exists a definite ordering in testing of conditions in
MSDT.

It has been shown that MSDT is also capable of representing both
structured as well as unstructured flowcharts or programs without
any change in the basic notions used for the construction of MSDT.
It is possible to convert unstructured flowcharts where
unstructuredness is due to intersecting Ifs, Loop with multiple
exit and multiple entry and Loop with mid exit, to MSDT without any
change in execution sequence with c+1 levels where c is the number
of basic program constructs in a program or flowchart. It is also
possible to obtain CDT or decision table suggested in [4] from
SDT.

The two complexity measures defined in [4] for decision tables
are level complexity (∧) which is the number of values its
sequencing variable assumes when ∞ is not counted and
cyclomatic complexity (VT) is equal to
ρ−∧ where ρ is the number of
rules in a decision table. Applying these measures, complexities of
different example decision tables has also been evaluated and it
has been shown that complexity of a MSDT of program or flowchart is
equal to the sum of complexities of the basic program constructs
available in the program or flowchart. Further the level and
cyclomatic complexities of these MSDT's compares very favourably
with other decision tables.
Developments in Pascal-FC
Authors: Davies G. L.
Published: November 2005

This paper reports additions to Pascal-FC, a language designed to provide students of concurrent programming with practical experience of a variety of interprocess communication primitives. An earlier report in this journal described the facilities for using semaphores, monitors and an occam/CSP-style rendezvous. To these facilities have now been added an Ada-style rendezvous. An improved post-mortem dump has also been included.
The effectiveness of error seeding
Authors: Meek B. , Siu K. K.
Published: November 2005

Randomised error seeding is a technique which can be used to evaluate the ability of language processors to detect and report errors in source programs. The advantages and disadvantages of the method are discussed, and various strategies for using it presented. The lessons learned from experiments in using it on selected Pascal and Prolog systems are summarised, and suggestions for further research are offered.
Regular attribute grammars and finite state machines
Authors: Chapman N. P.
Published: November 2005

A regular attribute grammar is an attribute grammar with an underlying context-free grammar which is right or left linear. The restriction to regular underlying grammars restricts the possible dependencies between attributes; this in turn permits efficient algorithms for attribute evaluation. An algorithm for performing attribute evaluation in parallel with a single scan of the input by a deterministic finite state machine is developed. Special cases of regular attribute grammars for which the algorithm uses very little space are identified. Several examples are included.
Random number generators are chaotic
Authors: Herring C. , Palmore J. I.
Published: November 2005

We observe that pseudo-random number generators, familiar to all programmers, are examples of deterministic chaotic dynamical systems. We discuss the implications of this finding and compare computer generation of pseudo-random numbers to the theoretical ideal of a (noncomputable) random sequence.
Treating failure as value
Authors: Wong L. , Ooi B. C.
Published: November 2005

Two's complement notation is a popular binary numeral representation of integers. However, this representation is asymmetric and partial. The consequences are complications like overflowing and underflowing. We try to re-interpret the asymmetry of two's complement numbers to provide a better representation of integers. Our effort leads us to consider the treatment of failure as value rather than as state. The result of this approach goes beyond the solution of our original problem and gives rise to a rather elegant treatment of failure.
A generative approach to Universal Cross Assembler design
Authors: Chiu P. P. K. , Fu S. T. K.
Published: November 2005

A new approach to Universal Cross Assembler design is proposed. New assemblers can be generated easily from the assembly language syntax, instruction set, addressing modes, binary code pattern of the instructions, directives, and the output file format. There are no constraints on the syntax, addressing modes, and instruction code lengths. It achieves high generality, extendibility and portability by considering assemblers as high level language compilers, using high level language development tools, YACC and LEX on UNIX. Using this approach, two prototype assemblers, one for 8086 and one for 68000, have been implemented on both UNIX and MSDOS. Their performance and comparison with existing assemblers are discussed in the paper.
FWEB: a literate programming system for Fortran8x
Authors: Avenarius A. , Oppermann S.
Published: November 2005

The new FWEB system applies the concept of literate programming to the FORTRAN8X language. Its design and implementation provided an opportunity to field-test WEB's applicability and provoked some reflections on its underlying concepts.
Dependence analysis for pointer variables
Authors: Horwitz S. , Pfeiffer P. , Reps T.
Published: November 2005

Our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. We are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as Lisp and Pascal. We have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependencies of a program written in such a language. Our algorithms account for destructive updates to fields of a structure and thus are
not
limited to the cases where all structures are trees or acyclic graphs; they
are
applicable to programs that build cyclic structures.

Our technique extends an analysis method described by Jones and Muchnick that determines an approximation to the actual layouts of memory that can arise at each program point during execution. We extend the domain used in their abstract interpretation so that the (abstract) memory locations are labeled by the program points that set their contents. Data dependencies are then determined from these memory layouts according to the component labels found along the access paths that must be traversed during execution to evaluate the program's statements and predicates.

For structured programming constructs, the technique can be extended to distinguish between loop-carried and loop-independent dependencies, as well as to determine lower bounds on minimum distances for loop-carried dependencies.
Experience with CST: programming and implementation
Authors: Horwat W. , Chien A. A. , Dally W. J.
Published: November 2005

CST is a programming language based on Smalltalk-80
2
that supports concurrency using locks, asynchronous messages, and distributed objects. In this paper, we describe CST: the language and its implementation. Example programs and initial programming experience with CST are described. Our implementation of CST generates native code for the J-machine, a fine-grained concurrent computer. Some compiler optimizations developed in conjunction with that implementation are also described.
Type inference in the presence of type abstraction
Authors: Boehm H.-J.
Published: November 2005

A number of recent programming language designs incorporate a type checking system based on the Girard-Reynolds polymorphic λ-calculus. This allows the construction of general purpose, reusable software without sacrificing compile-time type checking. A major factor constraining the implementation of these languages is the difficulty of automatically inferring the lengthy type information that is otherwise required if full use is made of these languages. There is no known algorithm to solve any natural and fully general formulation of this “type inference” problem. One very reasonable formulation of the problem is known to be undecidable.

Here we define a restricted version of the type inference problem and present an efficient algorithm for its solution. We argue that the restriction is sufficiently weak to be unobtrusive in practice.
Register allocation via clique separators
Authors: Gupta R. , Soffa M. L. , Steele T.
Published: November 2005

Although graph coloring is widely recognized as an effective technique for global register allocation, the overhead can be quite high, not only in execution time but also in memory, as the size of the interference graph needed in coloring can become quite large. In this paper, we present an algorithm based upon a result by R. Tarjan regarding the colorability of graphs which are decomposable using clique separators, that improves on the overhead of coloring. The algorithm first partitions program code into code segments using the notion of clique separators. The interference graphs for the code partitions are next constructed one at a time and colored independently. The colorings for the partitions are combined to obtain a register allocation for the program code. The technique presented is both efficient in space and time because the graph for only a single code segment needs to be constructed and colored at any given point in time. The partitioning of a graph using clique separators increases the likelihood of obtaining a coloring without spilling and hence an efficient allocation of registers for the program. For straight line code an optimal allocation for the entire program code can be obtained from optimal allocations for individual code segments. In the presence of branches, optimal allocation along one execution path and a near optimal allocation along alternative paths can be potentially obtained. Since the algorithm is highly efficient, it eliminates the need for a local register allocation phase.
Experiences creating a portable cedar
Authors: Atkinson R. , Demers A. , Hauser C. , Jacobi C. , Kessler P. , Weiser M.
Published: November 2005

Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and runtime types. Neither the language nor the environment was originally intended to be portable, and for many years ran only on D-machines at PARC and a few other locations in Xerox. We recently re-implemented the language to make it portable across many different architectures. Our strategy was, first, to use machine-dependent C code as an intermediate language, second, to create a language-independent layer known as the Portable Common Runtime, and third, to write a relatively large amount of Cedar-specific runtime code in a subset of Cedar itself. By treating C as an intermediate code we are able to achieve reasonably fast compilation, very good eventual machine code, and all with relatively small programmer effort. Because Cedar is a much richer language than C, there were numerous issues to resolve in performing an efficient translation and in providing reasonable debugging. These strategies will be of use to many other porters of high-level languages who may wish to use C as an assembler language without giving up either ease of debugging or high performance. We present a brief description of the Cedar language, our portability strategy for the compiler and runtime, our manner of making connections to other languages and the Unix
*
operating system, and some measures of the performance of our “Portable Cedar”.
A laboratory for teaching object oriented thinking
Authors: Beck K. , Cunningham W.
Published: November 2005

It is difficult to introduce both novice and experienced procedural programmers to the anthropomorphic perspective necessary for object-oriented design. We introduce CRC cards, which characterize objects by class name, responsibilities, and collaborators, as a way of giving learners a direct experience of objects. We have found this approach successful in teaching novice programmers the concepts of objects, and in introducing experienced programmers to complicated existing designs.
An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes
Authors: Chambers C. , Ungar D. , Lee E.
Published: November 2005

We have developed and implemented techniques that double the performance of dynamically-typed object-oriented languages. Our SELF implementation runs twice as fast as the fastest Smalltalk implementation, despite SELF's lack of classes and explicit variables.

To compensate for the absence of classes, our system uses implementation-level
maps
to transparently group objects cloned from the same prototype, providing data type information and eliminating the apparent space overhead for prototype-based systems. To compensate for dynamic typing, user-defined control structures, and the lack of explicit variables, our system dynamically compiles
multiple versions
of a source method, each
customized
according to its receiver's map. Within each version the type of the receiver is fixed, and thus the compiler can statically bind and
inline
all messages sent to self.
Message splitting
and
type prediction
extract and preserve even more static type information, allowing the compiler to inline many other messages. Inlining dramatically improves performance and eliminates the need to hard-wire low-level methods such as +,==, and ifTrue:.

Despite inlining and other optimizations, our system still supports interactive programming environments. The system traverses internal dependency lists to invalidate all compiled methods affected by a programming change. The debugger reconstructs inlined stack frames from compiler-generated debugging information, making inlining invisible to the SELF programmer.
Playground: an object-oriented simulation system with agent rules for children of all ages
Authors: Fenton J. , Beck K.
Published: November 2005

Programming languages for children have been limited by primitive control and data structures, indirect user interfaces, and artificial syntax. Playground is a child-oriented programming language that uses objects to structure data and has a modular control structure, a direct-manipulation user interface, and an English-like syntax. Integrating Playground into the curriculum of a classroom of 9- to 10-year-olds has given us valuable insights from the programs intended users, and confirmed many of our design decisions.
Vamp: the Aldus application framework
Authors: Ferrel P. J. , Meyer R. F.
Published: November 2005

This paper describes an application framework, called Vamp, which supports Interactive Compound Documents and applications as collections of Interactive Objects. Aldus developed Vamp as a practical experiment in solving several software engineering and project management problems including software reusability, portability, and management of large program teams. Vamp is written in C ++ to run on the Macintosh and Microsoft Windows. This paper discusses the decisions that led to the architecture of Vamp and what Aldus stands to gain by its use.
DSM: an object-relationship modeling language
Authors: Shah A. V. , Hamel J. H. , Borsari R. A. , Rumbaugh J. E.
Published: November 2005

The Data Structure Manager (DSM) combines object-oriented programming with semantic data modeling concepts in the context of the C language. DSM is a full-featured object-oriented language which includes single and multiple inheritance, class descriptor objects, metaclasses, choice of method binding time, error handling, persistent objects, modularity, and an interactive interpreter in an efficient manner. In addition, DSM supports the association and aggregation relationships as part of the Object Modeling Technique (OMT) used for conceptual design. DSM has been used since 1986 to build a variety of research and production-quality software such as an advanced CAF/CAD system.
Prototyping a real-time embedded system in Smalltalk
Authors: Barry B. M.
Published: November 2005

This paper presents a case study of AMEP, a prototype ESM signal processor which has been implemented in Smalltalk using an actor-based design methodology, Arguments for choosing an OOPS for implementing such applications are reviewed. AMEP is a large system which includes both hard real-time and knowledge-based subsystems. Extensive software metrics are presented for each subsystem and used to compare the characteristics of code designed for different purposes. For example, analysis of this data suggests that knowledge-based applications may be more difficult to port to an object-based language such as Ada than hard real-time systems. Team programming, productivity, documentation standards and other software engineering issues are also addressed.
Metaclass compatibility
Authors: Graube N.
Published: November 2005

Metaclasses provide control of object description, method compilation and more generally class behaviour. Consequently, they have been widely used in languages such as Smalltalk-80 or more recently CLOS by both users and implementers. Due to their powerful control of instances, careless inheritance of classes with different metaclasses can lead to unsound or inefficient implementations of instance methods. Using examples, we will pin-point these problems. Then we will introduce compatibility rules which need to be fulfilled by metaclasses of inherited classes in order to allow reasonable instance method description.
Language integration in the common language runtime
Authors: Hamilton Jennifer
Published: November 2005

The Common Language Runtime (CLR) is language and platform-neutral, and provides the underlying infrastructure for the Microsoft .NET Framework. A key innovation in the CLR is its support for multiple programming languages, enabling programming language integration at the runtime level to a much greater degree than is currently possible.
An algorithm for parallel incremental compaction
Authors: Ben-Yitzhak Ori , Goft Irit , Kolodner Elliot K. , Kuiper Kean , Leikehman Victor
Published: November 2005

Garbage collectors of the mark-sweep family may suffer from memory fragmentation and require the use of compaction. Known compaction methods are expensive and work while program activity is stopped, so that compaction is often a major contributor to garbage collection pause times. We present a parallel incremental compaction algorithm that reduces pause times by working in parallel and evacuating a part of the heap when the program threads are stopped for garbage collection. Our algorithm works with collectors based on mark-sweep, including mostly concurrent collectors. We have implemented a prototype of our algorithm as part of the garbage collector in the IBM JVM. Measurements of our prototype show that even with the most simple-minded policies, e.g., for choosing the area to evacuate, parallel incremental compaction can successfully reduce maximum garbage collection pause times with a minimal performance penalty.
Automatic pool allocation for disjoint data structures
Authors: Lattner Chris , Adve Vikram
Published: November 2005

This paper presents an analysis technique and a novel program transformation that can enable powerful optimizations for entire linked data structures. The fully automatic transformation converts ordinary programs to use pool (aka region) allocation for heap-based data structures. The transformation relies on an efficient link-time interprocedural analysis to identify disjoint data structures in the program, to check whether these data structures are accessed in a type-safe manner, and to construct a Disjoint Data Structure Graph that describes the connectivity pattern within such structures. We present preliminary experimental results showing that the data structure analysis and pool allocation are effective for a set of pointer intensive programs in the Olden benchmark suite. To illustrate the optimizations that can be enabled by these techniques, we describe a novel pointer compression transformation and briefly discuss several other optimization possibilities for linked data structures.
Link-time optimization of address calculation on a 64-bit architecture
Authors: Srivastava Amitabh , Wall David W.
Published: November 2005

Compilers for new machines with 64-bit addresses must generate code that works when the memory used by the program is large. Procedures and global variables are accessed indirectly via
global address tables
, and calling conventions include code to establish the addressability of the appropriate tables. In the common case of a program that does
not
require a lot of memory, all of this can be simplified considerably, with a corresponding reduction in program size and execution time.

We have used our link-time code modification system OM to perform program transformations related to global address use on the Alpha AXP. Though simple, many of these are
whole-program
optimizations that can be done only when we can see the entire program at once, so link-time is an ideal occasion to perform them.

This paper describes the optimizations performed and shows their effects on program size and performance. Relatively modest transformations, possible without moving code, improve the performance of SPEC benchmarks by an average of 1.5%. More ambitious transformations, requiring an understanding of program structure that is thorough but not difficult at link-time, can do even better, reducing program size by 10% or more, and improving performance by an average of 3.8%.

Even a program compiled monolithically with interprocedural optimization can benefit nearly as much from this technique, if it contains statically-linked pre-compiled library code. When the benchmark sources were compiled in this way, we were still able to improve their performance by 1.35% with the modest transformations and 3.4% with the ambitious transformations.
GIVE-N-TAKE—a balanced code placement framework
Authors: von Hanxleden Reinhard , Kennedy Ken
Published: November 2005

GIVE-N-TAKE is a code placement framework which uses a general producer-consumer concept. An advantage of GIVE-N-TAKE over existing partial redundancy elimination techniques is its concept of production
regions
, instead of single locations, which can be beneficial for general latency hiding. GIVE-N-TAKE guaranteed
balanced
production, that is, each production will be started and stopped once. The framework can also take advantage of production coming “for free,” as induced by side effects, without disturbing balance. GIVE-N-TAKE can place production either before or after consumption, and it also provides the option to hoist code out of potentially zero-trip loop (nest) constructs. GIVE-N-TAKE uses a fast elimination method based on Tarjan intervals, with a complexity linear in the program size in most cases.

We have implemented GIVE-N-TAKE as part of a Fortran D compiler prototype, where it solves various communication generation problems associated with compiling data-parallel languages onto distributed-memory architectures.
Counting solutions to Presburger formulas
Authors: Pugh William
Published: November 2005

We describe methods that are able to count the number of integer solutions to selected free variables of a Presburger formula, or sum a polynomial over all integer solutions of selected free variables of a Presburger formula. This answer is given symbolically, in terms of symbolic constants (the remaining free variables in the Presburger formula).

For example, we can create a Presburger formula who's solutions correspond to the iterations of a loop. By counting these, we obtain an estimate of the execution time of the loop.

In more complicated applications, we can create Presburger formulas who's solutions correspond to the distinct memory locations or cache lines touched by a loop, the flops executed by a loop, or the array elements that need to be communicated at a particular point in a distributed computation. By counting the number of solutions, we can evaluate the computation/memory balance of a computation, determine if a loop is load balanced and evaluate message traffic and allocate message buffers.
Energy-balanced task allocation for collaborative processing in networked embedded systems
Authors: Yu Yang , Prasanna Viktor K.
Published: November 2005

In this paper, we study the problem of allocating a real-time application onto a set of homogeneous processing elements connected by a single-hop wireless network. A periodic application consisting of a set of communicating tasks is considered. Each element is equipped with discrete dynamic voltage scaling for exploring the energy-latency tradeoffs. The time and energy costs of both computation and communication activities are considered. The goal is to balance the energy dissipation of the elements during each period of the application with respect to the remaining energy of elements, such that the system lifetime is maximized. An Integer Linear Programming (ILP) formulation is first developed, which can be solved to obtain the optimal solution. We then propose an efficient 3-phase heuristic. Experimental results show that for small scale problems, the performance of the heuristic achieves up to 85% of the system lifetime obtained by the ILP-based approach. For large scale problems, the performance of the heuristic shows an improvement of 120-250\% in the system lifetime compared with the case where no voltage scaling is used. Further, we present two extensions of our approaches that consider multiple communication channels and techniques for exploring the energy-latency tradeoffs of the communication activities.
Linear analysis and optimization of stream programs
Authors: Lamb Andrew A. , Thies William , Amarasinghe Saman
Published: November 2005

As more complex DSP algorithms are realized in practice, there is an increasing need for high-level stream abstractions that can be compiled without sacrificing efficiency. Toward this end, we present a set of aggressive optimizations that target linear sections of a stream program. Our input language is StreamIt, which represents programs as a hierarchical graph of autonomous filters. A filter is linear if each of its outputs can be represented as an affine combination of its inputs. Linearity is common in DSP components; examples include FIR filters, expanders, compressors, FFTs and DCTs.We demonstrate that several algorithmic transformations, traditionally hand-tuned by DSP experts, can be completely automated by the compiler. First, we present a linear extraction analysis that automatically detects linear filters from the C-like code in their work function. Then, we give a procedure for combining adjacent linear filters into a single filter, as well as for translating a linear filter to operate in the frequency domain. We also present an optimization selection algorithm, which finds the sequence of combination and frequency transformations that will give the maximal benefit.We have completed a fully-automatic implementation of the above techniques as part of the StreamIt compiler, and we demonstrate a 450% performance improvement over our benchmark suite.
Meta optimization
Authors: Stephenson Mark , Amarasinghe Saman , Martin Martin , O'Reilly Una-May
Published: November 2005

Compiler writers have crafted many heuristics over the years to approximately solve NP-hard problems efficiently. Finding a heuristic that performs well on a broad range of applications is a tedious and difficult process. This paper introduces Meta Optimization, a methodology for automatically fine-tuning compiler heuristics. Meta Optimization uses machine-learning techniques to automatically search the space of compiler heuristics. Our techniques reduce compiler design complexity by relieving compiler writers of the tedium of heuristic tuning. Our machine-learning system uses an evolutionary algorithm to automatically find effective compiler heuristics. We present promising experimental results. In one mode of operation Meta Optimization creates application-specific heuristics which often result in impressive speedups. For hyperblock formation, one optimization we present in this paper, we obtain an average speedup of 23% (up to 73%) for the applications in our suite. Furthermore, by evolving a compiler's heuristic over several benchmarks, we can create effective, general-purpose heuristics. The best general-purpose heuristic our system found for hyperblock formation improved performance by an average of 25% on our training set, and 9% on a completely unrelated test set. We demonstrate the efficacy of our techniques on three different optimizations in this paper: hyperblock formation, register allocation, and data prefetching.
Checking and inferring local non-aliasing
Authors: Aiken Alex , Foster Jeffrey S. , Kodumal John , Terauchi Tachio
Published: November 2005

In prior work [15] we studied a language construct restrict that allows programmers to specify that certain pointers are not aliased to other pointers used within a lexical scope. Among other applications, programming with these constructs helps program analysis tools locally recover strong updates, which can improve the tracking of state in flow-sensitive analyses. In this paper we continue the study of restrict and introduce the construct confine. We present a type and effect system for checking the correctness of these annotations, and we develop efficient constraint-based algorithms implementing these type checking systems. To make it easier to use restrict and confine in practice, we show how to automatically infer such annotations without programmer assistance. In experiments on locking in 589 Linux device drivers, confine inference can automatically recover strong updates to eliminate 95% of the type errors resulting from weak updates.
Predicting whole-program locality through reuse distance analysis
Authors: Ding Chen , Zhong Yutao
Published: November 2005

Profiling can accurately analyze program behavior for select data inputs. We show that profiling can also predict program locality for inputs other than profiled ones. Here locality is defined by the distance of data reuse. Studying whole-program data reuse may reveal global patterns not apparent in short-distance reuses or local control flow. However, the analysis must meet two requirements to be useful. The first is efficiency. It needs to analyze all accesses to all data elements in full-size benchmarks and to measure distance of any length and in any required precision. The second is predication. Based on a few training runs, it needs to classify patterns as regular and irregular and, for regular ones, it should predict their (changing) behavior for other inputs. In this paper, we show that these goals are attainable through three techniques: approximate analysis of reuse distance (originally called LRU stack distance), pattern recognition, and distance-based sampling. When tested on 15 integer and floating-point programs from SPEC and other benchmark suites, our techniques predict with on average 94% accuracy for data inputs up to hundreds times larger than the training inputs. Based on these results, the paper discusses possible uses of this analysis.
A compiler framework for speculative analysis and optimizations
Authors: Lin Jin , Chen Tong , Hsu Wei-Chung , Yew Pen-Chung , Ju Roy Dz-Ching , Ngai Tin-Fook , Chan Sun
Published: November 2005

Speculative execution, such as control speculation and data speculation, is an effective way to improve program performance. Using edge/path profile information or simple heuristic rules, existing compiler frameworks can adequately incorporate and exploit control speculation. However, very little has been done so far to allow existing compiler frameworks to incorporate and exploit data speculation effectively in various program transformations beyond instruction scheduling. This paper proposes a speculative SSA form to incorporate information from alias profiling and/or heuristic rules for data speculation, thus allowing existing program analysis frameworks to be easily extended to support both control and data speculation. Such a general framework is very useful for EPIC architectures that provide checking (such as
advanced load address table
(ALAT) [10]) on data speculation to guarantee the correctness of program execution. We use SSAPRE [21] as one example to illustrate how to incorporate data speculation in those important compiler optimizations such as partial redundancy elimination (PRE), register promotion, strength reduction and linear function test replacement. Our extended framework allows both control and data speculation to be performed on top of SSAPRE and, thus, enables more aggressive speculative optimizations. The proposed framework has been implemented on Intel's Open Research Compiler (ORC). We present experimental data on some SPEC2000 benchmark programs to demonstrate the usefulness of this framework and how data speculation benefits partial redundancy elimination.
A region-based compilation technique for a Java just-in-time compiler
Authors: Suganuma Toshio , Yasue Toshiaki , Nakatani Toshio
Published: November 2005

Method inlining and data flow analysis are two major optimization components for effective program transformations, however they often suffer from the existence of rarely or never executed code contained in the target method. One major problem lies in the assumption that the compilation unit is partitioned at method boundaries. This paper describes the design and implementation of a region-based compilation technique in our dynamic compilation system, in which the compiled regions are selected as code portions without rarely executed code. The key part of this technique is the region selection, partial inlining, and region exit handling. For region selection, we employ both static heuristics and dynamic profiles to identify rare sections of code. The region selection process and method inlining decision are interwoven, so that method inlining exposes other targets for region selection, while the region selection in the inline target conserves the inlining budget, leading to more method inlining. Thus the inlining process can be performed for parts of a method, not for the entire body of the method. When the program attempts to exit from a region boundary, we trigger recompilation and then rely on on-stack replacement to continue the execution from the corresponding entry point in the recompiled code. We have implemented these techniques in our Java JIT compiler, and conducted a comprehensive evaluation. The experimental results show that the approach of region-based compilation achieves approximately 5% performance improvement on average, while reducing the compilation overhead by 20 to 30%, in comparison to the traditional function-based compilation techniques.