Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 128 papers for “Interprocedural optimization”

Interprocedural optimization: eliminating unnecessary recompilation

Michael Burke · 1993

While efficient new algorithms for interprocedural data-flow analysis have made these techniques practical for use in production compilation systems,a new problem has arisen: collecting and using interprocedural information in a compiler introduces subtle dependence among the proceduresof a program. If the compiler dependson interprocedural information to optimize a given module, a subsequentediting changeto another module in the program may changethe interprocedural information and necessitaterecompilation. To avoid having to recompile every module in a program in responseto a single editing changeto one module, we have developed techniquesto more precisely determine which compilations have actually beeninvalidated by a changeto the program’s source.This paper presents a general recoi-npzlatton test to determine which proceduresmust be compiled in responseto a series of editing changes.Three different implementation strategies, which demonstrate the fundamental tradeoff between the cost of analysis and the precision of the resulting test, are also discussed.

Cited by 0

Automatic Interprocedural Optimization for Object-Oriented Languages

John Plevyak, Andrew A. Chien · 1996

The structure of object-oriented programs differs from that of procedural programs, requiring special compilation techniques to obtain efficiency. Object-orientation introduce additional layers of abstraction which separate the implementations of data structures and algorithms from their points of use. The result is smaller functions, increased data dependence of control flow, and an increase in potential aliasing. We present an automatic interprocedural optimization framework, which resolves these differences through interprocedural analysis and transformation; enabling a dynamically-typed pure object-oriented language to match the performance of C on a set of standard procedural benchmarks. For two standard object-oriented benchmarks we also compare this framework to the supplied annotations (e.g. inline, virtual and templates) for the hybrid OO-procedural language C++ [51], and show that the framework obtains up to 6 times the performance of the annotated C++ code.

Cited by 0

Interprocedural Load Elimination for Dynamic Optimization of Parallel Programs

Rajkishore Barik, Vivek Sarkar · 2009

Load elimination is a classical compiler transformation that is increasing in importance for multi-core and many-core architectures. The effect of the transformation is to replace a memory access, such as a read of an object field or an array element, by a read of a compiler-generated temporary that can be allocated in faster and more energy-efficient storage structures such as registers and local memories (scratchpads). Unfortunately, current just-in-time and dynamic compilers perform load elimination only in limited situations. In particular, they usually make worst-case assumptions about potential side effects arising from parallel constructs and method calls. These two constraints interact with each other since parallel constructs are usually translated to low-level runtime library calls. In this paper, we introduce an interprocedural load elimination algorithm suitable for use in dynamic optimization of parallel programs. The main contributions of the paper include: a) an algorithm for load elimination in the presence of three core parallel constructs -- async, finish, and isolated, b) efficient side-effect analysis for method calls, c) extended side-effect analysis for parallel constructs using an isolation consistency memory model, and d) performance results to study the impact of load elimination on a set of standard benchmarks using an implementation of the algorithm in Jikes RVM for optimizing programs written in a subset of the X10 v1.5 language. Our performance results show decreases in dynamic counts for getfield operations of up to 99.99%, and performance improvements of up to 1.76times on 1 core, and 1.39times on 16 cores, when comparing the algorithm in this paper with the load elimination algorithm available in Jikes RVM.

Cited by 39

Call Forwarding: A Simple Interprocedural Optimization Technique for Dynamically Typed Languages

Koen De Bosschere, Saumya Debray, David Gudeman et al. · 1994

This paper discusses call forwarding, a simple interprocedural optimization technique for dynamically typed languages. The basic idea behind the optimization is straightforward: find an ordering for the "entry actions" of a procedure, and generate multiple entry points for the procedure, such that the savings realized from different call sites bypassing different sets of entry actions, weighted by their estimated execution frequencies, is as large as possible. We show that the problem of computing optimal solutions to arbitrary call forwarding problems is NP-complete, and describe efficient heuristics for the problem. Experimental results indicate that (i) the heuristics are effective, in that the solutions produced are generally optimal or close to optimal; and (ii) the resulting optimization is effective, in that it leads to significant performance improvements for a number of benchmarks tested. The work of K. De Bosschere was supported by the National Fund for Scientific Research ...

