KickJava   Java API By Example, From Geeks To Geeks.

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


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 LoopInvariantFinder extends BodyTransformer {
30
31     private UnitGraph g;
32     private ArrayList constants;
33
34     public LoopInvariantFinder(Singletons.Global g){}
35     public static LoopInvariantFinder v() { return G.v().soot_jimple_toolkits_annotation_logic_LoopInvariantFinder();}
36
37     /**
38      * this one uses the side effect tester
39      */
40     protected void internalTransform (Body b, String JavaDoc phaseName, Map options){
41    
42         UnitGraph g = new ExceptionalUnitGraph(b);
43         LocalDefs sld = new SmartLocalDefs(g, new SimpleLiveLocals(g));
44         NaiveSideEffectTester nset = new NaiveSideEffectTester();
45         
46         LoopFinder lf = new LoopFinder();
47         lf.internalTransform(b, phaseName, options);
48
49         HashMap loops = lf.loops();
50         constants = new ArrayList();
51         
52         // no loop invariants if no loops
53 if (loops.isEmpty()) return;
54         
55         Iterator hIt = loops.keySet().iterator();
56         while (hIt.hasNext()){
57             Stmt header = (Stmt)hIt.next();
58             List loopStmts = (List)loops.get(header);
59             Iterator bIt = loopStmts.iterator();
60             while (bIt.hasNext()){
61                 Stmt tStmt = (Stmt)bIt.next();
62                 //System.out.println("will test stmt: "+tStmt+" for loop header: "+header);
63 //System.out.println("will test with loop stmts: "+loopStmts);
64 handleLoopBodyStmt(tStmt, nset, loopStmts);
65             }
66         }
67     }
68
69     private void handleLoopBodyStmt(Stmt s, NaiveSideEffectTester nset, List loopStmts){
70         // need to do some checks for arrays - when there is an multi-dim array
71 // --> for defs there is a get of one of the dims that claims to be
72 // loop invariant
73
74         // handle constants
75 if (s instanceof DefinitionStmt) {
76             DefinitionStmt ds = (DefinitionStmt)s;
77             if (ds.getLeftOp() instanceof Local && ds.getRightOp() instanceof Constant){
78                 if (!constants.contains(ds.getLeftOp())){
79                     constants.add(ds.getLeftOp());
80                 }
81                 else {
82                     constants.remove(ds.getLeftOp());
83                 }
84             }
85         }
86         
87         // ignore goto stmts
88 if (s instanceof GotoStmt) return;
89
90         // ignore invoke stmts
91 if (s instanceof InvokeStmt) return;
92        
93         G.v().out.println("s : "+s+" use boxes: "+s.getUseBoxes()+" def boxes: "+s.getDefBoxes());
94         // just use boxes here
95 Iterator useBoxesIt = s.getUseBoxes().iterator();
96         boolean result = true;
97         uses: while (useBoxesIt.hasNext()){
98             ValueBox vb = (ValueBox)useBoxesIt.next();
99             Value v = vb.getValue();
100             //System.out.println("next vb: "+v+" is a: "+vb.getClass());
101 //System.out.println("next vb: "+v+" class is a: "+v.getClass());
102 // new's are not invariant
103 if (v instanceof NewExpr) {
104                 result = false;
105                 G.v().out.println("break uses: due to new expr");
106                 break uses;
107             }
108             // invokes are not invariant
109 if (v instanceof InvokeExpr) {
110                 result = false;
111                 G.v().out.println("break uses: due to invoke expr");
112                 break uses;
113             }
114             // side effect tester doesn't handle expr
115 if (v instanceof Expr) continue;
116             
117             G.v().out.println("test: "+v+" of kind: "+v.getClass());
118             Iterator loopStmtsIt = loopStmts.iterator();
119             while (loopStmtsIt.hasNext()){
120                 Stmt next = (Stmt)loopStmtsIt.next();
121                 if (nset.unitCanWriteTo(next, v)){
122                     if (!isConstant(next)){
123                         G.v().out.println("result = false unit can be written to by: "+next);
124                         result = false;
125                         break uses;
126                     }
127                 }
128             }
129             
130         }
131
132         Iterator defBoxesIt = s.getDefBoxes().iterator();
133         defs: while (defBoxesIt.hasNext()){
134             ValueBox vb = (ValueBox)defBoxesIt.next();
135             Value v = vb.getValue();
136             // new's are not invariant
137 if (v instanceof NewExpr) {
138                 result = false;
139                 G.v().out.println("break defs due to new");
140                 break defs;
141             }
142             // invokes are not invariant
143 if (v instanceof InvokeExpr) {
144                 result = false;
145                 G.v().out.println("break defs due to invoke");
146                 break defs;
147             }
148             // side effect tester doesn't handle expr
149 if (v instanceof Expr) continue;
150             
151             G.v().out.println("test: "+v+" of kind: "+v.getClass());
152         
153             Iterator loopStmtsIt = loopStmts.iterator();
154             while (loopStmtsIt.hasNext()){
155                 Stmt next = (Stmt)loopStmtsIt.next();
156                 if (next.equals(s)) continue;
157                 if (nset.unitCanWriteTo(next, v)){
158                     if (!isConstant(next)){
159                         G.v().out.println("result false: unit can be written to by: "+next);
160                         result = false;
161                         break defs;
162                     }
163                 }
164             }
165             
166         }
167         G.v().out.println("stmt: "+s+" result: "+result);
168         if (result){
169             s.addTag(new LoopInvariantTag("is loop invariant"));
170             s.addTag(new ColorTag(ColorTag.RED, "Loop Invariant Analysis"));
171         }
172         else {
173             // if loops are nested it might be invariant in one of them
174 // so remove tag
175 //if (s.hasTag("LoopInvariantTag")) {
176 // s.removeTag("LoopInvariantTag");
177 //}
178 }
179     }
180     
181     private boolean isConstant(Stmt s){
182         if (s instanceof DefinitionStmt){
183             DefinitionStmt ds = (DefinitionStmt)s;
184             if (constants.contains(ds.getLeftOp())){
185                 return true;
186             }
187         }
188         return false;
189     }
190 }
191
Popular Tags