bluuebunny/crossref_metadata_2025 huggingface dataset:
From simulation to practice
Authors: Lopes Ricardo , Castro Luís Fernando , Costa Vítor Santos
Published: November 2005

Progress in Prolog applications requires ever better performance and scalability from Prolog implementation technology. Most modern Prolog systems are emulator-based. Best performance thus requires both good emulator design and good memory performance. Indeed, Prolog applications can often spend hundreds of megabytes of data, but there is little work on understanding and quantifying the interactions between Prolog programs and the memory architecture of modern computers.In a previous study of Prolog systems we have shown through simulation that Prolog applications usually, but not always, have good locality, both for deterministic and non-deterministic applications. We also showed that performance may strongly depend on garbage collection and on database operations. Our analysis left two questions unanswered: how well do our simulated results holds on actual hardware, and how much did our results depend on a specific configuration? In this work we use several simulation parameters and profiling counters to improve understanding of Prolog applications. We believe that our analysis is of interest to any system implementor who wants to understand his or her own system's memory performance.
Multi-objective
abstract data type refinement
for mapping tables in telecom network applications
Authors: Ykman-Couvreur Ch. , Lambrecht J. , van der Togt A. , Catthoor F.
Published: November 2005

We present a new multi-objective exploration method at the system level to select customized implementations for mapping tables, dynamically allocated, as encountered in telecom network, database, and multimedia applications. Our method fits in the context of embedded system synthesis for such applications, and it enables the optimization of the system-level memory management of these applications. To this end it mainly aims at trading off the average memory footprint, number of memory accesses, and memory power. Compared with existing methods, for large mapping tables, 90% (resp. 80%) of the average memory footprint (resp. power) can be saved, without decreasing the performance.
A proposal for a new hardware cache monitoring architecture
Authors: Schulz Martin , Tao Jie , Jeitner Jürgen , Karl Wolfgang
Published: November 2005

The analysis of the memory access behavior of applications, an essential step for a successful cache optimization, is a complex task. It needs to be supported with appropriate tools and monitoring facilities. Currently, however, users can only rely on either simulation based approaches, which deliver a large degree of detail but are restricted in their applicability, or on hardware counters embedded into processors, which allow to keep track of very few, mostly global events and hence only provide limited data.In this work a proposal for novel hardware monitoring facility is presented which exhibits both the details of traditional simulations and the low--overhead of hardware counters. Like the latter approach, it is also targeted towards an implementation within the processor for a direct and non--intrusive access to caches and memory busses. Unlike traditional counters, however, it delivers a detailed picture of the complete memory access behavior of applications. This is achieved by generating so--called memory access histograms, which show access frequencies in relation to the applications address space. Such spatial memory access information can then be used for efficient program optimization by focusing on the code and data segments which were found to exhibit a poor cache behavior.
VLIW compilation techniques in a superscalar environment
Authors: Ebcioglu Kemal , Groves Randy D. , Kim Ki-Chang , Silberman Gabriel M. , Ziv Isaac
Published: November 2005

We describe techniques for converting the intermediate code representation of a given program, as generated by a modern compiler, to another representation which produces the same run-time results, but can run faster on a superscalar machine. The algorithms, based on novel parallelization techniques for
Very Long Instruction Word (VLIW)
architectures, find and place together independently executable operations that may be far apart in the original code. i.e., they may be separated by many conditional branches or belong to different iterations of a loop. As a result, the functional units in the superscalar are presented with more work that can proceed in parallel, thus achieving higher performance than the approach of using hardware instruction dispatch techniques alone.

While general scheduling techniques improve performance by removing idle pipeline cycles, to further improve performance on a superscalar with only a few functional units requires a reduction in the pathlength. We have designed a set of new algorithms for reducing pathlength and removing stalls due to branches, namely speculative load-store motion out of loops, unspeculation, limited combining, basic block expansion, and prolog tailoring. These algorithms were implemented in a prototype version of the IBM RS/6000 xlc compiler and have shown significant improvement in SPEC integer benchmarks on the IBM POWER machines.

Also, we describe a new technique to obtain profiling information with low overhead, and some applications of profiling directed feedback, including scheduling heuristics, code reordering and branch reversal.
Effective partial redundancy elimination
Authors: Briggs Preston , Cooper Keith D.
Published: November 2005

Partial redundancy elimination is a code optimization with a long history of literature and implementation. In practice, its effectiveness depends on issues of naming and code shape. This paper shows that a combination of
global reassociation
and
global value numbering
can increase the effectiveness of partial redundancy elimination. By imposing a discipline on the choice of names and the shape of expressions, we are able to expose more redundancies.

