bluuebunny/crossref_metadata_2025 huggingface dataset:
Controllable delegation: an exercise in law-governed systems
Authors: Minsky N. H. , Rozenshtein E.
Published: November 2005

We believe that the regime governing the patterns of sharing between objects, and of exchange of messages between them, should not be “hard-wired” into a programming language, but should be specifiable by the builders of a system to fit its particular requirements. This thesis has been the primary motivation behind our general concept of
law-governed system
, which serves as the foundation for this paper.

We show how the law can be used to impose a variety of useful constraints over the structure and behavior of delegation-based systems. Such a law may contain some very specific rules that apply only to small parts of a system; it may also impose some very general regimes, such as class inheritance, on the entire system. We also argue that the constraints established by the law can be easily adapted to the changing requirements of an evolving system. This should be very useful in managing the process of software development from its design stage, through prototyping, construction, and beyond.
An abstract intermediate representation in compilation systems
Authors: Guilan Dai , Jinlan Tian , Suqing Zhang , Weidu Jiang
Published: November 2005

The design of an intermediate representation is critical to the portability of a compiler and the efficiency of code generation. In order to increase the reusability of compiler components, and to simplify the development process of compilers, the paper presents an abstract intermediate representation (AIR) that provides a concise notation for describing the abstract syntax of programming languages and the inner data structures of compilers. AIR integrates algebraic data types into the object-oriented paradigm and thus makes it have stronger expressive power, flexibility, and extensibility. AIR separates the abstract descriptions from the concrete implementation. This makes it easier to be implemented in different high-level languages and thus improves the interoperatibility of compiler components.
Efficient formalism-only parsing of XML/HTML using the §-calculus
Authors: Jackson Quinn Tyler
Published: November 2005

Traditionally, correct parsing of XML and HTML has been littered with semantic hacks in the parsing code to deal with the oddities of these languages, since HTML accepts unbalanced tags and tags that do not match in case, but XML is less forgiving. The detection of well-formedness of XML documents has, to date, required semantic analysis outside of the grammar specification. We present a grammar-only (HT\X)ML parser which, upon detecting that it is parsing XML, modifies itself dynamically in order to insure that the document conforms to XML'S stricter rules. Our grammar detects unbalanced tags in XML, as well as mismatched case in otherwise balanced tags, while, at the same time, requiring XML document tag's attribute values to be in quotes, but accepting the looser attribute syntax when in an HTML document. On a 733 MHz Windows 2000 machine, our parser did a wellformedness detecting parse on XML documents such as the KJV Old Testament at a rate of 92 Kb/second, the Austin's Pride and Prejudice at a rate of 108 Kb/second, and Wolfgang May 's Mondial 3.0 database at a rate of 149 Kb/second.
The simplest heuristics may be the best in Java JIT compilers
Authors: Schilling Jonathan L.
Published: November 2005

The simplest strategy in Java just-in-time (JIT) compilers is to compile each Java method the first time it is called. However, better performance can often be obtained by selectively compiling methods based on heuristics of how often they are likely to be called during the rest of the program's execution. Various heuristics are examined when used as part of the Caldera UNIX Java JIT compiler. The simplest heuristics involving the number of times the method has executed so far and the size of the method prove to be the most effective, with more complicated heuristics not providing much or any additional benefit.
Inverting back the inversion of control or, continuations versus page-centric programming
Authors: Queinnec Christian
Published: November 2005

Our thesis is that programming web applications with continuations is superior to the current page-centric technology. A continuation is a program-level manageable value representing the rest of the computation of the program. "What to do next" is precisely what has to be explicitly encoded in order to program non trivial web interactions. Continuations allow web applications to be written in direct style that is, as a single program that displays forms and reads form submission since continuations automatically capture everything (control point, lexical bindings, etc.) that is needed to resume the computation. Programming is therefore safer, easier and more re-usable.
Understanding the connectivity of heap objects
Authors: Hirzel Martin , Henkel Johannes , Diwan Amer , Hind Michael
Published: November 2005

Modern garbage collectors partition the set of heap objects to achieve the best performance. For example, generational garbage collectors partition objects by age and focus their efforts on the youngest objects. Partitioning by age works well for many programs because younger objects usually have short lifetimes and thus garbage collection of young objects is often able to free up many objects. However, generational garbage collectors are typically much less efficient for longer-lived objects, and thus prior work has proposed many enhancements to generational collection.Our work explores whether the connectivity of objects can yield useful partitions or improve existing partitioning schemes. We look at both direct (e.g., object A points to object B) and transitive (e.g., object A is reachable from object B) connectivity. Our results indicate that connectivity correlates strongly with object lifetimes and deathtimes and is therefore likely to be useful for partitioning objects.
Visualising the train garbage collector
Authors: Printezis Tony , Garthwaite Alex
Published: November 2005

