1,971 papers · page 81 of 99
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 …
this paper, we present an almost linear time algorithm to construct the GSA. The new algorithm is more efficient and simpler than the existing algorithms for GSA construction [BMO90, Hav93]. Since SSA is a special case of GSA, it can also be used as an efficient alternative algor…
This paper proposes an efficient technique for context-sensitive pointer analysis that is applicable to real C programs. For efficiency, we summarize the effects of procedures using partial transfer functions. A partial transfer function (PTF) describes the behavior of a procedur…
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 th…
Languages that support abstraction and modular structure, such as Standard ML, Modula, Ada, and (more or less) C++, may have deeply nested dependency hierarchies among source files. In ML the problem is particularly severe because ML's powerful parameterized module (functor) faci…
We present a pointer and array access checking technique that provides complete error coverage through a simple set of program transformations. Our technique, based on an extended safe pointer representation, has a number of novel aspects. Foremost, it is the first technique that…
Partial redundancy elimination is a code optimization with a long history of literature and implementation. In practice, its effectiveness depends on issues of naming and code shape. This paper shows that a combination of global reassociation and global value numbering can increa…
As microprocessor speeds increase, memory bandwidth is increasingly the performance bottleneck for microprocessors. This has occurred because innovation and technological improvements in processor design have outpaced advances in memory design. Most attempts at addressing this pr…
Existing methods for alias analysis of recursive pointer data structures are based on two approximation techniques: k-limiting, and store-based (or equivalently location or region-based) approximations, which blur distinction between elements of recursive data structures. Althoug…
We describe techniques for converting the intermediate code representation of a given program, as generated by a modern compiler, to another representation which produces the same run-time results, but can run faster on a superscalar machine. The algorithms, based on novel parall…
This paper reports on the design, implementation, and empirical results of a new method for dealing with the aliasing problem in C. The method is based on approximating the points-to relationships between accessible stack locations, and can be used to generate alias pairs, or use…
We present a method for automatically extracting parallel prefix programs from sequential loops, even in the presence of complicated conditional statements. Rather than searching for associative operators in the loop body directly, the method rests on the observation that functio…
Integer division remains expensive on today's processors as the cost of integer multiplication declines. We present code sequences for division by arbitrary nonzero integer constants and run-time invariants using integer multiplication. The algorithms assume a two's complement ar…
GIVE-N-TAKE is a code placement framework which uses a general producer-consumer concept. An advantage of GIVE-N-TAKE over existing partial redundancy elimination techniques is its concept of production regions, instead of single locations, which can be beneficial for general lat…