4.Algorithms sulting set is any member of SUS.S.FIND(z)returns the We present the algorithms used in MAHJONG.In Sec- representative of the disjoint set in S that contains z. tion 4.1,we give some domains used and then the main MAHJONG first initializes W by adding to it a singleton algorithm.In Sections 4.2-4.5,we describe the algorithms set for each object (lines 1-3).Then it iterates over every of its four components introduced in Sections 3.2-3.5. pair of objects,oi and o;in H,that are not yet merged,and merges the pair if both are type-consistent(lines 4-13). 4.1 MAHJONG According to line 5,oi and o;are mergeable only if both For a program,we use the three domains:(1)H is the set of have the same type.The function TYPEOF:H->Treturns all abstract heap objects (i.e.,allocation sites),(2)F is the the type of a given object and a special type for onm. set of all field names,and (3)T is the set of all types.Note To check the type consistency of oi and oj by Defini- that we have used H earlier in Definition 2.2. tion 2.1 efficiently,we handle its two conditions separately, Now,we can formally define the input and output of with Condition 2 in lines 6-7 and Condition 1 in lines 8 MAHJONG.MAHJONG takes a field points-to graph,FPG= 12.In lines 6-7.the function SINGLETYPE-CHECK (N.E),which is a directed weighted graph,as input.A node HxFPG{TRUE,FALSE}is applied to see if Condition 2 oiE N=H represents a heap object in the program.An holds for both o;and oj.If so,MAHJONG then proceeds to edge(oi,f,oj)∈ECN×F×N indicates thato-f points build the NFAs for the two objects(Section 4.2),convert the to oj.We assume that the FPG contains a dummy node onu NFAs to their equivalent DFAs(Section 4.3),and finally,test to represent null.If oi.f=null,then (oi,f,onu)EE.We their equivalence (Section 4.4).If the two DFAs are equiv- also assume(onu,f,onu1)EEfor every field f EF. alent,then MAHJONG calls W.UNION(o:,oj)to merge oi The output of MAHJONG is a new heap abstraction,rep- and oj at line 13.Finally,in lines 14-16,MAHJONG builds resented by a merged object map,MOM CHH,which a new heap abstraction as desired (Section 4.5). relates an object in an equivalence class in H/=to its rep- 4.2 The NFA Builder resentative object (as described in Section 3.5). Given an object o,Algorithm 2 (NFA-BUILDER)builds an NFA,A。=(Q,∑，d,qo,T,y),according to the mapping Algorithm 1:MAHJONG from the field points-to graph rooted at o to Ao in Figure 4. Input FPG (Field Points-to Graph) Output:MOM (Merged Object Map) Algorithm 2:NFA-BUILDER 1 Let W be a new set 2 foreach o∈Hdo Input 0 (Input object) (Field Points-to Graph) 3 Add fo to W FPG=(N,E) Output: NFA =(Q,S,6,90,I,Y) 4 foreach oi,oj E Hs.t.W.FIND(oi)W.FIND(o;)do 1q0=0 5 if TYPEOF(oi)==TYPEOF(oj)and 2 Let O be a set of objects reachable from o in FPG SINGLETYPE-CHECK(oi,FPG)and 3 Let X and I be two new sets SINGLETYPE-CHECK(oj,FPG)then 4 Let y and 6 be two new maps NFAO:NFA-BUILDER(0,FPG) s foreach o:∈Qdo 9 NFAoj NFA-BUILDER(0j,FPG) ∑=∑FIELDSOF(O) o DFAO=DFA-CONVERTER(NFAo) I=T U{TYPEOF(oi)} DFAO;=DFA-CONVERTER(NFAo) 8 Yo:]TYPEOF(O:) if EOUIV-CHECKER(DFAoi.DFAo;)then 9foreach(oi,∫，o)∈Edo 0 LW.UNION(0:,0;) 10 ifo:∈Q then 11 L Add oj to 5[oi,f] 14 Let MOM be a new map 12 return NFA=(Q,∑，d,go,T,y） 15 foreach o∈Hdo 16 L MOM[o]W.FIND(o) 17 return MOM NFA-BUILDER constructs all the six components for Ao. Its initial state go is simply o(line 1).Q is the set of objects reachable from o in FPG(line 2).The objects in Q are Algorithm I gives the main algorithm.To facilitate merg- iterated over to build >(set of input symbols).I (set of ing type-consistent objects,we make use of the concept of output symbols),and y (output map)at lines 5-8.The disjoint sets [11.In a set S of disjoint sets,each disjoint set function FIELDSOF:H->P(F)returns the fields of a is identified by a representative,which is some member of given object.Finally,the relevant edges in FPG are traversed the disjoint set.We make use of two classic operations over to build the state transition map 6(lines 9-11). disjoint sets,UNION and FIND.S.UNION(,y)unites the disjoint sets in S that contain x and y,say S and Sy,into 4.3 The DFA Converter a new disjoint set that is the union of the two,adds it to S, Algorithm 3 (DFA-CONVERTER)converts an NFA to its and destroys S and Su in S.The representative of the re equivalent DFA by using the subset construction [2] 2844. Algorithms We present the algorithms used in MAHJONG. In Sec￾tion 4.1, we give some domains used and then the main algorithm. In Sections 4.2 – 4.5, we describe the algorithms of its four components introduced in Sections 3.2 – 3.5. 4.1 MAHJONG For a program, we use the three domains: (1) H is the set of all abstract heap objects (i.e., allocation sites), (2) F is the set of all field names, and (3) T is the set of all types. Note that we have used H earlier in Definition 2.2. Now, we can formally define the input and output of MAHJONG. MAHJONG takes a field points-to graph, FPG = (N, E), which is a directed weighted graph, as input. A node oi ∈ N = H represents a heap object in the program. An edge (oi , f, oj ) ∈ E ⊆ N × F × N indicates that oi .f points to oj . We assume that the FPG contains a dummy node onull to represent null. If oi .f = null, then (oi , f, onull) ∈ E. We also assume (onull, f, onull) ∈ E for every field f ∈ F. The output of MAHJONG is a new heap abstraction, rep￾resented by a merged object map, MOM ⊆ H → H, which relates an object in an equivalence class in H / ≡ to its rep￾resentative object (as described in Section 3.5). Algorithm 1: MAHJONG Input : FPG (Field Points-to Graph) Output: MOM (Merged Object Map) 1 Let W be a new set 2 foreach o ∈ H do 3 Add {o} to W 4 foreach oi, oj ∈ H s.t. W.FIND(oi) 6= W.FIND(oj ) do 5 if TYPEOF(oi) == TYPEOF(oj ) and 6 SINGLETYPE-CHECK(oi, FPG) and 7 SINGLETYPE-CHECK(oj , FPG) then 8 NFAoi = NFA-BUILDER(oi, FPG) 9 NFAoj = NFA-BUILDER(oj , FPG) 10 DFAoi = DFA-CONVERTER(NFAoi) 11 DFAoj = DFA-CONVERTER(NFAoj ) 12 if EQUIV-CHECKER(DFAoi, DFAoj ) then 13 W.UNION(oi, oj ) 14 Let MOM be a new map 15 foreach o ∈ H do 16 MOM[o] = W.FIND(o) 17 return MOM Algorithm 1 gives the main algorithm. To facilitate merg￾ing type-consistent objects, we make use of the concept of disjoint sets [11]. In a set S of disjoint sets, each disjoint set is identified by a representative, which is some member of the disjoint set. We make use of two classic operations over disjoint sets, UNION and FIND. S.UNION(x, y) unites the disjoint sets in S that contain x and y, say Sx and Sy, into a new disjoint set that is the union of the two, adds it to S, and destroys Sx and Sy in S. The representative of the re￾sulting set is any member of Sx ∪ Sy. S.FIND(x) returns the representative of the disjoint set in S that contains x. MAHJONG first initializes W by adding to it a singleton set for each object (lines 1 – 3). Then it iterates over every pair of objects, oi and oj in H, that are not yet merged, and merges the pair if both are type-consistent (lines 4 – 13). According to line 5, oi and oj are mergeable only if both have the same type. The function TYPEOF : H → T returns the type of a given object and a special type for onull. To check the type consistency of oi and oj by Defini￾tion 2.1 efficiently, we handle its two conditions separately, with Condition 2 in lines 6 – 7 and Condition 1 in lines 8 – 12. In lines 6 – 7, the function SINGLETYPE-CHECK : H×FPG → {TRUE, FALSE} is applied to see if Condition 2 holds for both oi and oj . If so, MAHJONG then proceeds to build the NFAs for the two objects (Section 4.2), convert the NFAs to their equivalent DFAs (Section 4.3), and finally, test their equivalence (Section 4.4). If the two DFAs are equiv￾alent, then MAHJONG calls W.UNION(oi , oj ) to merge oi and oj at line 13. Finally, in lines 14 – 16, MAHJONG builds a new heap abstraction as desired (Section 4.5). 4.2 The NFA Builder Given an object o, Algorithm 2 (NFA-BUILDER) builds an NFA, Ao =(Q, Σ, δ, q0, Γ, γ), according to the mapping from the field points-to graph rooted at o to Ao in Figure 4. Algorithm 2: NFA-BUILDER Input : o (Input object) FPG = (N, E) (Field Points-to Graph) Output: NFA = (Q, Σ, δ, q0, Γ, γ) 1 q0 = o 2 Let Q be a set of objects reachable from o in FPG 3 Let Σ and Γ be two new sets 4 Let γ and δ be two new maps 5 foreach oi ∈ Q do 6 Σ = Σ ∪ FIELDSOF(oi) 7 Γ = Γ ∪ { TYPEOF(oi) } 8 γ[oi] = TYPEOF(oi) 9 foreach (oi, f, oj ) ∈ E do 10 if oi ∈ Q then 11 Add oj to δ[oi, f] 12 return NFA = (Q, Σ, δ, q0, Γ, γ) NFA-BUILDER constructs all the six components for Ao. Its initial state q0 is simply o (line 1). Q is the set of objects reachable from o in FPG (line 2). The objects in Q are iterated over to build Σ (set of input symbols), Γ (set of output symbols), and γ (output map) at lines 5 – 8. The function FIELDSOF : H → P(F) returns the fields of a given object. Finally, the relevant edges in FPG are traversed to build the state transition map δ (lines 9 – 11). 4.3 The DFA Converter Algorithm 3 (DFA-CONVERTER) converts an NFA to its equivalent DFA by using the subset construction [2]. 284