Method for optimizing locks in computer programs

[0002] 1. Field of the Invention

[0003] The present invention relates to computer programming. In particular it is a method and variant of the method for a compiler (either static or dynamic), programming development environment or tool, or programmer to transform a program or part of a program so as to reduce the overhead of lock operations by either removing the lock operations or replacing them with simpler operations, while strictly preserving the exact semantics of the program or parts of the program that existed before the transformation.

[0004] 2. Background Description

[0005] Multithreaded programming languages, for example Java™ [5] and programs built from sequential languages but executing in a multithreaded environment, for example Posix [2] often use locking operations. These locking operations are used to enforce the constraint that only one thread of execution may have access to some resource—data, hardware, code, etc. at a time. A thread is a locus of control in a computing environment. In an object-oriented Language such as Java™, the lock is typically associated with an object and is used to ensure mutual exclusion in accessing that object. In those cases, the lock is regarded as a part of that object. (Java is a trademark of Sun Microsystems, Inc.)

[0006] Each lock has associated with it some storage that is used to implement the lock. This storage provides a flag to indicate if the lock has been acquired by anyone else. The lock can also provide a queue. The queue provides a place for a thread that attempts to acquire a lock that has already been acquired by another thread to wait for the lock to become free. A thread that is on a queue is quiescent, i.e. it is not actively executing. If a lock provides a queue, it must provide some mechanism for threads on the queue to be notified that they can exit the quiescent state and again attempt to acquire the lock. This mechanism is referred to as the notify operation. Locks may also have side effects associated with them. For example, in the Java™ programming language, or various run-time and hardware systems that implement a release consistency programming model [1], a locking operation must update the globally accessible copy of a variable if required by the semantics of programming language or release consistency model being implemented. Other side effects could include updating tables indicating which locks are held by the program, or providing a point for a breakpoint operation in a debugger. Locking operations, and the locks needed to support the locking operation, have a cost in both an increased execution time of the program and in the amount of computer storage necessary for the program to execute.

[0007] 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. The term “procedure” is used 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 callee.

[0008] Within a procedure, many compilers use a representation called the “control flow graph” (CFG). Each node in a CFG represents a “basic block” and the edges represent the flow of control among the basic blocks. A basic block is a straight-line sequence of code that has a single entry (at the beginning) and a single exit (at the end). A statement with a procedure, call does not disrupt a straight-line sequence of code. In the context of languages that support “exceptions”, such as Java™, the definition of a basic block is relaxed to include statements which may throw an exception. In those cases, there is an implicit possible control flow from a statement throwing an exception to the block of code handling the exception. The basic block is not forced to end at each such statement, and instead, such a basic block bb is said to have a flag bb.outEdgeInMiddle set to true.

[0009] A topological sort order enumeration of nodes in a graph refers to an enumeration in which, if the graph contains an edge from node x to node y, then x appears before y. If a graph has cycles, then such an enumeration is not guaranteed for nodes involved in a cycle. A reverse topological sort order lists nodes in the reverse order of a topological sort.

[0010] Prior art for a similar goal of reducing the synchronization costs of a program by a compiler or programming tool or environment can be found in the papers [3,4,5,6,8,9,10,11,12,13]. These methods do not perform a class of optimizations, that of removing synchronization from objects acted upon by mutual exclusion, or mutex locks, based on the scope in which the lock is accessed. Furthermore, these methods do not handle programs with explicit constructs for multithreading and exceptions (e.g. “try-catch” constructs in Java™).

[0011] Prior art for reducing locking or synchronization operations by a compiler, programming tool or environment can be found in the papers [5,6,8,9,10,11,12,13]. The techniques described in these papers look at advance/wait, post/wait/clear and full/empty and extended full/empty or counter based synchronization. All of these synchronization methods enforce ordering (i.e., producer/consumer) synchronization, and the goal of these techniques is to transform programs so as to reduce the amount of ordering synchronization. Ordering synchronization is typified by post/wait/clear synchronization. A post operation on locks involves acquiring a lock on a key K, setting K to a known value (usually 1), and releasing the lock on K. A wait operation on key K involves repeatedly examining the value of K until it reaches the known value. A clear operation first acquires the lock on K, and then sets the value of K to another known value (usually 0). The clear operation is used to initialize K. Thus, by using clear/post/wait, an order can be enforced among the statements that pre cede the post and follow the wait. In particular, all statements before the post can be made to execute before any statement after the wait. All of the techniques described above use the ordering information. In particular, they determine what orders enforced by some ordering synchronization operations are enforced by other ordering synchronization operations, and eliminate the former synchronization operations. In some cases, a reduced number of new operations are introduced to eliminate all of the old operations [9], and in other cases the old state of keys are known after wait operations to reduce the number of initializing clear operations [6].

[0012] Prior art for reducing synchronization for mutex locks can be found in the papers [3,4]. In [3], the number of lock operations is reduced by a coarse-graining transformation, which leads to a single lock ensuring mutual exclusion for a coarser grain region, rather than multiple locks ensuring mutual exclusion for various finer-grain regions. While this reduces the number of lock operations, it leads to the problem of false exclusion, where operations that do not need mutual exclusion are also carried out in mutual exclusion. Therefore, the reduction in the number of lock operations comes at a price of potentially increased contention due to the lock. This transformation can sometimes degrade the performance of the program. In [4], the program is transformed so that multiple lock operations on the same object are replaced by a single lock operation on that object. While eliminating lock operations, this method has to retain at least one lock operation that achieves the same synchronization as the eliminated lock operations, i.e., it cannot eliminate mutex locks entirely from computation.

[0013] It is therefore an object of the invention to provide a method to reduce the number of locking operations that are performed in a computer pro,gram, by performing analysis to determine when these transformations can be applied, while preserving the strict semantics of the untransformed program.

[0014] It is another object of the invention to provide a method to simplify locking operations that cannot be completely removed by performing analysis to determine when these transformations can be applied, all while preserving the strict semantics of the untransformed program.

[0015] It is another object of the invention to provide a method for a compiler, programming development environment or tool, or programmer to transform a program or parts of a program written in some machine language so as to reduce the number of locking operations specified in the program or part of a program that must be performed when the program executes, or to reduce the cost of these operations with respect to increased execution time of the program and in the amount of computer storage necessary, or all of the above.

[0016] According to the invention, the locking operation is divided a into two parts:

[0017] 1. Those parts of the locking operation necessary to provide mutual exclusion, and to enqueue and dequeue threads that have attempted to acquire a lock already held by one or more other threads. These parts of the locking operation are referred to as the “synchronization” operation for mutual exclusion or alternatively, the “acquire” and “release” parts of the locking operation.

[0018] 2. Those parts of the locking operation that do other than synchronization for mutual exclusion. These parts of the locking operation are called the “side-effects.” In Java™, for example, the side-effects of a locking operation are the actions that update from the Java™ working memory to the Java™ main memory those values of shared variables that have changed since the last locking operation in this thread.

[0019] The present invention analyzes a program and uses the information formed by that analysis to transform the program, thereby reducing the number of locking operations that are performed in a program. If a locking operation cannot be completely removed from the program, the method substitutes a simpler operation for the locking operation. The ability to perform these transformations is important for two reasons:

[0020] 1. Locking operations increase the execution time of the programs. In some programs they may take a majority of the execution time.

[0021] 2. The necessity of enforcing the side effects can be significant, both in compile time and in increased memory traffic, I/O operations, and computer bus traffic. These costs can affect not only the performance of the program performing the locking operation but also other programs executing in the computer system.

[0022] Thus, the transformations described in this invention are important to decrease the execution time and storage requirements of the program being transformed, and to increase the performance of other programs executing on the system.

[0023] A locking operation with both synchronization for mutual exclusion and side effects is called as a “comprehensive” locking operation, and a locking operation with only synchronization for mutual exclusion is called a “simple” locking operation.

[0024] The preferred method of the present invention first analyzes all possible references to every object on which a locking operation is performed. The result of this analysis is, for each object, information about whether a locking operation can be performed on it in more than one thread. If the object is not accessed in multiple threads, and its locking operations are simple, the locking operations can be removed, and a process is performed to cause this transformation of the program. Next, the program is analyzed to determine for each comprehensive locking operation whether its side effects are required. When this analysis has been performed, the results are used to determine for each comprehensive locking operation, along with the results of the earlier analysis, whether

[0025] 1. the object is not locked in multiple threads, and the side effects of the locking operation are not needed, and the locking operation can be removed from the program;

[0026] 2. the object is not locked in multiple threads, but the side effects of the locking are needed, therefore only the side effect part of the locking operation needs to be performed, and the locking operation is replaced with a simpler form that does only the side effects;

[0027] 3. the object is locked in multiple threads, but the side effects of the comprehensive locking operation are not needed, therefore only the acquire and release parts of the locking operation needs to be performed, and the locking operation is replaced with a simpler form that does only the acquire and release parts of the locking operation; or

[0028] 4. the object is locked in multiple threads, and side effects of the comprehensive locking operation side effects are needed, thus the lock will not be optimized;

[0029] An alternative embodiment of the method performs the analysis of the procedure to determine the number of threads an object can be locked in, and removes simple locking operations that are on an object accessed in only a single thread. For comprehensive locking operations, if the object being locked is accessed in only a single thread, then the locking operation is; replaced by a simpler operation that only performs the locking operation side effects.

[0030] Another alternative embodiment of the method performs the analysis of the procedure to determine the number of threads an object can be locked in, and removes simple locking operations that are on an object accessed in only a single thread. For comprehensive locking operations, if the object is being accessed in only a single thread, and further analysis of the procedure determines that the side effects of the locking operation are not needed, the locking operation is removed. Other locking operations with side effects are unoptimized.

[0031] Another alternative embodiment of the method performs the analysis of the procedure to determine the number of threads an object can be locked in, and removes simple locking operations that are on an object accessed in only a single thread. Comprehensive locking operations are not optimized by this variant.

[0032] Another alternative embodiment of the method does not consider simple locking operations. For comprehensive locking operations, th, analysis and transformations are performed as in the original method.

[0033] Another alternative embodiment of the method does not consider simple locking operations, and only simplifies, but does not remove locks. For comprehensive locking operations, if the object being locked is accessed in only a single thread, then the locking operation is replaced by a simpler operation that only performs the locking operation side effects.

[0034] Another alternative embodiment of the method does not consider simple locking operations, and only removes but does not simplify locks. For comprehensive locking operations, if the object is being accessed in only a single thread, and the analysis of the method determines that the side effects of the locking operation are not needed, the locking operation is removed. Other locking operations with side effects are unoptimized.

[0035] The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:

[0036] FIG. 1 shows a block diagram of a compiler or compilation system that uses the method of this invention; and

[0037] FIG. 2 shows a block diagram of the method of this invention.