As part of the work, we introduce a new algorithm for global reassociation of expressions. It uses global information to reorder expressions, creating opportunities for other optimizations. The new algorithm generalizes earlier work that ordered FORTRAN array address expressions to improve otpimization [25].
Memory access coalescing
Authors: Davidson Jack W. , Jinturkar Sanjay
Published: November 2005

As microprocessor speeds increase, memory bandwidth is increasingly the performance bottleneck for microprocessors. This has occurred because innovation and technological improvements in processor design have outpaced advances in memory design. Most attempts at addressing this problem have involved hardware solutions. Unfortunately, these solutions do little to help the situation with respect to current microprocessors. In previous work, we developed, implemented, and evaluated an algorithm that exploited the ability of newer machines with wide-buses to load/store multiple floating-point operands in a single memory reference. This paper describes a general code improvement algorithm that transforms code to better exploit the available memory bandwidth on existing microprocessors as well as wide-bus machines. Where possible and advantageous, the algorithm coalesces narrow memory references into wide ones. An interesting characteristic of the algorithm is that some decisions about the applicability of the transformation are made at run time. This dynamic analysis significantly increases the probability of the transformation being applied. The code improvement transformation was implemented and added to the repertoire of code improvements of an existing retargetable optimizing back end. Using three current architectures as evaluation platforms, the effectiveness of the transformation was measured on a set of compute- and memory-intensive programs. Interestingly, the effectiveness of the transformation varied significantly with respect to the instruction-set architecture of the tested platform. For one of the tested architectures, improvements in execution speed ranging from 5 to 40 percent were observed. For another, the improvements in execution speed ranged from 5 to 20 percent, while for yet another, the transformation resulted in slower code for all programs.
ATOM
Authors: Srivastava Amitabh , Eustace Alan
Published: November 2005

ATOM (Analysis Tools with OM) is a single framework for building a wide range of customized program analysis tools. It provides the common infrastructure present in all code-instrumenting tools; this is the difficult and time-consuming part. The user simply defines the tool-specific details in instrumentation and analysis routines. Building a basic block counting tool like Pixie with ATOM requires only a page of code.

ATOM, using OM link-time technology, organizes the final executable such that the application program and user's analysis routines run in the same address space. Information is directly passed from the application program to the analysis routines through simple procedure calls instead of inter-process communication or files on disk. ATOM takes care that analysis routines do not interfere with the program's execution, and precise information about the program is presented to the analysis routines at all times. ATOM uses no simulation or interpretation.

ATOM has been implemented on the Alpha AXP under OSF/1. It is efficient and has been used to build a diverse set of tools for basic block counting, profiling, dynamic memory recording, instruction and data cache simulation, pipeline simulation, evaluating branch prediction, and instruction scheduling.
Cache performance of garbage-collected programs
Authors: Reinhold Mark B.
Published: November 2005

As processor speeds continue to improve relative to main-memory access times, cache performance is becoming an increasingly important component of program performance. Prior work on the cache performance of garbage-collected programs either argues or assumes that conventional garbage-collection methods will yield poor performance, and has therefore concentrated on new collection algorithms designed specifically to improve cache-level reference locality.

This paper argues to the contrary: Many programs written in garbage-collected languages are naturally well-suited to the direct-mapped caches typically found in modern computer systems. Garbage-collected programs written in a mostly-functional style should perform well when simple linear storage allocation and an infrequently-run generational compacting collector are employed; sophisticated collectors intended to improve cache performance are unlikely to be necessary. As locality becomes ever more important to program performance, programs of this kind may turn out to have a significant performance advantage over programs written in traditional languages.
A general data dependence test for dynamic, pointer-based data structures
Authors: Hummel Joseph , Hendren Laurie J. , Nicolau Alexandru
Published: November 2005

Optimizing compilers require accurate dependence testing to enable numerous, performance-enhancing transformations. However, data dependence testing is a difficult problem, particularly in the presence of pointers. Though existing approaches work well for pointers to named memory locations (i.e. other variables), they are overly conservative in the case of pointers to unnamed memory locations. The latter occurs in the context of dynamic, pointer-based data structures, used in a variety of applications ranging from system software to computational geometry to N-body and circuit simulations.

In this paper we present a new technique for performing more accurate data dependence testing in the presence of dynamic, pointer-based data structures. We will demonstrate its effectiveness by breaking false dependences that existing approaches cannot, and provide results which show that removing these dependences enables significant parallelization of a real application.
Context-sensitive interprocedural points-to analysis in the presence of function pointers
Authors: Emami Maryam , Ghiya Rakesh , Hendren Laurie J.
Published: November 2005