This paper presents a novel method for visualising an incremental garbage collector, based on the well-known Train algorithm, that generates concise snapshots of its state and informative graphs of its operation over time. To obtain these visualisations we used GC-spy, a generic heap visualisation framework. We show how this easy-to-use tool provided a visualisation model that was effective in both confirming our pre-existing beliefs about the collector's operation and, more interestingly, highlighting unexpected patterns in its behaviour. Based on this successful experience, we advocate the use of similar visualisation approaches to better understand and ultimately tune, profile, and improve other equally complex garbage collectors.
Estimating the impact of heap liveness information on space consumption in Java
Authors: Shaham Ran , Kolodner Elliot K. , Sagiv Mooly
Published: November 2005

We study the potential impact of different kinds of liveness information on the space consumption of a program in a garbage collected environment, specifically for Java. The idea is to measure the time difference between the actual time an object is collected by the garbage collector (GC) and the potential earliest time an object could be collected assuming liveness information were available. We focus on the following kinds of liveness information: (i) stack-reference liveness (local reference variable liveness in Java), (ii) global-reference liveness (static reference variable liveness in Java), (iii) heap-reference liveness (instance reference variable liveness or array reference liveness in Java), and (vi) any combination of (i)-(iii). We also provide some insights on the kind of interface between a compiler and GC that could achieve these potential savings.The Java Virtual Machine (JVM) was instrumented to measure (dynamic) liveness information. Experimental results are given for 10 benchmarks, including 5 of the SPEC-jvm98 benchmark suite. We show that in general stack-reference liveness may yield small benefits, global-reference liveness combined with stack-reference liveness may yield medium benefits, and heap-reference liveness yields the largest potential benefit. Specifically, for heap-reference liveness we measure an average potential savings of 39% using an interface with complete liveness information, and an average savings of 15% using a more restricted interface.
Thread-local heaps for Java
Authors: Domani Tamar , Goldshtein Gal , Kolodner Elliot K. , Lewis Ethan , Petrank Erez , Sheinwald Dafna
Published: November 2005

We present a memory management scheme for Java based on thread-local heaps. Assuming most objects are created and used by a single thread, it is desirable to free the memory manager from redundant synchronization for thread-local objects. Therefore, in our scheme each thread receives a partition of the heap in which it allocates its objects and in which it does local garbage collection without synchronization with other threads. We dynamically monitor to determine which objects are local and which are global. Furthermore, we suggest using profiling to identify allocation sites that almost exclusively allocate global objects, and allocate objects at these sites directly in a global area.We have implemented the thread-local heap memory manager and a preliminary mechanism for direct global allocation on an IBM prototype of JDK 1.3.0 for Windows. Our measurements of thread-local heaps with direct global allocation on a 4-way multiprocessor IBM Netfinity server show that the overall garbage collection times have been substantially reduced, and that most long pauses have been eliminated.
An adaptive, region-based allocator for java
Authors: Qian Feng , Hendren Laurie
Published: November 2005

This paper introduces an adaptive, region-based allocator for Java. The basic idea is to allocate non-escaping objects in local regions, which are allocated and freed in conjunction with their associated stack frames. By releasing memory associated with these stack frames, the burden on the garbage collector is reduced, possibly resulting in fewer collections.The novelty of our approach is that it does not require static escape analysis, programmer annotations, or special type systems. The approach is transparent to the Java programmer and relatively simple to add to an existing JVM. The system starts by assuming that all allocated objects are local to their stack region, and then catches escaping objects via write barriers. When an object is caught escaping, its associated allocation site is marked as a non-local site, so that subsequent allocations will be put directly in the global region. Thus, as execution proceeds, only those allocation sites that are likely to produce non-escaping objects are allocated to their local stack region.The paper presents the overall idea, and then provides details of a specific design and implementation. In particular, we present a region-based allocator and the necessary modifications of the Jikes RVM baseline JIT and a copying collector. Our experimental study evaluates the idea using the SPEC JVM98 benchmarks, plus one other large benchmark. We show that a region-based allocator is a reasonable choice, that overheads can be kept low, and that the adaptive system is successful at finding local regions that contain no escaping objects.
Older-first garbage collection in practice
Authors: Stefanović Darko , Hertz Matthew , Blackburn Stephen M. , McKinley Kathryn S. , Moss J. Eliot B.
Published: November 2005

