waashk/dblp huggingface dataset:
a recursive interpreter for the icon programming language. the implementation of the icon programming language is more interesting and difficult than the implementation of many other programming languages because an expression in icon can generate a sequence of results. the implementation therefore must support control backtracking in expression evaluation. there also are several novel control structures related to generators. because expression evaluation is limited lexically, a full coroutine mechanism is not needed and expression evaluation can be handled in a stack-like fashion.the implementation of icon consists of a virtual machine with a stack-based architecture and an interpreter that executes the virtual machine instructions. there have been several different interpreters for icon's virtual machine. this paper describes a new approach in which the interpreter is called recursively whenever the context for expression evaluation changes. this recursive interpreter has the advantage of being conceptually clear and flexible without sacrificing efficiency.
the design and implementation of home. home is a version of smalltalk which can be efficiently executed on a multiprocessor and can be executed in parallel by combining a smalltalk process with a mach thread and executing the process on the thread. home is nearly the same as ordinary smalltalk except that multiple processes may execute in parallel. thus, almost all applications running on ordinary smalltalk can be executed on home without changes in their code. home was designed and implemented based on the following fundamental policies: (1) theoretically, an infinite number of processes can become active; (2) the moment a process is scheduled, it becomes active; (3) no process switching occurs; (4) home is equivalent to ordinary smalltalk except for the previous three policies. the performance of the current implementation of home running on omron luna-88k, which had four processors, was measured by benchmarks which execute in parallel with multiple processes. in all benchmarks, the results showed that home's performance is much better than hps on the same workstation.
a parallel, incremental and concurrent gc for servers. multithreaded applications with multi-gigabyte heaps running on modern servers provide new challenges for garbage collection (gc). the challenges for "server-oriented" gc include: ensuring short pause times on a multi-gigabyte heap, while minimizing throughput penalty, good scaling on multiprocessor hardware, and keeping the number of expensive multi-cycle fence instructions required by weak ordering to a minimum. we designed and implemented a fully parallel, incremental, mostly concurrent collector, which employs several novel techniques to meet these challenges. first, it combines incremental gc to ensure short pause times with concurrent low-priority background gc threads to take advantage of processor idle time. second, it employs a low-overhead work packet mechanism to enable full parallelism among the incremental and concurrent collecting threads and ensure load balancing. third, it reduces memory fence instructions by using batching techniques: one fence for each block of small objects allocated, one fence for each group of objects marked, and no fence at all in the write barrier. when compared to the mature well-optimized parallel stop-the-world mark-sweep collector already in the ibm jvm, our collector prototype reduces the maximum pause time from 284 ms to 101 ms, and the average pause time from 266 ms to 66 ms while only losing 10% throughput when running the specjbb2000 benchmark on a 256 mb heap on a 4-way 550 mhz pentium multiprocessor.
simplification of array access patterns for compiler optimizations. existing array region representation techniques are sensitive to the complexity of array subscripts. in general, these techniques are very accurate and efficient for simple subscript expressions, but lose accuracy or require potentially expensive algorithms for complex subscripts. we found that in scientific applications, many access patterns are simple even when the subscript expressions are complex. in this work, we present a new, general array access representation and define operations for it. this allows us to aggregate and simplify the representation enough that precise region operations may be applied to enable compiler optimizations. our experiments show that these techniques hold promise for speeding up applications.
multiprocessor smalltalk: a case study of a multiprocessor-based programming environment. we have adapted an interactive programming system (smalltalk) to a multiprocessor (the firefly). the task was not as difficult as might be expected, thanks to the application of three basic strategies: serialization, replication, and reorganization. serialization of access to resources disallows concurrent access. replication provides multiple instances of resources when they cannot or should not be serialized. reorganization allows us to restructure part of the system when the other two strategies cannot be applied. we serialized i/o, memory allocation, garbage collection, and scheduling, we replicated the interpreter process, software caches, and a free-list, and we reorganized portions of the scheduling system to deal with some deep-seated assumptions. our changes yielded a fairly low static overhead. we attribute our success to the choice of a small, flexible operating system, a set of constraints which simplified the problem, and the versality of the three strategies for dealing with concurrency. the current system has a moderate amount of overhead when parallelism is being used&mdash;25% to 65%. it is acceptable, but we believe it can be improved.
escape analysis on lists. higher order functional programs constantly allocate objects dynamically. these objects are typically cons cells, closures, and records and are generally allocated in the heap and reclaimed later by some garbage collection process. this paper describes a compile time analysis, called escape analysis, for determining the lifetime of dynamically created objects in higher order functional programs, and describes optimizations that can be performed, based on the analysis, to improve storage allocation and reclamation of such objects. in particular, our analysis can be applied to programs manipulating lists, in which case optimizations can be performed to allow cons cells in spines of lists to be either reclaimed immediately or reused without incurring any garbage collection overhead. in a previous paper on escape analysis [10], we had left open the problem of performing escape analysis on lists. escape analysis simply determines when the argument (or some part of the argument) to a function call is returned by that call. this simple piece of information turns out to be sufficiently powerful to allow stack allocation of objects, compile-time garbage collection, reduction of run-time storage reclamation overhead, and other optimizations that are possible when the lifetimes of objects can be computed statically. our approach is to define a high-level non-standard semantics that, in many ways, is similar to the standard semantics and captures the escape behavior caused by the constructs in a functional language. the advantage of our analysis lies in its conceptual simplicity and portability (i.e. no assumption is made about an underlying abstract machine).
accurate static branch prediction by value range propagation. the ability to predict at compile time the likelihood of a particular branch being taken provides valuable information for several optimizations, including global instruction scheduling, code layout, function inlining, interprocedural register allocation and many high level optimizations. previous attempts at static branch prediction have either used simple heuristics, which can be quite inaccurate, or put the burden onto the programmer by using execution profiling data or source code hints.this paper presents a new approach to static branch prediction called value range propagation. this method tracks the weighted value ranges of variables through a program, much like constant propagation. these value ranges may be either numeric of symbolic in nature. branch prediction is then performed by simply consulting the value range of the appropriate variable. heuristics are used as a fallback for cases where the value range of the variable cannot be determined statically. in the process, value range propagationsubsumes both constant propagation and copy propagation.experimental results indicate that this approach produces significantly more accurate predictions than the best existing heuristic techniques. the value range propagation method can be implemented over any &ldquo;factored&rdquo; dataflow representation with a static single assignment property (such as ssa form or a dependence flow graph where the variables have been renamed to achieve single assignment). experimental results indicate that the technique maintains the linear runtime behavior of constant propagation experienced in practice.
implementing type classes. we describe the implementation of a type checker for the functional programming language haskell that supports the use of type classes. this extends the type system of ml to support overloading (ad-hoc polymorphism) and can be used to implement features such as equality types and numeric overloading in a simple and general way. the theory of type classes is well understood, but the practical issues involved in the implementation of such systems have not received a great deal of attention. in addition to the basic type checking algorithm, an implmenentation of type classes also requires some form of program transformation. in all current haskell compilers this takes the form of dictionary conversion, using functions as hidden parameters to overloaded values. we present efficient techniques for type checking and dictionary conversion. a number of optimizations and extensions to the basic type class sytems are also described.
profile guided code positioning. this paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. the primary objective of the positioning is to reduce the overhead of the instruction memory hierarchy. after initial investigation in the literature, we decided to implement two prototypes for the hewlett-packard precision architecture (pa-risc). the first, built on top of the linker, positions code based on whole procedures. this prototype has the ability to move procedures into an order that is determined by a &ldquo;closest is best&rdquo; strategy. the second prototype, built on top of an existing optimizer package, positions code based on basic blocks within procedures. groups of basic blocks that would be better as straight-line sequences are identified as chains. these chains are then ordered according to branch heuristics. code that is never executed during the data collection runs can be physically separated from the primary code of a procedure by a technique we devised called procedure splitting. the algorithms we implemented are described through examples in this paper. the performance improvements from our work are also summarized in various tables and charts.
higher-order abstract syntax. we describe motivation, design, use, and implementation of higher-order abstract syntax as a central representation for programs, formulas, rules, and other syntactic objects in program manipulation and other formal systems where matching and substitution or unification are central operations. higher-order abstract syntax incorporates name binding information in a uniform and language generic way. thus it acts as a powerful link integrating diverse tools in such formal environments. we have implemented higher-order abstract syntax, a supporting matching and unification algorithm, and some clients in common lisp in the framework of the ergo project at carnegie mellon university.
apt: a data structure for optimal control dependence computation. the control dependence relation is used extensively in restructuring compilers. this relation is usually represented using the control dependence graph; unfortunately, the size of this data structure can be quadratic in the size of the program, even for some structured programs. in this paper, we introduce a data structure called the augmented post-dominator tree (apt) which is constructed in space and time proportional to the size of the program, and which can answer control dependence queries in time proportional to the size of the output. therefore, apt is an optimal representation of control dependence. we also show that using apt, we can compute ssa graphs, as well as sparse dataflow evaluator graphs, in time proportional to the size of the program. finally, we put apt in perspective by showing that it can be viewed as a factored representation of control dependence graph in which filtered search is used to answer queries.
two-level hybrid interpreter/native code execution for combined space-time program efficiency. a two-level programming model permits the applications programmer to write programs that benefit both from the code density of interpreted virtual machines and from the speed of native code execution. a well-defined boundary between the native code and the virtual machine facilitates the development of translators to be used at both levels.
optimizing direct-threaded code by selective inlining. achieving good performance in bytecoded language interpreters is difficult without sacrificing both simplicity and portability. this is due to the complexity of dynamic translation ("just-in-time compilation") of bytecodes into native code, which is the mechanism employed universally by high-performance interpreters.we demonstrate that a few simple techniques make it possible to create highly-portable dynamic translators that can attain as much as 70% the performance of optimized c for certain numerical computations. translators based on such techniques can offer respectable performance without sacrificing either the simplicity or portability of much slower "pure" bytecode interpreters.
tcc: a system for fast, flexible, and high-level dynamic code generation. tcc is a compiler that provides efficient and high-level access to dynamic code generation. it implements the 'c ("tick-c") programming language, an extension of ansi c that supports dynamic code generation [15]. 'c gives power and flexibility in specifying dynamically generated code: whereas most other systems use annotations to denote run-time invariants. 'c allows the programmer to specify and compose arbitrary expressions and statements at run time. this degree of control is needed to efficiently implement some of the most important applications of dynamic code generation, such as "just in time" compilers [17] and efficient simulators [10, 48, 46].the paper focuses on the techniques that allow tcc to provide 'c's flexibility and expressiveness without sacrificing run-time code generation efficiency. these techniques include fast register allocation, efficient creation and composition of dynamic code specifications, and link-time analysis to reduce the size of dynamic code generators. tcc also implements two different dynamic code generation strategies, designed to address the tradeoff of dynamic compilation speed versus generated code quality. to characterize the effects of dynamic compilation, we present performance measurements for eleven programs compiled using tcc. on these applications, we measured performance improvements of up to one order of magnitude.to encourage further experimentation and use of dynamic code generation, we are making the tcc compiler available in the public domain. this is, to our knowledge, the first high-level dynamic compilation system to be made available.
locksmith: context-sensitive correlation analysis for race detection. one common technique for preventing data races in multi-threaded programs is to ensure that all accesses to shared locations are consistently protected by a lock. we present a tool called locksmith for detecting data races in c programs by looking for violations of this pattern. we call the relationship between locks and the locations they protect consistent correlation, and the core of our technique is a novel constraint-based analysis that infers consistent correlation context-sensitively, using the results to check that locations are properly guarded by locks. we present the core of our algorithm for a simple formal language λ> which we have proven sound, and discuss how we scale it up to an algorithm that aims to be sound for all of c. we develop several techniques to improve the precision and performance of the analysis, including a sharing analysis for inferring thread locality; existential quantification for modeling locks in data structures; and heuristics for modeling unsafe features of c such as type casts. when applied to several benchmarks, including multi-threaded servers and linux device drivers, locksmith found several races while producing a modest number of false alarm.
static conflict analysis for multi-threaded object-oriented programs. a compiler for multi-threaded object-oriented programs needs information about the sharing of objects for a variety of reasons: to implement optimizations, to issue warnings, to add instrumentation to detect access violations that occur at runtime. an object use graph (oug) statically captures accesses from different threads to objects. an oug extends the heap shape graph (hsg), which is a compile-time abstraction for runtime objects (nodes) and their reference relations (edges). an oug specifies for a specific node in the hsg a partial order of events relevant to the corresponding runtime object(s). relevant events include read and write access, object escape, thread start and join.ougs have been implemented in a java compiler. initial experience shows that ougs are effective to identify object accesses that potentially conflict at runtime and isolate accesses that never cause a problem at runtime. the capabilities of ougs are compared with an advanced program analysis that has been used for lock elimination. for the set of benchmarks investigated here, ougs report only a fraction of shared objects as conflicting and reduce the number of compile-time reports in terms of allocation sites of conflicting objects by 28--92% (average 64%). for benchmarks of up to 30 kloc, the time taken to construct ougs is, with one exception, in the order of seconds.the information collected in the oug has been used to instrument java programs with checks for object races. ougs provide precise information about object sharing and static protection, so runtime instrumentation that checks those cases that cannot be disambiguated at compile-time is sparse, and the total runtime overhead of checking for object races is only 3--86% (average 47%).
simple and efficient burs table generation. a simple and efficient algorithm for generating bottom-up rewrite system (burs) tables is described. a small prototype implementation produces tables 10 to 30 times more quickly than the best current techniques. the algorithm does not require novel data structures or complicated algorithmic techniques. previously published methods for the on-the-fly elimination of states are generalized and simplified to create a new method, triangle trimming, that is employed in the algorithm.
simple translation of goal-directed evaluation. this paper presents a simple, powerful and flexible technique for reasoning about and translating the goal-directed evaluation of programming language constructs that either succeed (and generate sequences of values) or fail. the technique generalizes the byrd box, a well-known device for describing prolog backtracking.
probalistic register allocation. a new global register allocation technique, probabilistic register allocation, is described. probabilistic register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that excellent allocation choices can be made. local allocation is done first, and then global allocation is done iteratively beginning in the most deeply nested loops. because local allocation precedes global allocation, probabilistic allocation does not interfere with the use of well-known, high-quality local register allocation and instruction scheduling techniques.
counting solutions to presburger formulas: how and why. we describe methods that are able to count the number of integer solutions to selected free variables of a presburger formula, or sum a polynomial over all integer solutions of selected free variables of a presburger formula. this answer is given symbolically, in terms of symbolic constants (the remaining free variables in the presburger formula). for example, we can create a presburger formula who's solutions correspond to the iterations of a loop. by counting these, we obtain an estimate of the execution time of the loop. in more complicated applications, we can create presburger formulas who's solutions correspond to the distinct memory locations or cache lines touched by a loop, the flops executed by a loop, or the array elements that need to be communicated at a particular point in a distributed computation. by counting the number of solutions, we can evaluate the computation/memory balance of a computation, determine if a loop is load balanced and evaluate message traffic and allocate message buffers.
compressing java class files. java class files are often distributed as jar files, which are collections of individually compressed class files (and possibility other files). jar files are typically about 1/2 the size of the original class files due to compression. i have developed a wire-code format for collections of java class files. this format is typically 1/2 to 1/5 of the size of the corresponding compressed jar file (1/4 to 1/10 the size of the original class files).
two-directional record layout for multiple inheritance. much recent work in polymorphic programming languages allows subtyping and multiple inheritance for records. in such systems, we would like to extract a field from a record with the same efficiency as if we were not making use of subtyping and multiple inheritance. methods currently used make field extraction 3-5 times slower, which can produce a significant overall performance slowdown. we describe a record layout algorithm that allows us to assign a fixed offset to each field name. this allows field extraction to done just as quickly as in systems that do not provide multiple inheritance. assigning fixed offsets may require us to leave gaps in some records (and waste space). however, by placing fields at both positive and negative offsets we can drastically reduce the amount of wasted space. finding an optimal layout is np-hard, so we propose and analyze heuristic algorithms for producing good two-direction record layouts. in a trial run, our algorithm produced a fixed layout for the instance variables of the 563 flavors of a lisp flavors system; this fixed layout only wastes 6% of the total space consumed by a collection of one instance of each flavor.
eliminating false data dependences using the omega test. array data dependence analysis methods currently in use generate false dependences that can prevent useful program transformations. these false dependences arise because the questions asked are conservative approximations to the questions we really should be asking. unfortunately, the questions we really should be asking go beyond integer programming and require decision procedures for a sublcass of presburger formulas. in this paper, we describe how to extend the omega test so that it can answer these queries and allow us to eliminate these false data dependences. we have implemented the techniques described here and believe they are suitable for use in production compilers.