|
1
19
20 package soot.dava.internal.asg;
21
22 import soot.*;
23 import java.util.*;
24 import soot.util.*;
25 import soot.dava.*;
26 import soot.jimple.*;
27 import soot.toolkits.graph.*;
28 import soot.dava.toolkits.base.finders.*;
29
30 public class AugmentedStmtGraph implements DirectedGraph
31 {
32 private HashMap binding, original2clone;
33 private IterableSet aug_list, stmt_list;
34 private List bheads, btails, cheads, ctails;
35
36
37 public AugmentedStmtGraph( AugmentedStmtGraph other)
38 {
39 this();
40
41 HashMap old2new = new HashMap();
42
43 Iterator it = other.aug_list.iterator();
44 while (it.hasNext()) {
45 AugmentedStmt oas = (AugmentedStmt) it.next();
46 Stmt s = oas.get_Stmt();
47
48 AugmentedStmt nas = new AugmentedStmt( s);
49 aug_list.add( nas);
50 stmt_list.add( s);
51 binding.put( s, nas);
52
53 old2new.put( oas, nas);
54 }
55
56
57 it = other.aug_list.iterator();
58 while (it.hasNext()) {
59 AugmentedStmt oas = (AugmentedStmt) it.next();
60 AugmentedStmt nas = (AugmentedStmt) old2new.get( oas);
61
62 Iterator pit = oas.bpreds.iterator();
63 while (pit.hasNext())
64 nas.bpreds.add( old2new.get( pit.next()));
65 if (nas.bpreds.isEmpty())
66 bheads.add( nas);
67
68 pit = oas.cpreds.iterator();
69 while (pit.hasNext())
70 nas.cpreds.add( old2new.get( pit.next()));
71 if (nas.cpreds.isEmpty())
72 cheads.add( nas);
73
74 Iterator sit = oas.bsuccs.iterator();
75 while (sit.hasNext())
76 nas.bsuccs.add( old2new.get( sit.next()));
77 if (nas.bsuccs.isEmpty())
78 btails.add( nas);
79
80 sit = oas.csuccs.iterator();
81 while (sit.hasNext())
82 nas.csuccs.add( old2new.get( sit.next()));
83 if (nas.csuccs.isEmpty())
84 ctails.add( nas);
85 }
86
87 find_Dominators();
88 }
89
90 public AugmentedStmtGraph( BriefUnitGraph bug, TrapUnitGraph cug)
91 {
92 this();
93
94 Dava.v().log( "AugmentedStmtGraph::AugmentedStmtGraph() - cug.size() = " + cug.size());
95
96 Iterator it = cug.iterator();
98 while (it.hasNext()) {
99 Stmt s = (Stmt) it.next();
100 add_StmtBinding( s, new AugmentedStmt( s));
101 }
102
103 it = (new PseudoTopologicalOrderer()).newList( cug).iterator();
105 while (it.hasNext()) {
106 Stmt s = (Stmt) it.next();
107 aug_list.add( get_AugStmt( s));
108 stmt_list.add( s);
109 }
110
111 it = aug_list.iterator();
113 while (it.hasNext()) {
114 AugmentedStmt as = (AugmentedStmt) it.next();
115
116 mirror_PredsSuccs( as, bug);
117 mirror_PredsSuccs( as, cug);
118 }
119
120 find_Dominators();
121 }
122
123 public AugmentedStmtGraph()
124 {
125 binding = new HashMap();
126 original2clone = new HashMap();
127 aug_list = new IterableSet();
128 stmt_list = new IterableSet();
129
130 bheads = new LinkedList();
131 btails = new LinkedList();
132 cheads = new LinkedList();
133 ctails = new LinkedList();
134 }
135
136 public void add_AugmentedStmt( AugmentedStmt as)
137 {
138 Stmt s = as.get_Stmt();
139
140 aug_list.add( as);
141 stmt_list.add( s);
142
143 add_StmtBinding( s, as);
144
145 if (as.bpreds.isEmpty())
146 bheads.add( as);
147
148 if (as.cpreds.isEmpty())
149 cheads.add( as);
150
151 if (as.bsuccs.isEmpty())
152 btails.add( as);
153
154 if (as.csuccs.isEmpty())
155 ctails.add( as);
156
157 check_List( as.bpreds, btails);
158 check_List( as.bsuccs, bheads);
159 check_List( as.cpreds, ctails);
160 check_List( as.csuccs, cheads);
161 }
162
163 public boolean contains( Object  o)
164 {
165 return aug_list.contains( o);
166 }
167
168 public AugmentedStmt get_CloneOf( AugmentedStmt as)
169 {
170 return (AugmentedStmt) original2clone.get( as);
171 }
172
173 public int size()
174 {
175 return aug_list.size();
176 }
177
178 private void check_List( List psList, List htList)
179 {
180 Iterator it = psList.iterator();
181 while (it.hasNext()) {
182 Object o = it.next();
183
184 if (htList.contains( o))
185 htList.remove(o);
186 }
187 }
188
189
190 public void calculate_Reachability( AugmentedStmt source, HashSet blockers, AugmentedStmt dominator)
191 {
192 if (blockers == null)
193 throw new RuntimeException ( "Tried to call AugmentedStmtGraph:calculate_Reachability() with null blockers.");
194
195 if (source == null)
196 return;
197
198 LinkedList worklist = new LinkedList();
199 HashSet touchSet = new HashSet();
200
201 worklist.addLast( source);
202 touchSet.add( source);
203
204 while (worklist.isEmpty() == false) {
205 AugmentedStmt as = (AugmentedStmt) worklist.removeFirst();
206
207 Iterator sit = as.csuccs.iterator();
208 while (sit.hasNext()) {
209 AugmentedStmt sas = (AugmentedStmt) sit.next();
210
211 if ((touchSet.contains( sas)) || (sas.get_Dominators().contains( dominator) == false))
212 continue;
213
214 touchSet.add( sas);
215
216 IterableSet reachers = sas.get_Reachers();
217
218 if (reachers.contains( source) == false)
219 reachers.add( source);
220
221 if (blockers.contains( sas) == false)
222 worklist.addLast( sas);
223 }
224 }
225 }
226
227 public void calculate_Reachability( Collection sources, HashSet blockers, AugmentedStmt dominator)
228 {
229 Iterator srcIt = sources.iterator();
230 while (srcIt.hasNext())
231 calculate_Reachability( (AugmentedStmt) srcIt.next(), blockers, dominator);
232 }
233
234 public void calculate_Reachability( AugmentedStmt source, AugmentedStmt blocker, AugmentedStmt dominator)
235 {
236 HashSet h = new HashSet();
237
238 h.add( blocker);
239
240 calculate_Reachability( source, h, dominator);
241 }
242
243 public void calculate_Reachability( Collection sources, AugmentedStmt blocker, AugmentedStmt dominator)
244 {
245 HashSet h = new HashSet();
246
247 h.add( blocker);
248
249 calculate_Reachability( sources, h, dominator);
250 }
251
252 public void calculate_Reachability( AugmentedStmt source, AugmentedStmt dominator)
253 {
254 calculate_Reachability( source, new HashSet(), dominator);
255 }
256
257 public void calculate_Reachability( Collection sources, AugmentedStmt dominator)
258 {
259 calculate_Reachability( sources, new HashSet(), dominator);
260 }
261
262 public void calculate_Reachability( AugmentedStmt source)
263 {
264 calculate_Reachability( source, null);
265 }
266
267 public void calculate_Reachability( Collection sources)
268 {
269 calculate_Reachability( sources, null);
270 }
271
272 public void add_StmtBinding( Stmt s, AugmentedStmt as)
273 {
274 binding.put( s, as);
275 }
276
277 public AugmentedStmt get_AugStmt( Stmt s)
278 {
279 AugmentedStmt as = (AugmentedStmt) binding.get( s);
280 if (as == null)
281 throw new RuntimeException ( "Could not find augmented statement for: " + s.toString());
282
283 return as;
284 }
285
286
287
289 public List getHeads()
290 {
291 return cheads;
292 }
293
294 public List getTails()
295 {
296 return ctails;
297 }
298
299 public Iterator iterator()
300 {
301 return aug_list.iterator();
302 }
303
304 public List getPredsOf( Object s)
305 {
306 if (s instanceof AugmentedStmt)
307 return ((AugmentedStmt) s).cpreds;
308 else if (s instanceof Stmt)
309 return get_AugStmt((Stmt) s).cpreds;
310 else
311 throw new RuntimeException ( "Object " + s + " class: " + s.getClass() + " not a member of this AugmentedStmtGraph");
312 }
313
314 public List getSuccsOf( Object s)
315 {
316 if (s instanceof AugmentedStmt)
317 return ((AugmentedStmt) s).csuccs;
318 else if (s instanceof Stmt)
319 return get_AugStmt((Stmt) s).csuccs;
320 else
321 throw new RuntimeException ( "Object " + s + " class: " + s.getClass() + " not a member of this AugmentedStmtGraph");
322 }
323
324
326 public List get_BriefHeads()
327 {
328 return bheads;
329 }
330
331 public List get_BriefTails()
332 {
333 return btails;
334 }
335
336 public IterableSet get_ChainView()
337 {
338 IterableSet c = new IterableSet();
339
340 c.addAll( aug_list);
341 return c;
342 }
343
344 public Object clone()
345 {
346 return new AugmentedStmtGraph( this);
347 }
348
349 public boolean remove_AugmentedStmt( AugmentedStmt toRemove)
350 {
351 if (aug_list.contains( toRemove) == false)
352 return false;
353
354 Iterator pit = toRemove.bpreds.iterator();
355 while (pit.hasNext()) {
356 AugmentedStmt pas = (AugmentedStmt) pit.next();
357 if (pas.bsuccs.contains( toRemove))
358 pas.bsuccs.remove( toRemove);
359 }
360
361 pit = toRemove.cpreds.iterator();
362 while (pit.hasNext()) {
363 AugmentedStmt pas = (AugmentedStmt) pit.next();
364 if (pas.csuccs.contains( toRemove))
365 pas.csuccs.remove( toRemove);
366 }
367
368 Iterator sit = toRemove.bsuccs.iterator();
369 while (sit.hasNext()) {
370 AugmentedStmt sas = (AugmentedStmt) sit.next();
371 if (sas.bpreds.contains( toRemove))
372 sas.bpreds.remove( toRemove);
373 }
374
375 sit = toRemove.csuccs.iterator();
376 while (sit.hasNext()) {
377 AugmentedStmt sas = (AugmentedStmt) sit.next();
378 if (sas.cpreds.contains( toRemove))
379 sas.cpreds.remove( toRemove);
380 }
381
382 aug_list.remove( toRemove);
383 stmt_list.remove( toRemove.get_Stmt());
384
385 if (bheads.contains( toRemove))
386 bheads.remove( toRemove);
387 if (btails.contains( toRemove))
388 btails.remove( toRemove);
389 if (cheads.contains( toRemove))
390 cheads.remove( toRemove);
391 if (ctails.contains( toRemove))
392 ctails.remove( toRemove);
393
394 binding.remove( toRemove.get_Stmt());
395
396 return true;
397
398 }
400
401 public String toString()
402 {
403 StringBuffer b = new StringBuffer ();
404 String cr = "\n";
405
406 b.append( "AugmentedStmtGraph (size: " + size() + " stmts)" + cr);
407
408 Iterator it = aug_list.iterator();
409 while (it.hasNext()) {
410 AugmentedStmt as = (AugmentedStmt) it.next();
411
412 b.append( "| .---" + cr + "| | AugmentedStmt " + as.toString() + cr + "| |" + cr + "| | preds:");
413
414 Iterator pit = as.cpreds.iterator();
415 while (pit.hasNext()) {
416 AugmentedStmt pas = (AugmentedStmt) pit.next();
417
418 b.append( " " + pas.toString());
419 }
420
421 b.append( cr + "| |" + cr + "| | succs:");
422 Iterator sit = as.csuccs.iterator();
423 while (sit.hasNext()) {
424 AugmentedStmt sas = (AugmentedStmt) sit.next();
425
426 b.append( " " + sas.toString());
427 }
428
429 b.append( cr + "| |" + cr + "| | doms:");
430 Iterator dit = as.get_Dominators().iterator();
431 while (dit.hasNext()) {
432 AugmentedStmt das = (AugmentedStmt) dit.next();
433
434 b.append( " " + das.toString());
435 }
436
437 b.append( cr + "| `---" + cr);
438 }
439
440 b.append( "-" + cr);
441 return b.toString();
442 }
443
444
445 private void mirror_PredsSuccs( AugmentedStmt as, UnitGraph ug)
446 {
447 Stmt s = as.get_Stmt();
448
449 LinkedList
450 preds = new LinkedList(),
451 succs = new LinkedList();
452
453 Iterator pit = ug.getPredsOf( s).iterator();
455 while (pit.hasNext()) {
456 Object po = get_AugStmt( (Stmt) pit.next());
457 if (preds.contains( po) == false)
458 preds.add( po);
459 }
460
461 Iterator sit = ug.getSuccsOf( s).iterator();
463 while (sit.hasNext()) {
464 Object so = get_AugStmt( (Stmt) sit.next());
465 if (succs.contains( so) == false)
466 succs.add( so);
467 }
468
469 if (ug instanceof BriefUnitGraph) {
471 as.bpreds = preds;
472 as.bsuccs = succs;
473
474 if (preds.size() == 0)
475 bheads.add( as);
476 if (succs.size() == 0)
477 btails.add( as);
478 }
479 else if (ug instanceof TrapUnitGraph) {
480 as.cpreds = preds;
481 as.csuccs = succs;
482
483 if (preds.size() == 0)
484 cheads.add( as);
485 if (succs.size() == 0)
486 ctails.add( as);
487 }
488 else throw new RuntimeException ( "Unknown UnitGraph type: " + ug.getClass());
489 }
490
491
492 public IterableSet clone_Body( IterableSet oldBody)
493 {
494 HashMap
495 old2new = new HashMap(),
496 new2old = new HashMap();
497
498 IterableSet newBody = new IterableSet();
499
500 Iterator it = oldBody.iterator();
501 while (it.hasNext()) {
502 AugmentedStmt as = (AugmentedStmt) it.next();
503 AugmentedStmt clone = (AugmentedStmt) as.clone();
504
505 original2clone.put( as, clone);
506
507 old2new.put( as, clone);
508 new2old.put( clone, as);
509 newBody.add( clone);
510 }
511
512 it = newBody.iterator();
513 while (it.hasNext()) {
514 AugmentedStmt newAs = (AugmentedStmt) it.next();
515 AugmentedStmt oldAs = (AugmentedStmt) new2old.get( newAs);
516
517 mirror_PredsSuccs( oldAs, oldAs.bpreds, newAs.bpreds, old2new);
518 mirror_PredsSuccs( oldAs, oldAs.cpreds, newAs.cpreds, old2new);
519 mirror_PredsSuccs( oldAs, oldAs.bsuccs, newAs.bsuccs, old2new);
520 mirror_PredsSuccs( oldAs, oldAs.csuccs, newAs.csuccs, old2new);
521 }
522
523 it = newBody.iterator();
524 while (it.hasNext())
525 add_AugmentedStmt( (AugmentedStmt) it.next());
526
527 HashMap so2n = new HashMap();
528
529 it = oldBody.iterator();
530 while (it.hasNext()) {
531 AugmentedStmt as = (AugmentedStmt) it.next();
532
533 Stmt os = as.get_Stmt();
534 Stmt ns = ((AugmentedStmt) old2new.get( as)).get_Stmt();
535
536 so2n.put( os, ns);
537 }
538
539 it = newBody.iterator();
540 while (it.hasNext()) {
541 AugmentedStmt nas = (AugmentedStmt) it.next();
542 AugmentedStmt oas = (AugmentedStmt) new2old.get( nas);
543
544 Stmt
545 ns = nas.get_Stmt(),
546 os = oas.get_Stmt();
547
548 if (os instanceof IfStmt) {
549 Unit
550 target = ((IfStmt) os).getTarget(),
551 newTgt = null;
552
553 if ((newTgt = (Unit) so2n.get( target)) != null)
554 ((IfStmt) ns).setTarget( newTgt);
555 else
556 ((IfStmt) ns).setTarget( target);
557 }
558
559 else if (os instanceof TableSwitchStmt) {
560 TableSwitchStmt
561 otss = (TableSwitchStmt) os,
562 ntss = (TableSwitchStmt) ns;
563
564 Unit
565 target = otss.getDefaultTarget(),
566 newTgt = null;
567
568 if ((newTgt = (Unit) so2n.get( target)) != null)
569 ntss.setDefaultTarget( newTgt);
570 else
571 ntss.setDefaultTarget( target);
572
573 LinkedList new_target_list = new LinkedList();
574
575 int target_count = otss.getHighIndex() - otss.getLowIndex() + 1;
576 for (int i=0; i<target_count; i++) {
577 target = otss.getTarget(i);
578 newTgt = null;
579
580 if ((newTgt = (Unit) so2n.get( target)) != null)
581 new_target_list.add( newTgt);
582 else
583 new_target_list.add( target);
584 }
585 ntss.setTargets( new_target_list);
586 }
587
588 else if (os instanceof LookupSwitchStmt) {
589 LookupSwitchStmt
590 olss = (LookupSwitchStmt) os,
591 nlss = (LookupSwitchStmt) ns;
592
593 Unit
594 target = olss.getDefaultTarget(),
595 newTgt = null;
596
597 if ((newTgt = (Unit) so2n.get( target)) != null)
598 nlss.setDefaultTarget( newTgt);
599 else
600 nlss.setDefaultTarget( target);
601
602 Unit[] new_target_list = new Unit[ olss.getTargetCount()];
603
604 for (int i=0; i<new_target_list.length; i++) {
605 target = olss.getTarget(i);
606 newTgt = null;
607
608 if ((newTgt = (Unit) so2n.get( target)) != null)
609 new_target_list[i] = newTgt;
610 else
611 new_target_list[i] = target;
612 }
613 nlss.setTargets( new_target_list);
614 nlss.setLookupValues( olss.getLookupValues());
615 }
616 }
617
618 return newBody;
619 }
620
621 private void mirror_PredsSuccs( AugmentedStmt originalAs, List oldList, List newList, Map old2new)
622 {
623 Iterator it = oldList.iterator();
624 while (it.hasNext()) {
625 AugmentedStmt oldAs = (AugmentedStmt) it.next();
626 AugmentedStmt newAs = (AugmentedStmt) old2new.get( oldAs);
627
628 if (newAs != null)
629 newList.add( newAs);
630
631 else {
632 newList.add( oldAs);
633
634 AugmentedStmt clonedAs = (AugmentedStmt) old2new.get( originalAs);
635
636 if (oldList == originalAs.bpreds)
637 oldAs.bsuccs.add( clonedAs);
638 else if (oldList == originalAs.cpreds)
639 oldAs.csuccs.add( clonedAs);
640 else if (oldList == originalAs.bsuccs)
641 oldAs.bpreds.add( clonedAs);
642 else if (oldList == originalAs.csuccs)
643 oldAs.cpreds.add( clonedAs);
644 else
645 throw new RuntimeException ( "Error mirroring preds and succs in Try block splitting.");
646 }
647 }
648 }
649
650
651 public void find_Dominators()
652 {
653 Iterator asgit = aug_list.iterator();
655 while (asgit.hasNext()) {
656 AugmentedStmt as = (AugmentedStmt) asgit.next();
657
658 if (as.cpreds.size() != 0) {
662
663 if (as.get_Dominators().isEmpty() == false)
664 as.get_Dominators().clear();
665
666 as.get_Dominators().addAll( aug_list);
667 }
668 else
669 as.get_Dominators().clear();
670 }
671
672 IterableSet worklist = new IterableSet();
674 worklist.addAll( aug_list);
675
676 while (worklist.isEmpty() == false) {
678 AugmentedStmt as = (AugmentedStmt) worklist.getFirst();
679 worklist.removeFirst();
680
681 IterableSet pred_intersection = new IterableSet();
682 boolean first_pred = true;
683
684 Iterator pit = as.cpreds.iterator();
686 while (pit.hasNext()) {
687 AugmentedStmt pas = (AugmentedStmt) pit.next();
688
689 if (first_pred) {
691 pred_intersection.addAll( pas.get_Dominators());
692 if (pred_intersection.contains( pas) == false)
693 pred_intersection.add( pas);
694 first_pred = false;
695 }
696
697 else {
699 Iterator piit = pred_intersection.snapshotIterator();
700 while (piit.hasNext()) {
701 AugmentedStmt pid = (AugmentedStmt) piit.next();
702
703 if ((pas.get_Dominators().contains( pid) == false) && (pas != pid))
704 pred_intersection.remove( pid);
705 }
706 }
707 }
708
709 if (as.get_Dominators().equals( pred_intersection) == false) {
711 Iterator sit = as.csuccs.iterator();
712 while (sit.hasNext()) {
713 Object o = sit.next();
714
715 if (worklist.contains( o) == false)
716 worklist.add( o);
717 }
718
719 as.get_Dominators().clear();
720 as.get_Dominators().addAll( pred_intersection);
721 }
722 }
723 }
724 }
725 |
Popular Tags |
Java API By Example, From Geeks To Geeks.