Until recently, the best performing copying garbage collectors used a generational policy which repeatedly collects the very youngest objects, copies any survivors to an older space, and then infrequently collects the older space. A previous study that used garbage-collection simulation pointed to potential improvements by using an
Older-First
copying garbage collection algorithm. The Older-First algorithm sweeps a fixed-sized window through the heap from older to younger objects, and avoids copying the very youngest objects which have not yet had sufficient time to die. We describe and examine here an implementation of the Older-First algorithm in the Jikes RVM for Java. This investigation shows that Older-First can perform as well as the simulation results suggested, and greatly improves total program performance when compared to using a fixed-size nursery generational collector. We further compare Older-First to a flexible-size nursery generational collector in which the nursery occupies all of the heap that does not contain older objects. In these comparisons, the flexible-nursery collector is occasionally the better of the two, but on average the Older-First collector performs the best.
Calculating stack distances efficiently
Authors: Almási George , Caşcaval Cǎlin , Padua David A.
Published: November 2005

This paper
1
describes our experience using the stack processing algorithm [6] for estimating the number of cache misses in scientific programs. By using a new data structure and various optimization techniques we obtain instrumented run-times within 50 to 100 times the original optimized run-times of our benchmarks.
The performance advantage of applying compression to the memory system
Authors: Mahapatra Nihar R. , Liu Jiangjiang , Sundaresan Krishnan
Published: November 2005

The memory system stores information comprising primarily instructions and data and secondarily address information, such as cache tag fields. It interacts with the processor by supporting related traffic (again comprising addresses, instructions, and data). Continuing exponential growth in processor performance, combined with technology, architecture, and application trends, place enormous demands on the memory system to permit this information storage and exchange at a high-enough performance (i.e., to provide low latency and high bandwidth access to large amounts of information). This paper comprehensively analyzes the redundancy in the information (addresses, instructions, and data) stored and exchanged between the processor and the memory system and evaluates the potential of compression in improving performance of the memory system. Analysis of traces obtained with Sun Microsystems' Shade simulator simulating SPARC executables of nine integer and six floating-point programs in the SPEC CPU2000 benchmark suite yield impressive results. Well-designed compression schemes may provide benefits in performance that far outweigh the extra time and logic for compression and decompression. This will be more so in the future since the speed and size of logic (which will be used to perform compression/decompression) are improving and are projected to improve at a much higher rate compared to those of interconnect (which will be used to communicate the information), both on-chip and off-chip.
Is continuation-passing useful for data flow analysis?
Authors: Sabry Amr , Felleisen Matthias
Published: November 2005

The widespread use of the continuation-passing style (CPS) transformation in compilers, optimizers, abstract interpreters, and partial evaluators reflects a common belief that the transformation has a positive effect on the analysis of programs. Investigations by Nielson [13] and Burn/Filho [5,6] support, to some degree, this belief with theoretical results. However, they do not pinpoint the source of increased abstract information and do not explain the observation of many people that continuation-passing confuses some conventional data flow analyses.

To study the impact of the CPS transformation on program analysis, we derive three canonical data flow analyzers for the core of an applicative higher-order programming language. The first analyzer is based on a direct semantics of the language, the second on a continuation-semantics of the language, and the last on the direct semantics of CPS terms. All analyzers compute the control flow graph of the source program and hence our results apply to a large class of data flow analyses. A comparison of the information gathered by our analyzers establishes the following points:

In view of these results, we argue that, in practice, a direct data flow analysis that relies on some amount of duplication would be as satisfactory as a CPS analysis.
Division by invariant integers using multiplication
Authors: Granlund Torbjörn , Montgomery Peter L.
Published: November 2005

Integer division remains expensive on today's processors as the cost of integer multiplication declines. We present code sequences for division by arbitrary nonzero integer constants and run-time invariants using integer multiplication. The algorithms assume a two's complement architecture. Most also require that the upper half of an integer product be quickly accessible. We treat unsigned division, signed division where the quotient rounds towards zero, signed division where the quotient rounds towards -∞, and division where the result is known
a priori
to be exact. We give some implementation results using the C compiler GCC.
The program structure tree
Authors: Johnson Richard , Pearson David , Pingali Keshav
Published: November 2005

In this paper, we describe the program structure tree (PST), a hierarchical representation of program structure based on single entry single exit (SESE) regions of the control flow graph. We give a linear-time algorithm for finding SESE regions and for building the PST of arbitrary control flow graphs (including irreducible ones). Next, we establish a connection between SESE regions and control dependence equivalence classes, and show how to use the algorithm to find control regions in linear time. Finally, we discuss some applications of the PST. Many control flow algorithms, such as construction of Static Single Assignment form, can be speeded up by applying the algorithms in a divide-and-conquer style to each SESE region on its own. The PST is also used to speed up data flow analysis by exploiting “sparsity”. Experimental results from the Perfect Club and SPEC89 benchmarks confirm that the PST approach finds and exploits program structure.
Debugging of globally optimized programs using data flow analysis
Authors: Wismüller Roland
Published: November 2005

