waashk/dblp huggingface dataset:
beltway: getting around garbage collection gridlock. we present the design and implementation of a new garbage collection framework that significantly generalizes existing copying collectors. the beltway framework exploits and separates object age and incrementality. it groups objects in one or more increments on queues called belts, collects belts independently, and collects increments on a belt in first-in-first-out order. we show that beltway configurations, selected by command line options, act and perform the same as semi-space, generational, and older-first collectors, and encompass all previous copying collectors of which we are aware. the increasing reliance on garbage collected languages such as java requires that the collector perform well. we show that the generality of beltway enables us to design and implement new collectors that are robust to variations in heap size and improve total execution time over the best generational copying collectors of which we are aware by up to 40%, and on average by 5 to 10%, for small to moderate heap sizes. new garbage collection algorithms are rare, and yet we define not just one, but a new family of collectors that subsumes previous work. this generality enables us to explore a larger design space and build better collectors.
automatic recognition of induction variables and recurrence relations by abstract interpretation. the recognition of recurrence relations is important in several ways to the compilation of programs. induction variables, the simplest form of recurrence, are pivotal in loop optimizations and dependence testing. many recurrence relations, although expressed sequentially by the programmer, lend themselves to efficient vector or parallel computation. despite the importance of recurrences, vectorizing and parallelizing compilers to date have recognized them only in an ad-hoc fashion. in this paper we put forth a systematic method for recognizing recurrence relations automatically. our method has two parts. first, abstract interpretation [cc77, cc79] is used to construct a map that associates each variable assigned in a loop with a symbolic form (expression) of its value. second, the elements of this map are matched with patterns that describe recurrence relations. the scheme is easily extensible by the addition of templates, and is able to recognize nested recurrences by the propagation of the closed forms of recurrences from inner loops. we present some applications of this method and a proof of its correctness.
exploiting hardware performance counters with flow and context sensitive profiling. a program profile attributes run-time costs to portions of a program's execution. most profiling systems suffer from two major deficiencies: first, they only apportion simple metrics, such as execution frequency or elapsed time to static, syntactic units, such as procedures or statements; second, they aggressively reduce the volume of information collected and reported, although aggregation can hide striking differences in program behavior.this paper addresses both concerns by exploiting the hardware counters available in most modern processors and by incorporating two concepts from data flow analysis--flow and context sensitivity--to report more context for measurements. this paper extends our previous work on efficient path profiling to flow sensitive profiling, which associates hardware performance metrics with a path through a procedure. in addition, it describes a data structure, the calling context tree, that efficiently captures calling contexts for procedure-level measurements.our measurements show that the spec95 benchmarks execute a small number (3--28) of hot paths that account for 9--98% of their l1 data cache misses. moreover, these hot paths are concentrated in a few routines, which have complex dynamic behavior.
automatic instruction scheduler retargeting by reverse-engineering. in order to generate high-quality code for modern processors, a compiler must aggressively schedule instructions, maximizing resource utilization for execution efficiency. for a compiler to produce such code, it must avoid structural hazards by being aware of the processor's available resources and of how these resources are utilized by each instruction. unfortunately, the most prevalent approach to constructing such a scheduler, manually discovering and specifying this information, is both tedious and error-prone. this paper presents a new approach which, when given a processor or processor model, automatically determines this information. after establishing that the problem of perfectly determining a processor's structural hazards through probing is not solvable, this paper proposes a heuristic algorithm that discovers most of this information in practice. this can be used either to alleviate the problems associated with manual creation or to verify an existing specification. scheduling with these automatically derived structural hazards yields almost all of the performance gain achieved using perfect hazard information.
improving data-flow analysis with path profiles. data-flow analysis computes its solutions over the paths in a control-flow graph. these paths---whether feasible or infeasible, heavily or rarely executed---contribute equally to a solution. however, programs execute only a small fraction of their potential paths and, moreover, programs' execution time and cost is concentrated in a far smaller subset of hot paths.this paper describes a new approach to analyzing and optimizing programs, which improves the precision of data flow analysis along hot paths. our technique identifies and duplicates hot paths, creating a hot path graph in which these paths are isolated. after flow analysis, the graph is reduced to eliminate unnecessary duplicates of unprofitable paths. in experiments on spec95 benchmarks, path qualification identified 2--112 times more non-local constants (weighted dynamically) than the wegman-zadek conditional constant algorithm, which translated into 1--7% more dynamic instructions with constant results.
effective partial redundancy elimination. partial redundancy elimination is a code optimization with a long history of literature and implementation. in practice, its effectiveness depends on issues of naming and code shape. this paper shows that a combination of global reassociation and global value numbering can increase the effectiveness of partial redundancy elimination. by imposing a discipline on the choice of names and the shape of expressions, we are able to expose more redundancies. as part of the work, we introduce a new algorithm for global reassociation of expressions. it uses global information to reorder expressions, creating opportunities for other optimizations. the new algorithm generalizes earlier work that ordered fortran array address expressions to improve otpimization [25].
coloring heuristics for register allocation. we describe an improvement to a heuristic introduced by chaitin for use in graph coloring register allocation. our modified heuristic produces better colorings, with less spill code. it has similar compile-time and implementation requirements. we present experimental data to compare the two methods.
debugging temporal specifications with concept analysis. program verification tools (such as model checkers and static analyzers) can find many errors in programs. these tools need formal specifications of correct program behavior, but writing a correct specification is difficult, just as writing a correct program is difficult. thus, just as we need methods for debugging programs, we need methods for debugging specifications.this paper describes a novel method for debugging formal, temporal specifications. our method exploits the short program execution traces that program verification tools generate from specification violations and that specification miners extract from programs. manually examining these traces is a straightforward way to debug a specification, but this method is tedious and error-prone because there may be hundreds or thousands of traces to inspect. our method uses concept analysis to automatically group the traces into highly similar clusters. by examining clusters instead of individual traces, a person can debug a specification with less work.to test our method, we implemented a tool, cable, for debugging specifications. we have used cable to debug specifications produced by strauss, our specification miner. we found that using cable to debug these specifications requires, on average, less than one third as many user decisions as debugging by examining all traces requires. in one case, using cable required only 28 decisions, while debugging by examining all traces required 224.
compilation of haskell array comprehensions for scientific computing. monolithic approaches to functional language arrays, such as haskell array comprehensions, define elements all at once, at the time the array is created, instead of incrementally. although monolithic arrays are elegant, a naive implementation can be very inefficient. for example, if a compiler does not know whether an element has zero or many definitions, it must compile runtime tests. if a compiler does not know inter-element data dependencies, it must resort to pessimistic strategies such as compiling elements as thunks, or making unnecessary copies when updating an array. subscript analysis, originally developed for imperative language vectorizing and parallelizing compilers, can be adapted to provide a functional language compiler with the information needed for efficient compilation of monolithic arrays. our contribution is to develop the number-theoretic basis of subscript analysis with assumptions appropriate to functional arrays, detail the kinds of dependence information subscript analysis can uncover, and apply that dependence information to sequential efficient compilation of functional arrays.
rematerialization. this paper examines a problem that arises during global register allocation &ndash; rematerialization. if a value cannot be kept in a register, the allocator should recognize when it is cheaper to recompute the value (rematerialize it) than to store and reload it. chaitin's original graph-coloring allocator handled simple instance of this problem correctly. this paper details a general solution to the problem and presents experimental evidence that shows its importance. our approach is to tag individual values in the procedure's ssa graph with information specifying how it should be spilled. we use a variant of wegman and zadeck's sparse simple constant algorithm to propagate tags throughout the graph. the allocator then splits live ranges into values with different tags. this isolates those values that can be easily rematerialized from values that require general spilling. we modify the base allocator to use this information when estimating spill costs and introducing spill code. our presentation focuses on rematerialization in the context of chaitin's allocator; however, the problem arises in any global allocator. we believe that our approach will work in other allocators&ndash;while the details of implementation will vary, the key insights should carry over directly.
design and implementation of the uw illustrated compiler. we have implemented an illustrated compiler for a simple block structured language. the compiler graphically displays its control and data structures, and so gives its viewers an intuitive understanding of compiler organization and operation. the illustrations were planned by hand and display information naturally and concisely.
a new approach to debugging optimized code. debugging optimized code is a desirable capability not provided by most current debuggers. users are forced to debug the unoptimized code when a bug occurs in the optimized version. current research offers partial solutions for a small class of optimizations, but not a unified approach that handles a wide range of optimizations, such as the sophisticated optimizations performed by supercomputer compilers. the trend with current research is to make the effects of optimization transparent, i.e., provide the same behavior as that of the unoptimized program. we contend that this approach is neither totally feasible nor entirely desirable. instead, we propose a new approach based on the premise that one should be able to debug the optimized code. this implies mapping the current state of execution back to the original source, tracking the location of variables, and mapping compiler-synthesized variables back to user-defined induction variables. to aid the user in understanding program behavior, various visual means are provided, e.g., different forms of highlighting and annotating of the source/assembly code. while this unavoidably requires the user to have a basic understanding of the optimizations performed, it permits the user to see what is actually happening, infer the optimizations performed, and detect bugs. an example illustrates the effectiveness of visual feedback. to support conventional debugger functionality for optimized code, the compiler must generate additional information. current compiler-debugger interfaces (cdis) were neither designed to handle this new information nor are they extensible in a straight forward manner. therefore, a new cdi was designed that supports providing visual feedback and the debugging of optimized code. this paper specifies the details of a new cdi and relates each feature back to the debugger functionality it supports.
social processes and proofs of theorems and programs, revisited. language-based security is a protection mechanism that allows software components to interact in a shared address space, such that each component is guaranteed to respect its interfaces and not steal or corrupt internal data of other components. this protection mechanism is complicated to implement correctly, so we might want a formal verification of it.but we know by a famous result of demillo, lipton, and perlis (popl 1978) that formal verification (1) is not what mathematicians do, (2) can never be practical, and (3) cannot tell us anything truly useful. is this still true 25 years later?the question is, then, how can we carefully skirt the legitimate objections of demillo et al. and successfully use formal verification in a context where it can do some good. i'll talk about foundational proof-carrying code, a machine-checked soundness proof for a protection mechanism usable in java-like virtual machines.
representing control in the presence of one-shot continuations. traditional first-class continuation mechanisms allow a captured continuation to be invoked multiple times. many continuations, however, are invoked only once. this paper introduces one-shot continuations, shows how they interact with traditional multi-shot continuations, and describes a stack-based implementation of control that handles both one-shot and multi-shot continuations. the implementation eliminates the copying overhead for one-shot continuations that is inherent in multi-shot continuations.
fast copy coalescing and live-range identification. this paper presents a fast new algorithm for modeling and reasoning about interferences for variables in a program without constructing an interference graph. it then describes how to use this information to minimize copy insertion for &fgr;-node instantiation during the conversion of the static single assignment (ssa) form into the control-flow graph (cfg), effectively yielding a new, very fast copy coalescing and live-range identification algorithm.this paper proves some properties of the ssa form that enable construction of data structures to compute interference information for variables that are considered for folding. the asymptotic complexity of our ssa-to-cfg conversion algorithm is where-is the number of instructions in the program.performing copy folding during the ssa-to-cfg conversion eliminates the need for a separate coalescing phase while simplifying the intermediate code. this may make graph-coloring register allocation more practical in just in time (jit) and other time-critical compilers for example, sun's hotspot server compiler already employs a graph-coloring register allocator[10].this paper also presents an improvement to the classical interference-graph based coalescing optimization that shows adecrease in memory usage of up to three orders of magnitude and a decrease of a factor of two in compilation time, while providing the exact same results.we present experimental results that demonstrate that our algorithm is almost as precise (within one percent on average) as the improved interference-graph-based coalescing algorithm, while requiring three times less compilation time.
real-time concurrent collection on stock multiprocessors. we've designed and implemented a copying garbage-collection algorithm that is efficient, real-time, concurrent, runs on commercial uniprocessors and shared-memory multiprocessors, and requires no change to compilers. the algorithm uses standard virtual-memory hardware to detect references to &ldquo;from space&rdquo; objects and to synchronize the collector and mutator threads. we've implemented and measured a prototype running on src's 5-processor firefly. it will be straightforward to merge our techniques with generational collection. an incremental, non-concurrent version could be implemented easily on many versions of unix.
printing floating-point numbers quickly and accurately. this paper presents a fast and accurate algorithm for printing floating-point numbers in both free- and fixed-format modes. in free-format mode, the algorithm generates the shortest, correctly rounded output string that converts to the same number when read back in, accommodating whatever rounding mode the reader uses. in fixed-format mode, the algorithm generates a correctly rounded output string using special # marks to denote insignificant trailing digits. for both modes, the algorithm employs a fast estimator to scale floating-point numbers efficiently.
optimal spilling for cisc machines with few registers. many graph-coloring register-allocation algorithms don't work well for machines with few registers. heuristics for live-range splitting are complex or suboptimal; heuristics for register assignment rarely factor the presence of fancy addressing modes; these problems are more severe the fewer registers there are to work with. we show how to optimally split live ranges and optimally use addressing modes, where the optimality condition measures dynamically weighted loads and stores but not register-register moves. our algorithm uses integer linear programming but is much more efficient than previous ilp-based approaches to register allocation. we then show a variant of park and moon's optimistic coalescing algorithm that does a very good (though not provably optimal) job of removing the register-register moves. the result is pentium code that is 9.5% faster than code generated by ssa-based splitting with iterated register coalescing.
register allocation using lazy saves, eager restores, and greedy shuffling. this paper presents a fast and effective linear intraprocedural register allocation strategy that optimizes register usage across procedure calls. it capitalizes on our observation that while procedures that do not contain calls (syntactic leaf routines) account for under one third of all procedure activations, procedures that actually make no calls (effective leaf routines) account for over two thirds of all procedure activations. well-suited for both caller-and calle-save registers, our strategy employs a &ldquo;lazy&rdquo; save mechanism that avoids saves for all effective leaf routines, an &ldquo;eager&rdquo; restore mechanism that reduces the effect of memory latency, and a &ldquo;greedy&rdquo; register shuffling algorithm that does a remarkbly good job of minimizing the need for temporaries in setting up procedure calls.
separate compilation for standard ml. languages that support abstraction and modular structure, such as standard ml, modula, ada, and (more or less) c++, may have deeply nested dependency hierarchies among source files. in ml the problem is particularly severe because ml's powerful parameterized module (functor) facility entails dependencies among implementation modules, not just among interfaces.to efficiently compile individual modules in such languages, it is useful (in ml, necessary) to infer, digest, and cache the static environment resulting from the compilation of each module. our system provides a simple model of compilation and linkage that supports incremental recompilation (a restricted form of separate compilation) with type-safe linkage. this model is made available to user programs in the form of a set of internal compiler modules, a feature that we call the &ldquo;visible compiler&rdquo;. the chief client of this interface is the irm incremental recompilation manager from cmu.
a framework for reducing the cost of instrumented code. instrumenting code to collect profiling information can cause substantial execution overhead. this overhead makes instrumentation difficult to perform at runtime, often preventing many known offline feedback-directed optimizations from being used in online systems. this paper presents a general framework for performing instrumentation sampling to reduce the overhead of previously expensive instrumentation. the framework is simple and effective, using code-duplication and counter-based sampling to allow switching between instrumented and non-instrumented code. our framework does not rely on any hardware or operating system support, yet provides a high frequency sample rate that is tunable, allowing the tradeoff between overhead and accuracy to be adjusted easily at runtime. experimental results are presented to validate that our technique can collect accurate profiles (93-98% overlap with a perfect profile) with low overhead (averaging 6% total overhead with a naive implementation). a jalape~ no-specific optimization is also presented that reduces overhead further, resulting in an average total overhead of 3%.
experiences creating a portable cedar. cedar is the name for both a language and an environment in use in the computer science laboratory at xerox parc since 1980. the cedar language is a superset of mesa, the major additions being garbage collection and runtime types. neither the language nor the environment was originally intended to be portable, and for many years ran only on d-machines at parc and a few other locations in xerox. we recently re-implemented the language to make it portable across many different architectures. our strategy was, first, to use machine-dependent c code as an intermediate language, second, to create a language-independent layer known as the portable common runtime, and third, to write a relatively large amount of cedar-specific runtime code in a subset of cedar itself. by treating c as an intermediate code we are able to achieve reasonably fast compilation, very good eventual machine code, and all with relatively small programmer effort. because cedar is a much richer language than c, there were numerous issues to resolve in performing an efficient translation and in providing reasonable debugging. these strategies will be of use to many other porters of high-level languages who may wish to use c as an assembler language without giving up either ease of debugging or high performance. we present a brief description of the cedar language, our portability strategy for the compiler and runtime, our manner of making connections to other languages and the unix* operating system, and some measures of the performance of our &ldquo;portable cedar&rdquo;.