1
2
3
4 package joeq.Compiler.Dataflow;
5
6 import java.util.Arrays;
7 import java.util.Collections;
8 import java.util.HashMap;
9 import java.util.HashSet;
10 import java.util.Iterator;
11 import java.util.Map;
12 import java.util.Set;
13 import joeq.Class.jq_Class;
14 import joeq.Class.jq_Method;
15 import joeq.Class.jq_Type;
16 import joeq.Compiler.Quad.BasicBlock;
17 import joeq.Compiler.Quad.CodeCache;
18 import joeq.Compiler.Quad.ControlFlowGraph;
19 import joeq.Compiler.Quad.ControlFlowGraphVisitor;
20 import joeq.Compiler.Quad.Quad;
21 import joeq.Compiler.Quad.RegisterFactory.Register;
22 import joeq.Main.HostedVM;
23 import joeq.Util.Templates.List;
24 import joeq.Util.Templates.ListIterator;
25 import jwutil.collections.BitStringSet;
26 import jwutil.collections.Pair;
27 import jwutil.graphs.EdgeGraph;
28 import jwutil.graphs.Graph;
29 import jwutil.math.BitString;
30
31 /***
32 * ReachingDefs
33 *
34 * @author John Whaley
35 * @version $Id: ReachingDefs.java 1931 2004-09-22 22:17:47Z joewhaley $
36 */
37 public class ReachingDefs extends Problem {
38
39 public static class RDVisitor implements ControlFlowGraphVisitor {
40
41 public static boolean DUMP = false;
42 public static int SOLVER = 1;
43
44 long totalTime;
45
46
47
48
49 public void visitCFG(ControlFlowGraph cfg) {
50 long time = System.currentTimeMillis();
51 Problem p = new ReachingDefs();
52 Solver s1;
53 switch (SOLVER) {
54 case 1:
55 s1 = new IterativeSolver();
56 break;
57 case 3:
58 s1 = new PriorityQueueSolver();
59 break;
60 case 2:
61 default:
62 s1 = new SortedSetSolver(BBComparator.INSTANCE);
63 break;
64 }
65 solve(cfg, s1, p);
66 time = System.currentTimeMillis() - time;
67 totalTime += time;
68 if (DUMP)
69 Solver.dumpResults(cfg, s1);
70 }
71
72 public String toString() {
73 return "Total time: "+totalTime+" ms";
74 }
75 }
76
77 Quad[] quads;
78 Map regToDefs;
79 Map transferFunctions;
80 BitVectorFact emptySet;
81 GenKillTransferFunction emptyTF;
82 Solver mySolver;
83
84 static final boolean TRACE = false;
85
86 public void initialize(Graph g) {
87 ControlFlowGraph cfg = (ControlFlowGraph) ((EdgeGraph) g).getGraph();
88
89 if (TRACE) System.out.println(cfg.fullDump());
90
91
92 int bitVectorSize = cfg.getMaxQuadID()+1;
93
94 if (TRACE) System.out.println("Bit vector size: "+bitVectorSize);
95
96 regToDefs = new HashMap();
97 transferFunctions = new HashMap();
98 quads = new Quad[bitVectorSize];
99 emptySet = new UnionBitVectorFact(bitVectorSize);
100 emptyTF = new GenKillTransferFunction(bitVectorSize);
101
102 List.BasicBlock list = cfg.reversePostOrder(cfg.entry());
103 for (ListIterator.BasicBlock i = list.basicBlockIterator(); i.hasNext(); ) {
104 BasicBlock bb = i.nextBasicBlock();
105 BitString gen = new BitString(bitVectorSize);
106 for (ListIterator.Quad j = bb.iterator(); j.hasNext(); ) {
107 Quad q = j.nextQuad();
108 if (!bb.getExceptionHandlers().isEmpty()) {
109 handleEdges(bb, bb.getExceptionHandlerEntries(), gen, null);
110 }
111 if (q.getDefinedRegisters().isEmpty()) continue;
112 int a = q.getID();
113 quads[a] = q;
114 for (ListIterator.RegisterOperand k = q.getDefinedRegisters().registerOperandIterator(); k.hasNext(); ) {
115 Register r = k.nextRegisterOperand().getRegister();
116 BitString kill = (BitString) regToDefs.get(r);
117 if (kill == null) regToDefs.put(r, kill = new BitString(bitVectorSize));
118 else gen.minus(kill);
119 kill.set(a);
120 }
121 gen.set(a);
122 }
123 GenKillTransferFunction tf = new GenKillTransferFunction(gen, new BitString(bitVectorSize));
124 handleEdges(bb, bb.getSuccessors(), gen, tf);
125 }
126 for (Iterator i = transferFunctions.values().iterator(); i.hasNext(); ) {
127 GenKillTransferFunction f = (GenKillTransferFunction) i.next();
128 for (BitString.BitStringIterator j = f.gen.iterator(); j.hasNext(); ) {
129 int a = j.nextIndex();
130 Quad q = quads[a];
131 for (ListIterator.RegisterOperand k = q.getDefinedRegisters().registerOperandIterator(); k.hasNext(); ) {
132 Register r = k.nextRegisterOperand().getRegister();
133 f.kill.or((BitString) regToDefs.get(r));
134 }
135 }
136 }
137 if (TRACE) {
138 for (Iterator i = transferFunctions.entrySet().iterator(); i.hasNext(); ) {
139 Map.Entry e = (Map.Entry) i.next();
140 System.out.println(e.getKey());
141 System.out.println(e.getValue());
142 }
143 }
144 }
145
146 private void handleEdges(BasicBlock bb, List.BasicBlock bbs, BitString gen, GenKillTransferFunction defaultTF) {
147 for (ListIterator.BasicBlock k = bbs.basicBlockIterator(); k.hasNext(); ) {
148 BasicBlock bb2 = k.nextBasicBlock();
149 Object edge = new Pair(bb, bb2);
150 GenKillTransferFunction tf = (GenKillTransferFunction) transferFunctions.get(edge);
151 if (tf == null) {
152 tf = (defaultTF != null)? defaultTF : new GenKillTransferFunction(gen.size());
153 transferFunctions.put(edge, tf);
154 }
155 tf.gen.or(gen);
156 }
157 }
158
159
160
161
162 public boolean direction() {
163 return true;
164 }
165
166
167
168
169 public Fact boundary() {
170 return emptySet;
171 }
172
173
174
175
176 public Fact interior() {
177 return emptySet;
178 }
179
180
181
182
183 public TransferFunction getTransferFunction(Object e) {
184 TransferFunction tf = (TransferFunction) transferFunctions.get(e);
185 if (tf == null) tf = emptyTF;
186 return tf;
187 }
188
189 public static void main(String[] args) {
190 HostedVM.initialize();
191 HashSet set = new HashSet();
192 for (int i=0; i<args.length; ++i) {
193 String s = args[i];
194 jq_Class c = (jq_Class) jq_Type.parseType(s);
195 c.load();
196 set.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
197 set.addAll(Arrays.asList(c.getDeclaredInstanceMethods()));
198 }
199 Problem p = new ReachingDefs();
200 Solver s1 = new IterativeSolver();
201 Solver s2 = new SortedSetSolver(BBComparator.INSTANCE);
202 Solver s3 = new PriorityQueueSolver();
203 for (Iterator i = set.iterator(); i.hasNext(); ) {
204 jq_Method m = (jq_Method) i.next();
205 if (m.getBytecode() == null) continue;
206 System.out.println("Method "+m);
207 ControlFlowGraph cfg = CodeCache.getCode(m);
208 System.out.println(cfg.fullDump());
209 solve(cfg, s1, p);
210 solve(cfg, s2, p);
211 solve(cfg, s3, p);
212 Solver.dumpResults(cfg, s1);
213 Solver.compareResults(cfg, s1, s2);
214 Solver.compareResults(cfg, s2, s3);
215 }
216 }
217
218 public static ReachingDefs solve(ControlFlowGraph cfg) {
219 ReachingDefs p = new ReachingDefs();
220 Solver s1 = new IterativeSolver();
221 p.mySolver = s1;
222 solve(cfg, s1, p);
223 if (TRACE) {
224 System.out.println("Finished solving ReachingDefs.");
225
226 }
227 return p;
228 }
229
230 private static void solve(ControlFlowGraph cfg, Solver s, Problem p) {
231 s.initialize(p, new EdgeGraph(cfg));
232 s.solve();
233 }
234
235 public Set
236 BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
237 return new BitStringSet(f.fact, Arrays.asList(quads));
238 }
239
240 public Set
241 BitString b = (BitString) regToDefs.get(r);
242 if (b == null) return Collections.EMPTY_SET;
243 BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
244 BitString result = (BitString) b.clone();
245 result.and(f.fact);
246 return new BitStringSet(result, Arrays.asList(quads));
247 }
248
249 public Set
250 BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
251 BitString result = (BitString) f.fact.clone();
252 withinBasicBlock(result, bb, q);
253 return new BitStringSet(result, Arrays.asList(quads));
254 }
255
256 public Set
257 BitString b = (BitString) regToDefs.get(r);
258 if (b == null) return Collections.EMPTY_SET;
259 BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
260 BitString result = (BitString) f.fact.clone();
261 withinBasicBlock(result, bb, q);
262 result.and(b);
263 return new BitStringSet(result, Arrays.asList(quads));
264 }
265
266 void withinBasicBlock(BitString bs, BasicBlock bb, Quad q2) {
267 for (ListIterator.Quad j = bb.iterator(); ; ) {
268 Quad q = j.nextQuad();
269 if (q == q2) break;
270 if (q.getDefinedRegisters().isEmpty()) continue;
271 int a = q.getID();
272 for (ListIterator.RegisterOperand k = q.getDefinedRegisters().registerOperandIterator(); k.hasNext(); ) {
273 Register r = k.nextRegisterOperand().getRegister();
274 BitString kill = (BitString) regToDefs.get(r);
275 bs.minus(kill);
276 }
277 bs.set(a);
278 }
279 }
280
281 }