Advanced processor and machine architectures need optimizing compilers to be efficiently programmed in high level languages. Therefore the need for source level debuggers that can handle optimized programs is rising. One difficulty in debugging optimized code arises from the problem to determine the values of source code variables. To ensure correct debugger behaviour with optimized programs, the debugger not only has to determine the variable's storage location or associated register. It must also verify that the variable is
current
, i.e. the value determined from that location is really the value that the variable would have in unoptimized code. We will deduce requirements on algorithms for currentness determination and present an algorithm meeting this requirements that is more general than previous work. We will also give first experiences with an implementation. To our knowledge this is the first implementation of a currentness determination algorithm for globally optimized code.
Advanced copy propagation for arrays
Authors: Vanbroekhoven Peter , Janssens Gerda , Bruynooghe Maurice , Corporaal Henk , Catthoor Francky
Published: November 2005

The focus of this paper is on a data flow-transformation called advanced copy propagation. After an array is assigned, we can, under certain conditions, replace a read from this array by the righthand side of the assignment. If so, the intermediate assignment can be skipped. In case it becomes dead code, it can be eliminated. Where necessary we distinguish between the different elements of arrays as well as the different runtime instances of statements, allowing us to do propagation over global loop and condition scopes. We have formalized two basic operations: non-recursive propagation that operates on two statements and recursive propagation that operates on one statement. A global algorithm uses these two operations to do propagation on code involving any number of statements. Running our prototype implementation on some multimedia kernels shows that we can get a decrease in memory acesses between 22% and 43%.
A java virtual machine architecture for very small devices
Authors: Shaylor Nik , Simon Douglas N. , Bush William R.
Published: November 2005

The smallest complete Java™ virtual machine implementations in use today are based on the CLDC standard and are deployed in mobile phones and PDAs. These implementations require several tens of kilobytes. Smaller Java-like implementations also exist, but these involve compromises in Java semantics. This paper describes a JVM™ architecture designed for very small devices. It supports all the CLDC Java platform semantics, including exact garbage collection, dynamic class loading, and verification. For portability and ease of debugging, the entire system is written in the Java language, with key components automatically translated into C and compiled for the target device. The resulting system will run on the next generation of smart cards, and has performance comparable to the reference CLDC implementation available from Sun™.
Compiling java for low-end embedded systems
Authors: Schultz Ulrik Pagh , Burgaard Kim , Christensen Flemming Gram , Knudsen Jørgen Lindskov
Published: November 2005

The production of embedded systems is continuously increasing, but developing reusable software for such systems is notoriously difficult, in particular in the case of low-end embedded systems based on 16-bit or 8-bit processors. We have developed a compilation system for executing Java byte code on low-end embedded systems, and we demonstrate how this system permits object-oriented programming techniques to be used on devices with only a few hundred bytes of RAM and a few kilobytes of ROM.We analyze the execution overheads of using object-orien\-ted programming on low-end embedded systems. Based on the conclusion that memory consumption is the major obstacle, we show how the configuration features and optimizations integrated into our compiler can be used to significantly reduce memory requirements. In particular, we use a novel approach based on Java interfaces to control integration of Java programs with the hardware, and demonstrate how aggressive whole-program optimization can significantly reduce the size of the compiled program.
Time-triggered garbage collection
Authors: Robertz Sven Gestegard , Henriksson Roger
Published: November 2005

The advent of Java and similar languages on the real-time system scene necessitates the development of efficient strategies for scheduling the work of a garbage collector in a non-intrusive way. We propose a scheduling strategy,
time-triggered garbage collection
, based on assigning the collector a deadline for when it must complete its current cycle.We show that a time-triggered GC with fixed deadline can have equal or better real-time performance than an allocation-triggered GC, which is the standard approach to real-time GC. Also, by using a deadline-based approach, the GC scheduling and, consequently, real-time performance, is independent of a complex and error-prone GC work metric.Time-triggered GC allows a more high-level view on GC scheduling; we look at the GC cycle level rather than at the individual work increments. This makes it possible to schedule GC as any other thread. It is also suitable for making the GC auto-tuning by dynamically adjusting its deadline as necessary.We have implemented our approach in a run-time system for Java and present experimental data to support the practical feasibility of the approach.
Transport layer abstraction in event channels for embedded systems
Authors: M Ravi Pratap , Cytron Ron K. , Sharp David , Pla Edward
Published: November 2005

