Abstract Building a Control-flow Graph from Scheduled Assembly Code (2008)
Keith D. Cooper, Timothy J. Harvey, Todd Waterman
A variety of applications have arisen where it is worthwhile to apply code optimizations directly to the machine code (or assembly code) produced by a compiler. These include link-time whole-program...
Keith D. Cooper, Devika Subramanian, Linda Torczon
In the past decade, we have seen an explosion in the number of computers in use and in their diversity. Even commodity microprocessors come in low-power versions, embedded versions, and a variety of...
An Effective Local Search Algorithm for an Adaptive Compiler (2008)
Yi Guo, Devika Subramanian, Keith D. Cooper
Abstract. Most algorithms currently used to find good compilation sequences in an iterative adaptive compiler, such as genetic algorithms and hill climbing, search in the space of sequences of fixed...
Abstract Searching for Compilation Sequences ∗ (2008)
Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steve Reeves, Devika Subramanian, Linda Torczon, ...
A growing body of literature on adaptive compilation suggests that using program-specific [7] or function-specific [24] compilation sequences can produce consistent improvements over compiling the...
Abstract ACME: Adaptive Compilation Made Efficient ∗ (2008)
Keith D. Cooper, Er Grosul, Timothy J. Harvey, Steven Reeves, Devika Subramanian, Linda Torczon, ...
Research over the past five years has shown significant performance improvements using a technique called adaptive compilation. An adaptive compiler uses a compile-execute-analyze feedback loop to...
RETROSPECTIVE: Coloring Heuristics for Register Allocation (2008)
Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon
From the earliest compilers, register allocation was recognized as an important optimization. Indeed, the original Fortran compiler spent two of its six passes on the problem [1]. (That compiler used...
Program Memory Redundancy Analysis and Elimination to Improve Application Performance (2008)
As a consequence of current evolution trend of both software development paradigm and processor architecture, memory operations have become not only more frequent during program execution, but also...
Importance of Spill Reduction (2008)
Keith D. Cooper, Linda Torczon, Jason Eckhardt
all rights reserved.
ABSTRACT Finding Effective Compilation Sequences (2008)
L. Almagor, Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven W. Reeves, Devika Subramanian, ...
Most modern compilers operate by applying a fixed, program-independent sequence of optimizations to all programs. Compiler writers choose a single “compilation sequence”, or perhaps a couple of...
Keith D. Cooper, Mary W. Hall, Ken Kennedy
Procedure cloning is an interprocedural transformation where the compiler creates specialized copies of procedure bodies. The compiler divides incoming calls between the original procedure and its...
MSCP: Recent Accomplishments (2007)
Keith Cooper Linda, Keith D. Cooper, Linda Torczon
This document provides, in outline form, an overview of our recent accomplishments.
Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick
Operator strength reduction is a technique that improves compiler-generated code by reformulating certain costly computations in terms of less expensive ones. A common case arises in array-addressing...
Abstract Optimizing for Reduced Code Space using Genetic Algorithms (2007)
Keith D. Cooper, Philip J. Schielke, Devika Subramanian
Code space is a critical issue facing designers of software for embedded systems. Many traditional compiler optimizations are designed to reduce the execution time of compiled code, but not...
ASimple,Fast Dominance Algorithm (2007)
Keith D. Cooper, Timothy J. Harvey, Ken Kennedy
The problem of finding the dominators in a control-flow graph has a long history in the literature. The original algorithms suffered from a large asymptotic complexity but were easy to understand....
Keith D. Cooper, L. Taylor Simpson
Abstract. Graph coloring is the dominant paradigm for global register allocation [8, 7, 4]. Coloring allocators use an interference graph to model the conflicts that prevent two values from sharing a...
ASimple,Fast Dominance Algorithm (2007)
Keith D. Cooper, Timothy J. Harvey, Ken Kennedy
The problem of finding the dominators in a control-flow graph has a long history in the literature. The original algorithms suffered from a large asymptotic complexity but were easy to understand....
Keith D. Cooper, Mary W. Hall, Linda Torczon
This paper describes an experiment undertaken to evaluate the effectiveness of inline substitution as a method of improving the running time of compiled code. Our particular interests are in the...
Trilogy Development Group (2007)
Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick
Operator strength reduction is a well known code-improvement technique. It improves compiler-generated code by reformulating certain costly computations in terms of less expensive ones. A common case...
Reusable Software Components (2007)
Robert S. Cartwright, Keith D. Cooper, David M. Lane, Matthew Flatt, Matthew Flatt
Programming languages offer a variety of constructs to support code reuse. For example, functional languages provide function constructs for encapsulating expressions to be used in multiple contexts....
Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor Simpson, C○ John Wiley
Static single assignment (SSA) form is a program representation that is becoming in-creasingly popular for compiler-based code optimization. In this paper, we address three problems that have arisen...
Abstract Building a Control-flow Graph from Scheduled Assembly Code (2007)
Keith D. Cooper, Timothy J. Harvey, Todd Waterman
A variety of applications have arisen where it is worthwhile to apply code optimizations directly to the machine code (or assembly code) produced by a compiler. These include link-time whole-program...
Toward a Tool for Scheduling Application Workflows onto Distributed Grid Systems (2006)
Anirban Mandal, W. Kennedy, Keith D. Cooper, John Mellor-crummey, Charles Koelbel, William W. Symes, ...
In this dissertation, we present a design and implementation of a tool for auto-matic mapping and scheduling of large scientific application workflows onto dis-tributed, heterogeneous Grid...
Keith D. Cooper, Anshuman Dasgupta, Jason Eckhardt
Abstract. Techniques for global register allocation via graph coloring have been extensively studied and widely implemented in compiler frameworks. This paper examines a particular variant – the...
Iterative data-flow analysis, revisited (2004)
Keith D. Cooper, Timothy J. Harvey, Ken Kennedy
ABSTRACT The iterative algorithm is widely used to solve instances of data-flow analysis problems. The algorithm is attractive because it is easy to implement and robust in its behavior. The theory...
Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steve Reeves, Devika Subramanian, Linda Torczon, ...
Modern optimizing compilers apply a fixed sequence of optimizations, which we call a compilation sequence, to each program that they compile. These compilers let the user modify their behavior in a...
Iterative data-flow analysis, revisited (2004)
Keith D. Cooper, Timothy J. Harvey, Ken Kennedy
The iterative algorithm is widely used to solve instances of data-flow analysis problems. The algorithm is attractive because it is easy to implement and robust in its behavior. The theory behind the...
L. Almagor, Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steve Reeves, Devika Subramanian, ...
Most modern compilers operate by applying a fixed sequence of code optimizations, called a compilation sequence, to all programs. Compiler writers determine a small set of good, general-purpose,...
Investigating Adaptive Compilation using the MIPSPro Compiler (2003)
Keith D. Cooper, Todd Waterman
Despite the astonishing increases in processor performance over the last forty years, delivered application performance remains a critical issue for many important problems. Compilers play a critical...
Memory redundancy elimination to improve application energy e#ciency (2003)
Abstract. Application energy consumption has become an increasingly important issue for both high-end microprocessors and mobile and embedded devices. A multitude of circuit and architecture-level...
Investigating Adaptive Compilation using the MIPSPro Compiler (2003)
Keith D. Cooper, Keith D. Cooper, Todd Waterman, Todd Waterman
Despite the astonishing increases in processor performance over the last 40 years, delivered application performance remains a critical issue for many important problems. Compilers play a critical...
Behavioral Software Contracts (2002)
Robert "corky Cartwright, Keith D. Cooper, Michael Barlow, Robert Bruce Findler, Robert Bruce Findler, Robert Bruce
by
Building a Control-Flow Graph from Scheduled Assembly Code (2002)
Keith D. Cooper, Timothy J. Harvey, Todd Waterman
Abstract A variety of applications have arisen where it isworthwhile to apply code optimizations directly to the machine code (or assembly code) produced bya compiler. These include link-time...
Compilation order matters (2002)
Keith D. Cooper, Timothy J. Harvey, Devika Subramanian, Linda Torczon
At design time, the compiler writer selects a set of optimizations and an order in which to apply them. These choices have a direct impact on the quality of code that the compiler can generate. They...
Building a Control-Flow Graph from Scheduled Assembly Code (2002)
Keith D. Cooper, Timothy J. Harvey, Todd Waterman
A variety of applications have arisen where it is worthwhile to apply code optimizations directly to the machine code (or assembly code) produced by a compiler. These include link-time whole-program...
Adaptive optimizing compilers for the 21st century (2002)
Keith D. Cooper, Devika Subramanian, Linda Torczon
Historically, compilers have operated by applying a fixed set of optimizations in a predetermined order. We call such an ordered list of optimizations a compilation sequence. This paper describes a...
Building a Control-Flow Graph from Scheduled Assembly Code (2002)
Keith D. Cooper, Timothy J. Harvey, Todd Waterman
Avarietyof applications have arisen where it is worthwhile to apply code optimizations directly to the machine code (or assembly code) produced by a compiler. These include link-time whole-program...
Adaptive optimizing compilers for the 21st century (2002)
Keith D. Cooper, Devika Subramanian, Linda Torczon
Historically, compilers have operated by applying a fixed set of optimizations in a predetermined order. We call such an ordered list of optimizations a compilation sequence. This paper describes a...
Behavioral Software Contracts (2002)
Robert Bruce Findler, Robert “corky Cartwright, Keith D. Cooper, Michael Barlow, Robert Bruce Findler, Robert Bruce Findler
by
Fast copy coalescing and live-range identification (2002)
Zoran Budimlić, Keith D. Cooper, Timothy J. Harvey, Ken Kennedy, Timothy S. Oberg, Steven W. Reeves
This paper presents a fast new algorithm for modeling and reasoning about interferences for variables in a program without constructing an interference graph. It then describes how to use this...
Fast copy coalescing and live-range identification (2002)
Keith D. Cooper, Timothy J. Harvey, Ken Kennedy, Timothy S. Oberg, Steven W. Reeves
ABSTRACT This paper presents a fast new algorithm for modeling and rea-soning about interferences for variables in a program without constructing an interference graph. It then describes how to use...
Fast copy coalescing and live-range identification (2002)
Zoran Budimlić, Keith D. Cooper, Timothy J. Harvey, Ken Kennedy, Timothy S. Oberg, Steven W. Reeves
This paper presents a fast new algorithm for modeling and reasoning about interferences for variables in a program without constructing an interference graph. It then describes how to use this...
Enhanced code compression for embedded RISC processors (1999)
Keith D. Cooper, Nathaniel Mcintosh
This paper explores compiler techniques for reducing the memory needed to load and run program executables. In embedded systems, where economic incentives to reduce both ram and rom are strong, the...
Optimizing for reduced code space using genetic algorithms (1999)
Keith D. Cooper, Philip J. Schielke, Devika Subramanian
Code space is a critical issue facing designers of software for embedded systems. Many traditional compiler optimizations are designed to reduce the execution time of compiled code, but not...
Optimizing VHDL Intermediate Forms (1998)
Cooper, Keith D., Bennett, John, Torczon, Linda
This program was based on leveraging software compiler optimization expertise to further improve upon hardware compiler optimization techniques for Field Programmable Gate Arrays (FPGAs).
Code Optimization for Embedded Systems (1998)
Cooper, Keith D., Subramanian, Devika, Torczon, Linda
This project investigated a number of problems that arise in compiling application code for embedded systems. These systems present the compiler with a number of challenges that arise from economic...
Compiler-Controlled Memory (1998)
Optimizations aimed at reducing the impact of memory operations on execution speed have long concentrated on improving cache performance. These efforts achieve a. reasonable level of success. The...
Compiler-Controlled Memory (1998)
Keith D. Cooper, Timothy J. Harvey
Optimizations aimed at reducing the impact of memory operations on execution speed have long concentrated on improving cache performance. These efforts achieve a reasonable level of success. The...
Non-local instruction scheduling with limited code growth (1998)
Keith D. Cooper, Philip J. Schielke
Abstract. Instruction scheduling is a necessary step in compiling for many modern microprocessors. Traditionally, global instruction scheduling techniques have outperformed local techniques. However...
An Experimental Evaluation of List Scheduling (1998)
Keith D. Cooper, Philip J. Schielke, Devika Subramanian
Abstract. While altering the scope of instruction scheduling has a rich heritage in compiler literature, instruction scheduling algorithms have received little coverage in recent times. The widely...
Non-local instruction scheduling with limited code growth (1998)
Keith D. Cooper, Philip J. Schielke
Instruction scheduling is a necessary step in compiling for many modern microprocessors. Traditionally, global instruction scheduling techniques have outperformed local techniques. However many of...
Practical Improvements to the Construction and Destruction of Static Single Assignment Form (1998)
Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor Simpson
Static single assignment (SSA) form is a program representation that is useful for compiler-based code optimization. In this paper, we address three problems that have arisen in our use of SSA form....
Compiler-Controlled Memory (1998)
Keith Cooper And, Keith D. Cooper, Timothy J. Harvey
Optimizations aimed at reducing the impact of memory operations on execution speed have long concentrated on improving cache performance. These e#orts achieve a reasonable level of success. The...
Preston Briggs, Keith D. Cooper, L. Taylor Simpson
This paper compares hash-based approaches derived from the classic local algorithm
Register Promotion in C Programs (1997)
The combination of pointers and pointer arithmetic in C makes the task of improving C programs somewhat more difficult than improving programs written in simpler languages like Fortran. While much...
Combining Analyses, Combining Optimizations (1995)
Modern optimizing compilers use several passes over a program’s intermediate representation to generate good code. Many of these optimizations exhibit a phase ordering problem. Getting the best...
Combining Analyses, Combining Optimizations (1995)
This paper presents a framework for describing optimizations. It shows how to combine two such frameworks and how to reason about the properties of the resulting framework. The structure of the...
Operator Strength Reduction (1995)
Keith Cooper, Laylor Simpson, Christopher Vick, Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick
This paper presents an algorithm for performing strength reduction on the static single assignment (SSA) form of a procedure [12]. It produces results similar to an earlier algorithm due to Allen,...
Using Conditional Branches to Improve Constant Propagation (1995)
Preston Briggs, Preston Briggs, Keith D. Cooper, Keith D. Cooper, Linda Torczon, Linda Torczon
This paper describes an efficient algorithm for discovering assertions of equality implied by conditional branches and discusses how to use these assertions to improve the results of Wegman and...
Value-Driven Code Motion (1995)
Keith Cooper, Taylor Simpson, Keith D. Cooper, L. Taylor Simpson
this paper focuses on lazy code motion as proposed by Knoop, Ruthing, and Steffen and modified by Drechsler and Stadel [14, 15, 11]. That algorithm is provably optimal; this paper shows that by...
SCC-Based Value Numbering (1995)
Keith Cooper, Taylor Simpson, Keith D. Cooper, L. Taylor Simpson
this paper, we describe a new technique for assigning value numbers that combines the advantages of both techniques -- it is easy to understand and implement; it can easily handle constant folding...
Combining Analyses, Combining Optimizations (1995)
Modern optimizing compilers use several passes over a program’s intermediate representation to generate good code. Many of these optimization exhibit a phase-ordering problem. Getting the best code...
Improvements to Graph Coloring Register Allocation (1994)
Preston Briggs, Keith D. Cooper, Linda Torczon
We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second...
Improvements to Graph Coloring Register Allocation (1994)
Preston Briggs, Keith D. Cooper, Linda Torczon
We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second...
Effective partial redundancy elimination (1994)
Preston Briggs, Keith D. Cooper
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...
Keith Cooper, Taylor Simpson, Preston Briggs, Preston Briggs, Keith D. Cooper, L. Taylor Simpson
This paper describes different techniques for assigning numbers and handling redundancies. It includes experimental evaluation of the relative effectiveness of these different approaches. In value...
ParaScope: a parallel programming environment (1993)
Keith D. Cooper, Mary W. Hall, Robert T. Hood, Senior Member, Kathryn S. M~kinley, ...
to support scientijic programming of shared-memop multiproces-sors, includes a collection of tools that use global program analysis to help users develop and debug parallel programs. This paper...
The ParaScope Parallel Programming Environment (1993)
Keith Cooper, Mary W. Hall, Robert T. Hood, Ken Kennedy, Kathryn S. M, Kinley John, ...
The ParaScope parallel programming environment, developed to support scientific programming of sharedmemory multiprocessors, includes a collection of tools that use global program analysis to help...
Coloring register pairs (1992)
Preston Briggs, Keith D. Cooper, Linda Torczon
Many architectures require that a program use pairs of adjacent registers to hold double-precision floatingpoint values. Register allocators based on Chaitin's graph-coloring technique have...
Unexpected side effects of inline substitution: a case study (1992)
Keith D. Cooper, Keith D. Cooper, Mary W. Hall, Mary W. Hall, Linda Torczon, Linda Torczon
The structure of a program can encode implicit information that changes both the shape and speed of the generated code. Interprocedural transformations like inlining often discard such information;...
Using compiler technology to drive advanced microprocessors (1992)
Recent years have seen the introduction of a series of ever faster, ever more complex microprocessors. These advanced microprocessors have found widespread application in machines that range from...
Automatic Inline Expansion for C Programs. Software – Practice and Experience, 25:349-369, (1992)
Frank Buschmann, Regine Meunier, Hans Rohnert, Peter Sommerlad, Michael Stal, ...
How to Build an Interference Graph (1988)
Keith D. Cooper, Timothy J. Harvey, Linda Torczon
This paper examines the tradeoffs between these two approaches