waashk/dblp huggingface dataset:
a generalized algorithm for graph-coloring register allocation. graph-coloring register allocation is an elegant and extremely popular optimization for modern machines. but as currently formulated, it does not handle two characteristics commonly found in commercial architectures. first, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. second, multiple register names may be aliases for a single hardware register. we present a generalization of graph-coloring register allocation that handles these problematic characteristics while preserving the elegance and practicality of traditional graph coloring. our generalization adapts easily to a new target machine, requiring only the sets of names in the register classes and a map of the register aliases. it also drops easily into a well-known graph-coloring allocator, is efficient at compile time, and produces high-quality code.
a compiler approach to fast hardware design space exploration in fpga-based systems. the current practice of mapping computations to custom hardware implementations requires programmers to assume the role of hardware designers. in tuning the performance of their hardware implementation, designers manually apply loop transformations such as loop unrolling. designers manually apply loop transformations. for example, loop unrolling is used to expose instruction-level parallelism at the expense of more hardware resources for concurrent operator evaluation. because unrolling also increases the amount of data a computation requires, too much unrolling can lead to a memory bound implementation where resources are idle. to negotiate inherent hardware space-time trade-offs, designers must engage in an iterative refinement cycle, at each step manually applying transformations and evaluating their impact. this process is not only error-prone and tedious but also prohibitively expensive given the large search spaces and with long synthesis times. this paper describes an automated approach to hardware design space exploration, through a collaboration between parallelizing compiler technology and high-level synthesis tools. we present a compiler algorithm that automatically explores the large design spaces resulting from the application of several program transformations commonly used in application-specific hardware designs. our approach uses synthesis estimation techniques to quantitatively evaluate alternate designs for a loop nest computation. we have implemented this design space exploration algorithm in the context of a compilation and synthesis system called defacto, and present results of this implementation on five multimedia kernels. our algorithm derives an implementation that closely matches the performance of the fastest design in the design space, and among implementations with comparable performance, selects the smallest design. we search on average only 0.3% of the design space. this technology thus significantly raises the level of abstraction for hardware design and explores a design space much larger than is feasible for a human designer.
programming by sketching for bit-streaming programs. this paper introduces the concept of programming with sketches, an approach for the rapid development of high-performance applications. this approach allows a programmer to write clean and portable reference code, and then obtain a high-quality implementation by simply sketching the outlines of the desired implementation. subsequently, a compiler automatically fills in the missing details while also ensuring that a completed sketch is faithful to the input reference code. in this paper, we develop streambit as a sketching methodology for the important class of bit-streaming programs (e.g., coding and cryptography).a sketch is a partial specification of the implementation, and as such, it affords several benefits to programmer in terms of productivity and code robustness. first, a sketch is easier to write compared to a complete implementation. second, sketching allows the programmer to focus on exploiting algorithmic properties rather than on orchestrating low-level details. third, a sketch-aware compiler rejects "buggy" sketches, thus improving reliability while allowing the programmer to quickly evaluate sophisticated implementation ideas.we evaluated the productivity and performance benefits of our programming methodology in a user-study, where a group of novice streambit programmers competed with a group of experienced c programmers on implementing a cipher. we learned that, given the same time budget, the ciphers developed in streambit ran 2.5x faster than ciphers coded in c. we also produced implementations of des and serpent that were competitive with hand optimized implementations available in the public domain.
new tiling techniques to improve cache temporal locality. tiling is a well-known loop transformation to improve temporal locality of nested loops. current compiler algorithms for tiling are limited to loops which are perfectly nested or can be transformed, in trivial ways, into a perfect nest. this paper presents a number of program transformations to enable tiling for a class of nontrivial imperfectly-nested loops such that cache locality is improved. we define a program model for such loops and develop compiler algorithms for their tiling. we propose to adopt odd-even variable duplication to break anti- and output dependences without unduly increasing the working-set size, and to adopt speculative execution to enable tiling of loops which may terminate prematurely due to, e.g. convergence tests in iterative algorithms. we have implemented these techniques in a research compiler, panorama. initial experiments with several benchmark programs are performed on sgi workstations based on mips r5k and r10k processors. overall, the transformed programs run faster by 9% to 164%.
dynascope: a tool for program directing. this paper introduces program directing, a new way of program interaction. directing enables one program, the director, to monitor and to control another program, the executor. one important application of program directing is human interaction with complex computer simulations. the dynascope programming environment is designed specifically to support directing in traditional, compiled languages. it provides a framework and building blocks for easy construction of sophisticated directors. directors are regular programs that perform the directing of executors through dynascope primitives. dynascope is built around the concept of the execution stream which provides a complete description of the executor's computational behavior. the source code of executors requires no changes in order to be subjected to directing. this paper gives an overview of the dynascope system. sample applications are presented: debugging register allocation, animation of procedure calls, and a complex artificial life simulation. the performance of dynascope is illustrated by real time measurements.
realistic compilation by partial evaluation. two key steps in the compilation of strict functional languages are the conversion of higher-order functions to data structures (closures) and the transformation to tail-recursive style. we show how to perform both steps at once by applying first-order offline partial evaluation to a suitable interpreter. the resulting code is easy to transliterate to low-level c or native code. we have implemented the compilation to c; it yields a performance comparable to that of other modern scheme-to-c compilers. in addition, we have integrated various optimizations such as constant propagation, higher-order removal, and arity raising simply by modifying the underlying interpreter. purely first-order methods suffice to achieve the transformations. our approach is an instance of semantics-directed compiler generation.
two for the price of one: composing partial evaluation and compilation. one of the flagship applications of partial evaluation is compilation and compiler generation. however, partial evaluation is usually expressed as a source-to-source transformation for high-level languages, whereas realistic compilers produce object code.we close this gap by composing a partial evaluator with a compiler by automatic means. our work is a successful application of several meta-computation techniques to build the system, both in theory and in practice. the composition is an application of deforestation or fusion.the result is a run-time code generation system built from existing components. its applications are numerous. for example, it allows the language designer to perform interpreter-based experiments with a source-to-source version of the partial evaluator before building a realistic compiler which generates object code automatically.
eventrons: a safe programming construct for high-frequency hard real-time applications. while real-time garbage collection has achieved worst-case latencies on the order of a millisecond, this technology is approaching its practical limits. for tasks requiring extremely low latency, and especially periodic tasks with frequencies above 1 khz, java programmers must currently resort to the noheaprealtimethread construct of the real-time specification for java. this technique requires expensive run-time checks, can result in unpredictable low-level exceptions, and inhibits communication with the rest of the garbage-collected application. we present eventrons, a programming construct that can arbitrarily preempt the garbage collector, yet guarantees safety and allows its data to be visible to the garbage-collected heap. eventrons are a strict subset of java, and require no run-time memory access checks. safety is enforced using a data-sensitive analysis and simple run-time support with extremely low overhead. we have implemented eventrons in ibm's j9 java virtual machine, and present experimental results in which we ran eventrons at frequencies up to 22 khz (a 45 μs period). across 10 million periods, 99.997% of the executions ran within 10 μss of their deadline, compared to 99.999% of the executions of the equivalent program written in c.
a framework for interprocedural optimization in the presence of dynamic class loading. dynamic class loading during program execution in the java programming language is an impediment for generating code that is as efficient as code generated using static whole-program analysis and optimization. whole-program analysis and optimization is possible for languages, such as c++, that do not allow new classes and/or methods to be loaded during program execution. one solution for performing whole-program analysis and avoiding incorrect execution after a new class is loaded is to invalidate and recompile affected methods. runtime invalidation and recompilation mechanisms can be expensive in both space and time, and, therefore, generally restrict optimization. to address these drawbacks, we propose a new framework, called the extant analysis framework, for interprocedural optimization of programs that support dynamic class (or method)loading. given a set of classes comprising the closed world, we perform an offline static analysis which partitions references into two categories:(1) unconditionally extant references which point only to objects whose runtime type is guaranteed to be in the closed world; and (2) conditionally extant references which point to objects whose runtime type is not guaranteed to be in the closed world. optimizations solely dependent on the first categorycan be statically performed, and are guaranteed to be correct even with any future class/method loading. optimizations dependent on the second category are guarded by dynamic tests, called extant safety tests, for correct execution behavior.we describe the properties for extant safety tests, and provide algorithms for their generation and placement.
a new framework for exhaustive and incremental data flow analysis using dj graphs. we present a new elimination-based framework for exhaustive and incremental data flow analysis using the dj graph representation of a program. unlike the previous approaches to elimination-based incremental data flow analysis, our approach can handle arbitrary non-structural and structural changes to program flowgraphs, including those causing irreducibility. we show how our approach is related to (iterated) dominance frontiers, and exploit this relationship to establish the complexity of our exhaustive analysis and to aid the design of our incremental analysis.
refinement-based context-sensitive points-to analysis for java. we present a scalable and precise context-sensitive points-to analysis with three key properties: (1) filtering out of unrealizable paths, (2) a context-sensitive heap abstraction, and (3) a context-sensitive call graph. previous work [21] has shown that all three properties are important for precisely analyzing large programs, e.g., to show safety of downcasts. existing analyses typically give up one or more of the properties for scalability. we have developed a refinement-based analysis that succeeds by simultaneously refining handling of method calls and heap accesses, allowing the analysis to precisely analyze important code while entirely skipping irrelevant code. the analysis is demanddriven and client-driven, facilitating refinement specific to each queried variable and increasing scalability. in our experimental evaluation, our analysis proved the safety of 61% more casts than one of the most precise existing analyses across a suite of large benchmarks. the analysis checked the casts in under 13 minutes per benchmark (taking less than 1 second per query) and required only 35mb of memory, far less than previous approaches.
atom - a system for building customized program analysis tools. atom (analysis tools with om) is a single framework for building a wide range of customized program analysis tools. it provides the common infrastructure present in all code-instrumenting tools; this is the difficult and time-consuming part. the user simply defines the tool-specific details in instrumentation and analysis routines. building a basic block counting tool like pixie with atom requires only a page of code.atom, using om link-time technology, organizes the final executable such that the application program and user's analysis routines run in the same address space. information is directly passed from the application program to the analysis routines through simple procedure calls instead of inter-process communication or files on disk. atom takes care that analysis routines do not interfere with the program's execution, and precise information about the program is presented to the analysis routines at all times. atom uses no simulation or interpretation.atom has been implemented on the alpha axp under osf/1. it is efficient and has been used to build a diverse set of tools for basic block counting, profiling, dynamic memory recording, instruction and data cache simulation, pipeline simulation, evaluating branch prediction, and instruction scheduling.
link-time optimization of address calculation on a 64-bit architecture. compilers for new machines with 64-bit addresses must generate code that works when the memory used by the program is large. procedures and global variables are accessed indirectly via global address tables, and calling conventions include code to establish the addressability of the appropriate tables. in the common case of a program that does not require a lot of memory, all of this can be simplified considerably, with a corresponding reduction in program size and execution time.we have used our link-time code modification system om to perform program transformations related to global address use on the alpha axp. though simple, many of these arewhole-program optimizations that can be done only when we can see the entire program at once, so link-time is an ideal occasion to perform them.this paper describes the optimizations performed and shows their effects on program size and performance. relatively modest transformations, possible without moving code, improve the performance of spec benchmarks by an average of 1.5%. more ambitious transformations, requiring an understanding of program structure that is thorough but not difficult at link-time, can do even better, reducing program size by 10% or more, and improving performance by an average of 3.8%.even a program compiled monolithically with interprocedural optimization can benefit nearly as much from this technique, if it contains statically-linked pre-compiled library code. when the benchmark sources were compiled in this way, we were still able to improve their performance by 1.35% with the modest transformations and 3.4% with the ambitious transformations.
how to print floating-point numbers accurately. we present algorithms for accurately converting floating-point numbers to decimal representation. the key idea is to carry along with the computation an explicit representation of the required rounding accuracy. we begin with the simpler problem of converting fixed-point fractions. a modification of the well-known algorithm for radix-conversion of fixed-point fractions by multiplication explicitly determines when to terminate the conversion process; a variable number of digits are produced. the algorithm has these properties: no information is lost; the original fraction can be recovered from the output by rounding. no &ldquo;garbage digits&rdquo; are produced. the output is correctly rounded. it is never necessary to propagate carries on rounding. we then derive two algorithms for free-formal output of floating-point numbers. the first simply scales the given floating-point number to an appropriate fractional range and then applies the algorithm for fractions. this is quite fast and simple to code but has inaccuracies stemming from round-off errors and oversimplification. the second algorithm guarantees mathematical accuracy by using multiple-precision integer arithmetic and handling special cases. both algorithms produce no more digits than necessary (intuitively, the &ldquo;1.3 prints as 1.2999999&rdquo; problem does not occur). finally, we modify the free-format conversion algorithm for use in fixed-format applications. information may be lost if the fixed format provides too few digit positions, but the output is always correctly rounded. on the other hand, no &ldquo;garbage digits&rdquo; are ever produced, even if the fixed format specifies too many digit positions (intuitively, the &ldquo;4/3 prints as 1.333333328366279602&rdquo; problem does not occur).
meta optimization: improving compiler heuristics with machine learning. compiler writers have crafted many heuristics over the years to approximately solve np-hard problems efficiently. finding a heuristic that performs well on a broad range of applications is a tedious and difficult process. this paper introduces meta optimization, a methodology for automatically fine-tuning compiler heuristics. meta optimization uses machine-learning techniques to automatically search the space of compiler heuristics. our techniques reduce compiler design complexity by relieving compiler writers of the tedium of heuristic tuning. our machine-learning system uses an evolutionary algorithm to automatically find effective compiler heuristics. we present promising experimental results. in one mode of operation meta optimization creates application-specific heuristics which often result in impressive speedups. for hyperblock formation, one optimization we present in this paper, we obtain an average speedup of 23% (up to 73%) for the applications in our suite. furthermore, by evolving a compiler's heuristic over several benchmarks, we can create effective, general-purpose heuristics. the best general-purpose heuristic our system found for hyperblock formation improved performance by an average of 25% on our training set, and 9% on a completely unrelated test set. we demonstrate the efficacy of our techniques on three different optimizations in this paper: hyperblock formation, register allocation, and data prefetching.
bitwidth analysis with application to silicon compilation. this paper introduces bitwise, a compiler that minimizes the bitwidth the number of bits used to represent each operand for both integers and pointers in a program. by propagating 70 static information both forward and backward in the program dataflow graph, bitwise frees the programmer from declaring bitwidth invariants in cases where the compiler can determine bitwidths automatically. because loop instructions comprise the bulk of dynamically executed instructions, bitwise incorporates sophisticated loop analysis techniques for identifying bitwidths. we find a rich opportunity for bitwidth reduction in modern multimedia and streaming application workloads. for new architectures that support sub-word data-types, we expect that our bitwidth reductions will save power and increase processor performance. this paper also applies our analysis to silicon compilation, the translation of programs into custom hardware, to realize the full benefits of bitwidth reduction. we describe our integration of bitwise with the deepc silicon compiler. by taking advantage of bitwidth information during architectural synthesis, we reduce silicon real estate by 15 - 86%, improve clock speed by 3 - 249%, and reduce power by 46 - 73%. the next era of general purpose and reconfigurable architectures should strive to capture a portion of these gains.
support for garbage collection at every instruction in a java compiler. a high-performance implementation of a java virtual machine1 requires a compiler to translate java bytecodes into native instructions, as well as an advanced garbage collector (e.g., copying or generational). when the java heap is exhausted and the garbage collector executes, the compiler must report to the garbage collector all live object references contained in physical registers and stack locations. typical compilers only allow certain instructions (e.g., call instructions and backward branches) to be gc-safe; if gc happens at some other instruction, the compiler may need to advance execution to the next gc-safe point. until now, no one has ever attempted to make every compiler-generated instruction gc-safe, due to the perception that recording this information would require too much space. this kind of support could improve the gc performance in multithreaded applications. we show how to use simple compression techniques to reduce the size of the gc map to about 20% of the generated code size, a result that is competitive with the best previously published results. in addition, we extend the work of agesen, detlefs, and moss, regarding the so-called "jsr problem" (the single exception to java's type safety property), in a way that eliminates the need for extra runtime overhead in the generated code.