1 package joeq.Compiler.Analysis.IPSSA;
2
3 import java.util.HashMap;
4 import java.util.HashSet;
5 import java.util.Iterator;
6 import java.util.LinkedList;
7 import java.io.PrintStream;
8 import joeq.Class.jq_Class;
9 import joeq.Class.jq_Method;
10 import joeq.Compiler.Analysis.IPSSA.Utils.SimpleDominatorQuery;
11 import joeq.Compiler.Quad.BasicBlock;
12 import joeq.Compiler.Quad.BasicBlockVisitor;
13 import joeq.Compiler.Quad.CodeCache;
14 import joeq.Compiler.Quad.ControlFlowGraph;
15 import joeq.Compiler.Quad.DotGraph;
16 import joeq.Compiler.Quad.ExceptionHandler;
17 import joeq.Compiler.Quad.Operator;
18 import joeq.Compiler.Quad.Quad;
19 import joeq.Compiler.Quad.QuadIterator;
20 import joeq.Util.Templates.ListIterator;
21 import jwutil.util.Assert;
22
23 /***
24 * @author V.Benjamin Livshits
25 * @see SSAProcInfo.Query
26 * @version $Id: SSAProcInfo.java 1931 2004-09-22 22:17:47Z joewhaley $
27 * */
28 public final class SSAProcInfo {
29 protected static HashMap
30 protected static HashMap
31 private static Iterator _emptyIterator = null;
32
33 public static Query retrieveQuery(jq_Method method){
34 if(_queryMap.containsKey(method)){
35 return (Query)_queryMap.get(method);
36 }else{
37 Query q = new Query(method);
38 _queryMap.put(method, q);
39
40 return q;
41 }
42 }
43 public static Helper retrieveHelper(jq_Method method){
44 if(_queryMap.containsKey(method)){
45 return (Helper)_helperMap.get(method);
46 }else{
47 Helper q = new Helper(method);
48 _helperMap.put(method, q);
49
50 return q;
51 }
52 }
53
54 static Iterator emptyIterator(){
55 if(_emptyIterator == null){
56 _emptyIterator = new HashSet().iterator();
57 }
58 return _emptyIterator;
59 }
60
61 /***
62 * This class is used to get information about the IPSSA representation.
63 * Use SSAProcInfo.retreiveQuery to get an appropriate query.
64 * @see SSAProcInfo.Helper
65 * */
66 public static class Query {
67 jq_Method _method;
68 protected ControlFlowGraph _cfg;
69 protected DominatorQuery _dom_query;
70 protected HashMap
71 private Quad _firstQuad;
72
73 protected Query(jq_Method method){
74 this._method = method;
75 this._cfg = CodeCache.getCode(method);
76 this._bindingMap = new HashMap();
77 this._dom_query = new SimpleDominatorQuery(_method);
78
79 makeFirstStatement();
80 }
81
82 private void makeFirstStatement(){
83 _firstQuad = Operator.Special.create(0, Operator.Special.NOP.INSTANCE);
84 }
85
86 public String toString(){
87 return "Query for " + _method.toString();
88 }
89
90 public SSADefinition getDefinitionFor(SSALocation loc, Quad q){
91 SSABindingAnnote ba = (SSABindingAnnote)_bindingMap.get(q);
92 if(ba == null) return null;
93
94 return ba.getDefinitionFor(loc);
95 }
96
97 public SSADefinition getLastDefinitionFor(SSALocation loc, Quad q, boolean strict){
98 if(strict){
99 q = _dom_query.getImmediateDominator(q);
100 }
101
102 while(q != null){
103 SSADefinition def = getDefinitionFor(loc, q);
104 if(def != null){
105 return def;
106 }
107 q = _dom_query.getImmediateDominator(q);
108 }
109
110
111 return getDefinitionFor(loc, _firstQuad);
112 }
113
114 public SSAIterator.BindingIterator getBindingIterator(Quad q){
115 Iterator iter = null;
116 if(_bindingMap.containsKey(q)){
117 iter = ((SSABindingAnnote)_bindingMap.get(q)).getBindingIterator();
118 }else{
119 iter = emptyIterator();
120 }
121
122 return new SSAIterator.BindingIterator(iter);
123 }
124
125 public int getBindingCount(Quad quad) {
126 if(!_bindingMap.containsKey(quad)){
127 return 0;
128 }else{
129 SSABindingAnnote ba = ((SSABindingAnnote)_bindingMap.get(quad));
130 return ba.size();
131 }
132 }
133
134 /***
135 * An iterator for all bindings in method.
136 * */
137 public SSAIterator.BindingIterator getBindingIterator(jq_Method method){
138 class MethodBindingIterator implements Iterator {
139 protected jq_Method _method;
140 protected Iterator _bindingIter;
141 protected Iterator _quadIter;
142 protected Query _query;
143
144 public MethodBindingIterator(jq_Method method){
145 this._method = method;
146 this._quadIter = new QuadIterator(CodeCache.getCode(_method));
147 this._bindingIter = emptyIterator();
148 this._query = retrieveQuery(_method);
149 }
150 public boolean hasNext(){
151 if(_bindingIter.hasNext()) return true;
152
153 while(_quadIter.hasNext()){
154 Quad quad = (Quad)_quadIter.next();
155 if(_query.getBindingCount(quad) > 0){
156 _bindingIter = _query.getBindingIterator(quad);
157
158 return true;
159 }
160 }
161
162 return false;
163 }
164 public Object next(){
165 if(_bindingIter.hasNext()){
166 return _bindingIter.next();
167 }else{
168 Quad quad = (Quad)_quadIter.next();
169 _bindingIter = _query.getBindingIterator(quad);
170
171 return _bindingIter.next();
172 }
173 }
174 public void remove(){
175 Assert._assert(false, "Don't call this method");
176 }
177 }
178 return new SSAIterator.BindingIterator(new MethodBindingIterator(method));
179 }
180
181 public void print(PrintStream out){
182 for (QuadIterator j=new QuadIterator(_cfg, true); j.hasNext(); ) {
183 Quad q = j.nextQuad();
184
185 SSABindingAnnote ba = (SSABindingAnnote)_bindingMap.get(q);
186 if(ba == null) continue;
187 out.println(q.toString() + "\n" + ba.toString("\t"));
188 }
189 }
190
191 public void printDot(){
192 new DotGraph(){
193 /*** Overwrite the CFG traversal method */
194 public void visitCFG(ControlFlowGraph cfg) {
195 try {
196 String filename = createMethodName(_method) + ".ssa.dot";
197
198 dot.openGraph("ssagraphs", filename);
199
200 cfg.visitBasicBlocks(new BasicBlockVisitor() {
201 public void visitBasicBlock(BasicBlock bb) {
202 SSAProcInfo.Query q = SSAProcInfo.retrieveQuery(_cfg.getMethod());
203 if (bb.isEntry()) {
204 if (bb.getNumberOfSuccessors() != 1)
205 throw new Error("entry bb has != 1 successors " + bb.getNumberOfSuccessors());
206 dot.addEntryEdge(bb.toString(), bb.getSuccessors().iterator().next().toString(), null);
207
208 StringBuffer l = new StringBuffer("Init://l");
209 Quad quad = getFirstQuad();
210 Iterator iter = q.getBindingIterator(quad);
211
212 if(iter.hasNext()){
213 do {
214 SSABinding b = (SSABinding)iter.next();
215 l.append(" => " + b.toString() + "//l");
216 } while(iter.hasNext());
217 dot.userDefined("\t\"" + bb.toString() + "\" [shape=box,label=\"" + l + "\"];\n");
218 }
219 } else
220 if (!bb.isExit()) {
221 ListIterator.Quad qit = bb.iterator();
222 StringBuffer l = new StringBuffer("Basic Block " + bb.toString() + "//l");
223 HashSet allExceptions = new HashSet();
224 while (qit.hasNext()) {
225
226 l.append(" ");
227 Quad quad = qit.nextQuad();
228 l.append(dot.escape(quad.toString()));
229 if(q.getBindingCount(quad) > 0){
230 l.append("(" + q.getBindingCount(quad) + ") //l");
231 for(Iterator iter = q.getBindingIterator(quad); iter.hasNext();){
232 SSABinding b = (SSABinding)iter.next();
233 l.append(" => " + b.toString() + "//l");
234 }
235 }else{
236 l.append("//l");
237 }
238
239 ListIterator.jq_Class exceptions = quad.getThrownExceptions().classIterator();
240 while (exceptions.hasNext()) {
241 allExceptions.add(exceptions.nextClass());
242 }
243 }
244 dot.userDefined("\t\"" + bb.toString() + "\" [shape=box,label=\"" + l + "\"];\n");
245
246 ListIterator.BasicBlock bit = bb.getSuccessors().basicBlockIterator();
247 while (bit.hasNext()) {
248 BasicBlock nextbb = bit.nextBasicBlock();
249 if (nextbb.isExit()) {
250 dot.addLeavingEdge(bb.toString(), nextbb.toString(), null);
251 } else {
252 dot.addEdge(bb.toString(), nextbb.toString());
253 }
254 }
255
256 Iterator eit = allExceptions.iterator();
257 while (eit.hasNext()) {
258 jq_Class exc = (jq_Class)eit.next();
259 ListIterator.ExceptionHandler mayCatch;
260 mayCatch = bb.getExceptionHandlers().mayCatch(exc).exceptionHandlerIterator();
261 while (mayCatch.hasNext()) {
262 ExceptionHandler exceptionHandler = mayCatch.nextExceptionHandler();
263 BasicBlock nextbb = exceptionHandler.getEntry();
264 dot.addEdge(bb.toString(), nextbb.toString(), exceptionHandler.getExceptionType().toString());
265 }
266
267 }
268 }
269 }
270 });
271 } catch(Exception e){
272 System.err.println("Error while writing ");
273 e.printStackTrace();
274 System.exit(2);
275 } finally {
276 dot.closeGraph();
277 }
278 }}.visitCFG(_cfg);
279 }
280
281 public DominatorQuery getDominatorQuery() {
282 return _dom_query;
283 }
284
285 public Quad getFirstQuad() {
286 return _firstQuad;
287 }
288 }
289
290 /***
291 * This class is used to make modifications to the IPSSA representation.
292 * @see SSAProcInfo.Query
293 * */
294 public static class Helper {
295 jq_Method _method;
296 Query _query;
297
298 protected Helper(jq_Method method){
299 this._method = method;
300 this._query = SSAProcInfo.retrieveQuery(_method);
301 }
302
303 public static SSADefinition create_ssa_definition(SSALocation loc, Quad quad, jq_Method method) {
304 return SSADefinition.Helper.create_ssa_definition(loc, quad, method);
305 }
306 }
307
308 static class SSABindingAnnote {
309 protected LinkedList _bindings;
310
311 SSABindingAnnote(){
312 _bindings = new LinkedList();
313 }
314
315 public SSADefinition getDefinitionFor(SSALocation loc) {
316 for(Iterator iter = _bindings.iterator(); iter.hasNext();){
317 SSABinding b = (SSABinding)iter.next();
318 SSADefinition def = b.getDestination();
319 if(def.getLocation() == loc){
320 return def;
321 }
322 }
323 return null;
324 }
325
326 public SSADefinition addBinding(SSALocation loc, SSAValue value, Quad quad, jq_Method method) {
327 SSABinding b = new SSABinding(quad, loc, value, method);
328 Assert._assert(quad == b.getDestination().getQuad());
329
330 this._bindings.addLast(b);
331
332
333
334
335 return b.getDestination();
336 }
337
338 /***
339 * Checks for duplicates among defined locations.
340 * */
341
342 public boolean is_valid() {
343 return true;
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361 }
362
363 public Iterator getBindingIterator(){
364 return _bindings.iterator();
365 }
366
367 public int size(){return _bindings.size();}
368
369 public String toString(String prepend){
370 StringBuffer result = new StringBuffer();
371 for(Iterator iter = _bindings.iterator(); iter.hasNext();){
372 SSABinding b = (SSABinding)iter.next();
373 result.append(prepend);
374 result.append(b.toString());
375 result.append("\n");
376 }
377
378 return result.toString();
379 }
380
381 public String toString(){return toString("");}
382 }
383 }
384