001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2004 Jennifer Lhotak
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: package soot.jimple.toolkits.annotation.logic;
021:
022: import soot.*;
023: import soot.toolkits.graph.*;
024: import soot.jimple.*;
025:
026: import java.util.*;
027:
028: import soot.toolkits.scalar.*;
029: import soot.tagkit.*;
030:
031: public class LoopInvariantFinder extends BodyTransformer {
032:
033: private ArrayList constants;
034:
035: public LoopInvariantFinder(Singletons.Global g) {
036: }
037:
038: public static LoopInvariantFinder v() {
039: return G
040: .v()
041: .soot_jimple_toolkits_annotation_logic_LoopInvariantFinder();
042: }
043:
044: /**
045: * this one uses the side effect tester
046: */
047: protected void internalTransform(Body b, String phaseName,
048: Map options) {
049:
050: UnitGraph g = new ExceptionalUnitGraph(b);
051: LocalDefs sld = new SmartLocalDefs(g, new SimpleLiveLocals(g));
052: NaiveSideEffectTester nset = new NaiveSideEffectTester();
053:
054: LoopFinder lf = new LoopFinder();
055: lf.internalTransform(b, phaseName, options);
056:
057: Collection<Loop> loops = lf.loops();
058: constants = new ArrayList();
059:
060: // no loop invariants if no loops
061: if (loops.isEmpty())
062: return;
063:
064: Iterator<Loop> lIt = loops.iterator();
065: while (lIt.hasNext()) {
066: Loop loop = lIt.next();
067: Stmt header = loop.getHead();
068: Collection<Stmt> loopStmts = loop.getLoopStatements();
069: Iterator<Stmt> bIt = loopStmts.iterator();
070: while (bIt.hasNext()) {
071: Stmt tStmt = bIt.next();
072: //System.out.println("will test stmt: "+tStmt+" for loop header: "+header);
073: //System.out.println("will test with loop stmts: "+loopStmts);
074: handleLoopBodyStmt(tStmt, nset, loopStmts);
075: }
076: }
077: }
078:
079: private void handleLoopBodyStmt(Stmt s, NaiveSideEffectTester nset,
080: Collection<Stmt> loopStmts) {
081: // need to do some checks for arrays - when there is an multi-dim array
082: // --> for defs there is a get of one of the dims that claims to be
083: // loop invariant
084:
085: // handle constants
086: if (s instanceof DefinitionStmt) {
087: DefinitionStmt ds = (DefinitionStmt) s;
088: if (ds.getLeftOp() instanceof Local
089: && ds.getRightOp() instanceof Constant) {
090: if (!constants.contains(ds.getLeftOp())) {
091: constants.add(ds.getLeftOp());
092: } else {
093: constants.remove(ds.getLeftOp());
094: }
095: }
096: }
097:
098: // ignore goto stmts
099: if (s instanceof GotoStmt)
100: return;
101:
102: // ignore invoke stmts
103: if (s instanceof InvokeStmt)
104: return;
105:
106: G.v().out.println("s : " + s + " use boxes: " + s.getUseBoxes()
107: + " def boxes: " + s.getDefBoxes());
108: // just use boxes here
109: Iterator useBoxesIt = s.getUseBoxes().iterator();
110: boolean result = true;
111: uses: while (useBoxesIt.hasNext()) {
112: ValueBox vb = (ValueBox) useBoxesIt.next();
113: Value v = vb.getValue();
114: //System.out.println("next vb: "+v+" is a: "+vb.getClass());
115: //System.out.println("next vb: "+v+" class is a: "+v.getClass());
116: // new's are not invariant
117: if (v instanceof NewExpr) {
118: result = false;
119: G.v().out.println("break uses: due to new expr");
120: break uses;
121: }
122: // invokes are not invariant
123: if (v instanceof InvokeExpr) {
124: result = false;
125: G.v().out.println("break uses: due to invoke expr");
126: break uses;
127: }
128: // side effect tester doesn't handle expr
129: if (v instanceof Expr)
130: continue;
131:
132: G.v().out.println("test: " + v + " of kind: "
133: + v.getClass());
134: Iterator loopStmtsIt = loopStmts.iterator();
135: while (loopStmtsIt.hasNext()) {
136: Stmt next = (Stmt) loopStmtsIt.next();
137: if (nset.unitCanWriteTo(next, v)) {
138: if (!isConstant(next)) {
139: G.v().out
140: .println("result = false unit can be written to by: "
141: + next);
142: result = false;
143: break uses;
144: }
145: }
146: }
147:
148: }
149:
150: Iterator defBoxesIt = s.getDefBoxes().iterator();
151: defs: while (defBoxesIt.hasNext()) {
152: ValueBox vb = (ValueBox) defBoxesIt.next();
153: Value v = vb.getValue();
154: // new's are not invariant
155: if (v instanceof NewExpr) {
156: result = false;
157: G.v().out.println("break defs due to new");
158: break defs;
159: }
160: // invokes are not invariant
161: if (v instanceof InvokeExpr) {
162: result = false;
163: G.v().out.println("break defs due to invoke");
164: break defs;
165: }
166: // side effect tester doesn't handle expr
167: if (v instanceof Expr)
168: continue;
169:
170: G.v().out.println("test: " + v + " of kind: "
171: + v.getClass());
172:
173: Iterator loopStmtsIt = loopStmts.iterator();
174: while (loopStmtsIt.hasNext()) {
175: Stmt next = (Stmt) loopStmtsIt.next();
176: if (next.equals(s))
177: continue;
178: if (nset.unitCanWriteTo(next, v)) {
179: if (!isConstant(next)) {
180: G.v().out
181: .println("result false: unit can be written to by: "
182: + next);
183: result = false;
184: break defs;
185: }
186: }
187: }
188:
189: }
190: G.v().out.println("stmt: " + s + " result: " + result);
191: if (result) {
192: s.addTag(new LoopInvariantTag("is loop invariant"));
193: s.addTag(new ColorTag(ColorTag.RED,
194: "Loop Invariant Analysis"));
195: } else {
196: // if loops are nested it might be invariant in one of them
197: // so remove tag
198: //if (s.hasTag("LoopInvariantTag")) {
199: // s.removeTag("LoopInvariantTag");
200: //}
201: }
202: }
203:
204: private boolean isConstant(Stmt s) {
205: if (s instanceof DefinitionStmt) {
206: DefinitionStmt ds = (DefinitionStmt) s;
207: if (constants.contains(ds.getLeftOp())) {
208: return true;
209: }
210: }
211: return false;
212: }
213: }
|