As embedded systems increase in complexity and begin to participate in distributed systems, the need for middleware in building such systems becomes imperative. However, the use of middleware that fully implements such standards can impose a significant increase in footprint for an application, making it unsuitable for use in embedded systems. We consider the use of a standard CORBA event channel in a setting where distribution and inter-language support are unnecessary. We report our experience in applying
aspects
to abstract the transport layer (CORBA) of the event channel into a selectable feature. Thus, enabling or disabling CORBA for a specific application can be decided at build-time, by merely selecting CORBA as a feature. We describe the patterns used to achieve this abstraction and present footprint and throughput results showing the effect of CORBA on automatically derived subsets of the event channel.
On efficient program synthesis from statecharts
Authors: Wasowski Andrzej
Published: November 2005

Program synthesis from hierarchical state diagrams has for long been discussed in various communities. My aim is to provide an efficient, lightweight code generation scheme suitable for resource constrained microcontrollers.I describe an initial implementation of SCOPE---a hierarchical code generator for a variant of the statechart language. I shall discuss several techniques implemented in the tool, namely imposing and exploiting a regular hierarchy structure, labeling schemes for fast ancestor queries, improvements in exiting states, compile-time scope resolution for transitions, and various details of compact runtime representation.The resulting algorithm avoids the exponential code growth exhibited by tools based on flattening of hierarchical state machine. At the same time it demonstrates that it is possible to maintain reasonable speed and size results even for small models, while preserving the hierarchy at runtime. SCOPE currently produces code that is comparable with that of industrial tools (IAR visualSTATE) for small models and clearly wins for bigger ones.
An algorithm for mapping loops onto coarse-grained reconfigurable architectures
Authors: Lee Jong-eun , Choi Kiyoung , Dutt Nikil D.
Published: November 2005

With the increasing demand for flexible yet highly efficient architecture platforms for media applications, there is a growing interest in the Coarse-grained Reconfigurable Architectures (CRAs). While many CRAs have demonstrated impressive performance improvement, the lack of compilation technology for such architectures causes a bottleneck in the current design process. In this paper, we present a novel mapping algorithm designed to support Reconfigurable ALU Array (RAA) architectures, that represent a significant class of CRAs. More specifically we present a core mapping algorithm that addresses the problem of placing and routing the operations of a loop body onto the ALU array, to be executed in a loop pipelined fashion. Experimental results using our mapping algorithm on a typical RAA show that our algorithm not only has very fast compilation time but can also generate quality mappings exhibiting high memory bandwidth utilization and low global interconnection requirements. Comparison with manual mapping also indicates that our algorithm can generate near-optimal mappings for several loops.
Profiling tools for hardware/software partitioning of embedded applications
Authors: Suresh Dinesh C. , Najjar Walid A. , Vahid Frank , Villarreal Jason R. , Stitt Greg
Published: November 2005

Loops constitute the most executed segments of programs and therefore are the best candidates for hardware software partitioning. We present a set of profiling tools that are specifically dedicated to loop profiling and do support combined function and loop profiling. One tool relies on an instruction set simulator and can therefore be augmented with architecture and micro-architecture features simulation while the other is based on compile-time instrumentation of gcc and therefore has very little slow down compared to the original program We use the results of the profiling to identify the compute core in each benchmark and study the effect of compile-time optimization on the distribution of cores in a program. We also study the potential speedup that can be achieved using a configurable system on a chip, consisting of a CPU embedded on an FPGA, as an example application of these tools in hardware/software partitioning.
A graph covering algorithm for a coarse grain reconfigurable system
Authors: Guo Yuanqing , Smit Gerard J.M. , Broersma Hajo , Heysters Paul M.
Published: November 2005

The availability of high-level design entry tooling is crucial for the viability of any reconfigurable SoC architecture. This paper presents a graph covering algorithm. The graph covering is done in two steps: template generation and template selection. The objective of template generation step is to extract functional equivalent structures, i.e. templates, from a control data flow graph. By inspecting the graph, the algorithm generates all the possible templates and the corresponding matches. Using unique serial numbers and circle numbers, the algorithm can find all distinct templates with multiple outputs. The template selection algorithm shows how this information can be used in compilers for reconfigurable systems. The objective of the template selection algorithm is to find an efficient cover for an application graph with a minimal number of distinct templates and minimal number of matches.
On the side-effects of code abstraction
Authors: De Sutter Bjorn , Vandierendonck Hans , De Bus Bruno , De Bosschere Koen
Published: November 2005

More and more devices contain computers with limited amounts of memory. As a result, code compaction techniques are gaining popularity, especially when they also improve performance and power consumption, or at least not degrade it. This paper quantifies the side-effects of code abstraction on performance using extensive measurements and simulations on the SPECint2000 benchmark suite and some additional C++ programs. We show how to use profile information in order to obtain almost all the code size reduction benefits of code abstraction, yet experience almost none of its disadvantages.
Taming the IXP network processor
Authors: George Lal , Blume Matthias
Published: November 2005

