View Javadoc

1   // ReachingDefs.java, created Jun 15, 2003 2:10:14 PM by joewhaley
2   // Copyright (C) 2003 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
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          /* (non-Javadoc)
47           * @see joeq.Compiler.Quad.ControlFlowGraphVisitor#visitCFG(joeq.Compiler.Quad.ControlFlowGraph)
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          // size of bit vector is bounded by the max quad id
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     /* (non-Javadoc)
160      * @see joeq.Compiler.Dataflow.Problem#direction()
161      */
162     public boolean direction() {
163         return true;
164     }
165 
166     /* (non-Javadoc)
167      * @see joeq.Compiler.Dataflow.Problem#boundary()
168      */
169     public Fact boundary() {
170         return emptySet;
171     }
172 
173     /* (non-Javadoc)
174      * @see joeq.Compiler.Dataflow.Problem#interior()
175      */
176     public Fact interior() {
177         return emptySet;
178     }
179 
180     /* (non-Javadoc)
181      * @see joeq.Compiler.Dataflow.Problem#getTransferFunction(java.lang.Object)
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             //Solver.dumpResults(cfg, s1);
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/*Quad*/ getReachingDefs(BasicBlock bb) {
236         BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
237         return new BitStringSet(f.fact, Arrays.asList(quads));
238     }
239     
240     public Set/*Quad*/ getReachingDefs(BasicBlock bb, Register r) {
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/*Quad*/ getReachingDefs(BasicBlock bb, Quad q) {
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/*Quad*/ getReachingDefs(BasicBlock bb, Quad q, Register r) {
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 }