[0038] Referring now to the drawings, and more particularly to FIG. 1, there is shown an embodiment of the invention. A computer program 100 has been transformed into a list of instructions 102 by the front end or parser 101. The list of instructions can be represented by a graph (G(E,N,L)) whose nodes N are operations on variables, and whose edges E represent the flow of control between instructions. It is not necessary that they be encoded as such, and may be encoded as records in a file, as a logically flat structure, or by other means. The instructions are the instruction set of an intermediate compiler language or machine. L, the labels of the graph, contain auxiliary information about the edges and nodes in the graph. Some of the instructions at nodes on the graph are locking operations. The locking operations are of two types. The first type have no side effects. These locking operations are referred to as O_NThe second type have side effects. These locking operations are referred to as O_S. The subscript may be augmented with the number or symbol to further distinguish among different operations, as in, e.g., O_S,1or O_Sj. Both locking and unlocking operations are treated under the category of locking operation. Several other types of operations are of interest. The second are the references to variables in the program. The r^thstatic reference to the variable V is referred to as V_r. References may be either reads or writes. Another type of operation of interest is a procedure invocation.

[0039] The types of side effects performed by O_Slocking operations are now described. A write to a shared variable, or object, in an executing computer program is typically initially made to the local storage of the processor that performs the lock. Actions are then performed against the computer memory system to update a (logically) global, shared version of the variable or object with the results of the lock. This update is initiated before the next O_Soperation completes, and must be completed before the next O_Soperation commences. The side effect of the O_Soperation is to ensure that all updated to global shared variables or objects that were initiated in the same thread that is executing the O_Soperation must complete before the O_Soperation completes.

[0040] The list of instructions 102 is optionally utilized by compiler, programming tool, or programming development operations 103 that may precede the Escape Analysis and Lock Optimization phase 105. These optional phases may or may not transform the instruction stream encoded in G. The output of these phases is referred to as Gi 104, and is utilized by the Escape Analysis and Lock Optimization phase 105. The Escape Analysis and Lock Optimization phase transforms the program representation into G_o106 by possibly removing and adding instructions.

[0041] FIG. 2 illustrates the actions performed by the Escape Analysis and Lock Optimization phase 105. This phase is described in more detail below, and in pseudocode lines 301 to 1535. First, Escape Analysis 202 is performed. It transforms the input Gi 104 to the Escape Analysis and Lock Optimization phase by augmenting the symbol table of the intermediate representation with escape analysis information and also obtaining information about connections between objects and pointers in the program in the form of a “connection graph.” Essentially, for each object variable in the program, the escape analysis 202, further described below, identifies those locks that are accessed by just a single thread. This in turn serves as input 203 to the Optimization of Simple Locks phase 204, which transforms Gi 203, producing Gi′ 205. The transformations are discussed in more detail below, and in pseudocode lines 1901 to 1914, below. The output from this phase, Gi′ 205, and the escape analysis information found in the connection graph CG 205, is utilized by the Side Effect Analysis phase 206. This phase transforms its input 205 by augmenting the nodes of the control flow graph of the methods with the information described in the following structure,

[0042] where,

[0043] visited is true if this node is being visited in some traversal, and false otherwise,

[0044] IN is true if any predecessor of the node has a true output, and false otherwise,

[0045] OUT equals IN ΛKILL V GEN for the Node,

[0046] GEN is true if the node performs an operation on an object that is affected by the side effects of a locking operation with side effects, and false otherwise, and

[0047] KILL is false if the node operation is a comprehensive locking operation, and true otherwise.

[0048] The updated fields added to nodes of the control flow graph contain information about side effects that must be handled by each lock O_Sin 208. The data structures 207 are further transformed by the Optimization of Comprehensive Locks phase 208, described below in more detail and in pseudocode lines 2201 to 2225. The information of value to future passes is contained in G_o209, which is then passed to later compiler passes 107 as shown in FIG. 1.

[0049] The final transformed program resulting from the method of this invention can be fed into other phases of a compiler, programming environment or program development tool in step 108, for further manipulation, or it can be stored into a file for later retrieval, analysis or processing.

[0050] The preferred embodiment can be better understood by analyzing each step of the process using pseudocode. The preferred embodiment is described below, and then variants are described by noting how these alternative embodiments differ from the preferred embodiment. A discussion of the preferred escape analysis phase, as shown in FIG. 2, step 202, is first described below.

[0051] For analyzing program code, a representation called a connection graph CG=(N, E) is used, which is a directed graph with nodes (forming the set N) representing variables, and edges (forming the set E) representing reachability connections between variables. There are two kinds of nodes: “object” nodes representing variables for data allocated in a program (hereafter referred to as object variables), and “pointer” nodes, representing variables that point to object variables. Each object may have zero or more fields. In some languages, like Java™, fields of an object can only be pointer variables, whereas in some other languages like C++, a field of an object may either be a pointer or another object. A node corresponding to a field of an object variable is also referred to as a field node; it may fundamentally be a pointer node, or in languages that allow it, an object node. Given the connection graph of a procedure, the term “phantom node” is used to refer to a node corresponding to an object that is created outside the procedure and is reachable from a formal parameter. A node, during various stages of the analysis, may have one of the following three states: global_escape, arg_escape, or procedure_local. Each node, with two exceptions, is marked procedure_local when created initially. The first exception is for a phantom node, which is marked arg_escape. The second exception is for an object that may correspond to a thread (and the fields of that object), for example, in Java™, any object of a class that implements the Runnable interface. Such an object is marked global_escape upon creation, signifying that it escapes the thread in which it is created, i.e., this object itself is not thread-local. Even though each runnable object is marked global_escape the fields of that object are initially marked arg_escape. The terms “variables” and “nodes” are used interchangeably during the description of this invention, where it is clear that the node referred to in the connection graph represents the given variable.

[0052] The connection graph has three kinds of edges: “points-to” edges, “deferred edges”, and “field” edges. A points-to edge, denoted as x^P→y, may be created from a pointer variable x to an object variable y. A deferred edge, x^D→y, may be created from one pointer variable x to another pointer variable y. In languages that allow copying assignment from one object to another, such as C++, a deferred edge may exist from one object node to another. Such a deferred edge from an object O₁to an object O₂is interpreted as a set of edges from each field in O₁, to the corresponding field in O₂. A field edge, x^F→y, may be created from an object node x to a field node y.

[0053] A points-to path (PtPath(x,y)) in a connection graph is defined to be a sequence of edges x→x₁→x₂→. . . →y, where x is a pointer node and y is an object node. The length of a points-to path, (Length(PtPath(x,y))), is the number of object nodes (including y) encountered along the path PtPath(x, y). The notation x⁺¹→y denotes a points-to path, PtPath(x,y), with length one.

[0054] In order to illustrate the method of the invention pseudocode is used. The line number or step of the pseudocode is used in order to describe the method. The following pseudocode describes the process of escape analysis on a program P.

[0055] 301: EscapeAnalysis (G, CG) {

[0056] 302: Build call-graph, CallG, of program represented by G;

[0057] 303: foreach procedure n of program do

[0058] 304: n.NumNodes=0;

[0059] 305: n.NumPaths=0;

[0060] 306: end do

[0061] 307: Set WorkList=enumeration of nodes in CallG in reverse topological sort order;

[0062] 308: while WorkList not empty do

[0063] 309: Get first element n and delete it from WorkList;

[0064] 310: Call AnalyzeStackProcedure(n, CallG, WorkList);

[0065] 311: end do

[0066] 312: Set WorkList=enumeration of nodes in CallG in topological sort order;

[0067] 313: while WorkList not empty do

[0068] 314: Get first element n and delete it from WorkList;

[0069] 315: Call AnalyzeThreadProcedure(n, CallG, WorkList):

[0070] 316: end do

[0071] 317: In symbol table for G, mark all variables whose state is not global_escape as thread-local;

[0072] 318: }

[0073] The EscapeAnalysis procedure in line 301 takes as input a representation G of the program, and modifies G to record information about variables which are accessed only by a single thread, and also generates information about the connections between pointers and objects in various procedures of the program in the form of a connection graph CG. A call graph of the program is built in line 302. If a node in the call graph corresponds to a procedure which the system chooses not to analyze, it is marked no-analyze in the call graph. Examples of such procedures include native methods in Java™, which the system may choose not to analyze further, or procedures from a different module (such as a dynamically linked library) whose changes are not supposed to change the behavior of the program being generated. Lines 303 through 306 perform an initialization for each procedure that will be used later to check for convergence of the analysis. The nodes in the call graph are added in a reverse-topological sort order to a work list in line 304. In the absence of cycles in the call graph, this ensures that a callee procedure appears in the work list before any of its callers. Loop 308 iterates over each procedure in the work list until the work list is empty. The procedure n at the head of the work list is removed from the work list in line 309. It is analyzed by AnalyzeStackProcedure in line 310 to obtain a classification of each variable in the procedure into one of the following categories: global_escape, arg_escape and procedure_local. AnalyzeStackProcedure described further below, also puts each caller of procedure n back on the work-list if the classification of any variable changed during that invocation of AnalyzeStackProcedure. This ensures that the program is analyzed correctly in the presence of cycles in the call graph, which arise due to recursion. After the work list becomes empty in line 311, a classification of all program variables is made into one of the following categories: global_escape, arg_escape and procedure_local. A new work list is initialized to have all procedures listed in topological sort order in line 312. Loop 313 iterates over each procedure in the work list until the work list is empty. The procedure n at the head of the work list is removed from the work list in line 314. It is analyzed by AnalyzeThreadProcedure in line 315 to check whether any arg_escape variable in the procedure should be changed to global_escape. AnalyzeThreadProcedure described further below, also puts each callee within procedure n back on the work-list if the classification of any variable changed during that invocation of AnalyzeThreadProcedure. In line 317, after all procedures have been analyzed, all program variables that are not marked global_escape (i.e., those that are marked arg_escape or procedure_local) are marked thread-local in the symbol table ST. Note that this is just a logical step; it can be achieved by structuring the test for thread-local variables to check for the global_escape flag, so there is no need for a separate traversal of the symbol table for this step. The information obtained by the connection graphs for various procedures in the program is also retained, so that during a later phase, the compiler can determine whether an object is thread-local or not, given either an object or a pointer to an object at a particular statement in the program (this test is referred to as IsThreadLocal in lines 1911 and 2212, to be described later).

[0074] The following pseudocode describes AnalyzeStackProcedure as called in line 310, above, which obtains a classification of each variable in the procedure n into one of the following categories: global_escape, arg_escape and procedure_local.

[0075] 401: AnalyzeStackProcedure(n, CallG, Worklist) {

[0076] 402: Build an initial connection graph, CG, for procedure n;

[0077] 403: if n is marked as no-analyze then // make pessimistic assumption

[0078] 404: foreach actual parameter and return node a_ido

[0079] 405: state(a_i)=global_escape;

[0080] 406: end do

[0081] 407: return;

[0082] 408: endif

[0083] 409: Build control flow graph, CFG, of procedure n;

[0084] 410: Set BBWorkList=enumeration of nodes in CFG in topological sort order;

[0085] 411: while BBWorkList not empty do

[0086] 412: Get first element bb and delete it from BBWorkList;

[0087] 413: AnalyzeBB(n CG, CFG, bb, BBWorkList);

[0088] 414: end do

[0089] 415: if (IsChanged(n)) then

[0090] 416: foreach caller c_iof procedure n do

[0091] 417: if c_iis not marked as no-analyze then

[0092] 418: add c_ito WorkList,

[0093] 419: endif

[0094] 420: end do

[0095] 421: endif

[0096] 422: }

