Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-10-08
2002-11-26
Dam, Tuan Q. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S147000, C717S148000, C717S159000, C712S244000
Reexamination Certificate
active
06487716
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to computer programming, and, in particular, to methods and apparatus for a compiler (either static or dynamic), programming development environment or tool, or programmer to enable transformations of a program that involve code motion across instructions that may throw an exception, while strictly preserving the precise exception semantics of the program or parts of the program that existed before the transformation.
BACKGROUND OF THE INVENTION
The present invention describes methods and apparatus for a compiler, programming development environment or tool, or programmer to enable transformation of a program or parts of a program written in some machine language so as to eliminate or reduce the impact of precise exceptions on optimizations that require instruction reordering.
Some programming languages, for example, Java™ (e.g., see J. Gosling, B. Joy, G. L. Steele, “The Java Language Specification (Java Series),” Addison-Wesley Publishing Company, Reading, Mass. 1996), Ada, Modula-3, and C++ support exceptions, which represent abnormal execution conditions arising, for instance, out of violations of the semantic constraints of the language. We shall refer to an exception as being thrown or raised at a point where it occurs, and as being caught at the exception handler, which is the point to which control is transferred when the exception is thrown. The actual mechanism for determining where the control is transferred in case of an exception being thrown is part of the specification of a programming language. For example, Java™ defines try-catch blocks that govern control flow when an exception is thrown by a statement—execution proceeds to the closest dynamically enclosing catch block that handles the exception. An exception may be thrown explicitly, such as via a throw statement in Java™, or implicitly, based on checks defined by the programming language. For instance, Java™ defines some runtime exceptions such as NullPointerException, IndexOutOfBoundsException, and ArithmeticException, and many instructions such as array-access instructions, object field-access instructions, and integer division instructions may throw one of the predefined runtime exceptions. We refer to an instruction that may throw an exception as a potentially excepting instruction (PEI in short).
In some languages, like Java™, exceptions are defined to be precise, which implies that:
1) exception(s) must be thrown in the same order as specified by the original program; and
2) when an exception is thrown, the program state observable at the entry of the corresponding exception handler must be the same as in the original program.
Compilers often use a representation called the Dependence Graph to represent constraints on code motion and instruction reordering. The nodes in a dependence graph typically represent statements, and edges represent dependence constraints. Compilers for languages supporting precise exceptions satisfy the precise exception requirement by imposing the following dependence constraints, described further in J.-D. Choi, D. Grove, M. Hind, and V. Sarkar, “Efficient and precise handling of exceptions for analysis of Java programs,” ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, September 1999:
1) dependences among PEIs, referred to as exception-sequence dependences, which ensure that the correct exception is thrown by the code, and
2) dependences between writes to non-temporary variables and PEIs, referred to as write-barrier dependences, which ensure that a write to a non-temporary variable is not moved before or after a PEI, in order to maintain the correct program state if an exception is thrown. These dependences hamper a wide range of program optimizations in the presence of PEIs, such as instruction scheduling, instruction selection (across a PEI), loop transformations, and parallelization. This impedes the performance of programs written in languages like Java™, in which PEIs are quite common.
A reference to a variable is said to be live at a program point if the value of the variable is used after that program point on some control flow path to the exit before it is redefined.
Let us use the Java code segment shown in
FIG. 3
as an example.
FIG. 4
shows the low-level intermediate representation (LIR) of the Java code in FIG.
3
. Compilers frequently use LIR representation of the input program, similar to the LIR in
FIG. 4
, during the analysis and optimization of the program.
FIG. 5
shows the dependence graph of the LIR in FIG.
4
. Compilers frequently use dependence graphs, similar to
FIG. 5
, for analysis and optimization of programs. We define the dependence locus of a node N
i
in the dependence graph to be the set of nodes that are transitively reachable from N
i
via dependence edges. Each node in the dependence graph corresponds to a statement (i.e., line) in the LIR. The column titled Dependence Graph Node in the LIR shows the corresponding node in the dependence graph of the statement.
In the dependence graph in
FIG. 5
, exception-sequence dependences are shown as dashed lines, while write-barrier dependences are shown as dotted edges, such as from n
9
to P
10
. The longest path of the graph shown in the figure has a length of 10: P
1
, P
5
, n
6
, P
7
, n
8
, n
9
, P
10
, n
11
, P
12
, n
13
, and n
14
.
A program with more than one thread (locus of control) is said to be multithreaded. In a multithreaded application, the shared program state when an exception is thrown can be visible not only to the exception handler, if any exists, of the exception-throwing thread, but also potentially to any other threads that can access the program state. Furthermore, an exception not caught by a handler terminates only the exception-throwing thread, and other threads can still access the shared program state affected by the terminating thread and continue their execution.
Allowing for uncontrolled accesses (read or write) to shared program state by multiple threads usually renders a program incorrect or, at best, hard to understand and develop. Most languages, therefore, provide mechanisms for controlling accesses to shared program state, i.e., shared variables. A synchronized region, such as a synchronized block or method in Java, is used in which to access a shared variable. Some languages go even further to specify that for a program to be correct, accesses to shared variables should be controlled “properly,” usually implying that the program should obey the CREW protocol—Concurrent Read, Exclusive Write. In a CREW protocol, there can be as many concurrent read accesses as long as there is no concurrent write access, but no read or write accesses can be concurrent with another write access to the same variable. We refer to languages that force parallel programs to obey the CREW protocol or which do not specify any constraints on the ordering of data accesses in regions not obeying the CREW protocol, as languages supporting weak consistency. We refer to other languages, which do impose constraints on the ordering of data accesses even in regions not obeying the CREW protocol, as supporting strong consistency.
Many compilers use a representation called a call graph to analyze an entire program. A call graph has nodes representing procedures, and edges representing procedure calls. We use the term procedure to refer to subroutines, functions, and also methods in object-oriented languages. A direct procedure call, where the callee (called procedure) is known at the call site, is represented by a single edge in the call graph from the caller to the callee. A procedure call, where the callee is not known, such as a virtual-method call in an object-oriented language or an indirect call through a pointer, is represented by edges from the caller to each possible callee. It is also possible that given a particular (callee) procedure, all callers of it may not be known. In that case, the call graph would conservatively put edges from all possible callers to that call
Choi Jong-Deok
Gupta Manish
Hind Michael
Cameron Douglas W.
Dam Tuan Q.
International Business Machines - Corporation
Kendall Chuck
Ryan & Mason & Lewis, LLP
LandOfFree
Methods and apparatus for optimizing programs in the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for optimizing programs in the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for optimizing programs in the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2989205