We compile Nova, a new language designed for writing network processing applications, using a back end based on integer-linear programming (ILP) for register allocation, optimal bank assignment, and spills. The compiler's optimizer employs CPS as its intermediate representation; some of the invariants that this IR guarantees are essential for the formulation of a practical ILP model.Appel and George used a similar ILP-based technique for the IA32 to decide which variables reside in registers but deferred the actual assignment of colors to a later phase. We demonstrate how to carry over their idea to an architecture with many more banks, register aggregates, variables with multiple simultaneous register assignments, and, very importantly, one where bank- and register-assignment cannot be done in isolation from each other. Our approach performs well in practise---without causing an explosion in size or solve time of the generated integer linear programs.
Compile-time composition of run-time data and iteration reorderings
Authors: Strout Michelle Mills , Carter Larry , Ferrante Jeanne
Published: November 2005

Many important applications, such as those using sparse data structures, have memory reference patterns that are unknown at compile-time. Prior work has developed run-time reorderings of data and computation that enhance locality in such applications.This paper presents a compile-time framework that allows the explicit composition of run-time data and iteration-reordering transformations. Our framework builds on the iteration-reordering framework of Kelly and Pugh to represent the effects of a given composition. To motivate our extension, we show that new compositions of run-time reordering transformations can result in better performance on three benchmarks.We show how to express a number of run-time data and iteration-reordering transformations that focus on improving data locality. We also describe the space of possible run-time reordering transformations and how existing transformations fit within it. Since sparse tiling techniques are included in our framework, they become more generally applicable, both to a larger class of applications, and in their composition with other reordering transformations. Finally, within the presented framework data need be remapped
only once
at runtime for a given composition thus exhibiting one example of overhead reductions the framework can express.
Points-to analysis using BDDs
Authors: Berndl Marc , Lhoták Ondrej , Qian Feng , Hendren Laurie , Umanee Navindra
Published: November 2005

This paper reports on a new approach to solving a subset-based points-to analysis for Java using Binary Decision Diagrams (BDDs). In the model checking community, BDDs have been shown very effective for representing large sets and solving very large verification problems. Our work shows that BDDs can also be very effective for developing a points-to analysis that is simple to implement and that scales well, in both space and time, to large programs.The paper first introduces BDDs and operations on BDDs using some simple points-to examples. Then, a complete subset-based points-to algorithm is presented, expressed completely using BDDs and BDD operations. This algorithm is then refined by finding appropriate variable orderings and by making the algorithm propagate sets incrementally, in order to arrive at a very efficient algorithm. Experimental results are given to justify the choice of variable ordering, to demonstrate the improvement due to incrementalization, and to compare the performance of the BDD-based solver to an efficient hand-coded graph-based solver. Finally, based on the results of the BDD-based solver, a variety of BDD-based queries are presented, including the points-to query.
Bug isolation via remote program sampling
Authors: Liblit Ben , Aiken Alex , Zheng Alice X. , Jordan Michael I.
Published: November 2005

We propose a low-overhead sampling infrastructure for gathering information from the executions experienced by a program's user community. Several example applications illustrate ways to use sampled instrumentation to isolate bugs. Assertion-dense code can be transformed to share the cost of assertions among many users. Lacking assertions, broad guesses can be made about predicates that predict program errors and a process of elimination used to whittle these down to the true bug. Finally, even for non-deterministic bugs such as memory corruption, statistical modeling based on logistic regression allows us to identify program behaviors that are strongly correlated with failure and are therefore likely places to look for the error.
A practical flow-sensitive and context-sensitive C and C++ memory leak detector
Authors: Heine David L. , Lam Monica S.
Published: November 2005

This paper presents a static analysis tool that can automatically find memory leaks and deletions of dangling pointers in large C and C++ applications.We have developed a type system to formalize a practical ownership model of memory management. In this model, every object is pointed to by one and only one
owning
pointer, which holds the exclusive right and obligation to either delete the object or to transfer the right to another owning pointer. In addition, a pointer-typed class member field is required to either always or never own its pointee at public method boundaries. Programs satisfying this model do not leak memory or delete the same object more than once.We have also developed a flow-sensitive and context-sensitive algorithm to automatically infer the likely ownership interfaces of methods in a program. It identifies statements inconsistent with the model as sources of potential leaks or double deletes. The algorithm is sound with respect to a large subset of the C and C++ language in that it will report all possible errors. It is also practical and useful as it identifies those warnings likely to correspond to errors and helps the user understand the reported errors by showing them the assumed method interfaces.Our techniques are validated with an implementation of a tool we call Clouseau. We applied Clouseau to a suite of applications: two web servers, a chat client, secure shell tools, executable object manipulation tools, and a compiler. The tool found a total of 134 serious memory errors in these applications. The tool analyzes over 50K lines of C++ code in about 9 minutes on a 2 GHz Pentium 4 machine and over 70K lines of C code in just over a minute.
Optimizing indirect branch prediction accuracy in virtual machine interpreters
Authors: Ertl M. Anton , Gregg David
Published: November 2005

