waashk/dblp huggingface dataset:
a practical data flow framework for array reference analysis and its use in optimizations. data flow analysis techniques have traditionally been restricted to the analysis of scalar variables. this retriction, however, imposes a limitation on the kinds of optimizations that can be performed in loops containing array references. we present a data flow framework for array reference analysis that provides the information needed in various optimizations targeted at sequential or fine-grained parallel architectures. the framework extends the traditional scalar framework by incorporating iteration distance values into the analysis to qualify the computed data flow solution during the fixed point iteration. analyses phrased in this framework are capable of discovering recurrent access patterns among array references that evolve during the execution of a loop. applications of our framework are discussed for register allocation, load/store optimizations, and controlled loop unrolling.
module-sensitive program specialisation. we present an approach for specialising large programs, such as programs consisting of several modules, or libraries. this approach is based on the idea of using a compiler generator (cogen) for creating generating extensions. generating extensions are specialisers specialised with respect to some input program. when run on some input data the generating extension produces a specialised version of the input program. here we use the cogen to tailor modules for specialisation. this happens once and for all, independently of all other modules. the resulting module can then be used as a building block for generating extensions for complete programs, in much the same way as the original modules can be put together into complete programs. the result of running the final generating extension is a collection of residual modules, with a module structure derived from the original program.
guardians in a generation-based garbage collector. this paper describes a new language feature that allows dynamically allocated objects to be saved from deallocation by an automatic storage management system so that clean-up or other actions can be performed using the data stored within the objects. the program has full control over the timing of clean-up actions, which eliminates several potential problems and often eliminates the need for critical sections in code that interacts with clean-up actions. our implementation is &ldquo;generation-friendly&rdquo; in the sense that the additional overhead within a generation-based garbage collector is proportional to the work already done there, and the overhead within the mutator is proportional to the number of clean-up actions actually performed.
vliw compilation techniques in a superscalar environment. we describe techniques for converting the intermediate code representation of a given program, as generated by a modern compiler, to another representation which produces the same run-time results, but can run faster on a superscalar machine. the algorithms, based on novel parallelization techniques for very long instruction word (vliw) architectures, find and place together independently executable operations that may be far apart in the original code. i.e., they may be separated by many conditional branches or belong to different iterations of a loop. as a result, the functional units in the superscalar are presented with more work that can proceed in parallel, thus achieving higher performance than the approach of using hardware instruction dispatch techniques alone.while general scheduling techniques improve performance by removing idle pipeline cycles, to further improve performance on a superscalar with only a few functional units requires a reduction in the pathlength. we have designed a set of new algorithms for reducing pathlength and removing stalls due to branches, namely speculative load-store motion out of loops, unspeculation, limited combining, basic block expansion, and prolog tailoring. these algorithms were implemented in a prototype version of the ibm rs/6000 xlc compiler and have shown significant improvement in spec integer benchmarks on the ibm power machines.also, we describe a new technique to obtain profiling information with low overhead, and some applications of profiling directed feedback, including scheduling heuristics, code reordering and branch reversal.
distributed garbage collection. there are two basic approachs to the problem of storage reclamation, process- and processor-based, named for the view point used to recognize when a particular piece of storage can be reclaimed. examples of the processor approach include mark/sweep and copying algorithms and their variants, while reference counting schemes use a process view of the collection. it is argued that the process approach is better suited for distributed computation where links between dynamically allocated objects may cross processor boundaries. in addition, the process approach allows the heap to be more conveniently shared with other processes in those cases when different processes might not have their own virtual address spaces. a new algorithm using the process approach is given. its space requirement per object is better than that for reference counting. in addition, a restricted form of pointer replacement is supported which allows circular structures so constructed to be properly collected.
a reduced multipipeline machine description that preserves scheduling constraints. high performance compilers increasingly rely on accurate modeling of the machine resources to efficiently exploit the instruction level parallelism of an application. in this paper, we propose a reduced machine description that results in faster detection of resource contentions while preserving the scheduling constraints present in the original machine description. the proposed approach reduces a machine description in an automated, error-free, and efficient fashion, moreover, it fully supports schedulers that backtrack and process operations in arbitrary order. reduced descriptions for the dec alpha 21064, mips r3000/r3010, and cydra 5 result in 4 to 7 times faster detection of resource contentions and require 22 to 90% of the memory storage used by the original machine descriptions. precise measurement for the cydra 5 indicates that reducing the machine description results in a 2.9 times faster contention query module.
efficient formulation for optimal modulo schedulers. modulo scheduling algorithms based on optimal solvers have been proposed to investigate and tune the performance of modulo scheduling heuristics. while recent advances have broadened the scope for which the optimal approach is applicable, this approach increasingly suffers from large execution times. in this paper, we propose a more efficient formulation of the modulo scheduling space that significantly decreases the execution time of solvers based on integer linear programs. for example, the total execution time is reduced by a factor of 8.6 when 782 loops from the perfect club, spec, and livermore fortran kernels are scheduled for minimum register requirements using the more efficient formulation instead of the traditional formulation. experimental evidence further indicates that significantly larger loops can be scheduled under realistic machine constraints.
vectorization for simd architectures with alignment constraints. when vectorizing for simd architectures that are commonly employed by today's multimedia extensions, one of the new challenges that arise is the handling of memory alignment. prior research has focused primarily on vectorizing loops where all memory references are properly aligned. an important aspect of this problem, namely, how to vectorize misaligned memory references, still remains unaddressed.this paper presents a compilation scheme that systematically vectorizes loops in the presence of misaligned memory references. the core of our technique is to automatically reorganize data in registers to satisfy the alignment requirement imposed by the hardware. to reduce the data reorganization overhead, we propose several techniques to minimize the number of data reorganization operations generated. during the code generation, our algorithm also exploits temporal reuse when aligning references that access contiguous memory across loop iterations. our code generation scheme guarantees to never load the same data associated with a single static access twice. experimental results indicate near peak speedup factors, e.g., 3.71 for 4 data per vector and 6.06 for 8 data per vector, respectively, for a set of loops where 75% or more of the static memory references are misaligned.
flick: a flexible, optimizing idl compiler. an interface definition language (idl) is a nontraditional language for describing interfaces between software components. idl compilers generate "stubs" that provide separate communicating processes with the abstraction of local object invocation or procedure call. high-quality stub generation is essential for applications to benefit from component-based designs, whether the components reside on a single computer or on multiple networked hosts. typical idl compilers, however, do little code optimization, incorrectly assuming that interprocess communication is always the primary bottleneck. more generally, typical idl compilers are "rigid" and limited to supporting only a single idl, a fixed mapping onto a target language, and a narrow range of data encodings and transport mechanisms.flick, our new idl compiler, is based on the insight that idls are true languages amenable to modern compilation techniques. flick exploits concepts from traditional programming language compilers to bring both flexibility and optimization to the domain of idl compilation. through the use of carefully chosen intermediate representations, flick supports multiple idls, diverse data encodings, multiple transport mechanisms, and applies numerous optimizations to all of the code it generates. our experiments show that flick-generated stubs marshal data between 2 and 17 times faster than stubs produced by traditional idl compilers, and on today's generic operating systems, increase end-to-end throughput by factors between 1.2 and 3.7.
vyrd: verifying concurrent programs by runtime refinement-violation detection. we present a runtime technique for checking that a concurrently-accessed data structure implementation, such as a file system or the storage management module of a database, conforms to an executable specification that contains an atomic method per data structure operation. the specification can be provided separately or a non-concurrent, "atomized" interpretation of the implementation can serve as the specification. the technique consists of two phases. in the first phase, the implementation is instrumented in order to record information into a log during execution. in the second, a separate verification thread uses the logged information to drive an instance of the specification and to check whether the logged execution conforms to it. we paid special attention to the general applicability and scalability of the techniques and to minimizing their concurrency and performance impact. the result is a lightweight verification method that provides a significant improvement over testing for concurrent programs.we formalize conformance to a specification using the notion of refinement: each trace of the implementation must be equivalent to some trace of the specification. among the novel features of our work are two variations on the definition of refinement appropriate for runtime checking: i/o and "view" refinement. these definitions were motivated by our experience with two industrial-scale concurrent data structure implementations: the boxwood project, a b-link tree data structure built on a novel storage infrastructure [10] and the scan file system [9]. i/o and view refinement checking were implemented as a verification tool named vryd (verifying concurrent programs by runtime refinement-violation detection). vyrd was applied to the verification of boxwood, java class libraries, and, previously, to the scan filesystem. it was able to detect previously unnoticed subtle concurrency bugs in boxwood and the scan file system, and the known bugs in the java class libraries and manually constructed examples. experimental results indicate that our techniques have modest computational cost.
context-sensitive interprocedural points-to analysis in the presence of function pointers. this paper reports on the design, implementation, and empirical results of a new method for dealing with the aliasing problem in c. the method is based on approximating the points-to relationships between accessible stack locations, and can be used to generate alias pairs, or used directly for other analyses and transformations. our method provides context-sensitive interprocedural information based on analysis over invocation graphs that capture all calling contexts including recursive and mutually-recursive calling contexts. furthermore, the method allows the smooth integration for handling general function pointers in c. we illustrate the effectiveness of the method with empirical results from an implementation in the mccat optimizing/parallelizing c compiler.
beg - a generator for efficient back ends. this paper describes a system that generates compiler back ends from a strictly declarative specification of the code generation process. the generated back ends use tree pattern matching for code selection. two methods for register allocation supporting a wide range of target architectures are provided. a general bottom-up pattern matching method avoids problems that occurred with previous systems using lr-parsing. the performance of compilers using generated back ends is comparable to very fast production compilers. some figures are given about the results of using the system to generate the back end of a modula-2 compiler.
vcode: a retargetable, extensible, very fast dynamic code generation system. dynamic code generation is the creation of executable code at runtime. such "on-the-fly" code generation is a powerful technique, enabling applications to use runtime information to improve performance by up to an order of magnitude [4, 8,20, 22, 23].unfortunately, previous general-purpose dynamic code generation systems have been either inefficient or non-portable. we present vcode, a retargetable, extensible, very fast dynamic code generation system. an important feature of vcode is that it generates machine code "in-place" without the use of intermediate data structures. eliminating the need to construct and consume an intermediate representation at runtime makes vcode both efficient and extensible. vcode dynamically generates code at an approximate cost of six to ten instructions per generated instruction, making it over an order of magnitude faster than the most efficient general-purpose code generation system in the literature [10].dynamic code generation is relatively well known within the compiler community. however, due in large part to the lack of a publicly available dynamic code generation system, it has remained a curiosity rather than a widely used technique. a practical contribution of this work is the free, unrestricted distribution of the vcode system, which currently runs on the mips, sparc, and alpha architectures.
stack caching for interpreters. an interpreter can spend a significant part of its execution time on accessing arguments of virtual machine instructions. this paper explores two methods to reduce this overhead for virtual stack machines by caching top-of-stack values in (real machine) registers. the dynamic method is based on having, for every possible state of the cache, one specialized version of the whole interpreter; the execution of an instruction usually changes the state of the cache and the next instruction is executed in the version corresponding to the new state. in the static method a state machine that keeps track of the cache state is added to the compiler. common instructions exist in specialized versions for several states, but it is not necessary to have a version of every instruction for every cache state. stack manipulation instructions are optimized away.
fast and flexible instruction selection with on-demand tree-parsing automata. tree parsing as supported by code generator generators like beg, burg, iburg, lburg and ml-burg is a popular instruction selection method. there are two existing approaches for implementing tree parsing: dynamic programming, and tree-parsing automata; each approach has its advantages and disadvantages. we propose a new implementation approach that combines the advantages of both existing approaches: we start out with dynamic programming at compile time, but at every step we generate a state for a tree-parsing automaton, which is used the next time a tree matching the state is found, turning the instruction selector into a fast tree-parsing automaton. we have implemented this approach in the gforth code generator. the implementation required little effort and reduced the startup time of gforth by up to a factor of 2.5.
optimizing indirect branch prediction accuracy in virtual machine interpreters. 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.
static detection of dynamic memory errors. many important classes of bugs result from invalid assumptions about the results of functions and the values of parameters and global variables. using traditional methods, these bugs cannot be detected efficiently at compile-time, since detailed cross-procedural analyses would be required to determine the relevant assumptions. in this work, we introduce annotations to make certain assumptions explicit at interface points. an efficient static checking tool that exploits these annotations can detect a broad class of errors including misuses of null pointers, uses of dead storage, memory leaks, and dangerous aliasing. this technique has been used successfully to fix memory management problems in a large program.
bytecode compression via profiled grammar rewriting. this paper describes the design and implementation of a method for producing compact, bytecoded instruction sets and interpreters for them. it accepts a grammar for programs written using a simple bytecoded stack-based instruction set, as well as a training set of sample programs. the system transforms the grammar, creating an expanded grammar that represents the same language as the original grammar, but permits a shorter derivation of the sample programs and others like them. a program's derivation under the expanded grammar forms the compressed bytecode representation of the program. the interpreter for this bytecode is automatically generated from the original bytecode interpreter and the expanded grammar. programs expressed using compressed bytecode can be substantially smaller than their original bytecode representation and even their machine code representation. for example, compression cuts the bytecode for lcc from 199kb to 58kb but increases the size of the interpreter by just over 11kb.
adoption and focus: practical linear types for imperative programming. a type system with linearity is useful for checking software protocols andresource management at compile time. linearity provides powerful reasoning about state changes, but at the price of restrictions on aliasing. the hard division between linear and nonlinear types forces the programmer to make a trade-off between checking a protocol on an object and aliasing the object. most onerous is the restriction that any type with a linear component must itself be linear. because of this, checking a protocol on an object imposes aliasing restrictions on any data structure that directly or indirectly points to the object. we propose a new type system that reduces these restrictions with the adoption and focus constructs. adoption safely allows a programmer to alias objects on which she is checking protocols, and focus allows the reverse. a programmer can alias data structures that point to linear objects and use focus for safe access to those objects. we discuss how we implemented these ideas in the vault programming language.
partial online cycle elimination in inclusion constraint graphs. many program analyses are naturally formulated and implemented using inclusion constraints. we present new results on the scalable implementation of such analyses based on two insights: first, that online elimination of cyclic constraints yields orders-of-magnitude improvements in analysis time for large problems; second, that the choice of constraint representation affects the quality and efficiency of online cycle elimination. we present an analytical model that explains our design choices and show that the model's predictions match well with results from a substantial experiment.
scalable context-sensitive flow analysis using instantiation constraints. this paper shows that a type graph (obtained via polymorphic type inference) harbors explicit directional flow paths between functions. these flow paths arise from the instantiations of polymorphic types and correspond to call-return sequences in first-order programs. we show that flow information can be computed efficiently while considering only paths with well matched call-return sequences, even in the higher-order case. furthermore, we present a practical algorithm for inferring type instantiation graphs and provide empirical evidence to the scalability of the presented techniques by applying them in the context of points-to analysis for c programs.
a vhdl compiler based on attribute grammar methodology. this paper presents aspects of a compiler for a new hardware description language (vhdl) written using attribute grammar techniques. vhdl is introduced, along with the new compiler challenges brought by a language that extends an ada subset for the purpose of describing hardware. attribute grammar programming solutions are presented for some of the language challenges. the organization of the compiler and of the target virtual machine represented by the simulation kernel are discussed, and performance and code-size figures are presented. the paper concludes that attribute grammars can be used for large commercial compilers with excellent results in terms of rapid development time and enhanced maintainability, and without paying any substantial penalty in terms of either the complexity of the language that can be handled or the resulting compilation speed.