[0097] An initial connection graph for the procedure is built in line 402. This connection graph has nodes for each pointer variable in the procedure., including those that are formal parameters of the procedure. For each i^th) formal parameter f_iand for the return value that is a pointer, there are two nodes in the connection graph, one referred to as f_i, and the other referred to as a_i, a placeholder for the corresponding actual parameter passed in or return value used at different call sites of the procedure. The connection graph initially created for the procedure has a deferred edge from each formal parameter node f_ito the corresponding a_i. Line 403 first checks if this procedure is marked no-analyze. If so, in lines 404 through 406, each node a_i, which serves as the placeholder for an actual parameter or return value, is marked global_escape and no further processing is done. If the procedure is not marked no-analyze a control flow graph of the procedure is built in line 409. The nodes of the control flow graph, representing basic blocks in the procedure, are added in topological sort order to a work list BBWorkList in line 410. Loop 411 iterates over each entry in BBWorkList until that work list is empty. The basic block bb at the head of the work list is removed from the work list in line 412. It is analyzed by AnalyzeBB in line 413, described further below in lines 501 to 517. In line 415, the call to IsChanged described further below, determines if the classification of any variable changed during this invocation of AnalyzeStackProcedure. If there was a change, each caller of the procedure n is added to the work list WorkList consisting of the procedures which need to be analyzed further.

[0098] The pseudocode below describes AnalyzeBB which is called in line 413 above, and is used to analyze a given basic block bb.

[0099] 501: AnalyzeBB(n, CG, CFG, bb, BBWorkList) {

[0100] 502: foreach predecessor basic block p of bb in CFG do

[0101] 503: foreach pointer variable v do

[0102] 504: merge connections for variable v in the representation for p;

[0103] 505: if merge leads to any new connection for v in bb then

[0104] 506: add successors of bb in CFG to BBWorkList,

[0105] 507: endif

[0106] 508: end do

[0107] 509: end do

[0108] 510: foreach statement S of basic block bb in forward order do

[0109] 511: switch (statement type)

[0110] 512: case assignment: AnalyzeAssign(CG, S, bb.outEdgeInMiddle);

[0111] 513: case procedure call: AnalyzeProcCall(n, CG, S);

[0112] 514: case return or exit: Summarize(n, CG);

[0113] 515: endswitch

[0114] 516: end do

[0115] 517: }