Interpreters designed for efficiency execute a huge number of indirect branches and can spend more than half of the execution time in indirect branch mispredictions. Branch target buffers are the best widely available form of indirect branch prediction; however, their prediction accuracy for existing interpreters is only 2%--50%. In this paper we investigate two methods for improving the prediction accuracy of BTBs for interpreters: replicating virtual machine (VM) instructions and combining sequences of VM instructions into superinstructions. We investigate static (interpreter build-time) and dynamic (interpreter run-time) variants of these techniques and compare them and several combinations of these techniques. These techniques can eliminate nearly all of the dispatch branch mispredictions, and have other benefits, resulting in speedups by a factor of up to 3.17 over efficient threaded-code interpreters, and speedups by a factor of up to 1.3 over techniques relying on superinstructions alone.
A type and effect system for atomicity
Authors: Flanagan Cormac , Qadeer Shaz
Published: November 2005

Ensuring the correctness of multithreaded programs is difficult, due to the potential for unexpected and nondeterministic interactions between threads. Previous work addressed this problem by devising tools for detecting
race conditions
, a situation where two threads simultaneously access the same data variable, and at least one of the accesses is a write. However, verifying the absence of such simultaneous-access race conditions is neither necessary nor sufficient to ensure the absence of errors due to unexpected thread interactions.We propose that a stronger non-interference property is required, namely
atomicity
. Atomic methods can be assumed to execute serially, without interleaved steps of other threads. Thus, atomic methods are amenable to sequential reasoning techniques, which significantly simplifies both formal and informal reasoning about program correctness.This paper presents a type system for specifying and verifying the atomicity of methods in multithreaded Java programs. The atomic type system is a synthesis of Lipton's theory of reduction and type systems for race detection.We have implemented this atomic type system for Java and used it to check a variety of standard Java library classes. The type checker uncovered subtle atomicity violations in classes such as java.lang.String and java.lang.String-Buffer that cause crashes under certain thread interleavings.This paper proposes that a stronger non-interference property is required, namely
atomicity
, and presents a type system for verifying the atomicity of methods in multithreaded Java programs. Methods in a class can be annotated with the keyword atomic. Clients of a well-typed class can then assume that each atomic method is executed in one step, thus significantly simplifying both formal and informal reasoning about the client's correctness.
Assessment of the Java programming language for use in high integrity systems
Authors: Kwon Jagun , Wellings Andy , King Steve
Published: November 2005

This paper sets a goal of investigating the use of Java in the development of high integrity systems. Based on previous studies, guidelines, and standards, we develop 23 criteria that are used for the following assessment of Java. A summary of the assessment is provided before we go on to review a few existing subsets of the language.
KGOL
Authors: Zhuge Hai , Liu Jie
Published: November 2005

This paper presents the design and implementation of a Knowledge Grid operating language and the programming environment KGOL. It provides not only a friendly user interface for end-users to easily access and manage the Knowledge Grid resources but also a programming environment for application developers to implement the Knowledge Grid applications. The KGOL programming environment consists of a parser, an interpreter, an execution engine, and a result generator. Comparisons between the KGOL, the SQL, and the XML-based query languages XQL and LOREL show the distinguished advantages of the KGOL.
Experience with porting techniques on a COBOL 74 compiler
Authors: Kipps I. M.
Published: November 2005

The problems of compiler construction have largely been solved for COBOL '74, but a remaining fundamental consideration in a commercial environment is the cost of compiler development. This can be reduced by the use of portable software, but the cost of porting to a new system remains significant. In the microprocessor system market, two approaches have been followed. The first is to produce software for a virtual machine environment and simulate this on real hardware be means of an interpreter. Most software, including language processors and large parts of the operating system, can be transferred almost unchanged to a new processor. Nearly all commercial software for microprocessors has been developed on this basis. The alternative approach is to produce software which, by virtue of certain characteristics, can be made to be portable to new real machine environments, provided the appropriate high level language compiler is available.

