waashk/dblp huggingface dataset:
a provably sound tal for back-end optimization. typed assembly languages provide a way to generate machine-checkable safety proofs for machine-language programs. but the soundness proofs of most existing typed assembly languages are hand-written and cannot be machine-checked, which is worrisome for such large calculi. we have designed and implemented a low-level typed assembly language (ltal) with a semantic model and established its soundness from the model. compared to existing typed assembly languages, ltal is more scalable and more secure; it has no macro instructions that hinder low-level optimizations such as instruction scheduling; its type constructors are expressive enough to capture dataflow information, support the compiler's choice of data representations and permit typed position-independent code; and its type-checking algorithm is completely syntax-directed.we have built a prototype system, based on standard ml of new jersey, that compiles most of core ml to sparc code. we explain how we were able to make the untyped back end in sml/nj preserve types during instruction selection and register allocation, without restricting low-level optimizations and without knowledge of any type system pervading the instruction selector and register allocator.
a parallel, real-time garbage collector. we describe a parallel, real-time garbage collector and present experimental results that demonstrate good scalability and good real-time bounds. the collector is designed for shared-memory multiprocessors and is based on an earlier collector algorithm [2], which provided fixed bounds on the time any thread must pause for collection. however, since our earlier algorithm was designed for simple analysis, it had some impractical features. this paper presents the extensions necessary for a practical implementation: reducing excessive interleaving, handling stacks and global variables, reducing double allocation, and special treatment of large and small objects. an implementation based on the modified algorithm is evaluated on a set of 15 sml benchmarks on a sun enterprise 10000, a 64-way ultrasparc-ii multiprocessor. to the best of our knowledge, this is the first implementation of a parallel, real-time garbage collector. the average collector speedup is 7.5 at 8 processors and 17.7 at 32 processors. maximum pause times range from 3 ms to 5 ms. in contrast, a non-incremental collector (whether generational or not) has maximum pause times from 10 ms to 650 ms. compared to a non-parallel, stop-copy collector, parallelism has a 39% overhead, while real-time behavior adds an additional 12% overhead. since the collector takes about 15% of total execution time, these features have an overall time costs of 6% and 2%.
modular interprocedural pointer analysis using access paths: design, implementation, and evaluation. in this paper we present a modular interprocedural pointer analysis algorithm based on access-paths for c programs. we argue that access paths can reduce the overhead of representing context-sensitive transfer functions and effectively distinguish non-recursive heap objects. and when the modular analysis paradigm is used together with other techniques to handle type casts and function pointers, we are able to handle significant programs like those in the speccint92 and speccint95 suites. we have implemented the algorithm and tested it on a pentium ii 450 pc running linux. the observed resource consumption and performance improvement are very encouraging.
generational stack collection and profile-driven pretenuring. this paper presents two techniques for improving garbage collection performance: generational stack collection and profile-driven pretenuring. the first is applicable to stack-based implementations of functional languages while the second is useful for any generational collector. we have implemented both techniques in a generational collector used by the til compiler (tarditi, morrisett, cheng, stone, harper, and lee 1996), and have observed decreases in garbage collection times of as much as 70% and 30%, respectively.functional languages encourage the use of recursion which can lead to a long chain of activation records. when a collection occurs, these activation records must be scanned for roots. we show that scanning many activation records can take so long as to become the dominant cost of garbage collection. however, most deep stacks unwind very infrequently, so most of the root information obtained from the stack remains unchanged across successive garbage collections. generational stack collection greatly reduces the stack scan cost by reusing information from previous scans.generational techniques have been successful in reducing the cost of garbage collection (ungar 1984). various complex heap arrangements and tenuring policies have been proposed to increase the effectiveness of generational techniques by reducing the cost and frequency of scanning and copying. in contrast, we show that by using profile information to make lifetime predictions, pretenuring can avoid copying data altogether. in essence, this technique uses a refinement of the generational hypothesis (most data die young) with a locality principle concerning the age of data: most allocations sites produce data that immediately dies, while a few allocation sites consistently produce data that survives many collections.
unified management of registers and cache using liveness and cache bypass. in current computer memory system hierarchy, registers and cache are both used to bridge the reference delay gap between the fast processor(s) and the slow main memory. while registers are managed by the compiler using program flow analysis, cache is mainly controlled by hardware without any program understanding. due to the lack of coordination in managing these two memory structures, significant loss of system performance results because: cache space is wasted to hold inaccessible copies of values in registers. inaccessible copies of values replace those accessible ones from cache. despite the fact that register allocation has long recognized the benefits of live range analysis, current cache management has completely ignored live range information. in this paper, we propose an unified management of registers and cache using liveness and cache bypass. by using a single model to manage these two memory structures, most redundant copies of values in cache can be eliminated. consequently, bus traffic and memory traffic in data cache are greatly reduced and cache effectiveness is improved.
efficient representations and abstractions for quantifying and exploiting data reference locality. with the growing processor-memory performance gap, understanding and optimizing a program's reference locality, and consequently, its cache performance, is becoming increasingly important. unfortunately, current reference locality optimizations rely on heuristics and are fairly ad-hoc. in addition, while optimization technology for improving instruction cache performance is fairly mature (though heuristic-based), data cache optimizations are still at an early stage. we believe the primary reason for this imbalance is the lack of a suitable representation of a program's dynamic data reference behavior and a quantitative basis for understanding this behavior. we address these issues by proposing a quantitative basis for understanding and optimizing reference locality, and by describing efficient data reference representations and an exploitable locality abstraction that support this framework. our data reference representations (whole program streams and stream flow graphs) are compact&mdash;two to four orders of magnitude smaller than the program's data reference trace&mdash;and permit efficient analysis&mdash;on the order of seconds to a few minutes&mdash;even for complex applications. these representations can be used to efficiently compute our exploitable locality abstraction (hot data streams). we demonstrate that these representations and our hot data stream abstraction are useful for quantifying and exploiting data reference locality. we applied our framework to several specint 2000 benchmarks, a graphics program, and a commercial microsoft database application. the results suggest significant opportunity for hot data stream-based locality optimizations.
cache-conscious structure definition. a program's cache performance can be improved by changing the organization and layout of its data---even complex, pointer-based data structures. previous techniques improved the cache performance of these structures by arranging distinct instances to increase reference locality. these techniques produced significant performance improvements, but worked best for small structures that could be packed into a cache block.this paper extends that work by concentrating on the internal organization of fields in a data structure. it describes two techniques---structure splitting and field reordering---that improve the cache behavior of structures larger than a cache block. for structures comparable in size to a cache block, structure splitting can increase the number of hot fields that can be placed in a cache block. in five java programs, structure splitting reduced cache miss rates 10--27% and improved performance 6--18% beyond the benefits of previously described cache-conscious reorganization techniques.for large structures, which span many cache blocks, reordering fields, to place those with high temporal affinity in the same cache block can also improve cache utilization. this paper describes bbcache, a tool that recommends c structure field reorderings. preliminary measurements indicate that reordering fields in 5 active structures improves the performance of microsoft sql server 7.0 2--3%.
dynamic hot data stream prefetching for general-purpose programs. prefetching data ahead of use has the potential to tolerate the grow ing processor-memory performance gap by overlapping long latency memory accesses with useful computation. while sophisti cated prefetching techniques have been automated for limited domains, such as scientific codes that access dense arrays in loop nests, a similar level of success has eluded general-purpose pro grams, especially pointer-chasing codes written in languages such as c and c++. we address this problem by describing, implementing and evaluating a dynamic prefetching scheme. our technique runs on stock hardware, is completely automatic, and works for general-purpose programs, including pointer-chasing codes written in weakly-typed languages, such as c and c++. it operates in three phases. first, the profiling phase gathers a temporal data reference profile from a running program with low-overhead. next, the profiling is turned off and a fast analysis algorithm extracts hot data streams, which are data reference sequences that frequently repeat in the same order, from the temporal profile. then, the system dynamically injects code at appropriate program points to detect and prefetch these hot data streams. finally, the process enters the hibernation phase where no profiling or analysis is performed, and the program continues to execute with the added prefetch instructions. at the end of the hibernation phase, the program is de-optimized to remove the inserted checks and prefetch instructions, and control returns to the profiling phase. for long-running programs, this profile, analyze and optimize, hibernate, cycle will repeat multiple times. our initial results from applying dynamic prefetching are promising, indicating overall execution time improvements of 5.19% for several memory-performance-limited specint2000 benchmarks running their largest (ref) inputs.
cache-conscious structure layout. hardware trends have produced an increasing disparity between processor speeds and memory access times. while a variety of techniques for tolerating or reducing memory latency have been proposed, these are rarely successful for pointer-manipulating programs.this paper explores a complementary approach that attacks the source (poor reference locality) of the problem rather than its manifestation (memory latency). it demonstrates that careful data organization and layout provides an essential mechanism to improve the cache locality of pointer-manipulating programs and consequently, their performance. it explores two placement techniques---clustering and coloring---that improve cache performance by increasing a pointer structure's spatial and temporal locality, and by reducing cache-conflicts.to reduce the cost of applying these techniques, this paper discusses two strategies---cache-conscious reorganization and cache-conscious allocation---and describes two semi-automatic tools---ccmorph and ccmalloc---that use these strategies to produce cache-conscious pointer structure layouts. ccmorph is a transparent tree reorganizer that utilizes topology information to cluster and color the structure. ccmalloc is a cache-conscious heap allocator that attempts to co-locate contemporaneously accessed data elements in the same physical cache block. our evaluations, with microbenchmarks, several small benchmarks, and a couple of large real-world applications, demonstrate that the cache-conscious structure layouts produced by ccmorph and ccmalloc offer large performance benefits---in most cases, significantly outperforming state-of-the-art prefetching.
cache-conscious coallocation of hot data streams. the memory system performance of many programs can be improved by coallocating contemporaneously accessed heap objects in the same cache block. we present a novel profile-based analysis for producing such a layout. the analysis achieves cacheconscious coallocation of a hot data stream h (i.e., a regular data access pattern that frequently repeats) by isolating and combining allocation sites of object instances that appear in h such that intervening allocations coming from other sites are separated. the coallocation solution produced by the analysis is enforced by an automatic tool, cminstr, that redirects a program's heap allocations to a run-time coallocation library comalloc. we also extend the analysis to coallocation at object field granularity. the resulting field coallocation solution generalizes common data restructuring techniques, such as field reordering, object splitting, and object merging, and allows their combination. furthermore, it provides insight into object restructuring by breaking down the coallocation benefit on a per-technique basis, which provides the opportunity to pick the "sweet spot" for each program. experimental results using a set of memory-performance-limited benchmarks, including a few specint2000 programs, and microsoft visualfoxpro, indicate that programs possess significant coallocation opportunities. automatic object coallocation improves execution time by 13% on average in the presence of hardware prefetching. hand-implemented field coallocation solutions for two of the benchmarks produced additional improvements (12% and 22%) but the effort involved suggests implementing an automated version for type-safe languages, such as java and c#.
region inference for an object-oriented language. region-based memory management offers several important potential advantages over garbage collection, including real-time performance, better data locality, and more efficient use of limited memory. researchers have advocated the use of regions for functional, imperative, and object-oriented languages. lexically scoped regions are now a core feature of the real-time specification for java (rtsj)[5].recent research in region-based programming for java has focused on region checking, which requires manual effort to augment the program with region annotations. in this paper, we propose an automatic region inference system for a core subset of java. to provide an inference method that is both precise and practical, we support classes and methods that are region-polymorphic, with region-polymorphic recursion for methods. one challenging aspect is to ensure region safety in the presence of features such as class subtyping, method overriding, and downcast operations. our region inference rules can handle these object-oriented features safely without creating dangling references.
semantic type qualifiers. we present a new approach for supporting user-defined type refinements, which augment existing types to specify and check additional invariants of interest to programmers. we provide an expressive language in which users define new refinements and associated type rules. these rules are automatically incorporated by an extensible typechecker during static typechecking of programs. separately, a soundness checkerautomatically proves that each refinement's type rules ensure the intended invariant, for all possible programs. we have formalized our approach and have instantiated it as a framework for adding new type qualifiers to c programs. we have used this framework to define and automatically prove sound a host of type qualifiers of different sorts, including pos and neg for integers, tainted and untainted for strings, and nonnull and unique for pointers, and we have applied our qualifiers to ensure important invariants on open-source c programs.
efficient and precise datarace detection for multithreaded object-oriented programs. we present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3x to 30x. in contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise. this performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques.
minimizing register usage penalty at procedure calls. inter-procedural register allocation can minimize the register usage penalty at procedure calls by reducing the saving and restoring of registers at procedure boundaries. a one-pass inter-procedural register allocation scheme based on processing the procedures in a depth-first traversal of the call graph is presented. this scheme can be overlaid on top of intra-procedural register allocation via a simple extension to the priority-based coloring algorithm. using two different usage conventions for the registers, the scheme can distribute register saves/restores throughout the call graph even in the presence of recursion, indirect calls or separate compilation. a natural and efficient way to pass parameters emerges from this scheme. a separate technique uses data flow analysis to optimize the placement of the save/restore code for registers within individual procedures. the techniques described have been implemented in a production compiler suite. measurements of the effects of these techniques on a set of practical programs are presented and the results analysed.
a new algorithm for partial redundancy elimination based on ssa form. a new algorithm, ssapre, for performing partial redundancy elimination based entirely on ssa form is presented. it achieves optimal code motion similar to lazy code motion [krs94a, ds93], but is formulated independently and does not involve iterative data flow analysis and bit vectors in its solution. it not only exhibits the characteristics common to other sparse approaches, but also inherits the advantages shared by other ssa-based optimization techniques. ssapre also maintains its output in the same ssa form as its input. in describing the algorithm, we state theorems with proofs giving our claims about ssapre. we also give additional description about our practical implementation of ssapre, and analyze and compare its performance with a bit-vector-based implementation of pre. we conclude with some discussion of the implications of this work.
region-based hierarchical operation partitioning for multicluster processors. clustered architectures are a solution to the bottleneck of centralized register files in superscalar and vliw processors. the main challenge associated with clustered architectures is compiler support to effectively partition operations across the available resources on each cluster. in this work, we present a novel technique for clustering operations based on graph partitioning methods. our approach incorporates new methods of assigning weights to nodes and edges within the dataflow graph to guide the partitioner. nodes are assigned weights to reflect their resource usage within a cluster, while a slack distribution method intelligently assigns weights to edges to reflect the cost of inserting moves across clusters. a multilevel graph partitioning algorithm, which globally divides a dataflow graph into multiple parts in a hierarchical manner, uses these weights to efficiently generate estimates for the quality of partitions. we found that our algorithm was able to achieve an average of 20% improvement in dsp kernels and 5% improvement in specint2000 for a four-cluster architecture.
unifying data and control transformations for distributed shared memory machines. we present a unified approach to locality optimization that employs both data and control transformations. data transformations include changing the array layout in memory. control transformations involve changing the execution order of programs. we have developed new techniques for compiler optimizations for distributed shared-memory machines, although the same techniques can be used for sequential machines with a memory hierarchy.our compiler optimizations are based on an algebraic representation of data mappings and a new data locality model. we present a pure data transformation algorithm and an algorithm unifying data and control transformations. while there has been much work on control transformations, the opportunities for data transformations have been largely neglected. in fact, data transformations have the advantage of being applicable to programs that cannot be optimized with control transformations. the unified algorithm, which performs data and control transformations simultaneously, offers improvement over optimizations obtained by applying data and control transformations separately.the experimental results using a set of applications on a parallel machine show that the new optimizations improve performance significantly. these results are further analyzed using locality metrics with instrumentation and simulation.
practicing judo: java under dynamic optimizations. a high-performance implementation of a java virtual machine (jvm) consists of efficient implementation of just-in-time (jit) compilation, exception handling, synchronization mechanism, and garbage collection (gc). these components are tightly coupled to achieve high performance. in this paper, we present some static anddynamic techniques implemented in the jit compilation and exception handling of the microprocessor research lab virtual machine (mrl vm), i.e., lazy exceptions, lazy gc mapping, dynamic patching, and bounds checking elimination. our experiments used ia-32 as the hardware platform, but the optimizations can be generalized to other architectures.
the jade interpreter: a risc interpreter for syntax directed editing. this paper describes key features of an interpreter for a language-based editor. the interpreter unites in a risc framework features which have been used in other domains. the paper examines each feature's integration into the risc framework.