waashk/dblp huggingface dataset:
static load classification for improving the value predictability of data-cache misses. while caches are effective at avoiding most main-memory accesses, the few remaining memory references are still expensive. even one cache miss per one hundred accesses can double a program's execution time. to better tolerate the data-cache miss latency, architects have proposed various speculation mechanisms, including load-value prediction. a load-value predictor guesses the result of a load so that the dependent instructions can immediately proceed without having to wait for the memory access to complete. to use the prediction resources most effectively, speculation should be restricted to loads that are likely to miss in the cache and that are likely to be predicted correctly. prior work has considered hardware- and profile-based methods to make these decisions. our work focuses on making these decisions at compile time. we show that a simple compiler classification is effective at separating the loads that should be speculated from the loads that should not. we present results for a number of c and java programs and demonstrate that our results are consistent across programming languages and across program inputs.
a static analyzer for large safety-critical software. we show that abstract interpretation-based static program analysis can be made efficient and precise enough to formally verify a class of properties for a family of large programs with few or no false alarms. this is achieved by refinement of a general purpose static analyzer and later adaptation to particular programs of the family by the end-user through parametrization. this is applied to the proof of soundness of data manipulation operations at the machine level for periodic synchronous safety critical embedded software.the main novelties are the design principle of static analyzers by refinement and adaptation through parametrization (sect. 3 and 7), the symbolic manipulation of expressions to improve the precision of abstract transfer functions (sect. 6.3), the octagon (sect. 6.2.2), ellipsoid (sect. 6.2.3), and decision tree (sect. 6.2.4) abstract domains, all with sound handling of rounding errors in oating point computations, widening strategies (with thresholds: sect. 7.1.2, delayed: sect. 7.1.3) and the automatic determination of the parameters (parametrized packing: sect. 7.2).
fast, effective dynamic compilation. dynamic compilation enables optimization based on the values of invariant data computed at run-time. using the values of these run-time constants, a dynamic compiler can eliminate their memory loads, perform constant propagation and folding, remove branches they determine, and fully unroll loops they bound. however, the performance benefits of the more efficient, dynamically-compiled code are offset by the run-time cost of the dynamic compile. our approach to dynamic compilation strives for both fast dynamic compilation and high-quality dynamically-compiled code: the programmer annotates regions of the programs that should be compiled dynamically; a static, optimizing compiler automatically produces pre-optimized machine-code templates, using a pair of dataflow analyses that identify which variables will be constant at run-time; and a simple, dynamic compiler copies the templates, patching in the computed values of the run-time constants, to produce optimized, executable code. our work targets general- purpose, imperative programming languages, initially c. initial experiments applying dynamic compilation to c programs have produced speedups ranging from 1.2 to 1.8.
corpus-based static branch prediction. correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. the name program-based branch prediction is given to static branch prediction techniques that base their prediction on a program's structure. in this paper, we investigate a new approach to program-based branch prediction that uses a body of existing programs to predict the branch behavior in a new program. we call this approach to program-based branch prediction, evidence-based static prediction, or esp. the main idea of esp is that the behavior of a corpus of programs can be used to infer the behavior of new programs. in this paper, we use a neural network to map static features associated with each branch to the probability that the branch will be taken. esp shows significant advantages over other prediction mechanisms. specifically, it is a program-based technique, it is effective across a range of programming languages and programming styles, and it does not rely on the use of expert-defined heuristics. in this paper, we describe the application of esp to the problem of branch prediction and compare our results to existing program-based branch predictors. we also investigate the applicability of esp across computer architectures, programming languages, compilers, and run-time systems. averaging over a body of 43 c and fortran programs, esp branch prediction results in a miss rate of 20%, as compared with the 25% miss rate obtained using the best existing program-based heuristics.
efficient detection of all pointer and array access errors. we present a pointer and array access checking technique that provides complete error coverage through a simple set of program transformations. our technique, based on an extended safe pointer representation, has a number of novel aspects. foremost, it is the first technique that detects all spatial and temporal access errors. its use is not limited by the expressiveness of the language; that is, it can be applied successfully to compiled or interpreted languages with subscripted and mutable pointers, local references, and explicit and typeless dynamic storage management, e.g., c. because it is a source level transformation, it is amenable to both compile- and run-time optimization. finally, its performance, even without compile-time optimization, is quite good. we implemented a prototype translator for the c language and analyzed the checking overheads of six non-trivial, pointer intensive programs. execution overheads range from 130% to 540%; with text and data size overheads typically below 100%.
on bounding time and space for multiprocessor garbage collection. our paper described a real-time garbage collection algorithm for shared-memory multiprocessors. the work differed from previous work on multiprocessor garbage collection in that we were interested in placing hard bounds on pause times and memory usage. we felt this was important in justifying the term real-time, and for giving users a better handle on actual performance characteristics. although the paper presented an algorithm without an implementation, and made some simplifying assumptions, we put considerable effort into making key aspects of the algorithm practical. in later work [9, 8] we implemented the ideas, and demonstrated performance characteristics that were in line with the characteristics predicted by the theory.this paper presents the first multiprocessor garbage collection algorithm with provable bounds on time and space. the algorithm is a real-time shared-memory copying colector. we prove that the algorithm requires at most 2(r(1 + 2/k) + n + 5pd) memory locations, where p is the number of processors, r is the maximum reachable space during a computation (number of locations accessible from the root set), n is the maximum number of reachable objects, d is the maximum depth of any data object, and k is a parameter specifying how many locations are copied each time a location is allocated. furthermore we show that client threads are never stopped for more than time proportional to k non-blocking machine instructions. the bounds are guaranteed even with arbitrary length arrays. the collector only requires write-barriers (reads are unaffected by the collector), makes few assumptions about the threads that are generating the garbage, and allows them to run mostly asynchronously.
eliminating array bound checking through dependent types. we present a type-based approach to eliminating array bound checking and list tag checking by conservatively extending standard ml with a restricted form of dependent types. this enables the programmer to capture more invariants through types while type-checking remains decidable in theory and can still be performed efficiently in practice. we illustrate our approach through concrete examples and present the result of our preliminary experiments which support support the feasibility and effectiveness of our approach.
optimising aspectj. aspectj, an aspect-oriented extension of java, is becoming increasingly popular. however, not much work has been directed at optimising compilers for aspectj. optimising aop languages provides many new and interesting challenges for compiler writers, and this paper identifies and addresses three such challenges.first, compiling around advice efficiently is particularly challenging. we provide a new code generation strategy for around advice, which (unlike previous implementations) both avoids the use of excessive inlining and the use of closures. we show it leads to more compact code, and can also improve run-time performance. second, woven code sometimes includes run-time tests to determine whether advice should execute. one important case is the cflow pointcut which uses information about the dynamic calling context. previous techniques for cflow were very costly in terms of both time and space. we present new techniques to minimise or eliminate the overhead of cflow using both intra- and inter-procedural analyses. third, we have addressed the general problem of how to structure an optimising compiler so that traditional analyses can be easily adapted to the aop setting.we have implemented all of the techniques in this paper in abc, our aspectbench compiler for aspectj, and we demonstrate significant speedups with empirical results. some of our techniques have already been integrated into the production aspectj compiler, ajc 1.2.1.
improving register allocation for subscripted variables. most conventional compilers fail to allocate array elements to registers because standard data-flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. this deficiency is particularly troublesome for floating-point registers, which are most often used as temporary repositories for subscripted variables.in this paper, we present a source-to-source transformation, called scalar replacement, that finds opportunities for reuse of subscripted variables and replaces the references involved by references to temporary scalar variables. the objective is to increase the likelihood that these elements will be assigned to registers by the coloring-based register allocators found in most compilers. in addition, we present transformations to improve the overall effectiveness of scalar replacement and show how these transformations can be applied in a variety of loop nest types. finally, we present experimental results showing that these techniques are extremely effective---capable of achieving integer factor speedups over code generated by good optimizing compilers of conventional design.
scalable cross-module optimization. large applications are typically partitioned into separately compiled modules. large performance gains in these applications are available by optimizing across module boundaries. one barrier to applying crossmodule optimization (cmo) to large applications is the potentially enormous amount of time and space consumed by the optimization process.we describe a framework for scalable cmo that provides large gains in performance on applications that contain millions of lines of code. two major techniques are described. first, careful management of in-memory data structures results in sub-linear memory occupancy when compared to the number of lines of code being optimized. second, profile data is used to focus optimization effort on the performance-critical portions of applications. we also present practical issues that arise in deploying this framework in a production environment. these issues include debuggability and compatibility with existing development tools, such as make. our framework is deployed in hewlett-packard's (hp) unix compiler products and speeds up shipped independent software vendors' applications by as much as 71%.
traceback: first fault diagnosis by reconstruction of distributed control flow. faults that occur in production systems are the most important faults to fix, but most production systems lack the debugging facilities present in development environments. traceback provides debugging information for production systems by providing execution history data about program problems (such as crashes, hangs, and exceptions). traceback supports features commonly found in production environments such as multiple threads, dynamically loaded modules, multiple source languages (e.g., java applications running with jni modules written in c++), and distributed execution across multiple computers. traceback supports first fault diagnosis-discovering what went wrong the first time a fault is encountered. the user can see how the program reached the fault state without having to re-run the computation; in effect enabling a limited form of a debugger in production code.traceback uses static, binary program analysis to inject low-overhead runtime instrumentation at control-flow block granularity. post-facto reconstruction of the records written by the instrumentation code produces a source-statement trace for user diagnosis. the trace shows the dynamic instruction sequence leading up to the fault state, even when the program took exceptions or terminated abruptly (e.g., kill -9).we have implemented traceback on a variety of architectures and operating systems, and present examples from a variety of platforms. performance overhead is variable, from 5% for apache running specweb99, to 16%-25% for the java specjbb benchmark, to 60% average for specint2000. we show examples of traceback's cross-language and cross-machine abilities, and report its use in diagnosing problems in production software.
java without the coffee breaks: a nonintrusive multiprocessor garbage collector. the deployment of java as a concurrent programming language has created a critical need for high-performance, concurrent, and incremental multiprocessor garbage collection. we present the recycler, a fully concurrent pure reference counting garbage collector that we have implemented in the jalape&ntilde;o java virtual machine running on shared memory multiprocessors. while a variety of multiprocessor collectors have been proposed and some have been implemented, experimental data is limited and there is little quantitative basis for comparison between different algorithms. we present measurements of the recycler and compare it against a non-concurrent but parallel load-balancing mark-and-sweep collector (that we also implemented in jalape&ntilde;o), and evaluate the classical tradeoff between response time and throughput. when processor or memory resources are limited, the recycler runs at about 90% of the speed of the mark-and-sweep collector. however, with an extra processor to run collection and with a moderate amount of memory headroom, the recycler is able to operate without ever blocking the mutators and achieves a maximum measured mutator delay of only 2.6 milliseconds for our benchmarks. end-to-end execution time is usually within 5%.
thin locks: featherweight synchronization for java. language-supported synchronization is a source of serious performance problems in many java programs. even single-threaded applications may spend up to half their time performing useless synchronization due to the thread-safe nature of the java libraries. we solve this performance problem with a new algorithm that allows lock and unlock operations to be performed with only a few machine instructions in the most common cases. our locks only require a partial word per object, and were implemented without increasing object size. we present measurements from our implementation in the jdk 1.1.2 for aix, demonstrating speedups of up to a factor of 5 in micro-benchmarks and up to a factor of 1.7 in real programs.
contaminated garbage collection. we describe a new method for determining when an object can be garbage collected. the method does not require marking live objects. instead, each object x is dynamically associated with a stack frame m, such that xis collectable when m pops. because x could have been dead earlier, our method is conservative. our results demonstrate that the method nonetheless identifies a large percentage of collectable objects. the method has been implemented in sun's java virtual machine interpreter, and results are presented based on this implementation
flow-sensitive interprocedural constant propagation. we present a flow-sensitive interprocedural constant propagation algorithm, which supports recursion while only performing one flow-sensitive analysis of each procedure. we present experimental results which show that this method finds substantially more constants than previous methods and is efficient in practice. we introduce new metrics for evaluating interprocedural constant propagation algorithms which measure the number of interprocedural constant values that are propagated. we use these metrics to provide further experimental results for our algorithm.
a generator for language-specific debugging systems. we present a system which generates interactive high-level debugging systems from formal language definitions. the language definer has to specify a denotational semantics augmented with a formal description of the language specific debugging facilities. the generated debugger offers the traditional features such as tracing programs, setting breakpoints, displaying variables etc; interaction with the user is always on language level rather than on machine level. the concept has been implemented as part of the psg-programming system generator, and has successfully been used to generate debuggers for pascal and modula-2. the core of the implementation consists of an interpreter for a functional language, which has been extended with the language-independent mechanisms needed in order to allow interaction with the user during program execution.
the atomos transactional programming language. atomos is the first programming language with implicit transactions, strong atomicity, and a scalable multiprocessor implementation. atomos is derived from java, but replaces its synchronization and conditional waiting constructs with simpler transactional alternatives.the atomos watch statement allows programmers to specify fine-grained watch sets used with the atomos retry conditional waiting statement for efficient transactional conflict-driven wakeup even in transactional memory systems with a limited number of transactional contexts. atomos supports open-nested transactions, which are necessary for building both scalable application programs and virtual machine implementations.the implementation of the atomos scheduler demonstrates the use of open nesting within the virtual machine and introduces the concept of transactional memory violation handlers that allow programs to recover from data dependency violations without rolling back.atomos programming examples are given to demonstrate the usefulness of transactional programming primitives. atomos and java are compared through the use of several benchmarks. the results demonstrate both the improvements in parallel programming ease and parallel program performance provided by atomos.
target-sensitive construction of diagnostic programs for procedure calling sequence generators. building compilers that generate correct code is difficult. in this paper we present a compiler testing technique that closes the gap between actual compiler implementations and correct compilers. using formal specifications of procedure calling conventions, we have built a target-sensitive test suite generator that builds test cases for a specific aspect of compiler code generators: the procedure calling sequence generator. by exercising compilers with these target-specific test suites, our automated testing tool has been able to expose and isolate 8 bugs in heavily used production-quality compilers. these bugs cause more than 700 test cases to fail.
the semantics of program dependence. optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependencies among atomic program operations. in this paper, we provide a semantic justification for this practice by deriving two different forms of program dependence graph &mdash; the output pdg and the def-order pdg&mdash;and their semantic definitions from non-strict generalizations of the denotational semantics of the programming language. in the process, we demonstrate that both the output pdg and the def-order pdg (with minor technical modifications) are conventional data-flow programs. in addition, we show that the semantics of the def-order pdg dominates the semantics of the output pdg and that both of these semantics dominate&mdash;rather than preserve&mdash;the semantics of sequential execution.
maya: multiple-dispatch syntax extension in java. we have designed and implemented maya, a version of java that allows programmers to extend and reinterpret its syntax. maya generalizes macro systems by treating grammar productions as generic functions, and semantic actions on productions as multimethods on the corresponding generic functions. programmers can write new generic functions (i.e., grammar productions) and new multimethods (i.e., semantic actions), through which they can extend the grammar of the language and change the semantics of its syntactic constructs, respectively. maya's multimethods are compile-time metaprograms that transform abstract syntax: they execute at program compile-time, because they are semantic actions executed by the parser. maya's multimethods can be dispatched on the syntactic structure of the input, as well as the static, source-level types of expressions in the input. in this paper we describe what maya can do and how it works. we describe how its novel parsing techniques work and how maya can statically detect certain kinds of errors, such as code that generates references to free variables. finally, to demonstrate maya's expressiveness, we describe how maya can be used to implement the multijava language, which was described by clifton et al. at oopsla 2000.
soft typing. type systems are designed to prevent the improper use of program operations. they can be classified as either static or dynamic depending on when they detect type errors. static type systems detect potential type errors at compile-time and prevent program execution. dynamic type systems detect type errors at run-time and abort program execution.static type systems have two important advantages over dynamic type systems. first, they help programmers detect a large class of program errors before execution. second, they extract information that a compiler can exploit to produce more efficient code. the price paid for these advantages, however, is a loss of expressiveness, generality, and semantic simplicity.this paper presents a generalization of static and dynamic typing---called soft typing---that combines the best features of both approaches. the key idea underlying soft typing is that a static type checker need not reject programs that contain potential type errors. instead, the type checker can insert explicit run-time checks around "suspect" arguments of primitive operations, converting dynamically typed programs into statically type-correct form. the inserted run-time checks identify program phrases that may be erroneous. for soft typing to be effective, the type system must avoid inserting unnecessary run-time checks. to accomplish this objective, we have developed an extension of the ml type system supporting union types and recursive types that assigns types to a wider class of programs than ml. we have also developed an algorithm for frugally inserting run-time checks in programs that do not type check.