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: package soot.toolkits.scalar;
027:
028: import soot.options.*;
029:
030: import soot.*;
031: import java.util.*;
032:
033: import soot.toolkits.graph.*;
034:
035: /**
036: * Analysis that provides an implementation of the LiveLocals interface.
037: */
038: public class SimpleLiveLocals implements LiveLocals {
039: Map<Unit, List> unitToLocalsAfter;
040: Map<Unit, List> unitToLocalsBefore;
041:
042: /**
043: * Computes the analysis given a UnitGraph computed from a
044: * method body. It is recommended that a ExceptionalUnitGraph (or
045: * similar) be provided for correct results in the case of
046: * exceptional control flow.
047: *
048: * @param g a graph on which to compute the analysis.
049: *
050: * @see ExceptionalUnitGraph
051: */
052: public SimpleLiveLocals(UnitGraph graph) {
053: if (Options.v().time())
054: Timers.v().liveTimer.start();
055:
056: if (Options.v().verbose())
057: G.v().out.println("["
058: + graph.getBody().getMethod().getName()
059: + "] Constructing SimpleLiveLocals...");
060:
061: SimpleLiveLocalsAnalysis analysis = new SimpleLiveLocalsAnalysis(
062: graph);
063:
064: if (Options.v().time())
065: Timers.v().livePostTimer.start();
066:
067: // Build unitToLocals map
068: {
069: unitToLocalsAfter = new HashMap<Unit, List>(
070: graph.size() * 2 + 1, 0.7f);
071: unitToLocalsBefore = new HashMap<Unit, List>(
072: graph.size() * 2 + 1, 0.7f);
073:
074: Iterator unitIt = graph.iterator();
075:
076: while (unitIt.hasNext()) {
077: Unit s = (Unit) unitIt.next();
078:
079: FlowSet set = (FlowSet) analysis.getFlowBefore(s);
080: unitToLocalsBefore.put(s, Collections
081: .unmodifiableList(set.toList()));
082:
083: set = (FlowSet) analysis.getFlowAfter(s);
084: unitToLocalsAfter.put(s, Collections
085: .unmodifiableList(set.toList()));
086: }
087: }
088:
089: if (Options.v().time())
090: Timers.v().livePostTimer.end();
091:
092: if (Options.v().time())
093: Timers.v().liveTimer.end();
094: }
095:
096: public List getLiveLocalsAfter(Unit s) {
097: return unitToLocalsAfter.get(s);
098: }
099:
100: public List getLiveLocalsBefore(Unit s) {
101: return unitToLocalsBefore.get(s);
102: }
103: }
104:
105: class SimpleLiveLocalsAnalysis extends BackwardFlowAnalysis {
106: FlowSet emptySet;
107: Map<Unit, FlowSet> unitToGenerateSet;
108: Map<Unit, FlowSet> unitToKillSet;
109:
110: SimpleLiveLocalsAnalysis(UnitGraph g) {
111: super (g);
112:
113: if (Options.v().time())
114: Timers.v().liveSetupTimer.start();
115:
116: emptySet = new ArraySparseSet();
117:
118: // Create kill sets.
119: {
120: unitToKillSet = new HashMap<Unit, FlowSet>(
121: g.size() * 2 + 1, 0.7f);
122:
123: Iterator unitIt = g.iterator();
124:
125: while (unitIt.hasNext()) {
126: Unit s = (Unit) unitIt.next();
127:
128: FlowSet killSet = emptySet.clone();
129:
130: Iterator boxIt = s.getDefBoxes().iterator();
131:
132: while (boxIt.hasNext()) {
133: ValueBox box = (ValueBox) boxIt.next();
134:
135: if (box.getValue() instanceof Local)
136: killSet.add(box.getValue(), killSet);
137: }
138:
139: unitToKillSet.put(s, killSet);
140: }
141: }
142:
143: // Create generate sets
144: {
145: unitToGenerateSet = new HashMap<Unit, FlowSet>(
146: g.size() * 2 + 1, 0.7f);
147:
148: Iterator unitIt = g.iterator();
149:
150: while (unitIt.hasNext()) {
151: Unit s = (Unit) unitIt.next();
152:
153: FlowSet genSet = emptySet.clone();
154:
155: Iterator boxIt = s.getUseBoxes().iterator();
156:
157: while (boxIt.hasNext()) {
158: ValueBox box = (ValueBox) boxIt.next();
159:
160: if (box.getValue() instanceof Local)
161: genSet.add(box.getValue(), genSet);
162: }
163:
164: unitToGenerateSet.put(s, genSet);
165: }
166: }
167:
168: if (Options.v().time())
169: Timers.v().liveSetupTimer.end();
170:
171: if (Options.v().time())
172: Timers.v().liveAnalysisTimer.start();
173:
174: doAnalysis();
175:
176: if (Options.v().time())
177: Timers.v().liveAnalysisTimer.end();
178:
179: }
180:
181: protected Object newInitialFlow() {
182: return emptySet.clone();
183: }
184:
185: protected Object entryInitialFlow() {
186: return emptySet.clone();
187: }
188:
189: protected void flowThrough(Object inValue, Object unit,
190: Object outValue) {
191: FlowSet in = (FlowSet) inValue, out = (FlowSet) outValue;
192:
193: // Perform kill
194: in.difference(unitToKillSet.get(unit), out);
195:
196: // Perform generation
197: out.union(unitToGenerateSet.get(unit), out);
198: }
199:
200: protected void merge(Object in1, Object in2, Object out) {
201: FlowSet inSet1 = (FlowSet) in1, inSet2 = (FlowSet) in2;
202:
203: FlowSet outSet = (FlowSet) out;
204:
205: inSet1.union(inSet2, outSet);
206: }
207:
208: protected void copy(Object source, Object dest) {
209: FlowSet sourceSet = (FlowSet) source, destSet = (FlowSet) dest;
210:
211: sourceSet.copy(destSet);
212: }
213: }
|