Just-in-time (JIT) compilation coupled with code caching are widely used to improve performance in dynamic programming language implementations. These code caches, along with the associated profiling data for the hot code, however, consume significant amounts of memory. Furthermore, they incur extra JIT compilation time for their creation. On Android, the current standard JIT compiler and its code caches are not shared among processes—that is, the runtime system maintains a private code cache, and its associated data, for each runtime process. However, applications running on the same platform tend to share multiple libraries in common. Sharing cached code across multiple applications and multiple processes can lead to a reduction in memory use. It can directly reduce compile time. It can also reduce the cumulative amount of time spent interpreting code. All three of these effects can improve actual runtime performance. In this paper, we describe ShareJIT, a global code cache for JITs that can share code across multiple applications and multiple processes. We implemented ShareJIT in the context of the Android Runtime (ART), a widely used, state-of-the-art system. To increase sharing, our implementation constrains the amount of context that the JIT compiler can use to optimize the code. This exposes a fundamental tradeoff: increased specialization to a single process’ context decreases the extent to which the compiled code can be shared. In ShareJIT, we limit some optimization to increase shareability. To evaluate the ShareJIT, we tested 8 popular Android apps in a total of 30 experiments. ShareJIT improved overall performance by 9% on average, while decreasing memory consumption by 16% on average and JIT compilation time by 37% on average.

Grid computing is now a viable computational paradigm for executing large scale workflow applications. However, many aspects of performance optimization remain challenging. In this paper, we focus on the workflow scheduling mechanism. While there is much work on static scheduling approaches for workflow applications in parallel environments, little work has been done on a real-world multi-cluster grid environment. Since a typical grid environment is dynamic, we propose a new cluster-based scheduling mechanism that dynamically executes a top-down static scheduling algorithm using the real-time feedback from the execution monitor. We also propose a novel two phase migration mechanism that mitigates the effect of a possible bad reschedule decision. Our experimental results show that this approach achieves the best performance among all the scheduling approaches we implemented on both reserved resources and those with external loads.

Complex scientific workflows are now Increasingly executed on computational grids. In addition to the challenges of managing and scheduling these workflows, reliability challenges arise because of the unreliable nature of large-scale grid infrastructure. Fault tolerance mechanisms like over-provisioning and checkpoint-recovery are used in current grid application management systems to address these reliability challenges. In this work, we propose new approaches that combine these fault tolerance techniques with existing workflow scheduling algorithms. We present a study on the effectiveness of the combined approaches by analyzing their impact on the reliability of workflow execution, workflow performance and resource usage under different reliability models, failure prediction accuracies and workflow application types.

Workflow computations have become a major programming paradigm for scientific applications. However, acquiring enough computational resources to execute a workflow poses a challenge in a batch queue controlled resource due to the space-sharing nature of the resource management policy. This paper introduces a scheduling technique that aggregates a workflow application into several subcomponents. It then uses the batch queue to acquire resources for each subcomponent, overlapping resource provisioning overhead (wait time) of one with the execution of others. We implemented a prototype of this technique and tested it using five high performance computing centers job submission logs. The results show that our approach can eliminate as much as 70% of the wait time over more traditional techniques that request resources for individual workflow nodes or that acquire all the resources for the whole workflow at once.

This work proposes and evaluates improvements to previously known algorithms for redundancy elimination.

Thanks to advances in wide-area network technologies and the decreasing cost of computing resources, Grid computing is now a viable computational paradigm. However, many aspects of successfully using the Grid remain research topics. Among them, we identify scheduling of workflow applications as a key problem. While there is much work on static scheduling approaches for workflow applications in parallel environments, little work has been done on a real-world Grid environment. In this paper, we launch four model workflow applications with different configurations on a multi-cluster Grid testbed. By observing the applications' performance, we propose a new cluster-based hybrid scheduling mechanism that dynamically executes a top-down static scheduling algorithm using the real-time feedback from the execution monitor. Our experimental results show that this approach achieves the best performance among all the scheduling approaches we implemented on both reserved resources and those with external loads.

