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.bafTransformations;
021:
022: import java.util.*;
023:
024: import soot.*;
025: import soot.baf.*;
026: import soot.jbco.IJbcoTransform;
027: import soot.jimple.*;
028: import soot.util.*;
029: import soot.toolkits.graph.*;
030:
031: /**
032: * @author Michael Batchelder
033: *
034: * Created on 12-May-2006
035: */
036: public class FindDuplicateSequences extends BodyTransformer implements
037: IJbcoTransform {
038:
039: int totalcounts[] = new int[512];
040:
041: public static String dependancies[] = new String[] {
042: "bb.jbco_j2bl", "bb.jbco_rds", "bb.jbco_ful", "bb.lp" };
043:
044: public String[] getDependancies() {
045: return dependancies;
046: }
047:
048: public static String name = "bb.jbco_rds";
049:
050: public String getName() {
051: return name;
052: }
053:
054: public void outputSummary() {
055: out.println("Duplicate Sequences:");
056: for (int count = totalcounts.length - 1; count >= 0; count--)
057: if (totalcounts[count] > 0)
058: out.println("\t" + count + " total: "
059: + totalcounts[count]);
060: }
061:
062: protected void internalTransform(Body b, String phaseName,
063: Map options) {
064:
065: int weight = soot.jbco.Main.getWeight(phaseName, b.getMethod()
066: .getSignature());
067: if (weight == 0)
068: return;
069:
070: if (output)
071: out.println("Checking " + b.getMethod().getName()
072: + " for duplicate sequences..");
073:
074: ArrayList<Unit> illegalUnits = new ArrayList<Unit>();
075: ArrayList seenUnits = new ArrayList();
076: ArrayList workList = new ArrayList();
077: PatchingChain units = b.getUnits();
078: BriefUnitGraph bug = new BriefUnitGraph(b);
079: workList.addAll(bug.getHeads());
080: while (workList.size() > 0) {
081: Unit u = (Unit) workList.remove(0);
082: if (seenUnits.contains(u))
083: continue;
084:
085: if (u instanceof NewInst) {
086: RefType t = ((NewInst) u).getBaseType();
087: ArrayList tmpWorkList = new ArrayList();
088: tmpWorkList.add(u);
089: while (tmpWorkList.size() > 0) {
090: Unit v = (Unit) tmpWorkList.remove(0);
091:
092: // horrible approximatin about which init call belongs to which new
093: if (v instanceof SpecialInvokeInst) {
094: SpecialInvokeInst si = (SpecialInvokeInst) v;
095: if (si.getMethodRef().getSignature().indexOf(
096: "void <init>") < 0
097: || si.getMethodRef().declaringClass() != t
098: .getSootClass())
099: tmpWorkList.addAll(bug.getSuccsOf(v));
100: } else {
101: tmpWorkList.addAll(bug.getSuccsOf(v));
102: }
103: illegalUnits.add(v);
104: }
105: }
106:
107: seenUnits.add(u);
108: workList.addAll(bug.getSuccsOf(u));
109: }
110: seenUnits = null;
111:
112: int controlLocalIndex = 0;
113: int longestSeq = (units.size() / 2) - 1;
114: if (longestSeq > 20)
115: longestSeq = 20;
116:
117: Local controlLocal = null;
118: Chain bLocals = b.getLocals();
119: int counts[] = new int[longestSeq + 1];
120: //ArrayList protectedUnits = new ArrayList();
121: HashMap bafToJLocals = soot.jbco.Main.methods2Baf2JLocals.get(b
122: .getMethod());
123: boolean changed = true;
124: HashMap stackHeightsBefore = null;
125: for (int count = longestSeq; count > 2; count--) {
126: Object uArry[] = units.toArray();
127: if (uArry.length <= 0)
128: return;
129:
130: //int count = uArry.length > 100 ? 4 : uArry.length > 50 ? 3 : 2;
131:
132: ArrayList<ArrayList<Unit>> candidates = new ArrayList<ArrayList<Unit>>();
133: ArrayList<Object> unitIDs = new ArrayList<Object>();
134:
135: if (changed) {
136: stackHeightsBefore = StackTypeHeightCalculator
137: .calculateStackHeights(b, bafToJLocals);
138: bug = StackTypeHeightCalculator.bug;
139: changed = false;
140: }
141:
142: LOOP: for (int i = 0; i < uArry.length; i++) {
143: unitIDs.add(uArry[i]);
144:
145: if (i + count > uArry.length)
146: continue;
147:
148: ArrayList<Unit> seq = new ArrayList<Unit>();
149: for (int j = 0; j < count; j++) {
150: Unit u = (Unit) uArry[i + j];
151: if (u instanceof IdentityInst
152: || u instanceof ReturnInst
153: || illegalUnits.contains(u))
154: break;
155:
156: // don't allow units within the sequence that have more than one
157: // predecessor that is not _within_ the sequence
158: if (j > 0) {
159: List preds = bug.getPredsOf(u);
160: if (preds.size() > 0) {
161: int found = 0;
162: Iterator pit = preds.iterator();
163: while (pit.hasNext()) {
164: Unit p = (Unit) pit.next();
165: for (int jj = 0; jj < count; jj++) {
166: if (p == uArry[i + jj]) {
167: found++;
168: break;
169: }
170: }
171: }
172: if (found < preds.size())
173: continue LOOP;
174: }
175: }
176:
177: seq.add(u);
178: }
179: if (seq.size() == count) {
180: if (seq.get(seq.size() - 1).fallsThrough())
181: candidates.add(seq);
182: }
183: }
184:
185: HashMap<ArrayList, ArrayList<ArrayList<Object>>> selected = new HashMap<ArrayList, ArrayList<ArrayList<Object>>>();
186: for (int i = 0; i < candidates.size(); i++) {
187: ArrayList seq = candidates.get(i);
188: ArrayList<ArrayList<Object>> matches = new ArrayList<ArrayList<Object>>();
189: for (int j = 0; j < (uArry.length - count); j++) {
190: if (overlap(uArry, seq, j, count))
191: continue;
192:
193: boolean found = false;
194: for (int k = 0; k < count; k++) {
195: Unit u = (Unit) seq.get(k);
196:
197: found = false;
198:
199: Unit v = (Unit) uArry[j + k];
200: if (!equalUnits(u, v, b)
201: || illegalUnits.contains(v))
202: break;
203:
204: if (k > 0) {
205: List preds = bug.getPredsOf(v);
206: if (preds.size() > 0) {
207: int fcount = 0;
208: Iterator pit = preds.iterator();
209: while (pit.hasNext()) {
210: Unit p = (Unit) pit.next();
211: for (int jj = 0; jj < count; jj++) {
212: if (p == uArry[j + jj]) {
213: fcount++;
214: break;
215: }
216: }
217: }
218: if (fcount < preds.size())
219: break;
220: }
221: }
222:
223: // No need to calc AFTER stack, since they are equal units
224: if (!stackHeightsBefore.get(u).equals(
225: stackHeightsBefore.get(v)))
226: break;
227:
228: found = true;
229: }
230:
231: if (found) {
232: ArrayList<Object> foundSeq = new ArrayList<Object>();
233: for (int m = 0; m < count; m++)
234: foundSeq.add(uArry[j + m]);
235: matches.add(foundSeq);
236: }
237: }
238:
239: if (matches.size() > 0) {
240: boolean done = false;
241: for (int x = 0; x < seq.size(); x++)
242: if (!unitIDs.contains(seq.get(x)))
243: done = true;
244: else
245: unitIDs.remove(seq.get(x));
246:
247: if (!done) {
248: matches = cullOverlaps(b, unitIDs, matches);
249: if (matches.size() > 0)
250: selected.put(seq, matches);
251: }
252: }
253: }
254:
255: if (selected.size() <= 0)
256: continue;
257:
258: Iterator<ArrayList> keys = selected.keySet().iterator();
259: while (keys.hasNext()) {
260: ArrayList key = keys.next();
261: ArrayList avalues = selected.get(key);
262: if (avalues.size() < 1
263: || soot.jbco.util.Rand.getInt(10) <= weight)
264: continue;
265:
266: changed = true;
267:
268: controlLocal = Baf.v().newLocal(
269: "controlLocalfordups" + controlLocalIndex,
270: IntType.v());
271: bLocals.add(controlLocal);
272: bafToJLocals.put(controlLocal, Jimple.v().newLocal(
273: "controlLocalfordups" + controlLocalIndex++,
274: IntType.v()));
275:
276: counts[key.size()] += avalues.size();
277:
278: ArrayList jumps = new ArrayList();
279:
280: Unit first = (Unit) key.get(0);
281: //protectedUnits.addAll(key);
282:
283: Unit store = Baf.v().newStoreInst(IntType.v(),
284: controlLocal);
285: //protectedUnits.add(store);
286:
287: units.insertBefore(store, first);
288:
289: Unit pushUnit = Baf.v().newPushInst(IntConstant.v(0));
290: //protectedUnits.add(pushUnit);
291:
292: units.insertBefore(pushUnit, store);
293:
294: int index = 1;
295: Iterator values = avalues.iterator();
296: while (values.hasNext()) {
297: ArrayList next = (ArrayList) values.next();
298: Unit jump = (Unit) units.getSuccOf(next.get(next
299: .size() - 1));
300: //protectedUnits.add(jump);
301:
302: Unit firstt = (Unit) next.get(0);
303: Unit storet = (Unit) store.clone();
304: //protectedUnits.add(storet);
305:
306: units.insertBefore(storet, firstt);
307:
308: pushUnit = Baf.v().newPushInst(
309: IntConstant.v(index++));
310: //protectedUnits.add(pushUnit);
311:
312: units.insertBefore(pushUnit, storet);
313:
314: Unit goUnit = Baf.v().newGotoInst(first);
315: //protectedUnits.add(goUnit);
316:
317: units.insertAfter(goUnit, storet);
318: jumps.add(jump);
319: }
320:
321: Unit insertAfter = (Unit) key.get(key.size() - 1);
322: //protectedUnits.add(insertAfter);
323:
324: Unit swUnit = Baf.v().newTableSwitchInst(
325: (Unit) units.getSuccOf(insertAfter), 1,
326: jumps.size(), jumps);
327: //protectedUnits.add(swUnit);
328:
329: units.insertAfter(swUnit, insertAfter);
330:
331: Unit loadUnit = Baf.v().newLoadInst(IntType.v(),
332: controlLocal);
333: //protectedUnits.add(loadUnit);
334:
335: units.insertAfter(loadUnit, insertAfter);
336:
337: values = avalues.iterator();
338: while (values.hasNext()) {
339: ArrayList next = (ArrayList) values.next();
340: units.removeAll(next);
341: //protectedUnits.removeAll(next);
342: }
343: }
344: } // end of for loop for duplicate seq of various length
345:
346: boolean dupsExist = false;
347: if (output)
348: System.out.println("Duplicate Sequences for "
349: + b.getMethod().getName());
350:
351: for (int count = longestSeq; count >= 0; count--)
352: if (counts[count] > 0) {
353: if (output)
354: out.println(count + " total: " + counts[count]);
355: dupsExist = true;
356: totalcounts[count] += counts[count];
357: }
358:
359: if (!dupsExist) {
360: if (output)
361: out.println("\tnone");
362: } else if (debug) {
363: StackTypeHeightCalculator.calculateStackHeights(b);
364: }
365: }
366:
367: private boolean equalUnits(Object o1, Object o2, Body b) {
368: if (o1.getClass() != o2.getClass())
369: return false;
370:
371: // this is actually handled by the predecessor checks
372:
373: // if units are targets of different jumps then not equal
374: //if (!((Unit)o1).getBoxesPointingToThis().equals(
375: // ((Unit)o2).getBoxesPointingToThis()))
376: // return false;
377:
378: List<Trap> l1 = getTrapsForUnit(o1, b);
379: List<Trap> l2 = getTrapsForUnit(o2, b);
380: if (l1.size() != l2.size())
381: return false;
382: else {
383: for (int i = 0; i < l1.size(); i++)
384: if (l1.get(i) != l2.get(i))
385: return false;
386: }
387:
388: if (o1 instanceof NoArgInst)
389: return true;
390:
391: /*
392: if (o1 instanceof IncInst) {
393: IncInst ii = (IncInst)o1;
394: if (ii.getLocal() != ((IncInst)o2).getLocal() || ii.getConstant() != ((IncInst)o2).getConstant())
395: return false;
396: return true;
397: }*/
398:
399: if (o1 instanceof TargetArgInst) {
400: //return false;
401: //Maybe shouldn't allow duplicate target units?
402: if (o1 instanceof OpTypeArgInst)
403: return ((TargetArgInst) o1).getTarget() == ((TargetArgInst) o2)
404: .getTarget()
405: && ((OpTypeArgInst) o1).getOpType() == ((OpTypeArgInst) o2)
406: .getOpType();
407: else
408: return ((TargetArgInst) o1).getTarget() == ((TargetArgInst) o2)
409: .getTarget();
410: }
411:
412: if (o1 instanceof OpTypeArgInst)
413: return ((OpTypeArgInst) o1).getOpType() == ((OpTypeArgInst) o2)
414: .getOpType();
415:
416: if (o1 instanceof MethodArgInst)
417: return ((MethodArgInst) o1).getMethod() == ((MethodArgInst) o2)
418: .getMethod();
419:
420: if (o1 instanceof FieldArgInst)
421: return ((FieldArgInst) o1).getField() == ((FieldArgInst) o2)
422: .getField();
423:
424: if (o1 instanceof PrimitiveCastInst) {
425: return ((PrimitiveCastInst) o1).getFromType() == ((PrimitiveCastInst) o2)
426: .getFromType()
427: && ((PrimitiveCastInst) o1).getToType() == ((PrimitiveCastInst) o2)
428: .getToType();
429: }
430:
431: if (o1 instanceof DupInst)
432: return compareDups(o1, o2);
433:
434: if (o1 instanceof LoadInst)
435: return ((LoadInst) o1).getLocal() == ((LoadInst) o2)
436: .getLocal();
437:
438: if (o1 instanceof StoreInst)
439: return ((StoreInst) o1).getLocal() == ((StoreInst) o2)
440: .getLocal();
441:
442: if (o1 instanceof PushInst)
443: return equalConstants(((PushInst) o1).getConstant(),
444: ((PushInst) o2).getConstant());
445:
446: if (o1 instanceof IncInst)
447: if (equalConstants(((IncInst) o1).getConstant(),
448: ((IncInst) o2).getConstant()))
449: return (((IncInst) o1).getLocal() == ((IncInst) o2)
450: .getLocal());
451:
452: if (o1 instanceof InstanceCastInst)
453: return equalTypes(((InstanceCastInst) o1).getCastType(),
454: ((InstanceCastInst) o2).getCastType());
455:
456: if (o1 instanceof InstanceOfInst)
457: return equalTypes(((InstanceOfInst) o1).getCheckType(),
458: ((InstanceOfInst) o2).getCheckType());
459:
460: if (o1 instanceof NewArrayInst)
461: return equalTypes(((NewArrayInst) o1).getBaseType(),
462: ((NewArrayInst) o2).getBaseType());
463:
464: if (o1 instanceof NewInst)
465: return equalTypes(((NewInst) o1).getBaseType(),
466: ((NewInst) o2).getBaseType());
467:
468: if (o1 instanceof NewMultiArrayInst)
469: return equalTypes(((NewMultiArrayInst) o1).getBaseType(),
470: ((NewMultiArrayInst) o2).getBaseType())
471: && ((NewMultiArrayInst) o1).getDimensionCount() == ((NewMultiArrayInst) o2)
472: .getDimensionCount();
473:
474: if (o1 instanceof PopInst)
475: return ((PopInst) o1).getWordCount() == ((PopInst) o2)
476: .getWordCount();
477:
478: if (o1 instanceof SwapInst) {
479: return ((SwapInst) o1).getFromType() == ((SwapInst) o2)
480: .getFromType()
481: && ((SwapInst) o1).getToType() == ((SwapInst) o2)
482: .getToType();
483: }
484:
485: return false;
486: }
487:
488: private List<Trap> getTrapsForUnit(Object o, Body b) {
489: ArrayList<Trap> list = new ArrayList<Trap>();
490: Chain traps = b.getTraps();
491: if (traps.size() != 0) {
492: PatchingChain units = b.getUnits();
493: Iterator it = traps.iterator();
494: while (it.hasNext()) {
495: Trap t = (Trap) it.next();
496: Iterator tit = units.iterator(t.getBeginUnit(), t
497: .getEndUnit());
498: while (tit.hasNext()) {
499: if (tit.next() == o) {
500: list.add(t);
501: break;
502: }
503: }
504: }
505: }
506: return list;
507: }
508:
509: private boolean overlap(Object units[], List list, int idx,
510: int count) {
511: if (idx < 0 || list == null || list.size() == 0)
512: return false;
513:
514: Object first = list.get(0);
515: Object last = list.get(list.size() - 1);
516: for (int i = idx; i < idx + count; i++)
517: if (i < units.length
518: && (first == units[i] || last == units[i]))
519: return true;
520:
521: return false;
522: }
523:
524: private boolean equalConstants(Constant c1, Constant c2) {
525: Type t = c1.getType();
526: if (t != c2.getType())
527: return false;
528:
529: if (t instanceof IntType)
530: return ((IntConstant) c1).value == ((IntConstant) c2).value;
531:
532: if (t instanceof FloatType)
533: return ((FloatConstant) c1).value == ((FloatConstant) c2).value;
534:
535: if (t instanceof LongType)
536: return ((LongConstant) c1).value == ((LongConstant) c2).value;
537:
538: if (t instanceof DoubleType)
539: return ((DoubleConstant) c1).value == ((DoubleConstant) c2).value;
540:
541: if (c1 instanceof StringConstant
542: && c2 instanceof StringConstant)
543: return ((StringConstant) c1).value == ((StringConstant) c2).value;
544:
545: return c1 instanceof NullConstant && c2 instanceof NullConstant;
546: }
547:
548: private boolean compareDups(Object o1, Object o2) {
549: DupInst d1 = (DupInst) o1;
550: DupInst d2 = (DupInst) o2;
551:
552: List<Type> l1 = d1.getOpTypes();
553: List<Type> l2 = d2.getOpTypes();
554: for (int k = 0; k < 2; k++) {
555: if (k == 1) {
556: l1 = d1.getUnderTypes();
557: l2 = d2.getUnderTypes();
558: }
559: if (l1.size() != l2.size())
560: return false;
561:
562: for (int i = 0; i < l1.size(); i++)
563: if (l1.get(i) != l2.get(i))
564: return false;
565: }
566:
567: return true;
568: }
569:
570: private boolean equalTypes(Type t1, Type t2) {
571: if (t1 instanceof RefType) {
572: if (t2 instanceof RefType) {
573: // TODO: more discerning comparison here?
574: RefType rt1 = (RefType) t1;
575:
576: return rt1.compareTo(t2) == 0;
577: }
578: return false;
579: }
580:
581: if (t1 instanceof PrimType && t2 instanceof PrimType)
582: return t1.getClass() == t2.getClass();
583:
584: return false;
585: }
586:
587: private static ArrayList<ArrayList<Object>> cullOverlaps(Body b,
588: ArrayList<Object> ids, ArrayList<ArrayList<Object>> matches) {
589: ArrayList<ArrayList<Object>> newMatches = new ArrayList<ArrayList<Object>>();
590: for (int i = 0; i < matches.size(); i++) {
591: ArrayList<Object> match = matches.get(i);
592: Iterator<Object> it = match.iterator();
593: boolean clean = true;
594: while (it.hasNext()) {
595: if (!ids.contains(it.next())) {
596: clean = false;
597: break;
598: }
599: }
600: if (clean) {
601: List targs = b.getUnitBoxes(true);
602: for (int j = 0; j < targs.size() && clean; j++) {
603: Unit u = ((UnitBox) targs.get(j)).getUnit();
604: it = match.iterator();
605: while (it.hasNext()) {
606: if (u == it.next()) {
607: clean = false;
608: break;
609: }
610: }
611: }
612: }
613:
614: if (clean) {
615: it = match.iterator();
616: while (it.hasNext())
617: ids.remove(it.next());
618: newMatches.add(match);
619: }
620: }
621: return newMatches;
622: }
623: }
|