KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > dava > internal > asg > AugmentedStmtGraph


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 Jerome Miecznikowski
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */

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     // make the augmented statements
97
Iterator it = cug.iterator();
98     while (it.hasNext()) {
99         Stmt s = (Stmt) it.next();
100         add_StmtBinding( s, new AugmentedStmt( s));
101     }
102
103     // make the list of augmented statements in pseudo topological order!
104
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     // now that we've got all the augmented statements, mirror the statement graph
112
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 JavaDoc 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 JavaDoc 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 JavaDoc( "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 JavaDoc( "Could not find augmented statement for: " + s.toString());
282
283     return as;
284     }
285
286
287     // now put in the methods to satisfy the DirectedGraph interface
288

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 JavaDoc 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 JavaDoc( "Object " + s + " class: " + s.getClass() + " not a member of this AugmentedStmtGraph");
312     }
313
314     public List getSuccsOf( Object JavaDoc 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 JavaDoc( "Object " + s + " class: " + s.getClass() + " not a member of this AugmentedStmtGraph");
322     }
323     
324     // end of methods satisfying DirectedGraph
325

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 JavaDoc 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     // NOTE: we do *NOT* touch the underlying unit graphs.
399
}
400
401     public String JavaDoc toString()
402     {
403     StringBuffer JavaDoc b = new StringBuffer JavaDoc();
404     String JavaDoc 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     // mirror the predecessors
454
Iterator pit = ug.getPredsOf( s).iterator();
455     while (pit.hasNext()) {
456         Object JavaDoc po = get_AugStmt( (Stmt) pit.next());
457         if (preds.contains( po) == false)
458         preds.add( po);
459     }
460
461     // mirror the successors
462
Iterator sit = ug.getSuccsOf( s).iterator();
463     while (sit.hasNext()) {
464         Object JavaDoc so = get_AugStmt( (Stmt) sit.next());
465         if (succs.contains( so) == false)
466         succs.add( so);
467     }
468
469     // attach the mirrors properly to the AugmentedStmt
470
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 JavaDoc( "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 JavaDoc( "Error mirroring preds and succs in Try block splitting.");
646         }
647     }
648     }
649
650
651     public void find_Dominators()
652     {
653     // set up the dominator sets for all the nodes in the graph
654
Iterator asgit = aug_list.iterator();
655     while (asgit.hasNext()) {
656         AugmentedStmt as = (AugmentedStmt) asgit.next();
657
658         // Dominators:
659
// safe starting approximation for S(0) ... empty set
660
// unsafe starting approximation for S(i) .. full set
661
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     // build the worklist
673
IterableSet worklist = new IterableSet();
674     worklist.addAll( aug_list);
675
676     // keep going until the worklist is empty
677
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         // run through all the predecessors and get their dominance intersection
685
Iterator pit = as.cpreds.iterator();
686         while (pit.hasNext()) {
687         AugmentedStmt pas = (AugmentedStmt) pit.next();
688         
689         // for the first predecessor just take all his dominators
690
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         // for the subsequent predecessors remove the ones they do not have from the intersection
698
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         // update dominance if we have a change
710
if (as.get_Dominators().equals( pred_intersection) == false) {
711         Iterator sit = as.csuccs.iterator();
712         while (sit.hasNext()) {
713             Object JavaDoc 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