waashk/dblp huggingface dataset:
path slicing. we present a new technique, path slicing, that takes as input a possibly infeasible path to a target location, and eliminates all the operations that are irrelevant towards the reachability of the target location. a path slice is a subsequence of the original path whose infeasibility guarantees the infeasibility of the original path, and whose feasibility guarantees the existence of some feasible variant of the given path that reaches the target location even though the given path may itself be infeasible. our method combines the ability of program slicing to look at several program paths, with the precision that dynamic slicing enjoys by focusing on a single path. we have implemented path slicing to analyze possible counterexamples returned by the software model checker blast. we show its effectiveness in drastically reducing the size of the counterexamples to less than 1% of their original size. this enables the precise verification of application programs (upto 100kloc), by allowing the analysis to focus on the part of the counterexample that is relevant to the property being checked.
code placement for improving dynamic branch prediction accuracy. code placement techniques have traditionally improved instruction fetch bandwidth by increasing instruction locality and decreasing the number of taken branches. however, traditional code placement techniques have less benefit in the presence of a trace cache that alters the placement of instructions in the instruction cache. moreover, as pipelines have become deeper to accommodate increasing clock rates, branch misprediction penalties have become a significant impediment to performance. we evaluate pattern history table partitioning, a feedback directed code placement technique that explicitly places conditional branches so that they are less likely to interfere destructively with one another in branch prediction tables. on spec cpu benchmarks running on an intel pentium 4, branch mispredictions are reduced by up to 22% and 3.5% on average. this reduction yields a speedup of up to 16.0% and 4.5% on average. by contrast, branch alignment, a previous code placement technique, yields only up to a 4.7% speedup and less than 1% on average.
context-sensitive domain-independent algorithm composition and selection. progressing beyond the productivity of present-day languages appears to require using domain-specific knowledge. domain-specific languages and libraries (dsls) proliferate, but most optimizations and language features have limited portability because each language's semantics are related closely to its domain. we explain how any dsl compiler can use a domain-independent ai planner to implement algorithm composition as a language feature. our notion of composition addresses a common dsl problem: good library designers tend to minimize redundancy by including only fundamental procedures that users must chain together into call sequences. novice users are confounded by not knowing an appropriate sequence to achieve their goal. composition allows the programmer to define and call an abstract algorithm (aa) like a procedure. the compiler replaces an aa call with a sequence of library calls, while considering the calling context. because ai planners compute a sequence of operations to reach a goal state, the compiler can implement composition by analyzing the calling context to provide the planner's initial state. nevertheless, mapping composition onto planning is not straightforward because applying planning to software requires extensions to classical planning, and procedure specifications may be incomplete when expressed in a planning language. compositions may not be provably correct, so our approach mitigates semantic incompleteness with unobtrusive programmer-compiler interaction. this tradeoff is key to making composition a practical and natural feature of otherwise imperative languages, whose users eschew complex logical specifications. compositions satisfying an aa may not be equal in performance, memory usage, or precision and require selection of a preferred solution. we examine language design and implementation issues, and we perform a case study on the bioperl bioinformatics library.
min-cut program decomposition for thread-level speculation. with billion-transistor chips on the horizon, single-chip multiprocessors (cmps) are likely to become commodity components. speculative cmps use hardware to enforce dependence, allowing the compiler to improve performance by speculating on ambiguous dependences without absolute guarantees of independence. the compiler is responsible for decomposing a sequential program into speculatively parallel threads, while considering multiple performance overheads related to data dependence, load imbalance, and thread prediction. although the decomposition problem lends itself to a min-cut-based approach, the overheads depend on the thread size, requiring the edge weights to be changed as the algorithm progresses. the changing weights make our approach different from graph-theoretic solutions to the general problem of task scheduling. one recent work uses a set of heuristics, each targeting a specific overhead in isolation, and gives precedence to thread prediction, without comparing the performance of the threads resulting from each heuristic. by contrast, our method uses a sequence of balanced min-cuts that give equal consideration to all the overheads, and adjusts the edge weights after every cut. this method achieves an (geometric) average speedup of 74% for floating-point programs and 23% for integer programs on a four-processor chip, improving on the 52% and 13% achieved by the previous heuristics.
dependence-based program analysis. program analysis and optimization can be speeded up through the use of the dependence flow graph (dfg), a representation of program dependences which generalizes def-use chains and static single assignment (ssa) form. in this paper, we give a simple graph-theoretic description of the dfg and show how the dfg for a program can be constructed in o(ev) time. we then show how forward and backward dataflow analyses can be performed efficiently on the dfg, using constant propagation and elimination of partial redundancies as examples. these analyses can be framed as solutions of dataflow equations in the dfg. our construction algorithm is of independent interest because it can be used to construct a program's control dependence graph in o(e) time and its ssa representation in o(ev) time, which are improvements over existing algorithms.
the program structure tree: computing control regions in linear time. in this paper, we describe the program structure tree (pst), a hierarchical representation of program structure based on single entry single exit (sese) regions of the control flow graph. we give a linear-time algorithm for finding sese regions and for building the pst of arbitrary control flow graphs (including irreducible ones). next, we establish a connection between sese regions and control dependence equivalence classes, and show how to use the algorithm to find control regions in linear time. finally, we discuss some applications of the pst. many control flow algorithms, such as construction of static single assignment form, can be speeded up by applying the algorithms in a divide-and-conquer style to each sese region on its own. the pst is also used to speed up data flow analysis by exploiting &ldquo;sparsity&rdquo;. experimental results from the perfect club and spec89 benchmarks confirm that the pst approach finds and exploits program structure.
a semantics for imprecise exceptions. some modern superscalar microprocessors provide only imprecise exceptions. that is, they do not guarantee to report the same exception that would be encountered by a straightforward sequential execution of the program. in exchange, they offer increased performance or decreased chip area (which amount to much the same thing).this performance/precision tradeoff has not so far been much explored at the programming language level. in this paper we propose a design for imprecise exceptions in the lazy functional programming language haskell. we discuss several designs, and conclude that imprecision is essential if the language is still to enjoy its current rich algebra of transformations. we sketch a precise semantics for the language extended with exceptions.the paper shows how to extend haskell with exceptions without crippling the language or its compilers. we do not yet have enough experience of using the new mechanism to know whether it strikes an appropriate balance between expressiveness and performance.
denali: a goal-directed superoptimizer. this paper provides a preliminary report on a new research project that aims to construct a code generator that uses an automatic theorem prover to produce very high-quality (in fact, nearly mathematically optimal) machine code for modern architectures. the code generator is not intended for use in an ordinary compiler, but is intended to be used for inner loops and critical subroutines in those cases where peak performance is required, no available compiler generates adequately efficient code, and where current engineering practice is to use hand-coded machine language. the paper describes the design of the superoptimizer, and presents some encouraging preliminary results.
design, implementation and evaluation of the fnc-2 attribute grammar system. fnc-2 is a new attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. its development at inria started in 1986, and a first running prototype is available since early 1989. its most important features are: efficient exhaustive and incremental visit-sequence-based evaluation of strongly (absolutely) non-circular ags; extensive space optimizations; a specially-designed ag-description language, with provisions for true modularity; portability and versatility of the generated evaluators; complete environment for application development. this paper briefly describes the design and implementation of fnc-2 and its peripherals. then preliminary experience with the system is reported.
reasoning about continuations with control effects. we present a new static analysis method for first-class continuations that uses an effect system to classify the control domain behavior of expressions in a typed polymorphic language. we introduce two new control effects, goto and comefrom, that describe the control flow properties of expressions. an expression that does not have a goto effect is said to be continuation following because it will always call its passed return continuation. an expression that does not have a comefrom effect is said to be continuation discarding because it will never preserve its return continuation for later use. unobservable control effects can be masked by the effect system. control effect soundness theorems guarantee that the effects computed statically by the effect system are a conservative approximation of the dynamic behavior of an expression. the effect system that we describe performs certain kinds of control flow analysis that were not previously feasible. we discuss how this analysis can enable a variety of compiler optimizations, including parallel expression scheduling in the presence of complex control structures, and stack allocation of continuations. the effect system we describe has been implemented as an extension to the fx-87 programming language.
incremental re-execution of programs. interpreters replace the edit/compile/run cyle with edit/run. dynamic computing environments, like spreadsheets, shorten this still more to just edit. so-called "visiprog" environments, such as maryland's xed, permit developing normal imperative programs in a dynamic computing environment, xed and similar environments, because they show the results of executing a program after every (reasonable) editing step, raise the issue of efficient incremental execution. incremental execution optimizations are also applicable to any programming situation, including batch/cards, in which nearly the same program is run many times on nearly the same data. however, the requirement of remembering large amounts of internal state between runs make incremental exectution most natural for interpreted languages. this paper examines some algorithms for incremental execution. based on the frequency of typical program editing changes, we predict the importance of optimizing certain kinds of incremental execution. we also examine actual speedups obtained in executing programs after subjecting them to these simulated incremental edits under these optimizations. the speedups range from factors of 1.1 to near 10. finally, we discuss the feasibility of including these optimizations in an actual dynamic computing environment like xed, and in more traditional programming environments.
effective sign extension elimination. computer designs are shifting from 32-bit architectures to 64-bit architectures, while most of the programs available today are still designed for 32-bit architectures. java&trade;, for example, specifies the frequently used int" as a 32-bit data type. if such java programs are executed on a 64-bit architecture, many 32-bit values must be sign-extended to 64-bit values for integer operations. this causes serious performance overhead. in this paper, we present a fast and effective algorithm for eliminating sign extensions. we implemented this algorithm in the ibm java just-in-time (jit) compiler for ia-64&trade;. our experimental results show that our algorithm effectively eliminates the majority of sign extensions. they also show that it significantly improves performance, while it increases jit compilation time by only 0.11%. we implemented our algorithm for programs in java, but it can be applied to any language requiring sign extensions.
ccal: an interpreted language for experimentation in concurrent control. concurrent control abstraction language, ccal, is an interpreted language which provides no particular control regime to the user. ccal instead supports five primitive operations which manipulate an abstract model of inter-procedural control. this model is intrinsically concurrent, and the user is allowed to construct high-level concurrent control operations from the primitives (hence, control abstraction). the primary use of ccal is as a vehicle by which rapid prototyping of application specific control forms may be done and as a tool for the construction and evaluation of novel control forms, especially control forms for highly concurrent and distributed systems. the ccal interpreter is implemented as a distributed program on a network of vaxen and sun-3 workstations under 4.2bsd and 4.3bsd unix1. ccal programs appear as multi-process programs in a shared memory system. both true and apparent concurrency are possible. this paper describes the control abstraction facilities offered by the ccal interpreter, its use, and implementation strategies in the distributed environment.
design and implementation of generics for the .net common language runtime. the microsoft.net common language runtime provides a shared type system, intermediate language and dynamic execution environment for the implementation and inter-operation of multiple source languages. in this paper we extend it with direct support for parametric polymorphism (also known as generics), describing the design through examples written in an extended version of the c# programming language, and explaining aspects of implementation by reference to a prototype extension to the runtime. our design is very expressive, supporting parameterized types, polymorphic static, instance and virtual methods, &ldquo;f-bounded&rdquo; type parameters, instantiation at pointer and value types, polymorphic recursion, and exact run-time types. the implementation takes advantage of the dynamic nature of the runtime, performing just-in-time type specialization, representation-based code sharing and novel techniques for efficient creation and use of run-time types. early performance results are encouraging and suggest that programmers will not need to pay an overhead for using generics, achieving performance almost matching hand-specialized code.
the compressor: concurrent, incremental, and parallel compaction. the widely used mark-and-sweep garbage collector has a drawback in that it does not move objects during collection. as a result, large long-running realistic applications, such as web application servers, frequently face the fragmentation problem. to eliminate fragmentation, a heap compaction is run periodically. however, compaction typically imposes very long undesirable pauses in the application. while efficient concurrent collectors are ubiquitous in production runtime systems (such as jvms), an efficient non-intrusive compactor is still missing.in this paper we present the compressor, a novel compaction algorithm that is concurrent, parallel, and incremental. the compressor compacts the entire heap to a single condensed area, while preserving the objects' order, but reduces pause times significantly, thereby allowing acceptable runs on large heaps. furthermore, the compressor is the first compactor that requires only a single heap pass. as such, it is the most efficient compactors known today, even when run in a parallel stop-the-world manner (i.e., when the program threads are halted). thus, to the best of our knowledge, the compressor is the most efficient compactor known today. the compressor was implemented on a jikes research rvm and we provide measurements demonstrating its qualities.
balanced scheduling: instruction scheduling when memory latency is uncertain. traditional list schedulers order instructions based on an optimistic estimate of the load delay imposed by the implementation. therefore they cannot respond to variations in load latencies (due to cache hits or misses, congestion in the memory interconnect, etc.) and cannot easily be applied across different implementations. we have developed an alternative algorithm, known as balanced scheduling, that schedules instructions based on an estimate of the amount of instruction level parallelism in the program. since scheduling decisions are program- rather than machine-based, balanced scheduling is unaffected by implementation changes. since it is based on the amount of instruction level parallelism that a program can support, it can respond better to variations in load latencies. performance improvements over a traditional list scheduler on a fortran workload and simulating several different machine types (cache-based workstations, large parallel machines with a multipath interconnect and a combination, all with non-blocking processors) are quite good, averaging between 3% and 18%.
fast breakpoints: design and implementation. in re-implementing fast breakpoints for stock hardware, i discovered the joys of putting self-modifying code to good use.by "fast breakpoints" i mean inserting transfers of control to change the behavior of a running program. i don't claim to have invented fast breakpoints: i have traced their use back to 1951 [1]. i didn't even put these breakpoints to novel uses. all i did was rediscover how easy it is to take statically compiled code and modify it at runtime to alter the semantics of programs. the most obvious application is to evaluate predicates and expressions for debugging, but other uses are possible.we have designed and implemented a fast breakpoint facility. breakpoints are usually thought of as a feature of an interactive debugger, in which case the breakpoints need not be particularly fast. in our environment breakpoints are often used for non-interactive information gathering; for example, procedure call count and statement execution count profiling [swinehart, et al.]. when used non-interactively, breakpoints should be as fast as possible, so as to perturb the execution of the program as little as possible. even in interactive debuggers, a conditional breakpoint facility would benefit from breakpoints that could transfer to the evaluation of the condition rapidly, and continue expeditiously if the condition were not satisfied. such conditional breakpoints could be used to check assertions, etc. program advising could also make use of fast breakpoints [teitelman]. examples of advising include tracing, timing, and even animation, all of which should be part of an advanced programming environment.we have ported the cedar environment from a machine with microcode support for breakpoints [lampson and pier] to commercial platforms running c code [atkinson, et al.]. most of our ports run under the unix* operating system, so one choice for implementing breakpoints for cedar was to use the breakpoint facility provided by that system. the breakpoints provided by the unix operating system are several orders of magnitude too slow (and also several process switches too complicated) for the applications we have in mind. so we designed a breakpoint system that was fast enough for our purposes.breakpoints for uni-processors running single threads of control used to be fast and simple to implement. this paper shows that breakpoints can still be fast, even with multiple threads of control on multi-processors. this paper describes problems in the design of a breakpoint package for modern computer architectures and programming styles, and our solutions to them for a particular architecture.
anatomy of a hardware compiler. programming-language compilers generate code targeted to machines with fixed architectures, either parallel or serial. compiler techniques can also be used to generate the hardware on which these programming languages are executed. in this paper we demonstrate that many compilation techniques developed for programming languages are applicable to compilation of register-transfer hardware designs. our approach uses a typical syntax-directed translation &rarr; global optimization &rarr; local optimization &rarr; code generation &rarr; peephole optimization method. in this paper we will describe ways in which we have both followed and diverged from traditional compiler approaches to these problems and compare our approach to other compiler oriented approaches to hardware compilation.
data specialization. given a repeated computation, part of whose input context remains invariant across all repetitions, program staging improves performance by separating the computation into two phases. an early phase executes only once, performing computations depending only on invariant inputs, while a late phase repeatedly performs the remainder of the work given the varying inputs and the results of the early computations.common staging techniques based on dynamic compilation statically construct an early phase that dynamically generates object code customized for a particular input context. in effect, the results of the invariant computations are encoded as the compiled code for the late phase.this paper describes an alternative approach in which the results of early computations are encoded as a data structure, allowing both the early and late phases to be generated statically. by avoiding dynamic code manipulation, we give up some optimization opportunities in exchange for significantly lower dynamic space/time overhead and reduced implementation complexity.
lazy code motion. we present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. the point of our algorithm is the decomposition of the bi-directional structure of the known placement algorithms into a sequence of a backward and a forward analysis, which directly implies the efficiency result. moreover, the new compositional structure opens the algorithm for modification: two further uni-directional analysis components exclude any unnecessary code motion. this laziness of our algorithm minimizes the register pressure, which has drastic effects on the run-time behaviour of the optimized programs in practice, where an economical use of registers is essential.