Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-06-11
2002-07-30
Khatri, Anil (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S148000, C717S153000
Reexamination Certificate
active
06427234
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally concerns compilers for generating computer code, and more particularly, dynamic-compilation systems that are used to generate executable instructions for selected parts of computer programs at run time.
BACKGROUND OF THE INVENTION
Selective dynamic compilation transforms selected parts of computer programs at run time, using information available only at run time to optimize execution of the programs. A compilation strategy is employed during selective dynamic compilation to enable the code-compilation process to be completed in stages—at static compile time, at link time, at load time, and (on demand) at run time. By delaying a portion of the compilation process, it is possible to take advantage of information available only at the later stages, with the goal of improving performance of the resulting code.
Postponing a portion of the compilation process until run time is called selective dynamic compilation and should not be confused with complete dynamic compilation, wherein all program compilation is done at run time. (Recently introduced “just in time” compilers for JAVA are examples of complete dynamic compilers.) As used in this specification and in the claims that follow, the term “dynamic compilation” refers only to selective dynamic compilation and not to complete dynamic compilation.
Value-specific selective dynamic compilers derive their benefits by optimizing parts of programs for particular run-time computed values of invariant variables and data structures (called run-time constants), in effect, performing a kind of dynamic constant propagation and folding. Programs and program portions that are suitable for selective dynamic compilation include: (a) highly parameterized computations that use a significant amount of time consulting parameters, but often run using the same parameter settings; (b) programs with many similar subcomputations; (c) programs of highly interpretive nature, e.g., circuit and other simulators, where specializations remove the time to scan the object being simulated; and (d) database query search algorithm. Additional proposed applications for selective, value-specific dynamic compilation include specializing architectural simulators for the configuration being simulated, language interpreters for the program being interpreted, rendering engines for scene-specific state variables, numeric programs for dimensions and values of frequently used arrays, and critical paths in operating systems for the type of data being processed and the current state of the system. Trends in software engineering that are moving toward dynamic reconfigurability, such as parameterization for reuse and portability across different hardware architectures, also imply a promising role for dynamic compilation.
The principle challenge and trade-off in selective dynamic compilation is achieving high-quality dynamically generated code at low run-time cost, since the time to perform run-time compilation and optimization must be recovered before any benefit from dynamic compilation can be obtained. Consequently, a key design issue in developing an effective dynamic-compilation system is the method for determining where, when, and on what run time state to apply dynamic compilation. Ideally, the compiler would make these decisions automatically, as in other (static) compiler optimizations; however, this ideal is beyond current state of the art for general-purpose systems.
Instead, current dynamic-compilation systems rely on some form of programmer direction to indicate where dynamic compilation is to be applied to program code. Some systems take an imperative or operational approach to user direction, requiring the user to explicitly construct, compose, and compile program fragments at run time. Imperative approaches can express a wide range of optimizations, but impose a substantial burden on the programmer to manually program the optimizations. Moreover, such a programming burden makes it difficult to effectively apply imperative approaches to large applications. An example of an imperative system, called “C,” is described by D. R. Engler, W. C. Hsieh, and M. F. Kaashoek in “C: A language for high-level, efficient, and machine-independent dynamic code generation,” Conference Record of POPL'96: 23rd ACM SIGPLAN_SIGACT Symposium on Principles of Programming Languages, pp. 131-144, January 1996.
As an alternative to the imperative approach, several dynamic-compilation systems take a declarative or transformational approach, with user annotations guiding the dynamic compilation process. Examples of declarative systems include “Tempo,” described by C. Consel and F. Nöel in “A general approach for run-time specialization and its application to C,” Conference Record of POPL'96: 23
rd
ACM SIGPLAN_SIGACT Symposium on Principles of Programming Languages, pp. 131-144, January 1996; and “Fabius,” described by M. Leone and P. Lee in “Optimizing ML with Run-Time Code Generation, Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 137-148, May 1996. Each of these declarative approaches adapts ideas from partial evaluation, expressing dynamic compilation as run-time specialization, where known or static values correspond to a run-time state for which programs are specialized. To keep dynamic compilation costs low, these systems preplan the possible effects of dynamic optimizations statically, producing a specialized dynamic compiler tuned to the particular part of the program being dynamically optimized; this sort of preplanning is known as staging the optimization. Declarative approaches offer the advantages of an easier interface to dynamic compilation for the programmer and easier program understanding and debugging. However, declarative systems usually offer less expressiveness and control over the dynamic compilation process than do imperative systems. Furthermore, the limitations of previous declarative systems have prevented them from coping effectively with the more involved patterns of control and data flow found in some small and most large applications, causing them to miss optimization opportunities or forcing substantial rewriting of the code to fit the limitations of the system. It would therefore be desirable to develop a system and associated programming interface that provides the ease of use of a declarative system, with the control and flexibility of an imperative-type system.
The cost of dynamic code generation must be recovered before benefits from specialized code can be realized. One way to recover this cost is to reuse the specialized code when a program's execution path reaches the same point. Unfortunately, it is not always possible to do this, because the values of the static variables for which the code was specialized may have changed, rendering the specialized code unreusable. Reuse is achieved by caching the specialized code when it is dynamically generated and then doing a cache lookup, based on the values of the static variables, to retrieve it when the code is executed again. Some prior art systems cache specialized code only at function entry points. This limitation restricts the granularity of code specialization and reuse to entire functions, eliminating opportunities for reusing portions of a function. Other systems aggressively reuse code by caching it at every specialized jump target. However, such frequent cache lookups cause unacceptable overhead in run-time code. It would therefore be desirable to produce a system that most efficiently uses caching of specialized code portions and associated cache lookups.
Another shortfall of the prior art systems is that they do not provide on-demand specialization at a sub-function level. On-demand specialization, also known as lazy specialization, enables specialization to be deferred until a portion of the program to be specialized is assured of being executed, thereby reducing both the amount of specialized code produced and the overhead required to produce such code. Furthermore,
Chambers Craig
Eggers Susan J.
Grant Brian K.
Mock Markus
Philipose Matthai
Anderson Ronald M.
Khatri Anil
University of Washington
LandOfFree
System and method for performing selective dynamic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing selective dynamic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing selective dynamic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2881400