KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > annotation > logic > LoopFinder


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2004 Jennifer Lhotak
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.jimple.toolkits.annotation.logic;
21
22 import soot.*;
23 import soot.toolkits.graph.*;
24 import soot.jimple.*;
25 import java.util.*;
26 import soot.toolkits.scalar.*;
27 import soot.tagkit.*;
28
29 public class LoopFinder extends BodyTransformer {
30
31     private UnitGraph g;
32
33     private HashMap loops;
34
35     public HashMap loops(){
36         return loops;
37     }
38     
39     protected void internalTransform (Body b, String JavaDoc phaseName, Map options){
40     
41         g = new ExceptionalUnitGraph(b);
42         DominatorAnalysis a = new DominatorAnalysis(g);
43         
44         loops = new HashMap();
45         
46         Iterator stmtsIt = b.getUnits().iterator();
47         while (stmtsIt.hasNext()){
48             Stmt s = (Stmt)stmtsIt.next();
49
50             List succs = g.getSuccsOf(s);
51             FlowSet dominators = (FlowSet)a.getFlowAfter(s);
52
53             ArrayList backEdges = new ArrayList();
54
55             Iterator succsIt = succs.iterator();
56             while (succsIt.hasNext()){
57                 Stmt succ = (Stmt)succsIt.next();
58                 if (dominators.contains(succ)){
59                     backEdges.add(succ);
60                 }
61             }
62
63             Iterator headersIt = backEdges.iterator();
64             while (headersIt.hasNext()){
65                 Stmt header = (Stmt)headersIt.next();
66                 List loopBody = getLoopBodyFor(header, s);
67
68                 // for now just print out loops as sets of stmts
69 //System.out.println("FOUND LOOP: Header: "+header+" Body: "+loopBody);
70 if (loops.containsKey(header)){
71                     // merge bodies
72 List lb1 = (List)loops.get(header);
73                     loops.put(header, union(lb1, loopBody));
74                 }
75                 else {
76                     loops.put(header, loopBody);
77                 }
78             }
79         }
80         
81         //print loops found
82 int colorId = 0;
83         Iterator printIt = loops.keySet().iterator();
84         while (printIt.hasNext()){
85             Stmt h = (Stmt)printIt.next();
86             System.out.println("FOUND LOOP: Header: "+h+" Body: "+loops.get(h));
87
88             // tag loop stmts with colors
89
90             /*Iterator bIt = ((List)loops.get(h)).iterator();
91             while (bIt.hasNext()){
92                 tagLoopStmt((Stmt)bIt.next(), colorId);
93             }*/
94
95             colorId++;
96         }
97     }
98     
99
100     private List getLoopBodyFor(Stmt header, Stmt node){
101     
102         ArrayList loopBody = new ArrayList();
103         Stack stack = new Stack();
104
105         loopBody.add(header);
106         stack.push(node);
107
108         while (!stack.isEmpty()){
109             Stmt next = (Stmt)stack.pop();
110             if (!loopBody.contains(next)){
111                 // add next to loop body
112 loopBody.add(0, next);
113                 // put all preds of next on stack
114 Iterator it = g.getPredsOf(next).iterator();
115                 while (it.hasNext()){
116                     stack.push(it.next());
117                 }
118             }
119         }
120
121         return loopBody;
122     }
123
124     private List union(List l1, List l2){
125         Iterator it = l2.iterator();
126         while (it.hasNext()){
127             Object JavaDoc next = it.next();
128             if (!l1.contains(next)){
129                 l1.add(next);
130             }
131         }
132         return l1;
133     }
134
135     private void tagLoopStmt(Stmt s, int id){
136         switch(id%5){
137             case 0: {
138                         s.addTag(new ColorTag(ColorTag.GREEN));
139                         break;
140                     }
141             case 1: {
142                         s.addTag(new ColorTag(ColorTag.RED));
143                         break;
144                     }
145             case 2: {
146                         s.addTag(new ColorTag(ColorTag.BLUE));
147                         break;
148                     }
149             case 3: {
150                         s.addTag(new ColorTag(ColorTag.YELLOW));
151                         break;
152                     }
153             case 4: {
154                         s.addTag(new ColorTag(ColorTag.ORANGE));
155                         break;
156                     }
157         
158         }
159     }
160 }
161
Popular Tags