001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2003 Navindra Umanee <navindra@cs.mcgill.ca>
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: package soot.shimple;
021:
022: import soot.*;
023: import soot.options.Options;
024: import soot.jimple.*;
025: import soot.shimple.internal.*;
026: import soot.util.*;
027: import soot.toolkits.scalar.ValueUnitPair;
028: import java.util.*;
029:
030: /**
031: * Contains the constructors for the components of the SSA Shimple
032: * grammar. Methods are available to construct Shimple from
033: * Jimple/Shimple, create Phi nodes, and converting back from
034: * Shimple to Jimple.
035: *
036: * <p> This should normally be used in conjunction with the
037: * constructor methods from soot.jimple.Jimple.
038: *
039: * <p> Miscellaneous utility functions are also available in this
040: * class.
041: *
042: * @author Navindra Umanee
043: * @see soot.jimple.Jimple
044: * @see <a
045: * href="http://citeseer.nj.nec.com/cytron91efficiently.html">Efficiently
046: * Computing Static Single Assignment Form and the Control Dependence
047: * Graph</a>
048: **/
049: public class Shimple {
050: public static final String IFALIAS = "IfAlias";
051: public static final String MAYMODIFY = "MayModify";
052: public static final String PHI = "Phi";
053: public static final String PI = "Pi";
054: public static final String PHASE = "shimple";
055:
056: public Shimple(Singletons.Global g) {
057: }
058:
059: public static Shimple v() {
060: return G.v().soot_shimple_Shimple();
061: }
062:
063: /**
064: * Returns an empty ShimpleBody associated with method m, using
065: * default phase options.
066: **/
067: public ShimpleBody newBody(SootMethod m) {
068: Map options = PhaseOptions.v().getPhaseOptions(PHASE);
069: return new ShimpleBody(m, options);
070: }
071:
072: /**
073: * Returns an empty ShimpleBody associated with method m, using
074: * provided option map.
075: **/
076: public ShimpleBody newBody(SootMethod m, Map options) {
077: return new ShimpleBody(m, options);
078: }
079:
080: /**
081: * Returns a ShimpleBody constructed from b, using default phase
082: * options.
083: **/
084: public ShimpleBody newBody(Body b) {
085: Map options = PhaseOptions.v().getPhaseOptions(PHASE);
086: return new ShimpleBody(b, options);
087: }
088:
089: /**
090: * Returns a ShimpleBody constructed from b, using provided option
091: * Map.
092: **/
093: public ShimpleBody newBody(Body b, Map options) {
094: return new ShimpleBody(b, options);
095: }
096:
097: /**
098: * Create a trivial PhiExpr, where preds are an ordered list of
099: * the control predecessor Blocks of the Phi expression. Instead
100: * of a list of blocks, you may provide a list of the tail Units
101: * from the corresponding blocks.
102: **/
103: public PhiExpr newPhiExpr(Local leftLocal, List preds) {
104: return new SPhiExpr(leftLocal, preds);
105: }
106:
107: public PiExpr newPiExpr(Local local, Unit predicate,
108: Object targetKey) {
109: return new SPiExpr(local, predicate, targetKey);
110: }
111:
112: /**
113: * Create a PhiExpr with the provided list of Values (Locals or
114: * Constants) and the corresponding control flow predecessor
115: * Blocks. Instead of a list of predecessor blocks, you may
116: * provide a list of the tail Units from the corresponding blocks.
117: **/
118: public PhiExpr newPhiExpr(List<Value> args, List<Unit> preds) {
119: return new SPhiExpr(args, preds);
120: }
121:
122: /**
123: * Constructs a JimpleBody from a ShimpleBody.
124: *
125: * @see soot.options.ShimpleOptions
126: **/
127: public JimpleBody newJimpleBody(ShimpleBody body) {
128: return body.toJimpleBody();
129: }
130:
131: /**
132: * Returns true if the value is a Phi expression, false otherwise.
133: **/
134: public static boolean isPhiExpr(Value value) {
135: return (value instanceof PhiExpr);
136: }
137:
138: /**
139: * Returns true if the unit is a Phi node, false otherwise.
140: **/
141: public static boolean isPhiNode(Unit unit) {
142: return getPhiExpr(unit) == null ? false : true;
143: }
144:
145: /**
146: * Returns the corresponding PhiExpr if the unit is a Phi node,
147: * null otherwise.
148: **/
149: public static PhiExpr getPhiExpr(Unit unit) {
150: if (!(unit instanceof AssignStmt))
151: return null;
152:
153: Value right = ((AssignStmt) unit).getRightOp();
154:
155: if (isPhiExpr(right))
156: return (PhiExpr) right;
157:
158: return null;
159: }
160:
161: public static boolean isPiExpr(Value value) {
162: return (value instanceof PiExpr);
163: }
164:
165: public static boolean isPiNode(Unit unit) {
166: return getPiExpr(unit) == null ? false : true;
167: }
168:
169: public static PiExpr getPiExpr(Unit unit) {
170: if (!(unit instanceof AssignStmt))
171: return null;
172:
173: Value right = ((AssignStmt) unit).getRightOp();
174:
175: if (isPiExpr(right))
176: return (PiExpr) right;
177:
178: return null;
179: }
180:
181: /**
182: * Returns the corresponding left Local if the unit is a Shimple node,
183: * null otherwise.
184: **/
185: public static Local getLhsLocal(Unit unit) {
186: if (!(unit instanceof AssignStmt))
187: return null;
188:
189: Value right = ((AssignStmt) unit).getRightOp();
190:
191: if (right instanceof ShimpleExpr) {
192: Value left = ((AssignStmt) unit).getLeftOp();
193: return (Local) left;
194: }
195:
196: return null;
197: }
198:
199: /**
200: * If you are removing a Unit from a Unit chain which contains
201: * PhiExpr's, you might want to call this utility function in
202: * order to update any PhiExpr pointers to the Unit to point to
203: * the Unit's predecessor(s). This function will not modify
204: * "branch target" UnitBoxes.
205: *
206: * <p> Normally you should not have to call this function
207: * directly, since patching is taken care of Shimple's internal
208: * implementation of PatchingChain.
209: **/
210: public static void redirectToPreds(Body body, Unit remove) {
211: boolean debug = Options.v().debug();
212: if (body instanceof ShimpleBody)
213: debug |= ((ShimpleBody) body).getOptions().debug();
214:
215: Chain units = body.getUnits();
216:
217: /* Determine whether we should continue processing or not. */
218:
219: Iterator pointersIt = remove.getBoxesPointingToThis()
220: .iterator();
221:
222: if (!pointersIt.hasNext())
223: return;
224:
225: while (pointersIt.hasNext()) {
226: UnitBox pointer = (UnitBox) pointersIt.next();
227:
228: // a PhiExpr may be involved, hence continue processing.
229: // note that we will use the value of "pointer" and
230: // continue iteration from where we left off.
231: if (!pointer.isBranchTarget())
232: break;
233:
234: // no PhiExpr's are involved, abort
235: if (!pointersIt.hasNext())
236: return;
237: }
238:
239: /* Ok, continuing... */
240:
241: Set<Unit> preds = new HashSet<Unit>();
242: Set<PhiExpr> phis = new HashSet<PhiExpr>();
243:
244: // find fall-through pred
245: if (!remove.equals(units.getFirst())) {
246: Unit possiblePred = (Unit) units.getPredOf(remove);
247: if (possiblePred.fallsThrough())
248: preds.add(possiblePred);
249: }
250:
251: // find the rest of the preds and all Phi's that point to remove
252: Iterator unitsIt = units.iterator();
253: while (unitsIt.hasNext()) {
254: Unit unit = (Unit) unitsIt.next();
255: Iterator targetsIt = unit.getUnitBoxes().iterator();
256: while (targetsIt.hasNext()) {
257: UnitBox targetBox = (UnitBox) targetsIt.next();
258:
259: if (remove.equals(targetBox.getUnit())) {
260: if (targetBox.isBranchTarget())
261: preds.add(unit);
262: else {
263: PhiExpr phiExpr = Shimple.getPhiExpr(unit);
264: if (phiExpr != null)
265: phis.add(phiExpr);
266: }
267: }
268: }
269: }
270:
271: /* sanity check */
272:
273: if (phis.size() == 0) {
274: if (debug)
275: G.v().out.println("Warning: Orphaned UnitBoxes to "
276: + remove
277: + "? Shimple.redirectToPreds is giving up.");
278: return;
279: }
280:
281: if (preds.size() == 0) {
282: if (debug)
283: G.v().out
284: .println("Warning: Shimple.redirectToPreds couldn't find any predecessors for "
285: + remove
286: + " in "
287: + body.getMethod()
288: + ".");
289:
290: if (!remove.equals(units.getFirst())) {
291: Unit pred = (Unit) units.getPredOf(remove);
292: if (debug)
293: G.v().out
294: .println("Warning: Falling back to immediate chain predecessor: "
295: + pred + ".");
296: preds.add(pred);
297: } else if (!remove.equals(units.getLast())) {
298: Unit succ = (Unit) units.getSuccOf(remove);
299: if (debug)
300: G.v().out
301: .println("Warning: Falling back to immediate chain successor: "
302: + succ + ".");
303: preds.add(succ);
304: } else
305: throw new RuntimeException("Assertion failed.");
306: }
307:
308: /* At this point we have found all the preds and relevant Phi's */
309:
310: /* Each Phi needs an argument for each pred. */
311: Iterator<PhiExpr> phiIt = phis.iterator();
312: while (phiIt.hasNext()) {
313: PhiExpr phiExpr = phiIt.next();
314: ValueUnitPair argBox = phiExpr.getArgBox(remove);
315:
316: if (argBox == null)
317: throw new RuntimeException("Assertion failed.");
318:
319: // now we've got the value!
320: Value arg = argBox.getValue();
321: phiExpr.removeArg(argBox);
322:
323: // add new arguments to Phi
324: Iterator<Unit> predsIt = preds.iterator();
325: while (predsIt.hasNext()) {
326: Unit pred = predsIt.next();
327: phiExpr.addArg(arg, pred);
328: }
329: }
330: }
331:
332: /**
333: * Redirects PhiExpr pointers to the given Unit to the new Unit.
334: *
335: * <p> Normally you should not have to call this function
336: * directly, since patching is taken care of Shimple's internal
337: * implementation of PatchingChain.
338: **/
339: public static void redirectPointers(Unit oldLocation,
340: Unit newLocation) {
341: List boxesPointing = oldLocation.getBoxesPointingToThis();
342:
343: // important to change this to an array to have a static copy
344: Object[] boxes = boxesPointing.toArray();
345:
346: for (Object element : boxes) {
347: UnitBox box = (UnitBox) element;
348:
349: if (box.getUnit() != oldLocation)
350: throw new RuntimeException(
351: "Something weird's happening");
352:
353: if (!box.isBranchTarget())
354: box.setUnit(newLocation);
355: }
356: }
357: }
|