1 cananian 1.1.2.1 // GlobalFieldOracle.java, created Sun Jan 14 00:56:29 2001 by cananian
2 cananian 1.1.2.4 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Transactions;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.1 import harpoon.Analysis.DomTree;
8 cananian 1.1.2.1 import harpoon.Analysis.ReachingDefs;
9 cananian 1.1.2.1 import harpoon.Analysis.SSxReachingDefsImpl;
10 cananian 1.1.2.1 import harpoon.Analysis.Maps.ExactTypeMap;
11 cananian 1.1.2.1 import harpoon.Analysis.Quads.CallGraphImpl2;
12 cananian 1.1.2.1 import harpoon.Analysis.Quads.TypeInfo;
13 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
14 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
15 cananian 1.1.2.1 import harpoon.ClassFile.HField;
16 cananian 1.1.2.2 import harpoon.ClassFile.HInitializer;
17 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
18 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
19 cananian 1.1.2.1 import harpoon.IR.Quads.GET;
20 cananian 1.1.2.1 import harpoon.IR.Quads.MONITORENTER;
21 cananian 1.1.2.1 import harpoon.IR.Quads.MONITOREXIT;
22 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
23 cananian 1.1.2.1 import harpoon.IR.Quads.SET;
24 cananian 1.1.2.1 import harpoon.Util.ArrayIterator;
25 cananian 1.3 import net.cscott.jutil.WorkSet;
26 cananian 1.3 import net.cscott.jutil.AggregateSetFactory;
27 cananian 1.3 import net.cscott.jutil.GenericMultiMap;
28 cananian 1.3 import net.cscott.jutil.MultiMap;
29 cananian 1.3 import net.cscott.jutil.SetFactory;
30 cananian 1.1.2.1
31 cananian 1.1.2.1 import java.util.Arrays;
32 cananian 1.1.2.1 import java.util.HashSet;
33 cananian 1.1.2.1 import java.util.Iterator;
34 cananian 1.1.2.1 import java.util.Set;
35 cananian 1.1.2.1 /**
36 cananian 1.1.2.1 * A <code>GlobalFieldOracle</code> does a global analysis to determine
37 cananian 1.1.2.1 * which fields can possibly be accessed in unsynchronized and
38 cananian 1.1.2.1 * synchronized contexts.
39 cananian 1.1.2.1 *
40 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
41 cananian 1.4 * @version $Id: GlobalFieldOracle.java,v 1.4 2004/02/08 03:20:25 cananian Exp $
42 cananian 1.1.2.1 */
43 cananian 1.1.2.1 class GlobalFieldOracle extends FieldOracle {
44 cananian 1.1.2.1 Set syncRead = new HashSet(); Set syncWrite = new HashSet();
45 cananian 1.1.2.1 Set unsyncRead = new HashSet(); Set unsyncWrite = new HashSet();
46 cananian 1.1.2.1 public boolean isSyncRead(HField hf) { return syncRead.contains(hf); }
47 cananian 1.1.2.1 public boolean isSyncWrite(HField hf) { return syncWrite.contains(hf); }
48 cananian 1.1.2.1 public boolean isUnsyncRead(HField hf) { return unsyncRead.contains(hf); }
49 cananian 1.1.2.1 public boolean isUnsyncWrite(HField hf) { return unsyncWrite.contains(hf);}
50 cananian 1.1.2.1
51 cananian 1.1.2.1 /** Creates a <code>GlobalFieldOracle</code>. */
52 cananian 1.1.2.1 public GlobalFieldOracle(ClassHierarchy ch, HMethod mainM, Set roots,
53 cananian 1.1.2.1 HCodeFactory hcf) {
54 cananian 1.1.2.3 /* Add callable static initializers to the root set */
55 cananian 1.1.2.3 Set myroots = new HashSet(roots);
56 cananian 1.4 for (Object hmO : ch.callableMethods()) {
57 cananian 1.4 HMethod hm = (HMethod) hmO;
58 cananian 1.1.2.3 if (hm instanceof HInitializer)
59 cananian 1.1.2.3 myroots.add(hm);
60 cananian 1.1.2.3 }
61 cananian 1.1.2.1 /* for every method, compile lists of methods and fields which
62 cananian 1.1.2.1 * are accessed in synchronized and unsynchronized contexts. */
63 cananian 1.1.2.1 MethodInfo mi = analyzeMethods(ch, hcf);
64 cananian 1.1.2.1 /* now determine which methods can possibly ever be called in
65 cananian 1.1.2.1 * syncronized and unsynchronized contexts. */
66 cananian 1.1.2.3 CallContextInfo cci = new CallContextInfo(mi, mainM, myroots);
67 cananian 1.1.2.1 /* and finally, determine "possibly ever accessed" info for
68 cananian 1.1.2.1 * fields from the above. */
69 cananian 1.1.2.1 transCloseFields(mi, cci);
70 cananian 1.1.2.3 {
71 cananian 1.1.2.3 Set sync = new HashSet(syncRead); sync.addAll(syncWrite);
72 cananian 1.1.2.3 Set unsync = new HashSet(unsyncRead); unsync.addAll(unsyncWrite);
73 cananian 1.1.2.3 Set common = new HashSet(sync); common.retainAll(unsync);
74 cananian 1.1.2.3 sync.removeAll(common); unsync.removeAll(common);
75 cananian 1.1.2.3 System.out.println("GLOBAL FIELD ORACLE: "+
76 cananian 1.1.2.3 sync.size()+" fields exclusively sync, "+
77 cananian 1.1.2.3 unsync.size()+" fields exclusively unsync");
78 cananian 1.1.2.3 }
79 cananian 1.1.2.1 }
80 cananian 1.1.2.1
81 cananian 1.1.2.1 //----------------------------------------------------------------
82 cananian 1.1.2.1 // method analysis
83 cananian 1.1.2.1 MethodInfo analyzeMethods(ClassHierarchy ch, HCodeFactory hcf) {
84 cananian 1.1.2.1 MethodInfo result = new MethodInfo();
85 cananian 1.1.2.1 CallGraphImpl2 cg = new CallGraphImpl2(ch, hcf);
86 cananian 1.4 for (Object hmO : ch.callableMethods()) {
87 cananian 1.4 HMethod hm = (HMethod) hmO;
88 cananian 1.1.2.1 HCode hc = hcf.convert(hm);
89 cananian 1.1.2.1 if (hc==null) continue;
90 cananian 1.1.2.1 analyzeOneMethod(result, hm, hc, cg);
91 cananian 1.1.2.1 }
92 cananian 1.1.2.1 return result;
93 cananian 1.1.2.1 }
94 cananian 1.1.2.1 private void analyzeOneMethod(MethodInfo mi, HMethod hm, HCode hc,
95 cananian 1.1.2.1 CallGraphImpl2 cg) {
96 cananian 1.1.2.1 /* MONITORENTER must dominate all associated MONITOREXITs and
97 cananian 1.1.2.1 * monitors must be properly nested. */
98 cananian 1.1.2.1 DomTree dt = new DomTree(hc, false);
99 cananian 1.1.2.1 ExactTypeMap etm = new TypeInfo((harpoon.IR.Quads.QuadSSI)hc);
100 cananian 1.1.2.1 ReachingDefs rd = new SSxReachingDefsImpl(hc);
101 cananian 1.1.2.1 analyzeOneQuad(mi, hm, (Quad)hc.getRootElement(), dt, etm, rd, cg, 0);
102 cananian 1.1.2.1 }
103 cananian 1.1.2.1 private void analyzeOneQuad(MethodInfo mi, HMethod hm, Quad q, DomTree dt,
104 cananian 1.1.2.1 ExactTypeMap etm, ReachingDefs rd,
105 cananian 1.1.2.1 CallGraphImpl2 cg, int synccount) {
106 cananian 1.1.2.1 /* analyze q */
107 cananian 1.1.2.1 if (q instanceof MONITORENTER) synccount++;
108 cananian 1.1.2.1 if (q instanceof MONITOREXIT) synccount--;
109 cananian 1.1.2.1 if (q instanceof GET) {
110 cananian 1.1.2.1 MultiMap mm = (synccount>0) ? mi.readSync : mi.readUnsync;
111 cananian 1.1.2.1 mm.add(hm, ((GET)q).field());
112 cananian 1.1.2.1 }
113 cananian 1.1.2.1 if (q instanceof SET) {
114 cananian 1.1.2.1 MultiMap mm = (synccount>0) ? mi.writeSync : mi.writeUnsync;
115 cananian 1.1.2.1 mm.add(hm, ((SET)q).field());
116 cananian 1.1.2.1 }
117 cananian 1.1.2.1 if (q instanceof CALL) {
118 cananian 1.1.2.1 MultiMap mm = (synccount>0) ? mi.calledSync : mi.calledUnsync;
119 cananian 1.1.2.1 mm.addAll(hm, Arrays.asList(cg.calls((CALL)q, rd, etm)));
120 cananian 1.1.2.1 }
121 cananian 1.1.2.1
122 cananian 1.1.2.1 /* recurse down the dominator tree */
123 cananian 1.1.2.1 for (Iterator it=new ArrayIterator(dt.children(q)); it.hasNext(); )
124 cananian 1.1.2.1 analyzeOneQuad(mi,hm, (Quad)it.next(), dt,etm,rd,cg, synccount);
125 cananian 1.1.2.1 }
126 cananian 1.1.2.1 private class MethodInfo {
127 cananian 1.1.2.1 /** fields read/written in synchronized/unsynchronized contexts. */
128 cananian 1.1.2.1 final MultiMap readSync, readUnsync, writeSync, writeUnsync;
129 cananian 1.1.2.1 /** methods called in synchronized/unsynchronized contexts. */
130 cananian 1.1.2.1 final MultiMap calledSync, calledUnsync;
131 cananian 1.1.2.1 MethodInfo() {
132 cananian 1.1.2.1 SetFactory sf = new AggregateSetFactory();
133 cananian 1.1.2.1 readSync = new GenericMultiMap(sf);
134 cananian 1.1.2.1 readUnsync = new GenericMultiMap(sf);
135 cananian 1.1.2.1 writeSync = new GenericMultiMap(sf);
136 cananian 1.1.2.1 writeUnsync = new GenericMultiMap(sf);
137 cananian 1.1.2.1 calledSync = new GenericMultiMap(sf);
138 cananian 1.1.2.1 calledUnsync = new GenericMultiMap(sf);
139 cananian 1.1.2.1 }
140 cananian 1.1.2.1 }
141 cananian 1.1.2.1 //----------------------------------------------------------------
142 cananian 1.1.2.1 // compute transitive closure on methods called.
143 cananian 1.1.2.1 private class CallContextInfo {
144 cananian 1.1.2.1 final Set calledSync = new HashSet();
145 cananian 1.1.2.1 final Set calledUnsync = new HashSet();
146 cananian 1.1.2.1 /* compute call context info */
147 cananian 1.1.2.1 CallContextInfo(MethodInfo mi, HMethod mainM, Set roots) {
148 cananian 1.1.2.1 WorkSet W = new WorkSet();
149 cananian 1.1.2.1 // ever called unsync?
150 cananian 1.1.2.1 // if in calledUnsync list of a method ever called unsync.
151 cananian 1.1.2.1 W.addAll(roots); // all roots called unsync.
152 cananian 1.1.2.1 while (!W.isEmpty()) {
153 cananian 1.1.2.1 HMethod hm = (HMethod) W.pop();
154 cananian 1.1.2.1 if (calledUnsync.contains(hm)) continue;
155 cananian 1.1.2.1 calledUnsync.add(hm);
156 cananian 1.1.2.1 W.addAll(mi.calledUnsync.getValues(hm));
157 cananian 1.1.2.1 }
158 cananian 1.1.2.1 // ever called sync?
159 cananian 1.1.2.1 // if in any calledSync list
160 cananian 1.1.2.1 // or in calledUnsync list of a method ever called sync.
161 cananian 1.1.2.1 W.addAll(roots); // all roots called sync
162 cananian 1.1.2.1 W.remove(mainM); // except main method.
163 cananian 1.1.2.2 for (Iterator it=W.iterator(); it.hasNext(); )
164 cananian 1.1.2.2 if (((HMethod)it.next()) instanceof HInitializer)
165 cananian 1.1.2.2 it.remove(); // and except static initializers.
166 cananian 1.4 for (Object hmO : mi.calledSync.keySet()){
167 cananian 1.4 HMethod hm = (HMethod) hmO;
168 cananian 1.1.2.1 W.addAll(mi.calledSync.getValues(hm));
169 cananian 1.1.2.1 } // add all calledSync to worklist.
170 cananian 1.1.2.1 while (!W.isEmpty()) {
171 cananian 1.1.2.1 HMethod hm = (HMethod) W.pop(); // a method called sync.
172 cananian 1.1.2.1 if (calledSync.contains(hm)) continue;//done already.
173 cananian 1.1.2.1 calledSync.add(hm);
174 cananian 1.1.2.1 // all unsync calls of a method called sync are called sync.
175 cananian 1.1.2.1 W.addAll(mi.calledUnsync.getValues(hm));
176 cananian 1.1.2.1 }
177 cananian 1.1.2.1 // done.
178 cananian 1.1.2.1 }
179 cananian 1.1.2.1 }
180 cananian 1.1.2.1 //----------------------------------------------------------------
181 cananian 1.1.2.1 // compute transitive closure on fields accessed.
182 cananian 1.1.2.1 void transCloseFields(MethodInfo mi, CallContextInfo cci) {
183 cananian 1.1.2.1 // ever accessed unsync?
184 cananian 1.1.2.1 // in fields accessedUnsync list of method called unsync.
185 cananian 1.4 for (Object hmO : cci.calledUnsync) {
186 cananian 1.4 HMethod hm = (HMethod) hmO;
187 cananian 1.1.2.1 unsyncRead.addAll(mi.readUnsync.getValues(hm));
188 cananian 1.1.2.1 unsyncWrite.addAll(mi.writeUnsync.getValues(hm));
189 cananian 1.1.2.1 }
190 cananian 1.1.2.1 // ever accessed sync?
191 cananian 1.1.2.1 // in any accessedSync list
192 cananian 1.1.2.1 // or in accessedUnsync list of a method called sync.
193 cananian 1.4 for (Object hmO : cci.calledUnsync) {
194 cananian 1.4 HMethod hm = (HMethod) hmO;
195 cananian 1.1.2.1 syncRead.addAll(mi.readSync.getValues(hm));
196 cananian 1.1.2.1 syncWrite.addAll(mi.writeSync.getValues(hm));
197 cananian 1.1.2.1 }
198 cananian 1.4 for (Object hmO : cci.calledSync) {
199 cananian 1.4 HMethod hm = (HMethod) hmO;
200 cananian 1.1.2.1 syncRead.addAll(mi.readSync.getValues(hm));
201 cananian 1.1.2.1 syncRead.addAll(mi.readUnsync.getValues(hm));
202 cananian 1.1.2.1 syncWrite.addAll(mi.writeSync.getValues(hm));
203 cananian 1.1.2.1 syncWrite.addAll(mi.writeUnsync.getValues(hm));
204 cananian 1.1.2.1 }
205 cananian 1.1.2.1 // done!
206 cananian 1.1.2.1 }
207 cananian 1.1.2.1 //----------------------------------------------------------------
208 cananian 1.2 }