Just-in-time compilers are invoked during application execution and therefore need to ensure fast compilation times. Consequently, runtime compiler designers are averse to implementing compile-time intensive optimization algorithms. Instead, they tend to select faster but less effective transformations. In this paper, we explore this trade-off for an important optimization - global register allocation. We present a graph-coloring register allocator that has been redesigned for runtime compilation. Compared to Chaitin-Briggs (1994), a standard graph-coloring technique, the reformulated algorithm requires considerably less allocation time and produces allocations that are only marginally worse than those of Chaitin-Briggs. Our experimental results indicate that the allocator performs better than the linear-scan and Chaitin-Briggs allocators on most benchmarks in a runtime compilation environment. By increasing allocation efficiency and preserving optimization quality, the presented algorithm increases the suitability and profitability of a graph-coloring register allocation strategy for a runtime compiler.

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 find the combination of optimizations and parameters that minimizes some performance goal, such as code size or execution time.Despite its ability to improve performance, adaptive compilation has not seen widespread use because of two obstacles: the large amounts of time that such systems have used to perform the many compilations and executions prohibits most users from adopting these systems, and the complexity inherent in a feedback-driven adaptive system has made it difficult to build and hard to use.A significant portion of the adaptive compilation process is devoted to multiple executions of the code being compiled. We have developed a technique called virtual execution to address this problem. Virtual execution runs the program a single time and preserves information that allows us to accurately predict the performance of different optimization sequences without running the code again. Our prototype implementation of this technique significantly reduces the time required by our adaptive compiler.In conjunction with this performance boost, we have developed a graphical-user interface (GUI) that provides a controlled view of the compilation process. By providing appropriate defaults, the interface limits the amount of information that the user must provide to get started. At the same time, it lets the experienced user exert fine-grained control over the parameters that control the system.