Cited by 0

A framework for interprocedural optimization in the presence of dynamic class loading

Vugranam C. Sreedhar, Michael Burke, Jong-Deok Choi · 2000

Dynamic class loading during program execution in the Java Programming Language is an impediment for generating code that is as efficient as code generated using static whole-program analysis and optimization. Whole-program analysis and optimization is possible for languages, such as C++, that do not allow new classes and/or methods to be loaded during program execution. One solution for performing whole-program analysis and avoiding incorrect execution after a new class is loaded is to invalidate and recompile affected methods. Runtime invalidation and recompilation mechanisms can be expensive in both space and time, and, therefore, generally restrict optimization.

Cited by 65Open access

Interprocedural control flow analysis of first-order programs with tail-call optimization

Saumya Debray, Todd A. Proebsting · ACM Transactions on Programming Languages and Systems · 1997

Knowledge of low-level control flow is essential for many compiler optimizations. In systems with tail-call optimization, the determination of interprocedural control flow is complicated by the fact that because of tail-call optimization, control flow at procedure returns is not readily evident from the call graph of the program. This article shows how interprocedural control-flow analysis of first-order programs can be carried out using well-known concepts from parsing theory. In particular, we show that context-insensitive ( or zeroth-order) control-flow analysis corresponds to the notion of FOLLOW sets in context-free grammars, while context-sensitive (or first-order) control-flow analysis corresponds to the notion of LR(1) items. The control-flow information so obtained can be used to improve the precision of interprocedural dataflow analyses as well as to extend certain low-level code optimizations across procedure boundaries.

Cited by 16Open access

Microsoft Research Video 104636: A Framework for Unrestricted Whole-Program Optimization

Microsoft Research · Bulletin of Miscellaneous Information (Royal Gardens Kew) · 2005

In current compilers, the vast majority of optimization routines operates within procedure boundaries. Since individual procedures do not usually present the ideal scope to optimization, significant performance enhancement opportunities are left unrealized. Although aggressive inlining and interprocedural analysis can alleviate this problem, these can be applied only sparingly, so as to avoid excessive code growth and compile-time dilation. Furthermore, the compiler's ability to exploit optimization opportunities across procedures is constrained by the need to maintain the program's procedure-based structure. In order to eliminate these restrictions, this talk proposes a novel compilation framework called Procedure Boundary Elimination (PBE). By generalizing interprocedural analysis algorithms and utilizing appropriate intermediate representations, PBE enables all optimization and analysis routines to operate freely across procedure boundaries. This enables the compiler to reorganize the program into arbitrarily shaped interprocedural compilation units, according to its compile-time and optimization needs. By using the proper encapsulation techniques, PBE allows each unit thus selected to be analyzed and optimized in isolation, thereby eliminating the scalability problems of traditional interprocedural optimization. Finally, the PBE framework leverages both existing and novel targeted code duplication techniques, so as to achieve the specialization benefits of inlining while avoiding unnecessary code growth. Overall, PBE achieves a superset of the benefits of inlining and traditional interprocedural optimization, while limiting their associated costs. ©2005 Microsoft Corporation. All rights reserved.

Cited by 0

Set constraints for destructive array update optimization

M. Wand, William Clinger · 2002

Destructive array update optimization is critical for writing scientific codes in functional languages. We present set constraints for an interprocedural update optimization that runs in polynomial time. This is a multi pass optimization, involving interprocedural flow analyses for aliasing and liveness. We characterize the soundness of these analyses using small step operational semantics. We have also proved that any sound liveness analysis induces a correct program transformation.

Cited by 13

Set constraints for destructive array update optimization

Mitchell Wand, William Clinger · Journal of Functional Programming · 2001

Destructive array update optimization is critical for writing scientific codes in functional languages. We present set constraints for an interprocedural update optimization that runs in polynomial time. This is a multi-pass optimization, involving interprocedural flow analyses for aliasing and liveness. We characterize and prove the soundness of these analyses using small-step operational semantics. We also prove that any sound liveness analysis induces a correct program transformation.

