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 java.util.ArrayList;
023: import java.util.Collection;
024: import java.util.HashMap;
025: import java.util.HashSet;
026: import java.util.Iterator;
027: import java.util.List;
028: import java.util.Map;
029: import java.util.Stack;
030:
031: import soot.Body;
032: import soot.BodyTransformer;
033: import soot.Unit;
034: import soot.jimple.Stmt;
035: import soot.toolkits.graph.ExceptionalUnitGraph;
036: import soot.toolkits.graph.MHGDominatorsFinder;
037: import soot.toolkits.graph.UnitGraph;
038:
039: public class LoopFinder extends BodyTransformer {
040:
041: private UnitGraph g;
042:
043: private HashMap<Stmt, List<Stmt>> loops;
044:
045: public Collection<Loop> loops() {
046: Collection<Loop> result = new HashSet<Loop>();
047: for (Map.Entry<Stmt, List<Stmt>> entry : loops.entrySet()) {
048: result.add(new Loop(entry.getKey(), entry.getValue(), g));
049: }
050: return result;
051: }
052:
053: protected void internalTransform(Body b, String phaseName,
054: Map options) {
055:
056: g = new ExceptionalUnitGraph(b);
057: MHGDominatorsFinder a = new MHGDominatorsFinder(g);
058:
059: loops = new HashMap<Stmt, List<Stmt>>();
060:
061: Iterator<Unit> stmtsIt = b.getUnits().iterator();
062: while (stmtsIt.hasNext()) {
063: Stmt s = (Stmt) stmtsIt.next();
064:
065: List<Unit> succs = g.getSuccsOf(s);
066: Collection<Unit> dominaters = (Collection<Unit>) a
067: .getDominators(s);
068:
069: ArrayList<Stmt> headers = new ArrayList<Stmt>();
070:
071: Iterator<Unit> succsIt = succs.iterator();
072: while (succsIt.hasNext()) {
073: Stmt succ = (Stmt) succsIt.next();
074: if (dominaters.contains(succ)) {
075: //header succeeds and dominates s, we have a loop
076: headers.add(succ);
077: }
078: }
079:
080: Iterator<Stmt> headersIt = headers.iterator();
081: while (headersIt.hasNext()) {
082: Stmt header = headersIt.next();
083: List<Stmt> loopBody = getLoopBodyFor(header, s);
084:
085: // for now just print out loops as sets of stmts
086: //System.out.println("FOUND LOOP: Header: "+header+" Body: "+loopBody);
087: if (loops.containsKey(header)) {
088: // merge bodies
089: List<Stmt> lb1 = loops.get(header);
090: loops.put(header, union(lb1, loopBody));
091: } else {
092: loops.put(header, loopBody);
093: }
094: }
095: }
096:
097: }
098:
099: private List<Stmt> getLoopBodyFor(Stmt header, Stmt node) {
100:
101: ArrayList<Stmt> loopBody = new ArrayList<Stmt>();
102: Stack<Unit> stack = new Stack<Unit>();
103:
104: loopBody.add(header);
105: stack.push(node);
106:
107: while (!stack.isEmpty()) {
108: Stmt next = (Stmt) stack.pop();
109: if (!loopBody.contains(next)) {
110: // add next to loop body
111: loopBody.add(0, next);
112: // put all preds of next on stack
113: Iterator<Unit> it = g.getPredsOf(next).iterator();
114: while (it.hasNext()) {
115: stack.push(it.next());
116: }
117: }
118: }
119:
120: assert (node == header && loopBody.size() == 1)
121: || loopBody.get(loopBody.size() - 2) == node;
122: assert loopBody.get(loopBody.size() - 1) == header;
123:
124: return loopBody;
125: }
126:
127: private List<Stmt> union(List<Stmt> l1, List<Stmt> l2) {
128: Iterator<Stmt> it = l2.iterator();
129: while (it.hasNext()) {
130: Stmt next = it.next();
131: if (!l1.contains(next)) {
132: l1.add(next);
133: }
134: }
135: return l1;
136: }
137: }
|