Java > Open Source Codes > soot > dava > toolkits > base > finders > CycleFinder


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 /*
21  * CHANGE LOG:
22  * 26-January-2007: Fixed Bug in Dava. Could not detect empty infinte loops.
23  */
24 package soot.dava.toolkits.base.finders;
25
26 import soot.*;
27 import java.util.*;
28 import soot.dava.*;
29 import soot.util.*;
30 import soot.jimple.*;
31 import soot.grimp.internal.*;
32 import soot.toolkits.graph.*;
33 import soot.jimple.internal.*;
34 import soot.dava.internal.asg.*;
35 import soot.dava.internal.SET.*;
36 import soot.dava.internal.AST.*;
37 import soot.dava.internal.javaRep.*;
38 import soot.dava.toolkits.base.misc.*;
39
40 public class CycleFinder implements FactFinder
41 {
42     public CycleFinder( Singletons.Global g ) {}
43     public static CycleFinder v() { return G.v().soot_dava_toolkits_base_finders_CycleFinder(); }
44
45     public void find( DavaBody body, AugmentedStmtGraph asg, SETNode SET) throws RetriggerAnalysisException
46     {
47     Dava.v().log("CycleFinder::find()");
48
49         AugmentedStmtGraph wasg = (AugmentedStmtGraph) asg.clone();
50         List component_list = build_component_list( wasg);
51
52         // loop through all nestings
53 while (component_list.isEmpty() == false) {
54
55             IterableSet node_list = new IterableSet();
56             
57             // loop through all the strongly connected components
58 Iterator cit = component_list.iterator();
59             while (cit.hasNext()) {
60                 
61                 node_list.clear();
62                 node_list.addAll( (List) cit.next());
63                 //node_list contains all the nodes belonging to this SCC
64
65                 IterableSet entry_points = get_EntryPoint( node_list);
66
67         //if more than one entry points found
68 if (entry_points.size() > 1) {
69             
70             LinkedList asgEntryPoints = new LinkedList();
71             Iterator it = entry_points.iterator();
72             while (it.hasNext())
73             asgEntryPoints.addLast( asg.get_AugStmt( ((AugmentedStmt) it.next()).get_Stmt()));
74
75             IterableSet asgScc = new IterableSet();
76             it = node_list.iterator();
77             while (it.hasNext())
78             asgScc.addLast( asg.get_AugStmt( ((AugmentedStmt) it.next()).get_Stmt()));
79
80             fix_MultiEntryPoint( body, asg, asgEntryPoints, asgScc);
81             throw new RetriggerAnalysisException();
82         }
83         
84         //gets to this code only if each SCC has one entry point?
85 AugmentedStmt entry_point = (AugmentedStmt) entry_points.getFirst();
86         AugmentedStmt
87             characterizing_stmt = find_CharacterizingStmt( entry_point, node_list, wasg),
88             succ_stmt = null;
89
90         if (characterizing_stmt != null) {
91             Iterator sit = characterizing_stmt.bsuccs.iterator();
92             while (sit.hasNext()) {
93             succ_stmt = (AugmentedStmt) sit.next();
94
95             if (node_list.contains( succ_stmt) == false)
96                 break;
97             }
98         }
99
100         wasg.calculate_Reachability( succ_stmt, new HashSet(), entry_point);
101                 IterableSet cycle_body = get_CycleBody( entry_point, succ_stmt, asg, wasg);
102         
103         SETCycleNode newNode = null;
104
105         if (characterizing_stmt != null) {
106             Iterator enlit = body.get_ExceptionFacts().iterator();
107
108         checkExceptionLoop:
109             while (enlit.hasNext()) {
110             ExceptionNode en = (ExceptionNode) enlit.next();
111             IterableSet tryBody = en.get_TryBody();
112
113             if (tryBody.contains( asg.get_AugStmt( characterizing_stmt.get_Stmt()))) {
114                 Iterator cbit = cycle_body.iterator();
115                 while (cbit.hasNext()) {
116                 AugmentedStmt cbas = (AugmentedStmt) cbit.next();
117                 
118                 if (tryBody.contains( cbas) == false) {
119                     characterizing_stmt = null;
120                     break checkExceptionLoop;
121                 }
122                 }
123             }
124             }
125         }
126                 
127         /*
128             if (tryBody.contains( asg.get_AugStmt( characterizing_stmt.get_Stmt()))) {
129                         
130                 if (checkExceptionNodes.contains( en) == false)
131                 checkExceptionNodes.add( en);
132                 
133                 Iterator cbit = cycle_body.snapshotIterator();
134                 while (cbit.hasNext()) {
135                 AugmentedStmt cbas = (AugmentedStmt) cbit.next();
136                 
137                 if (tryBody.contains( cbas) == false)
138                     cycle_body.remove( cbas);
139                 }
140             }
141             }
142
143             enlit = checkExceptionNodes.iterator();
144         exceptionNestingLoop:
145             while (enlit.hasNext()) {
146             ExceptionNode en = (ExceptionNode) enlit.next();
147
148             Iterator cbit = cycle_body.iterator();
149             while (cbit.hasNext()) {
150                 AugmentedStmt cbas = (AugmentedStmt) cbit.next();
151                 
152                 if (en.get_TryBody().contains( cbas) == false) {
153                 characterizing_stmt = null;
154                 break exceptionNestingLoop;
155                 }
156             }
157             }
158         }
159         */
160
161         // unconditional loop
162 if (characterizing_stmt == null) {
163             wasg.remove_AugmentedStmt( entry_point);
164             newNode = new SETUnconditionalWhileNode( cycle_body);
165         }
166         
167         else {
168             body.consume_Condition( asg.get_AugStmt( characterizing_stmt.get_Stmt()));
169             wasg.remove_AugmentedStmt( characterizing_stmt);
170
171             IfStmt condition = (IfStmt) characterizing_stmt.get_Stmt();
172             if ( cycle_body.contains( asg.get_AugStmt( condition.getTarget())) == false)
173             condition.setCondition( ConditionFlipper.flip((ConditionExpr) condition.getCondition()));
174
175             if (characterizing_stmt == entry_point)
176             newNode = new SETWhileNode( asg.get_AugStmt( characterizing_stmt.get_Stmt()), cycle_body);
177             else
178             newNode = new SETDoWhileNode( asg.get_AugStmt( characterizing_stmt.get_Stmt()), asg.get_AugStmt( entry_point.get_Stmt()), cycle_body);
179         }
180
181         if (newNode != null)
182             SET.nest( newNode);
183         }
184
185         component_list = build_component_list( wasg);
186     }
187     }
188
189     /*
190      * Nomair A. Naeem Entry point to a SCC ARE those stmts whose predecessor
191      * does not belong to the SCC
192      */
193     private IterableSet get_EntryPoint( IterableSet nodeList){
194     IterableSet entryPoints = new IterableSet();
195
196     Iterator it = nodeList.iterator();
197     while (it.hasNext()) {
198         AugmentedStmt as = (AugmentedStmt) it.next();
199
200         Iterator pit = as.cpreds.iterator();
201         while (pit.hasNext()) {
202         Object po = pit.next();
203
204         if (nodeList.contains( po) == false) {
205             entryPoints.add( as);
206             break;
207         }
208         }
209     }
210
211     return entryPoints;
212     }
213
214
215     private List build_component_list( AugmentedStmtGraph asg){
216         List c_list = new LinkedList();
217
218         StronglyConnectedComponents scc = new StronglyConnectedComponents( asg);
219
220     //makes sure that all scc's with only one statement in them are removed
221 /*
222       26th Jan 2006 Nomair A. Naeem
223       This could be potentially bad since self loops will also get removed
224       Adding code to check for self loop (a stmt is a self loop if its pred and succ
225       contain the stmt itself
226     */
227         Iterator scomit = scc.getComponents().iterator();
228     while (scomit.hasNext()) {
229         List wcomp = (List) scomit.next();
230         if (wcomp.size() > 1)
231         c_list.add( wcomp);
232         else if (wcomp.size()==1){
233         //this is a scc of one augmented stmt
234 //We should add those which are self loops
235 AugmentedStmt as = (AugmentedStmt)wcomp.get(0);
236       
237         if(as.cpreds.contains(as) && (as.csuccs.contains(as))){
238             //"as" has a predecssor and successor which is as i.e. it is a self loop
239
240             List currentComponent = null;
241             currentComponent = new StationaryArrayList();
242             currentComponent.add(as);
243             //System.out.println("Special add of"+as);
244 c_list.add(currentComponent);
245         }
246         }
247     }
248     return c_list;
249     }
250
251     private AugmentedStmt find_CharacterizingStmt( AugmentedStmt entry_point, IterableSet sc_component, AugmentedStmtGraph asg)
252     {
253     /*
254      * Check whether we are a while loop.
255      */
256
257         if (entry_point.get_Stmt() instanceof IfStmt) {
258         
259             // see if there's a successor who's not in the strict loop set
260 Iterator sit = entry_point.bsuccs.iterator();
261             while (sit.hasNext())
262                 if (sc_component.contains( sit.next()) == false)
263                     return entry_point;
264         }
265
266
267     /*
268      * We're not a while loop. Get the candidates for condition on a do-while loop.
269      */
270
271
272         IterableSet candidates = new IterableSet();
273     HashMap candSuccMap = new HashMap();
274     HashSet blockers = new HashSet();
275
276     // Get the set of all candidates.
277 Iterator pit = entry_point.bpreds.iterator();
278         while (pit.hasNext()) {
279             AugmentedStmt pas = (AugmentedStmt) pit.next();
280         
281         if ((pas.get_Stmt() instanceof GotoStmt) && (pas.bpreds.size() == 1))
282         pas = (AugmentedStmt) pas.bpreds.get(0);
283                 
284         if ((sc_component.contains( pas)) && (pas.get_Stmt() instanceof IfStmt)) {
285
286         Iterator spasit = pas.bsuccs.iterator();
287         while (spasit.hasNext()) {
288             AugmentedStmt spas = (AugmentedStmt) spasit.next();
289
290             if (sc_component.contains( spas) == false) {
291
292             candidates.add( pas);
293             candSuccMap.put( pas, spas);
294             blockers.add( spas);
295
296             break;
297             }
298         }
299         }
300     }
301     
302
303     /*
304      * If there was no candidate, we are an unconditional loop.
305      */
306
307     if (candidates.isEmpty())
308         return null;
309
310     
311     /*
312      * Get the best candidate for the do-while condition.
313      */
314     
315     if (candidates.size() == 1)
316         return (AugmentedStmt) candidates.getFirst();
317     
318     
319     // Take the candidate(s) whose successor has maximal reachability from all candidates.
320
321     asg.calculate_Reachability( candidates, blockers, entry_point);
322
323     IterableSet max_Reach_Set = null;
324     int reachSize = 0;
325     
326     Iterator candit = candidates.iterator();
327     while (candit.hasNext()) {
328         AugmentedStmt as = (AugmentedStmt) candit.next();
329         
330         int current_reach_size = ((AugmentedStmt) candSuccMap.get( as)).get_Reachers().intersection( candidates).size();
331         
332         if (current_reach_size > reachSize) {
333         max_Reach_Set = new IterableSet();
334         reachSize = current_reach_size;
335         }
336         
337         if (current_reach_size == reachSize)
338         max_Reach_Set.add( as);
339     }
340     
341     candidates = max_Reach_Set;
342     
343     if (candidates.size() == 1)
344         return (AugmentedStmt) candidates.getFirst();
345     
346
347     
348     // Find a single source shortest path from the entry point to any of the remaining candidates.
349
350     HashSet touchSet = new HashSet();
351     LinkedList worklist = new LinkedList();
352     worklist.addLast( entry_point);
353     touchSet.add( entry_point);
354     
355     while (worklist.isEmpty() == false) {
356
357         Iterator sit = ((AugmentedStmt) worklist.removeFirst()).csuccs.iterator();
358         while (sit.hasNext()) {
359         Object so = sit.next();
360
361         if (candidates.contains( so))
362             return (AugmentedStmt) so;
363
364         if ((sc_component.contains( so)) && (touchSet.contains( so) == false)) {
365             worklist.addLast( so);
366             touchSet.add( so);
367         }
368         }
369     }
370     
371     
372     throw new RuntimeException ( "Somehow didn't find a condition for a do-while loop!");
373     }
374     
375     private IterableSet get_CycleBody( AugmentedStmt entry_point, AugmentedStmt boundary_stmt, AugmentedStmtGraph asg, AugmentedStmtGraph wasg)
376     {
377     IterableSet cycle_body = new IterableSet();
378     LinkedList worklist = new LinkedList();
379     AugmentedStmt asg_ep = asg.get_AugStmt( entry_point.get_Stmt());
380
381     worklist.add( entry_point);
382     cycle_body.add( asg_ep);
383
384     while (worklist.isEmpty() == false) {
385         AugmentedStmt as = (AugmentedStmt) worklist.removeFirst();
386
387         Iterator sit = as.csuccs.iterator();
388         while (sit.hasNext()) {
389         AugmentedStmt wsas = (AugmentedStmt) sit.next();
390         AugmentedStmt sas = asg.get_AugStmt( wsas.get_Stmt());
391
392
393
394         if (cycle_body.contains( sas))
395             continue;
396
397         /*
398         if (sas.get_Dominators().contains( asg_ep) == false) {
399             G.v().out.println( wsas + " not dominated by " + asg_ep);
400             G.v().out.println( "doms");
401             Iterator dit = sas.get_Dominators().iterator();
402             while (dit.hasNext())
403             G.v().out.println( " " + dit.next());
404             G.v().out.println("preds");
405             dit = sas.cpreds.iterator();
406             while (dit.hasNext())
407             G.v().out.println( " " + dit.next());
408         }
409         */
410
411         if ((cycle_body.contains( sas) == false) && (sas.get_Dominators().contains( asg_ep))) {
412
413             if ((boundary_stmt != null) &&
414             ((wsas.get_Reachers().contains( boundary_stmt)) || (wsas == boundary_stmt)))
415             
416             continue;
417
418             // G.v().out.println( sas);
419
420             worklist.add( wsas);
421             cycle_body.add( sas);
422         }
423         }
424     }
425     
426     return cycle_body;
427     }
428
429
430     private void fix_MultiEntryPoint( DavaBody body, AugmentedStmtGraph asg, LinkedList entry_points, IterableSet scc)
431     {
432     AugmentedStmt naturalEntryPoint = get_NaturalEntryPoint( entry_points, scc);
433     Local controlLocal = body.get_ControlLocal();
434     
435     Unit defaultTarget = (Unit) naturalEntryPoint.get_Stmt();
436     LinkedList targets = new LinkedList();
437     
438     TableSwitchStmt tss = new GTableSwitchStmt( controlLocal, 0, entry_points.size() - 2, targets, defaultTarget);
439     AugmentedStmt dispatchStmt = new AugmentedStmt( tss);
440
441     IterableSet
442         predecessorSet = new IterableSet(),
443         indirectionStmtSet = new IterableSet(),
444         directionStmtSet = new IterableSet();
445     
446     int count = 0;
447     Iterator epit = entry_points.iterator();
448     while (epit.hasNext()) {
449         AugmentedStmt entryPoint = (AugmentedStmt) epit.next();
450     
451         GotoStmt gotoStmt = new JGotoStmt( entryPoint.get_Stmt());
452         AugmentedStmt indirectionStmt = new AugmentedStmt( gotoStmt);
453
454         indirectionStmtSet.add( indirectionStmt);
455         
456         tss.setTarget( count++, gotoStmt);
457     
458         dispatchStmt.add_BSucc( indirectionStmt);
459         indirectionStmt.add_BPred( dispatchStmt);
460         indirectionStmt.add_BSucc( entryPoint);
461         entryPoint.add_BPred( indirectionStmt);
462
463         asg.add_AugmentedStmt( indirectionStmt);
464
465         LinkedList toRemove = new LinkedList();
466
467         Iterator pit = entryPoint.cpreds.iterator();
468         while (pit.hasNext()) {
469         AugmentedStmt pas = (AugmentedStmt) pit.next();
470         
471         if ((pas == indirectionStmt) || ((entryPoint != naturalEntryPoint) && (scc.contains( pas))))
472             continue;
473
474         if (scc.contains( pas) == false)
475             predecessorSet.add( pas);
476
477         AssignStmt asnStmt = new GAssignStmt( controlLocal, DIntConstant.v( count, null));
478         AugmentedStmt directionStmt = new AugmentedStmt( asnStmt);
479
480         directionStmtSet.add( directionStmt);
481         
482         patch_Stmt( pas.get_Stmt(), entryPoint.get_Stmt(), asnStmt);
483
484         // Mark the original predecessor to be removed.
485 toRemove.addLast( pas);
486
487         pas.csuccs.remove( entryPoint);
488         pas.csuccs.add( directionStmt);
489         if (pas.bsuccs.contains( entryPoint)) {
490             pas.bsuccs.remove( entryPoint);
491             pas.bsuccs.add( directionStmt);
492         }
493         
494         directionStmt.cpreds.add( pas);
495         if (pas.bsuccs.contains( directionStmt))
496             directionStmt.bpreds.add( pas);
497
498         directionStmt.add_BSucc( dispatchStmt);
499         dispatchStmt.add_BPred( directionStmt);
500         
501         asg.add_AugmentedStmt( directionStmt);
502         }
503
504         Iterator trit = toRemove.iterator();
505         while (trit.hasNext()) {
506         AugmentedStmt ras = (AugmentedStmt) trit.next();
507
508         entryPoint.cpreds.remove( ras);
509         if (entryPoint.bpreds.contains( ras))
510             entryPoint.bpreds.remove( ras);
511         }
512     }
513
514     asg.add_AugmentedStmt( dispatchStmt);
515
516
517     Iterator efit = body.get_ExceptionFacts().iterator();
518
519     exceptionFactLoop:
520     while (efit.hasNext()) {
521         ExceptionNode en = (ExceptionNode) efit.next();
522         IterableSet tryBody = en.get_TryBody();
523
524         epit = entry_points.iterator();
525         while (epit.hasNext())
526         if (tryBody.contains( epit.next()) == false)
527             continue exceptionFactLoop;
528
529         en.add_TryStmts( indirectionStmtSet);
530         en.add_TryStmt( dispatchStmt);
531         
532         Iterator pit = predecessorSet.iterator();
533         while (pit.hasNext())
534         if (tryBody.contains( pit.next()) == false)
535             continue exceptionFactLoop;
536
537         en.add_TryStmts( directionStmtSet);
538     }
539     }
540
541     private AugmentedStmt get_NaturalEntryPoint( LinkedList entry_points, IterableSet scc)
542     {
543     AugmentedStmt best_candidate = null;
544     int minScore = 0;
545
546     Iterator epit = entry_points.iterator();
547     while (epit.hasNext()) {
548         AugmentedStmt entryPoint = (AugmentedStmt) epit.next();
549         HashSet
550         touchSet = new HashSet(),
551         backTargets = new HashSet();
552
553         touchSet.add( entryPoint);
554         DFS( entryPoint, touchSet, backTargets, scc);
555
556         if ((best_candidate == null) || (backTargets.size() < minScore)) {
557         minScore = touchSet.size();
558         best_candidate = entryPoint;
559         }
560     }
561
562     return best_candidate;
563     }
564     
565     private void DFS( AugmentedStmt as, HashSet touchSet, HashSet backTargets, IterableSet scc)
566     {
567     Iterator sit = as.csuccs.iterator();
568     while (sit.hasNext()) {
569         AugmentedStmt sas = (AugmentedStmt) sit.next();
570
571         if (scc.contains( sas) == false)
572         continue;
573
574         if (touchSet.contains( sas)) {
575         if (backTargets.contains( sas) == false)
576             backTargets.add( sas);
577         }
578         else {
579         touchSet.add( sas);
580         DFS( sas, touchSet, backTargets, scc);
581         touchSet.remove( sas);
582         }
583     }
584     }
585
586     private void patch_Stmt( Stmt src, Stmt oldDst, Stmt newDst)
587     {
588     if (src instanceof GotoStmt) {
589         ((GotoStmt) src).setTarget( newDst);
590         return;
591     }
592
593     if (src instanceof IfStmt) {
594         IfStmt ifs = (IfStmt) src;
595
596         if (ifs.getTarget() == oldDst)
597         ifs.setTarget( newDst);
598
599         return;
600     }
601
602     if (src instanceof TableSwitchStmt) {
603         TableSwitchStmt tss = (TableSwitchStmt) src;
604         
605         if (tss.getDefaultTarget() == oldDst) {
606         tss.setDefaultTarget( newDst);
607         return;
608         }
609
610         for (int i = tss.getLowIndex(); i <= tss.getHighIndex(); i++)
611         if (tss.getTarget( i) == oldDst) {
612             tss.setTarget( i, newDst);
613             return;
614         }
615     }
616
617     if (src instanceof LookupSwitchStmt) {
618         LookupSwitchStmt lss = (LookupSwitchStmt) src;
619
620         if (lss.getDefaultTarget() == oldDst) {
621         lss.setDefaultTarget( newDst);
622         return;
623         }
624
625         for (int i = 0; i < lss.getTargetCount(); i++)
626         if (lss.getTarget( i) == oldDst) {
627             lss.setTarget( i, newDst);
628             return;
629         }
630     }
631     }
632 }
633

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags