waashk/dblp huggingface dataset:
automatic pool allocation: improving performance by controlling data structure layout in the heap. this paper describes automatic pool allocation, a transformation framework that segregates distinct instances of heap-based data structures into seperate memory pools and allows heuristics to be used to partially control the internal layout of those data structures. the primary goal of this work is performance improvement, not automatic memory management, and the paper makes several new contributions. the key contribution is a new compiler algorithm for partitioning heap objects in imperative programs based on a context-sensitive pointer analysis, including a novel strategy for correct handling of indirect (and potentially unsafe) function calls. the transformation does not require type safe programs and works for the full generality of c and c++. second, the paper describes several optimizations that exploit data structure partitioning to further improve program performance. third, the paper evaluates how memory hierarchy behavior and overall program performance are impacted by the new transformations. using a number of benchmarks and a few applications, we find that compilation times are extremely low, and overall running times for heap intensive programs speed up by 10-25% in many cases, about 2x in two cases, and more than 10x in two small benchmarks. overall, we believe this work provides a new framework for optimizing pointer intensive programs by segregating and controlling the layout of heap-based data structures.
online performance auditing: using hot optimizations without getting burned. as hardware complexity increases and virtualization is added at more layers of the execution stack, predicting the performance impact of optimizations becomes increasingly difficult. production compilers and virtual machines invest substantial development effort in performance tuning to achieve good performance for a range of benchmarks. although optimizations typically perform well on average, they often have unpredictable impact on running time, sometimes degrading performance significantly. today's vms perform sophisticated feedback-directed optimizations, but these techniques do not address performance degradations, and they actually make the situation worse by making the system more unpredictable.this paper presents an online framework for evaluating the effectiveness of optimizations, enabling an online system to automatically identify and correct performance anomalies that occur at runtime. this work opens the door for a fundamental shift in the way optimizations are developed and tuned for online systems, and may allow the body of work in offline empirical optimization search to be applied automatically at runtime. we present our implementation and evaluation of this system in a product java vm.
lazy functional state threads. some algorithms make critical internal use of updatable state, even though their external specification is purely functional. based on earlier work on monads, we present a way of securely encapsulating stateful computations that manipulate multiple, named, mutable objects, in the context of a non-strict, purely-functional language.the security of the encapsulation is assured by the type system, using parametricity. intriguingly, this parametricity requires the provision of a (single) constant with a rank-2 polymorphic type.
optimizing programs over the constructive reals. the constructive reals provide programmers with a useful mechanism for prototyping numerical programs, and for experimenting with numerical algorithms. unfortunately, the performance of current implementations is inadequate for some potential applications. in particular, these implementations tend to be space inefficient, in that they essentially require a complete computation history to be maintained. some numerical analysts (cf. [3]) propose that the programmer instead be provided with variable precision interval arithmetic, and then be required to write code to restart a computation when the intervals become too inaccurate. though this model is no doubt appropriate at times, it is not an adequate replacement for exact arithmetic. the correct transformation from a program operating on the constructive reals to a reasonable program using iterated interval arithmetic can be nontrivial and error prone. here we present a technique based on program slicing to both automate this process and reduce the amount of reexecution. thus the programmer is still free to use the simpler abstraction of exact real arithmetic, but we can provide a more efficient interval arithmetic based implementation. some preliminary empirical results are presented.
optimizing ml with run-time code generation. we describe the design and implementation of a compiler that automatically translates ordinary programs written in a subset of ml into code that generates native code at run time. run-time code generation can make use of values and invariants that cannot be exploited at compile time, yielding code that is often superior to statically optimal code. but the cost of optimizing and generating code at run time can be prohibitive. we demonstrate how compile-time specialization can reduce the cost of run-time code generation by an order of magnitude without greatly affecting code quality. several benchmark programs are examined, which exhibit an average cost of only six cycles per instruction generated at run time.
using data groups to specify and check side effects. reasoning precisely about the side effects of procedure calls is important to many program analyses. this paper introduces a technique for specifying and statically checking the side effects of methods in an object-oriented language. the technique uses data groups, which abstract over variables that are not in scope, and limits program behavior by two alias-confining restrictions, pivot uniqueness and owner exclusion. the technique is shown to achieve modular soundness and is simpler than previous attempts at solving this problem.
automatically proving the correctness of compiler optimizations. we describe a technique for automatically proving compiler optimizations sound, meaning that their transformations are always semantics-preserving. we first present a domain-specific language, called cobalt, for implementing optimizations as guarded rewrite rules. cobalt optimizations operate over a c-like intermediate representation including unstructured control flow, pointers to local variables and dynamically allocated memory, and recursive procedures. then we describe a technique for automatically proving the soundness of cobalt optimizations. our technique requires an automatic theorem prover to discharge a small set of simple, optimization-specific proof obligations for each optimization. we have written a variety of forward and backward intraprocedural dataflow optimizations in cobalt, including constant propagation and folding, branch folding, full and partial redundancy elimination, full and partial dead assignment elimination, and simple forms of points-to analysis. we implemented our soundness-checking strategy using the simplify automatic theorem prover, and we have used this implementation to automatically prove our optimizations correct. our checker found many subtle bugs during the course of developing our optimizations. we also implemented an execution engine for cobalt optimizations as part of the whirlwind compiler infrastructure.
static single assignment form for machine code. static single assignment (ssa) is an effective intermediate representation in optimizing compilers. however, traditional ssa form and optimizations are not applicable to programs represented as native machine instructions because the use of dedicated registers imposed by calling conventions, the runtime system, and target architecture must be made explicit. we present a simple scheme for converting between programs in machine code and in ssa, such that references to dedicated physical registers in machine code are preserved. our scheme ignores all output- and anti-dependences imposed by physical registers while a program is in ssa form, but inserts compensation code during machine code reconstruction if any naming requirements have been violated. by resolving all mismatches between the two representations in separate phases, we are able to utilize existing ssa algorithms unaltered to perform machine code optimizations.
the implementation and evaluation of fusion and contraction in array languages. array languages such as fortran 90, hpf and zpl have many benefits in simplifying array-based computations and expressing data parallelism. however, they can suffer large performance penalties because they introduce intermediate arrays---both at the source level and during the compilation process---which increase memory usage and pollute the cache. most compilers address this problem by simply scalarizing the array language and relying on a scalar language compiler to perform loop fusion and array contraction. we instead show that there are advantages to performing a form of loop fusion and array contraction at the array level. this paper describes this approach and explains its advantages. experimental results show that our scheme typically yields runtime improvements of greater than 20% and sometimes up to 400%. in addition, it yields superior memory use when compared against commercial compilers and exhibits comparable memory use when compared with scalar languages. we also explore the interaction between these transformations and communication optimizations.
jedd: a bdd-based relational extension of java. in this paper we present jedd, a language extension to java that supports a convenient way of programming with binary decision diagrams (bdds). the jedd language abstracts bdds as database-style relations and operations on relations, and provides static type rules to ensure that relational operations are used correctly.the paper provides a description of the jedd language and reports on the design and implementation of the jedd translator and associated runtime system. of particular interest is the approach to assigning attributes from the high-level relations to physical domains in the underlying bdds, which is done by expressing the constraints as a sat problem and using a modern sat solver to compute the solution. further, a runtime system is defined that handles memory management issues and supports a browsable profiling tool for tuning the key bdd operations.the motivation for designing jedd was to support the development of whole program analyses based on bdds, and we have used jedd to express five key interrelated whole program analyses in our soot compiler framework. we provide some examples of this application and discuss our experiences using jedd.
storage assignment to decrease code size. dsp architectures typically provide indirect addressing modes with auto-increment and decrement. in addition, indexing mode is not available, and there are usually few, if any, general-purpose registers. hence, it is necessary to use address registers and perform address arithmetic to access automatic variables. subsuming the address arithmetic into auto-increment and auto-decrement modes improves the size of the generated code.in this paper we present a formulation of the problem of optimal storage assignment such that explicit instructions for address arithmetic are minimized. we prove that for the case of a single address register the decision problem is np-complete. we then generalize the problem to multiple address registers. for both cases heuristic algorithms are given. our experimental results indicate an improvement of 3.
bug isolation via remote program sampling. 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.
scalable statistical bug isolation. we present a statistical debugging algorithm that isolates bugs in programs containing multiple undiagnosed bugs. earlier statistical algorithms that focus solely on identifying predictors that correlate with program failure perform poorly when there are multiple bugs. our new technique separates the effects of different bugs and identifies predictors that are associated with individual bugs. these predictors reveal both the circumstances under which bugs occur as well as the frequencies of failure modes, making it easier to prioritize debugging efforts. our algorithm is validated using several case studies, including examples in which the algorithm identified previously unknown, significant crashing bugs in widely used systems.
a compiler framework for speculative analysis and optimizations. speculative execution, such as control speculation and data speculation, is an effective way to improve program performance. using edge/path profile information or simple heuristic rules, existing compiler frameworks can adequately incorporate and exploit control speculation. however, very little has been done so far to allow existing compiler frameworks to incorporate and exploit data speculation effectively in various program transformations beyond instruction scheduling. this paper proposes a speculative ssa form to incorporate information from alias profiling and/or heuristic rules for data speculation, thus allowing existing program analysis frameworks to be easily extended to support both control and data speculation. such a general framework is very useful for epic architectures that provide checking (such as advanced load address table (alat) [10]) on data speculation to guarantee the correctness of program execution. we use ssapre [21] as one example to illustrate how to incorporate data speculation in those important compiler optimizations such as partial redundancy elimination (pre), register promotion, strength reduction and linear function test replacement. our extended framework allows both control and data speculation to be performed on top of ssapre and, thus, enables more aggressive speculative optimizations. the proposed framework has been implemented on intel's open research compiler (orc). we present experimental data on some spec2000 benchmark programs to demonstrate the usefulness of this framework and how data speculation benefits partial redundancy elimination.
compiler analysis of irregular memory accesses. irregular array accesses are array accesses whose array subscripts do not have closed-form expressions in terms of loop indices. traditional array analysis and loop transformation techniques cannot handle irregular array accesses. in this paper, we study two kinds of simple and common cases of irregular array accesses: single-indexed access and indirect array access. we present techniques to analyze these two cases at compile-time, and we provide experimental results showing the effectiveness of these techniques in finding more implicit loop parallelism at compile-time and improved speedups.
promises: linguistic support for efficient asynchronous procedure calls in distributed systems. this paper deals with the integration of an efficient asynchronous remote procedure call mechanism into a programming language. it describes a new data type called a promise that was designed to support asynchronous calls. promises allow a caller to run in parallel with a call and to pick up the results of the call, including any exceptions it raises, in a convenient and type-safe manner. the paper also discusses efficient composition of sequences of asynchronous calls to different locations in a network.
parametric regular path queries. regular path queries are a way of declaratively expressing queries on graphs as regular-expression-like patterns that are matched against paths in the graph. there are two kinds of queries: existential queries, which specify properties about individual paths, and universal queries, which specify properties about all paths. they provide a simple and convenient framework for expressing program analyses as queries on graph representations of programs, for expressing verification (model-checking) problems as queries on transition systems, for querying semi-structured data, etc. parametric regular path queries extend the patterns with variables, called parameters, which significantly increase the expressiveness by allowing additional information along single or multiple paths to be captured and relate.this paper shows how a variety of program analysis and model-checking problems can be expressed easily and succinctly using parametric regular path queries. the paper describes the specification, design, analysis, and implementation of algorithms and data structures for efficiently solving existential and universal parametric regular path queries. major contributions include the first complete algorithms and data structures for directly and efficiently solving existential and universal parametric regular path queries, detailed complexity analysis of the algorithms, detailed analytical and experimental performance comparison of variations of the algorithms and data structures, and investigation of efficiency tradeoffs between different formulations of queries.
split-stream dictionary program compression. this paper describes split-stream dictionary (ssd) compression, a new technique for transforming programs into a compact, interpretable form. we define a compressed program as interpretable when it can be decompressed at basic-block granularity with reasonable efficiency. the granularity requirement enables interpreters or just-in-time (jit) translators to decompress basic blocks incrementally during program execution. our previous approach to interpretable compression, the byte-coded risc (brisc) program format [1], achieved unprecedented decompression speed in excess of 5 megabytes per second on a 450mhz pentium ii while compressing benchmark programs to an average of three-fifths the size of their optimized x86 representation. ssd compression combines the key idea behind brisc with new observations about instruction re-use frequencies to yield four advantages over brisc and other competing techniques. first, ssd is simple, requiring only a few pages of code for an effective implementation. second, ssd compresses programs more effectively than any interpretable program compression scheme known to us. for example, ssd compressed a set of programs including the spec95 benchmarks and microsoft word97 to less than half the size, on average, of their optimized x86 representation. third, ssd exceeds brisc's decompression and jit translation rates by over 50%. finally, ssd's two-phased approach to jit translation enables a virtual machine to provide graceful degradation of program execution time in the face of increasing ram constraints. for example, using ssd, we ran word97 using a jit-translation buffer one-third the size of word97's optimized x86 code, yet incurred only 27% execution time overhead.
call-cost directed register allocation. choosing the right kind of register for a live range plays a major role in eliminating the register-allocation overhead when the compiled function is frequently executed or function tails are on the most frequently executed paths. picking the wrong kind of register for a live range incurs a high penalty that may dominate the total overhead of register allocation. in this paper, we present three improvements, storage-class analysis, benefit-driven simplification, and preference decision that are effective in selecting the right kind of register for a live range. then we compare an enhanced chaitin-style register allocator (with these three improvements) with priority-based and optimistic coloring.
pin: building customized program analysis tools with dynamic instrumentation. robust and powerful software instrumentation tools are essential for program analysis tasks such as profiling, performance evaluation, and bug detection. to meet this need, we have developed a new instrumentation system called pin. our goals are to provide easy-to-use, portable, transparent, and efficient instrumentation. instrumentation tools (called pintools) are written in c/c++ using pin's rich api. pin follows the model of atom, allowing the tool writer to analyze an application at the instruction level without the need for detailed knowledge of the underlying instruction set. the api is designed to be architecture independent whenever possible, making pintools source compatible across different architectures. however, a pintool can access architecture-specific details when necessary. instrumentation with pin is mostly transparent as the application and pintool observe the application's original, uninstrumented behavior. pin uses dynamic compilation to instrument executables while they are running. for efficiency, pin uses several techniques, including inlining, register re-allocation, liveness analysis, and instruction scheduling to optimize instrumentation. this fully automated approach delivers significantly better instrumentation performance than similar tools. for example, pin is 3.3x faster than valgrind and 2x faster than dynamorio for basic-block counting. to illustrate pin's versatility, we describe two pintools in daily use to analyze production software. pin is publicly available for linux platforms on four architectures: ia32 (32-bit x86), em64t (64-bit x86), itanium®, and arm. in the ten months since pin 2 was released in july 2004, there have been over 3000 downloads from its website.
jungloid mining: helping to navigate the api jungle. reuse of existing code from class libraries and frameworks is often difficult because apis are complex and the client code required to use the apis can be hard to write. we observed that a common scenario is that the programmer knows what type of object he needs, but does not know how to write the code to get the object.in order to help programmers write api client code more easily, we developed techniques for synthesizing jungloid code fragments automatically given a simple query that describes that desired code in terms of input and output types. a jungloid is simply a unary expression; jungloids are simple, enabling synthesis, but are also versatile, covering many coding problems, and composable, combining to form more complex code fragments. we synthesize jungloids using both api method signatures and jungloids mined from a corpus of sample client programs.we implemented a tool, prospector, based on these techniques. prospector is integrated with the eclipse ide code assistance feature, and it infers queries from context so there is no need for the programmer to write queries. we tested prospector on a set of real programming problems involving apis; prospector found the desired solution for 18 of 20 problems. we also evaluated prospector in a user study, finding that programmers solved programming problems more quickly and with more reuse when using prospector than without prospector.