This paper reports on the design, implementation, and empirical results of a new method for dealing with the aliasing problem in C. The method is based on approximating the points-to relationships between accessible stack locations, and can be used to generate alias pairs, or used directly for other analyses and transformations.

Our method provides context-sensitive interprocedural information based on analysis over invocation graphs that capture all calling contexts including recursive and mutually-recursive calling contexts. Furthermore, the method allows the smooth integration for handling general function pointers in C.

We illustrate the effectiveness of the method with empirical results from an implementation in the McCAT optimizing/parallelizing C compiler.
Zero-cost range splitting
Authors: Kurlander Steven M. , Fischer Charles N.
Published: November 2005

This paper presents a new optimization technique that uses empty delay slots to improve code scheduling. We are able to split live ranges for free, by inserting spill code into empty delay slots. Splitting a live range can reduce interferences with other live ranges and can sometimes free registers. Live ranges no longer interfering with the split live range can sometimes make use of the extra register.

Our algorithm, as a final pass over the code, exploits empty delay slots that would remain unused if spill code was not inserted. This paper proposes a variety of optimizations that use the extra registers generated from live range splitting, including coalescing live ranges and improving code scheduling. We present an algorithm for improving code scheduling and present implementation results.
Efficient detection of all pointer and array access errors
Authors: Austin Todd M. , Breach Scott E. , Sohi Gurindar S.
Published: November 2005

We present a pointer and array access checking technique that provides complete error coverage through a simple set of program transformations. Our technique, based on an extended safe pointer representation, has a number of novel aspects. Foremost, it is the first technique that detects all spatial and temporal access errors. Its use is not limited by the expressiveness of the language; that is, it can be applied successfully to compiled or interpreted languages with subscripted and mutable pointers, local references, and explicit and typeless dynamic storage management, e.g., C. Because it is a source level transformation, it is amenable to both compile- and run-time optimization. Finally, its performance, even without compile-time optimization, is quite good. We implemented a prototype translator for the C language and analyzed the checking overheads of six non-trivial, pointer intensive programs. Execution overheads range from 130% to 540%; with text and data size overheads typically below 100%.
Type analysis of Prolog using type graphs
Authors: Van Hentenryck P. , Cortesi A. , Le Charlier B.
Published: November 2005

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.
Predicting the impact of optimizations for embedded systems
Authors: Zhao Min , Childers Bruce , Soffa Mary Lou
Published: November 2005

When applying optimizations, a number of decisions are made using fixed strategies, such as always applying an optimization if it is applicable, applying optimizations in a fixed order and assuming a fixed configuration for optimizations such as tile size and loop unrolling factor. While it is widely recognized that these fixed strategies may not be the most appropriate for producing high quality code, especially for embedded systems, there are no general and automatic strategies that do otherwise. In this paper, we present a framework that enables these decisions to be made based on predicting the impact of an optimization, taking into account resources and code context. The framework consists of optimization models, code models and resource models, which are integrated for predicting the impact of applying optimizations. Because data cache performance is important to embedded codes, we focus on cache performance and present an instance of the framework for cache performance in this paper. Since most opportunities for cache improvement come from loop optimizations, we describe code, optimization and cache models tailored to predict the impact of applying loop optimizations for data locality. Experimentally we demonstrate the need to selectively apply optimizations and show the performance benefit of our framework in predicting when to apply an optimization. We also show that our framework can be used to choose the most beneficial optimization when a number of optimizations can be applied to a loop nest. And lastly, we show that we can use the framework to combine optimizations on a loop nest.
Data size optimizations for java programs
Authors: Ananian C. Scott , Rinard Martin
Published: November 2005

We present a set of techniques for reducing the memory consumption of object-oriented programs. These techniques include analysis algorithms and optimizations that use the results of these analyses to eliminate fields with constant values, reduce the sizes of fields based on the range of values that can appear in each field, and eliminate fields with common default values or usage patterns. We apply these optimizations both to fields declared by the programmer and to implicit fields in the runtime object header. Although it is possible to apply these techniques to any object-oriented program, we expect they will be particularly appropriate for memory-limited embedded systems.We have implemented these techniques in the MIT FLEX compiler system and applied them to the programs in the SPECjvm98 benchmark suite. Our experimental results show that our combined techniques can reduce the maximum live heap size required for the programs in our benchmark suite by as much as 40%. Some of the optimizations reduce the overall execution time; others may impose modest performance penalties.
Generating embedded software from hierarchical hybrid models
Authors: Alur Rajeev , Ivancic Franjo , Kim Jesung , Lee Insup , Sokolsky Oleg
Published: November 2005

