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 soot.toolkits.graph.*;
032: import soot.util.*;
033: import java.util.*;
034:
035: /**
036: * A BodyTransformer that attemps to indentify and separate uses of a local
037: * varible that are independent of each other. Conceptually the inverse transform
038: * with respect to the LocalPacker transform.
039: *
040: * For example the code:
041: *
042: * for(int i; i < k; i++);
043: * for(int i; i < k; i++);
044: *
045: * would be transformed into:
046: * for(int i; i < k; i++);
047: * for(int j; j < k; j++);
048: *
049: *
050: * @see BodyTransformer
051: * @see LocalPacker
052: * @see Body
053: */
054: public class LocalSplitter extends BodyTransformer {
055: public LocalSplitter(Singletons.Global g) {
056: }
057:
058: public static LocalSplitter v() {
059: return G.v().soot_toolkits_scalar_LocalSplitter();
060: }
061:
062: protected void internalTransform(Body body, String phaseName,
063: Map options) {
064: Chain units = body.getUnits();
065: List<List> webs = new ArrayList<List>();
066:
067: if (Options.v().verbose())
068: G.v().out.println("[" + body.getMethod().getName()
069: + "] Splitting locals...");
070:
071: Map boxToSet = new HashMap(units.size() * 2 + 1, 0.7f);
072:
073: if (Options.v().time())
074: Timers.v().splitPhase1Timer.start();
075:
076: // Go through the definitions, building the webs
077: {
078: ExceptionalUnitGraph graph = new ExceptionalUnitGraph(body);
079:
080: LocalDefs localDefs;
081:
082: localDefs = new SmartLocalDefs(graph, new SimpleLiveLocals(
083: graph));
084:
085: LocalUses localUses = new SimpleLocalUses(graph, localDefs);
086:
087: if (Options.v().time())
088: Timers.v().splitPhase1Timer.end();
089:
090: if (Options.v().time())
091: Timers.v().splitPhase2Timer.start();
092:
093: Set<ValueBox> markedBoxes = new HashSet<ValueBox>();
094: Map<ValueBox, Unit> boxToUnit = new HashMap<ValueBox, Unit>(
095: units.size() * 2 + 1, 0.7f);
096:
097: Iterator codeIt = units.iterator();
098:
099: while (codeIt.hasNext()) {
100: Unit s = (Unit) codeIt.next();
101:
102: if (s.getDefBoxes().size() > 1)
103: throw new RuntimeException(
104: "stmt with more than 1 defbox!");
105:
106: if (s.getDefBoxes().size() < 1)
107: continue;
108:
109: ValueBox loBox = (ValueBox) s.getDefBoxes().get(0);
110: Value lo = loBox.getValue();
111:
112: if (lo instanceof Local && !markedBoxes.contains(loBox)) {
113: LinkedList<Unit> defsToVisit = new LinkedList<Unit>();
114: LinkedList<ValueBox> boxesToVisit = new LinkedList<ValueBox>();
115:
116: List web = new ArrayList();
117: webs.add(web);
118:
119: defsToVisit.add(s);
120: markedBoxes.add(loBox);
121:
122: while (!boxesToVisit.isEmpty()
123: || !defsToVisit.isEmpty()) {
124: if (!defsToVisit.isEmpty()) {
125: Unit d = defsToVisit.removeFirst();
126:
127: web.add(d.getDefBoxes().get(0));
128:
129: // Add all the uses of this definition to the queue
130: {
131: List uses = localUses.getUsesOf(d);
132: Iterator useIt = uses.iterator();
133:
134: while (useIt.hasNext()) {
135: UnitValueBoxPair use = (UnitValueBoxPair) useIt
136: .next();
137:
138: if (!markedBoxes
139: .contains(use.valueBox)) {
140: markedBoxes.add(use.valueBox);
141: boxesToVisit
142: .addLast(use.valueBox);
143: boxToUnit.put(use.valueBox,
144: use.unit);
145: }
146: }
147: }
148: } else {
149: ValueBox box = boxesToVisit.removeFirst();
150:
151: web.add(box);
152:
153: // Add all the definitions of this use to the queue.
154: {
155: List<Unit> defs = localDefs
156: .getDefsOfAt((Local) box
157: .getValue(), boxToUnit
158: .get(box));
159: Iterator<Unit> defIt = defs.iterator();
160:
161: while (defIt.hasNext()) {
162: Unit u = defIt.next();
163:
164: Iterator defBoxesIter = u
165: .getDefBoxes().iterator();
166: ValueBox b;
167:
168: for (; defBoxesIter.hasNext();) {
169: b = (ValueBox) defBoxesIter
170: .next();
171: if (!markedBoxes.contains(b)) {
172: markedBoxes.add(b);
173: defsToVisit.addLast(u);
174: }
175: }
176: }
177: }
178: }
179: }
180: }
181: }
182: }
183:
184: // Assign locals appropriately.
185: {
186: Map<Local, Integer> localToUseCount = new HashMap<Local, Integer>(
187: body.getLocalCount() * 2 + 1, 0.7f);
188: Iterator<List> webIt = webs.iterator();
189:
190: while (webIt.hasNext()) {
191: List web = webIt.next();
192:
193: ValueBox rep = (ValueBox) web.get(0);
194: Local desiredLocal = (Local) rep.getValue();
195:
196: if (!localToUseCount.containsKey(desiredLocal)) {
197: // claim this local for this set
198:
199: localToUseCount.put(desiredLocal, new Integer(1));
200: } else {
201: // generate a new local
202:
203: int useCount = localToUseCount.get(desiredLocal)
204: .intValue() + 1;
205: localToUseCount.put(desiredLocal, new Integer(
206: useCount));
207:
208: Local local = (Local) desiredLocal.clone();
209: local.setName(desiredLocal.getName() + "#"
210: + useCount);
211:
212: body.getLocals().add(local);
213:
214: // Change all boxes to point to this new local
215: {
216: Iterator j = web.iterator();
217:
218: while (j.hasNext()) {
219: ValueBox box = (ValueBox) j.next();
220:
221: box.setValue(local);
222: }
223: }
224: }
225: }
226: }
227:
228: if (Options.v().time())
229: Timers.v().splitPhase2Timer.end();
230:
231: }
232: }
|