001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1997-1999 Raja Vallee-Rai
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: /*
021: * Modified by the Sable Research Group and others 1997-1999.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: /* Reference Version: $SootVersion: 1.2.5.dev.5 $ */
027:
028: package soot.jimple.toolkits.base;
029:
030: import soot.options.*;
031:
032: import soot.*;
033: import soot.jimple.*;
034: import soot.toolkits.scalar.*;
035: import soot.toolkits.graph.*;
036: import soot.util.*;
037: import java.util.*;
038:
039: public class Aggregator extends BodyTransformer {
040: public Aggregator(Singletons.Global g) {
041: }
042:
043: public static Aggregator v() {
044: return G.v().soot_jimple_toolkits_base_Aggregator();
045: }
046:
047: /** Traverse the statements in the given body, looking for
048: * aggregation possibilities; that is, given a def d and a use u,
049: * d has no other uses, u has no other defs, collapse d and u.
050: *
051: * option: only-stack-locals; if this is true, only aggregate variables
052: starting with $ */
053: protected void internalTransform(Body b, String phaseName,
054: Map options) {
055: StmtBody body = (StmtBody) b;
056: boolean onlyStackVars = PhaseOptions.getBoolean(options,
057: "only-stack-locals");
058:
059: int aggregateCount = 1;
060:
061: if (Options.v().time())
062: Timers.v().aggregationTimer.start();
063: boolean changed = false;
064:
065: Map<ValueBox, Zone> boxToZone = new HashMap<ValueBox, Zone>(
066: body.getUnits().size() * 2 + 1, 0.7f);
067:
068: // Determine the zone of every box
069: {
070: Zonation zonation = new Zonation(body);
071:
072: Iterator unitIt = body.getUnits().iterator();
073:
074: while (unitIt.hasNext()) {
075: Unit u = (Unit) unitIt.next();
076: Zone zone = zonation.getZoneOf(u);
077:
078: Iterator boxIt = u.getUseBoxes().iterator();
079: while (boxIt.hasNext()) {
080: ValueBox box = (ValueBox) boxIt.next();
081: boxToZone.put(box, zone);
082: }
083: boxIt = u.getDefBoxes().iterator();
084: while (boxIt.hasNext()) {
085: ValueBox box = (ValueBox) boxIt.next();
086: boxToZone.put(box, zone);
087: }
088: }
089: }
090:
091: do {
092: if (Options.v().verbose())
093: G.v().out.println("[" + body.getMethod().getName()
094: + "] Aggregating iteration " + aggregateCount
095: + "...");
096:
097: // body.printTo(new java.io.PrintWriter(G.v().out, true));
098:
099: changed = internalAggregate(body, boxToZone, onlyStackVars);
100:
101: aggregateCount++;
102: } while (changed);
103:
104: if (Options.v().time())
105: Timers.v().aggregationTimer.end();
106:
107: }
108:
109: private static boolean internalAggregate(StmtBody body,
110: Map<ValueBox, Zone> boxToZone, boolean onlyStackVars) {
111: Iterator stmtIt;
112: LocalUses localUses;
113: LocalDefs localDefs;
114: ExceptionalUnitGraph graph;
115: boolean hadAggregation = false;
116: Chain units = body.getUnits();
117:
118: graph = new ExceptionalUnitGraph(body);
119: localDefs = new SmartLocalDefs(graph, new SimpleLiveLocals(
120: graph));
121: localUses = new SimpleLocalUses(graph, localDefs);
122:
123: stmtIt = (new PseudoTopologicalOrderer()).newList(graph, false)
124: .iterator();
125:
126: while (stmtIt.hasNext()) {
127: Stmt s = (Stmt) (stmtIt.next());
128:
129: if (!(s instanceof AssignStmt))
130: continue;
131:
132: Value lhs = ((AssignStmt) s).getLeftOp();
133: if (!(lhs instanceof Local))
134: continue;
135:
136: if (onlyStackVars
137: && !((Local) lhs).getName().startsWith("$"))
138: continue;
139:
140: List lu = localUses.getUsesOf(s);
141: if (lu.size() != 1)
142: continue;
143:
144: UnitValueBoxPair usepair = (UnitValueBoxPair) lu.get(0);
145: Unit use = usepair.unit;
146: ValueBox useBox = usepair.valueBox;
147:
148: List<Unit> ld = localDefs.getDefsOfAt((Local) lhs, use);
149: if (ld.size() != 1)
150: continue;
151:
152: // Check to make sure aggregation pair in the same zone
153: if (boxToZone.get(((AssignStmt) s).getRightOpBox()) != boxToZone
154: .get(usepair.valueBox)) {
155: continue;
156: }
157:
158: /* we need to check the path between def and use */
159: /* to see if there are any intervening re-defs of RHS */
160: /* in fact, we should check that this path is unique. */
161: /* if the RHS uses only locals, then we know what
162: to do; if RHS has a method invocation f(a, b,
163: c) or field access, we must ban field writes, other method
164: calls and (as usual) writes to a, b, c. */
165:
166: boolean cantAggr = false;
167: boolean propagatingInvokeExpr = false;
168: boolean propagatingFieldRef = false;
169: boolean propagatingArrayRef = false;
170: ArrayList<Value> fieldRefList = new ArrayList<Value>();
171:
172: LinkedList<Value> localsUsed = new LinkedList<Value>();
173: for (Iterator useIt = (s.getUseBoxes()).iterator(); useIt
174: .hasNext();) {
175: Value v = ((ValueBox) (useIt.next())).getValue();
176: if (v instanceof Local)
177: localsUsed.add(v);
178: else if (v instanceof InvokeExpr)
179: propagatingInvokeExpr = true;
180: else if (v instanceof ArrayRef)
181: propagatingArrayRef = true;
182: else if (v instanceof FieldRef) {
183: propagatingFieldRef = true;
184: fieldRefList.add(v);
185: }
186: }
187:
188: // look for a path from s to use in graph.
189: // only look in an extended basic block, though.
190:
191: List<Unit> path = graph.getExtendedBasicBlockPathBetween(s,
192: use);
193:
194: if (path == null)
195: continue;
196:
197: Iterator<Unit> pathIt = path.iterator();
198:
199: // skip s.
200: if (pathIt.hasNext())
201: pathIt.next();
202:
203: while (pathIt.hasNext() && !cantAggr) {
204: Stmt between = (Stmt) (pathIt.next());
205:
206: if (between != use) {
207: // Check for killing definitions
208:
209: for (Iterator it = between.getDefBoxes().iterator(); it
210: .hasNext();) {
211: Value v = ((ValueBox) (it.next())).getValue();
212: if (localsUsed.contains(v)) {
213: cantAggr = true;
214: break;
215: }
216:
217: if (propagatingInvokeExpr
218: || propagatingFieldRef
219: || propagatingArrayRef) {
220: if (v instanceof FieldRef) {
221: if (propagatingInvokeExpr) {
222: cantAggr = true;
223: break;
224: } else if (propagatingFieldRef) {
225: // Can't aggregate a field access if passing a definition of a field
226: // with the same name, because they might be aliased
227:
228: Iterator<Value> frIt = fieldRefList
229: .iterator();
230: while (frIt.hasNext()) {
231: FieldRef fieldRef = (FieldRef) frIt
232: .next();
233: if (((FieldRef) v).getField() == fieldRef
234: .getField()) {
235: cantAggr = true;
236: break;
237: }
238: }
239: }
240: } else if (v instanceof ArrayRef) {
241: if (propagatingInvokeExpr) {
242: // Cannot aggregate an invoke expr past an array write
243: cantAggr = true;
244: break;
245: } else if (propagatingArrayRef) {
246: // cannot aggregate an array read past a write
247: // this is somewhat conservative
248: // (if types differ they may not be aliased)
249:
250: cantAggr = true;
251: break;
252: }
253: }
254: }
255: }
256:
257: // Make sure not propagating past a {enter,exit}Monitor
258: if (propagatingInvokeExpr
259: && between instanceof MonitorStmt)
260: cantAggr = true;
261: }
262:
263: // Check for intervening side effects due to method calls
264: if (propagatingInvokeExpr || propagatingFieldRef
265: || propagatingArrayRef) {
266: for (Iterator boxIt = (between.getUseBoxes())
267: .iterator(); boxIt.hasNext();) {
268: final ValueBox box = (ValueBox) boxIt.next();
269:
270: if (between == use && box == useBox) {
271: // Reached use point, stop looking for
272: // side effects
273: break;
274: }
275:
276: Value v = box.getValue();
277:
278: if (v instanceof InvokeExpr
279: || (propagatingInvokeExpr && (v instanceof FieldRef || v instanceof ArrayRef))) {
280: cantAggr = true;
281: break;
282: }
283:
284: }
285: }
286: }
287:
288: // we give up: can't aggregate.
289: if (cantAggr) {
290: continue;
291: }
292: /* assuming that the d-u chains are correct, */
293: /* we need not check the actual contents of ld */
294:
295: Value aggregatee = ((AssignStmt) s).getRightOp();
296:
297: if (usepair.valueBox.canContainValue(aggregatee)) {
298: boolean wasSimpleCopy = isSimpleCopy(usepair.unit);
299: usepair.valueBox.setValue(aggregatee);
300: units.remove(s);
301: hadAggregation = true;
302: // clean up the tags. If s was not a simple copy, the new statement should get
303: // the tags of s.
304: // OK, this fix was wrong. The condition should not be
305: // "If s was not a simple copy", but rather "If usepair.unit
306: // was a simple copy". This way, when there's a load of a constant
307: // followed by an invoke, the invoke gets the tags.
308: if (wasSimpleCopy) {
309: //usepair.unit.removeAllTags();
310: usepair.unit.addAllTagsOf(s);
311: }
312: } else {/*
313: if(Options.v().verbose())
314: {
315: G.v().out.println("[debug] failed aggregation");
316: G.v().out.println("[debug] tried to put "+aggregatee+
317: " into "+usepair.stmt +
318: ": in particular, "+usepair.valueBox);
319: G.v().out.println("[debug] aggregatee instanceof Expr: "
320: +(aggregatee instanceof Expr));
321: }*/
322: }
323: }
324: return hadAggregation;
325: }
326:
327: private static boolean isSimpleCopy(Unit u) {
328: if (!(u instanceof DefinitionStmt))
329: return false;
330: DefinitionStmt defstmt = (DefinitionStmt) u;
331: if (!(defstmt.getRightOp() instanceof Local))
332: return false;
333: if (!(defstmt.getLeftOp() instanceof Local))
334: return false;
335: return true;
336: }
337:
338: }
|