Benefits of high-level modeling and analysis are significantly enhanced if code can be generated automatically from a model such that the correspondence between the model and the code is precisely understood. For embedded control software,
hybrid systems
is an appropriate modeling paradigm because it can be used to specify continuous dynamics as well as discrete switching between modes. Establishing a formal relationship between the mathematical semantics of a hybrid model and the actual executions of the corresponding code is particularly challenging due to sampling and switching errors. In this paper, we describe an approach to compile the modeling language
Charon
that allows hierarchical specifications of interacting hybrid systems. We show how to exploit the semantics of
Charon
to generate code from a model in a modular fashion, and identify sufficient conditions on the model that guarantee the absence of switching errors in the compiled code. The approach is illustrated by compiling a model for coordinated motion of legs for walking onto Sony's AIBO robot.
Storage assignment optimizations through variable coalescence for embedded processors
Authors: Zhuang Xiaotong , Lau ChokSheak , Pande Santosh
Published: November 2005

Modern embedded processors with dedicated address generation unit support memory access with indirect addressing mode with auto-increment and decrement. The auto-increment/decrement mode saves address arithmetic instructions.Liao et al [2][3] categorized this problem as simple offset assignment (SOA) problem and general offset assignment (GOA) problem, which involve storage layout of variables and assignment of address registers respectively proposing heuristic solutions. Later work [6][7] proposed improvements in the performance of Liao's solution by undertaking program and storage transformations that affect access sequence.The algorithms are incorporated into and evaluated on the commercial compiler provided by Motorola to boost code generation performance on the DSP 56k chip. Compared to previous approaches, variable coalescence with program reordering reduces SOA costs by 48% and GOA (2AR) costs by 66% for Mediabench and SPEC benchmarks. Moreover, we show that our approach obtains theoretically optimal solution (zero cost) for the GOA problem in 87% of the cases with just 2 address registers and in 94% of the cases with 3 address registers.
Energy management for real-time embedded applications with compiler support
Authors: AbouGhazaleh Nevine , Childers Bruce , Mosse Daniel , Melhem Rami , Craven Matthew
Published: November 2005

Reducing device energy has become one of the most important challenges to embedded systems designers. Processors with dynamic voltage scaling permit trading performance for reduced energy consumption as a program executes. In this paper, we first present a novel hybrid scheme that uses dynamic voltage scaling to adjust the performance of embedded applications to reduce energy consumption while also meeting time constraints. Our fine grained approach uses the compiler to insert power management hints in the application code. These hints convey path specific run-time information about the program's progress to power management points invoked by the operating system that adjust processor performance. Second we present an algorithm for inserting power management hints along different program paths. Finally, we experimentally evaluate our approach and show that signi cant energy reduction can be achieved. On two embedded applications, MPEG movie decoding and automatic target recognition, our scheme reduces energy by up to 79% over no power management and by up to over 50% static power management. We also experimentally demonstrate that our scheme achieves more energy savings compared to two purely compiler directed schemes.
The design, implementation, and evaluation of a compiler algorithm for CPU energy reduction
Authors: Hsu Chung-Hsing , Kremer Ulrich
Published: November 2005

This paper presents the design and implementation of a compiler algorithm that effectively optimizes programs for energy usage using dynamic voltage scaling (DVS). The algorithm identifies program regions where the CPU can be slowed down with negligible performance loss. It is implemented as a source-to-source level transformation using the SUIF2 compiler infrastructure. Physical measurements on a high-performance laptop show that total
system
(i.e., laptop) energy savings of up to 28% can be achieved with performance degradation of less than 5% for the
SPECfp95
benchmarks. On average, the system energy and energy-delay product are reduced by 11% and 9%, respectively, with a performance slowdown of 2%. It was also discovered that the energy usage of the programs using our DVS algorithm is within 6% from the theoretical lower bound. To the best of our knowledge, this is one of the first work that evaluates DVS algorithms by physical measurements.
A comparison of empirical and model-driven optimization
Authors: Yotov Kamen , Li Xiaoming , Ren Gang , Cibulskis Michael , DeJong Gerald , Garzaran Maria , Padua David , Pingali Keshav , Stodghill Paul , Wu Peng
Published: November 2005