Cited by 15Open access

The impact of interprocedural analysis and optimization on the design of a software development environment

Keith D. Cooper, Ken Kennedy, Linda Torczon · ACM SIGPLAN Notices · 1985

One of the primary goals of the IR n programming environment project is to mount a concerted attack on the problems of performing interprocedural analysis and optimization in a compiler. Few commercial optimizing compilers employ interprocedural techniques because the cost of gathering the requisite information in a traditional compiler is too great. Computing the side effects of a procedure call requires detailed knowledge of the internals of both the called procedure and any procedures invoked either directly or indirectly from it. Thus, the compiler potentially needs information about the internals of every procedure to determine the side effects of procedure calls, even separately compiled procedures. Gathering this information would require examining the source of every procedure in the program - an expensive process, particularly unfortunate since the primary goal of separate compilation is to reduce the amount of recompilation required in response to changes in an individual procedure. The existence of a software development environment like the IR n programming environment [HoKe 84] changes the compilation process enough to make computing such information palatable. Since all modules are developed and all programs are defined using tools of the environment, these tools can cooperate to record the information necessary to do a good job of interprocedural analysis and optimization. Whenever the compiler needs information about possible side effects of a particular procedure, it can simply extract this information from the environment's central database. Because the only mechanism for changing modules or programs is through the tools provided by the environment, the compiler is assured that it will be notified of any changes. Thus, it can use information derived from previous analysis with certain knowledge that the information reflects the current state of the program and its procedures.

Cited by 0Open access

Interprocedural compilation of Fortran D for MIMD distributed-memory machines

Mary Hall, Seema Hiranandani, Ken Kennedy et al. · 2003

Algorithms exist for compiling Fortran D for MIMD (multiple-instruction multiple-data) distributed-memory machines, but they are significantly restricted in the presence of procedure calls. The authors present interprocedural analysis, optimization, and code generation algorithms for Fortran D that limit compilation to only one pass over each procedure. This is accomplished by collecting summary information after edits, and then compiling procedures in reverse topological order to propagate necessary information. Delaying instantiation of the computation partition, communication, and dynamic data decomposition is key to enabling interprocedural optimization. Recompilation analysis preserves the benefits of separate compilation. Empirical results show that interprocedural optimization is crucial in achieving acceptable performance for a common application.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 24

Computation of interprocedural control dependence

Saurabh Sinha, Mary Jean Harrold, Gregg Rothermel · 1998

Program-dependence information is useful for a variety of applications, such as software testing and maintenance tasks and code optimization. Properly defined, control and data dependences can be used to identify semantic dependences. To function effectively on whole programs, tools that utilize dependence information require information about interprocedural dependences: dependences that are identified by analyzing the interactions among procedures. Many techniques for computing interprocedural data dependences exist; however, virtually no attention has been paid to interprocedural control dependence. Analysis techniques that fail to account for interprocedural control dependences can suffer unnecessary imprecision and loss of safety. This paper presents a definition of interprocedural control dependence that supports the relationship of control and data dependence to semantic dependence. The paper presents two approaches for computing interprocedural control dependences, and empirical results pertaining to the use of those approaches.

Cited by 0

Intraprocedural Control Dependence

Saurabh Sinha, Mary Jean Harrold, Gregg Rothermel · 2008

Program-dependence information is useful for a variety of applications, such as software testing and maintenance tasks and code optimization. Properly defined, control and data dependences can be used to identify semantic dependences. To function effectively on whole programs, tools that utilize dependence information require information about interprocedural dependences: dependences that are identified by analyzing the interactions among procedures. Many techniques for computing interprocedural data dependences exist; however, virtually no attention has been paid to interprocedural control dependence. Analysis techniques that fail to account for interprocedural control dependences can su er unnecessary imprecision and loss of safety. This paper presents a definition of interprocedural control dependence that supports the relationship of control and data dependence to semantic dependence. The paper presents two approaches for computing interprocedural control dependences, and empirical results pertaining to the use of those approaches.

Cited by 0