waashk/dblp huggingface dataset:
register allocation for software pipelined multi-dimensional loops. software pipelining of a multi-dimensional loop is an important optimization that overlaps the execution of successive outermost loop iterations to explore instruction-level parallelism from the entire n-dimensional iteration space. this paper investigates register allocation for software pipelined multi-dimensional loops.for single loop software pipelining, the lifetime instances of a loop variant in successive iterations of the loop form a repetitive pattern. an effective register allocation method is to represent the pattern as a vector of lifetimes (or a vector lifetime using rau's terminology) and map it to rotating registers. unfortunately, the software pipelined schedule of a multi-dimensional loop is considerably more complex, and so are the vector lifetimes in it.in this paper, we develop a way to normalize and represent vector lifetimes in multi-dimensional loop software pipelining, which capture their complexity, while exposing their regularity that enables us to develop a simple, yet powerful solution. our algorithm is based on the development of a metric, called distance, that quantitatively determines the degree of potential overlapping (conflicts) between two vector lifetimes. we show how to calculate and use the distance, conservatively or aggressively, to guide the register allocation of the vector lifetimes under a bin-packing algorithm framework. the classical register allocation for software pipelined single loops is subsumed by our method as a special case.the method has been implemented in the orc compiler and produced code for the itanium architecture. we report the effectiveness of our method on 134 loop nests with 348 loop levels. several strategies for register allocation are compared and analyzed.
off-line variable substitution for scaling points-to analysis. most compiler optimizations and software productivity tools rely on information about the effects of pointer dereferences in a program. the purpose of points-to analysis is to compute this information safely, and as accurately as is practical. unfortunately, accurate points-to information is difficult to obtain for large programs, because the time and space requirements of the analysis become prohibitive. we consider the problem of scaling flow- and context-insensitive points-to analysis to large programs, perhaps containing hundreds of thousands of lines of code. our approach is based on a variable substitution transformation, which is performed off-line, i.e., before a standard points-to analysis is performed. the general idea of variable substitution is that a set of variables in a program can be replaced by a single representative variable, thereby reducing the input size of the problem. our main contribution is a linear-time algorithm which finds a particular variable substitution that maintains the precision of the standard analysis, and is also very effective in reducing the size of the problem. we report our experience in performing points-to analysis on large c programs, including some industrial-sized ones. experiments show that our algorithm can reduce the cost of andersen's points-to analysis substantially: on average, it reduced the running time by 53% and the memory cost by 59%, relative to an efficient baseline implementation of the analysis.
symbolic bounds analysis of pointers, array indices, and accessed memory regions. this article presents a novel framework for the symbolic bounds analysis of pointers, array indices, and accessed memory regions. our framework formulates each analysis problem as a system of inequality constraints between symbolic bound polynomials. it then reduces the constraint system to a linear program. the solution to the linear program provides symbolic lower and upper bounds for the values of pointer and array index variables and for the regions of memory that each statement and procedure accesses. this approach eliminates fundamental problems associated with applying standard fixed-point approaches to symbolic analysis problems. experimental results from our implemented compiler show that the analysis can solve several important problems, including static race detection, automatic parallelization, static detection of array bounds violations, elimination of array bounds checks, and reduction of the number of bits used to store computed values.
pointer analysis for multithreaded programs. this paper presents a novel interprocedural, flow-sensitive, and context-sensitive pointer analysis algorithm for multithreaded programs that may concurrently update shared pointers. for each pointer and each program point, the algorithm computes a conservative approximation of the memory locations to which that pointer may point. the algorithm correctly handles a full range of constructs in multithreaded programs, including recursive functions, function pointers, structures, arrays, nested structures and arrays, pointer arithmetic, casts between pointer variables of different types, heap and stack allocated memory, shared global variables, and thread-private global variables.we have implemented the algorithm in the suif compiler system and used the implementation to analyze a sizable set of multithreaded programs written in the cilk multithreaded programming language. our experimental results show that the analysis has good precision and converges quickly for our set of cilk programs.
replay for concurrent non-deterministic shared memory applications. replay of shared-memory program execution is desirable in many domains including cyclic debugging, fault tolerance and performance monitoring. past approaches to repeatable execution have focused on the problem of re-executing the shared-memory access patterns in parallel programs. with the proliferation of operating system supported threads and shared memory for uniprocessor programs, there is a clear need for efficient replay of concurrent applications. the solutions for parallel systems can be performance prohibitive when applied to the uniprocessor case. we present an algorithm, called the repeatable scheduling algorithm, combining scheduling and instruction counts to provide an invariant for efficient, language independent replay of concurrent shared-memory applications. the approach is shown to have trace overheads that are independent of the amount of sharing that takes place. an implementation for cyclic debugging on mach 3.0 is evaluated and benchmarks show typical performance overheads of around 10%. the algorithm implemented is compared with optimal event-based tracing and shown to do better with respect to the number of events monitored or number of events logged, in most cases by several orders of magnitude.
is continuation-passing useful for data flow analysis? the widespread use of the continuation-passing style (cps) transformation in compilers, optimizers, abstract interpreters, and partial evaluators reflects a common belief that the transformation has a positive effect on the analysis of programs. investigations by nielson [13] and burn/filho [5,6] support, to some degree, this belief with theoretical results. however, they do not pinpoint the source of increased abstract information and do not explain the observation of many people that continuation-passing confuses some conventional data flow analyses. to study the impact of the cps transformation on program analysis, we derive three canonical data flow analyzers for the core of an applicative higher-order programming language. the first analyzer is based on a direct semantics of the language, the second on a continuation-semantics of the language, and the last on the direct semantics of cps terms. all analyzers compute the control flow graph of the source program and hence our results apply to a large class of data flow analyses. a comparison of the information gathered by our analyzers establishes the following points:1. the results of a direct analysis of a source program are incomparable to the results of an analysis of the equivalent cps program. in other words, the translation of the source program to a cps version may increase or decrease static information. the gain of information occurs in non-distributive analyses and is solely due to the duplication of the analysis of the continuation. the loss of information is due to the confusion of distinct procedure returns.2. the analyzer based on the continuation semantics produces more accurate results than both direct analyzers, but again only in non-distributive analyses due to the duplication of continuations along every execution path. however, when the analyzer explicitly accounts for looping constructs, the results of the semantic-cps analysis are no longer computable.in view of these results, we argue that, in practice, a direct data flow analysis that relies on some amount of duplication would be as satisfactory as a cps analysis.
scannerless nslr(1) parsing of programming languages. the disadvantages of traditional two-phase parsing (a scanner phase preprocessing input for a parser phase) are discussed. we present metalanguage enhancements for context-free grammars that allow the syntax of programming languages to be completely described in a single grammar. the enhancements consist of two new grammar rules, the exclusion rule, and the adjacency-restriction rule. we also present parser construction techniques for building parsers from these enhanced grammars, that eliminate the need for a scanner phase.
register allocation across procedure and module boundaries. this paper describes a method for compiling programs using interprocedural register allocation. a strategy for handling programs built from multiple modules is presented, as well as algorithms for global variable promotion and register spill code motion. these algorithms attempt to address some of the shortcomings of previous interprocedural register allocation strategies. results are given for an implementation on a single register file risc-based architecture.
determining average program execution times and their variance. this paper presents a general framework for determining average program execution times and their variance, based on the program's interval structure and control dependence graph. average execution times and variance values are computed using frequency information from an optimized counter-based execution profile of the program.
a general framework for iteration-reordering loop transformations. this paper describes a general framework for representing iteration-reordering transformations. these transformations can be both matrix-based and non-matrix-based. transformations are defined by rules for mapping dependence vectors, rules for mapping loop bound expressions, and rules for creating new initialization statements. the framework is extensible, and can be used to represent any iteration-reordering transformation. mapping rules for several common transformations are included in the paper.
a new algorithm for scalar register promotion based on ssa form. we present a new register promotion algorithm based on static single assignment (ssa) form. register promotion is aimed at promoting program names from memory locations to registers. our algorithm is profile-driven and is based on the scope of intervals. in cases where a complete promotion is not possible because of the presence of function calls or pointer references, the proposed algorithm is capable of eliminating loads and stores on frequently executed paths by placing loads and stores on less frequently executed paths. we also describe an efficient method to incrementally update ssa form when new definitions are cloned from an existing name during register promotion. on specint95 benchmarks, our algorithm removes about ~12% of memory operations which access scalar variables.
exploiting idle floating-point resources for integer execution. in conventional superscalar microarchitectures with partitioned integer and floating-point resources, all floating-point resources are idle during execution of integer programs. palacharla and smith [26] addressed this drawback and proposed that the floating-point subsystem be augmented to support integer operations. the hardware changes required are expected to be fairly minimal.to exploit these idle floating resources, the compiler must identify integer code that can be profitably offloaded to the augmented floating-point subsystem. in this paper, we present two compiler algorithms to do this. the basic scheme offloads integer computation to the floating-point subsystem using existing program loads/stores for inter-partition communication. for the specint95 benchmarks, we show that this scheme offloads from 5% to 29% of the total dynamic instructions to the floating-point subsystem. the advanced scheme inserts copy instructions and duplicates some instructions to further offload computation. we evaluate the effectiveness of the two schemes using timing simulation. we show that the advanced scheme can offload from 9% to 41% of the total dynamic instructions to the floating-point subsystem. in doing so, speedups from 3% to 23% are achieved over a conventional microarchitecture.
control cpr: a branch height reduction optimization for epic architectures. the challenge of exploiting high degrees of instruction-level parallelism is often hampered by frequent branching. both exposed branch latency and low branch throughput can restrict parallelism. control critical path reduction (control cpr) is a compilation technique to address these problems. control cpr can reduce the dependence height of critical paths through branch operations as well as decrease the number of executed branches. in this paper, we present an approach to control cpr that recognizes sequences of branches using profiling statistics. the control cpr transformation is applied to the predominant path through this sequence. our approach, its implementation, and experimental results are presented. this work demonstrates that control cpr enhances instruction-level parallelism for a variety of application programs and improves their performance across a range of processors.
facile: a language and compiler for high-performance processor simulators. architectural simulators are essential tools for computer architecture and systems research and development. simulators, however, are becoming frustratingly slow, because they must now model increasingly complex micro-architectures running realistic workloads. previously, we developed a technique called fast-forwarding, which applied partial evaluation and mermoization to improve the performance of detailed architectural simulations by as much as an order of magnitude [14]. while writing a detailed processor simulator is difficult, implementing fast-forwarding is even more complex. this paper describes facile, a domain-specific language for writing detailed, accurate micro-architecture simulators. architectural descriptions written in facile can be compiled, using partial evaluation techniques, into fast-forwarding simulators that achieve significant performance improvements with far less programmer effort. facile and its compiler make this performance-enhancing technique accessible to computer architects.
on-the-fly detection of access anomalies. access anomalies are a common class of bugs in shared-memory parallel programs. an access anomaly occurs when two concurrent execution threads both write (or one thread reads and the other writes) the same shared memory location without coordination. approaches to the detection of access anomalies include static analysis, post-mortem trace analysis, and on-the-fly monitoring.a general on-the-fly algorithm for access anomaly detection is presented, which can be applied to programs with both nested fork-join and synchronization operations. the advantage of on-the-fly detection over post-mortem analysis is that the amount of storage used can be greatly reduced by data compression techniques and by discarding information as soon as it becomes obsolete. in the algorithm presented, the amount of storage required at any time depends only on the number v of shared variables being monitored and the number n of threads, not on the number of synchronizations. data compression is achieved by the use of two techniques called merging and subtraction. upper bounds on storage are shown to be v x n2 for merging and v x n for subtraction.
an optimizer for ada - design, experiences and results. in this paper we describe the design of a global machine independent low level optimizer for the karlsruhe ada compiler. we give a short overview on the optimizations and data structures used in the optimizer as well as some experiences with the optimizer. detailed measurements are provided for a collection of benchmarks. the average improvement of code speed is 40%.
heap profiling for space-efficient java. we present a heap-profiling tool for exploring the potential for space savings in java programs. the output of the tool is used to direct rewriting of application source code in a way that allows more timely garbage collection (gc) of objects, thus saving space. the rewriting can also avoid allocating some objects that are never used. the tool measures the difference between the actual collection time and the potential earliest collection time of objects for a java application. this time difference indicates potential savings. then the tool sorts the allocation sites in the application source code according to the accumulated potential space saving for the objects allocated at the sites. a programmer can investigate the source code surrounding the sites with the highest savings to find opportunities for code rewriting that could save space. our experience shows that in many cases simple code rewriting leads to actual space savings and in some cases also to improvements in program runtime. experimental results using the tool and manually rewriting code show average space savings of 18% for the specjvm98 benchmark suite. results for other benchmarks are also promising. we have also classified the program transformations that we have used and argue that in many cases improvements can be achieved by an optimizing compiler.
a type-based compiler for standard ml. compile-time type information should be valuable in efficient compilation of statically typed functional languages such as standard ml. but how should type-directed compilation work in real compilers, and how much performance gain will type-based optimizations yield? in order to support more efficient data representations and gain more experience about type-directed compilation, we have implemented a new type-based middle end and back end for the standard ml of new jersey compiler. we describe the basic design of the new compiler, identify a number of practical issues, and then compare the performance of our new compiler with the old non-type-based compiler. our measurement shows that a combination of several simple type-based optimizations reduces heap allocation by 36%; and improves the already-efficient code generated by the old non-type-based compiler by about 19% on a decstation 500.
automatic design and implementation of language data types. language implementation is in need of automation. although compiler construction has long been aided by parser generators and other tools, interpreters and runtime systems have been neglected, even though they constitute a large component of languages like lisp, prolog, and smalltalk. of the several parts of a runtime system, the primitive datatype definitions present some of the most difficult decisions for the implementor. the effectiveness of type discrimination schemes, interactions between storage allocation and virtual memory, and general time/space tradeoffs are issues that have no simple resolution-they must be evaluated for each implementation. a formalism for describing implementations has been developed and used in a prototype designer of primitive data structures. the designer is a collection of heuristic rules that produce multiple designs of differing characteristics. cost evaluation on machine code derived from those designs yields performance formulas, which are then used to estimate the designs' effect on benchmark programs.
control-flow analysis in scheme. traditional flow analysis techniques, such as the ones typically employed by optimizing fortran compilers, do not work for scheme-like languages. this paper presents a flow analysis technique &mdash; control flow analysis &mdash; which is applicable to scheme-like languages. as a demonstration application, the information gathered by control flow analysis is used to perform a traditional flow analysis problem, induction variable elimination. extensions and limitations are discussed. the techniques presented in this paper are backed up by working code. they are applicable not only to scheme, but also to related languages, such as common lisp and ml.
continuations and transducer composition. on-line transducers are an important class of computational agent; we construct and compose together many software systems using them, such as stream processors, layered network protocols, dsp networks and graphics pipelines. we show an interesting use of continuations, that, when taken in a cps setting, exposes the control flow of these systems. this enables a cps-based compiler to optimise systems composed of these transducers, using only standard, known analyses and optimisations. critically, the analysis permits optimisation across the composition of these transducers, allowing efficient construction of systems in a hierarchical way.
essential language support for generic programming. concepts are an essential language feature for generic programming in the large. concepts allow for succinct expression of constraints on type parameters of generic algorithms, enable systematic organization of problem domain abstractions, and make generic algorithms easier to use. in this paper we present the design of a type system and semantics for concepts that is suitable for non-type-inferencing languages. our design shares much in common with the type classes of haskell, though our primary influence is from best practices in the c++ community, where concepts are used to document type requirements for templates in generic libraries. concepts include a novel combination of associated types and same-type constraints that do not appear in type classes, but that are similar to nested types and type sharing in ml.
handling control. non-local control transfer and exception handling have a long tradition in higher-order programming languages such as common lisp, scheme and ml. however, each language stops short of providing a full and complementary approach&mdash;control handling is provided only if the corresponding control operator is first-order. in this work, we describe handlers in a higher-order control setting. we invoke our earlier theoretical result that all denotational models of control languages invariably include capabilities that handle control. these capabilities, when incorporated into the language, form an elegant and powerful higher-order generalization of the first-order exception-handling mechanism.
di: an interactive debugging interpreter for applicative languages. the di interpreter is both a debugger and interpreter of sisal programs. its use as a program interpreter is only a small part of its role; it is designed to be a tool for studying compilation techniques for applicative languages. di interprets dataflow graphs expressed in the if1 and if2 languages, and is heavily instrumented to report the activity of dynamic storage activity, reference counting, copying and updating of structured data values. it also aids the sisal language evaluation by providing an interim execution vehicle for sisal programs. di provides determinate, sequential interpretation of graph nodes for sequential and parallel operations in a canonical order. as a debugging aid, di allows tracing, breakpointing, and interactive display of program data values. di handles creation of sisal and if1 error values for each data type and propagates them according to a well-defined algebra. we have begun to implement if1 optimizers and have measured the improvements with di.