Empirical program optimizers estimate the values of key optimization parameters by generating different program versions and running them on the actual hardware to determine which values give the best performance. In contrast, conventional compilers use models of programs and machines to choose these parameters. It is widely believed that model-driven optimization does not compete with empirical optimization, but few quantitative comparisons have been done to date. To make such a comparison, we replaced the empirical optimization engine in ATLAS (a system for generating a dense numerical linear algebra library called the BLAS) with a model-driven optimization engine that used detailed models to estimate values for optimization parameters, and then measured the relative performance of the two systems on three different hardware platforms. Our experiments show that model-driven optimization can be surprisingly effective, and can generate code whose performance is comparable to that of code generated by empirical optimizers for the BLAS.
Static conflict analysis for multi-threaded object-oriented programs
Authors: von Praun Christoph , Gross Thomas R.
Published: November 2005

A compiler for multi-threaded object-oriented programs needs information about the sharing of objects for a variety of reasons: to implement optimizations, to issue warnings, to add instrumentation to detect access violations that occur at runtime. An Object Use Graph (OUG) statically captures accesses from different threads to objects. An OUG extends the Heap Shape Graph (HSG), which is a compile-time abstraction for runtime objects (nodes) and their reference relations (edges). An OUG specifies for a specific node in the HSG a partial order of events relevant to the corresponding runtime object(s). Relevant events include read and write access, object escape, thread start and join.OUGs have been implemented in a Java compiler. Initial experience shows that OUGs are effective to identify object accesses that potentially conflict at runtime and isolate accesses that never cause a problem at runtime. The capabilities of OUGs are compared with an advanced program analysis that has been used for lock elimination. For the set of benchmarks investigated here, OUGs report only a fraction of shared objects as conflicting and reduce the number of compile-time reports in terms of allocation sites of conflicting objects by 28--92% (average 64%). For benchmarks of up to 30 KLOC, the time taken to construct OUGs is, with one exception, in the order of seconds.The information collected in the OUG has been used to instrument Java programs with checks for object races. OUGs provide precise information about object sharing and static protection, so runtime instrumentation that checks those cases that cannot be disambiguated at compile-time is sparse, and the total runtime overhead of checking for object races is only 3--86% (average 47%).
CSSV
Authors: Dor Nurit , Rodeh Michael , Sagiv Mooly
Published: November 2005

Erroneous string manipulations are a major source of software defects in C programs yielding vulnerabilities which are exploited by software viruses. We present
C
S
tring
S
tatic
V
erifyer (CSSV), a tool that statically uncovers
all
string manipulation errors. Being a conservative tool, it reports all such errors at the expense of sometimes generating
false alarms
. Fortunately, only a small number of false alarms are reported, thereby proving that statically reducing software vulnerability is achievable. CSSV handles large programs by analyzing each procedure separately. To this end procedure
contracts
are allowed which are verified by the tool.We implemented a CSSV prototype and used it to verify the absence of errors in real code from EADS Airbus. When applied to another commonly used string intensive application, CSSV uncovered real bugs with very few false alarms.
Debugging temporal specifications with concept analysis
Authors: Ammons Glenn , Mandelin David , Bodík Rastislav , Larus James R.
Published: November 2005

Program verification tools (such as model checkers and static analyzers) can find many errors in programs. These tools need formal specifications of correct program behavior, but writing a correct specification is difficult, just as writing a correct program is difficult. Thus, just as we need methods for debugging programs, we need methods for debugging specifications.This paper describes a novel method for debugging formal, temporal specifications. Our method exploits the short program execution traces that program verification tools generate from specification violations and that specification miners extract from programs. Manually examining these traces is a straightforward way to debug a specification, but this method is tedious and error-prone because there may be hundreds or thousands of traces to inspect. Our method uses concept analysis to automatically group the traces into highly similar clusters. By examining clusters instead of individual traces, a person can debug a specification with less work.To test our method, we implemented a tool, Cable, for debugging specifications. We have used Cable to debug specifications produced by Strauss, our specification miner. We found that using Cable to debug these specifications requires, on average, less than one third as many user decisions as debugging by examining all traces requires. In one case, using Cable required only 28 decisions, while debugging by examining all traces required 224.
A static analyzer for large safety-critical software
Authors: Blanchet Bruno , Cousot Patrick , Cousot Radhia , Feret Jérome , Mauborgne Laurent , Miné Antoine , Monniaux David , Rival Xavier
Published: November 2005

