KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > annotation > arraycheck > RectangularArrayFinder


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2000 Feng Qian
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */

19
20 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */

25
26 package soot.jimple.toolkits.annotation.arraycheck;
27 import soot.options.*;
28
29 import soot.*;
30 import soot.util.*;
31 import soot.toolkits.graph.*;
32 import soot.jimple.*;
33 import soot.jimple.internal.*;
34 import soot.jimple.toolkits.callgraph.*;
35 import java.util.*;
36
37 /** Interprocedural analysis to identify rectangular multi-dimension array
38  * locals. It is based on the call graph.
39  */

40
41 public class RectangularArrayFinder extends SceneTransformer
42 {
43     public RectangularArrayFinder( Singletons.Global g ) {}
44     public static RectangularArrayFinder v() { return G.v().soot_jimple_toolkits_annotation_arraycheck_RectangularArrayFinder(); }
45
46     private ExtendedHashMutableDirectedGraph agraph =
47     new ExtendedHashMutableDirectedGraph();
48
49     private Set falseSet = new HashSet();
50     private Set trueSet = new HashSet();
51     private CallGraph cg;
52
53     protected void internalTransform(String JavaDoc phaseName, Map opts)
54     {
55     Scene sc = Scene.v();
56
57         cg = sc.getCallGraph();
58
59     Date start = new Date();
60     if (Options.v().verbose())
61         G.v().out.println("[ra] Finding rectangular arrays, start on "+start);
62
63     Chain appClasses = sc.getApplicationClasses();
64
65     Iterator classIt = appClasses.iterator();
66
67     while (classIt.hasNext())
68     {
69         SootClass c = (SootClass)classIt.next();
70
71         Iterator methodIt = c.methodIterator();
72         
73         while (methodIt.hasNext())
74         {
75         SootMethod method = (SootMethod)methodIt.next();
76         
77         if (!method.isConcrete())
78             continue;
79         
80         if (!sc.getReachableMethods().contains(method))
81             continue;
82
83         recoverRectArray(method);
84         addInfoFromMethod(method);
85         }
86     }
87     
88     /*
89     MutableDirectedGraph methodGraph = ig.newMethodGraph();
90     HashSet visitedMethods = new HashSet();
91     LinkedList tovisitMethods = new LinkedList();
92
93     List heads = methodGraph.getHeads();
94     Iterator headIt = heads.iterator();
95     while (headIt.hasNext())
96     {
97         SootMethod entry = (SootMethod)headIt.next();
98         String sig = entry.getSubSignature();
99
100         if (sig.equals(mainSignature))
101         tovisitMethods.add(entry);
102     }
103
104     while (!tovisitMethods.isEmpty())
105     {
106         SootMethod visiting = (SootMethod)tovisitMethods.removeFirst();
107         visitedMethods.add(visiting);
108
109         recoverRectArray(visiting);
110         addInfoFromMethod(visiting);
111
112         List succs = methodGraph.getSuccsOf(visiting);
113         Iterator succIt = succs.iterator();
114         while (succIt.hasNext())
115         {
116         Object succ = succIt.next();
117         if (!visitedMethods.contains(succ))
118             tovisitMethods.add(succ);
119         }
120     }
121     */

122
123     /* propagate the graph info from FALSE node. */
124     if (agraph.containsNode(BoolValue.v(false)))
125     {
126         List changedNodeList = new ArrayList();
127
128         List startNodes = agraph.getSuccsOf(BoolValue.v(false));
129
130         falseSet.addAll(startNodes);
131         changedNodeList.addAll(startNodes);
132     
133         while (!changedNodeList.isEmpty())
134         {
135         Object JavaDoc node = changedNodeList.remove(0);
136
137         List succs = agraph.getSuccsOf(node);
138         
139         Iterator succsIt = succs.iterator();
140
141         while (succsIt.hasNext())
142         {
143             Object JavaDoc succ = succsIt.next();
144
145             if (!falseSet.contains(succ))
146             {
147             falseSet.add(succ);
148             changedNodeList.add(succ);
149             }
150         }
151         }
152     }
153
154         /* propagate graph info from TRUE node then. */
155     if (agraph.containsNode(BoolValue.v(true)))
156     {
157         List changedNodeList = new ArrayList();
158
159         List startNodes = agraph.getSuccsOf(BoolValue.v(true));
160
161         Iterator nodesIt = startNodes.iterator();
162         while (nodesIt.hasNext())
163         {
164         Object JavaDoc node = nodesIt.next();
165         if (falseSet.contains(node))
166             continue;
167
168         changedNodeList.add(node);
169         trueSet.add(node);
170         }
171
172         while (!changedNodeList.isEmpty())
173         {
174         Object JavaDoc node = changedNodeList.remove(0);
175         
176         List succs = agraph.getSuccsOf(node);
177
178         Iterator succsIt = succs.iterator();
179
180         while (succsIt.hasNext())
181         {
182             Object JavaDoc succ = succsIt.next();
183
184             if (falseSet.contains(succ))
185             continue;
186
187             if (trueSet.contains(succ))
188             continue;
189
190             trueSet.add(succ);
191             changedNodeList.add(succ);
192         }
193         }
194     }
195
196     /* For verification, print out true set and false set. */
197     
198     if (Options.v().debug())
199     {
200         G.v().out.println("Rectangular Array :");
201         {
202         Iterator nodeIt = trueSet.iterator();
203         while (nodeIt.hasNext())
204         {
205             Object JavaDoc node = nodeIt.next();
206
207             G.v().out.println(node);
208         }
209         }
210
211         G.v().out.println("\nNon-rectangular Array :");
212         {
213         Iterator nodeIt = falseSet.iterator();
214         while (nodeIt.hasNext())
215         {
216             Object JavaDoc node = nodeIt.next();
217             
218             G.v().out.println(node);
219         }
220         }
221     }
222     
223     Date finish = new Date();
224     if (Options.v().verbose())
225     {
226         long runtime = finish.getTime() - start.getTime();
227         long mins = runtime/60000;
228         long secs = (runtime%60000)/1000;
229         G.v().out.println("[ra] Rectangular array finder finishes."
230                    +" It took "+mins+" mins and "+secs+" secs.");
231     }
232     }
233
234     private void addInfoFromMethod(SootMethod method)
235     {
236     if (Options.v().verbose())
237         G.v().out.println("[ra] Operating "+method.getSignature());
238
239     boolean needTransfer = true;
240
241     Body body = method.getActiveBody();
242
243     Set tmpNode = new HashSet();
244
245     /* check the return type of method, if it is multi-array. */
246
247     boolean trackReturn = false;
248     Type rtnType = method.getReturnType();
249     
250     if (rtnType instanceof ArrayType)
251     {
252         if (((ArrayType)rtnType).numDimensions > 1)
253         {
254         trackReturn = true;
255         needTransfer = true;
256         }
257     }
258
259     Set arrayLocal = new HashSet();
260
261     /* Collect the multi-array locals */
262
263     Chain locals = body.getLocals();
264     Iterator localIt = locals.iterator();
265     while (localIt.hasNext())
266     {
267         Local local = (Local)localIt.next();
268         
269         Type type = local.getType();
270
271         if (type instanceof ArrayType)
272         {
273         if ( ((ArrayType)type).numDimensions > 1)
274         {
275             arrayLocal.add(local);
276         }
277         else
278             tmpNode.add(new MethodLocal(method, local));
279         }
280     }
281
282     /* The method has a local graph. It will be merged to the whole graph after simplification. */
283     ExtendedHashMutableDirectedGraph ehmdg = new ExtendedHashMutableDirectedGraph();
284
285     Iterator unitIt = body.getUnits().snapshotIterator();
286
287     while (unitIt.hasNext())
288     {
289         Stmt s = (Stmt)unitIt.next();
290
291         /* for each invoke site, add edges from local parameter to the target methods' parameter node. */
292         if (s.containsInvokeExpr())
293         {
294         InvokeExpr iexpr = (InvokeExpr)s.getInvokeExpr();
295         
296         int argnum = iexpr.getArgCount();
297         
298         for (int i=0; i<argnum; i++)
299         {
300             Value arg = iexpr.getArg(i);
301             if (! arrayLocal.contains(arg))
302             continue;
303
304             needTransfer = true;
305
306             /* from node, it is a local */
307             MethodLocal ml = new MethodLocal(method, (Local)arg);
308
309                     Iterator targetIt = new Targets( cg.edgesOutOf(s) );
310             
311             while (targetIt.hasNext())
312             {
313             SootMethod target = (SootMethod)targetIt.next();
314             
315             MethodParameter mp = new MethodParameter(target, i);
316             
317             /* add edge to the graph. */
318             ehmdg.addMutualEdge(ml, mp);
319             }
320         }
321         }
322
323         /* if the return type is multiarray, add an mutual edge from local to return node. */
324
325         if (trackReturn && (s instanceof ReturnStmt))
326         {
327         Value op = ((ReturnStmt)s).getOp();
328
329         if (op instanceof Local)
330         {
331             ehmdg.addMutualEdge(new MethodLocal(method, (Local)op), new MethodReturn(method));
332         }
333         }
334
335         /* examine each assign statement. build edge relationship between them. */
336         if (s instanceof DefinitionStmt)
337         {
338         Value leftOp = ((DefinitionStmt)s).getLeftOp();
339         Value rightOp = ((DefinitionStmt)s).getRightOp();
340         
341         if (! (leftOp.getType() instanceof ArrayType)
342             && ! (rightOp.getType() instanceof ArrayType))
343             continue;
344
345         Object JavaDoc from = null;
346         Object JavaDoc to = null;
347         
348         /* kick out the possible cast. */
349         if ((leftOp instanceof Local) && (rightOp instanceof Local))
350         {
351             if (arrayLocal.contains(leftOp) && arrayLocal.contains(rightOp))
352             {
353             int leftDims = ((ArrayType)((Local)leftOp).getType()).numDimensions;
354             int rightDims = ((ArrayType)((Local)rightOp).getType()).numDimensions;
355             
356             to = new MethodLocal(method, (Local)leftOp);
357             from = new MethodLocal(method, (Local)rightOp);
358             ehmdg.addMutualEdge(from, to);
359             
360             if (leftDims != rightDims)
361                 ehmdg.addEdge(BoolValue.v(false), from);
362             }
363             else
364             if (! arrayLocal.contains(leftOp))
365             { /* implicitly cast from right side to left side, and the left side declare type is Object ... */
366             ehmdg.addEdge(BoolValue.v(false), new MethodLocal(method, (Local)rightOp));
367             }
368         }
369         else
370         if ((leftOp instanceof Local) && (rightOp instanceof ParameterRef))
371         {
372             if (arrayLocal.contains(leftOp))
373             {
374             to = new MethodLocal(method, (Local)leftOp);
375             int index = ((ParameterRef)rightOp).getIndex();
376             from = new MethodParameter(method, index);
377             ehmdg.addMutualEdge(from, to);
378
379             needTransfer = true;
380             }
381         }
382         else
383         if ((leftOp instanceof Local) && (rightOp instanceof ArrayRef))
384         {
385             Local base = (Local)((ArrayRef)rightOp).getBase();
386
387             /* it may include one-dimension array into the graph, */
388             if (arrayLocal.contains(base))
389             {
390             /* add 'a' to 'a[' first */
391             to = new ArrayReferenceNode(method, (Local)base);
392             from = new MethodLocal(method, (Local)base);
393             ehmdg.addMutualEdge(from, to);
394
395             /* put 'a[' into temporary object pool. */
396             tmpNode.add(to);
397
398             /* add 'a[' to 'p' then */
399             from = to;
400             to = new MethodLocal(method, (Local)leftOp);
401             ehmdg.addMutualEdge(from, to);
402             }
403         }
404         else
405         if ((leftOp instanceof ArrayRef) && (rightOp instanceof Local))
406         {
407             Local base = (Local)((ArrayRef)leftOp).getBase();
408
409             if (arrayLocal.contains(base))
410             {
411             /* to recover the SWAP of array dimensions. */
412             Object JavaDoc suspect = new MethodLocal(method, (Local)rightOp);
413             Object JavaDoc arrRef = new ArrayReferenceNode(method, (Local)base);
414             
415             boolean doNothing = false;
416
417             blocklabel:
418             {
419                 if (!ehmdg.containsNode(suspect))
420                     break blocklabel;
421
422                 List succs = ehmdg.getSuccsOf(suspect);
423                 List preds = ehmdg.getSuccsOf(suspect);
424
425                 Set neighbor = new HashSet();
426                 
427                 neighbor.addAll(succs);
428                 neighbor.addAll(preds);
429
430                 if (neighbor.size() != 1)
431                 break blocklabel;
432
433                 Object JavaDoc neighborOne = (neighbor.toArray())[0];
434
435                 if (arrRef.equals(neighborOne))
436                 doNothing = true;
437             }
438
439             if (!doNothing)
440                 ehmdg.addEdge(BoolValue.v(false), new MethodLocal(method, base));
441             }
442         }
443         else
444         if ((leftOp instanceof Local) && (rightOp instanceof InvokeExpr))
445         {
446             if (arrayLocal.contains(leftOp))
447             {
448             to = new MethodLocal(method, (Local)leftOp);
449
450             Iterator targetIt = new Targets( cg.edgesOutOf(s) );
451             
452             while (targetIt.hasNext())
453             {
454                 SootMethod target = (SootMethod)targetIt.next();
455
456                 ehmdg.addMutualEdge(new MethodReturn(target), to);
457             }
458             }
459         }
460         else
461         /* For field reference, we can make conservative assumption that all instance fieldRef use the same node.*/
462         if ((leftOp instanceof FieldRef) && (rightOp instanceof Local))
463         {
464             if (arrayLocal.contains(rightOp))
465             {
466             Type ftype = ((FieldRef)leftOp).getType();
467             Type ltype = ((Local)rightOp).getType();
468
469             to = ((FieldRef)leftOp).getField();
470             from = new MethodLocal(method, (Local)rightOp);
471             
472             ehmdg.addMutualEdge(from, to);
473             
474             if (!ftype.equals(ltype))
475             {
476                 ehmdg.addEdge(BoolValue.v(false), to);
477             }
478
479             needTransfer = true;
480             }
481         }
482         else
483         if ((leftOp instanceof Local) && (rightOp instanceof FieldRef))
484         {
485             if (arrayLocal.contains(leftOp))
486             {
487             Type ftype = ((FieldRef)rightOp).getType();
488             Type ltype = ((Local)leftOp).getType();
489
490             to = new MethodLocal(method, (Local)leftOp);
491             from = ((FieldRef)rightOp).getField();
492             
493             ehmdg.addMutualEdge(from, to);
494             
495             if (!ftype.equals(ltype))
496             {
497                 ehmdg.addEdge(BoolValue.v(false), to);
498             }
499
500             needTransfer = true;
501             }
502         }
503         else
504         if ((leftOp instanceof Local) && ((rightOp instanceof NewArrayExpr)||(rightOp instanceof NewMultiArrayExpr)))
505         {
506             if (arrayLocal.contains(leftOp))
507             {
508             ehmdg.addEdge(BoolValue.v(true), new MethodLocal(method, (Local)leftOp));
509             }
510         }
511         else
512         if ((leftOp instanceof Local) && (rightOp instanceof CastExpr))
513         /* Cast express, we will use conservative solution. */
514         {
515             Local rOp = (Local)((CastExpr)rightOp).getOp();
516
517             to = new MethodLocal(method, (Local)leftOp);
518             from = new MethodLocal(method, rOp);
519
520             if (arrayLocal.contains(leftOp) && arrayLocal.contains(rOp))
521             {
522             ArrayType lat = (ArrayType)leftOp.getType();
523             ArrayType rat = (ArrayType)rOp.getType();
524
525             if (lat.numDimensions == rat.numDimensions)
526             {
527                 ehmdg.addMutualEdge(from, to);
528             }
529             else
530             {
531                 ehmdg.addEdge(BoolValue.v(false), from);
532                 ehmdg.addEdge(BoolValue.v(false), to);
533             }
534             }
535             else
536             if (arrayLocal.contains(leftOp))
537             {
538             ehmdg.addEdge(BoolValue.v(false), to);
539             }
540             else
541             if (arrayLocal.contains(rOp))
542             {
543             ehmdg.addEdge(BoolValue.v(false), from);
544             }
545         }
546         }
547     }
548
549     /* Compute the graph locally, it will skip all locals */
550     
551     if (needTransfer)
552     {
553         Iterator tmpNodeIt = tmpNode.iterator();
554     
555         while (tmpNodeIt.hasNext())
556         {
557             ehmdg.skipNode(tmpNodeIt.next());
558         }
559     
560         /* Add local graph to whole graph */
561         agraph.mergeWith(ehmdg);
562     }
563
564     }
565
566     private void recoverRectArray(SootMethod method)
567     {
568     Body body = method.getActiveBody();
569     HashSet malocal = new HashSet();
570
571     Chain locals = body.getLocals();
572     Iterator localsIt = locals.iterator();
573     while (localsIt.hasNext())
574     {
575         Local local = (Local)localsIt.next();
576         Type type = local.getType();
577         if (!(type instanceof ArrayType))
578         continue;
579         
580         if (((ArrayType)type).numDimensions == 2)
581         malocal.add(local);
582     }
583
584     if (malocal.size() == 0)
585         return;
586
587     Chain units = body.getUnits();
588
589     Stmt stmt = (Stmt)units.getFirst();
590
591     while (true)
592     {
593         if (stmt == null)
594         break;
595
596         /* only deal with the first block */
597         if (!stmt.fallsThrough())
598         break;
599
600     searchblock:
601         {
602         /* possible candidates */
603         if (!(stmt instanceof AssignStmt))
604             break searchblock;
605             
606         Value leftOp = ((AssignStmt)stmt).getLeftOp();
607         Value rightOp = ((AssignStmt)stmt).getRightOp();
608
609         if (!malocal.contains(leftOp) || !(rightOp instanceof NewArrayExpr))
610             break searchblock;
611
612         Local local = (Local)leftOp;
613  
614         NewArrayExpr naexpr = (NewArrayExpr)rightOp;
615         
616         Value size = naexpr.getSize();
617         if (!(size instanceof IntConstant))
618             break searchblock;
619
620         int firstdim = ((IntConstant)size).value;
621         if (firstdim > 100)
622             break searchblock;
623
624         ArrayType localtype = (ArrayType)local.getType();
625         Type basetype = localtype.baseType;
626
627         Local[] tmplocals = new Local[firstdim];
628
629         int seconddim = lookforPattern(units, stmt,
630                            firstdim, local,
631                            basetype, tmplocals);
632
633         if (seconddim >= 0)
634             transferPattern(units, stmt,
635                     firstdim, seconddim,
636                     local, basetype, tmplocals);
637         }
638
639         stmt = (Stmt)units.getSuccOf(stmt);
640     }
641     }
642
643     /* if the local is assigned a rect array, return back the second dimension length,
644        else return -1
645     */

646     private int lookforPattern(Chain units, Stmt startpoint,
647                    int firstdim, Local local,
648                    Type basetype, Local[] tmplocals)
649     {
650     /* It is a state machine to match the pattern */
651     /* state input goto
652         start r1 = new(A[])[c] 1
653         1 r2 = newA[d] 2
654         2 r2[?] = ... 2
655                      r1[e] = r2 (e = c-1) 3
656              r1[e] = r2 (e = e'+1) 2
657         3 end
658     */

659
660     int seconddim = -1;
661     int curdim = 0;
662     Object JavaDoc curtmp = local; // Local, I have to initialize it. It should not be this value.
663

664     Stmt curstmt = startpoint;
665
666     int fault = 99;
667     int state = 1;
668
669     while (true)
670     {
671         curstmt = (Stmt)units.getSuccOf(curstmt);
672         if (curstmt == null)
673         return -1;
674
675         if (!(curstmt instanceof AssignStmt))
676         return -1;
677
678         Value leftOp = ((AssignStmt)curstmt).getLeftOp();
679         Value rightOp = ((AssignStmt)curstmt).getRightOp();
680
681         switch (state)
682         {
683         /* we already did state 0 outside */
684         case 0:
685         break;
686         
687         case 1:
688         /* make sure it is a new array expr */
689         {
690             state = fault;
691
692             if (!(rightOp instanceof NewArrayExpr))
693             break;
694             
695             NewArrayExpr naexpr = (NewArrayExpr)rightOp;
696             Type type = naexpr.getBaseType();
697             Value size = naexpr.getSize();
698
699             if (!type.equals(basetype))
700                 break;
701
702             if (!(size instanceof IntConstant))
703             break;
704
705             if (curdim == 0)
706             seconddim = ((IntConstant)size).value;
707             else
708             {
709             if (((IntConstant)size).value != seconddim)
710                 break;
711             }
712             
713             curtmp = leftOp;
714
715             state = 2;
716         }
717         break;
718
719         case 2:
720         {
721             state = fault;
722
723             if (!(leftOp instanceof ArrayRef))
724             break;
725
726             Value base = ((ArrayRef)leftOp).getBase();
727             Value idx = ((ArrayRef)leftOp).getIndex();
728
729             /* curtmp[?] = ? */
730             if (base.equals(curtmp))
731             state = 2;
732             else
733             /* local[?] = curtmp? */
734             if (base.equals(local))
735             {
736             if (!(idx instanceof IntConstant))
737                 break;
738             
739             if (curdim != ((IntConstant)idx).value)
740                 break;
741
742             if (!rightOp.equals(curtmp))
743                 break;
744
745             tmplocals[curdim] = (Local)curtmp;
746
747             curdim++;
748
749             if (curdim >= firstdim)
750                 state = 3;
751             else
752                 state = 1;
753             }
754         }
755         break;
756         
757         case 3:
758         return seconddim;
759       
760
761         default:
762         return -1;
763         }
764     }
765     }
766     
767     private void transferPattern(Chain units, Stmt startpoint,
768                  int firstdim, int seconddim,
769                  Local local, Type basetype,
770                  Local[] tmplocals)
771     {
772     /* sequentially search and replace the sub dimension assignment */
773     {
774         /* change the first one, reset the right op */
775         ArrayType atype = (ArrayType)local.getType();
776         List sizes = new ArrayList(2);
777         sizes.add(IntConstant.v(firstdim));
778         sizes.add(IntConstant.v(seconddim));
779         Value nmexpr = new JNewMultiArrayExpr(atype, sizes);
780
781         ((AssignStmt)startpoint).setRightOp(nmexpr);
782     }
783
784     {
785         int pos = 0;
786         int curdim = 0;
787         Local tmpcur = local;
788
789         Stmt curstmt = (Stmt)units.getSuccOf(startpoint);
790
791         while (curdim < firstdim)
792         {
793         Value leftOp = ((AssignStmt)curstmt).getLeftOp();
794         Value rightOp = ((AssignStmt)curstmt).getRightOp();
795         
796         if (tmplocals[curdim].equals(leftOp) && (rightOp instanceof NewArrayExpr))
797         {
798             ArrayRef arexpr = new JArrayRef(local, IntConstant.v(curdim));
799             ((AssignStmt)curstmt).setRightOp(arexpr);
800             tmpcur = (Local)leftOp;
801         }
802         else
803         if ((leftOp instanceof ArrayRef) && (rightOp.equals(tmpcur)))
804         {
805             /* delete current stmt */
806             Stmt tmpstmt = curstmt;
807             curstmt = (Stmt)units.getSuccOf(curstmt);
808             units.remove(tmpstmt);
809
810             curdim++;
811         }
812         else
813             curstmt = (Stmt)units.getSuccOf(curstmt);
814         }
815     }
816     }
817
818
819     public boolean isRectangular(Object JavaDoc obj)
820     {
821     if (trueSet.contains(obj))
822         return true;
823     else
824         return false;
825     }
826 }
827
828
829
Popular Tags