001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2000 Feng Qian
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.jimple.toolkits.annotation.arraycheck;
027:
028: import soot.options.*;
029:
030: import soot.*;
031: import soot.util.*;
032: import soot.jimple.*;
033: import soot.jimple.internal.*;
034: import soot.jimple.toolkits.callgraph.*;
035: import java.util.*;
036:
037: /** Interprocedural analysis to identify rectangular multi-dimension array
038: * locals. It is based on the call graph.
039: */
040:
041: public class RectangularArrayFinder extends SceneTransformer {
042: public RectangularArrayFinder(Singletons.Global g) {
043: }
044:
045: public static RectangularArrayFinder v() {
046: return G
047: .v()
048: .soot_jimple_toolkits_annotation_arraycheck_RectangularArrayFinder();
049: }
050:
051: private final ExtendedHashMutableDirectedGraph agraph = new ExtendedHashMutableDirectedGraph();
052:
053: private final Set falseSet = new HashSet();
054: private final Set<Object> trueSet = new HashSet<Object>();
055: private CallGraph cg;
056:
057: protected void internalTransform(String phaseName, Map opts) {
058: Scene sc = Scene.v();
059:
060: cg = sc.getCallGraph();
061:
062: Date start = new Date();
063: if (Options.v().verbose())
064: G.v().out
065: .println("[ra] Finding rectangular arrays, start on "
066: + start);
067:
068: Chain appClasses = sc.getApplicationClasses();
069:
070: Iterator classIt = appClasses.iterator();
071:
072: while (classIt.hasNext()) {
073: SootClass c = (SootClass) classIt.next();
074:
075: Iterator methodIt = c.methodIterator();
076:
077: while (methodIt.hasNext()) {
078: SootMethod method = (SootMethod) methodIt.next();
079:
080: if (!method.isConcrete())
081: continue;
082:
083: if (!sc.getReachableMethods().contains(method))
084: continue;
085:
086: recoverRectArray(method);
087: addInfoFromMethod(method);
088: }
089: }
090:
091: /*
092: MutableDirectedGraph methodGraph = ig.newMethodGraph();
093: HashSet visitedMethods = new HashSet();
094: LinkedList tovisitMethods = new LinkedList();
095:
096: List heads = methodGraph.getHeads();
097: Iterator headIt = heads.iterator();
098: while (headIt.hasNext())
099: {
100: SootMethod entry = (SootMethod)headIt.next();
101: String sig = entry.getSubSignature();
102:
103: if (sig.equals(mainSignature))
104: tovisitMethods.add(entry);
105: }
106:
107: while (!tovisitMethods.isEmpty())
108: {
109: SootMethod visiting = (SootMethod)tovisitMethods.removeFirst();
110: visitedMethods.add(visiting);
111:
112: recoverRectArray(visiting);
113: addInfoFromMethod(visiting);
114:
115: List succs = methodGraph.getSuccsOf(visiting);
116: Iterator succIt = succs.iterator();
117: while (succIt.hasNext())
118: {
119: Object succ = succIt.next();
120: if (!visitedMethods.contains(succ))
121: tovisitMethods.add(succ);
122: }
123: }
124: */
125:
126: /* propagate the graph info from FALSE node. */
127: if (agraph.containsNode(BoolValue.v(false))) {
128: List changedNodeList = new ArrayList();
129:
130: List startNodes = agraph.getSuccsOf(BoolValue.v(false));
131:
132: falseSet.addAll(startNodes);
133: changedNodeList.addAll(startNodes);
134:
135: while (!changedNodeList.isEmpty()) {
136: Object node = changedNodeList.remove(0);
137:
138: List succs = agraph.getSuccsOf(node);
139:
140: Iterator succsIt = succs.iterator();
141:
142: while (succsIt.hasNext()) {
143: Object succ = succsIt.next();
144:
145: if (!falseSet.contains(succ)) {
146: falseSet.add(succ);
147: changedNodeList.add(succ);
148: }
149: }
150: }
151: }
152:
153: /* propagate graph info from TRUE node then. */
154: if (agraph.containsNode(BoolValue.v(true))) {
155: List<Object> changedNodeList = new ArrayList<Object>();
156:
157: List startNodes = agraph.getSuccsOf(BoolValue.v(true));
158:
159: Iterator nodesIt = startNodes.iterator();
160: while (nodesIt.hasNext()) {
161: Object node = nodesIt.next();
162: if (falseSet.contains(node))
163: continue;
164:
165: changedNodeList.add(node);
166: trueSet.add(node);
167: }
168:
169: while (!changedNodeList.isEmpty()) {
170: Object node = changedNodeList.remove(0);
171:
172: List succs = agraph.getSuccsOf(node);
173:
174: Iterator succsIt = succs.iterator();
175:
176: while (succsIt.hasNext()) {
177: Object succ = succsIt.next();
178:
179: if (falseSet.contains(succ))
180: continue;
181:
182: if (trueSet.contains(succ))
183: continue;
184:
185: trueSet.add(succ);
186: changedNodeList.add(succ);
187: }
188: }
189: }
190:
191: /* For verification, print out true set and false set. */
192:
193: if (Options.v().debug()) {
194: G.v().out.println("Rectangular Array :");
195: {
196: Iterator<Object> nodeIt = trueSet.iterator();
197: while (nodeIt.hasNext()) {
198: Object node = nodeIt.next();
199:
200: G.v().out.println(node);
201: }
202: }
203:
204: G.v().out.println("\nNon-rectangular Array :");
205: {
206: Iterator nodeIt = falseSet.iterator();
207: while (nodeIt.hasNext()) {
208: Object node = nodeIt.next();
209:
210: G.v().out.println(node);
211: }
212: }
213: }
214:
215: Date finish = new Date();
216: if (Options.v().verbose()) {
217: long runtime = finish.getTime() - start.getTime();
218: long mins = runtime / 60000;
219: long secs = (runtime % 60000) / 1000;
220: G.v().out.println("[ra] Rectangular array finder finishes."
221: + " It took " + mins + " mins and " + secs
222: + " secs.");
223: }
224: }
225:
226: private void addInfoFromMethod(SootMethod method) {
227: if (Options.v().verbose())
228: G.v().out
229: .println("[ra] Operating " + method.getSignature());
230:
231: boolean needTransfer = true;
232:
233: Body body = method.getActiveBody();
234:
235: Set<Object> tmpNode = new HashSet<Object>();
236:
237: /* check the return type of method, if it is multi-array. */
238:
239: boolean trackReturn = false;
240: Type rtnType = method.getReturnType();
241:
242: if (rtnType instanceof ArrayType) {
243: if (((ArrayType) rtnType).numDimensions > 1) {
244: trackReturn = true;
245: needTransfer = true;
246: }
247: }
248:
249: Set<Local> arrayLocal = new HashSet<Local>();
250:
251: /* Collect the multi-array locals */
252:
253: Chain locals = body.getLocals();
254: Iterator localIt = locals.iterator();
255: while (localIt.hasNext()) {
256: Local local = (Local) localIt.next();
257:
258: Type type = local.getType();
259:
260: if (type instanceof ArrayType) {
261: if (((ArrayType) type).numDimensions > 1) {
262: arrayLocal.add(local);
263: } else
264: tmpNode.add(new MethodLocal(method, local));
265: }
266: }
267:
268: /* The method has a local graph. It will be merged to the whole graph after simplification. */
269: ExtendedHashMutableDirectedGraph ehmdg = new ExtendedHashMutableDirectedGraph();
270:
271: Iterator unitIt = body.getUnits().snapshotIterator();
272:
273: while (unitIt.hasNext()) {
274: Stmt s = (Stmt) unitIt.next();
275:
276: /* for each invoke site, add edges from local parameter to the target methods' parameter node. */
277: if (s.containsInvokeExpr()) {
278: InvokeExpr iexpr = s.getInvokeExpr();
279:
280: int argnum = iexpr.getArgCount();
281:
282: for (int i = 0; i < argnum; i++) {
283: Value arg = iexpr.getArg(i);
284: if (!arrayLocal.contains(arg))
285: continue;
286:
287: needTransfer = true;
288:
289: /* from node, it is a local */
290: MethodLocal ml = new MethodLocal(method,
291: (Local) arg);
292:
293: Iterator targetIt = new Targets(cg.edgesOutOf(s));
294:
295: while (targetIt.hasNext()) {
296: SootMethod target = (SootMethod) targetIt
297: .next();
298:
299: MethodParameter mp = new MethodParameter(
300: target, i);
301:
302: /* add edge to the graph. */
303: ehmdg.addMutualEdge(ml, mp);
304: }
305: }
306: }
307:
308: /* if the return type is multiarray, add an mutual edge from local to return node. */
309:
310: if (trackReturn && (s instanceof ReturnStmt)) {
311: Value op = ((ReturnStmt) s).getOp();
312:
313: if (op instanceof Local) {
314: ehmdg.addMutualEdge(new MethodLocal(method,
315: (Local) op), new MethodReturn(method));
316: }
317: }
318:
319: /* examine each assign statement. build edge relationship between them. */
320: if (s instanceof DefinitionStmt) {
321: Value leftOp = ((DefinitionStmt) s).getLeftOp();
322: Value rightOp = ((DefinitionStmt) s).getRightOp();
323:
324: if (!(leftOp.getType() instanceof ArrayType)
325: && !(rightOp.getType() instanceof ArrayType))
326: continue;
327:
328: Object from = null;
329: Object to = null;
330:
331: /* kick out the possible cast. */
332: if ((leftOp instanceof Local)
333: && (rightOp instanceof Local)) {
334: if (arrayLocal.contains(leftOp)
335: && arrayLocal.contains(rightOp)) {
336: int leftDims = ((ArrayType) ((Local) leftOp)
337: .getType()).numDimensions;
338: int rightDims = ((ArrayType) ((Local) rightOp)
339: .getType()).numDimensions;
340:
341: to = new MethodLocal(method, (Local) leftOp);
342: from = new MethodLocal(method, (Local) rightOp);
343: ehmdg.addMutualEdge(from, to);
344:
345: if (leftDims != rightDims)
346: ehmdg.addEdge(BoolValue.v(false), from);
347: } else if (!arrayLocal.contains(leftOp)) { /* implicitly cast from right side to left side, and the left side declare type is Object ... */
348: ehmdg
349: .addEdge(BoolValue.v(false),
350: new MethodLocal(method,
351: (Local) rightOp));
352: }
353: } else if ((leftOp instanceof Local)
354: && (rightOp instanceof ParameterRef)) {
355: if (arrayLocal.contains(leftOp)) {
356: to = new MethodLocal(method, (Local) leftOp);
357: int index = ((ParameterRef) rightOp).getIndex();
358: from = new MethodParameter(method, index);
359: ehmdg.addMutualEdge(from, to);
360:
361: needTransfer = true;
362: }
363: } else if ((leftOp instanceof Local)
364: && (rightOp instanceof ArrayRef)) {
365: Local base = (Local) ((ArrayRef) rightOp).getBase();
366:
367: /* it may include one-dimension array into the graph, */
368: if (arrayLocal.contains(base)) {
369: /* add 'a' to 'a[' first */
370: to = new ArrayReferenceNode(method, base);
371: from = new MethodLocal(method, base);
372: ehmdg.addMutualEdge(from, to);
373:
374: /* put 'a[' into temporary object pool. */
375: tmpNode.add(to);
376:
377: /* add 'a[' to 'p' then */
378: from = to;
379: to = new MethodLocal(method, (Local) leftOp);
380: ehmdg.addMutualEdge(from, to);
381: }
382: } else if ((leftOp instanceof ArrayRef)
383: && (rightOp instanceof Local)) {
384: Local base = (Local) ((ArrayRef) leftOp).getBase();
385:
386: if (arrayLocal.contains(base)) {
387: /* to recover the SWAP of array dimensions. */
388: Object suspect = new MethodLocal(method,
389: (Local) rightOp);
390: Object arrRef = new ArrayReferenceNode(method,
391: base);
392:
393: boolean doNothing = false;
394:
395: blocklabel: {
396: if (!ehmdg.containsNode(suspect))
397: break blocklabel;
398:
399: List succs = ehmdg.getSuccsOf(suspect);
400: List preds = ehmdg.getSuccsOf(suspect);
401:
402: Set neighbor = new HashSet();
403:
404: neighbor.addAll(succs);
405: neighbor.addAll(preds);
406:
407: if (neighbor.size() != 1)
408: break blocklabel;
409:
410: Object neighborOne = (neighbor.toArray())[0];
411:
412: if (arrRef.equals(neighborOne))
413: doNothing = true;
414: }
415:
416: if (!doNothing)
417: ehmdg.addEdge(BoolValue.v(false),
418: new MethodLocal(method, base));
419: }
420: } else if ((leftOp instanceof Local)
421: && (rightOp instanceof InvokeExpr)) {
422: if (arrayLocal.contains(leftOp)) {
423: to = new MethodLocal(method, (Local) leftOp);
424:
425: Iterator targetIt = new Targets(cg
426: .edgesOutOf(s));
427:
428: while (targetIt.hasNext()) {
429: SootMethod target = (SootMethod) targetIt
430: .next();
431:
432: ehmdg.addMutualEdge(
433: new MethodReturn(target), to);
434: }
435: }
436: } else
437: /* For field reference, we can make conservative assumption that all instance fieldRef use the same node.*/
438: if ((leftOp instanceof FieldRef)
439: && (rightOp instanceof Local)) {
440: if (arrayLocal.contains(rightOp)) {
441: Type ftype = ((FieldRef) leftOp).getType();
442: Type ltype = ((Local) rightOp).getType();
443:
444: to = ((FieldRef) leftOp).getField();
445: from = new MethodLocal(method, (Local) rightOp);
446:
447: ehmdg.addMutualEdge(from, to);
448:
449: if (!ftype.equals(ltype)) {
450: ehmdg.addEdge(BoolValue.v(false), to);
451: }
452:
453: needTransfer = true;
454: }
455: } else if ((leftOp instanceof Local)
456: && (rightOp instanceof FieldRef)) {
457: if (arrayLocal.contains(leftOp)) {
458: Type ftype = ((FieldRef) rightOp).getType();
459: Type ltype = ((Local) leftOp).getType();
460:
461: to = new MethodLocal(method, (Local) leftOp);
462: from = ((FieldRef) rightOp).getField();
463:
464: ehmdg.addMutualEdge(from, to);
465:
466: if (!ftype.equals(ltype)) {
467: ehmdg.addEdge(BoolValue.v(false), to);
468: }
469:
470: needTransfer = true;
471: }
472: } else if ((leftOp instanceof Local)
473: && ((rightOp instanceof NewArrayExpr) || (rightOp instanceof NewMultiArrayExpr))) {
474: if (arrayLocal.contains(leftOp)) {
475: ehmdg
476: .addEdge(BoolValue.v(true),
477: new MethodLocal(method,
478: (Local) leftOp));
479: }
480: } else if ((leftOp instanceof Local)
481: && (rightOp instanceof CastExpr))
482: /* Cast express, we will use conservative solution. */
483: {
484: Local rOp = (Local) ((CastExpr) rightOp).getOp();
485:
486: to = new MethodLocal(method, (Local) leftOp);
487: from = new MethodLocal(method, rOp);
488:
489: if (arrayLocal.contains(leftOp)
490: && arrayLocal.contains(rOp)) {
491: ArrayType lat = (ArrayType) leftOp.getType();
492: ArrayType rat = (ArrayType) rOp.getType();
493:
494: if (lat.numDimensions == rat.numDimensions) {
495: ehmdg.addMutualEdge(from, to);
496: } else {
497: ehmdg.addEdge(BoolValue.v(false), from);
498: ehmdg.addEdge(BoolValue.v(false), to);
499: }
500: } else if (arrayLocal.contains(leftOp)) {
501: ehmdg.addEdge(BoolValue.v(false), to);
502: } else if (arrayLocal.contains(rOp)) {
503: ehmdg.addEdge(BoolValue.v(false), from);
504: }
505: }
506: }
507: }
508:
509: /* Compute the graph locally, it will skip all locals */
510:
511: if (needTransfer) {
512: Iterator<Object> tmpNodeIt = tmpNode.iterator();
513:
514: while (tmpNodeIt.hasNext()) {
515: ehmdg.skipNode(tmpNodeIt.next());
516: }
517:
518: /* Add local graph to whole graph */
519: agraph.mergeWith(ehmdg);
520: }
521:
522: }
523:
524: private void recoverRectArray(SootMethod method) {
525: Body body = method.getActiveBody();
526: HashSet<Local> malocal = new HashSet<Local>();
527:
528: Chain locals = body.getLocals();
529: Iterator localsIt = locals.iterator();
530: while (localsIt.hasNext()) {
531: Local local = (Local) localsIt.next();
532: Type type = local.getType();
533: if (!(type instanceof ArrayType))
534: continue;
535:
536: if (((ArrayType) type).numDimensions == 2)
537: malocal.add(local);
538: }
539:
540: if (malocal.size() == 0)
541: return;
542:
543: Chain units = body.getUnits();
544:
545: Stmt stmt = (Stmt) units.getFirst();
546:
547: while (true) {
548: if (stmt == null)
549: break;
550:
551: /* only deal with the first block */
552: if (!stmt.fallsThrough())
553: break;
554:
555: searchblock: {
556: /* possible candidates */
557: if (!(stmt instanceof AssignStmt))
558: break searchblock;
559:
560: Value leftOp = ((AssignStmt) stmt).getLeftOp();
561: Value rightOp = ((AssignStmt) stmt).getRightOp();
562:
563: if (!malocal.contains(leftOp)
564: || !(rightOp instanceof NewArrayExpr))
565: break searchblock;
566:
567: Local local = (Local) leftOp;
568:
569: NewArrayExpr naexpr = (NewArrayExpr) rightOp;
570:
571: Value size = naexpr.getSize();
572: if (!(size instanceof IntConstant))
573: break searchblock;
574:
575: int firstdim = ((IntConstant) size).value;
576: if (firstdim > 100)
577: break searchblock;
578:
579: ArrayType localtype = (ArrayType) local.getType();
580: Type basetype = localtype.baseType;
581:
582: Local[] tmplocals = new Local[firstdim];
583:
584: int seconddim = lookforPattern(units, stmt, firstdim,
585: local, basetype, tmplocals);
586:
587: if (seconddim >= 0)
588: transferPattern(units, stmt, firstdim, seconddim,
589: local, basetype, tmplocals);
590: }
591:
592: stmt = (Stmt) units.getSuccOf(stmt);
593: }
594: }
595:
596: /* if the local is assigned a rect array, return back the second dimension length,
597: else return -1
598: */
599: private int lookforPattern(Chain units, Stmt startpoint,
600: int firstdim, Local local, Type basetype, Local[] tmplocals) {
601: /* It is a state machine to match the pattern */
602: /* state input goto
603: start r1 = new(A[])[c] 1
604: 1 r2 = newA[d] 2
605: 2 r2[?] = ... 2
606: r1[e] = r2 (e = c-1) 3
607: r1[e] = r2 (e = e'+1) 2
608: 3 end
609: */
610:
611: int seconddim = -1;
612: int curdim = 0;
613: Object curtmp = local; // Local, I have to initialize it. It should not be this value.
614:
615: Stmt curstmt = startpoint;
616:
617: int fault = 99;
618: int state = 1;
619:
620: while (true) {
621: curstmt = (Stmt) units.getSuccOf(curstmt);
622: if (curstmt == null)
623: return -1;
624:
625: if (!(curstmt instanceof AssignStmt))
626: return -1;
627:
628: Value leftOp = ((AssignStmt) curstmt).getLeftOp();
629: Value rightOp = ((AssignStmt) curstmt).getRightOp();
630:
631: switch (state) {
632: /* we already did state 0 outside */
633: case 0:
634: break;
635:
636: case 1:
637: /* make sure it is a new array expr */
638: {
639: state = fault;
640:
641: if (!(rightOp instanceof NewArrayExpr))
642: break;
643:
644: NewArrayExpr naexpr = (NewArrayExpr) rightOp;
645: Type type = naexpr.getBaseType();
646: Value size = naexpr.getSize();
647:
648: if (!type.equals(basetype))
649: break;
650:
651: if (!(size instanceof IntConstant))
652: break;
653:
654: if (curdim == 0)
655: seconddim = ((IntConstant) size).value;
656: else {
657: if (((IntConstant) size).value != seconddim)
658: break;
659: }
660:
661: curtmp = leftOp;
662:
663: state = 2;
664: }
665: break;
666:
667: case 2: {
668: state = fault;
669:
670: if (!(leftOp instanceof ArrayRef))
671: break;
672:
673: Value base = ((ArrayRef) leftOp).getBase();
674: Value idx = ((ArrayRef) leftOp).getIndex();
675:
676: /* curtmp[?] = ? */
677: if (base.equals(curtmp))
678: state = 2;
679: else
680: /* local[?] = curtmp? */
681: if (base.equals(local)) {
682: if (!(idx instanceof IntConstant))
683: break;
684:
685: if (curdim != ((IntConstant) idx).value)
686: break;
687:
688: if (!rightOp.equals(curtmp))
689: break;
690:
691: tmplocals[curdim] = (Local) curtmp;
692:
693: curdim++;
694:
695: if (curdim >= firstdim)
696: state = 3;
697: else
698: state = 1;
699: }
700: }
701: break;
702:
703: case 3:
704: return seconddim;
705:
706: default:
707: return -1;
708: }
709: }
710: }
711:
712: private void transferPattern(Chain units, Stmt startpoint,
713: int firstdim, int seconddim, Local local, Type basetype,
714: Local[] tmplocals) {
715: /* sequentially search and replace the sub dimension assignment */
716: {
717: /* change the first one, reset the right op */
718: ArrayType atype = (ArrayType) local.getType();
719: List sizes = new ArrayList(2);
720: sizes.add(IntConstant.v(firstdim));
721: sizes.add(IntConstant.v(seconddim));
722: Value nmexpr = new JNewMultiArrayExpr(atype, sizes);
723:
724: ((AssignStmt) startpoint).setRightOp(nmexpr);
725: }
726:
727: {
728: int curdim = 0;
729: Local tmpcur = local;
730:
731: Stmt curstmt = (Stmt) units.getSuccOf(startpoint);
732:
733: while (curdim < firstdim) {
734: Value leftOp = ((AssignStmt) curstmt).getLeftOp();
735: Value rightOp = ((AssignStmt) curstmt).getRightOp();
736:
737: if (tmplocals[curdim].equals(leftOp)
738: && (rightOp instanceof NewArrayExpr)) {
739: ArrayRef arexpr = new JArrayRef(local, IntConstant
740: .v(curdim));
741: ((AssignStmt) curstmt).setRightOp(arexpr);
742: tmpcur = (Local) leftOp;
743: } else if ((leftOp instanceof ArrayRef)
744: && (rightOp.equals(tmpcur))) {
745: /* delete current stmt */
746: Stmt tmpstmt = curstmt;
747: curstmt = (Stmt) units.getSuccOf(curstmt);
748: units.remove(tmpstmt);
749:
750: curdim++;
751: } else
752: curstmt = (Stmt) units.getSuccOf(curstmt);
753: }
754: }
755: }
756:
757: public boolean isRectangular(Object obj) {
758: if (trueSet.contains(obj))
759: return true;
760: else
761: return false;
762: }
763: }
|