001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1999 Patrice Pominville, 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-2003.
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.graph;
027:
028: import soot.*;
029: import soot.util.*;
030: import java.util.*;
031: import java.util.Map.Entry;
032:
033: import soot.options.Options;
034:
035: /**
036: * <p>
037: * Represents a CFG where the nodes are {@link Unit} instances and
038: * edges represent unexceptional and (possibly) exceptional control
039: * flow between <tt>Unit</tt>s.</p>
040: *
041: * <p>
042: * This is an abstract class, providing the facilities used to build
043: * CFGs for specific purposes.</p>
044: */
045:
046: public abstract class UnitGraph implements DirectedGraph<Unit> {
047: List heads;
048: List tails;
049:
050: protected Map unitToSuccs;
051: protected Map unitToPreds;
052: protected SootMethod method;
053: protected Body body;
054: protected Chain unitChain;
055:
056: /**
057: * Performs the work that is required to construct any sort of
058: * <tt>UnitGraph</tt>.
059: *
060: * @param body The body of the method for which to construct a
061: * control flow graph.
062: */
063: protected UnitGraph(Body body) {
064: this .body = body;
065: unitChain = body.getUnits();
066: method = body.getMethod();
067: if (Options.v().verbose())
068: G.v().out.println("[" + method.getName()
069: + "] Constructing " + this .getClass().getName()
070: + "...");
071:
072: }
073:
074: /**
075: * Utility method for <tt>UnitGraph</tt> constructors. It computes
076: * the edges corresponding to unexceptional control flow.
077: *
078: * @param unitToSuccs A {@link Map} from {@link Unit}s to
079: * {@link List}s of {@link Unit}s. This is
080: * an ``out parameter''; callers must pass an empty
081: * {@link Map}. <tt>buildUnexceptionalEdges</tt> will
082: * add a mapping for every <tt>Unit</tt> in the
083: * body to a list of its unexceptional successors.
084: *
085: * @param unitToPreds A {@link Map} from {@link Unit}s to
086: * {@link List}s of {@link Unit}s. This is an
087: * ``out parameter''; callers must pass an empty
088: * {@link Map}. <tt>buildUnexceptionalEdges</tt> will
089: * add a mapping for every <tt>Unit</tt> in the body
090: * to a list of its unexceptional predecessors.
091: */
092: protected void buildUnexceptionalEdges(Map unitToSuccs,
093: Map unitToPreds) {
094:
095: // Initialize the predecessor sets to empty
096: for (Iterator unitIt = unitChain.iterator(); unitIt.hasNext();) {
097: unitToPreds.put(unitIt.next(), new ArrayList());
098: }
099:
100: Iterator unitIt = unitChain.iterator();
101: Unit currentUnit, nextUnit;
102:
103: nextUnit = unitIt.hasNext() ? (Unit) unitIt.next() : null;
104:
105: while (nextUnit != null) {
106: currentUnit = nextUnit;
107: nextUnit = unitIt.hasNext() ? (Unit) unitIt.next() : null;
108:
109: List<Unit> successors = new ArrayList<Unit>();
110:
111: if (currentUnit.fallsThrough()) {
112: // Add the next unit as the successor
113: if (nextUnit != null) {
114: successors.add(nextUnit);
115: ((List) unitToPreds.get(nextUnit)).add(currentUnit);
116: }
117: }
118:
119: if (currentUnit.branches()) {
120: for (Iterator targetIt = currentUnit.getUnitBoxes()
121: .iterator(); targetIt.hasNext();) {
122: Unit target = ((UnitBox) targetIt.next()).getUnit();
123: // Arbitrary bytecode can branch to the same
124: // target it falls through to, so we screen for duplicates:
125: if (!successors.contains(target)) {
126: successors.add(target);
127: ((List) unitToPreds.get(target))
128: .add(currentUnit);
129: }
130: }
131: }
132:
133: // Store away successors
134: unitToSuccs.put(currentUnit, successors);
135: }
136: }
137:
138: /**
139: * <p>Utility method used in the construction of {@link UnitGraph}s, to be
140: * called only after the unitToPreds and unitToSuccs maps have
141: * been built.</p>
142: *
143: * <p><code>UnitGraph</code> provides an implementation of
144: * <code>buildHeadsAndTails()</code> which defines the graph's set
145: * of heads to include the first {@link Unit} in the graph's body,
146: * together with any other <tt>Unit</tt> which has no predecessors.
147: * It defines the graph's set of tails to include all
148: * <tt>Unit</tt>s with no successors. Subclasses of
149: * <code>UnitGraph</code> may override this method to change the
150: * criteria for classifying a node as a head or tail.</p>
151: */
152: protected void buildHeadsAndTails() {
153: List tailList = new ArrayList();
154: List headList = new ArrayList();
155:
156: for (Iterator unitIt = unitChain.iterator(); unitIt.hasNext();) {
157: Unit s = (Unit) unitIt.next();
158: List succs = (List) unitToSuccs.get(s);
159: if (succs.size() == 0) {
160: tailList.add(s);
161: }
162: List preds = (List) unitToPreds.get(s);
163: if (preds.size() == 0) {
164: headList.add(s);
165: }
166: }
167:
168: // Add the first Unit, even if it is the target of
169: // a branch.
170: Unit entryPoint = (Unit) unitChain.getFirst();
171: if (!headList.contains(entryPoint)) {
172: headList.add(entryPoint);
173: }
174:
175: tails = Collections.unmodifiableList(tailList);
176: heads = Collections.unmodifiableList(headList);
177: }
178:
179: /**
180: * Utility method that replaces the values of a {@link Map},
181: * which must be instances of {@link List}, with unmodifiable
182: * equivalents.
183: *
184: * @param map The map whose values are to be made unmodifiable.
185: */
186: protected static void makeMappedListsUnmodifiable(
187: Map<?, List<Unit>> map) {
188: for (Entry<?, List<Unit>> entry : map.entrySet()) {
189: List value = entry.getValue();
190: if (value.size() == 0) {
191: entry.setValue(Collections.EMPTY_LIST);
192: } else {
193: entry.setValue(Collections.unmodifiableList(value));
194: }
195: }
196: }
197:
198: /**
199: * Utility method that produces a new map from the {@link Unit}s
200: * of this graph's body to the union of the values stored in the
201: * two argument {@link Map}s, used to combine the maps of
202: * exceptional and unexceptional predecessors and successors into
203: * maps of all predecessors and successors. The values stored in
204: * both argument maps must be {@link List}s of {@link Unit}s,
205: * which are assumed not to contain any duplicate <tt>Unit</tt>s.
206: *
207: * @param mapA The first map to be combined.
208: *
209: * @param mapB The second map to be combined.
210: */
211: protected Map combineMapValues(Map mapA, Map mapB) {
212: // The duplicate screen
213: Map result = new HashMap(mapA.size() * 2 + 1, 0.7f);
214: for (Iterator chainIt = unitChain.iterator(); chainIt.hasNext();) {
215: Unit unit = (Unit) chainIt.next();
216: List listA = (List) mapA.get(unit);
217: if (listA == null) {
218: listA = Collections.EMPTY_LIST;
219: }
220: List listB = (List) mapB.get(unit);
221: if (listB == null) {
222: listB = Collections.EMPTY_LIST;
223: }
224:
225: int resultSize = listA.size() + listB.size();
226: if (resultSize == 0) {
227: result.put(unit, Collections.EMPTY_LIST);
228: } else {
229: List resultList = new ArrayList(resultSize);
230: Iterator listIt = null;
231: // As a minor optimization of the duplicate screening,
232: // copy the longer list first.
233: if (listA.size() >= listB.size()) {
234: resultList.addAll(listA);
235: listIt = listB.iterator();
236: } else {
237: resultList.addAll(listB);
238: listIt = listA.iterator();
239: }
240: while (listIt.hasNext()) {
241: Object element = listIt.next();
242: // It is possible for there to be both an exceptional
243: // and an unexceptional edge connecting two Units
244: // (though probably not in a class generated by
245: // javac), so we need to screen for duplicates. On the
246: // other hand, we expect most of these lists to have
247: // only one or two elements, so it doesn't seem worth
248: // the cost to build a Set to do the screening.
249: if (!resultList.contains(element)) {
250: resultList.add(element);
251: }
252: }
253: result.put(unit, Collections
254: .unmodifiableList(resultList));
255: }
256: }
257: return result;
258: }
259:
260: /**
261: * Utility method for adding an edge to maps representing the CFG.
262: *
263: * @param unitToSuccs The {@link Map} from {@link Unit}s to {@link List}s
264: * of their successors.
265: *
266: * @param unitToPreds The {@link Map} from {@link Unit}s to {@link List}s
267: * of their successors.
268: *
269: * @param head The {@link Unit} from which the edge starts.
270: *
271: * @param tail The {@link Unit} to which the edge flows.
272: */
273: protected void addEdge(Map unitToSuccs, Map unitToPreds, Unit head,
274: Unit tail) {
275: List headsSuccs = (List) unitToSuccs.get(head);
276: if (headsSuccs == null) {
277: headsSuccs = new ArrayList(3); // We expect this list to
278: // remain short.
279: unitToSuccs.put(head, headsSuccs);
280: }
281: if (!headsSuccs.contains(tail)) {
282: headsSuccs.add(tail);
283: List tailsPreds = (List) unitToPreds.get(tail);
284: if (tailsPreds == null) {
285: tailsPreds = new ArrayList();
286: unitToPreds.put(tail, tailsPreds);
287: }
288: tailsPreds.add(head);
289: }
290: }
291:
292: /**
293: * @return The body from which this UnitGraph was built.
294: *
295: * @see Body
296: */
297: public Body getBody() {
298: return body;
299: }
300:
301: /**
302: * Look for a path in graph, from def to use.
303: * This path has to lie inside an extended basic block
304: * (and this property implies uniqueness.). The path returned
305: * includes from and to.
306: *
307: * @param from start point for the path.
308: * @param to end point for the path.
309: * @return null if there is no such path.
310: */
311: public List<Unit> getExtendedBasicBlockPathBetween(Unit from,
312: Unit to) {
313: UnitGraph g = this ;
314:
315: // if this holds, we're doomed to failure!!!
316: if (g.getPredsOf(to).size() > 1)
317: return null;
318:
319: // pathStack := list of succs lists
320: // pathStackIndex := last visited index in pathStack
321: LinkedList<Unit> pathStack = new LinkedList<Unit>();
322: LinkedList<Integer> pathStackIndex = new LinkedList<Integer>();
323:
324: pathStack.add(from);
325: pathStackIndex.add(new Integer(0));
326:
327: int psiMax = (g.getSuccsOf(pathStack.get(0))).size();
328: int level = 0;
329: while (pathStackIndex.get(0).intValue() != psiMax) {
330: int p = (pathStackIndex.get(level)).intValue();
331:
332: List succs = g.getSuccsOf((pathStack.get(level)));
333: if (p >= succs.size()) {
334: // no more succs - backtrack to previous level.
335:
336: pathStack.remove(level);
337: pathStackIndex.remove(level);
338:
339: level--;
340: int q = pathStackIndex.get(level).intValue();
341: pathStackIndex.set(level, new Integer(q + 1));
342: continue;
343: }
344:
345: Unit betweenUnit = (Unit) (succs.get(p));
346:
347: // we win!
348: if (betweenUnit == to) {
349: pathStack.add(to);
350: return pathStack;
351: }
352:
353: // check preds of betweenUnit to see if we should visit its kids.
354: if (g.getPredsOf(betweenUnit).size() > 1) {
355: pathStackIndex.set(level, new Integer(p + 1));
356: continue;
357: }
358:
359: // visit kids of betweenUnit.
360: level++;
361: pathStackIndex.add(new Integer(0));
362: pathStack.add(betweenUnit);
363: }
364: return null;
365: }
366:
367: /* DirectedGraph implementation */
368: public List<Unit> getHeads() {
369: return heads;
370: }
371:
372: public List<Unit> getTails() {
373: return tails;
374: }
375:
376: public List<Unit> getPredsOf(Unit u) {
377: if (!unitToPreds.containsKey(u))
378: throw new NoSuchElementException("Invalid unit " + u);
379:
380: return (List) unitToPreds.get(u);
381: }
382:
383: public List<Unit> getSuccsOf(Unit u) {
384: List l = (List) unitToSuccs.get(u);
385: if (l == null)
386: throw new RuntimeException("Invalid unit " + u);
387: return l;
388: }
389:
390: public int size() {
391: return unitChain.size();
392: }
393:
394: public Iterator<Unit> iterator() {
395: return unitChain.iterator();
396: }
397:
398: public String toString() {
399: Iterator it = unitChain.iterator();
400: StringBuffer buf = new StringBuffer();
401: while (it.hasNext()) {
402: Unit u = (Unit) it.next();
403: buf.append("// preds: " + getPredsOf(u) + "\n");
404: buf.append(u.toString() + '\n');
405: buf.append("// succs " + getSuccsOf(u) + "\n");
406: }
407: return buf.toString();
408: }
409: }
|