We show that abstract interpretation-based static program analysis can be made efficient and precise enough to formally verify a class of properties for a family of large programs with few or no false alarms. This is achieved by refinement of a general purpose static analyzer and later adaptation to particular programs of the family by the end-user through parametrization. This is applied to the proof of soundness of data manipulation operations at the machine level for periodic synchronous safety critical embedded software.The main novelties are the design principle of static analyzers by refinement and adaptation through parametrization (Sect. 3 and 7), the symbolic manipulation of expressions to improve the precision of abstract transfer functions (Sect. 6.3), the octagon (Sect. 6.2.2), ellipsoid (Sect. 6.2.3), and decision tree (Sect. 6.2.4) abstract domains, all with sound handling of rounding errors in oating point computations, widening strategies (with thresholds: Sect. 7.1.2, delayed: Sect. 7.1.3) and the automatic determination of the parameters (parametrized packing: Sect. 7.2).
A provably sound TAL for back-end optimization
Authors: Chen Juan , Wu Dinghao , Appel Andrew W. , Fang Hai
Published: November 2005

Typed assembly languages provide a way to generate machine-checkable safety proofs for machine-language programs. But the soundness proofs of most existing typed assembly languages are hand-written and cannot be machine-checked, which is worrisome for such large calculi. We have designed and implemented a low-level typed assembly language (LTAL) with a semantic model and established its soundness from the model. Compared to existing typed assembly languages, LTAL is more scalable and more secure; it has no macro instructions that hinder low-level optimizations such as instruction scheduling; its type constructors are expressive enough to capture dataflow information, support the compiler's choice of data representations and permit typed position-independent code; and its type-checking algorithm is completely syntax-directed.We have built a prototype system, based on Standard ML of New Jersey, that compiles most of core ML to Sparc code. We explain how we were able to make the untyped back end in SML/NJ preserve types during instruction selection and register allocation, without restricting low-level optimizations and without knowledge of any type system pervading the instruction selector and register allocator.
CCured in the real world
Authors: Condit Jeremy , Harren Matthew , McPeak Scott , Necula George C. , Weimer Westley
Published: November 2005

CCured is a program transformation system that adds memory safety guarantees to C programs by verifying statically that memory errors cannot occur and by inserting run-time checks where static verification is insufficient.This paper addresses major usability issues in a previous version of CCured, in which many type casts required the use of pointers whose representation was expensive and incompatible with precompiled libraries. We have extended the CCured type inference algorithm to recognize and verify statically a large number of type casts; this goal is achieved by using physical subtyping and pointers with run-time type information to allow parametric and subtype polymorphism. In addition, we present a new instrumentation scheme that splits CCured's metadata into a separate data structure whose shape mirrors that of the original user data. This scheme allows instrumented programs to invoke external functions directly on the program's data without the use of a wrapper function.With these extensions we were able to use CCured on real-world security-critical network daemons and to produce instrumented versions without memory-safety vulnerabilities.
Static array storage optimization in MATLAB
Authors: Joisha Pramod G. , Banerjee Prithviraj
Published: November 2005

Static array storage optimization in MATLAB.
Stride prefetching by dynamically inspecting objects
Authors: Inagaki Tatsushi , Onodera Tamiya , Komatsu Hideaki , Nakatani Toshio
Published: November 2005

Software prefetching is a promising technique to hide cache miss latencies, but it remains challenging to effectively prefetch pointer-based data structures because obtaining the memory address to be prefetched requires pointer dereferences. The recently proposed stride prefetching overcomes this problem, but it only exploits
inter-iteration
stride patterns and relies on an off-line profiling method.We propose a new algorithm for stride prefetching which is intended for use in a dynamic compiler. We exploit both
inter-
and
intra-iteration
stride patterns, which we discover using an ultra-lightweight profiling technique, called
object inspection
. This is a kind of partial interpretation that only a dynamic compiler can perform. During the compilation of a method, the dynamic compiler gathers the profile information by partially interpreting the method using the actual values of parameters and causing no side effects.We evaluated an implementation of our prefetching algorithm in a production-level Java just-in time compiler. The results show that the algorithm achieved up to an
18.9%
and
25.1%
speedup in industry-standard benchmarks on the Pentium 4 and the Athlon MP, respectively, while it increased the compilation time by less than
3.0%
.
Region-based hierarchical operation partitioning for multicluster processors
Authors: Chu Michael , Fan Kevin , Mahlke Scott
Published: November 2005

