1 package joeq.Compiler.Analysis.IPSSA;
2
3 import java.util.Arrays;
4 import java.util.Collection;
5 import java.util.Collections;
6 import java.util.HashMap;
7 import java.util.HashSet;
8 import java.util.Iterator;
9 import java.util.LinkedList;
10 import java.util.Set;
11 import java.util.StringTokenizer;
12 import java.util.Vector;
13 import java.io.BufferedReader;
14 import java.io.FileInputStream;
15 import java.io.FileNotFoundException;
16 import java.io.FileOutputStream;
17 import java.io.FileReader;
18 import java.io.IOException;
19 import java.io.InputStreamReader;
20 import java.io.PrintStream;
21 import joeq.Class.PrimordialClassLoader;
22 import joeq.Class.jq_Class;
23 import joeq.Class.jq_Method;
24 import joeq.Compiler.Analysis.IPA.PAResults;
25 import joeq.Compiler.Analysis.IPA.PointerAnalysisResults;
26 import joeq.Compiler.Analysis.IPA.ProgramLocation;
27 import joeq.Compiler.Analysis.IPA.ProgramLocation.QuadProgramLocation;
28 import joeq.Compiler.Analysis.IPSSA.SSAProcInfo.Helper;
29 import joeq.Compiler.Analysis.IPSSA.SSAProcInfo.Query;
30 import joeq.Compiler.Analysis.IPSSA.SSAProcInfo.SSABindingAnnote;
31 import joeq.Compiler.Analysis.IPSSA.SSAValue.ActualOut;
32 import joeq.Compiler.Analysis.IPSSA.Utils.SSAGraphPrinter;
33 import joeq.Compiler.Quad.BasicBlock;
34 import joeq.Compiler.Quad.BasicBlockVisitor;
35 import joeq.Compiler.Quad.CallGraph;
36 import joeq.Compiler.Quad.CodeCache;
37 import joeq.Compiler.Quad.ControlFlowGraph;
38 import joeq.Compiler.Quad.Operator;
39 import joeq.Compiler.Quad.Quad;
40 import joeq.Compiler.Quad.QuadIterator;
41 import joeq.Compiler.Quad.QuadVisitor;
42 import joeq.Compiler.Quad.RegisterFactory.Register;
43 import joeq.Main.HostedVM;
44 import joeq.Util.Templates.ListIterator;
45 import jwutil.collections.AppendIterator;
46 import jwutil.graphs.SCCTopSortedGraph;
47 import jwutil.graphs.SCComponent;
48 import jwutil.graphs.Traversals;
49 import jwutil.util.Assert;
50
51 /***
52 * This is where the main action pertaining to IPSSA construction happens.
53 * A subclass is SSABuilder, which is responsible for intraprocedural IPSSA
54 * construction.
55 *
56 * @author V.Benjamin Livshits
57 * @see IPSSABuilder.SSABuilder
58 * @version $Id: IPSSABuilder.java 2283 2005-05-28 11:14:47Z joewhaley $
59 * */
60 public class IPSSABuilder implements Runnable {
61 protected int _verbosity;
62 private static HashMap _builderMap = new HashMap();
63 private PointerAnalysisResults _ptr = null;
64 private IPSSABuilder.ApplicationLaunchingPad _appPad = null;
65 private Collection _classes = null;
66
67 boolean PRINT_CFG = !System.getProperty("ipssa.print_cfg", "no").equals("no");
68 boolean PRINT_SSA_GRAPH = !System.getProperty("ipssa.print_ssa", "no").equals("no");
69 boolean RUN_BUILDER = !System.getProperty("ipssa.run_builder", "no").equals("no");
70 boolean RUN_APPS = !System.getProperty("ipssa.run_apps", "no").equals("no");
71
72
73 public IPSSABuilder(Collection classes, int verbosity){
74
75 CodeCache.AlwaysMap = true;
76 this._verbosity = verbosity;
77 this._classes = classes;
78
79 try {
80 String resdir = System.getProperty("pa.resultdir");
81 String[] args = null;
82 if(resdir != null) {
83 args = new String[1];
84 args[0] = resdir;
85 System.out.println("Reading pointer analysis results from directory " + resdir);
86 }
87 _ptr = PAResults.loadResults(args, null);
88 } catch (IOException e) {
89 System.err.println("Caught an exception: " + e.toString());
90 e.printStackTrace();
91 System.exit(1);
92 }
93 if(RUN_APPS) {
94 _appPad = new IPSSABuilder.ApplicationLaunchingPad(this, true);
95 }
96 }
97
98 public PAResults getPAResults() {
99 return (PAResults)_ptr;
100 }
101
102 public CallGraph getCallGraph() {
103 return _ptr.getCallGraph();
104 }
105
106 /***
107 * Handle an SCC in the call graph. Nodes of the SCC are jq_Method's.
108 * */
109 protected void processSCC(SCComponent c) {
110 Set nodes = c.nodeSet();
111 for(Iterator iter = nodes.iterator(); iter.hasNext();) {
112 jq_Method method = (jq_Method)iter.next();
113 if(skipMethod(method)) continue;
114
115 SSABuilder builder = new SSABuilder(method, _ptr, _verbosity);
116 Assert._assert(_builderMap.get(method ) == null);
117 _builderMap.put(method, builder);
118
119
120 builder.run(0);
121 builder.run(1);
122 }
123
124 for(Iterator iter = nodes.iterator(); iter.hasNext();) {
125 jq_Method method = (jq_Method)iter.next();
126 if(skipMethod((method))) continue;
127
128 SSABuilder builder = (SSABuilder)_builderMap.get(method);
129 Assert._assert(builder != null);
130
131 builder.run(2);
132
133 }
134 }
135
136 /***
137 * Do the whole analysis.
138 * */
139 public void run() {
140 if(RUN_BUILDER){
141 if(_classes.size() == 1) {
142 System.out.println("Analyzing one class...");
143 }else if(_classes.size() > 1) {
144 System.out.println("Analyzing these " + _classes.size() + " classes...");
145 }
146
147 Collection rootMethods = new LinkedList();
148 Iterator i = _classes.iterator();
149 while (i.hasNext()) {
150 jq_Class c = (jq_Class)i.next();
151 rootMethods.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
152 }
153
154 System.out.println("Using " + rootMethods.size() + " root(s)...");
155
156 CallGraph cg = this.getCallGraph();
157 for(Iterator iter = cg.getAllMethods().iterator(); iter.hasNext(); ) {
158 jq_Method method = (jq_Method)iter.next();
159 if(skipMethod(method)) continue;
160
161 System.err.println("Allowing \t" + method);
162 }
163 SCCTopSortedGraph sccGraph = SCCTopSortedGraph.topSort(SCComponent.buildSCC(rootMethods,
164 System.err.println("Found " + sccGraph.list().size() + " components");
165
166
167
168 for(Iterator graphIter = Traversals.postOrder(sccGraph.getNavigator(), sccGraph.getFirst()).iterator(); graphIter.hasNext();){
169 SCComponent d = (SCComponent) graphIter.next();
170
171 this.processSCC(d);
172 }
173 }
174
175 if(RUN_APPS) {
176 _appPad.run();
177 }
178 }
179
180 /***
181 * A method filter.
182 * */
183 public boolean skipMethod(jq_Method method) {
184 jq_Class k = method.getDeclaringClass();
185 if(!_classes.contains(k)) {
186
187 if(_verbosity > 3) {
188 System.err.println("Skipping " + method);
189 }
190 return true;
191 }
192 return false;
193 }
194
195 /*** The return result may be NULL */
196 public static SSABuilder getBuilder(jq_Method m){
197 return (SSABuilder)_builderMap.get(m);
198 }
199
200
201 /***
202 * SSABuilder takes care of a single method.
203 * */
204 class SSABuilder {
205 protected int _verbosity;
206 protected jq_Method _method;
207 protected ControlFlowGraph _cfg;
208 protected SSAProcInfo.Query _q;
209 private PointerAnalysisResults _ptr;
210 SSABuilder(jq_Method method, PointerAnalysisResults ptr, int verbosity){
211 this._method = method;
212 this._cfg = CodeCache.getCode(_method);
213 this._verbosity = verbosity;
214 this._q = null;
215 this._ptr = ptr;
216 }
217
218 public ControlFlowGraph getCFG() { return _cfg; }
219 public SSAProcInfo.Query getQuery() { return _q; }
220
221
222
223 /****************************************** Auxilary routines ************************************/
224
225 protected int addBinding(Quad quad, SSALocation loc, SSAValue value){
226 if(_ptr.hasAliases(_method, loc)){
227
228 int i = 0;
229 for(Iterator iter = _ptr.getAliases(_method, loc).iterator(); iter.hasNext();){
230 ContextSet.ContextLocationPair clPair = (ContextSet.ContextLocationPair)iter.next();
231
232
233 i += addBinding(quad, clPair.getLocation(), value, clPair.getContext());
234 }
235 return i;
236 }else{
237 addBinding(quad, loc, value, null);
238 return 1;
239 }
240 }
241
242 /***
243 * This is used by addBinding(Quad quad, SSALocation loc, SSAValue value) and
244 * should never be called directly.
245 * */
246 private int addBinding(Quad quad, SSALocation loc, SSAValue value, ContextSet context){
247
248 if(quad != _q.getFirstQuad()){
249 initializeLocation(loc);
250 }
251
252 SSABindingAnnote ba = (SSABindingAnnote)_q._bindingMap.get(quad);
253 if(ba == null){
254 ba = new SSABindingAnnote();
255 _q._bindingMap.put(quad, ba);
256 }
257
258 int result = 0;
259 if(context == null){
260 ba.addBinding(loc, value, quad, _method);
261 result++;
262 if(quad != _q.getFirstQuad()){
263 result += markIteratedDominanceFrontier(loc, quad);
264 }
265 }else{
266 SSADefinition tmpForValue = makeTemporary(value, quad, context);
267 result++;
268 SSADefinition lastDef = _q.getLastDefinitionFor(loc, quad, true);
269
270 SSAValue.SigmaPhi sigma = new SSAValue.SigmaPhi(context, tmpForValue, lastDef);
271 ba.addBinding(loc, sigma, quad, _method);
272 result++;
273 result += markIteratedDominanceFrontier(loc, quad);
274 }
275
276 return result;
277 }
278
279 /***
280 * This is used by addBinding(...) routines and should not be called directly.
281 * */
282 private int initializeLocation(SSALocation loc) {
283 if(_q.getDefinitionFor(loc, _q.getFirstQuad()) == null){
284 if(loc instanceof SSALocation.LocalLocation){
285
286 return addBinding(_q.getFirstQuad(), loc, null, null);
287 }else{
288
289 return addBinding(_q.getFirstQuad(), loc, new SSAValue.FormalIn(), null);
290 }
291 }else{
292 return 0;
293 }
294 }
295
296 /***
297 * Creates new empty definitions at the dominance frontier of quad for
298 * location loc.
299 */
300 private int markIteratedDominanceFrontier(SSALocation loc, Quad quad) {
301 if(loc instanceof SSALocation.Unique){
302
303 return 0;
304 }
305 int result = 0;
306 HashSet set = new HashSet();
307 _q.getDominatorQuery().getIteratedDominanceFrontier(quad, set);
308 if(_verbosity > 2) System.err.println("There are " + set.size() + " element(s) on the frontier");
309
310 for(Iterator iter = set.iterator(); iter.hasNext();){
311 Quad dom = (Quad)iter.next();
312 Assert._assert(dom.getOperator() instanceof Operator.Special.NOP, "" +
313 "Expected the quad on the dominance frontier to be a NOP, not a " + dom);
314 if(_q.getDefinitionFor(loc, dom) == null){
315 SSAValue.Gamma gamma = new SSAValue.Gamma();
316
317
318 result += addBinding(dom, loc, gamma, null);
319 if(_verbosity > 3) System.err.println("Created a gamma function for " + loc + " at " + dom);
320 }else{
321
322 }
323 }
324
325 return result;
326 }
327
328 /***
329 * Creates a temporary definition at quad with the RHS value in
330 * the given context.
331 * */
332 private SSADefinition makeTemporary(SSAValue value, Quad quad, ContextSet context) {
333
334 SSALocation.Temporary temp = SSALocation.Temporary.FACTORY.get();
335
336 addBinding(quad, temp, value, context);
337
338 SSADefinition def = _q.getDefinitionFor(temp, quad);
339 Assert._assert(def != null);
340
341 return def;
342 }
343
344
345 /********************************************* Stages ********************************************/
346
347 /***
348 * This functions runs one of the analysis stages for the given procedure.
349 * */
350 void run(int stage){
351 if(stage == 0) {
352
353 _cfg.visitBasicBlocks(new LiftMergesVisitor());
354
355 _q = SSAProcInfo.retrieveQuery(_method);
356
357 if(_verbosity>2) System.out.println("Created query: " + _q.toString());
358 if(_verbosity > 0){
359 String name = _method.toString();
360 if(name.length() > 40){
361 name = name.substring(40);
362 }else{
363 name = repeat(" ", 40-name.length())+name;
364 }
365 System.out.println("============= Processing method " + name + " in IPSSABuilder =============");
366 }
367 return;
368 }
369
370
371
372
373
374
375
376
377
378
379
380
381 if(stage == 1) {
382
383 Stage1Visitor vis1 = new Stage1Visitor(_method);
384 for (QuadIterator j=new QuadIterator(_cfg, true); j.hasNext(); ) {
385 Quad quad = j.nextQuad();
386 quad.accept(vis1);
387 }
388 if(_verbosity > 2){
389 System.err.println("Created a total of " + vis1.getBindingCount() + " bindings");
390 }
391 vis1 = null;
392 }
393
394
395
396
397
398
399
400
401
402
403 if(stage == 2) {
404 Stage2Visitor vis2 = new Stage2Visitor(_method);
405 for (QuadIterator j=new QuadIterator(_cfg, true); j.hasNext(); ) {
406 Quad quad = j.nextQuad();
407 quad.accept(vis2);
408 }
409 }
410
411 if(stage == 3) {
412 /*** Now print the results */
413 if(PRINT_CFG){
414
415 _q.printDot();
416 }
417
418 if(PRINT_SSA_GRAPH) {
419 try {
420 FileOutputStream file = new FileOutputStream("ssa.dot");
421 PrintStream out = new PrintStream(file);
422 SSAGraphPrinter.printAllToDot(out);
423 } catch (Exception e) {
424 e.printStackTrace();
425 System.exit(2);
426 }
427 }
428 }
429 }
430
431 /***
432 * This pass adds dummy NOP quads at the first quad of a basic block with more than one predecessors.
433 * That quad will later be used by gamma functions.
434 * */
435 private class LiftMergesVisitor implements BasicBlockVisitor {
436 public void visitBasicBlock(BasicBlock bb) {
437 if(bb.getPredecessors().size() > 1) {
438
439 Quad padding = Operator.Special.create(0, Operator.Special.NOP.INSTANCE);
440 int oldSize = bb.size();
441
442 bb.addQuad(0, padding);
443 Assert._assert(oldSize + 1 == bb.size());
444 }
445 }
446 }
447
448 /***
449 * Stage 1 : Process all statements in turn and create slots for each modified location.
450 * Invariant 1 : All necessary assignments are created by this point and all definitions are numbered.
451 * */
452 private class Stage1Visitor extends QuadVisitor.EmptyVisitor {
453 jq_Method _method;
454 SSAProcInfo.Helper _h;
455 SSAProcInfo.Query _q;
456 private int _bindings;
457
458 Stage1Visitor(jq_Method method){
459 this._method = method;
460 this._h = SSAProcInfo.retrieveHelper(_method);
461 this._q = SSAProcInfo.retrieveQuery(_method);
462 this._bindings = 0;
463 }
464
465 int getBindingCount(){
466 return _bindings;
467 }
468
469 /***************************** Begin handlers ****************************/
470 /*** A get static field instruction. */
471 public void visitGetstatic(Quad quad) {
472 processLoad(quad);
473 }
474 /*** A get instance field instruction. */
475 public void visitGetfield(Quad quad) {
476 processLoad(quad);
477 }
478 private void processLoad(Quad quad) {
479 markDestinations(quad);
480 }
481 /*** A put instance field instruction. */
482 public void visitPutfield(Quad quad) {
483 processStore(quad);
484 }
485 /*** A put static field instruction. */
486 public void visitPutstatic(Quad quad) {
487 processStore(quad);
488 }
489 /*** A register move instruction. */
490 public void visitMove(Quad quad) {
491 markDestinations(quad);
492 }
493 /*** An array load instruction. */
494 public void visitALoad(Quad quad) {
495 processLoad(quad);
496 }
497 /*** An array store instruction. */
498 public void visitAStore(Quad quad) {
499 print(quad);
500 }
501 /*** An quadect allocation instruction. */
502 public void visitNew(Quad quad) {
503 markDestinations(quad);
504 }
505 /*** An array allocation instruction. */
506 public void visitNewArray(Quad quad) {
507 markDestinations(quad);
508 }
509 /*** A return from method instruction. */
510 public void visitReturn(Quad quad) {
511
512 print(quad);
513 }
514 public void visitInvoke(Quad quad) {
515
516 processDefs(quad);
517 }
518 /***************************** End of handlers ****************************/
519
520 private void markDestinations(Quad quad) {
521 Register reg = getOnlyDefinedRegister(quad);
522 Assert._assert(reg != null);
523 SSALocation.LocalLocation loc = SSALocation.LocalLocation.FACTORY.createLocalLocation(reg);
524
525 addBinding(quad, loc, null, null);
526 }
527 private void processStore(Quad quad) {
528 processDefs(quad);
529 }
530
531 private void processDefs(Quad quad) {
532 QuadProgramLocation pl = new QuadProgramLocation(_method, quad);
533 Assert._assert(isCall(quad) || isStore(quad));
534 Set mods = _ptr.mod(pl, _q.getDominatorQuery().getBasicBlock(quad));
535
536
537 if(mods != null && mods.size() > 0){
538 if(_verbosity > 2) System.out.print("Found " + mods.size() + " mods at " + pl.toString() + ": [ ");
539 Iterator iter = mods.iterator();
540 while(iter.hasNext()){
541 SSALocation loc = (SSALocation)iter.next();
542 if(_verbosity > 2) System.out.print(loc.toString(_ptr.getPAResults()) + " ");
543 if(isCall(quad)){
544 _bindings += addBinding(quad, loc, new SSAValue.ActualOut(), null);
545 }else
546 if(isStore(quad)){
547 _bindings += addBinding(quad, loc, null, null);
548 }else{
549 Assert._assert(false);
550 }
551 }
552 if(_verbosity > 2) System.out.println("]\n");
553 }
554 }
555
556 /*** Any quad */
557 public void visitQuad(Quad quad) {print(quad);}
558
559 protected void print(Quad quad, boolean force){
560 if(!force) return;
561 ProgramLocation loc = new QuadProgramLocation(_method, quad);
562 String loc_str = null;
563
564 try {
565 loc_str = loc.getSourceFile() + ":" + loc.getLineNumber();
566 }catch(Exception e){
567 loc_str = "<unknown>";
568 }
569
570 System.out.println("Visited quad # " + quad.toString() + "\t\t\t at " + loc_str);
571 }
572
573 protected void printAlways(Quad quad){
574 print(quad, true);
575 }
576
577 protected void print(Quad quad){
578 print(quad, false);
579 }
580
581 protected void warn(String s){
582 System.err.println(s);
583 }
584 }
585
586 /***
587 * Stage 2 : Walk over and fill in all RHSs that don't require dereferencing.
588 * Invariant 2 : Update RHSs referring to heap objects to refer to the right locations.
589 * */
590 private class Stage2Visitor extends QuadVisitor.EmptyVisitor {
591 private jq_Method _method;
592 private Query _q;
593 private Helper _h;
594
595 Stage2Visitor(jq_Method method){
596 this._method = method;
597 this._h = SSAProcInfo.retrieveHelper(_method);
598 this._q = SSAProcInfo.retrieveQuery(_method);
599 }
600
601 /***************************** Begin handlers ****************************/
602 /*** A get static field instruction. */
603 public void visitGetstatic(Quad quad) {
604 processLoad(quad);
605 }
606 /*** A get instance field instruction. */
607 public void visitGetfield(Quad quad) {
608 processLoad(quad);
609 }
610 /*** A put instance field instruction. */
611 public void visitPutfield(Quad quad) {
612 processStore(quad);
613 }
614 /*** A put static field instruction. */
615 public void visitPutstatic(Quad quad) {
616 processStore(quad);
617 }
618 /*** A register move instruction. */
619 public void visitMove(Quad quad) {
620
621 Assert._assert(_q.getBindingCount(quad) == 1);
622 SSABinding b = _q.getBindingIterator(quad).nextBinding();
623 Assert._assert(b.getValue() == null);
624 b.setValue(markUses(quad));
625 }
626 /*** An array load instruction. */
627 public void visitALoad(Quad quad) {
628 processLoad(quad);
629 }
630 /*** An array store instruction. */
631 public void visitAStore(Quad quad) {
632 processStore(quad);
633 }
634 /*** An quadect allocation instruction. */
635 public void visitNew(Quad quad) {
636
637 Assert._assert(_q.getBindingCount(quad) == 1);
638 SSABinding b = _q.getBindingIterator(quad).nextBinding();
639 Assert._assert(b.getValue() == null);
640 b.setValue(makeAlloc(quad));
641 }
642 /*** An array allocation instruction. */
643 public void visitNewArray(Quad quad) {
644
645 Assert._assert(_q.getBindingCount(quad) == 1);
646 SSABinding b = _q.getBindingIterator(quad).nextBinding();
647 Assert._assert(b.getValue() == null);
648 b.setValue(makeAlloc(quad));
649 }
650 /*** A return from method instruction. */
651 public void visitReturn(Quad quad) {
652
653 }
654 public void visitInvoke(Quad quad) {
655 processCall(quad);
656 }
657 /***************************** End of handlers ****************************/
658
659 private void processStore(Quad quad) {
660
661
662 for(SSAIterator.BindingIterator iter = _q.getBindingIterator(quad); iter.hasNext();) {
663 SSABinding b = iter.nextBinding();
664 Assert._assert(b.getValue() == null);
665 b.setValue(markUses(quad));
666 }
667 }
668
669
670 /*** A special instruction. */
671 public void visitSpecial(Quad quad) {
672 if(quad.getOperator() instanceof Operator.Special.NOP) {
673 SSAIterator.BindingIterator bindingIter = _q.getBindingIterator(quad);
674 while(bindingIter.hasNext()){
675 SSABinding b = bindingIter.nextBinding();
676 SSAValue value = b.getValue();
677
678 if(value != null && value instanceof SSAValue.Gamma){
679 SSAValue.Gamma gamma = (SSAValue.Gamma)value;
680 fillInGamma(quad, gamma);
681 }
682 }
683 }
684 }
685
686 /***
687 * Fill in the gamma function with reaching definitions
688 * */
689 private void fillInGamma(Quad quad, SSAValue.Gamma gamma) {
690 SSALocation loc = gamma.getDestination().getLocation();
691
692 BasicBlock basicBlock = _q.getDominatorQuery().getBasicBlock(quad);
693 Assert._assert(basicBlock != null);
694 Assert._assert(basicBlock.size() > 0);
695 Assert._assert(basicBlock.getQuad(0) == quad);
696 ListIterator.BasicBlock predIter = basicBlock.getPredecessors().basicBlockIterator();
697 while(predIter.hasNext()){
698 BasicBlock predBlock = predIter.nextBasicBlock();
699 Quad predQuad = predBlock.isEntry() ? _q.getFirstQuad() : predBlock.getLastQuad();
700 SSADefinition predDef = _q.getLastDefinitionFor(loc, predQuad, false);
701 gamma.add(predDef, null);
702 }
703 }
704
705 /***
706 * This method fills in the RHS of loads.
707 * */
708 private void processLoad(Quad quad) {
709 QuadProgramLocation pl = new QuadProgramLocation(_method, quad);
710 Assert._assert(isLoad(quad));
711 Set refs = _ptr.ref(pl, _q.getDominatorQuery().getBasicBlock(quad));
712
713 SSAValue.OmegaPhi value = new SSAValue.OmegaPhi();
714
715
716 if(refs != null && refs.size() > 0){
717 if(_verbosity > 2) System.out.print("Found " + refs.size() + " refs at " + pl.toString() + ": [ ");
718 Iterator iter = refs.iterator();
719 while(iter.hasNext()){
720 SSALocation loc = (SSALocation)iter.next();
721 if(_verbosity > 2) System.out.print(loc.toString(_ptr.getPAResults()) + " ");
722
723 initializeLocation(loc);
724 SSADefinition def = _q.getLastDefinitionFor(loc, quad, true);
725 Assert._assert(def != null);
726 if(_verbosity > 1) System.out.println("Using " + def + " at " + quad);
727 value.addUsedDefinition(def);
728 }
729 if(_verbosity > 2) System.out.println("]\n");
730 }
731
732 Assert._assert(_q.getBindingCount(quad) == 1, "Have " + _q.getBindingCount(quad) + " bindings at " + quad);
733 SSABinding b = _q.getBindingIterator(quad).nextBinding();
734 Assert._assert(b.getValue() == null);
735 Assert._assert(b.getDestination().getLocation() instanceof SSALocation.LocalLocation);
736 SSALocation.LocalLocation loc = (SSALocation.LocalLocation) b.getDestination().getLocation();
737 Assert._assert(loc.getRegister() == getOnlyDefinedRegister(quad));
738 b.setValue(value);
739 }
740
741 private void processCall(Quad quad) {
742 Assert._assert(isCall(quad));
743 QuadProgramLocation pl = new QuadProgramLocation(_method, quad);
744 Set
745 if(targets.size() == 0) {
746 System.err.println("No targets of call " + quad);
747 return;
748 }
749 /***
750 * Fill in the existing rho values at this call site.
751 * */
752 for(SSAIterator.BindingIterator iter = _q.getBindingIterator(quad); iter.hasNext(); ) {
753 SSABinding b = iter.nextBinding();
754 Assert._assert(b.getValue() instanceof SSAValue.ActualOut);
755 SSAValue.ActualOut value = (ActualOut)b.getValue();
756 SSALocation loc = b.getDestination().getLocation();
757
758
759 for(Iterator targetIter = targets.iterator(); targetIter.hasNext();) {
760 jq_Method method = (jq_Method)targetIter.next();
761
762 SSABuilder calleeBuilder = getBuilder(method);
763 if(calleeBuilder == null) {
764 Assert._assert(false, "Method " + method + " hasn't been processed");
765 }
766 calleeBuilder.initializeLocation(loc);
767 SSADefinition lastDef = calleeBuilder.getQuery().getLastDefinitionFor(loc,
768 calleeBuilder.getCFG().exit().getLastQuad(), false);
769
770 value.add(lastDef, method);
771 }
772
773 }
774
775 /***
776 * Add this call site to FormalIn's at all the callees.
777 * */
778 for(Iterator targetIter = targets.iterator(); targetIter.hasNext();) {
779 jq_Method method = (jq_Method)targetIter.next();
780 if(skipMethod(method)) continue;
781
782 SSABuilder calleeBuilder = getBuilder(method);
783 if(calleeBuilder == null) {
784 Assert._assert(false, "Method " + method + " hasn't been processed yet");
785 }
786
787 for(Iterator iter = calleeBuilder.getQuery().getBindingIterator(calleeBuilder.getQuery().getFirstQuad()); iter.hasNext();) {
788 SSABinding b = (SSABinding)iter.next();
789 if(!(b.getValue() instanceof SSAValue.FormalIn)) continue;
790
791 SSALocation loc = b.getDestination().getLocation();
792
793
794 SSAValue.FormalIn value = (SSAValue.FormalIn)b.getValue();
795 if(!value.hasCallSite(quad)) {
796 initializeLocation(loc);
797 SSADefinition lastDef = _q.getLastDefinitionFor(loc, quad, true);
798 Assert._assert(lastDef != null);
799 value.add(lastDef, quad);
800 } else {
801 Assert._assert(false, "Already added a definition for " + method + " to " + value + ". Recursion?");
802 }
803 }
804 }
805 }
806
807 private SSAValue.Normal markUses(Quad quad) {
808 SSAValue.UseCollection value = SSAValue.UseCollection.FACTORY.createUseCollection();
809 ListIterator.RegisterOperand iter = quad.getUsedRegisters().registerOperandIterator();
810 while(iter.hasNext()) {
811 Register reg = iter.nextRegisterOperand().getRegister();
812 SSALocation loc = SSALocation.LocalLocation.FACTORY.createLocalLocation(reg);
813 initializeLocation(loc);
814 SSADefinition def =_q.getLastDefinitionFor(loc, quad, true);
815 Assert._assert(def != null);
816
817 value.addUsedDefinition(def);
818 }
819
820 return value;
821 }
822
823 private SSAValue makeAlloc(Quad quad) {
824 return SSAValue.Alloc.FACTORY.createAlloc(quad);
825 }
826 }
827 }
828
829
830 public static boolean isLoad(Quad quad) {
831 return
832 (quad.getOperator() instanceof Operator.Getfield) ||
833 (quad.getOperator() instanceof Operator.Getstatic);
834 }
835 public static boolean isStore(Quad quad) {
836 return
837 (quad.getOperator() instanceof Operator.Putfield) ||
838 (quad.getOperator() instanceof Operator.Putstatic);
839 }
840 public static boolean isCall(Quad quad) {
841 return (quad.getOperator() instanceof Operator.Invoke);
842 }
843 private static String repeat(String string, int n) {
844 StringBuffer result = new StringBuffer();
845 for(int i = 0; i<n; i++) result.append(string);
846
847 return result.toString();
848 }
849 private static Register getOnlyDefinedRegister(Quad quad) {
850 joeq.Util.Templates.ListIterator.RegisterOperand iter = quad.getDefinedRegisters().registerOperandIterator();
851 if(!iter.hasNext()){
852
853 return null;
854 }
855 Register reg = iter.nextRegisterOperand().getRegister();
856 Assert._assert(!iter.hasNext(), "More than one defined register");
857
858 return reg;
859 }
860 private static Register getOnlyUsedRegister(Quad quad) {
861 joeq.Util.Templates.ListIterator.RegisterOperand iter = quad.getUsedRegisters().registerOperandIterator();
862 if(!iter.hasNext()){
863
864 return null;
865 }
866 Register reg = iter.nextRegisterOperand().getRegister();
867 Assert._assert(!iter.hasNext(), "More than one used register");
868
869 return reg;
870 }
871
872 /***
873 * This class allows to specify applications to be
874 * run after IPSSA has been constructed.
875 *
876 * @see IPSSABuilder.Application
877 * */
878 public static class ApplicationLaunchingPad implements Runnable {
879 LinkedList _applications;
880 boolean _verbosity;
881 private IPSSABuilder _builder;
882
883 public ApplicationLaunchingPad(IPSSABuilder builder, boolean verbosity){
884 _builder = builder;
885 _applications = new LinkedList();
886 _verbosity = verbosity;
887
888 readConfig();
889 }
890 public ApplicationLaunchingPad(IPSSABuilder builder, Application app, boolean verbosity){
891 this(builder, verbosity);
892
893 addApplication(app);
894 }
895 public ApplicationLaunchingPad(IPSSABuilder builder){
896 this(builder, false);
897 }
898 public void addApplication(Application app){
899 _applications.addLast(app);
900 }
901 public IPSSABuilder getBuilder() {
902 return _builder;
903 }
904 public void run() {
905 for(Iterator iter = _applications.iterator(); iter.hasNext(); ) {
906 Application app = (Application)iter.next();
907
908 if(_verbosity){
909 System.out.println("Running application " + app.getName());
910 }
911 app.run();
912 }
913 }
914 /***
915 Read the configuration for applications.
916 */
917 private void readConfig(){
918 String filename = "app.config";
919 FileInputStream fi = null;
920 try {
921 fi = new FileInputStream(filename);
922 BufferedReader r = new BufferedReader(new InputStreamReader(fi));
923 String line = r.readLine();
924 while(line != null){
925 if(line.charAt(0) == '#') {
926 line = r.readLine();
927 continue;
928 }
929 Application app = Application.create(_builder, line);
930 if(app != null){
931 addApplication(app);
932 app.setBuilder(this.getBuilder());
933 }else{
934 System.err.println("Skipped " + line);
935 }
936 line = r.readLine();
937 }
938 } catch (FileNotFoundException e) {
939 System.err.println("Couldn't read file " + filename);
940 return;
941 } catch (Exception e) {
942 e.printStackTrace();
943 return;
944 } finally {
945 if (fi != null) try { fi.close(); } catch (IOException _) { }
946 }
947 }
948 }
949
950 /***
951 * This is something we typically run afte the IPSSABuilder.
952 * @see IPSSABuilder
953 * @see IPSSABuilder.ApplicationLaunchingPad
954 * */
955 public abstract static class Application implements Runnable {
956 private String _name;
957 protected IPSSABuilder _builder;
958
959 public Application() {
960 this(null, null);
961 }
962 public Application(IPSSABuilder builder, String name, String[] args){
963 parseParams(args);
964 _name = name;
965 _builder = builder;
966
967 initialize();
968 }
969 protected void initialize() {}
970
971 protected void setBuilder(IPSSABuilder builder) {
972 _builder = builder;
973 }
974 protected IPSSABuilder getBuilder() {
975 return _builder;
976 }
977 public static Application create(IPSSABuilder builder, String line) {
978 StringTokenizer tokenizer = new StringTokenizer(line, " ");
979 String className = tokenizer.nextToken();
980 String appName = tokenizer.nextToken();
981
982 Vector argv = new Vector();
983 while(tokenizer.hasMoreTokens()) {
984 argv.add(tokenizer.nextToken());
985 }
986
987 Application app = null;
988
989 Class c;
990 try {
991
992
993 c = Class.forName(className);
994 try {
995 app = (Application)c.newInstance();
996 } catch (InstantiationException e1) {
997 e1.printStackTrace();
998 return null;
999 } catch (IllegalAccessException e1) {
1000 e1.printStackTrace();
1001 return null;
1002 }
1003 } catch (ClassNotFoundException e) {
1004 e.printStackTrace();
1005 return null;
1006 }
1007
1008 if(app == null) {
1009 System.err.println("Can't create an instance of " + className);
1010 return null;
1011 }
1012
1013 app.setBuilder(builder);
1014 app.setName(appName);
1015 app.parseParams(argv.toArray());
1016
1017
1018 app.initialize();
1019
1020 return app;
1021 }
1022 private void setName(String appName) {
1023 _name = appName;
1024
1025 }
1026 public String getName() {
1027 return _name;
1028 }
1029 Application(String name, String args){
1030 _name = name;
1031 StringTokenizer tokenizer = new StringTokenizer(args, " ");
1032 Vector argv = new Vector();
1033 while(tokenizer.hasMoreTokens()) {
1034 argv.add(tokenizer.nextToken());
1035 }
1036 parseParams((String[])argv.toArray());
1037 }
1038
1039 protected abstract void parseParams(String[] args);
1040
1041 private void parseParams(Object[] objects) {
1042 String[] argv = new String[objects.length];
1043 for(int i = 0; i < objects.length; i++) {
1044 argv[i] = (String)objects[i];
1045 }
1046
1047 parseParams(argv);
1048 }
1049
1050 public abstract void run();
1051 }
1052
1053 /***
1054 * This is an entry point for IPSSABuilder with a main(...) function.
1055 * */
1056 public static class Main {
1057 static boolean _verbose = false;
1058
1059 public static void main(String[] args) {
1060 HostedVM.initialize();
1061
1062 Iterator i = null; String memberName = null;
1063 for (int x=0; x<args.length; ++x) {
1064 if (args[x].equals("-file")) {
1065 try {
1066 BufferedReader br = new BufferedReader(new FileReader(args[++x]));
1067 LinkedList list = new LinkedList();
1068 for (;;) {
1069 String s = br.readLine();
1070 if (s == null) break;
1071 if (s.length() == 0) continue;
1072 if (s.startsWith("%")) continue;
1073 if (s.startsWith("#")) continue;
1074 list.add(s);
1075 }
1076 i = new AppendIterator(list.iterator(), i);
1077 }catch(IOException e) {
1078 e.printStackTrace();
1079 System.exit(2);
1080 }
1081
1082 } else
1083 if (args[x].endsWith("*")) {
1084 i = new AppendIterator(PrimordialClassLoader.loader.listPackage(args[x].substring(0, args[x].length()-1)), i);
1085 } else
1086 if(args[x].charAt(0) == '-'){
1087 usage();
1088 System.exit(2);
1089 }else {
1090 String classname = args[x];
1091 i = new AppendIterator(Collections.singleton(classname).iterator(), i);
1092 }
1093 }
1094 if (i == null) {
1095 System.err.println("At least one class is requred for execution");
1096 System.exit(2);
1097 }
1098
1099 LinkedList classes = new LinkedList();
1100 while (i.hasNext()) {
1101 String classname = (String)i.next();
1102 if (classname.endsWith(".properties")) continue;
1103 if (classname.endsWith(".class")) classname = classname.substring(0, classname.length()-6);
1104 String classdesc = "L" + classname.replace('.', '/') + ";";
1105 jq_Class c = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType(classdesc);
1106 System.err.println("Preparing class [" + classdesc + "] ...");
1107 c.prepare();
1108 classes.add(c);
1109 }
1110
1111
1112 IPSSABuilder builder = new IPSSABuilder(classes, 2);
1113 builder.run();
1114 }
1115
1116 private static void usage() {
1117 System.err.println("Usage: ");
1118
1119 }
1120 }
1121 };