001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2000 Patrick Lam
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: package soot.jimple.toolkits.scalar;
027:
028: import soot.options.*;
029: import soot.*;
030: import soot.toolkits.scalar.*;
031: import soot.jimple.*;
032: import java.util.*;
033: import soot.util.*;
034: import soot.jimple.toolkits.pointer.PASideEffectTester;
035: import soot.tagkit.*;
036:
037: /** Runs an available expressions analysis on a body, then
038: * eliminates common subexpressions.
039: *
040: * This implementation is especially slow, as it does not
041: * run on basic blocks. A better implementation (which wouldn't
042: * catch every single cse, but would get most) would use
043: * basic blocks instead.
044: *
045: * It is also slow because the flow universe is explicitly created; it
046: * need not be. A better implementation would implicitly compute the
047: * kill sets at every node. */
048:
049: public class CommonSubexpressionEliminator extends BodyTransformer {
050: public CommonSubexpressionEliminator(Singletons.Global g) {
051: }
052:
053: public static CommonSubexpressionEliminator v() {
054: return G
055: .v()
056: .soot_jimple_toolkits_scalar_CommonSubexpressionEliminator();
057: }
058:
059: /** Common subexpression eliminator. */
060: protected void internalTransform(Body b, String phaseName,
061: Map options) {
062: int counter = 0;
063:
064: // Sigh. check for name collisions.
065: Iterator localsIt = b.getLocals().iterator();
066: HashSet<String> localNames = new HashSet<String>(b.getLocals()
067: .size());
068: while (localsIt.hasNext()) {
069: localNames.add(((Local) localsIt.next()).getName());
070: }
071:
072: SideEffectTester sideEffect;
073: if (Scene.v().hasCallGraph()
074: && !PhaseOptions.getBoolean(options,
075: "naive-side-effect")) {
076: sideEffect = new PASideEffectTester();
077: } else {
078: sideEffect = new NaiveSideEffectTester();
079: }
080: sideEffect.newMethod(b.getMethod());
081:
082: if (Options.v().verbose())
083: G.v().out
084: .println("["
085: + b.getMethod().getName()
086: + "] Eliminating common subexpressions "
087: + (sideEffect instanceof NaiveSideEffectTester ? "(naively)"
088: : "") + "...");
089:
090: AvailableExpressions ae = // new SlowAvailableExpressions(b);
091: new FastAvailableExpressions(b, sideEffect);
092:
093: Chain units = b.getUnits();
094: Iterator unitsIt = units.snapshotIterator();
095: while (unitsIt.hasNext()) {
096: Stmt s = (Stmt) unitsIt.next();
097:
098: if (s instanceof AssignStmt) {
099: Chain availExprs = ae.getAvailableEquivsBefore(s);
100: //G.v().out.println("availExprs: "+availExprs);
101: Value v = ((AssignStmt) s).getRightOp();
102: EquivalentValue ev = new EquivalentValue(v);
103:
104: if (availExprs.contains(ev)) {
105: // now we need to track down the containing stmt.
106: List availPairs = ae.getAvailablePairsBefore(s);
107: //G.v().out.println("availPairs: "+availPairs);
108: Iterator availIt = availPairs.iterator();
109: while (availIt.hasNext()) {
110: UnitValueBoxPair up = (UnitValueBoxPair) availIt
111: .next();
112: if (up.getValueBox().getValue().equivTo(v)) {
113: // create a local for temp storage.
114: // (we could check to see that the def must-reach, I guess...)
115: String newName = "$cseTmp" + counter;
116: counter++;
117:
118: while (localNames.contains(newName)) {
119: newName = "$cseTmp" + counter;
120: counter++;
121: }
122:
123: Local l = Jimple.v().newLocal(newName,
124: Type.toMachineType(v.getType()));
125:
126: b.getLocals().add(l);
127:
128: // I hope it's always an AssignStmt -- Jimple should guarantee this.
129: AssignStmt origCalc = (AssignStmt) up
130: .getUnit();
131: Value origLHS = origCalc.getLeftOp();
132:
133: origCalc.setLeftOp(l);
134:
135: Unit copier = Jimple.v().newAssignStmt(
136: origLHS, l);
137: units.insertAfter(copier, origCalc);
138:
139: ((AssignStmt) s).setRightOp(l);
140: copier.addTag(new StringTag(
141: "Common sub-expression"));
142: s.addTag(new StringTag(
143: "Common sub-expression"));
144: //G.v().out.println("added tag to : "+copier);
145: //G.v().out.println("added tag to : "+s);
146: }
147: }
148: }
149: }
150: }
151: if (Options.v().verbose())
152: G.v().out.println("[" + b.getMethod().getName()
153: + "] Eliminating common subexpressions done!");
154: }
155: }
|