[0116] Loop 502 iterates over each basic block p which is a predecessor of bb in the control flow graph. Loop 503 iterates over each connection graph node representing a pointer variable. In line 504, the connections for each pointer variable node are merged with the connections for that pointer variable, as they exist in basic block p. If this merging of connections leads to any new edges being introduced for variable v in bb, the successors of bb in the (control flow graph are added, in line 506, to BBWorkList to ensure that those basic blocks are analyzed again. Loop 510 iterates over each statement in its order of appearance in the basic block bb. Based on the check for the type of statement in line 511, the appropriate analysis is done. If the statement is an assignment statement, it is handled by AnalyzeAssign in line 512, described further below. If the given basic block bb appears in an exception block in the current procedure, such as a “try” block as part of a “try-catch” constrict in Java™, the last parameter to AnalyzeAssign (bb.outEdgeInMiddle) is true. This parameter ensures that AnalyzeAssign takes into account the possible control flow out of the basic block due to an exception thrown in that basic block.

[0117] If the statement consists of a procedure call, it is handled by AnalyzeProcCall in line 513, described further below. If the statement represents the end of the procedure or a return from it, the connection graph for the procedure is summarized by Summarize as shown in line 514 and described further below.

[0118] The pseudocode below describes AnalyzeAssign which is called in line 512 above.

[0119] 601: AnalyzeAssign (CG, S, noKill) {

[0120] 602: switch (statement type)

[0121] 603: case [a₁.a₂. . . a_n=(address of) O;]

[0122] 604: AnalyzeAssignCase1 (CG, S, nokill)

[0123] 605: case [a₁.a₂. . . a_n=b₁.b₂. . . b_m]

[0124] 606: AnalyzeAssignCase2 (CG, S, noKill)

[0125] 607: endswitch

[0126] 608: }

[0127] Lines 602 through 607 check for two types of assignment statements, which are illustrated as case [a₁.a₂. . . a_n=(address of) O] and as case [a₁.a₂. . . a_n=b₁.b₂. . . b_m]. For the first case, the procedure AnalyzeAssignCase1 is called in Line 605, and for the second case, the procedure AnalyzeAssignCase2 is called in line 607.

[0128] The pseudocode below describes AnalyzeAssignCase1 which analyzes statements of the form a₁.a₂. . . a_n=(address of) O. This represents all assignment statements where a pointer gets the value of the address of an object which may be allocated dynamically or statically. The actual notation for this kind of statement varies in different languages. For instance, in Java™, the statement may appear as a₁.a₂. . . a_n=new Constructor(. . .).

[0129] 701: AnalyzeAssignCase1(CG, S, nokill) {

[0130] 702: // S is: a₁.a₂. . . a_n=(address of) O;

[0131] 703: Create a new object O_n(if one does not exist for this site);

[0132] 704: if (a₁is a formal parameter and no phantom node for a₁exists) then

[0133] 705: Create phantom nodes O₂, O₃, . . . O_n−1such that a₂is a field in O₂, a₃is a field in O₃, and so on; Insert points-to edge from a₁to O₂, from a₂to O₃, and so on.

[0134] 706: endif

[0135] 707: if (n=1) then

[0136] 708: Let R be the set of incoming deferred edges into a₁;

[0137] 709: Let S be the set of outgoing points-to edges from a₁;

[0138] 710: Let T be the set of outgoing deferred edges from a₁;

[0139] 711: if (not noKill) then

[0140] 712: Add new points-to edges from the source node of edges in R to target nodes of edges in S;

[0141] 713: Add new deferred edges from the source node of edges in R to target nodes of edges in T;

[0142] 714: Delete all edges in the sets R, S, and T from CG;

[0143] 715: endif

[0144] 716: Add a points-to edge from a₁to O_n;

[0145] 717: else

[0146] 718: Find all the field nodes a_nstarting from node a₁corresponding to the path a₁.a₂. . . a_n; Let A be the set of all a_nnodes;

[0147] 719: if (for any a_inode, 1≦i≦n, state(a_i)=global_escape) then

[0148] 720: MakeBottom(O_n);

[0149] 721: else

[0150] 722: Add a points-to edge from each node in A to O_n;

[0151] 723: endif

[0152] 724: endif

[0153] 725: }

[0154] Line 703 first creates a new object node O_n(if one does not already exist for this site). Next, line 705 creates phantom nodes and edges in case a₁is a parameter (if the phantom nodes have not yet been created). These phantom nodes and edges are needed for interprocedural analysis to collect procedural summary information. At line 707, if n is 1 the general case can be simplified (specialized) to a₁=(address of) O. This simplified case is handled in Lines 708 through 716. First, line 711 checks if it is safe to kill the information about the previous connections of a₁; whether or not to “kill” was originally determined for the entire basic block in line 512 above. Effectively, this check ensures that if the given statement S appears inside an exception block within the current procedure, such as inside a try block in Java™, the previous connections of a₁are not killed. Thus, the analysis remains valid in case an exception is thrown and the control is transferred to an exception handling code (such as the “catch” block in Java™) within the procedure. The present invention allows previous connections of a₁to be killed if the statement S does not appear in an exception block in the current procedure, even if dynamically, it appears inside an exception block of a calling procedure. Since the new value of a₁would not be visible at any exception handling code outside the current procedure, it is safe to kill the previous connections of a₁within the procedure in this case.

[0155] If it is safe to kill the previous data flow information, lines 712 and 713 bypass a₁by connecting the predecessor nodes of a₁with the successor nodes of a₁, and 714 deletes the previous incoming edges into a₁and the previous outgoing edges from a₁. These steps 712 through 714 may actually be implemented using a new node for a₁and using this new node for a₁instead of the previous node for a₁from this point onwards. A points-to edge is added from the node for a₁to O_nin 716. The more general case of the assignment statement, where n is larger than 1 is handled in Lines 718 through 723. No deletion of edges is done in this case. Line 718 identifies all the field nodes in the connection graph at path length n from a₁corresponding to the path a₁.a₂. . . a_n. Let all of these field nodes form the set A. If during the traversal of nodes during the previous step in line 718, any node with state global_escape was encountered, the object O_n(and any node reachable from it) is also marked global_escape by invoking MakeBottom on O_n. Finally, in line 722, a points-to edge is added from each node in the set A (computed in line 718) to O_n.

[0156] The following pseudocode describes AnalyzeAssignCase2 which analyzes statements of the form a₁.a₂. . . a_n=b₁.b₂. . . b_n.

[0157] 801: AnalyzeAssignCase2 (CG, S, noKill){

[0158] 802: // S is: a₁.a₂. . . a_n=b₁.b₂. . . b_m;

[0159] 803: if (a₁is a formal parameter and no phantom node for a₁exists)

[0160] 804: Create phantom nodes O₂, O₃, . . . O_n−1such that a₂is a field in O₂, a₃is a field in O₃, and so on; Insert points-to edge from a₁to O₂, from a₂, to O₃, and so on.

[0161] 805: endif

[0162] 806: if (b₁is a formal parameter and no phantom node for b₁exists)

[0163] 807: Create phantom nodes Q₂, Q₃, . . . Q_m−1such that b₂is a field ii Q₂, b₃is a field in Q₃, and so on; Insert points-to edge from b₁to Q₂, from b₂to Q₃, and so on.

[0164] 808: endif

[0165] 809: Find all the field nodes b_mstarting from node b₁corresponding to the path b₁.b₂. . . b_m; Let B be the set of all b_mnodes.

[0166] 810: if (n=1) then

[0167] 811: Let R be the set of incoming deferred edges into a₁;

[0168] 812: Let S be the set of outgoing points-to edges from a₁;

[0169] 813: Let T be the set of outgoing deferred edges from a₁;

[0170] 814: if (a₁is a pointer and not noKill) then

[0171] 815: Add new points-to edges from the source node of edges in R to target nodes of edges in S;

[0172] 816: Add new deferred edges from the source node of edges in R to target nodes of edges in T;

[0173] 817: Delete all edges in the sets R, S, and T from CG;

[0174] 818: endif

[0175] 819: Add a deferred edge from a₁to each node in B;

[0176] 820: else

[0177] 821: Find all the field nodes an starting from node a₁corresponding to the path a₁.a₂. . . a_n; Let A be the set of a_nnodes.

[0178] 822: if (for any a_inode, 1≦i≦n, state(a)=global escape) then

[0179] 823: foreach node b in B do

[0180] 824: MakeBottom(b);

[0181] 825: end do

[0182] 826: else

[0183] 827: Add a deferred edge from each node in A to each node in B;

[0184] 828: endif

[0185] 829: endif

[0186] 830: }

[0187] As described above for AnalyzeAssignCase 1, phantom nodes and edges are created whenever a₁or b₁is a formal parameter. This is done in Lines 803 through 808. Then line 809 identifies all the field nodes in the connection graph at path length m from b₁corresponding to the path b₁.b₂. . . b_m. Let all of these field nodes form the set B. When m is 1, a special case a₁=b₁. b₂. . . b_mis handled in lines 811 through 819. If a₁is a pointer and if it is safe to kill the previous connections of pointer variables in the given statement (determined, as in the case of line 711, for the entire basic block in line 512), lines 815 and 816 bypass a₁by connecting the predecessor nodes of a with the successor nodes of a₁and line 817 deletes the previous incoming edges into a₁and the previous outgoing edges from a₁. These steps 815 through 817 may actually be implemented, as for the previous case, using a new node for a₁and using this new node for a₁instead of the previous node for a₁from this point onwards. A points-to edge is added from the node for a₁to each node in B in line 819. The more general case of the assignment statement, where n is larger than 1 is handled in Lines 821 through 829. No deletion of edges is done in this case. Line 821 identifies all the field nodes in the connection graph at path length n from a₁corresponding to the path a₁.a₂. . . a_n. Let all of these field nodes form the set A. If during the traversal of nodes during the previous step in line 821, any node with state global_escape was encountered, all nodes b in the set B (iterated over in Loop 823) are marked global_escape by calling MakeBottom in line 824, which also marks each node reachable from b as global_escape. Finally, in line 827, a deferred edge is added from each node in the set A (computed in 821) to each node in the set B (computed in line 809).

[0188] The following pseudocode describes AnalyzeProcCall which is called at line 513, above.

[0189] 901: AnalyzeProcCall(S){

[0190] 902: Let <a_i, â_i>, 0≦i≦n−1 be the actual parameter pairs at S.

[0191] 903: Let <a_n, â_n>be the return node pair at S.

[0192] 904: foreach target method m_iat S do

[0193] 905: // Multiple candidate target methods might exist due to virtual call.

[0194] 906: foreach object node n_oof the callee reachable from a_iof the callee do

[0195] 907: visited (n_o)=false;

[0196] 908: end do

[0197] 909: foreach <a_i, â_i>pair do

[0198] 910: // For each object node n_oreachable from a_iof the callee, compute

[0199] 911: // its equivalent object nodes, EquivObj(n_o, S), of the caller.

[0200] 912: // In doing so, create phantom nodes if necessary.

[0201] 913: ComputeEquivNodes (a_i, {â_i}, S);

[0202] 914: end do

[0203] 915: foreach a_i, 0≦i≦n do

[0204] 916: // For each object node o_ireachable from a_iof the callee,

[0205] 917: // if o_i^F→f_j^P→o_k, make sure

[0206] 918: // (1) ô_i^P→f_j^P→ô_k, for all o_i's

[0207] 919: // equivalent nodes ô_i, and for all o_k's equivalent nodes ô_k;

[0208] 920: // (2) any deferred edge from f_ito another field node or a_lwill have

[0209] 921: // its corresponding edge between equivalent nodes at the caller

[0210] 922: InsertEdges(a_i, S);

[0211] 923: end do

[0212] 924: end do

[0213] 925: }

[0214] As explained earlier, a call site can have multiple target methods statically associated with it, which the loop 904 handles by applying the body of the loop to each target method at the call site. For each target method, line 907 first logically marks all the object nodes reachable from the actual parameter nodes of the method as “not visited.” This step is not physically needed due to a version-number scheme employed. Then, for each pair of actual node of the method and the corresponding actual node at the call site, line 913 (described further at line 1001, below) computes the equivalent nodes of object and field nodes of the called method, creating phantom nodes at the caller method. Using the equivalent node information, line 919 (described in detail at line 1101 ) inserts edges, if not already existent, between nodes of the caller method if their equivalent nodes of the callee method have edges between them.

[0215] The pseudocode below describes ComputeEquivNodes which is called in line 913 to compute the equivalent nodes of object and field nodes of the called method.

[0216] 1001: ComputeEquivNodes(f_ee: node; EquivF: set of nodes, S: call.site) {

[0217] 1002: // EqvivF is the set of equivalent nodes of fee.

[0218] 1003: // Subscript “ee” stands for callee. and “er” stands for caller.

[0219] 1004: if (state(f_ee)=global_escape) then

[0220] 1005: foreach (f_erε EquivF) do

[0221] 1006: MakeBottom(f_er);

[0222] 1007: end do

[0223] 1008: return;

[0224] 1009: endif

[0225] 1010: foreach object node n_os . t. f_ee^P→n_odo

[0226] 1011: if visited(n_o)=true then

[0227] 1012: continue; // skip the following with the current n_o

[0228] 1013: endif

[0229] 1014: visited (n_o)=true;

[0230] 1015: // n_ois pointed to by f_ee

[0231] 1016: foreach n{circumflex over ( )}_oε {n{circumflex over ( )}_o| f_er⁺¹→n{circumflex over ( )}₀, f_erε EquivF} do

[0232] 1017: // f_eris one of f_ee's equivalent nodes of the caller.

[0233] 1018: // n{circumflex over ( )}_ois one of the nodes pointed to by f_er.

[0234] 1019: // If no such n{circumflex over ( )}_oexists, create one phantom node.

[0235] 1020: EqF={}; // initialize EqF to empty set

[0236] 1021: if n{circumflex over ( )}_oε EquivObj(n_o, S) then

[0237] 1022: EquivObj(n_o, S)=EquivObj(n_o, S) U {n{circumflex over ( )}_o};

[0238] 1023: // add n{circumflex over ( )}_oto EquivObj(n_o, S)

[0239] 1024: endif

[0240] 1025: foreach f{circumflex over ( )}_ees.t. n_o^F→f{circumflex over ( )}_eedo

[0241] 1026: EqF={f{circumflex over ( )}_er|n{circumflex over ( )}_o^F→f{circumflex over ( )}_er, f id (f{circumflex over ( )}_ee)=f id (f{circumflex over ( )}_er)};

[0242] 1027: // Matching field nodes of n{circumflex over ( )}_o

[0243] 1028: // become equivalent field nodes of f_ee

[0244] 1029: ComputeEquivNodes(f{circumflex over ( )}_ee, EqF, S); // invoke recursively

[0245] 1030: end do

[0246] 1031: end do

[0247] 1032: end do

[0248] 1033: }

[0249] The first parameter, f_eeis either an actual parameter node or a field node of an object node. Line 1004 checks if the callee node f_eeis marked global_escape. In that case, each equivalent node of f_eeis marked global_escape in lines 1005 through 1007, and the procedure returns in line 1008. Loop 1010 iterates over each node, no in the connection graph that has a point-to edge from f_ee, skipping no if it has already been visited (Lines 1011 and 1012) while computing equivalent nodes. If it has not been visited before, line 1014 marks it as visited for proper termination of the algorithm. Then, Loop 1016 iterates over each object node of the caller that has a point-to path of length one from any of the nodes in EquivF, which is the set of nodes of the caller equivalent to f_ee. These caller's object nodes are added to the set of equivalent nodes of the callee node n₀in lines 1021 through 1024. Then, for each field node of n₀iterated over in Loop 1025, line 1026 computes the, matching field nodes, EqF of the caller's equivalent. The procedure then invokes itself recursively at line 1029, using the field node of n₀and the equivalent caller nodes' matching field nodes, EqF as the new parameters.

[0250] The following pseudocode describes InsertEdges which is called in line 922, and is used to insert edges out of the equivalent node of n_iin the caller to reflect the effect of the procedure call. p01101: InsertEdges(n_i: node, S: callsite) {

[0251] 1102: if (visited(n_i)=true) then

[0252] 1103: return;

[0253] 1104: endif

[0254] 1105: visited(n_i)=true;

[0255] 1106: if n_iis an object node then

[0256] 1107: foreach objectnode o_ks.t. n_i^F→f_j^P→o_kdo

[0257] 1108: // o_kis pointed to by f_j, which is a field node of n_i

[0258] 1109: foreach object node n{circumflex over ( )}_iε EquivObj(n_i, S) do

[0259] 1110: foreach object node o{circumflex over ( )}_kε EquivObj(o_k, S) do

[0260] 1111: insert a points-to edge, if not already existing, from f{circumflex over ( )}_jto o{circumflex over ( )}_k, where n{circumflex over ( )}_i^F_j→f{circumflex over ( )}_j

[0261] 1112:: end do

[0262] 1113: end do

[0263] 1114: foreach object node o_is.t. o_i^F_m→f_m, and there exists a deferred edge from f_jto f_mdo

[0264] 1115: foreach object node n{circumflex over ( )}_iε EquivObj(n_i, S) do

[0265] 1116: foreach object node o{circumflex over ( )}_iε EquivObj(o_i, S) do

[0266] 1117: insert a deferred edge, if not already existing, from f{circumflex over ( )}_jto f{circumflex over ( )}_m, where n{circumflex over ( )}_i^F_j→f{circumflex over ( )}_jand o{circumflex over ( )}_i^F_m→f{circumflex over ( )}_m;

[0267] 1118: end do

[0268] 1119: end do

[0269] 1120: end do

[0270] 1121: foreach a_pto which there exists a deferred edge from f_jdo

[0271] 1122: insert deferred edges from f{circumflex over ( )}_jof all n_i's equivalent nodes to the equivalent node a {circumflex over ( )}_pof a_pin the caller;

[0272] 1123: end do

[0273] 1124: InsertEdges(o_k, S); // recursively invoke.

[0274] 1125: end do

[0275] 1126: else

[0276] 1127: foreach edge e_jfrom n_ito n_kdo

[0277] 1128: insert an edge of the same type from equivalent nodes, n{circumflex over ( )}_i, of n_ito equivalent nodes, n{circumflex over ( )}_k, of n_kin the caller;

[0278] 1129: if n_kis not a field node then

[0279] 1130: InsertEdges(n_k, S);

[0280] 1131: endif

[0281] 1132: end do

[0282] 1133: endif

[0283] 1134: }

[0284] First, line 1102 checks, using a version-numbering scheme, if n_ihas already been visited. If so, the procedure returns in line 1103. The node n_iis marked visited, using the version-numbering scheme, in 1105. Line 1106 checks if n_iis an object node, and lines 1007 through 1125 handle that case. Loop 1107 identifies, for each field, f_j, of the object node, n_i, in the callee's connection graph, the set of object nodes, o_k, that have a points-to edge, onto from f_j. Lines 1109 through 1113 insert edges, if not already existent, from the matching field nodes of the caller's object nodes equivalent to n_i, to caller's object nodes equivalent to o_k(the equivalent nodes of n_iare iterated over in Loop 1109 and the equivalent nodes of o_kare iterated over in Loop 1110). Next, Loop 1114 iterates over each object node o_k, that owns a field f_mto which there is a deferred edge from field f_jof n_i. Lines 1115 through 1119 insert deferred edges, if not already existent, from the matching field nodes of the caller's object nodes equivalent to n_i, to the matching field nodes of the caller's object nodes equivalent to o_l(the equivalent nodes of n_iare iterated over in Loop 1115 and the equivalent nodes of o_l, are iterated over in Loop 1116). Next, Loop 1121 iterates over each actual parameter node or return node, a_p, to which there is a deferred edge from f_j. Line 1122 inserts deferred edges from the matching field nodes of the caller's object nodes equivalent to n_i, to the equivalent node(s) of the actual parameter or return node in the caller. Line 1124 invokes the procedure recursively for the object node o_kin place of n_i, to ensure that edges out of o_kor its fields are reflected in the caller. Lines 1127 through 1132 take care of the case where n_iis not an object node (i.e., it may be an actual parameter or return node). Loop 1127 iterates over each outgoing edge from n_i. For each such node n_k, 1128 inserts edges from the equivalent nodes of n_ito the equivalent nodes of n_kin the caller's connection graph. Furthermore, if n_kis an object node, line 1130 recursively invokes the procedure for n_k, to ensure that edges out of n_kor its fields are reflected in the caller.

[0285] The following pseudocode describes MakeBottom, which is called above in lines 720, 824 and 1006.

[0286] 1201: MakeBottom(v) {

[0287] 1202: if (state(v)≠global_escape) then

[0288] 1203: state(v)=global_escape;

[0289] 1204: foreach node x reachable from v do

[0290] 1205: if (state(x)≠global_escape) then

[0291] 1206: state(x)=global escape;

[0292] 1207: endif

[0293] 1208: end do

[0294] 1209: endif

[0295] 1210: }

[0296] First, line 1202 checks if the node v is not currently marked global_escape. If the node is already marked global_escape, nothing further needs to be done. Otherwise, line 1203 marks the node as global_escape. Loop 1204 goes over each node in the connection graph that is reachable from v. For each such node, x, line 1205 checks if the node is not currently marked global_escape, and in that case, line 1006 marks it global_escape.

[0297] The following pseudocode describes Summarize, which is called in line 514, above.

[0298] 1301: Summarize(n,CG) {

[0299] 1302: foreach formal parameter f_iof procedure n do

[0300] 1303: foreach node v in CG reachable from f_ido

[0301] 1304: if (state(v)=procedure_local) then

[0302] 1305: state(v)=arg_escape;

[0303] 1306: endif

[0304] 1307: if a PtPath v⁺¹→w exists, but the edge v^P→w does not exist then

[0305] 1308: add edge v^P→w;

[0306] 1309: endif

[0307] 1310: remove all deferred edges out of v;

[0308] 1311: enddo

[0309] 1312: enddo

[0310] 1313:}

[0311] Loop 1302 iterates over each formal parameter, f_i, of the given procedure n. Loop 1303 iterates over each node, v, in the connection graph that is reachable from _i. If the node v is marked procedure_local, line 1305 marks it arg_escape. Furthermore, all deferred edges out of v are taken into account by creating a points to edge v^P→w (line 1308) that did not previously exist for every PtPath v⁺¹→w. Thus, the effect of Summarize is to leave the nodes marked global_escape as they are, but mark other nodes that are reachable from a parameter node as arg_escape, and factor in the information from all deferred edges along those paths.

[0312] The following pseudocode describes IsChanged, which is called in line 415, above.

[0313] 1401: IsChanged(n) {

[0314] 1402: RealNodes={object_nodes, field_nodes, local_variable_nodes,

[0315] 1403: actual_nodes, return_node }

[0316] 1404: NumNodes=SizeOf (Real Nodes); // number of nodes in RealNodes set

[0317] 1405: NumPaths=number of length one point to paths among nodes in RealNodes;

[0318] 1406: if (NumNodes>=n.NumNodes) or (NumPaths>=n.NumPaths) then

[0319] 1407: n. NumNodes=NumNodes;

[0320] 1408: n.NumPaths=Numpaths;

[0321] 1409: return true;

[0322] 1410: else

[0323] 1411: return false;

[0324] 1412: endif

[0325] 1413: }

[0326] The algorithm determines whether there is a change in the connection graph that needs further iterations. Changes in the connection graph that need further iterations are defined to be any of the following: (1) change in the number of real nodes: object nodes, field nodes, local variable nodes, parameter nodes, and the return node; or (2) change in the number of point-to paths of length one among the real nodes. If any change has occurred, the procedure returns true in line 1409, otherwise it returns false in line 1411.

[0327] The following pseudocode describes AnalyzeThreadProcedure, which is called in line 315, above.

[0328] 1501: AnalyzeThreadProcedure(n, CallG, WorkList) {

[0329] 1502: if any caller of n is marked as no-analyze then

[0330] 1503: foreach object variable o_iin procedure n do

[0331] 1504: if (state(o_i)=arg_escape) then

[0332] 1505: Makebotttom(o_i);

[0333] 1506: endif

[0334] 1507: end do

[0335] 1508: return;

[0336] 1509: endif

[0337] p11510: procChange=false;

[0338] 1511: foreach thread object variable o_iin procedure do

[0339] 1512: foreach field f_kof o_ido

[0340] 1513: if state(f_k)≠global_escape and f_kis accessed before o_iis killed then

[0341] 1514: MakeBottom(f_k); procChange=true;

[0342] 1515: endif

[0343] 1516: end do

[0344] 1517: end do

[0345] 1518: foreach object variable o_iwith state arg_escape in procedure n do

[0346] 1519: foreach eo_ithat is an equivalent object of o_iin a caller of n do

[0347] 1520: if (state(eo_i)=global escape) then

[0348] 1521: if (state(o_i) g global escape) then

[0349] 1522: MakeBottom(o_i);

[0350] 1523: procChange=true;

[0351] 1524: endif

[0352] 1525: endif

[0353] 1526: end do

[0354] 1527: end do

[0355] 1528: if (procChange) then

[0356] 1529: foreach callee c_iof procedure n do

[0357] 1530: if c_iis not marked as no-analyze then

[0358] 1531: add c_ito WorkList;

[0359] 1532: endif

[0360] 1533: end do

[0361] 1534: endif

[0362] 1535: }

[0363] First, line 1502 checks if any caller of the procedure n is marked no-analyze. If so, each object node o_iof the procedure that was previously marked arg_escape and each node reachable from o_iis conservatively marked global_escape, in lines 1503 through 1507. No further processing is needed in this case, and so the procedure returns in line 1508. The remainder of the procedure handles the case when no caller of the procedure is marked no-analyze. For internal book-keeping, line 1510 initializes the variable procChange to false. Loop 1511 iterates over each thread variable allocated in the procedure n. Loop 1512 iterates over each field,f_k, of the thread object o_i. If f_kis not already marked global_escape and f_kis used before o_iis killed (which can be determined by standard data flow analysis), then line 1514 marks f_kand nodes reachable from it as global_escape, and sets procChange to true. Loop 1518 iterates over each object variable node, o_i, in the connection graph that is marked arg_escape. Loop 1519 iterates over each equivalent object, eo_iof o_iover all call-sites in different callers of procedure n. Line 1520 checks if eo_iis marked global_escape. In that case, if o_iwas not already marked global_escape, it is marked global_escape, and procChange is set to true, in Lines 1521 through 1524. Finally, line 1528 checks if there has been a change in the status of some variable in n (by checking the value of procChange). If there has been a change, lines 1529 through 1533 add all of the procedures called inside n, that are not marked no-analyze, to the work list, to ensure that those procedures will be analyzed again by AnalyzeThreadProcedure.

[0364] The following pseudocode describes the process of step 204 of FIG. 2, removeSimpleLockOperations. The pseudocode describes how the program representation contained in G is transformed, using the results of the escape analysis process contained in G and the connection graph CG, The method for transforming the program takes as inputs G, which is an intermediate language representation of the program being optimized; M, the particular procedure being optimized (M is referred to by its signature, and may optionally be a devirtualized invocation), and CG, the connection graph containing the results of the Escape Analysis. These inputs are shown as arguments to the removeSimpleLockOperations algorithm in step 1901. It is initially invoked with M=MAIN.

[0365] 1901: removeSimpleLockOperations(G, M, CG) {

[0366] 1902: GM=G(M)

[0367] 1903: M.nseRemoved=true

[0368] 1904: foreach node N in G do

[0369] 1905: if N.op is a procedure invocation then

[0370] 1906: M_N=N.procedure

[0371] 1907: if not M_N.nseRemoved then

[0372] 1908: removeSimpleLockOperations(G, M_N, CG)

[0373] 1909: endif

[0374] 1910: else

[0375] 1911: if N.op=O_Nand IsThreadLocal(N.obj,CG,N.stmt) then

[0376] 1912: removeLock(G_M, N)

[0377] 1913: endif

[0378] 1914: endif

[0379] 1915: }

[0380] In line 1902, G_M, the intermediate language form of the procedure to be transformed is accessed. Line 1903 updates the globally accessible data structure associated with the procedure M to indicate that it is being visited. Marking this structure allows the method to handle recursive routines by entering, and transforming them only once.

[0381] Line 1904 begins an iteration over each node of G_M. Each node is checked to see if it corresponds to a procedure invocation (step 1905) or some simple locking operation on an object that does not escape (step 1911). If the former, and if the procedure has not already been transformed (the check of line 1907), the procedure is transformed by recursively performing removeSimpleLockOperations (line 1908). If the latter, the program is transformed by removing the locking operation from the program. Thus, our invention uses information about the scope in which a lock is accessed in order to optimize it.

[0382] The sideEffectAnalysis process, as shown in FIG. 2, step 206, logically creates a table (T_sideEffects) with an entry for each node N in G, ,where N.op is a comprehensive locking operation. T_sideEffects[N] is true if the side effects, of the locking operation at node N, must be performed. The table T_sideEffectsmay be physically implemented as a table or hash table, or as a table whose entries are distributed among the nodes of the control flow graph for the method contained in G for which the table contains entries. The other transformation brought about by the analysis process is the addition of summary information, in the form of fields (or flags) KILL and GEN for each procedure M. These are described above in the discussion of line 205 of FIG. 2. These fields can take on the values true and false, and are attached to the label information in L for each procedure M in the intermediate representation of the program. The additional fields of information of a node in a method's control flow graph that are transformed by sideEffectsAnalysis, are read by the locking operation optimization routines.

[0383] The inputs to the process of sideEffectAnalysis are the intermediate program representation G; the procedure M being analyzed; the results of the Escape Analysis process in the connection graph CG; a flag IN which contains the initial value (true or false) for the analysis, and a flag OUT which represents summary information for the analysis as applied to IN. Below is pseudocode describing the method for sideEffectAnalysis.

[0384] 2001: sideEffectAnalysis(G, M, CG, IN, OUT) {

[0385] 2002: G_m=G(M)

[0386] 2003: foreach node N ε G_mdo

[0387] 2004: N._IN=false

[0388] 2005: N._OUT=false

[0389] 2006: if N.type≠procedureCall then

[0390] 2007: N._GEN=false

[0391] 2008: N._KILL=true

[0392] 2009: if (∃k s.t. V_kε N ΛV_k.lval=true) N._GEN=true

[0393] 2010: if ((N.op=O_S) and (not inside exception block)) N._KILL=false

[0394] 2011: else

[0395] 2012: M=N.procedure

[0396] 2013: if M.summarized then

[0397] 2014: N._GEN=M._GEN

[0398] 2015: N._KILL=M._KILL

[0399] 2016: else

[0400] 2017: if (M.visited) then

[0401] 2018: N._GEN=true

[0402] 2019: N._KILL=true

[0403] 2020: else

[0404] 2021: summarizeMethodSideEffects(G, M, CG, N._GEN, N._KILL)

[0405] 2022: endif

[0406] 2023: endif

[0407] 2024: enddo

[0408] 2025: ENTRY._IN=IN

[0409] 2026: C=true

[0410] 2027: while(C=true) do

[0411] 2028: C=false

[0412] 2029: foreach node N in a traversal of G_Mdo

[0413] 2030: N._IN=−{OUT_P/P ε N.pred}

[0414] 2031: OUT_TEMP=N._OUT

[0415] 2032: N._OUT=(N._IN. N._KILL)−N._GEN

[0416] 2033: C=C−(OUT_TEMP≠N._OUT)

[0417] 2034: enddo

[0418] 2035: enddo

[0419] 2036: OUT=EXIT._OUT

[0420] 2037: }

[0421] In line 2002, the portion of the intermediate representation that concerns the procedure (M) being analyzed is accessed. The loop from lines 2003 through 2024 sets up information at each node N in G_Mthat tells what objects at the node N are affected by locking operation side effects (N._GEN); and what objects' side effect requirements are provided for by the node (N._KILL) Lines 2025 to 2035 takes the just-modified G_Mand determines for each node whose operation is a comprehensive locking operation whether there are any objects affected by the side effects of the locking operation. If not, it will not be necessary to perform the side effect, as discussed later when describing the effects of the process labeled 208 in FIG. 2. Line 2036 sets the OUT parameter to sideEffectsAnalysis to be the OUT value for the EXIT node of the method's control flow graph.

[0422] Lines 2004 and 2005 fill in default values for N._IN, N._OUT. Lines 2007 and 2008 set defaults for N._GENand N._KILLwhen the node is not a procedure invocation. All but N._KILLare set to false, with N._KILLset to true. N._INis set to false, indicating that none of the predecessors of the node in the program have operations on objects affected by comprehensive locking operations. N._OUTis initially set to false, indicating that no objects affected by locking operation side effects reach the end of the node. N._GENis set to false, indicating no objects operations are performed in the node that require locking operation side effects. N._KILLis set to true, indicating that the node has no comprehensive locking operations. For nodes that have operations that make these flags inaccurate, more accurate information is computed. Otherwise, the default values make nodes for other operations act as identity functions on their inputs. Line 2009 updates the N._GENflag if any global object is updated in this node, i.e. has any object operation that is affected by the next executed comprehensive locking operation. Line 2010 updates the N._KILLset to false if the node contains an O_Soperation, i.e. a comprehensive locking operation. This reflects the O_Snode performing the side effect for all previously written objects for which no other O_Sintervenes between the writing of the object and the execution of this O_Sstatement.

[0423] Lines 2012 through 2023 handle the case where the node is a procedure invocation. In this situation, information that summarizes the effect of the entire procedure call is placed into the N._GENand N._KILLstructures. If an invocation of the procedure has already been visited at another node, and the required summary information is associated with the procedure M, this information is labeled M._GENand M._KILLand is either copied to, or referenced as, N._GENand N._KILL. The check for the availability of the information occurs at line 2013, and the copying or referencing operation occurs at lines 2014 and 2015. If an invocation of the procedure has been visited in another node, but the summary information is not present, then the invocation at the current node N is a recursive invocation, and the previous invocation(s) have not yet completed. This is detected by the if statement at line 2017, in conjunction with the knowledge that the process is at the false branch of the if at line 2013. The process safely approximates the results of the analysis by setting N._GENto true and N._KILLto true, indicating that all objects shown by the connection graph to be accessed in more than one thread have side effects that must be performed by O_S, and that no side effects prior to the procedure M call at node N are taken care of by any O_Slocking operation in the invocation of procedure M. Finally, line 2021, selected by the else at line 2020, is executed when no summary information is available and no invocation of the procedure has been previously encountered.

[0424] In this case, summarizeMethodSideEffects, described in pseudocode and discussed below, is invoked with arguments G, M, CG, N._GENand N._KILL. summarizeMethodSideEffects, using the procedure M, the program representation in G, and the connection graph information for each object containing the results of the escape analysis step, transforms the structures for procedure M to have summary information, and updates N._GENand N._KILLto also have that information.

[0425] Lines 2025 through 2035 propagate the information at each node through the representation of the procedure being analyzed. This is done by repeatedly traversing the intermediate representation of the procedure M(G_M), annotated with the node summary information (N._KILLand N._GEN), until no changes are made in a traversal (C=false). The repetition of the traversal is done by the loop at line 2027, and the traversal itself is done in the loop beginning at line 2029. Lines 2030 through 2033 are performed on each node N visited in the traversal. At line 2030, information, about all objects affected by a comprehensive locking operation are gathered from all nodes that might immediately precede the current node in some execution of the program, and stored in N._IN. N._OUT, the current information about all objects affected by a comprehensive locking operation after the execution of node N is saved in OUT_TEMPby line 2031. Line 2032 then computes a new value for N._OUTby removing from N._INall objects whose side effect requirements are handled by node N, and adding to it all objects which are affected by a locking operation's side effects because of operations within node N. Finally, in line 2033, we compare OUT_TEMPwith the newly computed value of N._OUT. If they are different, then C is set to true to indicate that a change has occurred in this traversal. Line 2035 returns the value of the EXIT node OUT field through the OUT parameter; this serves as a summary of the entire method.

[0426] Below is pseudocode describing the method for summarizeMethodSideEffects called in line 2021, above.

[0427] 2101: summarizeMethodSideEffects(G, M, CG, GEN, KILL) {

[0428] 2102: M.visited=true

[0429] 2103: G_M=G(M)

[0430] 2104: if G_M=null then

[0431] 2105: GEN=true

[0432] 2106: KILL=true

[0433] 2107: else

[0434] 2108: sideEffectsAnalysis(G, M, CG, false, GEN)

[0435] 2109: sideEffectsAnalysis(G, M, C, CG, true, KILL)

[0436] 2110: endif

[0437] 2111: M._GEN=GEN

[0438] 2112: M._KILL=KILL

[0439] 2113: M.summarized=true

[0440] 2114: M.visited=false

[0441] 2115: }

[0442] Routine summarizeMethodSideEffects is invoked on methods whose intermediate representation is contained in G. It transforms the information on methods in G to have summary GEN and KILL information for each procedure, as well as setting a flag, in G, indicating for each procedure if the procedure has valid GEN and KILL summary information.

[0443] The summary information for GEN is true if any operations on any object in M require that the side effects of the next comprehensive locking operation to be executed must be performed. Furthermore, there is some path through M such that no comprehensive locking operation is executed between the operation on the object and an exit from M. It is false otherwise.

[0444] The summary information for KILL is true if either GEN is true, or if some object operation prior to the invocation of M requires that the side effects of the next comprehensive locking operation to be executed be performed, and that, furthermore, there is some path through M such that no such comprehensive locking operation is performed.

[0445] As shown in line 2101, the information used to compute this is G, M, CG, with GEN and KILL information passed out to the side effect analysis algorithm. In line 2102, M.visited is set to true to indicate that M is currently being analyzed. Line 2103 extracts the intermediate program representation from G. Lines 2105 through 2106 compute conservative information if the procedure is not available. The if at line 2104 determines whether this is necessary.

[0446] Line 2108 computes summary GEN information by recursively invoking sideEffectAnalysis (described at line 2001) with IN=false. If OUT=true is returned from sideEffectAnalysis, then GEN is set to true, indicating that some object operation in M requires that the next comprehensive locking operation execute its side effects, and that some path exists from the object operation to an exit from sideEffectAnalysis without encountering such a locking operation.

[0447] Line 2109 computes summary KILL information by recursively invoking sideEffectAnalysis (described above) with IN=true. If OUT=true, then either there is a path from the ENTRY node of M to its EXIT node such that no comprehensive locking operation exists, or there is a path from some operation on an object within M, that requires that the next comprehensive locking operation perform its side effects, to an exit of M, such that no such comprehensive locking operation exists on the path.

[0448] Lines 2113 sets the flag for M indicating that the GEN and KILL information has been computed. Line 2114 sets M's visited flag to false indicating that we are no longer analyzing M.

[0449] Below is pseudocode describing the method of step 208 in FIG. 2, for optimizeComprehensiveLockOperations.

[0450] 2201: optimizeComprehensiveLockOperations(G, M, CG) {

[0451] 2202: G_M=G(M)

[0452] 2203: M._seOptimized=true

[0453] 2204: foreach n εaQ G_Mdo

[0454] 2205: if N.op is a procedure invocation then

[0455] 2206: M_N=N.procedure

[0456] 2207: if not M_N.seOptimized then

[0457] 2208: optimizeComprehensiveLockOperations(G, M_N, CG)

[0458] 2209: endif

[0459] 2210: else

[0460] 2211: if N.op=O_Sthen

[0461] 2212: if not IsThreadLocal(N.obj, CG, N.stmt) then

[0462] 2213: if N._IN=false then

[0463] 2214: makeLockSimple(G_M, N)

[0464] 2215: endif

[0465] 2216: else

[0466] 2217: if N._IN=true then

[0467] 2218: makeLockSideEffectOnly (G_M, N)

[0468] 2219: else

[0469] 2220: makeLockNull(G_M, N)

[0470] 2221: endif

[0471] 2222: endif

[0472] 2223: endif

[0473] 2224: endif

[0474] 2225: }

[0475] This routine takes as inputs G, M, and CG and produces a transformed program by modifying the representation G_Mof the procedure M in the intermediate language of the compiler by optimizing the comprehensive locking operations, where possible, while maintaining the semantics of the original program.

[0476] Line 2202 extracts the intermediate representation of the procedure to be optimized. Line 2203 marks that the procedure has been optimized using the transformation of optimizeComprehensiveLockOperations.

[0477] The loop at line 2204 visits each node in G_Min turn. At line 2205, it is determined if the node is a procedure invocation. If so, and if the procedure is not already optimized or being optimized for comprehensive locking operations (this test is done by line 2207) the method's handle in G (extracted in line 2206) is passed to a recursive call to optimizeComprehensiveLockOperations in line 2208 to optimize the procedure.

[0478] The case where the node in G_Mis not a procedure invocation is handled in lines 2211 through 2220. If the node is an O_Soperations (line 2211), but the locking operation is on an object that escape (line 2212) and there are no objects requiring side effects (line 2213), the operation O_Sis replaced with an operation O'_Sthat transforms the comprehensive locking operation to a simple locking operation (line 2214). The locking operation would in this case would only perform the synchronization operations necessary to ensure mutual exclusion, and not perform any side effects.

[0479] If the node is an O_Soperation, but the object being locked does not escape (line 2216), but there are side effects (the if at line 2217 is true), the O_Soperation is replaced with a fence (sometimes called a sync) operation that performs the side effect part of the locking operation (line 2218). Note that in this case, the synchronization operation to ensure mutual exclusion is recognized as unnecessary, and eliminated.

[0480] If object being locked does not escape, and the side effects of the locking operation are not needed, it can be removed, as done by line 2220. A practitioner skilled in the art will realize that this has the effect of a “no-op,” therefore the effect of makeLockNull can be to emit no code at all for the locking operation. This is true whether the program is being compiled by a static or dynamic compiler.

[0481] The actual implementation of the optimization of locking operations can be performed by a static compiler, a dynamic compiler, or by the run-time system performing the locking operation, based on the analysis performed by the compiler.

[0482] The final transformed program resulting from the method of this invention can be fed into other phases of a compiler, programming environment or program development tool, as shown in FIG. 1, step 108, for further manipulation, or it can be stored into a file for later retrieval, analysis or processing.

[0483] In addition to the preferred embodiment as described above, various modifications are now described. The following variants of the preferred embodiment of the Escape Analysis generally simplify this analysis phase and make it more efficient either in speed and/or memory usage, but some variants may also lead to less precise results. For example, in the Escape_Analysis process, lines 308 through 312 can be omitted, and instead of those steps, each variable of the type arg_escape can be marked global_escape, so that at the end of AnalyzeProgram, only variables of the type procedure_local are viewed as thread-local. This variant simplifies the compiler analysis and makes the analysis more efficient.

[0484] In another possible embodiment, the compiler may not perform iterations over the procedures involved in a cycle in the call graph, as performed in Loop 308 and/or Loop 313, above, until the solution converges (i.e., until there is no change to the computed solution). Instead, the compiler may impose an upper limit on the number of times that a procedure is analyzed, and in the presence of cycles in the call graph, if the solution has not converged yet, may use conservative analysis, such as marking variables corresponding to actual parameters and return values as global_escape. This variant simplifies the compiler analysis and makes the analysis more efficient.

[0485] Similarly, in another embodiment, the cycles in the control flow graph may be handled differently than in the preferred method, shown in Loop 411 above. Again, an upper limit may be imposed on the number of times that a basic block is analyzed, and if a converged solution is not obtained while adhering to that limit, a more conservative solution might be used instead. This variant simplifies the compiler analysis and makes the analysis more efficient.

[0486] In other embodiments, the compiler may choose not to build a complete call graph of the program, or equivalently, regard many procedures in the call graph as no-analyze. This may be done due to the code for the procedure being unavailable, or to make analysis faster, or to avoid problems with binary compatibility of the generated code. In an embodiment that represents one extreme of this variation, the compiler, may choose not to do any interprocedural analysis, and regard each procedure called inside the current procedure as no-analyze, and assume conservative information at the call site. As an example of another embodiment that represents a less extreme version of this variation, a run-time compiler, with more constraints or compilation time, may decide to do detailed analysis of only selected parts of the program where it is spending a fair amount of time during execution. Those procedures, in which the program does not spend much time, may be marked no-analyze and conservative information may be used (similar to the way the preferred method handles procedures marked no-analyze in line 403) at call sites to those procedures.

[0487] In yet another embodiment, a “flow-insensitive” version of the method described in AnalyzeStackProcedure (which those skilled in the art would recognize as a “flow-sensitive method”) may be used. In this embodiment, no killing of data flow information (represented by the bypassing and deletion of previous connection graph edges in Lines 712 through 714, above, and lines 815 through 817, above) is performed. Furthermore, there is no need to have different nodes in the connection graph for the same pointer variable in this embodiment. This variant simplifies the compiler analysis and makes the analysis more efficient.

[0488] In another embodiment, when a node is just marked global_escape, the method would not eagerly mark each node reachable from it as global_escape, as done in procedure MakeBottom, called on lines 720, 824 and 1006. Instead, the act of marking each node reachable from a global_escape node as global_escape would be deferred until the connection graph is summarized for the procedure. Those skilled in the art would recognize this as a lazy variant of this step in the preferred embodiment. On the other hand, in another embodiment, a node that is reachable from a formal parameter node of the procedure may be marked arg—escape eagerly, instead of being marked arg_escape when the connection graph is summarized for the procedure, as in Line 1305.

[0489] In another embodiment, a different method may be used to determine whether the connection graph has changed. Instead of using the method shown in lines 1401 to 1413, each time a new edge is added or the state of a node is changed (for example, from procedure_local to global_escape), a flag may be set to indicate that the connection graph has changed.

[0490] In another embodiment, the fields of a thread object may be conservatively marked global_escape as well. In that case, the lines 1511 through 1517 and the lines 1525 through 1532, above, would not be needed. This variant simplifies the compiler analysis and makes the analysis more efficient.

[0491] In other embodiments, separate nodes may not be used for all different fields of an object variable. At one extreme, in an embodiment, each field of an object may be represented by the node for the object itself. In another embodiment representing a less extreme position, multiple fields of an object may be represented by a single node. The variations reduce the space requirements of the method and make it faster than the method in the preferred embodiment, but the analysis also becomes more conservative.

[0492] On the other hand, this variant of the preferred embodiment is used to make the analysis more precise. In this variant, “type” information may be used to refine the connection graph information when compiling a language that is “type-safe”, such as Java™. For instance, at a call-site to a procedure which is regarded as no-analyze, less conservative information may be used than that shown in AnalyzeStackProcedure in lines 402 to 407. This embodiment would only allow connections to parameters and return value nodes that are allowed by the type system. A deferred edge is allowed only from a variable that points to type T₁to another variable that points to type T₂if the type system allows a variable of type T₁to be assigned to another variable of type T₂. A points-to edge is allowed only from a variable that points to type T₁to another variable of type T₂if the type system allows a variable of type T₁to be assigned to another variable of type T₂. A field edge is allowed from a variable of type T₁to variable of type T₂if under the type system, T₁has a member of type T₃and if a variable of type T₃may be assigned to another variable of type T₂.

[0493] In another embodiment, the compiler may not actually use a connection graph data structure—it may use a different representation, for example, lists, to maintain information about connections between variables.

[0494] One skilled in the art would recognize that other methods of analysis could be used in the practice of the present invention. For instance, the compiler may use pointer analysis to identify thread-local variables. Pointer analysis obtains information on the set of variables that each pointer variable points to. By marking each variable corresponding to a thread-escaping variable as global_escape, and by further marking each variable which can be pointed to from a global_escape variable as global_escape, a compiler can identify those variables that are not marked global_escape as thread-local.

[0495] In other possible embodiments of this invention, the optimization of the locking operation may be performed by the run-time implementation of the locking operation rather than the (static or dynamic) compiler. In this variant, the transformation of a locking operation to a simple locking operation is done as follows. The locking operation is passed two pieces of information, preferably in only two bits. The first bit is true if the object does not escape the thread, and is information provided by escape analysis. If the object does escape, this bit is set to false. The second bit is true if the locking operation should perform the side effects, and is false otherwise. The locking operation can read these bits to determine what actions it should take. When generating code, either in the context of a static compiler or a dynamic compiler, these bits are set appropriately for the operations to be performed. The default for a comprehensive locking operation would be to set both bits to true. One skilled in the art will realize that these bits could also be carried along in the object, and set appropriately, and then reset to true, true (for a comprehensive locking operation) or true, false (for a simple locking operation), before and after each optimized locking operation. One skilled in the art will also realize that a straightforward data flow analysis can reduce the number of setting and resettings of these bits, whether in or outside of an object, by determining when a bit will have the same value at dynamically adjacent locking operations.

[0496] In the case of makeLockSimple on line 2214, the first bit is set to true, and the second is set to false. The locking operation would in this case would only perform the synchronization operations necessary to ensure mutual exclusion, and not perform any side effects. In the case of makeLockSideEffectOnly on line 2218, the bits are set to false and true, respectively, and the locking operation will not perform the synchronization necessary to ensure mutual exclusion. Again, if the bits are contained in the object itself, they will be reset after the locking operation, as described above. In the case of makeLockNull (on line 2220), both of the bits are set to false and false, and the locking operation need not perform any synchronization operation to ensure mutual exclusion or the side effects.

[0497] An embodiment of this variant of the invention is shown in pseudocode below.

[0498] 2301: lockOpt2(G, CG) {

[0499] 2302: EscapeAnalysis(G, CG)

[0500] 2303: removeSimpleLockOperations(G, M=MAIN, CG)

[0501] 2304: optimizeComprehensiveLockOperations2 (G, M=MAIN, CG)

[0502] 2305: }

[0503] This variant differs from the method of the previous section, described in FIG. 2, in the optimization of comprehensive locking operations. In the method described in the previous section, comprehensive locking operations performed on objects locked in a single thread, and whose side effects are not necessary to preserve the semantics of the program, are removed. In this variant, these locking operations are not removed, but replaced with a simpler locking operation which performs the side effects but does not perform the actual locking operation.

[0504] The differences are shown above in the lockOpt2 routine at lines 2301 to 2305 and below in the optimizeComprehensiveLockOperations2 routine at lines 2501 to 2517.

[0505] The lockOpt2procedure differs from the method of FIG. 2 first in that the side effect analysis procedure of line 206 is not performed in the variant. This step is not necessary for the current method because comprehensive locking operations are treated the same whether their side effects affect the correctness of the program or not. The second difference is the procedure called to transform the program. In the method of FIG. 1, the procedure optimizeComprehensiveLockOperations as shown above is invoked, and in lockOpt2, the procedure of optimizeComprehensiveLockOperations2, shown below, is invoked. The differences between the procedures of optimizeComprehensiveLockOperations and of optimizeComprehensiveLockOperations2 can be seen by comparing lines 2217 through 2221 and line 2513. In line 2513, the locking operation is simplified regardless of whether its side effects are necessary.

[0506] 2501: optimizeComprehensiveLockOperations2(G, M, CG) {

[0507] 2502: G_M=G(M)

[0508] 2503: M._seOptimized=true

[0509] 2504: foreach N ε G_Mdo

[0510] 2505: if N.op=procedure invocation do

[0511] 2506: M_N=N.procedure

[0512] 2507: if not M_N.seOptimized do

[0513] 2508: optimizeComprehensiveLockOperations2(G, M_N, CG)

[0514] 2509: endif

[0515] 2510: else

[0516] 2511: if N.op=O_Sthen

[0517] 2512: if notmayEscapeThread(CG, N.obj, N.stmt) then

[0518] 2513: makeLockSideEffectOnly(G_M, N)

[0519] 2514: endif

[0520] 2515: endif

[0521] 2516: endif

[0522] 2517: }

[0523] An embodiment of this variant of the first described aspect of the invention is shown in lockOpt3, below in lines 2401 to 2406.

[0524] 2401: lockOpt3 (G, CG) {

[0525] 2402: EscapeAnalysis(G, CG)

[0526] 2403: removeSimpleLockOperations(G, M=MAIN, CG)

[0527] 2404: sideEffectAnalysis(G, M=MAIN, CG, IN_MAIN=false, OUT_MAIN)

[0528] 2405: optimizeComprehensiveLockOperations3 (G, M=MAIN, CG)

[0529] 2406: }

[0530] This variant differs in the optimization of comprehensive locking operations. In the first embodiment, described previously, comprehensive locking operations performed on objects locked in a single thread, and whose side effects are not necessary to preserve the semantics of the program, are removed, and locking operations with whose side effects are necessary to preserve the semantics of the program are simplified. In this variant, the comprehensive locking operations whose side effects are necessary to preserve the semantics of the program are not simplified.

[0531] The differences are shown in lockopt3 lines 2401 to 2406, above, and optimizeComprehensiveLockOperations3 lines 2601 to 2620, below.

[0532] 2601: optimizeComprehensiveLocksOperations3(G, M, CG) {

[0533] 2602: G_M=G(M)

[0534] 2603: M._seOptimized=true

[0535] 2604: foreach N c G_Mdo

[0536] 2605: if N.op=procedure invocation then

[0537] 2606: M_N=N.procedure

[0538] 2607: if not M_N.seOptimized then

[0539] 2608: optimizeComprehensiveLocksOperations3(G, M_N, CG)

[0540] 2609: endif

[0541] 2610: else

[0542] 2611: if N.op=O_Sthen

[0543] 2612: if not mayEscapeThread(CG, N.obj, N.stmt) then

[0544] 2613: if N._IN=false then

[0545] 2614: makeLockNull(G_M, N)

[0546] 2616: endif

[0547] 2617: endif

[0548] 2618: endif

[0549] 2619: endif

[0550] 2620: enddo

[0551] 2621:}

[0552] The process described in FIG. 2 differs from the process described in the procedure called to transform the program for optimizing comprehensive locking operations. In previous embodiment, the procedure of optimizeComprehensiveLockOperations is invoked, and in this variant, the procedure of optimizeComprehensiveLockOperations3 is invoked. The differences between these procedures can be seen by comparing lines 2211 through 2219 and lines 2611 through 2615. In line 2611, it is determined that the locking operation is a comprehensive locking operation. In lines 2612 and 2613, it is determined that the object on which the locking operation is performed is not locked in another thread, and that the side effects of this locking operation do not need to be performed to ensure the correctness of the program. Finally, in line 2614, the locking operation is optimized, as described previously. In optimizeComprehensiveLockOperations the corresponding code (lines 2211 through 2219) also check for the cases here the locking operation is not needed but the sides effects are, and the case where the locking operation is not needed, but the side effects are.

[0553] An embodiment of this variant of the first described embodiment of the invention is shown in lockOpt4, below.

[0554] 2701: lockOpt4(G, CG) {

[0555] 2702: EscapeAnalysis(G, CG)

[0556] 2703: removeSimpleLockOperations(G, M=MAIN, CG)

[0557] 2704: }

[0558] This variant differs in the optimization of comprehensive locking operations. In the previously described method, comprehensive locking operations were considered when performing optimizations. In this method, comprehensive locking operations are not considered, and no attempt is made to analyze or optimize them.

[0559] The differences are shown in the process of lockOpt4, above. The process differs from that of the method of FIG. 2 in that the program analysis of line 206 is not performed to analyze the program, and line 208 is not performed to transform the program. Lines 2702 and 2703 of lockOpt4 and steps 202 and 204 of the method of FIG. 2 perform the same processes, described in the first embodiment of the invention, and discussed previously. In lockOpt4, line 2702 performs escape analysis to determine which objects may have locking operations performed on them in more than one thread, and line 2703 transforms the input program by removing simple locking operations that are performed on locks that are locked in at most one thread.

[0560] An embodiment of this variant of the invention is shown in lockOpt5, below.

[0561] 2801: lockOpt5(G, CG) {

[0562] 2802: EscapeAnalysis(G, CG)

[0563] 2803: sideEffectAnalysis(G, M=MAIN, CG, IN_MAIN=false, OUT_MAIN)

[0564] 2804: optimizeComprehensiveLockOperations(G, M=MAIN, CG)

[0565] 2805: }

[0566] This variant differs from the previously described first embodiment in the optimization of simple locking operations. In particular, step 204 of the process described above is not performed in the process described by lockOpt5. That step removes simple locking operations whenever the object being locked by that operation is locked by at most one thread.

[0567] Line 2803 of this method performs the analysis to determine which comprehensive locking operations must perform their side effects. The analysis is shown in more detail in the procedure sideEffectAnalysis at lines 2001 to 2036, and previously discussed in more detail above. Line 2804 of this method invokes the process to transform the program by removing comprehensive locking operations whose side effects and locking operation are both not needed, and simplifying the remaining locks where shown to be possible by the analysis of lines 2803 and 2804. The process of line 2804 is shown in more detail in optimizeComprehensiveLockOperations at lines 2201 to 2225, and discussed above.

[0568] An embodiment of this variant of the first described embodiment of the invention is shown in lockOpt6, below.

[0569] 2901: lockOpt6(G, CG) {

[0570] 2902: EscapeAnalysis(G, CG)

[0571] 2903: optimizeComprehensiveLockOperations2(G, M=MAIN, CG)

[0572] 2904: }

[0573] This variant differs from the previously described method in the optimization of simple locking operations. In particular, the process of line 2803 of the process described above in lockOpt5 is not performed in the process described by lockOpt62903 the process optimizeComprehensiveLockOperations2 described above. This process does not remove the comprehensive locking operations, but only simplifies them by reducing them to a simple locking operation.

[0574] An embodiment of this variant of the method is shown in lockOpt7, below.

[0575] 3001: lockOpt7(G, CG) {

[0576] 3002: EscapeAnalysis(G, CG)

[0577] 3003: sideEffectAnalysis(G, M=MAIN, CG, IN_MAIN=false, OUT_MAIN)

[0578] 3004: optimizeComprehensiveLockOperations3(G , M=MAIN, CG)

[0579] 3005: }

[0580] This variant differs in the optimization of comprehensive locking operations that can be transformed to simple locking operations but not removed. In particular, the process of line 2803 of the process described by lockOpt5, above, is not performed in the process described by lockOpt7. Instead, the present method performs for line 2803 the optimizeComprehensiveLockOperations3 process shown in pseudocode below. This process only optimizes comprehensive locking operations that can be removed.

[0581] An embodiment of this variant of the invention is shown below in lockOpt8.

[0582] 3101: lockOpt8(G, CG) {

[0583] 3102: sideEffectAnalysis(G, M=MAIN, CG, IN_MAIN=false, OUT_MAIN)

[0584] 3103: optimizeComprehensiveLockOperations8(G, M=MAIN, CG)

[0585] 3104: }

[0586] This process differs in the optimization of comprehensive locking operations. In particular, the process used by the embodiment in line 2802 (the escape analysis) of the lockOpt5 process described above is not performed in this variant process. Thus, no escape analysis is performed in this variant on the method. As well, the process of line 2804 (locking operation optimization) is not performed in this variant process, either. Instead, the present method performs for step 2804 the process described above, and does not remove the comprehensive locking operations, but only transforms them to a simple locking operation. This process is now described.

[0587] The process is shown as the procedure optimizeComprehensiveLocksOperations8, as shown below.

[0588] 3201: optimizeComprehensiveLockOperations8(G, M, CG) {

[0589] 3202: G_M=G(M)

[0590] 3203: M._seOptimized=true

[0591] 3204: foreach N c G_Mdo

[0592] 3205: if N.op=procedure invocation then

[0593] 3206: M_N=N.procedure

[0594] 3207: if not M_{N.seOptimized}then

[0595] 3208: optimizeComprehensiveLockOperations8(G, M_N, CG)

[0596] 3209: endif

[0597] 3210: else

[0598] 3211: if N.op=O_Sthen

[0599] 3212: if N.IN=false then

[0600] 3213: N.op=O_N

[0601] 3214: endif

[0602] 3215: endif

[0603] 3216: endif

[0604] 3217: }

[0605] This process differs from optimizeComprehensiveLockOperations3, discussed previously in the following way. In line 2512, a node that performs a comprehensive locking operation is checked to determine if the object being locked is accessed outside the thread. In the current method, a node performing a comprehensive locking operation is checked to see if any side effects are required (in line 3212). No check is made to determine the scope of accesses to the object being locked. In line 2513, the locking operation is replaced with an operation that only performs the side effect if the above determination is made. In the process of the current method, the comprehensive locking operation is only transformed to a simple locking operation (when possible to do so without changing the semantics of the original program), and therefore does not perform the side effects. This is done in line 3113.

[0606] While the invention has been described in terms of a single preferred embodiment, with several variants, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.

[0607] [1] Sarita V. Adve and Mark D. Hill, “Weak Ordering, A New Definition,” Proceedings of the1990 International Symposium on Computer Architecture(ISCA), June, 1990.

[0608] [2] David R. Butenhof, “Programming With Posix Threads” (Addison Wesley Professional Computing Series), Addison-Wesley Publishing Company, Reading, Mass.

[0609] [3] P. Diniz and M. Rinard, “Lock-Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs,” Proceedings of the9th Workshop on Languages and Compilers for Parallel Computing, San Jose, Calif., August 1996.

[0610] [4] P. Diniz and M. Rinard, “Synchronization Transformations for Parallel Computing,” Proceedings of24th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Paris, France, January 1997.

[0611] [5] Perry E. Emrath, Sanjoy Ghosh and David Padua, “Detecting Nondeterminacy in Parallel Program,” IEEE Software, Vol. 9, No. 1, pages 69-77, Jan. 1, 1992.

[0612] [6] Zhixi Fang, Peiyti Tang, Pen-Chung Yew and Chuan-Qi Zhu, “Dynamic Processor Self Scheduling for General Parallel Nested Loops,” IEEE Transactions on Computers, Vol 39, No. 7, pages 919-929, July 1990.

[0613] [7] James Gosling, Bill Joy and Guy L. Steele, Jr., “The Java Language Specification” (Java Series), Addison-Wesley Publishing Company, Reading, Mass.

[0614] [8] Manish Gupta and Edith Schonberg, “Static Analysis to Reduce Synchronization Costs in Data-Parallel Programs.” Proceedings of23rd SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg, Fla., January 1996.

[0615] [9] Z Li and Walid Abu-Sufah, “On Reducing Data Synchronization in Multiprocessed Loops,” IEEE Transactions on Computers, Vol C-36, pages 105-109, No. 1, January 1987

[0616] [10] Samuel P. Midkiff and David A. Padua, “Compiler Algorithms for Synchronization,” IEEE Transactions on Computers, Vol. 36, No. 12, pages 1485-1495, December 1987.

[0617] [11] M. O'Boyle and F. Bodin, “Compiler Reduction of Synchronization in Shared Virtual Memory Systems,” Proceedings of9th ACM International Conference on Supercomputing, Barcelona, Spain, July 1995.

[0618] [12] H. M. Su and P. C. Yew, “On Data Synchronization for Multiprocessors”, ACM Proceedings of the16th International Symposium on Computer Architecture, 1989, pp 416-423.

[0619] [13] C. -W. Tseng, “Compiler Optimizations for Eliminating Barrier Synchronization,” Proceedings of5th ACM Symposium on Principles and Practices of Parallel Programming, Santa Barbara, Calif., July 1995.