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.*;
029: import soot.toolkits.scalar.*;
030: import soot.toolkits.graph.*;
031: import soot.jimple.*;
032: import java.util.*;
033:
034: /** Implements an available expressions analysis on local variables.
035: * The current implementation is slow but correct.
036: * A better implementation would use an implicit universe and
037: * the kill rule would be computed on-the-fly for each statement. */
038: public class FastAvailableExpressionsAnalysis extends
039: ForwardFlowAnalysis {
040: SideEffectTester st;
041:
042: Map<Unit, FlowSet> unitToGenerateSet;
043: Map unitToPreserveSet;
044: Map<Value, Unit> rhsToContainingStmt;
045:
046: FlowSet emptySet;
047:
048: public FastAvailableExpressionsAnalysis(DirectedGraph dg,
049: SootMethod m, SideEffectTester st) {
050: super (dg);
051: this .st = st;
052:
053: ExceptionalUnitGraph g = (ExceptionalUnitGraph) dg;
054: LocalDefs ld = new SmartLocalDefs(g, new SimpleLiveLocals(g));
055:
056: // maps an rhs to its containing stmt. object equality in rhs.
057: rhsToContainingStmt = new HashMap<Value, Unit>();
058:
059: emptySet = new ToppedSet(new ArraySparseSet());
060:
061: // Create generate sets
062: {
063: unitToGenerateSet = new HashMap<Unit, FlowSet>(
064: g.size() * 2 + 1, 0.7f);
065:
066: Iterator unitIt = g.iterator();
067:
068: while (unitIt.hasNext()) {
069: Unit s = (Unit) unitIt.next();
070:
071: FlowSet genSet = emptySet.clone();
072: // In Jimple, expressions only occur as the RHS of an AssignStmt.
073: if (s instanceof AssignStmt) {
074: AssignStmt as = (AssignStmt) s;
075: if (as.getRightOp() instanceof Expr
076: || as.getRightOp() instanceof FieldRef) {
077: Value gen = as.getRightOp();
078: rhsToContainingStmt.put(gen, s);
079:
080: boolean cantAdd = false;
081: if (gen instanceof NewExpr
082: || gen instanceof NewArrayExpr
083: || gen instanceof NewMultiArrayExpr)
084: cantAdd = true;
085: if (gen instanceof InvokeExpr)
086: cantAdd = true;
087:
088: // Whee, double negative!
089: if (!cantAdd)
090: genSet.add(gen, genSet);
091: }
092: }
093:
094: unitToGenerateSet.put(s, genSet);
095: }
096: }
097:
098: doAnalysis();
099: }
100:
101: protected Object newInitialFlow() {
102: Object newSet = emptySet.clone();
103: ((ToppedSet) newSet).setTop(true);
104: return newSet;
105: }
106:
107: protected Object entryInitialFlow() {
108: return emptySet.clone();
109: }
110:
111: protected void flowThrough(Object inValue, Object unit,
112: Object outValue) {
113: FlowSet in = (FlowSet) inValue, out = (FlowSet) outValue;
114:
115: in.copy(out);
116: if (((ToppedSet) in).isTop())
117: return;
118:
119: // Perform generation
120: out.union(unitToGenerateSet.get(unit), out);
121:
122: // Perform kill.
123: Unit u = (Unit) unit;
124: List toRemove = new ArrayList();
125:
126: if (((ToppedSet) out).isTop()) {
127: throw new RuntimeException("trying to kill on topped set!");
128: }
129: List l = new LinkedList();
130: l.addAll((out).toList());
131: Iterator it = l.iterator();
132:
133: // iterate over things (avail) in out set.
134: while (it.hasNext()) {
135: Value avail = (Value) it.next();
136: if (avail instanceof FieldRef) {
137: if (st.unitCanWriteTo(u, avail)) {
138: out.remove(avail, out);
139: }
140: } else {
141: Iterator usesIt = avail.getUseBoxes().iterator();
142:
143: // iterate over uses in each avail.
144: while (usesIt.hasNext()) {
145: Value use = ((ValueBox) usesIt.next()).getValue();
146:
147: if (st.unitCanWriteTo(u, use)) {
148: out.remove(avail, out);
149: }
150: }
151: }
152: }
153: }
154:
155: protected void merge(Object in1, Object in2, Object out) {
156: FlowSet inSet1 = (FlowSet) in1, inSet2 = (FlowSet) in2;
157:
158: FlowSet outSet = (FlowSet) out;
159:
160: inSet1.intersection(inSet2, outSet);
161: }
162:
163: protected void copy(Object source, Object dest) {
164: FlowSet sourceSet = (FlowSet) source, destSet = (FlowSet) dest;
165:
166: sourceSet.copy(destSet);
167: }
168: }
|