In this work, we describe new strategies for scheduling and executing workflow applications on Grid resources using the GrADS infrastructure. Workflow scheduling is based on heuristic scheduling strategies that use combined computational and memory hierarchy application component performance models. The workflow is executed using a novel strategy to bind and launch the application onto heterogeneous resources. We apply these strategies in the context of launching EMAN, a bio-imaging workflow application, onto the Grid.

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 compilation sequences. In choosing a sequence, they may consider performance of benchmarks or other important codes. These sequences are intended as general-purpose tools, accessible through command-line flags such as -O2 and -O3.Specific compilation sequences make a significant difference in the quality of the generated code, whether compiling for speed, for space, or for other metrics. A single universal compilation sequence does not produce the best results over all programs [8, 10, 29, 32]. Finding an optimal program-specific compilation sequence is difficult because the space of potential sequences is huge and the interactions between optimizations are poorly understood. Moreover, there is no systematic exploration of the costs and benefits of searching for good (i.e., within a certain percentage of optimal) program-specific compilation sequences.In this paper, we perform a large experimental study of the space of compilation sequences over a set of known benchmarks, using our prototype adaptive compiler. Our goal is to characterize these spaces and to determine if it is cost-effective to construct custom compilation sequences. We report on five exhaustive enumerations which demonstrate that 80% of the local minima in the space are within 5 to 10% of the optimal solution. We describe three algorithms tailored to search such spaces and report on experiments that use these algorithms to find good compilation sequences. These experiments suggest that properties observed in the enumerations hold for larger search spaces and larger programs. Our findings indicate that for the cost of 200 to 4,550 compilations, we can find custom sequences that are 15 to 25% better than the human-designed fixed-sequence originally used in our compiler.

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 information to minimize copy insertion for ϕ-node instantiation during the conversion of the static single assignment (SSA) form into the control-flow graph (CFG), effectively yielding a new, very fast copy coalescing and live-range identification algorithm.This paper proves some properties of the SSA form that enable construction of data structures to compute interference information for variables that are considered for folding. The asymptotic complexity of our SSA-to-CFG conversion algorithm is where-is the number of instructions in the program.Performing copy folding during the SSA-to-CFG conversion eliminates the need for a separate coalescing phase while simplifying the intermediate code. This may make graph-coloring register allocation more practical in just in time (JIT) and other time-critical compilers For example, Sun's Hotspot Server Compiler already employs a graph-coloring register allocator[10].This paper also presents an improvement to the classical interference-graph based coalescing optimization that shows adecrease in memory usage of up to three orders of magnitude and a decrease of a factor of two in compilation time, while providing the exact same results.We present experimental results that demonstrate that our algorithm is almost as precise (within one percent on average) as the improved interference-graph-based coalescing algorithm, while requiring three times less compilation time.

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 expressions used in loops. The compiler can replace the sequence of multiplies generated by a direct translation of the address expression with an equivalent sequence of additions. When combined with linear function test replacement, strength reduction can speed up the execution of loops containing array references. The improvement comes from two sources: a reduction in the number of operations needed to implement the loop and the use of less costly operations.This paper presents a new algorithm for operator strength reduction, called OSR. OSR improves upon an earlier algorithm of Allen, Cocke, and Kennedy [Allen et al. 1981]. OSR operates on the static single assignment (SSA) form of a procedure [Cytron et al. 1991]. By taking advantage of the properties of SSA form, we have derived an algorithm that is simple to understand, quick to implement, and, in practice, fast to run. Its asymptotic complexity is, in the worst case, the same as the Allen, Cocke,and Kennedy algorithm (ACK). OSR achieves optimization results that are equivalent to those obtained with the ACK algorithm. OSR has been implemented in several research and production compilers.

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 size of compiled code is increasingly important. Similarly, in mobile and network computing, the need to transmit an executable before running it places a premium on code size. Our work focuses on reducing the size of a program's code segment, using pattern-matching techniques to identify and coalesce together repeated instruction sequences. In contrast to other methods, our framework preserves the ability to run program executables directly, without an intervening decompression stage. Our compression framework is integrated into an industrial-strength optimizing compiler, which allows us to explore the interaction between code compression and classical code optimization techniques, and requires that we contend with the difficulties of compressing previously optimized code. The specific contributions in this paper include a comprehensive experimental evaluation of code compression for a Risc-like architecture, a more powerful pattern-matching scheme for improved identification of repeated code fragments, and a new form of profile-driven code compression that reduces the speed penalty arising from compression.

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 primary limit on the compiler's ability to improve memory behavior is its imperfect knowledge about the run-time behavior of the program. The compiler cannot completely predict runtime access patterns.There is an exception to this rule. During the register allocation phase, the compiler often must insert substantial amounts of spill code; that is, instructions that move values from registers to memory and back again. Because the compiler itself inserts these memory instructions, it has more knowledge about them than other memory operations in the program.Spill-code operations are disjoint from the memory manipulations required by the semantics of the program being compiled, and, indeed, the two can interfere in the cache. This paper proposes a hardware solution to the problem of increased spill costs---a small compiler-controlled memory (CCM) to hold spilled values. This small random-access memory can (and should) be placed in a distinct address space from the main memory hierarchy. The compiler can target spill instructions to use the CCM, moving most compiler-inserted memory traffic out of the pathway to main memory and eliminating any impact that those spill instructions would have on the state of the main memory hierarchy. Such memories already exist on some DSP microprocessors. Our techniques can be applied directly on those chips.This paper presents two compiler-based methods to exploit such a memory, along with experimental results showing that speedups from using CCM may be sizable. It shows that using the register allocation's coloring paradigm to assign spilled values to memory can greatly reduce the amount of memory required by a program.

Static Single Assignment (SSA) form is a program representation that is becoming increasingly popular for compiler-based code optimization. In this paper, we address three problems that have arisen in our use of SSA form. Two are variations to the SSA construction algorithms presented by Cytron et al.1 The first variation is a version of SSA form that we call ‘semi-pruned’ SSA. It offers an attractive trade-off between the cost of global data-flow analysis required to build ‘pruned’ SSA and the large number of unused ϕ-functions found in minimal SSA. The second variation speeds up the program renaming process by efficiently manipulating the stacks of names used during renaming. Our improvement reduces the number of pushes performed, in addition to more efficiently locating the stacks that should be popped. To convert code in SSA form back into an executable form, the compiler must use an algorithm that replaces ϕ-functions with appropriately-placed copy instructions. The algorithm given by Cytron et al. for inserting copies produces incorrect results in some situations; particularly in cases like instruction scheduling, where the compiler may not be able to split ‘critical edges’, and in the aftermath of optimizations that aggressively rewrite the name space, like some forms of global value numbering.2 We present a new algorithm for inserting copy instructions to replace ϕ-functions. It fixes the problems that we have encountered with the original copy insertion algorithm. We present experimental results that demonstrate the effectiveness of the first two improvements not only during the construction of SSA form, but also in the time saved by subsequent optimization passes that use a smaller representation of the program. © 1998 John Wiley & Sons, Ltd.

