waashk/dblp huggingface dataset:
a new framework for debugging globally optimized code. with an increasing number of executable binaries generated by optimizing compilers today, providing a clear and correct source-level debugger for programmers to debug optimized code has become a necessity. in this paper, a new framework for debugging globally optimized code is proposed. this framework consists of a new code location mapping scheme, a data location tracking scheme, and an emulation-based forward recovery model. by taking over the control early and emulating instructions selectively, the debugger can preserve and gather the required program state for the recovery of expected variable values at source breakpoints. the framework has been prototyped in the impact compiler and gdb-4.16. preliminary experiments conducted on several spec95 integer programs have yielded encouraging results. the extra time needed for the debugger to calculate the limits of the emulated region and to emulate instructions is hardly noticeable, while the increase in executable file size due to the extra debug information is on average 76% of that of the executable file with no debug information.
compile-time dynamic voltage scaling settings: opportunities and limits. with power-related concerns becoming dominant aspects of hardware and software design, significant research effort has been devoted towards system power minimization. among run-time power-management techniques, dynamic voltage scaling (dvs) has emerged as an important approach, with the ability to provide significant power savings. dvs exploits the ability to control the power consumption by varying a processor's supply voltage (v) and clock frequency (f). dvs controls energy by scheduling different parts of the computation to different (v, f) pairs; the goal is to minimize energy while meeting performance needs. although processors like the intel xscale and transmeta crusoe allow software dvs control, such control has thus far largely been used at the process/task level under operating system control. this is mainly because the energy and time overhead for switching dvs modes is considered too large and difficult to manage within a single program.in this paper we explore the opportunities and limits of compile-time dvs scheduling. we derive an analytical model for the maximum energy savings that can be obtained using dvs given a few known program and processor parameters. we use this model to determine scenarios where energy consumption benefits from compile-time dvs and those where there is no benefit. the model helps us extrapolate the benefits of compile-time dvs into the future as processor parameters change. we then examine how much of these predicted benefits can actually be achieved through optimal settings of dvs modes. this is done by extending the existing mixed-integer linear program (milp) formulation for this problem by accurately accounting for dvs energy switching overhead, by providing finer-grained control on settings and by considering multiple data categories in the optimization. overall, this research provides a comprehensive view of compile-time dvs management, providing both practical techniques for its immediate deployment as well theoretical bounds for use into the future.
spl: a language and compiler for dsp algorithms. we discuss the design and implementation of a compiler that translates formulas representing signal processing transforms into efficient c or fortran programs. the formulas are represented in a language that we call spl, an acronym from signal processing language. the compiler is a component of the spiral system which makes use of formula transformations and intelligent search strategies to automatically generate optimized digital signal processing (dsp) libraries. after a discussion of the translation and optimization techniques implemented in the compiler, we use spl formulations of the fast fourier transform (fft) to evaluate the compiler. our results show that spiral, which can be used to implement many classes of algorithms, produces programs that perform as well as &ldquo;hard-wired&rdquo; systems like fftw.
a serializability violation detector for shared-memory server programs. we aim to improve reliability of multithreaded programs by proposing a dynamic detector that detects potentially erroneous program executions and their causes. we design and evaluate a serializability violation detector (svd) that has two unique goals: (i) triggering automatic recovery from erroneous executions using backward error recovery (ber), or simply alerting users that a software error may have occurred; and (ii) helping debug programs by revealing causes of error symptoms.two properties of svd help in achieving these goals. first, to detect only erroneous executions, svd checks serializability of atomic regions, which are code regions that need to be executed atomically. second, to improve usability, svd does not require a priori annotations of atomic regions; instead, svd approximates them using a heuristic. experimental results on three widely-used multithreaded server programs show that svd finds real bugs and reports modest false positives. the goal of this paper is to develop a detector suitable for (i) ber-based avoidance of erroneous program executions; and (ii) alerting users as software errors occur. we argue that such a detector should have the following two properties.
safety checking of machine code. we show how to determine statically whether it is safe for untrusted machine code to be loaded into a trusted host system. our safety-checking technique operates directly on the untrusted machine-code program, requiring only that the initial inputs to the untrusted program be annotated with typestate information and linear constraints. this approach opens up the possibility of being able to certify code produced by any compiler from any source language, which gives the code producers more freedom in choosing the language in which they write their programs. it eliminates the dependence of safety on the correctness of the compiler because the final product of the compiler is checked. it leads to the decoupling of the safety policy from the language in which the untrusted code is written, and consequently, makes it possible for safety checking to be performed with respect to an extensible set of safety properties that are specified on the host side. we have implemented a prototype safety checker for sparc machine-language programs, and applied the safety checker to several examples. the safety checker was able to either prove that an example met the necessary safety conditions, or identify the places where the safety conditions were violated. the checking times ranged from less than a second to 14 seconds on an ultrasparc machine.
verifying safety properties using separation and heterogeneous abstractions. in this paper, we show how separation (decomposing a verification problem into a collection of verification subproblems) can be used to improve the efficiency and precision of verification of safety properties. we present a simple language for specifying separation strategies for decomposing a single verification problem into a set of subproblems. (the strategy specification is distinct from the safety property specification and is specified separately.) we present a general framework of heterogeneous abstraction that allows different parts of the heap to be abstracted using different degrees of precision at different points during the analysis. we show how the goals of separation (i.e., more efficient verification) can be realized by first using a separation strategy to transform (instrument) a verification problem instance (consisting of a safety property specification and an input program), and by then utilizing heterogeneous abstraction during the verification of the transformed verification problem.
improving performance by branch reordering. the conditional branch has long been considered an expensive operation. the relative cost of conditional branches has increased as recently designed machines are now relying on deeper pipelines and higher multiple issue. reducing the number of conditional branches executed can often result in a substantial performance benefit. this paper describes a code-improving transformation to reorder sequences of conditional branches. first, sequences of branches that can be reordered are detected in the control flow. second, profiling information is collected to predict the probability that each branch will transfer control out of the sequence. third, the cost of performing each conditional branch is estimated. fourth, the most beneficial ordering of the branches based on the estimated probability and cost is selected. the most beneficial ordering often included the insertion of additional conditional branches that did not previously exist in the sequence. finally, the control flow is restructured to refflect the new ordering. the results of applying the transformation were significant reductions in the dynamic number of instructions and branches, as well as decreases in execution time.
inc: a language for incremental computations. an incremental computation is one that is performed repeatedly on nearly identical inputs. incremental computations occur naturally in many environments, such as compilers, language-based editors, spreadsheets, and formatters. this article describes a proposed tool for making it easy to write incremental programs. the tool consists of a programming language, inc, and a set of compile-time transformations for the primitive elements of inc. a programmer defines an algorithm in inc without regard to efficient incremental execution. the transformations automatically convert this algorithm into an efficient incremental algorithm. inc is a functional language. the implementation of an inc program is a network of processes. each inc function is transformed into a process that receives and transmits messages describing changes to its inputs and outputs. we give an overview to the language and illustrate the incremental techniques employed by inc. we present the static and incremental complexity bounds for the primitive inc functions. we also present some example programs illustrating inc's flexibility.
transforming loops to recursion for multi-level memory hierarchies. recently, there have been several experimental and theoretical results showing significant performance benefits of recursive algorithms on both multi-level memory hierarchies and on shared-memory systems. in particular, such algorithms have the data reuse characteristics of a blocked algorithm that is simultaneously blocked at many different levels. most existing applications, however, are written using ordinary loops. we present a new compiler transformation that can be used to convert loop nests into recursive form automatically. we show that the algorithm is fast and effective, handling loop nests with arbitrary nesting and control flow. the transformation achieves substantial performance improvements for several linear algebra codes even on a current system with a two level cache hierarchy. as a side-effect of this work, we also develop an improved algorithm for transitive dependence analysis (a powerful technique used in the recursion transformation and other loop transformations)that is much faster than the best previously known algorithm in practice.
pointer analysis for programs with structures and casting. type casting allows a program to access an object as if it had a type different from its declared type. this complicates the design of a pointer-analysis algorithm that treats structure fields as separate objects; therefore, some previous pointer-analysis algorithms "collapse" a structure into a single variable. the disadvantage of this approach is that it can lead to very imprecise points-to information. other algorithms treat each field as a separate object based on its offset and size. while this approach leads to more precise results, the results are not portable because the memory layout of structures is implementation dependent.this paper first describes the complications introduced by type casting, then presents a tunable pointer-analysis framework for handling structures in the presence of casting. different instances of this framework produce algorithms with different levels of precision, portability, and efficiency. experimental results from running our implementations of four instances of this framework show that (i) it is important to distinguish fields of structures in pointer analysis, but (ii) making conservative approximations when casting is involved usually does not cost much in terms of time, space, or the precision of the results.
a comparison of empirical and model-driven optimization. empirical program optimizers estimate the values of key optimization parameters by generating different program versions and running them on the actual hardware to determine which values give the best performance. in contrast, conventional compilers use models of programs and machines to choose these parameters. it is widely believed that model-driven optimization does not compete with empirical optimization, but few quantitative comparisons have been done to date. to make such a comparison, we replaced the empirical optimization engine in atlas (a system for generating a dense numerical linear algebra library called the blas) with a model-driven optimization engine that used detailed models to estimate values for optimization parameters, and then measured the relative performance of the two systems on three different hardware platforms. our experiments show that model-driven optimization can be surprisingly effective, and can generate code whose performance is comparable to that of code generated by empirical optimizers for the blas.
improved spill code generation for software pipelined loops. software pipelining is a loop scheduling technique that extracts parallelism out of loops by overlapping the execution of several consecutive iterations. due to the overlapping of iterations, schedules impose high register requirements during their execution. a schedule is valid if it requires at most the number of registers available in the target architecture. if not, its register requirements have to be reduced either by decreasing the iteration overlapping or by spilling registers to memory. in this paper we describe a set of heuristics to increase the quality of register-constrained modulo schedules. the heuristics decide between the two previous alternatives and define criteria for effectively selecting spilling candidates. the heuristics proposed for reducing the register pressure can be applied to any software pipelining technique. the proposals are evaluated using a register-conscious software pipeliner on a workbench composed of a large set of loops from the perfect club benchmark and a set of processor configurations. proposals in this paper are compared against a previous proposal already described in the literature. for one of these processor configurations and the set of loops that do not fit in the available registers (32), a speed-up of 1.68 and a reduction of the memory traffic by a factor of 0.57 are achieved with an affordable increase in compilation time. for all the loops, this represents a speed-up of 1.38 and a reduction of the memory traffic by a factor of 0.7.
timestamped whole program path representation and its applications. a whole program path (wpp) is a complete control flow trace of a program's execution. recently larus [18] showed that although wpp is expected to be very large (100's of mbytes), it can be greatly compressed (to 10's of mbytes) and therefore saved for future analysis. while the compression algorithm proposed by larus is highly effective, the compression is accompanied with a loss in the ease with which subsets of information can be accessed. in particular, path traces pertaining to a particular function cannot generally be obtained without examining the entire compressed wpp representation. to solve this problem we advocate the application of compaction techniques aimed at providing easy access to path traces on a per function basis. we present a wpp compaction algorithm in which the wpp is broken in to path traces corresponding to individual function calls. all of the path traces for a given function are stored together as a block. ability to construct the complete wpp from individual path traces is preserved by maintaining a dynamic call graph. the compaction is achieved by eliminating redundant path traces that result from different calls to a function and by replacing a sequence of static basic block ids that correspond to a dynamic basic block by a single id. we transform a compacted wpp representation into a timestamped wpp (twpp) representation in which the path traces are organized from the perspective of dynamic basic blocks. twpp representation also offers additional opportunities for compaction. experiments show that our algorithm compacts the wpps by factors ranging from 7 to 64. at the same time information is organized in a highly accessible form which speeds up the responses to queries requesting the path traces of a given function by over 3 orders of magnitude.
cost effective dynamic program slicing. although dynamic program slicing was first introduced to aid in user level debugging, applications aimed at improving software quality, reliability, security, and performance have since been identified as candidates for using dynamic slicing. however, the dynamic dependence graph constructed to compute dynamic slices can easily cause slicing algorithms to run out of memory for realistic program runs. in this paper we present the design and evaluation of a cost effective dynamic program slicing algorithm. this algorithm is based upon a dynamic dependence graph representation that is highly compact and rapidly traversable. thus, the graph can be held in memory and dynamic slices can be quickly computed. a compact representation is derived by recognizing that all dynamic dependences (data and control) need not be individually represented. we identify sets of dynamic dependence edges between a pair of statements that can share a single representative edge. we further show that the dependence graph can be transformed in a manner that increases sharing and sharing can be performed even in the presence of aliasing. experiments show that transformed dynamic dependence graphs explicitly represent only 6% of the dependence edges present in the full dynamic dependence graph. when the full graph sizes range from 0.84 to 1.95 gigabytes in size, our compacted graphs range from 20 to 210 megabytes in size. average slicing times for our algorithm range from 1.74 to 36.25 seconds across several benchmarks from specint2000/95.
pruning dynamic slices with confidence. given an incorrect value produced during a failed program run (e.g., a wrong output value or a value that causes the program to crash), the backward dynamic slice of the value very frequently captures the faulty code responsible for producing the incorrect value. although the dynamic slice often contains only a small percentage of the statements executed during the failed program run, the dynamic slice can still be large and thus considerable effort may be required by the programmer to locate the faulty code.in this paper we develop a strategy for pruning the dynamic slice to identify a subset of statements in the dynamic slice that are likely responsible for producing the incorrect value. we observe that some of the statements used in computing the incorrect value may also have been involved in computing correct values (e.g., a value produced by a statement in the dynamic slice of the incorrect value may also have been used in computing a correct output value prior to the incorrect value). for each such executed statement in the dynamic slice, using the value profiles of the executed statements, we compute a confidence value ranging from 0 to 1 - a higher confidence value corresponds to greater likelihood that the execution of the statement produced a correct value. given a failed run involving execution of a single error, we demonstrate that the pruning of a dynamic slice by excluding only the statements with the confidence value of 1 is highly effective in reducing the size of the dynamic slice while retaining the faulty code in the slice. our experiments show that the number of distinct statements in a pruned dynamic slice are 1.79 to 190.57 times less than the full dynamic slice. confidence values also prioritize the statements in the dynamic slice according to the likelihood of them being faulty. we show that examining the statements in the order of increasing confidence values is an effective strategy for reducing the effort of fault location.
array regrouping and structure splitting using whole-program reference affinity. while the memory of most machines is organized as a hierarchy, program data are laid out in a uniform address space. this paper defines a model of reference affinity, which measures how close a group of data are accessed together in a reference trace. it proves that the model gives a hierarchical partition of program data. at the top is the set of all data with the weakest affinity. at the bottom is each data element with the strongest affinity. based on the theoretical model, the paper presents k-distance analysis, a practical test for the hierarchical affinity of source-level data. when used for array regrouping and structure splitting, k-distance analysis consistently outperforms data organizations given by the programmer, compiler analysis, frequency profiling, statistical clustering, and all other methods we have tried.
symbolic pointer analysis revisited. pointer analysis is a critical problem in optimizing compiler, parallelizing compiler, software engineering and most recently, hardware synthesis. while recent efforts have suggested symbolic method, which uses bryant's binary decision diagram as an alternative to capture the point-to relation, no speed advantage has been demonstrated for context-insensitive analysis, and results for context-sensitive analysis are only preliminary.in this paper, we refine the concept of symbolic transfer function proposed earlier and establish a common framework for both context-insensitive and context-sensitive pointer analysis. with this framework, our transfer function of a procedure can abstract away the impact of its callers and callees, and represent its point-to information completely, compactly and canonically. in addition, we propose a symbolic representation of the invocation graph, which can otherwise be exponentially large. in contrast to the classical frameworks where context-sensitive point-to information of a procedure has to be obtained by the application of its transfer function exponentially many times, our method can obtain point-to information of all contexts in a single application. our experimental evaluation on a wide range of c benchmarks indicates that our context-sensitive pointer analysis can be made almost as fast as its context-insensitive counterpart.
communication optimizations for parallel c programs. this paper presents algorithms for reducing the communication overhead for parallel c programs that use dynamically-allocated data structures. the framework consists of an analysis phase called possible-placement analysis, and a transformation phase called communication selection.the fundamental idea of possible-placement analysis is to find all possible points for insertion of remote memory operations. remote reads are propagated upwards, whereas remote writes are propagated downwards. based on the results of the possible-placement analysis, the communication selection transformation selects the "best" place for inserting the communication, and determines if pipelining or blocking of communication should be performed.the framework has been implemented in the earth-mccat optimizing/parallelizing c compiler, and experimental results are presented for five pointer-intensive benchmarks running on the earth-manna distributed-memory parallel architecture. these experiments show that the communication optimization can provide performance improvements of up to 16% over the unoptimized benchmarks.