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: package soot.jbco.jimpleTransformations;
021:
022: import java.util.*;
023:
024: import soot.*;
025: import soot.jbco.*;
026: import soot.util.*;
027: import soot.jimple.*;
028: import soot.BodyTransformer;
029: import soot.jbco.util.*;
030:
031: /**
032: * @author Michael Batchelder
033: *
034: * Created on 6-Mar-2006
035: */
036:
037: // when shifting, add multiple of 32 or 64 to the shift value, since it will
038: // have no effect
039: // shift negatively to confuse things further?
040: // look into calculating operational cost and limiting to those transforms that
041: // will
042: // not hurt the speed of the program. Empirically: 4 adds/shifts == 1 mult?
043: public class ArithmeticTransformer extends BodyTransformer implements
044: IJbcoTransform {
045:
046: private static int mulPerformed = 0;
047:
048: private static int divPerformed = 0;
049:
050: private static int total = 0;
051:
052: public static String dependancies[] = new String[] { "jtp.jbco_cae2bo" };
053:
054: public String[] getDependancies() {
055: return dependancies;
056: }
057:
058: public static String name = "jtp.jbco_cae2bo";
059:
060: public String getName() {
061: return name;
062: }
063:
064: protected void internalTransform(Body b, String phaseName,
065: Map options) {
066: int weight = soot.jbco.Main.getWeight(phaseName, b.getMethod()
067: .getSignature());
068: if (weight == 0)
069: return;
070:
071: PatchingChain units = b.getUnits();
072:
073: int localCount = 0;
074: Chain locals = b.getLocals();
075: if (output)
076: out.println("*** Performing Arithmetic Transformation on "
077: + b.getMethod().getSignature());
078:
079: Iterator it = units.snapshotIterator();
080: while (it.hasNext()) {
081: Unit u = (Unit) it.next();
082: if (u instanceof AssignStmt) {
083: AssignStmt as = (AssignStmt) u;
084: Value v = as.getRightOp();
085: if (v instanceof MulExpr) {
086: total++;
087:
088: MulExpr me = (MulExpr) v;
089: Value op1 = me.getOp1();
090: Value op = null, op2 = me.getOp2();
091: NumericConstant nc = null;
092: if (op1 instanceof NumericConstant) {
093: nc = (NumericConstant) op1;
094: op = op2;
095: } else if (op2 instanceof NumericConstant) {
096: nc = (NumericConstant) op2;
097: op = op1;
098: }
099:
100: if (nc != null) {
101: if (output)
102: out.println("Considering: " + as + "\r");
103:
104: Type opType = op.getType();
105: int max = opType instanceof IntType ? 32
106: : opType instanceof LongType ? 64 : 0;
107:
108: if (max != 0) {
109: Object shft_rem[] = checkNumericValue(nc);
110: if (shft_rem[0] != null
111: && ((Integer) shft_rem[0])
112: .intValue() < max
113: && Rand.getInt(10) <= weight) {
114: List<Unit> unitsBuilt = new ArrayList<Unit>();
115: int rand = Rand.getInt(16);
116: int shift = ((Integer) shft_rem[0])
117: .intValue();
118: boolean neg = ((Boolean) shft_rem[2])
119: .booleanValue();
120: if (rand % 2 == 0) {
121: shift += rand * max;
122: } else {
123: shift -= rand * max;
124: }
125:
126: Expr e = null;
127: if (shft_rem[1] != null) { // if there is an additive floating
128: // component
129: Local tmp2 = null, tmp1 = Jimple
130: .v()
131: .newLocal(
132: "__tmp_shft_lcl"
133: + localCount++,
134: opType);
135: locals.add(tmp1);
136:
137: // shift the integral portion
138: Unit newU = Jimple
139: .v()
140: .newAssignStmt(
141: tmp1,
142: Jimple
143: .v()
144: .newShlExpr(
145: op,
146: IntConstant
147: .v(shift)));
148: unitsBuilt.add(newU);
149: units.insertBefore(newU, u);
150:
151: // grab remainder (that not part of the 2^x)
152: double rem = ((Double) shft_rem[1])
153: .doubleValue();
154: if (rem != 1) {
155: if (rem == ((int) rem)
156: && opType instanceof IntType)
157: nc = IntConstant
158: .v((int) rem);
159: else if (rem == ((long) rem)
160: && opType instanceof LongType)
161: nc = LongConstant
162: .v((long) rem);
163: else
164: nc = DoubleConstant.v(rem);
165:
166: if (nc instanceof DoubleConstant
167: && !(opType instanceof DoubleType)) {
168: tmp2 = Jimple
169: .v()
170: .newLocal(
171: "__tmp_shft_lcl"
172: + localCount++,
173: DoubleType
174: .v());
175: locals.add(tmp2);
176:
177: newU = Jimple
178: .v()
179: .newAssignStmt(
180: tmp2,
181: Jimple
182: .v()
183: .newCastExpr(
184: op,
185: DoubleType
186: .v()));
187: unitsBuilt.add(newU);
188: units.insertBefore(newU, u);
189:
190: newU = Jimple
191: .v()
192: .newAssignStmt(
193: tmp2,
194: Jimple
195: .v()
196: .newMulExpr(
197: tmp2,
198: nc));
199: } else {
200: tmp2 = Jimple
201: .v()
202: .newLocal(
203: "__tmp_shft_lcl"
204: + localCount++,
205: nc
206: .getType());
207: locals.add(tmp2);
208: newU = Jimple
209: .v()
210: .newAssignStmt(
211: tmp2,
212: Jimple
213: .v()
214: .newMulExpr(
215: op,
216: nc));
217: }
218: unitsBuilt.add(newU);
219: units.insertBefore(newU, u);
220: }
221: if (tmp2 == null) {
222: e = Jimple.v().newAddExpr(tmp1,
223: op);
224: } else if (tmp2.getType()
225: .getClass() != tmp1
226: .getType().getClass()) {
227: Local tmp3 = Jimple
228: .v()
229: .newLocal(
230: "__tmp_shft_lcl"
231: + localCount++,
232: tmp2.getType());
233: locals.add(tmp3);
234:
235: newU = Jimple
236: .v()
237: .newAssignStmt(
238: tmp3,
239: Jimple
240: .v()
241: .newCastExpr(
242: tmp1,
243: tmp2
244: .getType()));
245: unitsBuilt.add(newU);
246: units.insertBefore(newU, u);
247:
248: e = Jimple.v().newAddExpr(tmp3,
249: tmp2);
250: } else {
251: e = Jimple.v().newAddExpr(tmp1,
252: tmp2);
253: }
254: } else {
255: e = Jimple.v().newShlExpr(op,
256: IntConstant.v(shift));
257: }
258:
259: if (e.getType().getClass() != as
260: .getLeftOp().getType()
261: .getClass()) {
262: Local tmp = Jimple.v().newLocal(
263: "__tmp_shft_lcl"
264: + localCount++,
265: e.getType());
266: locals.add(tmp);
267: Unit newU = Jimple.v()
268: .newAssignStmt(tmp, e);
269: unitsBuilt.add(newU);
270: units.insertAfter(newU, u);
271:
272: e = Jimple.v().newCastExpr(tmp,
273: as.getLeftOp().getType());
274: }
275:
276: as.setRightOp(e);
277: unitsBuilt.add(as);
278: if (neg) {
279: Unit newU = Jimple
280: .v()
281: .newAssignStmt(
282: as.getLeftOp(),
283: Jimple
284: .v()
285: .newNegExpr(
286: as
287: .getLeftOp()));
288: unitsBuilt.add(newU);
289: units.insertAfter(newU, u);
290: }
291:
292: mulPerformed++;
293:
294: if (output) {
295: System.out.println(" after as: ");
296: Iterator<Unit> ait = unitsBuilt
297: .iterator();
298: while (ait.hasNext()) {
299: Unit uu = ait.next();
300: System.out
301: .println("\t"
302: + uu
303: + "\ttype : "
304: + (uu instanceof AssignStmt ? ((AssignStmt) uu)
305: .getLeftOp()
306: .getType()
307: .toString()
308: : ""));
309: }
310: }
311: }
312: }
313: }
314: } else if (v instanceof DivExpr) {
315: total++;
316: DivExpr de = (DivExpr) v;
317: Value op2 = de.getOp2();
318: NumericConstant nc = null;
319: if (op2 instanceof NumericConstant) {
320: nc = (NumericConstant) op2;
321:
322: if (nc != null) {
323: Type opType = de.getOp1().getType();
324: int max = opType instanceof IntType ? 32
325: : opType instanceof LongType ? 64
326: : 0;
327:
328: if (max != 0) {
329: Object shft_rem[] = checkNumericValue(nc);
330: if (shft_rem[0] != null
331: && ((Integer) shft_rem[0])
332: .intValue() < max
333: && Rand.getInt(10) <= weight) {
334: List<Unit> unitsBuilt = new ArrayList<Unit>();
335: int rand = Rand.getInt(16);
336: int shift = ((Integer) shft_rem[0])
337: .intValue();
338: boolean neg = ((Boolean) shft_rem[2])
339: .booleanValue();
340: if (Rand.getInt() % 2 == 0) {
341: shift += rand * max;
342: } else {
343: shift -= rand * max;
344: }
345:
346: Expr e = Jimple.v().newShrExpr(
347: de.getOp1(),
348: IntConstant.v(shift));
349:
350: if (e.getType().getClass() != as
351: .getLeftOp().getType()
352: .getClass()) {
353: Local tmp = Jimple
354: .v()
355: .newLocal(
356: "__tmp_shft_lcl"
357: + localCount++,
358: e.getType());
359: locals.add(tmp);
360: Unit newU = Jimple.v()
361: .newAssignStmt(tmp, e);
362: unitsBuilt.add(newU);
363: units.insertAfter(newU, u);
364:
365: e = Jimple.v().newCastExpr(
366: tmp,
367: as.getLeftOp()
368: .getType());
369: }
370:
371: as.setRightOp(e);
372: unitsBuilt.add(as);
373: if (neg) {
374: Unit newU = Jimple
375: .v()
376: .newAssignStmt(
377: as.getLeftOp(),
378: Jimple
379: .v()
380: .newNegExpr(
381: as
382: .getLeftOp()));
383: unitsBuilt.add(newU);
384: units.insertAfter(newU, u);
385: }
386:
387: divPerformed++;
388:
389: if (output) {
390: System.out
391: .println(" after as: ");
392: Iterator<Unit> ait = unitsBuilt
393: .iterator();
394: while (ait.hasNext()) {
395: Unit uu = ait.next();
396: System.out
397: .println("\t"
398: + uu
399: + "\ttype : "
400: + (uu instanceof AssignStmt ? ((AssignStmt) uu)
401: .getLeftOp()
402: .getType()
403: .toString()
404: : ""));
405: }
406: }
407: }
408: }
409: }
410: }
411: }
412: }
413: }
414: }
415:
416: public void outputSummary() {
417: out.println("Replaced mul/div expressions: "
418: + (divPerformed + mulPerformed));
419: out.println("Total mul/div expressions: " + total);
420: }
421:
422: private Object[] checkNumericValue(NumericConstant nc) {
423: Double d = null;
424: Object shift[] = new Object[3];
425: if (nc instanceof IntConstant) {
426: d = new Double(((IntConstant) nc).value);
427: } else if (nc instanceof DoubleConstant) {
428: d = new Double(((DoubleConstant) nc).value);
429: } else if (nc instanceof FloatConstant) {
430: d = new Double(((FloatConstant) nc).value);
431: } else if (nc instanceof LongConstant) {
432: d = new Double(((LongConstant) nc).value);
433: }
434:
435: if (d != null) {
436: shift[2] = new Boolean(d.doubleValue() < 0);
437: double tmp[] = checkShiftValue(d.doubleValue());
438: if (tmp[0] != 0) {
439: shift[0] = new Integer((int) tmp[0]);
440: if (tmp[1] != 0)
441: shift[1] = new Double(tmp[1]);
442: else
443: shift[1] = null;
444: } else
445: d = null;
446: }
447:
448: if (d == null) {
449: shift[0] = null;
450: shift[1] = null;
451: }
452:
453: return shift;
454: }
455:
456: private double[] checkShiftValue(double val) {
457:
458: double shift[] = new double[2];
459: if (val == 0 || val == 1 || val == -1) {
460: shift[0] = 0;
461: shift[1] = 0;
462: } else {
463: double shift_dbl = Math.log(val) / Math.log(2);
464: double shift_int = Math.rint(shift_dbl);
465: if (shift_dbl == shift_int) {
466: shift[1] = 0;
467: } else {
468: if (Math.pow(2, shift_int) > val)
469: shift_int--;
470: shift[1] = val - Math.pow(2, shift_int);
471: }
472: shift[0] = shift_int;
473: }
474:
475: return shift;
476: }
477: }
|