The design and implementation of an interference graph is critical to the performance of a graph-coloring register allocator. The cost of constructing and manipulating the interference graph dominates the overall cost of allocation. The literature on graph-coloring register allocation suggests the use of a bit matrix coupled with lists of edges to represent the graph.1–3 Recently, George and Appel4 claimed that their tests show better results using a hash table. This paper examines the trade-offs between these two approaches. Our experiments were conducted with an optimistic, Chaitin-style register allocator.5 We believe, however, that the lessons learned in the experiment are applicable to any program that needs to build and manipulate large graphs. For most graphs, we obtained our best results, in terms of both time and space, using a modification of the data structures suggested by both Chaitin and Briggs that we call the split bit-matrix method. On a few large graphs, we found that a closed hash-table with the universal hash function suggested by Cormen et al.6 ran faster than the split bit-matrix method. We found one case where it used less space. This suggests that the split bit-matrix technique should be the method of choice, unless the compiler regularly encounters large interference graphs. In that case, the best strategy might be to implement both data structures behind a common interface, and switch between them based on graph size. © 1998 John Wiley & Sons, Ltd.

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 work has been published that focuses on the analysis of pointers, little has appeared that uses the results of such analysis to improve the code compiled for C. This paper examines the problem of register promotion in C and presents experimental results showing that it can have dramatic effects on memory traffic.

Value numbering is a compiler-based program analysis method that allows redundant computations to be removed. This paper compares hash-based approaches derived from the classic local algorithm1 with partitioning approaches based on the work of Alpern, Wegman and Zadeck.2 Historically, the hash-based algorithm has been applied to single basic blocks or extended basic blocks. We have improved the technique to operate over the routine's dominator tree. The partitioning approach partitions the values in the routine into congruence classes and removes computations when one congruent value dominates another. We have extended this technique to remove computations that define a value in the set of available expressions (AVAIL).3 Also, we are able to apply a version of Morel and Renvoise's partial redundancy elimination4 to remove even more redundancies. The paper presents a series of hash-based algorithms and a series of refinements to the partitioning technique. Within each series, it can be proved that each method discovers at least as many redundancies as its predecessors. Unfortunately, no such relationship exists between the hash-based and global techniques. On some programs, the hash-based techniques eliminate more redundancies than the partitioning techniques, while on others, partitioning wins. We experimentally compare the improvements made by these techniques when applied to real programs. These results will be useful for commercial compiler writers who wish to assess the potential impact of each technique before implementation. © 1997 John Wiley & Sons, Ltd.

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 code may require iterating optimizations until a fixed point is reached. Combining these phases can lead to the discovery of more facts about the program, exposing more opportunities for optimization. This article 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 frame work provides insight into when a combination yields better results. To make the ideas more concrete, this article presents a framework for combining constant propagation, value numbering, and unreachable-code elimination. It is an open question as to what other frameworks can be combined in this way.

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 increase the effectiveness of partial redundancy elimination. By imposing a discipline on the choice of names and the shape of expressions, we are able to expose more redundancies.

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 extends Chaitin's treatment of rematerialization to handle a larger class of values. These techniques are complementary. Optimistic coloring decreases the number of procedures that require spill code and reduces the amount of spill code when spilling is unavoidable. Rematerialization lowers the cost of spilling some values. This paper describes both of the techniques and our experience building and using register allocators that incorporate them. It provides a detailed description of optimistic coloring and rematerialization. It presents experimental data to show the performance of several versions of the register allocator on a suite of FORTRAN programs. It discusses several insights that we discovered only after repeated implementation of these allocators.

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 copies. By carefully partitioning the calls, the compiler ensures that each clone inherits an environment that allows for better code optimization. This paper presents a three-phase algorithm for deciding when to clone a procedure. The algorithm seeks to avoid unnecessary code growth by considering how the information exposed by cloning will be used during optimization. We present a set of assumptions that bound both the algorithm's running time and code expansion.

