7,482 papers · page 305 of 375
Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The name program-based branch prediction is given to static branch prediction techniques that base their prediction on a program's structure. In this…
We present a flow-sensitive interprocedural constant propagation algorithm, which supports recursion while only performing one flow-sensitive analysis of each procedure. We present experimental results which show that this method finds substantially more constants than previous m…
We present a unified approach to locality optimization that employs both data and control transformations. Data transformations include changing the array layout in memory. Control transformations involve changing the execution order of programs. We have developed new techniques …
We believe that optimizing compilers should treat the machine-independent optimizations (e.g., conditional constant propagation, global value numbering) and code motion issues separately.’ Removing the code motion requirements from the machine-independent optimization allows stro…
When dense matrix computations are too large to fit in cache, previous research proposes tiling to reduce or eliminate capacity misses. This paper presents a new algorithm for choosing problem-size dependent tile sizes based on the cache size and cache line size for a direct-mapp…
Dynamic dispatching is a major source of run-time overhead in object-oriented languages, due both to the direct cost of method lookup and to the indirect effect of preventing other optimizations. To reduce this overhead, optimizing compilers for object-oriented languages analyze …
An interpreter can spend a significant part of its execution time on accessing arguments of virtual machine instructions. This paper explores two methods to reduce this overhead for virtual stack machines by caching top-of-stack values in (real machine) registers. The dynamic met…
Modula-3 supports development of modular programs by separating an object's interface from its implementation. This separation induces a runtime overhead in the implementation of objects, because it prevents the compiler from having complete information about a program's type hie…
Assignment motion (AM) and expression motion (EM) are the basis of powerful and at the first sight incomparable techniques for removing partially redundant code from a program. Whereas AM aims at the elimination of complete assignments, a transformation which is always desirable,…
This paper presents a compiler optimization algorithm to reduce the run time overhead of array subscript range checks in programs without compromising safety. The algorithm is based on partial redundancy elimination and it incorporates previously developed algorithms for range ch…
We present compiler analyses and optimizations for explicitly parallel programs that communicate through a shared address space. Any type of code motion on explicitly parallel programs requires a new kind of analysis to ensure that operations reordered on one processor cannot be …
EEL (Executable Editing Library) is a library for building tools to analyze and modify an executable (compiled) program. The systems and languages communities have built many tools for error detection, fault isolation, architecture translation, performance measurement, simulation…
DSP architectures typically provide indirect addressing modes with auto-increment and decrement. In addition, indexing mode is not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address registers and perform address arithmet…
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 …
On-chip instruction caches are increasing in size.Compiler writers are exploiting this fact by applying a variety of optimization that improve the execution performance of a program at the expense of increasing its code size.This paper describes a new optimization that can be use…
The ability to predict at compile time the likelihood of a particular branch being taken provides valuable information for several optimizations, including global instruction scheduling, code layout, function inlining, interprocedural register allocation and many high level optim…
The control dependence relation is used extensively in restructuring compilers. This relation is usually represented using the control dependence graph; unfortunately, the size of this data structure can be quadratic in the size of the program, even for some structured programs. …
Current parallelizing compilers cannot identify a significant fraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. As parallelizable loops arise frequently in practice, we advocate a novel framework for their identificat…
Recent work on alias analysis in the presence of pointers has concentrated on context-sensitive interprocedural analyses, which treat multiple calls to a single procedure independently rather than constructing a single approximation to a procedure's effect on all of its callers. …
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 …