Clustered architectures are a solution to the bottleneck of centralized register files in superscalar and VLIW processors. The main challenge associated with clustered architectures is compiler support to effectively partition operations across the available resources on each cluster. In this work, we present a novel technique for clustering operations based on graph partitioning methods. Our approach incorporates new methods of assigning weights to nodes and edges within the dataflow graph to guide the partitioner. Nodes are assigned weights to reflect their resource usage within a cluster, while a slack distribution method intelligently assigns weights to edges to reflect the cost of inserting moves across clusters. A multilevel graph partitioning algorithm, which globally divides a dataflow graph into multiple parts in a hierarchical manner, uses these weights to efficiently generate estimates for the quality of partitions. We found that our algorithm was able to achieve an average of 20% improvement in DSP kernels and 5% improvement in SPECint2000 for a four-cluster architecture.
A formal semantic definition of DEVIL
Authors: Luo Lei , Zhu Ming-Yuan , Zhang Qing-Li
Published: November 2005

In this paper we present a formal semantic definition of a device interface language called
DEVIL
(DEVice Interface Language). The semantic model is based on a high-order logic system supported by a mathematical theorem proof development system called
PowerEpsilon
. This work is intended for fully understanding semantics of
DEVIL
and will be used as a reference-guide in implementation project for the embedded real-time operating system δ-
OS
.
Cray Pascal
Authors: Madhavji N. H. , Wilson I. R.
Published: November 2005

This paper presents an investigation of the design decisions taken in the implementation of a compiler for Pascal on the CRAY-1 computer. The structured nature of Pascal statements and data structures is contrasted with the 'powerful computing engine' nature of the CRAY-1 hardware. The accepted views of Pascal as a simple one-pass language and the CRAY-1 as a vector processor are laid aside in favour of a multi-pass approach, taking account of the machine's scalar capabilities. The project as a whole, aims to produce highly efficient run-time code for applications likely to be programmed in Pascal. Some statistics are given to indicate the nature of such applications.
An implementation of a code generator specification language for table driven code generators
Authors: Bird Peter L.
Published: November 2005

This paper discusses an implementation of Glanville's code generator generator for producing a code generator for a production Pascal compiler on an Amdahl 470.

We successfully replaced the hand written code generator of an existing compiler with one which was produced automatically from a formal specification. This paper first outlines Glanville's original scheme, then describes extensions which were necessary for generating code for a production compiler.
A practical method for syntactic error diagnosis and recovery
Authors: Burke Michael , Fisher Gerald A.
Published: November 2005

Our goal is to develop a practical syntactic error recovery method applicable within the general framework of viable prefix parsing. Our method represents an attempt to accurately diagnose and report all syntax errors without reporting errors that are not actually present. Successful recovery depends upon accurate diagnosis of errors together with sensible “correction” or alteration of the text to put the parse back on track. The issuing of accurate and helpful diagnostics is achieved by indicating the nature of the recovery made for each error encountered. The error recovery is prior to and independent of any semantic analysis of the program. However, the method does not exclude the invocation of semantic actions while parsing or preclude the use of semantic information for error recovery.

The method assumes a framework in which an LR or LL parser, driven by the tables produced by a parser generator, maintains an input symbol buffer, state or prediction stack, and parse stack. The input symbol buffer contains part or all of the sequence of remaining input tokens, including the current token. The LR state stack is analogous to the LL prediction stack; except when restricting our attention to the LL case, prediction stack shall serve as a generic term indicating the LR state or LL prediction stack. The parse stack contains the symbols of the right hand sides that have not yet been reduced.
Semantic errors - diagnosis and repair
Authors: Johnson C W , Runciman C
Published: November 2005

In compiler technology, semantic error handling has too often used ad hoc techniques and terse messages of fixed content. In contrast, we present general models of diagnosis and repair of semantic errors and illustrate their use in the York Ada Workbench Compiler. The diagnostic model focuses upon the problem of selecting suitable information from which the programmer can locate and correct an error; following a brief discussion of an approach in which
filters
are applied to reports, and we give a more extensive account of a new approach using an
interactive diagnostic interpreter
. The repair model is based upon the idea of
plastic
nodes which are introduced into the compiler's internal representation of a program to replace
normal
nodes which are missing or erroneous.
Compiler construction using attribute grammars
Authors: Koskimies Kai , Räihä Kari-Jouko , Sarjakoski Matti
Published: November 2005

The adequacy of attribute grammars as a compiler writing tool is studied on the basis of the experiences on attribute grammars for Pascal and a subset of Euclid. A qualitative assessment of the grammars shows that the compiler oriented view in the design of an attribute grammar tends to make the grammar hard to understand. A design discipline is proposed to improve the comprehensibility of the grammar. Quantitative measurements of the automatically generated compilers suggest that an efficient compiler can be produced from an attribute grammar. To achieve this, a carefully optimized implementation of the compiler-compiler is required.
Current status of a portable LISP compiler
Authors: Griss Martin L. , Benson Eric , Hearn Anthony C.
Published: November 2005

