waashk/dblp huggingface dataset:
a sparse algorithm for predicated global value numbering. this paper presents a new algorithm for performing global value numbering on a routine in static single assignment form. our algorithm has all the strengths of the most powerful existing practical methods of global value numbering; it unifies optimistic value numbering with constant folding, algebraic simplification and unreachable code elimination. it goes beyond existing methods by unifying optimistic value numbering with further analyses: it canonicalizes the structure of expressions in order to expose more congruences by performing global reassociation, it exploits the congruences induced by the predicates of conditional jumps (predicate inference and value inference), and it associates the arguments of acyclic &oslash; functions with the predicates controlling their arrival (&oslash; predication), thus enabling congruence finding on conditional control structures. finally, it implements an efficient sparse formulation and offers a range of tradeoffs between compilation time and optimization strength. we describe an implementation of the algorithm and present measurements of its strength and efficiency collected when optimizing the spec cint2000 c benchmarks.
language support for regions. region-based memory management systems structure memory by grouping objects in regions under program control. memory is reclaimed by deleting regions, freeing all objects stored therein. our compiler for c with regions, rc, prevents unsafe region deletions by keeping a count of references to each region. using type annotations that make the structure of a program's regions more explicit, we reduce the overhead of reference counting from a maximum of 27% to a maximum of 11% on a suite of realistic benchmarks. we generalise these annotations in a region type system whose main novelty is the use of existentially quantified abstract regions to represent pointers to objects whose region is partially or totally unknown. a distribution of rc is available at http://www.cs.berkeley.edu/~dgay/rc.tar.gz.
memory management with explicit regions. much research has been devoted to studies of and algorithms for memory management based on garbage collection or explicit allocation and deallocation. an alternative approach, region-based memory management, has been known for decades, but has not been well-studied. in a region-based system each allocation specifies a region, and memory is reclaimed by destroying a region, freeing all the storage allocated therein. we show that on a suite of allocation-intensive c programs, regions are competitive with malloc/free and sometimes substantially faster. we also show that regions support safe memory management with low overhead. experience with our benchmarks suggests that modifying many existing programs to use regions is not difficult.
the nesc language: a holistic approach to networked embedded systems. we present nesc, a programming language for networked embedded systems that represent a new design space for application developers. an example of a networked embedded system is a sensor network, which consists of (potentially) thousands of tiny, low-power "motes," each of which execute concurrent, reactive programs that must operate with severe memory and power constraints.nesc's contribution is to support the special needs of this domain by exposing a programming model that incorporates event-driven execution, a flexible concurrency model, and component-oriented application design. restrictions on the programming model allow the nesc compiler to perform whole-program analyses, including data-race detection (which improves reliability) and aggressive function inlining (which reduces resource consumption).nesc has been used to implement tinyos, a small operating system for sensor networks, as well as several significant sensor applications. nesc and tinyos have been adopted by a large number of sensor network research groups, and our experience and evaluation of the language shows that it is effective at supporting the complex, concurrent programming style demanded by this new class of deeply networked systems.
parallelism, persistence and meta-cleanliness in the symmetric lisp interpreter. symmetric lisp is a programming language designed around first-class environments, where an environment is a dictionary that associates names with definitions or values. in this paper we describe the logical structure of the symmetric lisp interpreter. in other interpreted languages, the interpreter is a virtual machine that evaluates user input on the basis of its own internal state. the symmetric lisp interpreter, on the other hand, is a simple finite-state machine with no internal state. its role is to attach user input to whatever environment the user has specified; such environments are transparent objects created by, maintained by and fully accessible to the user. the interpreter's semantics are secondary to the semantics of environments in symmetric lisp: it is the environment-object to which an expression is attached, not the interpreter, that controls the evaluation of expressions.this arrangement has several consequences. because environments in symmetric lisp are governed by a parallel evaluation rule, the symmetric lisp interpreter is a parallel interpreter. a symmetric lisp environment evaluates to another environment; a session with the interpreter therefore yields a well-defined environment object as its result. users are free to write routines that manage these interpreter-created objects - routines that list the elements of a namespace, coalesce environments, maintain multiple name definitions and so on precisely because environment objects may be freely inspected and manipulated. because a named environment may contain other named environments as elements, interpreter-created objects may be regarded as hierarchical file systems. because of the parallel evaluation semantics of environments, the interpreter is well-suited as an interface to a concurrent, language-based computer system that uses symmetric lisp as its base language. we argue that - in short - a basic semantic simplification in symmetric lisp promises a correspondingly basic increase in power at the user-interpreter interface.
taming the ixp network processor. 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.
field analysis: getting useful and low-cost interprocedural information. we present a new limited form of interprocedural analysis called field analysis that can be used by a compiler to reduce the costs of modern language features such as object-oriented programming, automatic memory management, and run-time checks required for type safety. unlike many previous interprocedural analyses, our analysis is cheap, and does not require access to the entire program. field analysis exploits the declared access restrictions placed on fields in a modular language (e.g. field access modifiers in java) in order to determine useful properties of fields of an object. we describe our implementation of field analysis in the swift optimizing compiler for java, as well a set of optimizations that exploit the results of field analysis. these optimizations include removal of run-time tests, compile-time resolution of method calls, object inlining, removal of unnecessary synchronization, and stack allocation. our results demonstrate that field analysis is efficient and effective. speedups average 7% on a wide range of applications, with some times reduced by up to 27%. compile time overhead of field analysis is about 10%.
on the importance of points-to analysis and other memory disambiguation methods for c programs. in this paper, we evaluate the benefits achievable from pointer analysis and other memory disambiguation techniques for c/c++ programs, using the framework of the production compiler for the intel&reg; itanium&trade; processor. most of the prior work on memory disambiguation has primarily focused on pointer analysis, and either presents only static estimates of the accuracy of the analysis (such as average points-to set size), or provides performance data in the context of certain individual optimizations. in contrast, our study is based on a complete memory disambiguation framework that uses a whole set of techniques including pointer analysis. further, it presents how various compiler analyses and optimizations interact with the memory disambiguator, evaluates how much they benefit from disambiguation, and measures the eventual impact on the performance of the program. the paper also analyzes the types of disambiguation queries that are typically received by the disambiguator, which disambiguation techniques prove most effective in resolving them, and what type of queries prove difficult to be resolved. the study is based on empirical data collected for the spec cint2000 c/c++ programs, running on the itanium processor.
dart: directed automated random testing. we present a new tool, named dart, for automatically testing software that combines three main techniques: (1) automated extraction of the interface of a program with its external environment using static source-code parsing; (2) automatic generation of a test driver for this interface that performs random testing to simulate the most general environment the program can operate in; and (3) dynamic analysis of how the program behaves under random testing and automatic generation of new test inputs to direct systematically the execution along alternative program paths. together, these three techniques constitute directed automated random testing, or dart for short. the main strength of dart is thus that testing can be performed completely automatically on any program that compiles -- there is no need to write any test driver or harness code. during testing, dart detects standard errors such as program crashes, assertion violations, and non-termination. preliminary experiments to unit test several examples of c programs are very encouraging.
generational reference counting: a reduced-communication distributed storage reclamation scheme. this paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. it has a significantly lower communication overhead than distributed versions of conventional reference counting. although generational reference counting has greater computational and space requirements than ordinary reference counting, it may provide a significant saving in overall execution time on machines in which message passing is expensive. the communication overhead for generational reference counting is one message for each copy of an interprocessor reference (pointer). unlike conventional reference counting, when a reference to an object is copied no message is sent to the processor on which the object lies. a message is sent only when a reference is discarded. unfortunately, generational reference counting shares conventional reference counting's inability to reclaim cyclical structures. in this paper, we present the generational reference counting algorithm, prove it correct, and discuss some refinements that make it more efficient. we also compare it with weighted reference counting, another distributed reference counting scheme described in the literature.
interprocedural dataflow analysis in an executable optimizer. interprocedural dataflow information enables link-time and post-link-time optimizers to perform analyses and code transformations that are not possible in a traditional compiler. this paper describes the interprocedural dataflow analysis techniques used by spike, a post-linktime optimizer for alpha/nt executables. spike uses dataflow analysis to summarize the register definitions, uses, and kills that occur external to each routine, allowing spike to perform a variety of optimizations that require interprocedural dataflow information. because spike is designed to optimize large pc applications, the time required to perform interprocedural dataflow analysis could potentially be unacceptably long, limiting spike's effectiveness and applicability. to decrease dataflow analysis time, spike uses a compact representation of a program's intraprocedural and interprocedural control flow that efficiently summarizes the register definitions and uses that occur in the program. experimental results are presented for the spec95 integer benchmarks and eight large pc applications. the results show that the compact representation allows spike to compute interprocedural dataflow information in less than 2 seconds for each of the spec95 integer benchmarks. even for the largest pc application containing over 1.7 million instructions in 340 thousand basic blocks, interprocedural dataflow analysis requires just 12 seconds.
orchestrating interactions among parallel computations. many parallel programs contain multiple sub-computations, each with distinct communication and load balancing requirements. the traditional approach to compiling such programs is to impose a processor synchronization barrier between sub-computations, optimizing each as a separate entity. this paper develops a methodology for managing the interactions among sub-computations, avoiding strict synchronization where concurrent or pipelined relationships are possible. our approach to compiling parallel programs has two components: symbolic data access analysis and adaptive runtime support. we summarize the data access behavior of sub-computations (such as loop nests) and split them to expose concurrency and pipelining opportunities. the split transformation has been incorporated into an extended fortran compiler, which outputs a fortran 77 program augmented with calls to library routines written in c and a coarse-grained dataflow graph summarizing the exposed parallelism. the compiler encodes symbolic information, including loop bounds and communication requirements, for an adaptive runtime system, which uses runtime information to improve the scheduling efficiency of irregular sub-computations. the runtime system incorporates algorithms that allocate processing resources to concurrently executing sub-computations and choose communication granularity. we have demonstrated that these dynamic techniques substantially improve performance on a range of production applications including climate modeling and x-ray tomography, expecially when large numbers of processors are available.
division by invariant integers using multiplication. 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 -&infin;, and division where the result is known a priori to be exact. we give some implementation results using the c compiler gcc.
an evaluation of staged run-time optimizations in dyc. previous selective dynamic compilation systems have demonstrated that dynamic compilation can achieve performance improvements at low cost on small kernels, but they have had difficulty scaling to larger programs. to overcome this limitation, we developed dyc, a selective dynamic compilation system that includes more sophisticated and flexible analyses and transformations. dyc is able to achieve good performance improvements on programs that are much larger and more complex than the kernels. we analyze the individual optimizations of dyc and assess their impact on performance collectively and individually.
better extensibility through modular syntax. we explore how to make the benefits of modularity available for syntactic specifications and present rats!, a parser generator for java that supports easily extensible syntax. our parser generator builds on recent research on parsing expression grammars (pegs), which, by being closed under composition, prioritizing choices, supporting unlimited lookahead, and integrating lexing and parsing, offer an attractive alternative to context-free grammars. pegs are implemented by so-called packrat parsers, which are recursive descent parsers that memoize all intermediate results (hence their name). memoization ensures linear-time performance in the presence of unlimited lookahead, but also results in an essentially lazy, functional parsing technique. in this paper, we explore how to leverage pegs and packrat parsers as the foundation for extensible syntax. in particular, we show how make packrat parsing more widely applicable by implementing this lazy, functional technique in a strict, imperative language, while also generating better performing parsers through aggressive optimizations. next, we develop a module system for organizing, modifying, and composing large-scale syntactic specifications. finally, we describe a new technique for managing (global) parsing state in functional parsers. our experimental evaluation demonstrates that the resulting parser generator succeeds at providing extensible syntax. in particular, rats! enables other grammar writers to realize real-world language extensions in little time and code, and it generates parsers that consistently out-perform parsers created by two glr parser generators.
parallel compilation for a parallel machine. an application for a parallel computer with multiple, independent processors often includes different programs (functions) for the individual processors; compilation of such functions can proceed independently. we implemented a compiler that exploits this parallelism by partitioning the input program for parallel translation. the host system for the parallel compiler is an ethernet-based network of workstations, and different functions of the application program are compiled in parallel on different workstations. for typical programs in our environment, we observe a speedup ranging from 3 to 6 using not more than 9 processors. the paper includes detailed measurements for this parallel compiler; we report the system overhead, implementation overhead, as well as the speedup obtained when compared with sequential compilation.
region-based memory management in cyclone. cyclone is a type-safe programming language derived from c. the primary design goal of cyclone is to let programmers control data representation and memory management without sacrificing type-safety. in this paper, we focus on the region-based memory management of cyclone and its static typing discipline. the design incorporates several advancements, including support for region subtyping and a coherent integration with stack allocation and a garbage collector. to support separate compilation, cyclone requires programmers to write some explicit region annotations, but a combination of default annotations, local type inference, and a novel treatment of region effects reduces this burden. as a result, we integrate c idioms in a region-based framework. in our experience, porting legacy c to cyclone has required altering about 8% of the code; of the changes, only 6% (of the 8%) were region annotations.
interprocedural constant propagation: a study of jump function implementations. an implementation of interprocedural constant propagation must model the transmission of values through each procedure. in the framework proposed by callahan, cooper, kennedy, and torczon in 1986, this intraprocedural propagation is modeled with a jump function. while callahan et al. propose several kinds of jump functions, they give no data to help choose between them. this paper reports on a comparative study of jump function implementations. it shows that different jump functions produce different numbers of useful constants; it suggests a particular function, called the pass-through parameter jump function, as the most cost-effective in practice.
improving the cache locality of memory allocation. the allocation and disposal of memory is a ubiquitous operation in most programs. rarely do programmers concern themselves with details of memory allocators; most assume that memory allocators provided by the system perform well. this paper presents a performance evaluation of the reference locality of dynamic storage allocation algorithms based on trace-driven simualtion of five large allocation-intensive c programs. in this paper, we show how the design of a memory allocator can significantly affect the reference locality for various applications. our measurements show that poor locality in sequential-fit allocation algorithms reduces program performance, both by increasing paging and cache miss rates. while increased paging can be debilitating on any architecture, cache misses rates are also important for modern computer architectures. we show that algorithms attempting to be space-efficient by coalescing adjacent free objects show poor reference locality, possibly negating the benefits of space efficiency. at the other extreme, algorithms can expend considerable effort to increase reference locality yet gain little in total execution performance. our measurements suggest an allocator design that is both very fast and has good locality of reference.
combining abstract interpreters. we present a methodology for automatically combining abstract interpreters over given lattices to construct an abstract interpreter for the combination of those lattices. this lends modularity to the process of design and implementation of abstract interpreters.we define the notion of logical product of lattices. this kind of combination is more precise than the reduced product combination. we give algorithms to obtain the join operator and the existential quantification operator for the combined lattice from the corresponding operators of the individual lattices. we also give a bound on the number of steps required to reach a fixed point across loops during analysis over the combined lattice in terms of the corresponding bounds for the individual lattices. we prove that our combination methodology yields the most precise abstract interpretation operators over the logical product of lattices when the individual lattices are over theories that are convex, stably infinite, and disjoint.we also present an interesting application of logical product wherein some lattices can be reduced to combination of other (unrelated) lattices with known abstract interpreters.