waashk/dblp huggingface dataset:
partial dead code elimination. a new aggressive algorithm for the elimination of partially dead code is presented, i.e., of code which is only dead on some program paths. besides being more powerful than the usual approaches to dead code elimination, this algorithm is optimal in the following sense: partially dead code remaining in the resulting program cannot be eliminated without changing the branching structure or the semantics of the program, or without impairing some program executions. our approach is based on techniques for partial redundancy elimination. besides some new technical problems there is a significant difference here: partial dead code elimination introduces second order effects, which we overcome by means of exhaustive motion and elimination steps. the optimality and the uniqueness of the program obtained is proved by means of a new technique which is universally applicable and particularly useful in the case of mutually interdependent program optimizations.
the power of assignment motion. assignment motion (am) and expression motion (em) are the basis of powerful and at the first sight incomparable techniques for removing partially redundant code from a program. whereas am aims at the elimination of complete assignments, a transformation which is always desirable, the more flexible em requires temporaries to remove partial redundancies. based on the observation that a simple program transformation enhances am to subsume em, we develop an algorithm that for the first time captures all second order effects between am and em transformations. under usual structural restrictions, the worst case time complexity of our algorithm is essentially quadratic, a fact which explains the promising experience with our implementation.
data-centric multi-level blocking. we present a simple and novel framework for generating blocked codes for high-performance machines with a memory hierarchy. unlike traditional compiler techniques like tiling, which are based on reasoning about the control flow of programs, our techniques are based on reasoning directly about the flow of data through the memory hierarchy. our data-centric transformations permit a more direct solution to the problem of enhancing data locality than current control-centric techniques do, and generalize easily to multiple levels of memory hierarchy. we buttress these claims with performance numbers for standard benchmarks from the problem domain of dense numerical linear algebra. the simplicity and intuitive appeal of our approach should make it attractive to compiler writers as well as to library writers.
the set constraint/cfl reachability connection in practice. many program analyses can be reduced to graph reachability problems involving a limited form of context-free language reachability called dyck-cfl reachability. we show a new reduction from dyck-cfl reachability to set constraints that can be used in practice to solve these problems. our reduction is much simpler than the general reduction from context-free language reachability to set constraints. we have implemented our reduction on top of a set constraints toolkit and tested its performance on a substantial polymorphic flow analysis application.
a global progressive register allocator. this paper describes a global progressive register allocator, a register allocator that uses an expressive model of the register allocation problem to quickly find a good allocation and then progressively find better allocations until a provably optimal solution is found or a preset time limit is reached. the key contributions of this paper are an expressive model of global register allocation based on multicommodity network flows that explicitly represents spill code optimization, register preferences, copy insertion, and constant rematerialization; two fast, but effective, heuristic allocators based on this model; and a more elaborate progressive allocator that uses lagrangian relaxation to compute the optimality of its allocations. our progressive allocator demonstrates code size improvements as large as 16.75% compared to a traditional graph allocator. on average, we observe an initial improvement of 3.47%, which increases progressively to 6.84% as more time is permitted for compilation.
load/store range analysis for global register allocation. live range splitting techniques improve global register allocation by splitting the live ranges of variables into segments that are individually allocated registers. load/store range analysis is a new technique for live range splitting that is based on reaching definition and live variable analyses. our analysis localizes the profits and the register requirements of every access to every variable to provide a fine granularity of candidates for register allocation. experiments on a suite of c and fortran benchmark programs show that a graph coloring register allocator operating on load/store ranges often provides better allocations than the same allocator operating on live ranges. experimental results also show that the computational cost of using load/store ranges for register allocation is moderately more than the cost of using live ranges.
elimination of redundant array subscript range checks. this paper presents a compiler optimization algorithm to reduce the run time overhead of array subscript range checks in programs without compromising safety. the algorithm is based on partial redundancy elimination and it incorporates previously developed algorithms for range check optimization. we implemented the algorithm in our research compiler, nascent, and conducted experiments on a suite of 10 benchmark programs to obtain four results: (1) the execution overhead of naive range checking is high enough to merit optimization, (2) there are substantial differences between various optimizations, (3) loop-based optimizations that hoist checks out of loops are effective in eliminating about 98% of the range checks, and (4) more sophisticated analysis and optimization algorithms produce very marginal benefits.
a fresh look at combinator graph reduction. we present a new abstract machine for graph reduction called tigre. benchmark results show that tigre's execution speed compares quite favorably with previous combinator-graph reduction techniques on similar hardware. furthermore, the mapping of tigre onto conventional hardware is simple and efficient. mainframe implementations of tigre provide performance levels exceeding those previously available on custom graph reduction hardware.
preference-directed graph coloring. this paper describes a new framework of register allocation based on chaitin-style coloring. our focus is on maximizing the chances for live ranges to be allocated to the most preferred registers while not destroying the colorability obtained by graph simplification. our coloring algorithm uses a graph representation of preferences called a register preference graph, which helps find a good register selection. we then try to relax the register selection order created by the graph simplification. the relaxed order is defined as a partial order, represented using a graph called a coloring precedence graph. our algorithm utilizes such a partial order for the register selection instead of using the traditional simplification-driven order so that the chances of honoring the preferences are effectively increased. experimental results show that our coloring algorithm is powerful to simultaneously handle spill decisions, register coalescing, and preference resolutions.
tools: a unifying approach to object-oriented language interpretation. the object-oriented paradigm is applied to the interpreting of programming languages. an intermediate representation of a program is created as a collection of objects representing various entities in the conceptual world of the source language. these objects cover both the static and the dynamic aspects of a program. as a major advantage of this approach, issues that are traditionally handled by very different techniques (like symbol table management and the generation and execution of intermediate code) can be treated in a unified manner. the specification language of an interpreter generator based on these principles is described.
implementation of a high-speed prolog interpreter. this paper describes the implementation of a high speed prolog interpreter on a standard microprocessor (50 klips on a 16 mhz mc68020). the interpreter is based on direct threaded code. by this method an interpreted program achieves the same speed as a compiled program, but uses only a tenth of memory. the first part of this paper describes the implementation of the interpreter. the second part compares the implementation, the runtime and the storage requirements with that of a compiler.
improving semi-static branch prediction by code replication. speculative execution on superscalar processors demands substantially better branch prediction than what has been previously available. in this paper we present code replication techniques that improve the accuracy of semi-static branch prediction to a level comparable to dynamic branch prediction schemes. our technique uses profiling to collect information about the correlation between different branches and about the correlation between the subsequent outcomes of a single branch. using this information and code replication the outcome of branches is represented in the program state. our experiments have shown that the misprediction rate can almost be halved while the code size is increased by one third.
mul-t: a high-performance parallel lisp. mul-t is a parallel lisp system, based on multilisp's future construct, that has been developed to run on an encore multimax multiprocessor. mul-t is an extended version of the yale t system and uses the t system's orbit compiler to achieve &ldquo;production quality&rdquo; performance on stock hardware &mdash; about 100 times faster than multilisp. mul-t shows that futures can be implemented cheaply enough to be useful in a production-quality system. mul-t is fully operational, including a user interface that supports managing groups of parallel tasks.
using annotation to reduce dynamic optimization time. dynamic compilation and optimization are widely used in heterogenous computing environments, in which an intermediate form of the code is compiled to native code during execution. an important trade off exists between the amount of time spent dynamically optimizing the program and the running time of the program. the time to perform dynamic optimizations can cause significant delays during execution and also prohibit performance gains that result from more complex optimization. in this research, we present an annotation framework that substantially reduces compilation overhead of java programs. annotations consist of analysis information collected off-line and are incorporated into java programs. the annotations are then used by dynamic compilers to guide optimization. the annotations we present reduce compilation overhead incurred at all stages of compilation and optimization as well as enable complex optimizations to be performed dynamically. on average, our annotation optimizations reduce optimized compilation overhead by 78% and enable speedups of 7% on average for the programs examined.
optimizing parallel programs with explicit synchronization. we present compiler analyses and optimizations for explicitly parallel programs that communicate through a shared address space. any type of code motion on explicitly parallel programs requires a new kind of analysis to ensure that operations reordered on one processor cannot be observed by another. the analysis, based on work by shasha and snir, checks for cycles among interfering accesses. we improve the accuracy of their analysis by using additional information from post-wait synchronization, barriers, and locks.we demonstrate the use of this analysis by optimizing remote access on distributed memory machines. the optimizations include message pipelining, to allow multiple outstanding remote memory operations, conversion of two-way to one-way communication, and elimination of communication through data re-use. the performance improvements are as high as 20-35% for programs running on a cm-5 multiprocessor using the split-c language as a global address layer.
permission-based ownership: encapsulating state in higher-order typed languages. today's module systems do not effectively support information hiding in the presence of shared mutable objects, causing serious problems in the development and evolution of large software systems. ownership types have been proposed as a solution to this problem, but current systems have ad-hoc access restrictions and are limited to java-like languages.in this paper, we describe system fown, an extension of system f with references and ownership. our design shows both how ownership fits into standard type theory and the encapsulation benefits it can provide in languages with first-class functions, abstract data types, and parametric polymorphism. by looking at ownership in the setting of systemf, we were able to develop a design that is more principled and flexible than previous ownership type systems, while also providing stronger encapsulation guarantees.
fast searches for effective optimization phase sequences. it has long been known that a fixed ordering of optimization phases will not produce the best code for every application. one approach for addressing this phase ordering problem is to use an evolutionary algorithm to search for a specific sequence of phases for each module or function. while such searches have been shown to produce more efficient code, the approach can be extremely slow because the application is compiled and executed to evaluate each sequence's effectiveness. consequently, evolutionary or iterative compilation schemes have been promoted for compilation systems targeting embedded applications where longer compilation times may be tolerated in the final stage of development. in this paper we describe two complementary general approaches for achieving faster searches for effective optimization sequences when using a genetic algorithm. the first approach reduces the search time by avoiding unnecessary executions of the application when possible. results indicate search time reductions of 65% on average, often reducing searches from hours to minutes. the second approach modifies the search so fewer generations are required to achieve the same results. measurements show that the average number of required generations decreased by 68%. these improvements have the potential for making evolutionary compilation a viable choice for tuning embedded applications.
esp: a language for programmable devices. this paper presents the design and implementation of event-driven state-machines programming (esp)&mdash;a language for programmable devices. in traditional languages, like c, using event-driven state-machine forces a tradeoff that requires giving up ease of development and reliability to achieve high performance. esp is designed to provide all of these three properties simultaneously. esp provides a comprehensive set of features to support development of compact and modular programs. the esp compiler compiles the programs into two targets&mdash;a c file that can be used to generate efficient firmware for the device; and a specification that can be used by a verifier like spln to extensively test the firmware. as a case study, we reimplemented vmmc firmware that runs on myrinet network interface cards using esp. we found that esp simplifies the task of programming with event-driven state machines. it required an order of magnitude fewer lines of code than the previous implementation. we also found that model-checking verifiers like spin can be used to effectively debug the firmware. finally, our measurements indicate that the performance overhead of using esp is relatively small.
zero-cost range splitting. this paper presents a new optimization technique that uses empty delay slots to improve code scheduling. we are able to split live ranges for free, by inserting spill code into empty delay slots. splitting a live range can reduce interferences with other live ranges and can sometimes free registers. live ranges no longer interfering with the split live range can sometimes make use of the extra register. our algorithm, as a final pass over the code, exploits empty delay slots that would remain unused if spill code was not inserted. this paper proposes a variety of optimizations that use the extra registers generated from live range splitting, including coalescing live ranges and improving code scheduling. we present an algorithm for improving code scheduling and present implementation results.
linear analysis and optimization of stream programs. as more complex dsp algorithms are realized in practice, there is an increasing need for high-level stream abstractions that can be compiled without sacrificing efficiency. toward this end, we present a set of aggressive optimizations that target linear sections of a stream program. our input language is streamit, which represents programs as a hierarchical graph of autonomous filters. a filter is linear if each of its outputs can be represented as an affine combination of its inputs. linearity is common in dsp components; examples include fir filters, expanders, compressors, ffts and dcts.we demonstrate that several algorithmic transformations, traditionally hand-tuned by dsp experts, can be completely automated by the compiler. first, we present a linear extraction analysis that automatically detects linear filters from the c-like code in their work function. then, we give a procedure for combining adjacent linear filters into a single filter, as well as for translating a linear filter to operate in the frequency domain. we also present an optimization selection algorithm, which finds the sequence of combination and frequency transformations that will give the maximal benefit.we have completed a fully-automatic implementation of the above techniques as part of the streamit compiler, and we demonstrate a 450% performance improvement over our benchmark suite.
a safe approximate algorithm for interprocedural pointer aliasing. during execution, when two or more names exist for the same location at some program point, we call them aliases. in a language which allows arbitrary pointers, the problem of determining aliases at a program point is p-space-hard [lan92]. we present an algorithm for the conditional may alias problem, which can be used to safely approximate interprocedural may alias in the presence of pointers. this algorithm is as precise as possible in the worst case and has been implemented in a prototype analysis tool for c programs. preliminary speed and precision results are presented.
incremental incrementally compacting garbage collection. a mixed-strategy garbage collection algorithm is presented, which combines mark-and-sweep and copy collection. the intent is to benefit from the compacting and linearizing properties of copy collection without losing computational use of half the memory. the stop-and-collect version of the algorithm is a simple and cheap technique to fight memory fragmentation. the collection strategy may be dynamically adapted to minimize the cost of collection, according to the amount of memory actually accessed by the computing process. the parallel version of the algorithm is to our knowledge the only parallel compacting collector for varisized cells, that leaves most (more than half) of the memory available for the computing process.
exploiting superword level parallelism with multimedia instruction sets. increasing focus on multimedia applications has prompted the addition of multimedia extensions to most existing general purpose microprocessors. this added functionality comes primarily with the addition of short simd instructions. unfortunately, access to these instructions is limited to in-line assembly and library calls. generally, it has been assumed that vector compilers provide the most promising means of exploiting multimedia instructions. although vectorization technology is well understood, it is inherently complex and fragile. in addition, it is incapable of locating simd-style parallelism within a basic block. in this paper we introduce the concept of superword level parallelism (slp) ,a novel way of viewing parallelism in multimedia and scientific applications. we believe slpp is fundamentally different from the loop level parallelism exploited by traditional vector processing, and therefore demands a new method of extracting it. we have developed a simple and robust compiler for detecting slpp that targets basic blocks rather than loop nests. as with techniques designed to extract ilp, ours is able to exploit parallelism both across loop iterations and within basic blocks. the result is an algorithm that provides excellent performance in several application domains. in our experiments, dynamic instruction counts were reduced by 46%. speedups ranged from 1.24 to 6.70.
whole program paths. whole program paths (wpp) are a new approach to capturing and representing a program's dynamic---actually executed---control flow. unlike other path profiling techniques, which record intraprocedural or acyclic paths, wpps produce a single, compact description of a program's entire control flow, including loop iteration and interprocedural paths.this paper explains how to collect and represent wpps. it also shows how to use wpps to find hot subpaths, which are the heavily executed sequences of code that should be the focus of performance tuning and compiler optimization.
detecting conflicts between structure accesses. two references to a record structure conflict if they access the same field and at least one modifies the location. because structures can be connected by pointers, deciding if two statements conflict requires knowledge of the possible aliases for the locations that they access. this paper describes a dataflow computation that produces a conservative description of the aliases visible at any point in a program. the data structure that records aliases is an alias graph. it also labels instances of structures so that the objects referenced at different points in a program can be compared. this paper shows how alias graphs can be used to detect potential conflicts.
eel: machine-independent executable editing. eel (executable editing library) is a library for building tools to analyze and modify an executable (compiled) program. the systems and languages communities have built many tools for error detection, fault isolation, architecture translation, performance measurement, simulation, and optimization using this approach of modifying executables. currently, however, tools of this sort are difficult and time-consuming to write and are usually closely tied to a particular machine and operating system. eel supports a machine- and system-independent editing model that enables tool builders to modify an executable without being aware of the details of the underlying architecture or operating system or being concerned with the consequences of deleting instructions or adding foreign code.