This report describes the current status of a Portable LISP Compiler used with great success to compile Standard LISP on a variety of machines. It has also been used to provide a portable implementation base for a new LISP (PSL) on the DECSystem 20 and VAX.
The why and wherefore of the Cornell Program Synthesizer
Authors: Teitelbaum Tim , Reps Thomas , Horwitz Susan
Published: November 2005

The Cornell Program Synthesizer is a syntax-directed programming environment that has been used in introductory programming courses since June, 1979. We present our experience with the Synthesizer by introducing its main features, by presenting our basic principles of design, and by discussing important design decisions.
The implementation and experiences of a structure-oriented text editor.
Authors: Strömfors O. , Jonesjö L.
Published: November 2005

This paper presents a generalized approach to data editing in interactive systems. We describe the ED3 editor, which is a powerful tool for text editing combining the ability to handle hierarchical structures with screen-oriented text editing facilities. Extensions for handling simple pictures and formatted data records in a uniform way are part of our approach. Examples of ED3 applications are presented.
A graphics typesetting language
Authors: Van Wyk Christopher J.
Published: November 2005

We present a new programming language, IDEAL, in which two-dimensional figures can be expressed. The language is intended to work with existing text-formatting systems so that text and figures can be typeset at the same time.

The building block for IDEAL programs is called a “box” it shares some features with procedures and some with records in general-purpose programming languages. A box includes a system of constraints (in this incarnation, equations in complex variables) that declares the relative positions of its significant points and requests for actions to be performed at those points.

A box is called by adding enough constraints to the system in its definition that its significant points can be solved for uniquely. A box call may also include additional actions to be performed during the call. The notions of drawing a line using a pattern and texturing a polygonal area follow directly from the mechanism for defining and calling boxes.

Users may also ask for a box to be “opaque” so that it blots out pieces of picture that it covers. Finally, two commands embody the idea of sketching several pictures on different parallel planes, then merging them into a single picture. We use these when erasing to create one part of a picture would destroy another part that we want.

We discuss good algorithms for implementing IDEAL when the constraints are expressed as a special kind of nonlinear system and the pictures are composed of straight lines and circular arcs. The language has been implemented, and was used to produce the paper.
Design of the PEN video editor display module
Authors: Barach David R. , Taenzer David H. , Wells Robert E.
Published: November 2005

PEN, a new portable video editor, uses a number of simple but effective techniques. Most are not new, but are unavailable in the literature. We will describe our goals for PEN's display module, discuss implementation alternatives and describe in detail the techniques used in the editor.
The implementation of Etude, an integrated and interactive document production system
Authors: Hammer Michael , Ilson Richard , Anderson Tim , Gilbert Edward , Good Michael , Niamir Bahram , Rosentein Larry , Schoichet Sandor
Published: November 2005

Etude is an experimental text processing system that is being developed in order to formulate and evaluate new approaches to the design of user interfaces for office automation tools. The primary design goal for Etude is to provide the user with substantial functionality in the editing and formatting of documents in the context of a system that is easy to learn and use.
Hashed symbol tables for languages with explicit scope control
Authors: Graham S. L. , Joy W. N. , Roubine O.
Published: November 2005

Newer programming languages such as Modula and Euclid provide more control than traditional Algol-like languages such as ALGOL-60 and Pascal over the inheritance, in inner scopes, of named entities available in outer scopes. They also provide mechanisms whereby chosen entities from inner scopes may be made available to outer scopes. In this paper we show how a hashed symbol table can be organized to implement these new scope rules in a time and space efficient way.
An all(1) compiler generator
Authors: Milton D. R. , Kirchhoff L. W. , Rowland B. R.
Published: November 2005

Aparse is a flexible and modular system for generating efficient one-pass compilers from attributed grammar specifications. The system is of particular interest in that it combines recent research in attributed parsing and error-correction into a powerful and practical tool.

It has been amply demonstrated that attributed grammars are a convenient mechanism for organizing translations ([Fan 72], [LRS 74], [Bra 76]). This is partially due to the fact that an attributed grammar is not a completely formal specification tool—it merely provides a framework for structuring a semantic and syntactic specification. A number of compiler-compilers have been written to process attributed grammars ([LB 74], [BW 78], [GRW 77]), but Aparse is unique in incorporating attribute values in the parsing function. We have found that this facility permits smaller grammars to be used, and smaller parsers to be generated. In addition, a significant degree of context-sensitivity can be reflected in what is essentially a context-free framework. Section 2 will contain a brief introduction to attributed grammars, and section 3 will sketch the theory of attributed parsing.