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.*;
029: import soot.toolkits.graph.*;
030: import soot.util.*;
031:
032: import java.util.*;
033:
034: /** Provides methods for register coloring. Jimple uses these methods
035: * to assign the local slots appropriately. */
036: public class FastColorer {
037: /** Provides a coloring for the locals of
038: * <code>unitBody</code>, attempting to not
039: * split locals assigned the same name in the original Jimple. */
040: public static void unsplitAssignColorsToLocals(Body unitBody,
041: Map<Local, Object> localToGroup,
042: Map<Local, Integer> localToColor,
043: Map<Object, Integer> groupToColorCount) {
044: ExceptionalUnitGraph unitGraph = new ExceptionalUnitGraph(
045: unitBody);
046:
047: LiveLocals liveLocals;
048: liveLocals = new SimpleLiveLocals(unitGraph);
049:
050: UnitInterferenceGraph intGraph = new UnitInterferenceGraph(
051: unitBody, localToGroup, liveLocals);
052:
053: Map<Local, String> localToOriginalName = new HashMap<Local, String>();
054:
055: // Map each local variable to its original name
056: {
057: Iterator localIt = intGraph.getLocals().iterator();
058:
059: while (localIt.hasNext()) {
060: Local local = (Local) localIt.next();
061:
062: int signIndex;
063:
064: signIndex = local.getName().indexOf("#");
065:
066: if (signIndex != -1) {
067: localToOriginalName.put(local, local.getName()
068: .substring(0, signIndex));
069: } else
070: localToOriginalName.put(local, local.getName());
071:
072: }
073: }
074:
075: Map<StringGroupPair, List> originalNameAndGroupToColors = new HashMap<StringGroupPair, List>();
076: // maps an original name to the colors being used for it
077:
078: // Assign a color for each local.
079: {
080: int[] freeColors = new int[10];
081: Iterator localIt = intGraph.getLocals().iterator();
082:
083: while (localIt.hasNext()) {
084: Local local = (Local) localIt.next();
085:
086: if (localToColor.containsKey(local)) {
087: // Already assigned, probably a parameter
088: continue;
089: }
090:
091: Object group = localToGroup.get(local);
092: int colorCount = groupToColorCount.get(group)
093: .intValue();
094:
095: if (freeColors.length < colorCount)
096: freeColors = new int[Math.max(
097: freeColors.length * 2, colorCount)];
098:
099: // Set all colors to free.
100: {
101: for (int i = 0; i < colorCount; i++)
102: freeColors[i] = 1;
103: }
104:
105: // Remove unavailable colors for this local
106: {
107: Local[] interferences = intGraph
108: .getInterferencesOf(local);
109:
110: for (Local element : interferences) {
111: if (localToColor.containsKey(element)) {
112: int usedColor = localToColor.get(element)
113: .intValue();
114:
115: freeColors[usedColor] = 0;
116: }
117: }
118: }
119:
120: // Assign a color to this local.
121: {
122: String originalName = localToOriginalName
123: .get(local);
124: List<Integer> originalNameColors = originalNameAndGroupToColors
125: .get(new StringGroupPair(originalName,
126: group));
127:
128: if (originalNameColors == null) {
129: originalNameColors = new ArrayList<Integer>();
130: originalNameAndGroupToColors
131: .put(new StringGroupPair(originalName,
132: group), originalNameColors);
133: }
134:
135: boolean found = false;
136: int assignedColor = 0;
137:
138: // Check if the colors assigned to this
139: // original name is already free
140: {
141: Iterator<Integer> colorIt = originalNameColors
142: .iterator();
143:
144: while (colorIt.hasNext()) {
145: Integer color = colorIt.next();
146:
147: if (freeColors[color.intValue()] == 1) {
148: found = true;
149: assignedColor = color.intValue();
150: }
151: }
152: }
153:
154: if (!found) {
155: assignedColor = colorCount++;
156: groupToColorCount.put(group, new Integer(
157: colorCount));
158: originalNameColors.add(new Integer(
159: assignedColor));
160: }
161:
162: localToColor.put(local, new Integer(assignedColor));
163: }
164: }
165: }
166: }
167:
168: /** Provides an economical coloring for the locals of
169: * <code>unitBody</code>. */
170: public static void assignColorsToLocals(Body unitBody,
171: Map<Local, Object> localToGroup,
172: Map<Local, Integer> localToColor,
173: Map<Object, Integer> groupToColorCount) {
174: ExceptionalUnitGraph unitGraph = new ExceptionalUnitGraph(
175: unitBody);
176: LiveLocals liveLocals;
177:
178: liveLocals = new SimpleLiveLocals(unitGraph);
179:
180: UnitInterferenceGraph intGraph = new UnitInterferenceGraph(
181: unitBody, localToGroup, liveLocals);
182:
183: // Assign a color for each local.
184: {
185: int[] freeColors = new int[10];
186: Iterator localIt = intGraph.getLocals().iterator();
187:
188: while (localIt.hasNext()) {
189: Local local = (Local) localIt.next();
190:
191: if (localToColor.containsKey(local)) {
192: // Already assigned, probably a parameter
193: continue;
194: }
195:
196: Object group = localToGroup.get(local);
197: int colorCount = groupToColorCount.get(group)
198: .intValue();
199:
200: if (freeColors.length < colorCount)
201: freeColors = new int[Math.max(
202: freeColors.length * 2, colorCount)];
203:
204: // Set all colors to free.
205: {
206: for (int i = 0; i < colorCount; i++)
207: freeColors[i] = 1;
208: }
209:
210: // Remove unavailable colors for this local
211: {
212: Local[] interferences = intGraph
213: .getInterferencesOf(local);
214:
215: for (Local element : interferences) {
216: if (localToColor.containsKey(element)) {
217: int usedColor = localToColor.get(element)
218: .intValue();
219:
220: freeColors[usedColor] = 0;
221: }
222: }
223: }
224:
225: // Assign a color to this local.
226: {
227: boolean found = false;
228: int assignedColor = 0;
229:
230: for (int i = 0; i < colorCount; i++)
231: if (freeColors[i] == 1) {
232: found = true;
233: assignedColor = i;
234: }
235:
236: if (!found) {
237: assignedColor = colorCount++;
238: groupToColorCount.put(group, new Integer(
239: colorCount));
240: }
241:
242: localToColor.put(local, new Integer(assignedColor));
243: }
244: }
245: }
246:
247: }
248:
249: /** Implementation of a unit interference graph. */
250: public static class UnitInterferenceGraph {
251: Map<Local, ArraySet> localToLocals;// Maps a local to its interfering locals.
252: List locals;
253:
254: private UnitInterferenceGraph() {
255: }
256:
257: public List getLocals() {
258: return locals;
259: }
260:
261: public UnitInterferenceGraph(Body body,
262: Map<Local, Object> localToGroup, LiveLocals liveLocals) {
263: locals = new ArrayList();
264: locals.addAll(body.getLocals());
265:
266: // Initialize localToLocals
267: {
268: localToLocals = new HashMap<Local, ArraySet>(body
269: .getLocalCount() * 2 + 1, 0.7f);
270:
271: Iterator localIt = body.getLocals().iterator();
272:
273: while (localIt.hasNext()) {
274: Local local = (Local) localIt.next();
275:
276: localToLocals.put(local, new ArraySet());
277: }
278: }
279:
280: // Go through code, noting interferences
281: {
282: Iterator codeIt = body.getUnits().iterator();
283:
284: while (codeIt.hasNext()) {
285: Unit unit = (Unit) codeIt.next();
286:
287: List liveLocalsAtUnit = liveLocals
288: .getLiveLocalsAfter(unit);
289:
290: // Note interferences if this stmt is a definition
291: {
292: List defBoxes = unit.getDefBoxes();
293:
294: if (!defBoxes.isEmpty()) {
295:
296: if (!(defBoxes.size() == 1))
297: throw new RuntimeException(
298: "invalid number of def boxes");
299:
300: if (((ValueBox) defBoxes.get(0)).getValue() instanceof Local) {
301: Local defLocal = (Local) ((ValueBox) defBoxes
302: .get(0)).getValue();
303: Iterator localIt = liveLocalsAtUnit
304: .iterator();
305:
306: while (localIt.hasNext()) {
307: Local otherLocal = (Local) localIt
308: .next();
309:
310: if (localToGroup
311: .get(otherLocal)
312: .equals(
313: localToGroup
314: .get(defLocal)))
315: setInterference(defLocal,
316: otherLocal);
317: }
318: }
319: }
320:
321: }
322: }
323: }
324: }
325:
326: public boolean localsInterfere(Local l1, Local l2) {
327: return localToLocals.get(l1).contains(l2);
328: }
329:
330: public void setInterference(Local l1, Local l2) {
331: localToLocals.get(l1).add(l2);
332: localToLocals.get(l2).add(l1);
333: }
334:
335: public boolean isEmpty() {
336: return localToLocals.isEmpty();
337: }
338:
339: Local[] getInterferencesOf(Local l) {
340: Object[] objects = localToLocals.get(l).toArray();
341: Local[] locals = new Local[objects.length];
342:
343: for (int i = 0; i < objects.length; i++)
344: locals[i] = (Local) objects[i];
345:
346: return locals;
347: }
348: }
349: }
350:
351: /** Binds together a String and a Group. */
352: class StringGroupPair {
353: String string;
354: Object group;
355:
356: public StringGroupPair(String s, Object g) {
357: string = s;
358: group = g;
359: }
360:
361: public boolean equals(Object p) {
362: if (p instanceof StringGroupPair) {
363: return ((StringGroupPair) p).string.equals(this .string)
364: && ((StringGroupPair) p).group.equals(this .group);
365: }
366:
367: return false;
368: }
369:
370: public int hashCode() {
371: return string.hashCode() * 101 + group.hashCode() + 17;
372: }
373: }
|