The ParaScope parallel programming environment, developed to support scientific programming of shared-memory multiprocessors, is described. It includes a collection of tools that use global program analysis to help users develop and debug parallel programs. The focus is on ParaScope's compilation system. The compilation system extends the traditional single-procedure compiler by providing a mechanism for managing the compilation of complete programs. The ParaScope editor brings both compiler analysis and user expertise to bear on program parallelization. The debugging system detects and reports timing-dependent errors, called data races, in execution of parallel programs. A project aimed at extending ParaScope to support programming in FORTRAN D, a machine-independent parallel programming language for use with both distributed-memory and shared-memory parallel computers, is described.>

This paper examines a problem that arises during global register allocation – rematerialization. If a value cannot be kept in a register, the allocator should recognize when it is cheaper to recompute the value (rematerialize it) than to store and reload it. Chaitin's original graph-coloring allocator handled simple instance of this problem correctly. This paper details a general solution to the problem and presents experimental evidence that shows its importance.

Abstract 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 interaction between inline substitution and aggressive code optimization. To understand this relationship, we used commercially available FORTRAN optimizing compilers as the basis for our study. This paper reports on the effectiveness of the various compilers at optimizing the inlined code. We examine both the runtime performance of the resulting code and the compile‐time performance of the compilers. This work can be viewed as a study of the effectiveness of inlining in modern optimizers; alternatively, it can be viewed as one data point on the overall effectiveness of modern optimizing compilers. We discovered that, with optimizing FORTRAN compilers, (1) object‐code growth from inlining is substantially smaller than source‐code growth, (2) compile‐time growth from inlining is smaller than source‐code growth, and (3) the compilers we tested were not able to capitalize consistently on the opportunities presented by inlining.

We describe an improvement to a heuristic introduced by Chaitin for use in graph coloring register allocation. Our modified heuristic produces better colorings, with less spill code. It has similar compile-time and implementation requirements. We present experimental data to compare the two methods.

We present a new algorithm for computing interprocedural aliases due to passing parameters by reference. This algorithm runs in O(N2+NE) time and, when combined with algorithms for alias-free, flow-insensitive data-flow problems, yields algorithms for solution of the general flow-insensitive problems that also run in O(N2+NE) time.

We present a new method for solving Banning's alias-free flow-insensitive side-effect analysis problem. The algorithm employs a new data structure, called the binding multi-graph, along with depth-first search to achieve a running time that is linear in the size of the call multi-graph of the program. This method can be extended to produce fast algorithms for data-flow problems with more complex lattice structures.

In spite of substantial progress in the theory of interprocedural data flow analysis, few practical compiling systems can afford to apply it to produce more efficient object programs. To perform interprocedural analysis, a compiler needs not only the source code of the module being compiled, but also information about the side effects of every procedure in the program containing that module, even separately compiled procedures. In a conventional batch compiler system, the increase in compilation time required to gather this information would make the whole process impractical. In an integrated programming environment, however, other tools can cooperate with the compiler to compute the necessary interprocedural information incrementally . as the program is being developed, decreasing both the overall cost of the analysis and the cost of individual compilations. A central goal of the R n project at Rice University is to construct a prototype software development environment that is designed to build whole programs, rather than just individual modules. It employs interprocedural analysis and optimization to produce high-quality machine code for whole programs. This paper presents an overview of the methods used by the environment to accomplish this task and discusses the impact of these methods on the various environment components. The responsibilities of each component of the environment for the preparation and use of interprocedural information are presented in detail.

Compilers for languages with call-by-reference formal parameters must deal with aliases arising from the renaming effects at call sites. This paper presents a set of techniques for analyzing aliasing patterns. The analysis is divided into detecting the introduction of aliases and tracking their propagation. The algorithm for introduction analysis is simple enough to be performed in a structured editor or parser. A data flow analysis framework is given for the propagation problem, making it possible to solve using standard algorithms from global data flow analysis. Several optimizations are shown which can shrink the size of the problem, and extensions are given to handle ALGOL-style name scoping. Finally, this technique is compared to an alternative implementation strategy and an approximate technique.