Method for optimizing locks in computer programs6530079Abstract A method and several variants for using information about the scope of access of objects acted upon by mutual exclusion, or mutex, locks to transform a computer program by eliminating locking operations from the program or simplifying the locking operations, while strictly performing the semantics of the original program. In particular, if it can be determined by a compiler that the object locked can only be accessed by a single thread it is not necessary to perform the "acquire" or "release" part of the locking operation, and only its side effects must be performed. Likewise, if it can be determined that the side effects of a locking operation acting on a variable which is locked in multiple threads are not needed, then only the locking operation, and not the side effects, needs to be performed. This simplifies the locking operation, and leads to faster programs which use fewer computer processor resources to execute; and programs which perform fewer shared memory accesses, which in turn not only causes the optimized program, but also other programs executing on the same computing machine to execute faster. The method also describes how information about the semantics of the locking operation side effects and the information about the scope of access can also be used to eliminate performing the side effect parts of the locking operation, thereby completely eliminating the locking operation. The method also describes how to analyze the program to compute the necessary information about the scope of access. Variants of the method show how one or several of the features of the method may be performed. Claims Having thus described our invention, what we claim as new and desire to secure by letters patent is as follows: Description BACKGROUND OF THE INVENTION
pre-existing data for call graph node
visited
IN
OUT
GEN
KILL
where, visited is true if this node is being visited in some traversal, and false otherwise, IN is true if any predecessor of the node has a true output, and false otherwise, OUT equals IN .LAMBDA.KILL V GEN for the Node, 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 KILL is false if the node operation is a comprehensive locking operation, and true otherwise. The updated fields added to nodes of the control flow graph contain information about side effects that must be handled by each lock O.sub.S in 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.sub.o 209, which is then passed to later compiler passes 107 as shown in FIG. 1. 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. 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. The Escape Analysis Phase 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.TM., 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.TM., 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. The connection graph has three kinds of edges: "points-to" edges, "deferred edges", and "field" edges. A points-to edge, denoted as x.sup.P.fwdarw.y, may be created from a pointer variable x to an object variable y. A deferred edge, x.sup.D.fwdarw.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.sub.1 to an object O.sub.2 is interpreted as a set of edges from each field in O.sub.1, to the corresponding field in O.sub.2. A field edge, x.sup.F.fwdarw.y, may be created from an object node x to a field node y. A points-to path (PtPath(x,y)) in a connection graph is defined to be a sequence of edges x.fwdarw.x.sub.1.fwdarw.x.sub.2.fwdarw.. . . .fwdarw.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.sup.+1.fwdarw.y denotes a points-to path, PtPath(x,y), with length one. 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. 301: EscapeAnalysis (G, CG) { 302: Build call-graph, CallG, of program represented by G; 303: foreach procedure n of program do 304: n.NumNodes=0; 305: n.NumPaths=0; 306: end do 307: Set WorkList=enumeration of nodes in CallG in reverse topological sort order; 308: while WorkList not empty do 309: Get first element n and delete it from WorkList; 310: Call AnalyzeStackProcedure(n, CallG, WorkList); 311: end do 312: Set WorkList=enumeration of nodes in CallG in topological sort order; 313: while WorkList not empty do 314: Get first element n and delete it from WorkList; 315: Call AnalyzeThreadProcedure(n, CallG, WorkList): 316: end do 317: In symbol table for G, mark all variables whose state is not global_escape as thread-local; 318: } 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.TM., 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). 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. 401: AnalyzeStackProcedure(n, CallG, Worklist) { 402: Build an initial connection graph, CG, for procedure n; 403: if n is marked as no-analyze then // make pessimistic assumption 404: foreach actual parameter and return node a.sub.i do 405: state(a.sub.i)=global_escape; 406: end do 407: return; 408: endif 409: Build control flow graph, CFG, of procedure n; 410: Set BBWorkList=enumeration of nodes in CFG in topological sort order; 411: while BBWorkList not empty do 412: Get first element bb and delete it from BBWorkList; 413: AnalyzeBB(n CG, CFG, bb, BBWorkList); 414: end do 415: if (IsChanged(n)) then 416: foreach caller c.sub.i of procedure n do 417: if c.sub.i is not marked as no-analyze then 418: add c.sub.i to WorkList, 419: endif 420: end do 421: endif 422: } 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.sup.th) formal parameter f.sub.i and for the return value that is a pointer, there are two nodes in the connection graph, one referred to as f.sub.i, and the other referred to as a.sub.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.sub.i to the corresponding a.sub.i. Line 403 first checks if this procedure is marked no-analyze. If so, in lines 404 through 406, each node a.sub.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. The pseudocode below describes AnalyzeBB which is called in line 413 above, and is used to analyze a given basic block bb. 501: AnalyzeBB(n, CG, CFG, bb, BBWorkList) { 502: foreach predecessor basic block p of bb in CFG do 503: foreach pointer variable v do 504: merge connections for variable v in the representation for p; 505: if merge leads to any new connection for v in bb then 506: add successors of bb in CFG to BBWorkList, 507: endif 508: end do 509: end do 510: foreach statement S of basic block bb in forward order do 511: switch (statement type) 512: case assignment: AnalyzeAssign(CG, S, bb.outEdgeInMiddle); 513: case procedure call: AnalyzeProcCall(n, CG, S); 514: case return or exit: Summarize(n, CG); 515: endswitch 516: end do 517: } 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.TM., 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. 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. The pseudocode below describes AnalyzeAssign which is called in line 512 above. 601: AnalyzeAssign (CG, S, noKill) { 602: switch (statement type) 603: case [a.sub.1.a.sub.2. . . a.sub.n =(address of) O;] 604: AnalyzeAssignCase1 (CG, S, nokill) 605: case [a.sub.1.a.sub.2. . . a.sub.n =b.sub.1.b.sub.2. . . b.sub.m ] 606: AnalyzeAssignCase2 (CG, S, noKill) 607: endswitch 608: } Lines 602 through 607 check for two types of assignment statements, which are illustrated as case [a.sub.1.a.sub.2. . . a.sub.n =(address of) O] and as case [a.sub.1.a.sub.2. . . a.sub.n =b.sub.1.b.sub.2. . . b.sub.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. The pseudocode below describes AnalyzeAssignCase1 which analyzes statements of the form a.sub.1.a.sub.2. . . a.sub.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.TM., the statement may appear as a.sub.1.a.sub.2. . . a.sub.n =new Constructor(. . .). 701: AnalyzeAssignCase1(CG, S, nokill) { 702: // S is: a.sub.1.a.sub.2. . . a.sub.n =(address of) O; 703: Create a new object O.sub.n (if one does not exist for this site); 704: if (a.sub.1 is a formal parameter and no phantom node for a.sub.1 exists) then 705: Create phantom nodes O.sub.2, O.sub.3, . . . O.sub.n-1 such that a.sub.2 is a field in O.sub.2, a.sub.3 is a field in O.sub.3, and so on; Insert points-to edge from a.sub.1 to O.sub.2, from a.sub.2 to O.sub.3, and so on. 706: endif 707: if (n=1) then 708: Let R be the set of incoming deferred edges into a.sub.1 ; 709: Let S be the set of outgoing points-to edges from a.sub.1 ; 710: Let T be the set of outgoing deferred edges from a.sub.1 ; 711: if (not noKill) then 712: Add new points-to edges from the source node of edges in R to target nodes of edges in S; 713: Add new deferred edges from the source node of edges in R to target nodes of edges in T; 714: Delete all edges in the sets R, S, and T from CG; 715: endif 716: Add a points-to edge from a.sub.1 to O.sub.n ; 717: else 718: Find all the field nodes a.sub.n starting from node a.sub.1 corresponding to the path a.sub.1.a.sub.2. . . a.sub.n ; Let A be the set of all a.sub.n nodes; 719: if (for any a.sub.i node, 1.ltoreq.i.ltoreq.n, state(a.sub.i)=global_escape) then 720: MakeBottom(O.sub.n); 721: else 722: Add a points-to edge from each node in A to O.sub.n ; 723: endif 724: endif 725: } Line 703 first creates a new object node O.sub.n (if one does not already exist for this site). Next, line 705 creates phantom nodes and edges in case a.sub.1 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.sub.1 =(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.sub.1 ; 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.TM., the previous connections of a.sub.1 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.TM.) within the procedure. The present invention allows previous connections of a.sub.1 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.sub.1 would not be visible at any exception handling code outside the current procedure, it is safe to kill the previous connections of a.sub.1 within the procedure in this case. If it is safe to kill the previous data flow information, lines 712 and 713 bypass a.sub.1 by connecting the predecessor nodes of a.sub.1 with the successor nodes of a.sub.1, and 714 deletes the previous incoming edges into a.sub.1 and the previous outgoing edges from a.sub.1. These steps 712 through 714 may actually be implemented using a new node for a.sub.1 and using this new node for a.sub.1 instead of the previous node for a.sub.1 from this point onwards. A points-to edge is added from the node for a.sub.1 to O.sub.n in 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.sub.1 corresponding to the path a.sub.1.a.sub.2 . . . a.sub.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.sub.n (and any node reachable from it) is also marked global_escape by invoking MakeBottom on O.sub.n. Finally, in line 722, a points-to edge is added from each node in the set A (computed in line 718) to O.sub.n. The following pseudocode describes AnalyzeAssignCase2 which analyzes statements of the form a.sub.1.a.sub.2. . . a.sub.n =b.sub.1.b.sub.2. . . b.sub.n. 801: AnalyzeAssignCase2 (CG, S, noKill){ 802: // S is: a.sub.1.a.sub.2. . . a.sub.n =b.sub.1.b.sub.2. . . b.sub.m ; 803: if (a.sub.1 is a formal parameter and no phantom node for a.sub.1 exists) 804: Create phantom nodes O.sub.2, O.sub.3, . . . O.sub.n-1 such that a.sub.2 is a field in O.sub.2, a.sub.3 is a field in O.sub.3, and so on; Insert points-to edge from a.sub.1 to O.sub.2, from a.sub.2, to O.sub.3, and so on. 805: endif 806: if (b.sub.1 is a formal parameter and no phantom node for b.sub.1 exists) 807: Create phantom nodes Q.sub.2, Q.sub.3, . . . Q.sub.m-1 such that b.sub.2 is a field ii Q.sub.2, b.sub.3 is a field in Q.sub.3, and so on; Insert points-to edge from b.sub.1 to Q.sub.2, from b.sub.2 to Q.sub.3, and so on. 808: endif 809: Find all the field nodes b.sub.m starting from node b.sub.1 corresponding to the path b.sub.1.b.sub.2. . . b.sub.m ; Let B be the set of all b.sub.m nodes. 810: if (n=1) then 811: Let R be the set of incoming deferred edges into a.sub.1 ; 812: Let S be the set of outgoing points-to edges from a.sub.1 ; 813: Let T be the set of outgoing deferred edges from a.sub.1 ; 814: if (a.sub.1 is a pointer and not noKill) then 815: Add new points-to edges from the source node of edges in R to target nodes of edges in S; 816: Add new deferred edges from the source node of edges in R to target nodes of edges in T; 817: Delete all edges in the sets R, S, and T from CG; 818: endif 819: Add a deferred edge from a.sub.1 to each node in B; 820: else 821: Find all the field nodes an starting from node a.sub.1 corresponding to the path a.sub.1.a.sub.2. . . a.sub.n ; Let A be the set of a.sub.n nodes. 822: if (for any a.sub.i node, 1.ltoreq.i.ltoreq.n, state(a)=global escape) then 823: foreach node b in B do 824: MakeBottom(b); 825: end do 826: else 827: Add a deferred edge from each node in A to each node in B; 828: endif 829: endif 830: } As described above for AnalyzeAssignCase 1, phantom nodes and edges are created whenever a.sub.1 or b.sub.1 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.sub.1 corresponding to the path b.sub.1.b.sub.2. . . b.sub.m. Let all of these field nodes form the set B. When m is 1, a special case a.sub.1 =b.sub.1. b.sub.2. . . b.sub.m is handled in lines 811 through 819. If a.sub.1 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.sub.1 by connecting the predecessor nodes of a with the successor nodes of a.sub.1 and line 817 deletes the previous incoming edges into a.sub.1 and the previous outgoing edges from a.sub.1. These steps 815 through 817 may actually be implemented, as for the previous case, using a new node for a.sub.1 and using this new node for a.sub.1 instead of the previous node for a.sub.1 from this point onwards. A points-to edge is added from the node for a.sub.1 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.sub.1 corresponding to the path a.sub.1.a.sub.2. . . a.sub.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). The following pseudocode describes AnalyzeProcCall which is called at line 513, above. 901: AnalyzeProcCall(S){ 902: Let <a.sub.i, a.sub.i >, 0.ltoreq.i.ltoreq.n-1 be the actual parameter pairs at S. 903: Let <a.sub.n, a.sub.n >be the return node pair at S. 904: foreach target method m.sub.i at S do 905: // Multiple candidate target methods might exist due to virtual call. 906: foreach object node n.sub.o of the callee reachable from a.sub.i of the callee do 907: visited (n.sub.o)=false; 908: end do 909: foreach <a.sub.i, a.sub.i >pair do 910: // For each object node n.sub.o reachable from a.sub.i of the callee, compute 911: // its equivalent object nodes, EquivObj(n.sub.o, S), of the caller. 912: // In doing so, create phantom nodes if necessary. 913: ComputeEquivNodes (a.sub.i, {a.sub.i }, S); 914: end do 915: foreach a.sub.i, 0.ltoreq.i.ltoreq.n do 916: // For each object node o.sub.i reachable from a.sub.i of the callee, 917: // if o.sub.i.sup.F.fwdarw.f.sub.j.sup.P.fwdarw.o.sub.k, make sure 918: // (1) o.sub.i.sup.P.fwdarw.f.sub.j.sup.P.fwdarw.o.sub.k, for all o.sub.i 's 919: // equivalent nodes o.sub.i, and for all o.sub.k 's equivalent nodes o.sub.k ; 920: // (2) any deferred edge from f.sub.i to another field node or a.sub.l will have 921: // its corresponding edge between equivalent nodes at the caller 922: InsertEdges(a.sub.i, S); 923: end do 924: end do 925: } 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. 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. 1001: ComputeEquivNodes(f.sub.ee : node; EquivF: set of nodes, S: call.site) { 1002: // EqvivF is the set of equivalent nodes of fee. 1003: // Subscript "ee" stands for callee. and "er" stands for caller. 1004: if (state(f.sub.ee)=global_escape) then 1005: foreach (f.sub.er.epsilon. EquivF) do 1006: MakeBottom(f.sub.er); 1007: end do 1008: return; 1009: endif 1010: foreach object node n.sub.o s . t. f.sub.ee.sup.P.fwdarw.n.sub.o do 1011: if visited(n.sub.o)=true then 1012: continue; // skip the following with the current n.sub.o 1013: endif 1014: visited (n.sub.o)=true; 1015: // n.sub.o is pointed to by f.sub.ee 1016: foreach n .sub.o .epsilon. {n .sub.o.vertline. f.sub.er.sup.+1.fwdarw.n .sub.0, f.sub.er .epsilon. EquivF} do 1017: // f.sub.er is one of f.sub.ee 's equivalent nodes of the caller. 1018: // n .sub.o is one of the nodes pointed to by f.sub.er. 1019: // If no such n .sub.o exists, create one phantom node. 1020: EqF={}; // initialize EqF to empty set 1021: if n .sub.o .epsilon. EquivObj(n.sub.o, S) then 1022: EquivObj(n.sub.o, S)=EquivObj(n.sub.o, S) U {n .sub.o }; 1023: // add n .sub.o to EquivObj(n.sub.o, S) 1024: endif 1025: foreach f .sub.ee s.t. n.sub.o.sup.F.fwdarw.f .sub.ee do 1026: EqF={f .sub.er.vertline.n .sub.o.sup.F.fwdarw.f .sub.er, f id (f .sub.ee)=f id (f .sub.er)}; 1027: // Matching field nodes of n .sub.o 1028: // become equivalent field nodes of f.sub.ee 1029: ComputeEquivNodes(f .sub.ee, EqF, S); // invoke recursively 1030: end do 1031: end do 1032: end do 1033: } The first parameter, f.sub.ee is either an actual parameter node or a field node of an object node. Line 1004 checks if the callee node f.sub.ee is marked global_escape. In that case, each equivalent node of f.sub.ee is 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.sub.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.sub.ee. These caller's object nodes are added to the set of equivalent nodes of the callee node n.sub.0 in lines 1021 through 1024. Then, for each field node of n.sub.0 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.sub.0 and the equivalent caller nodes' matching field nodes, EqF as the new parameters. The following pseudocode describes InsertEdges which is called in line 922, and is used to insert edges out of the equivalent node of n.sub.i in the caller to reflect the effect of the procedure call. p01101: InsertEdges(n.sub.i : node, S: callsite) { 1102: if (visited(n.sub.i)=true) then 1103: return; 1104: endif 1105: visited(n.sub.i)=true; 1106: if n.sub.i is an object node then 1107: foreach objectnode o.sub.k s.t. n.sub.i.sup.F.fwdarw.f.sub.j.sup.P.fwdarw.o.sub.k do 1108: // o.sub.k is pointed to by f.sub.j, which is a field node of n.sub.i 1109: foreach object node n .sub.i .epsilon. EquivObj(n.sub.i, S) do 1110: foreach object node o .sub.k .epsilon. EquivObj(o.sub.k, S) do 1111: insert a points-to edge, if not already existing, from f .sub.j to o .sub.k, where n .sub.i.sup.F.sub.j.fwdarw.f .sub.j 1112:: end do 1113: end do 1114: foreach object node o.sub.i s.t. o.sub.i.sup.F.sub.m.fwdarw.f.sub.m, and there exists a deferred edge from f.sub.j to f.sub.m do 1115: foreach object node n .sub.i .epsilon. EquivObj(n.sub.i, S) do 1116: foreach object node o .sub.i .epsilon. EquivObj(o.sub.i, S) do 1117: insert a deferred edge, if not already existing, from f .sub.j to f .sub.m, where n .sub.i.sup.F.sub.j.fwdarw.f .sub.j and o .sub.i.sup.F.sub.m.fwdarw.f .sub.m ; 1118: end do 1119: end do 1120: end do 1121: foreach a.sub.p to which there exists a deferred edge from f.sub.j do 1122: insert deferred edges from f .sub.j of all n.sub.i 's equivalent nodes to the equivalent node a .sub.p of a.sub.p in the caller; 1123: end do 1124: InsertEdges(o.sub.k, S); // recursively invoke. 1125: end do 1126: else 1127: foreach edge e.sub.j from n.sub.i to n.sub.k do 1128: insert an edge of the same type from equivalent nodes, n .sub.i, of n.sub.i to equivalent nodes, n .sub.k, of n.sub.k in the caller; 1129: if n.sub.k is not a field node then 1130: InsertEdges(n.sub.k, S); 1131: endif 1132: end do 1133: endif 1134: } First, line 1102 checks, using a version-numbering scheme, if n.sub.i has already been visited. If so, the procedure returns in line 1103. The node n.sub.i is marked visited, using the version-numbering scheme, in 1105. Line 1106 checks if n.sub.i is an object node, and lines 1007 through 1125 handle that case. Loop 1107 identifies, for each field, f.sub.j, of the object node, n.sub.i, in the callee's connection graph, the set of object nodes, o.sub.k, that have a points-to edge, onto from f.sub.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.sub.i, to caller's object nodes equivalent to o.sub.k (the equivalent nodes of n.sub.i are iterated over in Loop 1109 and the equivalent nodes of o.sub.k are iterated over in Loop 1110). Next, Loop 1114 iterates over each object node o.sub.k, that owns a field f.sub.m to which there is a deferred edge from field f.sub.j of n.sub.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.sub.i, to the matching field nodes of the caller's object nodes equivalent to o.sub.l (the equivalent nodes of n.sub.i are iterated over in Loop 1115 and the equivalent nodes of o.sub.l, are iterated over in Loop 1116). Next, Loop 1121 iterates over each actual parameter node or return node, a.sub.p, to which there is a deferred edge from f.sub.j. Line 1122 inserts deferred edges from the matching field nodes of the caller's object nodes equivalent to n.sub.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.sub.k in place of n.sub.i, to ensure that edges out of o.sub.k or its fields are reflected in the caller. Lines 1127 through 1132 take care of the case where n.sub.i is not an object node (i.e., it may be an actual parameter or return node). Loop 1127 iterates over each outgoing edge from n.sub.i. For each such node n.sub.k, 1128 inserts edges from the equivalent nodes of n.sub.i to the equivalent nodes of n.sub.k in the caller's connection graph. Furthermore, if n.sub.k is an object node, line 1130 recursively invokes the procedure for n.sub.k, to ensure that edges out of n.sub.k or its fields are reflected in the caller. The following pseudocode describes MakeBottom, which is called above in lines 720, 824 and 1006. 1201: MakeBottom(v) { 1202: if (state(v).noteq.global_escape) then 1203: state(v)=global_escape; 1204: foreach node x reachable from v do 1205: if (state(x).noteq.global_escape) then 1206: state(x)=global escape; 1207: endif 1208: end do 1209: endif 1210: } 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. The following pseudocode describes Summarize, which is called in line 514, above. 1301: Summarize(n,CG) { 1302: foreach formal parameter f.sub.i of procedure n do 1303: foreach node v in CG reachable from f.sub.i do 1304: if (state(v)=procedure_local) then 1305: state(v)=arg_escape; 1306: endif 1307: if a PtPath v.sup.+1.fwdarw.w exists, but the edge v.sup.P.fwdarw.w does not exist then 1308: add edge v.sup.P.fwdarw.w; 1309: endif 1310: remove all deferred edges out of v; 1311: enddo 1312: enddo 1313:} Loop 1302 iterates over each formal parameter, f.sub.i, of the given procedure n. Loop 1303 iterates over each node, v, in the connection graph that is reachable from .sub.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.sup.P.fwdarw.w (line 1308) that did not previously exist for every PtPath v.sup.+1.fwdarw.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. The following pseudocode describes IsChanged, which is called in line 415, above. 1401: IsChanged(n) { 1402: RealNodes={object_nodes, field_nodes, local_variable_nodes, 1403: actual_nodes, return_node } 1404: NumNodes=SizeOf (Real Nodes); // number of nodes in RealNodes set 1405: NumPaths=number of length one point to paths among nodes in RealNodes; 1406: if (NumNodes>=n.NumNodes) or (NumPaths>=n.NumPaths) then 1407: n. NumNodes=NumNodes; 1408: n.NumPaths=Numpaths; 1409: return true; 1410: else 1411: return false; 1412: endif 1413: } 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. The following pseudocode describes AnalyzeThreadProcedure, which is called in line 315, above. 1501: AnalyzeThreadProcedure(n, CallG, WorkList) { 1502: if any caller of n is marked as no-analyze then 1503: foreach object variable o.sub.i in procedure n do 1504: if (state(o.sub.i)=arg_escape) then 1505: Makebotttom(o.sub.i); 1506: endif 1507: end do 1508: return; 1509: endif p11510: procChange=false; 1511: foreach thread object variable o.sub.i in procedure do 1512: foreach field f.sub.k of o.sub.i do 1513: if state(f.sub.k).noteq.global_escape and f.sub.k is accessed before o.sub.i is killed then 1514: MakeBottom(f.sub.k); procChange=true; 1515: endif 1516: end do 1517: end do 1518: foreach object variable o.sub.i with state arg_escape in procedure n do 1519: foreach eo.sub.i that is an equivalent object of o.sub.i in a caller of n do 1520: if (state(eo.sub.i)=global escape) then 1521: if (state(o.sub.i) g global escape) then 1522: MakeBottom(o.sub.i); 1523: procChange=true; 1524: endif 1525: endif 1526: end do 1527: end do 1528: if (procChange) then 1529: foreach callee c.sub.i of procedure n do 1530: if c.sub.i is not marked as no-analyze then 1531: add c.sub.i to WorkList; 1532: endif 1533: end do 1534: endif 1535: } First, line 1502 checks if any caller of the procedure n is marked no-analyze. If so, each object node o.sub.i of the procedure that was previously marked arg_escape and each node reachable from o.sub.i is 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.sub.k, of the thread object o.sub.i. If f.sub.k is not already marked global_escape and f.sub.k is used before o.sub.i is killed (which can be determined by standard data flow analysis), then line 1514 marks f.sub.k and nodes reachable from it as global_escape, and sets procChange to true. Loop 1518 iterates over each object variable node, o.sub.i, in the connection graph that is marked arg_escape. Loop 1519 iterates over each equivalent object, eo.sub.i of o.sub.i over all call-sites in different callers of procedure n. Line 1520 checks if eo.sub.i is marked global_escape. In that case, if o.sub.i was 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. The Optimization of Simple Locking Operations Phase 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. 1901: removeSimpleLockOperations(G, M, CG) { 1902: GM=G(M) 1903: M.nseRemoved=true 1904: foreach node N in G do 1905: if N.op is a procedure invocation then 1906: M.sub.N =N.procedure 1907: if not M.sub.N.nseRemoved then 1908: removeSimpleLockOperations(G, M.sub.N, CG) 1909: endif 1910: else 1911: if N.op=O.sub.N and IsThreadLocal(N.obj,CG,N.stmt) then 1912: removeLock(G.sub.M, N) 1913: endif 1914: endif 1915: } In line 1902, G.sub.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. Line 1904 begins an iteration over each node of G.sub.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. The Analysis of Side Effects Phase Side Effect Analysis The sideEffectAnalysis process, as shown in FIG. 2, step 206, logically creates a table (T.sub.sideEffects) with an entry for each node N in G, ,where N.op is a comprehensive locking operation. T.sub.sideEffects [N] is true if the side effects, of the locking operation at node N, must be performed. The table T.sub.sideEffects may 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. 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. 2001: sideEffectAnalysis(G, M, CG, IN, OUT) { 2002: G.sub.m =G(M) 2003: foreach node N .epsilon. G.sub.m do 2004: N..sub.IN =false 2005: N..sub.OUT =false 2006: if N.type.noteq.procedureCall then 2007: N..sub.GEN =false 2008: N..sub.KILL =true 2009: if (.E-backward.k s.t. V.sub.k .epsilon. N .LAMBDA.V.sub.k.lval=true) N..sub.GEN =true 2010: if ((N.op=O.sub.S) and (not inside exception block)) N..sub.KILL =false 2011: else 2012: M=N.procedure 2013: if M.summarized then 2014: N..sub.GEN =M..sub.GEN 2015: N..sub.KILL =M..sub.KILL 2016: else 2017: if (M.visited) then 2018: N..sub.GEN =true 2019: N..sub.KILL =true 2020: else 2021: summarizeMethodSideEffects(G, M, CG, N..sub.GEN, N..sub.KILL) 2022: endif 2023: endif 2024: enddo 2025: ENTRY..sub.IN =IN 2026: C=true 2027: while(C=true) do 2028: C=false 2029: foreach node N in a traversal of G.sub.M do 2030: N..sub.IN =-{OUT.sub.P /P .epsilon. N.pred} 2031: OUT.sub.TEMP =N..sub.OUT 2032: N..sub.OUT =(N..sub.IN. N..sub.KILL)-N..sub.GEN 2033: C=C-(OUT.sub.TEMP.noteq.N..sub.OUT) 2034: enddo 2035: enddo 2036: OUT=EXIT..sub.OUT 2037: } 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.sub.M that tells what objects at the node N are affected by locking operation side effects (N..sub.GEN); and what objects' side effect requirements are provided for by the node (N..sub.KILL) Lines 2025 to 2035 takes the just-modified G.sub.M and 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. Lines 2004 and 2005 fill in default values for N..sub.IN, N..sub.OUT. Lines 2007 and 2008 set defaults for N..sub.GEN and N..sub.KILL when the node is not a procedure invocation. All but N..sub.KILL are set to false, with N..sub.KILL set to true. N..sub.IN is 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..sub.OUT is initially set to false, indicating that no objects affected by locking operation side effects reach the end of the node. N..sub.GEN is set to false, indicating no objects operations are performed in the node that require locking operation side effects. N..sub.KILL is 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..sub.GEN flag 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..sub.KILL set to false if the node contains an O.sub.S operation, i.e. a comprehensive locking operation. This reflects the O.sub.S node performing the side effect for all previously written objects for which no other O.sub.S intervenes between the writing of the object and the execution of this O.sub.S statement. 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..sub.GEN and N..sub.KILL structures. 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..sub.GEN and M..sub.KILL and is either copied to, or referenced as, N..sub.GEN and N..sub.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..sub.GEN to true and N..sub.KILL to 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.sub.S, and that no side effects prior to the procedure M call at node N are taken care of by any O.sub.S locking 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. In this case, summarizeMethodSideEffects, described in pseudocode and discussed below, is invoked with arguments G, M, CG, N..sub.GEN and N..sub.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..sub.GEN and N..sub.KILL to also have that information. 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.sub.M), annotated with the node summary information (N..sub.KILL and N..sub.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..sub.IN. N..sub.OUT, the current information about all objects affected by a comprehensive locking operation after the execution of node N is saved in OUT.sub.TEMP by line 2031. Line 2032 then computes a new value for N..sub.OUT by removing from N..sub.IN all 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.sub.TEMP with the newly computed value of N..sub.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. Below is pseudocode describing the method for summarizeMethodSideEffects called in line 2021, above. 2101: summarizeMethodSideEffects(G, M, CG, GEN, KILL) { 2102: M.visited=true 2103: G.sub.M =G(M) 2104: if G.sub.M =null then 2105: GEN=true 2106: KILL=true 2107: else 2108: sideEffectsAnalysis(G, M, CG, false, GEN) 2109: sideEffectsAnalysis(G, M, C, CG, true, KILL) 2110: endif 2111: M..sub.GEN =GEN 2112: M..sub.KILL =KILL 2113: M.summarized=true 2114: M.visited=false 2115: } 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. 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. 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. 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. 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. 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. 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. The Optimization of Comprehensive Locking Operations Phase Below is pseudocode describing the method of step 208 in FIG. 2, for optimizeComprehensiveLockOperations. 2201: optimizeComprehensiveLockOperations(G, M, CG) { 2202: G.sub.M =G(M) 2203: M..sub.seOptimized =true 2204: foreach n .epsilon.aQ G.sub.M do 2205: if N.op is a procedure invocation then 2206: M.sub.N =N.procedure 2207: if not M.sub.N.seOptimized then 2208: optimizeComprehensiveLockOperations(G, M.sub.N, CG) 2209: endif 2210: else 2211: if N.op=O.sub.S then 2212: if not IsThreadLocal(N.obj, CG, N.stmt) then 2213: if N..sub.IN =false then 2214: makeLockSimple(G.sub.M, N) 2215: endif 2216: else 2217: if N..sub.IN =true then 2218: makeLockSideEffectOnly (G.sub.M, N) 2219: else 2220: makeLockNull(G.sub.M, N) 2221: endif 2222: endif 2223: endif 2224: endif 2225: } This routine takes as inputs G, M, and CG and produces a transformed program by modifying the representation G.sub.M of 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. 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. The loop at line 2204 visits each node in G.sub.M in 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. The case where the node in G.sub.M is not a procedure invocation is handled in lines 2211 through 2220. If the node is an O.sub.S operations (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.sub.S is replaced with an operation O'.sub.S that 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. If the node is an O.sub.S operation, but the object being locked does not escape (line 2216), but there are side effects (the if at line 2217 is true), the O.sub.S operation 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. 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. 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. 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. Variants of Escape Analysis 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.TM.. 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.sub.1 to another variable that points to type T.sub.2 if the type system allows a variable of type T.sub.1 to be assigned to another variable of type T.sub.2. A points-to edge is allowed only from a variable that points to type T.sub.1 to another variable of type T.sub.2 if the type system allows a variable of type T.sub.1 to be assigned to another variable of type T.sub.2. A field edge is allowed from a variable of type T.sub.1 to variable of type T.sub.2 if under the type system, T.sub.1 has a member of type T.sub.3 and if a variable of type T.sub.3 may be assigned to another variable of type T.sub.2. 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. 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. Variants of Methods for Reducing and Simplifying Locking Operations 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. 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. Reducing and Simplifying Locking Operations In Programs with Comprehensive Locking Operations and Simple Locking Operations, by Removing Where Possible Simple Locking Operations, And by Transforming to Simple Locking Operations, Where Possible, Comprehensive Locking Operations An embodiment of this variant of the invention is shown in pseudocode below. 2301: lockOpt2(G, CG) { 2302: EscapeAnalysis(G, CG) 2303: removeSimpleLockOperations(G, M=MAIN, CG) 2304: optimizeComprehensiveLockOperations2 (G, M=MAIN, CG) 2305: } 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. 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. 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. 2501: optimizeComprehensiveLockOperations2(G, M, CG) { 2502: G.sub.M =G(M) 2503: M..sub.seOptimized =true 2504: foreach N .epsilon. G.sub.M do 2505: if N.op=procedure invocation do 2506: M.sub.N =N.procedure 2507: if not M.sub.N.seOptimized do 2508: optimizeComprehensiveLockOperations2(G, M.sub.N, CG) 2509: endif 2510: else 2511: if N.op=O.sub.S then 2512: if notmayEscapeThread(CG, N.obj, N.stmt) then 2513: makeLockSideEffectOnly(G.sub.M, N) 2514: endif 2515: endif 2516: endif 2517: } Optimizing Locking Operations in Programs with Comprehensive Locking Operations and Simple Locking Operations, by Removing, Where Possible, Either Kind of Locking Operations An embodiment of this variant of the first described aspect of the invention is shown in lockOpt3, below in lines 2401 to 2406. 2401: lockOpt3 (G, CG) { 2402: EscapeAnalysis(G, CG) 2403: removeSimpleLockOperations(G, M=MAIN, CG) 2404: sideEffectAnalysis(G, M=MAIN, CG, IN.sub.MAIN =false, OUT.sub.MAIN) 2405: optimizeComprehensiveLockOperations3 (G, M=MAIN, CG) 2406: } 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. The differences are shown in lockopt3 lines 2401 to 2406, above, and optimizeComprehensiveLockOperations3 lines 2601 to 2620, below. 2601: optimizeComprehensiveLocksOperations3(G, M, CG) { 2602: G.sub.M =G(M) 2603: M..sub.seOptimized =true 2604: foreach N c G.sub.M do 2605: if N.op=procedure invocation then 2606: M.sub.N =N.procedure 2607: if not M.sub.N.seOptimized then 2608: optimizeComprehensiveLocksOperations3(G, M.sub.N, CG) 2609: endif 2610: else 2611: if N.op=O.sub.S then 2612: if not mayEscapeThread(CG, N.obj, N.stmt) then 2613: if N..sub.IN =false then 2614: makeLockNull(G.sub.M, N) 2616: endif 2617: endif 2618: endif 2619: endif 2620: enddo 2621:} 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. Optimizing Locking Operations in Programs with Simple Locking Operations by Removing, there Possible, Simple Locking Operations An embodiment of this variant of the first described embodiment of the invention is shown in lockOpt4, below. 2701: lockOpt4(G, CG) { 2702: EscapeAnalysis(G, CG) 2703: removeSimpleLockOperations(G, M=MAIN, CG) 2704: } 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. 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. Optimizing Locking Operations in Programs with Comprehensive Locking Operations, by Removing, Where Possible, Comprehensive Locking Operations; and Transforming the Comprehensive Locking Operations That Cannot Be Removed Into a Simple Locking Operation An embodiment of this variant of the invention is shown in lockOpt5, below. 2801: lockOpt5(G, CG) { 2802: EscapeAnalysis(G, CG) 2803: sideEffectAnalysis(G, M=MAIN, CG, IN.sub.MAIN =false, OUT.sub.MAIN) 2804: optimizeComprehensiveLockOperations(G, M=MAIN, CG) 2805: } 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. 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. Optimizing Locking Operations in Programs Having Comprehensive Locking Operations, by Simplifying the Comprehensive Locking Operations So as to Only Perform a Simple Locking Operation An embodiment of this variant of the first described embodiment of the invention is shown in lockOpt6, below. 2901: lockOpt6(G, CG) { 2902: EscapeAnalysis(G, CG) 2903: optimizeComprehensiveLockOperations2(G, M=MAIN, CG) 2904: } 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. Optimizing Locking Operations in Programs with Comprehensive Locking Operations, by Removing the Comprehensive Locking Operations When Doing So Does Not Affect the Semantics of the Program Being Transformed An embodiment of this variant of the method is shown in lockOpt7, below. 3001: lockOpt7(G, CG) { 3002: EscapeAnalysis(G, CG) 3003: sideEffectAnalysis(G, M=MAIN, CG, IN.sub.MAIN =false, OUT.sub.MAIN) 3004: optimizeComprehensiveLockOperations3(G , M=MAIN, CG) 3005: } 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. Optimizing Locking Operations in Programs Having Comprehensive Locking Operations, by Transforming the Comprehensive Locking Operations to Simple Lock Operations An embodiment of this variant of the invention is shown below in lockOpt8. 3101: lockOpt8(G, CG) { 3102: sideEffectAnalysis(G, M=MAIN, CG, IN.sub.MAIN =false, OUT.sub.MAIN) 3103: optimizeComprehensiveLockOperations8(G, M=MAIN, CG) 3104: } 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. The process is shown as the procedure optimizeComprehensiveLocksOperations8, as shown below. 3201: optimizeComprehensiveLockOperations8(G, M, CG) { 3202: G.sub.M =G(M) 3203: M..sub.seOptimized =true 3204: foreach N c G.sub.M do 3205: if N.op=procedure invocation then 3206: M.sub.N =N.procedure 3207: if not M.sub.N..sub.seOptimized then 3208: optimizeComprehensiveLockOperations8(G, M.sub.N, CG) 3209: endif 3210: else 3211: if N.op=O.sub.S then 3212: if N.IN=false then 3213: N.op=O.sub.N 3214: endif 3215: endif 3216: endif 3217: } 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. 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. REFERENCES [1] Sarita V. Adve and Mark D. Hill, "Weak Ordering, A New Definition," Proceedings of the 1990 International Symposium on Computer Architecture (ISCA), June, 1990. [2] David R. Butenhof, "Programming With Posix Threads" (Addison Wesley Professional Computing Series), Addison-Wesley Publishing Company, Reading, Mass. [3] P. Diniz and M. Rinard, "Lock-Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs," Proceedings of the 9th Workshop on Languages and Compilers for Parallel Computing, San Jose, Calif., August 1996. [4] P. Diniz and M. Rinard, "Synchronization Transformations for Parallel Computing," Proceedings of 24th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Paris, France, January 1997. [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. [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. [7] James Gosling, Bill Joy and Guy L. Steele, Jr., "The Java Language Specification" (Java Series), Addison-Wesley Publishing Company, Reading, Mass. [8] Manish Gupta and Edith Schonberg, "Static Analysis to Reduce Synchronization Costs in Data-Parallel Programs." Proceedings of 23rd SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg, Fla., January 1996. [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 [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. [11] M. O'Boyle and F. Bodin, "Compiler Reduction of Synchronization in Shared Virtual Memory Systems," Proceedings of 9th ACM International Conference on Supercomputing, Barcelona, Spain, July 1995. [12] H. M. Su and P. C. Yew, "On Data Synchronization for Multiprocessors", ACM Proceedings of the 16th International Symposium on Computer Architecture, 1989, pp 416-423. [13] C. -W. Tseng, "Compiler Optimizations for Eliminating Barrier Synchronization," Proceedings of 5th ACM Symposium on Principles and Practices of Parallel Programming, Santa Barbara, Calif., July 1995.
| |||||||