1,205 papers · page 22 of 61
The problem of inferring array shapes ahead of time in languages that exhibit both implicit and dynamic typing is a critical one because the ramifications of its solution are the better organization of array storage through compaction and reuse, and the generation of high-perform…
This article presents a design for the Denali-2 superoptimizer, which will generate minimum-instruction-length machine code for realistic machine architectures using automatic theorem-proving technology: specifically, using E-graph matching (a technique for pattern matching in th…
Computer designs are shifting from 32-bit architectures to 64-bit architectures, while most of the programs available today are still designed for 32-bit architectures. Java, for example, specifies the frequently used “int” as a 32-bit signed integer. If such Java programs are ex…
Recent proposals for multithreaded architectures employ speculative execution to allow threads with unknown dependences to execute speculatively in parallel. The architectures use hardware speculative storage to buffer speculative data, track data dependences and correct incorrec…
We introduce Jinja, a Java-like programming language with a formal semantics designed to exhibit core features of the Java language architecture. Jinja is a compromise between the realism of the language and the tractability and clarity of its formal semantics. The following aspe…
Reference-counting is traditionally considered unsuitable for multiprocessor systems. According to conventional wisdom, the update of reference slots and reference-counts requires atomic or synchronized operations. In this work we demonstrate this is not the case by presenting a …
We develop a semantics theory for SAP, a variant of Levi and Sangiorgi's Safe Ambients, SA.The dynamics of SA relies upon capabilities (and co-capabilities ) exercised by mobile agents , called ambients , to interact with each other. These capabilities contain references, the nam…
Slicing is a well-known program reduction technique where for a given program P and a variable of interest v at some statement P in the program, a program slice contains those set of statements belonging to P that affect v . This article presents two algorithms for interprocedura…
Optimizing exception handling is critical for programs that frequently throw exceptions. We observed that there are many such exception-intensive programs written in Java. There are two commonly used exception handling techniques, stack unwinding and stack cutting. Stack unwindin…
We present a static analysis technique for nontermination inference of logic programs. Our framework relies on an extension of the subsumption test, where some specific argument positions can be instantiated while others are generalized. We give syntactic criteria to statically i…
We consider the analysis and optimization of code utilizing operations and functions operating on entire arrays. Models are developed for studying the minimization of the number of materializations of array-valued temporaries in basic blocks, each consisting of a sequence of assi…
The right nulled generalized LR parsing algorithm is a new generalization of LR parsing which provides an elegant correction to, and extension of, Tomita's GLR methods whereby we extend the notion of a reduction in a shift-reduce parser to include right nulled items. The result i…
Method inlining and data flow analysis are two major optimization components for effective program transformations, but they often suffer from the existence of rarely or never executed code contained in the target method. One major problem lies in the assumption that the compilat…
Regular expression patterns provide a natural, declarative way to express constraints on semistructured data and to extract relevant information from it. Indeed, it is a core feature of the programming language Perl, surfaces in various UNIX tools such as sed and awk, and has rec…
Recursive state machines (RSMs) enhance the power of ordinary state machines by allowing vertices to correspond either to ordinary states or to potentially recursive invocations of other state machines. RSMs can model the control flow in sequential imperative programs containing …
Single-language runtime systems, in the form of Java virtual machines, are widely deployed platforms for executing untrusted mobile code. These runtimes provide some of the features that operating systems provide: interapplication memory protection and basic system services. They…
Predicate abstraction is a technique for creating abstract models of software that are amenable to model checking algorithms. We show how polymorphism, a well-known concept in programming languages and program analysis, can be incorporated in a predicate abstraction algorithm for…
Multithreaded applications with multigigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for “server-oriented” GC include: ensuring short pause times on a multigigabyte heap while minimizing throughput penalty, good scaling …
In programming language and software engineering, the main mathematical tool isde factosome form of predicate logic. Yet, as elsewhere in applied mathematics, it is used mostly far below its potential, due to its traditional formulation as just a topic in logic instead of a calcu…
Corrigendum to ACM Transactions on Programming Languages and Systems , 20(6):1265--1296, 1998.