We have developed an ANS COBOL 74 compiler for microprocessors using this second approach [1]. Since the compiler compiles COBOL at a level approaching level 2 in the main modules to the true machine code of the target machine, the same approach becomes available to the applications programmer. As far as can be established, this work is unique. Both compiler and object code interface directly to the machine environment. No interpreter is required for their execution. The compiler system runs on, and generates code for, three machines. In addition, since the compiler is written in a high level language, portable cross compilers are available.
An overview of the PL.8 compiler
Authors: Auslander Marc , Hopkins Martin
Published: November 2005

The PL.8 compiler accepts multiple source languages and produces high quality object code for several different machines. The strategy used is to first do a simple translation of the source program to a low level intermediate language. Global optimization and register allocation are then used to improve code rather than relying on special case code selection.
The design of a data flow analyzer
Authors: Chow Anita L. , Rudmik Andres
Published: November 2005

This paper presents an efficient inter-procedural data flow analysis algorithm for precisely determining aliases in programs that employ a rich set of parameter passing mechanisms and pointer data types. This approach handles the use of pointers bounded to a data type as in Pascal, as well as unbounded pointers that can point to the same locations to which variables map. In the last step of this approach, the alias information is used to compute data flow information that is required for optimization.
A flexible compiler structure that allows dynamic phase ordering
Authors: LaLonde Wilf R. , Rivieres Jim des
Published: November 2005

Traditionally, compilers have been internally organized into separate phases that are invoked in a fixed, predetermined order. However, the optimal phase invocation order is usually different for different contexts, such as (1) large batch-oriented production environments, (2) small batch-oriented student environments, and (3) interactive programming environments.

We discuss the constraints that must be met in order to obtain a compiler with flexible phase ordering, a property that allows the compiler to be designed and implemented without consideration for the intended operating environment. Flexible phase ordering allows the compiler to be specially configured after the fact. A production compiler based on this principle is also discussed.
Analyzing exotic instructions for a retargetable code generator
Authors: Morgan Thomas M. , Rowe Lawrence A.
Published: November 2005

Exotic instructions are complex instructions, such as block move, string search, and string edit, which are found on most conventional computers. Recent retargetable code generator and instruction set analysis systems have not dealt with exotic instructions. A method to analyze exotic instructions is presented which provides the information needed by a retargetable code generator. The analysis uses source-to-source transformations to prove the equivalence of high-level language operators to exotic instructions. Examples are presented which illustrate the analysis process.
Denotational semantics as a specification of code generators
Authors: Raskovsky Martin R.
Published: November 2005

We describe the automatic generation - from the formal denotational semantic specification - of an efficient compiler's code generation phase, producing efficient code for real machines. The method has been succesfully implemented and tested with languages as complex as GEDANKEN!
The linear graph package, a compiler building environment
Authors: Marshall Howard Z.
Published: November 2005

The Linear Graph package is a collection of software tools that provides a software development environment particularly well suited to compiler construction. More precisely, the Linear Graph (or “LG”) package is a generic specification of these tools. No specific implementation language or host computer system is presumed, and, in fact, LG packages have been built in several languages on a variety of computers.

These LG packages have proved to be powerful tools. We have used LG to build two FORTRAN-77 compilers, a JOVIAL compiler, and a Pascal compiler; we are presently using LG to build a CHILL compiler, an Ada* compiler, a third FORTRAN-77 compiler, and an optimizer for the JOVIAL compiler. We have also used LG to build some related support software: the linker used with the Pascal compiler, and a global symbol data base system for the JOVIAL and Pascal compilers. The LG package simplified the design, implementation, and maintenance of these compilers and support programs.
Experience with the formal semantic definition of HAL/S
Authors: Pratt Terrence W. , Maydwell George D.
Published: November 2005

HAL/S is a large general purpose real-time programming language somewhat similar to ADA. Its major applications are for embedded real-time systems, in particular for the Space Shuttle on-board computer software and similar applications within NASA. After the language had been in regular use for several years, we were requested by NASA to prepare a formal semantic definition of the language using the method of H-graph semantics. This paper reports on the method and structure of that definition and on experience with its use in finding and correcting errors in the language specification and in the design of implementations for the language.
An attribute grammar for Ada
Authors: Drossopoulou S. , Uhl J. , Persch G. , Goos G. , Dausmann M. , Winterstein G.
Published: November 2005

We describe the development of a formal specification of the static semantics of Ada in form of an attribute grammar. This specification is complete, and was tested extensively with automatically generated equivalent Pascal programs. From this specification we systematically developed the semantic analysis part of our Ada Compiler Front End. We outline the general proceeding when specifying semantic analysis with attribute grammars and then discuss to some extent examples about declaration elaboration and overloading resolution.

CR Categories and Subject Descriptors: D.3.1 [Programming Languages]: Formal definitions and Theory - semantics; D.3.4 [Programming Languages]: Processors - Translator writing systems and compiler generators; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages - algebraic approaches to semantics.