1 cananian 1.1.2.1 // FieldSyncOracle.java, created Sun Jan 14 00:56:29 2001 by cananian
2 cananian 1.1.2.2 // 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.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.CallGraph;
7 cananian 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
8 cananian 1.1.2.1 import harpoon.Analysis.CallGraph;
9 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
10 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
11 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
12 cananian 1.1.2.1 import harpoon.ClassFile.HField;
13 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
14 cananian 1.1.2.1 import harpoon.IR.Quads.GET;
15 cananian 1.1.2.1 import harpoon.IR.Quads.MONITORENTER;
16 cananian 1.1.2.1 import harpoon.IR.Quads.MONITOREXIT;
17 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
18 cananian 1.1.2.1 import harpoon.IR.Quads.SET;
19 cananian 1.3 import net.cscott.jutil.WorkSet;
20 cananian 1.3 import net.cscott.jutil.AggregateSetFactory;
21 cananian 1.3 import net.cscott.jutil.BitSetFactory;
22 cananian 1.3 import net.cscott.jutil.GenericInvertibleMultiMap;
23 cananian 1.3 import net.cscott.jutil.GenericMultiMap;
24 cananian 1.3 import net.cscott.jutil.InvertibleMultiMap;
25 cananian 1.3 import net.cscott.jutil.MultiMap;
26 cananian 1.3 import net.cscott.jutil.SetFactory;
27 cananian 1.1.2.1
28 cananian 1.1.2.1 import java.util.Arrays;
29 cananian 1.1.2.1 import java.util.Collection;
30 cananian 1.1.2.5 import java.util.Collections;
31 cananian 1.1.2.1 import java.util.HashSet;
32 cananian 1.1.2.1 import java.util.Iterator;
33 cananian 1.1.2.1 import java.util.Set;
34 cananian 1.1.2.1 /**
35 cananian 1.1.2.1 * A <code>FieldSyncOracle</code> tells which fields a given method could
36 cananian 1.1.2.1 * possibly access (either directly, or via a method call), and whether
37 cananian 1.1.2.1 * the given method will ever acquire/release a lock (either directly, or
38 cananian 1.1.2.1 * via a method call). This analysis is useful for determining which
39 cananian 1.1.2.4 * memory optimizations are safe across a given method call (and
40 cananian 1.1.2.4 * other things).
41 cananian 1.1.2.1 *
42 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
43 cananian 1.4 * @version $Id: FieldSyncOracle.java,v 1.4 2004/02/08 03:20:10 cananian Exp $
44 cananian 1.1.2.1 */
45 cananian 1.1.2.4 public class FieldSyncOracle {
46 cananian 1.1.2.1 final MultiMap fieldsRead, fieldsWritten;
47 cananian 1.1.2.1 final Set syncMethods = new HashSet();
48 cananian 1.1.2.1 /** Returns <code>true</code> if <code>HMethod</code>
49 cananian 1.1.2.1 <code>hm</code> will ever acquire/release a lock (either
50 cananian 1.1.2.1 directly, or via a method call). */
51 cananian 1.1.2.1 public boolean isSync(HMethod hm) {
52 cananian 1.1.2.1 return syncMethods.contains(hm);
53 cananian 1.1.2.1 }
54 cananian 1.1.2.1 /** Returns <code>true</code> if <code>HMethod</code>
55 cananian 1.1.2.1 <code>hm</code> will ever read <code>HField</code>
56 cananian 1.1.2.1 <code>hf</code>, either directly or via a method call. */
57 cananian 1.1.2.1 public boolean isRead(HMethod hm, HField hf) {
58 cananian 1.1.2.1 return fieldsRead.contains(hm, hf);
59 cananian 1.1.2.1 }
60 cananian 1.1.2.5 /** Returns a <code>Set</code> of <code>HField</code>s read,
61 cananian 1.1.2.5 * either directly or indirectly, by <code>HMethod</code> hm. */
62 cananian 1.1.2.5 public Set fieldsRead(HMethod hm) {
63 cananian 1.1.2.5 return Collections.unmodifiableSet((Set) fieldsRead.getValues(hm));
64 cananian 1.1.2.5 }
65 cananian 1.1.2.1 /** Returns <code>true</code> if <code>HMethod</code>
66 cananian 1.1.2.5 <code>hm</code> will ever write <code>HField</code>
67 cananian 1.1.2.1 <code>hf</code>, either directly or via a method call. */
68 cananian 1.1.2.1 public boolean isWritten(HMethod hm, HField hf) {
69 cananian 1.1.2.1 return fieldsWritten.contains(hm, hf);
70 cananian 1.1.2.5 }
71 cananian 1.1.2.5 /** Returns a <code>Set</code> of <code>HField</code>s written,
72 cananian 1.1.2.5 * either directly or indirectly, by <code>HMethod</code> hm. */
73 cananian 1.1.2.5 public Set fieldsWritten(HMethod hm) {
74 cananian 1.1.2.5 return Collections.unmodifiableSet((Set) fieldsWritten.getValues(hm));
75 cananian 1.1.2.1 }
76 cananian 1.1.2.1 /** Creates a <code>FieldSyncOracle</code>. */
77 cananian 1.1.2.1 public FieldSyncOracle(HCodeFactory hcf, ClassHierarchy ch, CallGraph cg) {
78 cananian 1.1.2.1 Set s = new HashSet();
79 cananian 1.1.2.1 /* compute field universe */
80 cananian 1.4 for (Object hcO : ch.classes()) {
81 cananian 1.4 HClass hc = (HClass) hcO;
82 cananian 1.1.2.1 s.addAll(Arrays.asList(hc.getDeclaredFields()));
83 cananian 1.1.2.1 }
84 cananian 1.1.2.1 /* initialize maps. */
85 cananian 1.1.2.1 SetFactory sf =new BitSetFactory(s);
86 cananian 1.1.2.1 this.fieldsRead = new GenericMultiMap(sf);
87 cananian 1.1.2.1 this.fieldsWritten = new GenericMultiMap(sf);
88 cananian 1.1.2.1
89 cananian 1.1.2.1 /* analyze all callable methods */
90 cananian 1.1.2.1 for (Iterator it=ch.callableMethods().iterator(); it.hasNext(); )
91 cananian 1.1.2.1 analyze((HMethod)it.next(), hcf);
92 cananian 1.1.2.1 /* compute transitive closure */
93 cananian 1.1.2.1 transClose(ch, callGraphMap(ch, cg));
94 cananian 1.1.2.1 /* done! */
95 cananian 1.1.2.3 int sum=0, n=0;
96 cananian 1.1.2.3 for (Iterator it=fieldsRead.keySet().iterator(); it.hasNext(); n++)
97 cananian 1.1.2.3 sum+=fieldsRead.getValues(it.next()).size();
98 cananian 1.1.2.3 System.out.println("FIELDS read: (avg) "+((float)sum/n)+
99 cananian 1.1.2.3 " of "+s.size());
100 cananian 1.1.2.3 sum=0; n=0;
101 cananian 1.1.2.3 for (Iterator it=fieldsWritten.keySet().iterator(); it.hasNext(); n++)
102 cananian 1.1.2.3 sum+=fieldsWritten.getValues(it.next()).size();
103 cananian 1.1.2.3 System.out.println("FIELDS written: (avg) "+((float)sum/n)+
104 cananian 1.1.2.3 " of "+s.size());
105 cananian 1.1.2.3 System.out.println("SYNC methods: "+syncMethods.size()+
106 cananian 1.1.2.3 " of "+ch.callableMethods().size());
107 cananian 1.1.2.1 }
108 cananian 1.1.2.1
109 cananian 1.1.2.1 //----------------------------------------------------------------
110 cananian 1.1.2.1 // method analysis
111 cananian 1.1.2.1 void analyze(HMethod hm, HCodeFactory hcf) {
112 cananian 1.1.2.1 HCode hc = hcf.convert(hm);
113 cananian 1.1.2.1 if (hc==null) return; // abstract.
114 cananian 1.1.2.1 for (Iterator it=hc.getElementsI(); it.hasNext(); ) {
115 cananian 1.1.2.1 Quad q = (Quad) it.next();
116 cananian 1.1.2.1 /* analyze q */
117 cananian 1.1.2.1 if (q instanceof MONITORENTER || q instanceof MONITOREXIT)
118 cananian 1.1.2.1 syncMethods.add(hm);
119 cananian 1.1.2.1 if (q instanceof GET)
120 cananian 1.1.2.1 fieldsRead.add(hm, ((GET)q).field());
121 cananian 1.1.2.1 if (q instanceof SET)
122 cananian 1.1.2.1 fieldsWritten.add(hm, ((SET)q).field());
123 cananian 1.1.2.1 }
124 cananian 1.1.2.1 }
125 cananian 1.1.2.1 // make invertible multimap out of the callgraph
126 cananian 1.1.2.1 InvertibleMultiMap callGraphMap(ClassHierarchy ch, CallGraph cg) {
127 cananian 1.1.2.1 InvertibleMultiMap imm =
128 cananian 1.1.2.1 new GenericInvertibleMultiMap(new AggregateSetFactory());
129 cananian 1.4 for (Object hmO : ch.callableMethods()) {
130 cananian 1.4 HMethod hm = (HMethod) hmO;
131 cananian 1.1.2.1 imm.addAll(hm, Arrays.asList(cg.calls(hm)));
132 cananian 1.1.2.1 }
133 cananian 1.1.2.1 return imm;
134 cananian 1.1.2.1 }
135 cananian 1.1.2.1
136 cananian 1.1.2.1 //----------------------------------------------------------------
137 cananian 1.1.2.1 // compute transitive closure.
138 cananian 1.1.2.1 void transClose(ClassHierarchy ch, InvertibleMultiMap calls) {
139 cananian 1.1.2.1 // create an invertable multimap from the call graph.
140 cananian 1.1.2.1 WorkSet w = new WorkSet(ch.callableMethods());
141 cananian 1.1.2.1 while (!w.isEmpty()) {
142 cananian 1.1.2.1 HMethod hm = (HMethod) w.pop();
143 cananian 1.1.2.1 boolean changed = false;
144 cananian 1.4 for (Object calleeO : calls.getValues(hm)) {
145 cananian 1.4 HMethod callee = (HMethod) calleeO;
146 cananian 1.1.2.1 // add all fields read/written by callee to this.
147 cananian 1.1.2.1 if (fieldsRead.addAll(hm, fieldsRead.getValues(callee)))
148 cananian 1.1.2.1 changed = true;
149 cananian 1.1.2.1 if (fieldsWritten.addAll(hm, fieldsWritten.getValues(callee)))
150 cananian 1.1.2.1 changed = true;
151 cananian 1.1.2.1 // close on syncMethods.
152 cananian 1.1.2.1 if (syncMethods.contains(callee))
153 cananian 1.1.2.1 if (syncMethods.add(hm))
154 cananian 1.1.2.1 changed = true;
155 cananian 1.1.2.1 }
156 cananian 1.1.2.1 // if hm's data was modified, add all callers to the worklist.
157 cananian 1.1.2.1 if (changed)
158 cananian 1.1.2.1 w.addAll(calls.invert().getValues(hm));
159 cananian 1.1.2.1 }
160 cananian 1.1.2.1 // done.
161 cananian 1.1.2.1 }
162 cananian 1.2 }