waashk/dblp huggingface dataset:
detection and recovery of endangered variables caused by instruction scheduling. instruction scheduling re-orders and interleaves instruction sequences from different source statements. this impacts the task of a symbolic debugger, which attempts to present the user a picture of program execution that matches the source program. at a breakpoint b, if the value in the run-time location of a variable v may not correspond to the value the user expects v to have, then this variable is endangered at b. this paper describes an approach to detecting and recovering endangered variables caused by instruction scheduling. we measure the effects of instruction scheduling on a symbolic debugger's ability to recover source values at a breakpoint. this paper reports measurements for three c programs from the spec suite and a collection of programs from the numerical recipes, which have been compiled with a variant of a commercial c compiler.
automatic predicate abstraction of c programs. model checking has been widely successful in validating and debugging designs in the hardware and protocol domains. however, state-space explosion limits the applicability of model checking tools, so model checkers typically operate on abstractions of systems. recently, there has been significant interest in applying model checking to software. for infinite-state systems like software, abstraction is even more critical. techniques for abstracting software are a prerequisite to making software model checking a reality. we present the first algorithm to automatically construct a predicate abstraction of programs written in an industrial programming language such as c, and its implementation in a tool &mdash; c2bp. the c2bp tool is part of the slam toolkit, which uses a combination of predicate abstraction, model checking, symbolic reasoning, and iterative refinement to statically check temporal safety properties of programs. predicate abstraction of software has many applications, including detecting program errors, synthesizing program invariants, and improving the precision of program analyses through predicate sensitivity. we discuss our experience applying the c2bp predicate abstraction tool to a variety of problems, ranging from checking that list-manipulating code preserves heap invariants to finding errors in windows nt device drivers.
software pipelining: an effective scheduling technique for vliw machines. the basic idea behind software pipelining was first developed by patel and davidson for scheduling hardware pipe-lines. as instruction-level parallelism made its way into general-purpose computing, it became necessary to automate scheduling. how and whether instructions can be scheduled statically have major ramifications on the design of computer architectures. rau and glaeser were the first to use software pipelining in a compiler for a machine with specialized hardware designed to support software pipelining. in the meantime, trace scheduling was touted to be the scheduling technique of choice for vliw (very long instruction word) machines. the most important contribution from this paper is to show that software pipelining is effective on vliw machines without complicated hardware support. our understanding of software pipelining subsequently deepened with the work of many others. and today, software pipelining is used in all advanced compilers for machines with instruction-level parallelism, none of which, except the intel itanium, relies on any specialized support for software pipelining.this paper shows that software pipelining is an effective and viable scheduling technique for vliw processors. in software pipelining, iterations of a loop in the source program are continuously initiated at constant intervals, before the preceding iterations complete. the advantage of software pipelining is that optimal performance can be achieved with compact object code.this paper extends previous results of software pipelining in two ways: first, this paper shows that by using an improved algorithm, near-optimal performance can be obtained without specialized hardware. second, we propose a hierarchical reduction scheme whereby entire control constructs are reduced to an object similar to an operation in a basic block. with this scheme, all innermost loops, including those containing conditional statements, can be software pipelined. it also diminishes the start-up cost of loops with small number of iterations. hierarchical reduction complements the software pipelining technique, permitting a consistent performance improvement be obtained.the techniques proposed have been validated by an implementation of a compiler for warp, a systolic array consisting of 10 vliw processors. this compiler has been used for developing a large number of applications in the areas of image, signal and scientific processing.
source-level debugging of scalar optimized code. although compiler optimizations play a crucial role in the performance of modern computer systems, debugger technology has lagged behind in its support of optimization. yet debugging the unoptimized translation is often impossible or futile, so handling of code optimizations in the debugger is necessary. but compiler optimizations make it difficult to provide source-level debugger functionality: global optimizations can cause the runtime value of a variable to be inconsistent with the source-level value expected at a breakpoint; such variables are called endangered variables. a debugger must detect and warn the user of endangered variables otherwise the user may draw incorrect conclusions about the program. this paper presents a new algorithm for detecting variables that are endangered due to global scalar optimization. our approach provides more precise classifications of variables and is still simpler than past approaches. we have implemented and evaluated our techniques in the context of the cmcc optimizing c compiler. we describe the compiler extensions necessary to perform the required bookkeeping of compiler optimization. we present measurements of the effect of optimizations on a debugger's ability to present the expected values of variables to the user.
improving balanced scheduling with compiler optimizations that increase instruction-level parallelism. traditional list schedulers order instructions based on an optimistic estimate of the load latency imposed by the hardware and therefore cannot respond to variations in memory latency caused by cache hits and misses on non-blocking architectures. in contrast, balanced scheduling schedules instructions based on an estimate of the amount of instruction-level parallelism in the program. by scheduling independent instructions behind loads based on what the program can provide, rather than what the implementation stipulates in the best case (i.e., a cache hit), balanced scheduling can hide variations in memory latencies more effectively.since its success depends on the amount of instruction-level parallelism in the code, balanced scheduling should perform even better when more parallelism is available. in this study, we combine balanced scheduling with three compiler optimizations that increase instruction-level parallelism: loop unrolling, trace scheduling and cache locality analysis. using code generated for the dec alpha by the multiflow compiler, we simulated a non-blocking processor architecture that closely models the alpha 21164. our results show that balanced scheduling benefits from all three optimizations, producing average speedups that range from 1.15 to 1.40, across the optimizations. more importantly, because of its ability to tolerate variations in load interlocks, it improves its advantage over traditional scheduling. without the optimizations, balanced scheduled code is, on average, 1.05 times faster than that generated by a traditional scheduler; with them, its lead increases to 1.18.
prefetch inection based on hardware monitoring and object metadata. cache miss stalls hurt performance because of the large gap between memory and processor speeds - for example, the popular server benchmark spec jbb2000 spends 45% of its cycles stalled waiting for memory requests on the itanium® 2 processor. traversing linked data structures causes a large portion of these stalls. prefetching for linked data structures remains a major challenge because serial data dependencies between elements in a linked data structure preclude the timely materialization of prefetch addresses. this paper presents mississippi delta (ms delta), a novel technique for prefetching linked data structures that closely integrates the hardware performance monitor (hpm), the garbage collector's global view of heap and object layout, the type-level metadata inherent in type-safe programs, and jit compiler analysis. the garbage collector uses the hpm's data cache miss information to identify cache miss intensive traversal paths through linked data structures, and then discovers regular distances (deltas) between these linked objects. jit compiler analysis injects prefetch instructions using deltas to materialize prefetch addresses.we have implemented ms delta in a fully dynamic profile-guided optimization system: the starjit dynamic compiler [1] and the orp java virtual machine [9]. we demonstrate a 28-29% reduction in stall cycles attributable to the high-latency cache misses targeted by ms delta and a speedup of 11-14% on the cache miss intensive spec jbb2000 benchmark.
grammatical abstraction and incremental syntax analysis in a language-based editor. processors for programming languages and other formal languages typically use a concrete syntax to describe the user's view of a program and an abstract syntax to represent language structures internally. grammatical abstraction is defined as a relationship between two context-free grammars. it formalizes the notion of one syntax being &ldquo;more abstract&rdquo; than another. two variants of abstraction are presented. weak grammatical abstraction supports (i) the construction during lr parsing of an internal representation that is closely related to the abstract syntax and (ii) incremental lr parsing using that internal representation as its base. strong grammatical abstraction tightens the correspondence so that top-down construction of incrementally-parsable internal representations is possible. these results arise from an investigation into language-based editing systems, but apply to any program that transforms a linguistic object from a representation in its concrete syntax to a representation in its abstract syntax or vice versa.
mimic: a fast system/370 simulator. software simulation of one computer on another tends to be slow. traditional simulators typically execute about 100 instructions on the host machine per instruction simulated. newer simulators reduce the expansion factor to about 10, by saving and reusing translations of individual instructions. this paper describes an experimental simulator which takes the progression one step further, translating groups of instructions as a unit. this approach, combined with flow analysis, reduces the expansion factor to about 4. the new simulator simulates system/370 on a risc, namely the ibm rt pc.
efficient and language-independent mobile programs. this paper evaluates the design and implementation of omniware: a safe, efficient, and language-independent system for executing mobile program modules. previous approaches to implementing mobile code rely on either language semantics or abstract machine interpretation to enforce safety. in the former case, the mobile code system sacrifices universality to gain safety by dictating a particular source language or type system. in the latter case, the mobile code system sacrifices performance to gain safety through abstract machine interpretation.omniware uses software fault isolation, a technology developed to provide safe extension code for databases and operating systems, to achieve a unique combination of language-independence and excellent performance. software fault isolation uses only the semantics of the underlying processor to determine whether a mobile code module can corrupt its execution environment. this separation of programming language implementation from program module safety enables our mobile code system to use a radically simplified virtual machine as its basis for portability. we measured the performance of omniware using a suite of four spec92 programs on the pentium, powerpc, mips, and sparc processor architectures. including the overhead for enforcing safety on all four processors, omnivm executed the benchmark programs within 21% as fast as the optimized, unsafe code produced by the vendor-supplied compiler.
efficient interpretation of prolog programs. the paper focuses on three ideas for solving problems with writing interpreters for the logic programming language prolog in prolog and how to combine these ideas to an interpreter for prolog which is both simple and efficient. the resulting interpreter system can be incorporated into a prolog based on warren's abstract machine and built mostly from existing parts of it. the interpreter has been implemented and is used in a prolog system developed at uppsala university.
effective synchronization removal for java. we present a new technique for removing unnecessary synchronization operations from statically compiled java programs. our approach improves upon current efforts based on escape analysis, as it can eliminate synchronization operations even on objects that escape their allocating threads. it makes use of a compact, equivalence-class-based representation that eliminates the need for fixed point operations during the analysis. we describe and evaluate the performance of an implementation in the marmot native java compiler. for the benchmark programs examined, the optimization removes 100% of the dynamic synchronization operations in single-threaded programs, and 0-99% in multi-threaded programs, at a low cost in additional compilation time and code growth.
compiler and runtime support for efficient software transactional memory. programmers have traditionally used locks to synchronize concurrent access to shared data. lock-based synchronization, however, has well-known pitfalls: using locks for fine-grain synchronization and composing code that already uses locks are both difficult and prone to deadlock. transactional memory provides an alternate concurrency control mechanism that avoids these pitfalls and significantly eases concurrent programming. transactional memory language constructs have recently been proposed as extensions to existing languages or included in new concurrent language specifications, opening the door for new compiler optimizations that target the overheads of transactional memory.this paper presents compiler and runtime optimizations for transactional memory language constructs. we present a high-performance software transactional memory system (stm) integrated into a managed runtime environment. our system efficiently implements nested transactions that support both composition of transactions and partial roll back. our jit compiler is the first to optimize the overheads of stm, and we show novel techniques for enabling jit optimizations on stm operations. we measure the performance of our optimizations on a 16-way smp running multi-threaded transactional workloads. our results show that these techniques enable transactional memory's performance to compete with that of well-tuned synchronization.
interprocedural conditional branch elimination. the existence of statically detectable correlation among conditional branches enables their elimination, an optimization that has a number of benefits. this paper presents techniques to determine whether an interprocedural execution path leading to a conditional branch exists along which the branch outcome is known at compile time, and then to eliminate the branch along this path through code restructuring. the technique consists of a demand driven interprocedural analysis that determines whether a specific branch outcome is correlated with prior statements or branch outcomes. the optimization is performed using a code restructuring algorithm that replicates code to separate out the paths with correlation. when the correlated path is affected by a procedure call, the restructuring is based on procedure entry splitting and exit splitting. the entry splitting transformation creates multiple entries to a procedure, and the exit splitting transformation allows a procedure to return control to one of several return points in the caller. our technique is efficient in that the correlation detection is demand driven, thus avoiding exhaustive analysis of the entire program, and the restructuring never increases the number of operations along a path through an interprocedural control flow graph. we describe the benefits of our interprocedural branch elimination optimization (icbe). our experimental results show that, for the same amount of code growth, the estimated reduction in executed conditional branches is about 2.5 times higher with the icbe optimization than when only intraprocedural conditional branch elimination is applied.
using integer sets for data-parallel program analysis and optimization. in this paper, we describe our experience with using an abstract integer-set framework to develop the rice dhpf compiler, a compiler for high performance fortran. we present simple, yet general formulations of the major computation partitioning and communication analysis tasks as well as a number of important optimizations in terms of abstract operations on sets of integer tuples. this approach has made it possible to implement a comprehensive collection of advanced optimizations in dhpf, and to do so in the context of a more general computation partitioning model than previous compilers. one potential limitation of the approach is that the underlying class of integer set problems is fundamentally unable to represent hpf data distributions on a symbolic number of processors. we describe how we extend the approach to compile codes for a symbolic number of processors, without requiring any changes to the set formulations for the above optimizations. we show experimentally that the set representation is not a dominant factor in compile times on both small and large codes. finally, we present preliminary performance measurements to show that the generated code achieves good speedups for a few benchmarks. overall, we believe we are the first to demonstrate by implementation experience that it is practical to build a compiler for hpf using a general and powerful integer-set framework.
garbage collection and local variable type-precision and liveness in java virtual machines. full precision in garbage collection implies retaining only those heap allocated objects that will actually be used in the future. since full precision is not computable in general, garbage collectors use safe (i.e., conservative) approximations such as reachability from a set of root references. ambiguous roots collectors (commonly called "conservative") can be overly conservative because they overestimate the root set, and thereby retain unexpectedly large amounts of garbage. we consider two more precise collection schemes for java virtual machines (jvms). one uses a type analysis to obtain a type-precise root set (only those variables that contain references); the other adds a live variable analysis to reduce the root set to only the live reference variables. even with the java programming language's strong typing, it turns out that the jvm specification has a feature that makes type-precise root sets difficult to compute. we explain the problem and ways in which it can be solved.our experimental results include measurements of the costs of the type and liveness analyses at load time, of the incremental benefits at run time of the liveness analysis over the type analysis alone, and of various map sizes and counts. we find that the liveness analysis often produces little or no improvement in heap size, sometimes modest improvements, and occasionally the improvement is dramatic. while further study is in order, we conclude that the main benefit of the liveness analysis is preventing bad surprises.
related field analysis. we present an extension of field analysis (sec [4]) called related field analysis which is a general technique for proving relationships between two or more fields of an object. we demonstrate the feasibility and applicability of related field analysis by applying it to the problem of removing array bounds checks. for array bounds check removal, we define a pair of related fields to be an integer field and an array field for which the integer field has a known relationship to the length of the array. this related field information can then be used to remove array bounds checks from accesses to the array field. our results show that related field analysis can remove an average of 50% of the dynamic array bounds checks on a wide range of applications. we describe the implementation of related field analysis in the swift optimizing compiler for java, as well as the optimizations that exploit the results of related field analysis.
load-reuse analysis: design and evaluation. load-reuse analysis finds instructions that repeatedly access the same memory location. this location can be promoted to a register, eliminating redundant loads by reusing the results of prior memory accesses. this paper develops a load-reuse analysis and designs a method for evaluating its precision.in designing the analysis, we aspire for completeness---the goal of exposing all reuse that can be harvested by a subsequent program transformation. for register promotion, a suitable transformation is partial redundancy elimination (pre). to approach the ideal goal of pre-completeness, the load-reuse analysis is phrased as a data-flow problem on a program representation that is path-sensitive, as it detects reuse even when it originates in a different instruction along each control flow path. furthermore, the analysis is comprehensive, as it treats scalar, array and pointer-based loads uniformly.in evaluating the analysis, we compare it with an ideal analysis. by observing the run-time stream of memory references, we collect all pre-exploitable reuse and treat it as the ideal analysis performance. to compare the (static) load-reuse analysis with the (dynamic) ideal reuse, we use an estimator algorithm that computes, given a data-flow solution and a program profile, the dynamic amount of reuse detected by the analysis. we developed a family of estimators that differ in how well they bound the profiling error inherent in the edge profile. by bounding the error, the estimators offer a precise and practical method for determining the run-time optimization benefit.our experiments show that about 55% of loads executed in spec95 exhibit reuse. of those, our analysis exposes about 80%.
on slicing programs with jump statements. program slices have potential uses in many software engineering applications. traditional slicing algorithms, however, do not work correctly on programs that contain explicit jump statements. two similar algorithms were proposed recently to alleviate this problem. both require the flowgraph and the program dependence graph of the program to be modified. in this paper, we propose an alternative algorithm that leaves these graphs intact and uses a separate graph to store the additional required information. we also show that this algorithm permits an extremely efficient, conservative adaptation for use with programs that contain only &ldquo;structured&rdquo; jump statements.