waashk/dblp huggingface dataset:
a fresh look at optimizing array bound checking. this paper describes techniques for optimizing range checks performed to detect array bound violations. in addition to the elimination of range checks, the optimizations discussed in this paper also reduce the overhead due to range checks that cannot be eliminated by compile-time analysis. the optimizations reduce the program execution time and the object code size through elimination of redundant checks, propagation of checks out of loops, and combination of multiple checks into a single check. a minimal control flow graph (mcfg) is constructed using which the minimal amount of data flow information required for range check optimizations is computed. the range check optimizations are performed using the mcfg rather the cfg for the entire program. this allows the global range check optimizations to be performed efficiently since the mcfg is significantly smaller than the cfg. any array bound violation that is detected by a program with all range checks included, will also be detected by the program after range check optimization and vice versa. even though the above optimizations may appear to be similar to traditional code optimizations, similar reduction in the number of range checks executed can not be achieved by a traditional code optimizer. experimental results indicate that the number of range checks performed in executing a program is greatly reduced using the above techniques.
register allocation via clique separators. although graph coloring is widely recognized as an effective technique for global register allocation, the overhead can be quite high, not only in execution time but also in memory, as the size of the interference graph needed in coloring can become quite large. in this paper, we present an algorithm based upon a result by r. tarjan regarding the colorability of graphs which are decomposable using clique separators, that improves on the overhead of coloring. the algorithm first partitions program code into code segments using the notion of clique separators. the interference graphs for the code partitions are next constructed one at a time and colored independently. the colorings for the partitions are combined to obtain a register allocation for the program code. the technique presented is both efficient in space and time because the graph for only a single code segment needs to be constructed and colored at any given point in time. the partitioning of a graph using clique separators increases the likelihood of obtaining a coloring without spilling and hence an efficient allocation of registers for the program. for straight line code an optimal allocation for the entire program code can be obtained from optimal allocations for individual code segments. in the presence of branches, optimal allocation along one execution path and a near optimal allocation along alternative paths can be potentially obtained. since the algorithm is highly efficient, it eliminates the need for a local register allocation phase.
free-me: a static analysis for automatic individual object reclamation. garbage collection has proven benefits, including fewer memory related errors and reduced programmer effort. garbage collection, however, trades space for time. it reclaims memory only when it is invoked: invoking it more frequently reclaims memory quickly, but incurs a significant cost; invoking it less frequently fills memory with dead objects. in contrast, explicit memory management provides prompt low cost reclamation, but at the expense of programmer effort.this work comes closer to the best of both worlds by adding novel compiler and runtime support for compiler inserted frees to a garbage-collected system. the compiler's free-me analysis identifies when objects become unreachable and inserts calls to free. it combines a lightweight pointer analysis with liveness information that detects when short-lived objects die. our approach differs from stack and region allocation in two crucial ways. first, it frees objects incrementally exactly when they become unreachable, instead of based on program scope. second, our system does not require allocation-site lifetime homogeneity, and thus frees objects on some paths and not on others. it also handles common patterns: it can free objects in loops and objects created by factory methods.we evaluate free() variations for free-list and bump-pointer allocators. explicit freeing improves performance by promptly reclaiming objects and reducing collection load. compared to marksweep alone, free-me cuts total time by 22% on average, collector time by 50% to 70%, and allows programs to run in 17% less memory. this combination retains the software engineering benefits of garbage collection while increasing space efficiency and improving performance, and thus is especially appealing for real-time and space constrained systems.
a system and language for building system-specific, static analyses. this paper presents a novel approach to bug-finding analysis and an implementation of that approach. our goal is to find as many serious bugs as possible. to do so, we designed a flexible, easy-to-use extension language for specifying analyses and an efficent algorithm for executing these extensions. the language, metal, allows the users of our system to specify a broad class of analyses in terms that resemble the intuitive description of the rules that they check. the system, xgcc, executes these analyses efficiently using a context-sensitive, interprocedural analysis. our prior work has shown that the approach described in this paper is effective: it has successfully found thousands of bugs in real systems code. this paper describes the underlying system used to achieve these results. we believe that our system is an effective framework for deploying new bug-finding analyses quickly and easily.
combining events and threads for scalable network services implementation and evaluation of monadic, application-level concurrency primitives. this paper proposes to combine two seemingly opposed programming models for building massively concurrent network services: the event-driven model and the multithreaded model. the result is a hybrid design that offers the best of both worlds--the ease of use and expressiveness of threads and the flexibility and performance of events. this paper shows how the hybrid model can be implemented entirely at the application level using concurrency monads in haskell, which provides type-safe abstractions for both events and threads. this approach simplifies the development of massively concurrent software in a way that scales to real-world network services. the haskell implementation supports exceptions, symmetrical multiprocessing, software transactional memory, asynchronous i/o mechanisms and application-level network protocol stacks. experimental results demonstrate that this monad-based approach has good performance: the threads are extremely lightweight (scaling to ten million threads), and the i/o performance compares favorably to that of linux nptl. tens of thousands of simultaneous, mostly-idle client connections. such massively-concurrent programs are difficult to implement, especially when other requirements, such as high performance and strong security, must also be met.
combining region inference and garbage collection. this paper describes a memory discipline that combines region-based memory management and copying garbage collection by extending cheney's copying garbage collection algorithm to work with regions. the paper presents empirical evidence that region inference very significantly reduces the number of garbage collections; and evidence that the fastest execution is obtained by using regions alone, without garbage collection. the memory discipline is implemented for standard ml in the ml kit compiler and measurements show that for a variety of benchmark programs, code generated by the compiler is as efficient, both with respect to execution time and memory usage, as programs compiled with standard ml of new jersey, another state-of-the-art standard ml compiler.
dynamic variables. most programming languages use static scope rules for associating uses of identifiers with their declarations. static scope helps catch errors at compile time, and it can be implemented efficiently. some popular languages&mdash;perl, tel, tex, and postscript&mdash;offer dynamic scope, because dynamic scope works well for variables that &ldquo;customize&rdquo; the execution environment, for example. programmers must simulate dynamic scope to implement this kind of usage in statically scoped languages. this paper describes the design and implementation of imperative language constructs for introducing and referencing dynamically scoped variables&mdash;dynamic variables for short. the design is a minimalist one, because dynamic variables are best used sparingly, much like exceptions. the facility does, however, cater to the typical uses for dynamic scope, and it provides a cleaner mechanism for so-called thread-local variables. a particularly simple implementation suffices for languages without exception handling. for languages with exception handling, a more efficient implementation builds on existing compiler infrastructure. exception handling can be viewed as a control construct with dynamic scope. likewise, dynamic variables are a data construct with dynamic scope.
relaxing simd control flow constraints using loop transformations. many loop nests in scientific codes contain a parallelizable outer loop but have an inner loop for which the number of iterations varies between different iterations of the outer loop. when running this kind of loop nest on a simd machine, the simd-inherent restriction to single program counter common to all processors will cause a performance degradation relative to comparable mimd implementations. this problem is not due to limited parallelism or bad load balance, it is merely a problem of control flow. this paper presents a loop transformation, which we call loop flattening, that overcomes this limitation by letting each processor advance to the next loop iteration containing useful computation, if there is such an iteration for the given processor. we study a concrete example derived from a molecular dynamics code and compare performance results for flattened and unflattened versions of this kernel on two simd machines, the cm-2 and the decmpp 12000. we then evaluate loop flattening from the compiler's perspective in terms of applicability, cost, profitability, and safety. we conclude with arguing that loop flattening, whether performed by the programmer or by the compiler, introduces negligible overhead and can significantly improve the performance of scientific codes for solving irregular problems.
optimizing memory transactions. atomic blocks allow programmers to delimit sections of code as 'atomic', leaving the language's implementation to enforce atomicity. existing work has shown how to implement atomic blocks over word-based transactional memory that provides scalable multi-processor performance without requiring changes to the basic structure of objects in the heap. however, these implementations perform poorly because they interpose on all accesses to shared memory in the atomic block, redirecting updates to a thread-private log which must be searched by reads in the block and later reconciled with the heap when leaving the block.this paper takes a four-pronged approach to improving performance: (1) we introduce a new 'direct access' implementation that avoids searching thread-private logs, (2) we develop compiler optimizations to reduce the amount of logging (e.g. when a thread accesses the same data repeatedly in an atomic block), (3) we use runtime filtering to detect duplicate log entries that are missed statically, and (4) we present a series of gc-time techniques to compact the logs generated by long-running atomic blocks.our implementation supports short-running scalable concurrent benchmarks with less than 50\% overhead over a non-thread-safe baseline. we support long atomic blocks containing millions of shared memory accesses with a 2.5-4.5x slowdown.
efficient procedure mapping using cache line coloring. as the gap between memory and processor performance continues to widen, it becomes increasingly important to exploit cache memory eflectively. both hardware and aoftware approaches can be explored to optimize cache performance. hardware designers focus on cache organization issues, including replacement policy, associativity, line size and the resulting cache access time. software writers use various optimization techniques, including software prefetching, data scheduling and code reordering. our focus is on improving memory usage through code reordering compiler techniques.in this paper we present a link-time procedure mapping algorithm which can significantly improve the eflectiveness of the instruction cache. our algorithm produces an improved program layout by performing a color mapping of procedures to cache lines, taking into consideration the procedure size, cache size, cache line size, and call graph. we use cache line coloring to guide the procedure mapping, indicating which cache lines to avoid when placing a procedure in the program layout. our algorithm reduces on average the instruction cache miss rate by 40% over the original mapping and by 17% over the mapping algorithm of pettis and hansen [12].
using static single assignment form to improve flow-insensitive pointer analysis. a pointer-analysis algorithm can be either flow-sensitive or flow-insensitive. while flow-sensitive analysis usually provides more precise information, it is also usually considerably more costly in terms of time and space. the main contribution of this paper is the presentation of another option in the form of an algorithm that can be 'tuned' to provide a range of results that fall between the results of flow-insensitive and flow-sensitive analysis. the algorithm combines a flow-insensitive pointer analysis with static single assignment (ssa) form and uses an iterative process to obtain progressively better results.
incremental generation of parsers. an lr-based parser generator for arbitrary context-free grammars that generates parsers by need and handles modifications to its input grammar by updating the parser it has generated so far is described. the need for these techniques is discussed in the context of interactive language definition environments. all required algorithms are presented. measurements are given comparing their performance with that of conventional techniques.
a practical flow-sensitive and context-sensitive c and c++ memory leak detector. this paper presents a static analysis tool that can automatically find memory leaks and deletions of dangling pointers in large c and c++ applications.we have developed a type system to formalize a practical ownership model of memory management. in this model, every object is pointed to by one and only one owning pointer, which holds the exclusive right and obligation to either delete the object or to transfer the right to another owning pointer. in addition, a pointer-typed class member field is required to either always or never own its pointee at public method boundaries. programs satisfying this model do not leak memory or delete the same object more than once.we have also developed a flow-sensitive and context-sensitive algorithm to automatically infer the likely ownership interfaces of methods in a program. it identifies statements inconsistent with the model as sources of potential leaks or double deletes. the algorithm is sound with respect to a large subset of the c and c++ language in that it will report all possible errors. it is also practical and useful as it identifies those warnings likely to correspond to errors and helps the user understand the reported errors by showing them the assumed method interfaces.our techniques are validated with an implementation of a tool we call clouseau. we applied clouseau to a suite of applications: two web servers, a chat client, secure shell tools, executable object manipulation tools, and a compiler. the tool found a total of 134 serious memory errors in these applications. the tool analyzes over 50k lines of c++ code in about 9 minutes on a 2 ghz pentium 4 machine and over 70k lines of c code in just over a minute.
linear-time subtransitive control flow analysis. we present a linear-time algorithm for bounded-type programs that builds a directed graph whose transitive closure gives exactly the results of the standard (cubic-time) control-flow analysis (cfa) algorithm. our algorithm can be used to list all functions calls from all call sites in (optimal) quadratic time. more importantly, it can be used to give linear-time algorithms for cfa-consuming applications such as:&bull; effects analysis: find the side-effecting expressions in a program.&bull; k-limited cfa: for each call-site, list the functions if there are only a few of them (&le; k) and otherwise output "many".&bull; called-once analysis: identify all functions called from only one call-site.
demand-driven pointer analysis. known algorithms for pointer analysis are &ldquo;global&rdquo; in the sense that they perform an exhaustive analysis of a program or program component. in this paper we introduce a demand-driven approach for pointer analysis. specifically, we describe a demand-driven flow-insensitive, subset-based, con text-insensitive points-to analysis. given a list of pointer variables (a query), our analysis performs just enough computation to determine the points-to sets for these query variables. using deductive reachability formulations of both the exhaustive and the demand-driven analyses, we prove that our algorithm is correct. we also show that our analysis is optimal in the sense that it does not do more work than necessary. we illustrate the feasibility and efficiency of our analysis with an implementation of demand-driven points-to analysis for computing the call-graphs of c programs with function pointers. the performance of our system varies substantially across benchmarks - the main factor is how much of the points-to graph must be computed to determine the call-graph. for some benchmarks, only a small part of the points-to graph is needed (e.g pouray emacs and gcc), and here we see more than a 10x speedup. for other benchmarks (e.g. burlap and gimp), we need to compute most (> 95%) of the points-to graph, and here the demand-driven algorithm is considerably slower, because using the demand-driven algorithm is a slow method of computing the full points-to graph.
ultra-fast aliasing analysis using cla: a million lines of c code in a second. we describe the design and implementation of a system for very fast points-to analysis. on code bases of about million lines of unpreprocessed c code, our system performs field-based andersen-style points-to analysis in less than a second and uses less than 10mb of memory. our two main contributions are a database-centric analysis architecture called compile-link-analyze (cla), and a new algorithm for implementing dynamic transitive closure. our points-to analysis system is built into a forward data-dependence analysis tool that is deployed within lucent to help with consistent type modifications to large legacy c code bases.
the university of washington illustrating compiler. the university of washington illustrating compiler (uwpi) automatically illustrates the data structures used in simple programs written in a subset of pascal2. a uwpi user submits a program to uwpi, and can then watch a graphical display show time varying illustrations of the data structures and program source code. uwpi uses the information latent in the program to determine how to illustrate the program. uwpi infers the abstract data types directly from the declarations and operations used in the source program, and then lays out the illustration in a natural way by instantiating well-known layouts for the abstracts types. uwpi solves program illustration using compile-time pattern matching and type inferencing to link anticipated execution events to display events, rather than relying on user assistance or specialized programming techniques. uwpi has been used to automatically illustrate didactic sorting and searching examples, and can be used to help teach basic data structures, or to help when debugging programs.
type analysis of prolog using type graphs. type analysis of prolog is of primary importance for high-performance compilers, since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates to name a few. however, these optimizations often require a sophisticated type inference system capable of inferring disjunctive and recursive types and hence expensive in computation time. the purpose of this paper is to describe a type analysis system for prolog based on abstract interpretation and type graphs (i.e. disjunctive rational trees) with this functionality. the system (about 15,000 lines of c) consists of the combination of a generic fixpoint algorithm, a generic pattern domain, and a type graph domain. the main contribution of the paper is to show that this approach can be engineered to be practical for medium-sized programs without sacrificing accuracy. the main technical contributions to achieve this result are (1) a novel widening operator for type graphs which appears to be accurate and effective in keeping the sizes of the graphs, and hence the computation time, reasonably small; (2) the use of the generic pattern domain to obtain a compact representation of equality constraints between subterms and to factor out sure structural information.
race checking by context inference. software model checking has been successful for sequential programs, where predicate abstraction offers suitable models, and counterexample-guided abstraction refinement permits the automatic inference of models. when checking concurrent programs, we need to abstract threads as well as the contexts in which they execute. stateless context models, such as predicates on global variables, prove insufficient for showing the absence of race conditions in many examples. we therefore use richer context models, which combine (1) predicates for abstracting data state, (2) control flow quotients for abstracting control state, and (3) counters for abstracting an unbounded number of threads. we infer suitable context models automatically by a combination of counterexample-guided abstraction refinement, bisimulation minimization, circular assume-guarantee reasoning, and parametric reasoning about an unbounded number of threads. this algorithm, called circ, has been implemented in blast and succeeds in checking many examples of nesc code for data races. in particular, blast proves the absence of races in several cases where previous race checkers give false positives.
the embedded machine: predictable, portable real-time code. the embedded machine is a virtual machine that mediates in real time the interaction between software processes and physical processes. it separates the compilation of embedded programs into two phases. the first phase, the platform-independent compiler phase, generates e code (code executed by the embedded machine), which supervises the timing, not the scheduling of, application tasks relative to external events such as clock ticks and sensor interrupts. e code is portable and, given an input behavior, exhibits predictable (i.e., deterministic) timing and output behavior. the second phase, the platform-dependent compiler phase, checks the time safety of the e code, that is, whether platform performance (determined by the hardware) and platform utilization (determined by the scheduler of the operating system) enable its timely execution. we have used the embedded machine to compile and execute high-performance control applications written in giotto, such as the flight control system of an autonomous model helicopter.