001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2002 Florian Loitsch
003: * based on FastAvailableExpressionsAnalysis from Patrick Lam.
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the
017: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
018: * Boston, MA 02111-1307, USA.
019: */
020:
021: /*
022: * Modified by the Sable Research Group and others 1997-2002.
023: * See the 'credits' file distributed with Soot for the complete list of
024: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
025: */
026:
027: package soot.jimple.toolkits.scalar.pre;
028:
029: import soot.*;
030: import soot.toolkits.scalar.*;
031: import soot.toolkits.graph.*;
032: import soot.jimple.*;
033: import java.util.*;
034:
035: /**
036: * Performs an UpSafe-analysis on the given graph.
037: * An expression is upsafe, if the computation already has been performed on
038: * every path from START to the given program-point.
039: */
040: public class UpSafetyAnalysis extends ForwardFlowAnalysis {
041: private SideEffectTester sideEffect;
042:
043: private Map unitToGenerateMap;
044:
045: private BoundedFlowSet set;
046:
047: /**
048: * this constructor should not be used, and will throw a runtime-exception!
049: */
050: public UpSafetyAnalysis(DirectedGraph dg) {
051: /* we have to add super(dg). otherwise Javac complains. */
052: super (dg);
053: throw new RuntimeException("Don't use this Constructor!");
054: }
055:
056: /**
057: * this constructor automaticly performs the UpSafety-analysis.<br>
058: * the result of the analysis is as usual in FlowBefore (getFlowBefore())
059: * and FlowAfter (getFlowAfter()).<br>
060: *
061: * @param dg a ExceptionalUnitGraph
062: * @param unitToGen the EquivalentValue of each unit.
063: * @param sideEffect the SideEffectTester that will be used to perform kills.
064: */
065: public UpSafetyAnalysis(DirectedGraph dg, Map unitToGen,
066: SideEffectTester sideEffect) {
067: this (dg, unitToGen, sideEffect, new ArrayPackedSet(
068: new CollectionFlowUniverse(unitToGen.values())));
069: }
070:
071: /**
072: * this constructor automaticly performs the UpSafety-analysis.<br>
073: * the result of the analysis is as usual in FlowBefore (getFlowBefore())
074: * and FlowAfter (getFlowAfter()).<br>
075: * As usually flowset-operations are more efficient if shared, this allows to
076: * share sets over several analyses.
077: *
078: * @param dg a ExceptionalUnitGraph
079: * @param unitToGen the EquivalentValue of each unit.
080: * @param sideEffect the SideEffectTester that will be used to perform kills.
081: * @param set a bounded flow-set.
082: */
083: public UpSafetyAnalysis(DirectedGraph dg, Map unitToGen,
084: SideEffectTester sideEffect, BoundedFlowSet set) {
085: super (dg);
086: this .sideEffect = sideEffect;
087: this .set = set;
088: unitToGenerateMap = unitToGen;
089: doAnalysis();
090: }
091:
092: protected Object newInitialFlow() {
093: return set.topSet();
094: }
095:
096: protected Object entryInitialFlow() {
097: return set.emptySet();
098: }
099:
100: protected void flowThrough(Object inValue, Object unit,
101: Object outValue) {
102: FlowSet in = (FlowSet) inValue, out = (FlowSet) outValue;
103:
104: in.copy(out);
105:
106: // Perform generation
107: Value add = (Value) unitToGenerateMap.get(unit);
108: if (add != null)
109: out.add(add, out);
110:
111: { /* Perform kill */
112: Unit u = (Unit) unit;
113:
114: Iterator outIt = (out).iterator();
115:
116: // iterate over things (avail) in out set.
117: while (outIt.hasNext()) {
118: EquivalentValue equiVal = (EquivalentValue) outIt
119: .next();
120: Value avail = equiVal.getValue();
121: if (avail instanceof FieldRef) {
122: if (sideEffect.unitCanWriteTo(u, avail))
123: outIt.remove();
124: } else {
125: Iterator usesIt = avail.getUseBoxes().iterator();
126:
127: // iterate over uses in each avail.
128: while (usesIt.hasNext()) {
129: Value use = ((ValueBox) usesIt.next())
130: .getValue();
131: if (sideEffect.unitCanWriteTo(u, use)) {
132: outIt.remove();
133: break;
134: }
135: }
136: }
137: }
138: }
139: }
140:
141: protected void merge(Object in1, Object in2, Object out) {
142: FlowSet inSet1 = (FlowSet) in1;
143: FlowSet inSet2 = (FlowSet) in2;
144:
145: FlowSet outSet = (FlowSet) out;
146:
147: inSet1.intersection(inSet2, outSet);
148: }
149:
150: protected void copy(Object source, Object dest) {
151: FlowSet sourceSet = (FlowSet) source;
152: FlowSet destSet = (FlowSet) dest;
153:
154: sourceSet.copy(destSet);
155: }
156: }
|