ArrayIndexLivenessAnalysis


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.jimple.*;
31  import soot.jimple.internal.*;
32  import soot.util.*;
33  import soot.toolkits.graph.*;
34  import soot.toolkits.scalar.*;
35  
36  import java.util.*;
37  
38  class ArrayIndexLivenessAnalysis extends BackwardFlowAnalysis
39  {
40      HashSet fullSet = new HashSet();
41      ExceptionalUnitGraph eug;
42  
43      /* for each unit, kill set has variables to be killed.
44       * gen set was considered with conditionOfGenSet,
45       * for example, gen set of unit s are valid only when the condition object.
46       * was in the living input set.
47       */
48      HashMap genOfUnit;
49      HashMap absGenOfUnit;
50      HashMap killOfUnit;
51      HashMap conditionOfGen;
52  
53      // s --> a kill all a[?].
54      HashMap killArrayRelated;
55      // s --> true
56      HashMap killAllArrayRef;
57  
58      IntContainer zero = new IntContainer(0);
59  
60      private boolean fieldin;
61      HashMap localToFieldRef, fieldToFieldRef;
62      HashSet allFieldRefs;
63  
64      private boolean arrayin;
65      HashMap localToArrayRef;
66      HashSet allArrayRefs;
67  
68      private boolean csin;
69      HashMap localToExpr;
70  
71      private boolean rectarray;
72      HashSet multiarraylocals;
73  
74      public ArrayIndexLivenessAnalysis(DirectedGraph dg, 
75                                        boolean takeFieldRef, 
76                                        boolean takeArrayRef,
77                                        boolean takeCSE,
78                                        boolean takeRectArray)
79      {
80          super(dg);
81          
82          fieldin = takeFieldRef;
83          arrayin = takeArrayRef;
84          csin = takeCSE;
85          rectarray = takeRectArray;
86          
87          if (Options.v().debug()) 
88              G.v().out.println("Enter ArrayIndexLivenessAnalysis");
89          
90          eug = (ExceptionalUnitGraph)dg;
91          retrieveAllArrayLocals(eug.getBody(), fullSet);
92          
93          /* compute gen set, kill set, and condition set */
94          genOfUnit = new HashMap(eug.size()*2+1);
95          absGenOfUnit = new HashMap(eug.size()*2+1);
96          killOfUnit = new HashMap(eug.size()*2+1);
97          conditionOfGen = new HashMap(eug.size()*2+1);
98          
99          if (fieldin)
100         {
101             localToFieldRef = new HashMap();
102             fieldToFieldRef = new HashMap();
103             allFieldRefs = new HashSet();
104         }
105         
106         if (arrayin)
107         {
108             localToArrayRef = new HashMap();
109             allArrayRefs = new HashSet();
110             
111             killArrayRelated = new HashMap();
112             killAllArrayRef = new HashMap();
113             
114             if (rectarray)
115             {
116                 multiarraylocals = new HashSet();
117                 retrieveMultiArrayLocals(eug.getBody(), multiarraylocals);
118             }
119         }
120         
121         if (csin)
122         {
123             localToExpr = new HashMap();
124         }
125 
126         getAllRelatedMaps(eug.getBody());
127 
128         getGenAndKillSet(eug.getBody(), absGenOfUnit, genOfUnit, killOfUnit, conditionOfGen);
129 
130         doAnalysis();
131 
132         if (Options.v().debug()) 
133             G.v().out.println("Leave ArrayIndexLivenessAnalysis");
134     }
135 
136     public HashMap getLocalToFieldRef()
137     {
138         return localToFieldRef;
139     }
140 
141     public HashMap getFieldToFieldRef()
142     {
143         return fieldToFieldRef;
144     }
145 
146     public HashSet getAllFieldRefs()
147     {
148         return this.allFieldRefs;
149     }
150 
151     public HashMap getLocalToArrayRef()
152     {
153         return localToArrayRef;
154     }
155 
156     public HashSet getAllArrayRefs()
157     {
158         return allArrayRefs;
159     }
160 
161     public HashMap getLocalToExpr()
162     {
163         return localToExpr;
164     }
165 
166     public HashSet getMultiArrayLocals()
167     {
168         return multiarraylocals;
169     }
170 
171     private void getAllRelatedMaps(Body body)
172     {
173         Iterator unitIt = body.getUnits().iterator();
174         while (unitIt.hasNext())
175         {
176             Stmt stmt = (Stmt)unitIt.next();
177             
178             if (csin)
179             {
180                 if (stmt instanceof DefinitionStmt)
181                 {
182                     Value rhs = ((DefinitionStmt)stmt).getRightOp();
183 
184                     if (rhs instanceof BinopExpr) 
185                     {
186                         Value op1 = ((BinopExpr)rhs).getOp1();
187                         Value op2 = ((BinopExpr)rhs).getOp2();
188                         
189                         if (rhs instanceof AddExpr) 
190                         {
191                             // op1 + op2 --> a + b
192                             if ((op1 instanceof Local) &&
193                                 (op2 instanceof Local)) 
194                             {
195                                 HashSet refs = (HashSet)localToExpr.get(op1);
196                                 if (refs == null)
197                                 {
198                                     refs = new HashSet();
199                                     localToExpr.put(op1, refs);
200                                 }
201                                 refs.add(rhs);
202                                 
203                                 refs = (HashSet)localToExpr.get(op2);
204                                 if (refs == null)
205                                 {
206                                     refs = new HashSet();
207                                     localToExpr.put(op2, refs);
208                                 }
209                                 refs.add(rhs);
210                             }
211                         }
212                         // a * b, a * c, c * a
213                         else if (rhs instanceof MulExpr)
214                         {
215                             HashSet refs = (HashSet)localToExpr.get(op1);
216                             if (refs == null)
217                             {
218                                 refs = new HashSet();
219                                 localToExpr.put(op1, refs);
220                             }
221                             refs.add(rhs);
222                 
223                             refs = (HashSet)localToExpr.get(op2);
224                             if (refs == null)
225                             {
226                                 refs = new HashSet();
227                                 localToExpr.put(op2, refs);
228                             }
229                             refs.add(rhs);
230                         }
231                         else if (rhs instanceof SubExpr)
232                         {
233                             if (op2 instanceof Local)
234                             {
235                                 HashSet refs = (HashSet)localToExpr.get(op2);
236                                 if (refs == null)
237                                 {
238                                     refs = new HashSet();
239                                     localToExpr.put(op2, refs);
240                                 }
241                                 refs.add(rhs);
242                                 
243                                 if (op1 instanceof Local)
244                                 {
245                                     refs = (HashSet)localToExpr.get(op1);
246                                     if (refs == null)
247                                     {
248                                         refs = new HashSet();
249                                         localToExpr.put(op1, refs);
250                                     }
251                                     refs.add(rhs);
252                                 }
253                             }
254                         }
255                     }
256                 }
257             }
258             
259             List vboxes = stmt.getUseAndDefBoxes();
260             Iterator vboxIt = vboxes.iterator();
261             while (vboxIt.hasNext())
262             {
263                 Value v = ((ValueBox)vboxIt.next()).getValue();
264                 
265                 if (fieldin)
266                 {
267                     if (v instanceof InstanceFieldRef)
268                     {
269                         Value base = ((InstanceFieldRef)v).getBase();
270                         SootField field = ((InstanceFieldRef)v).getField();
271                         
272                         HashSet baseset = (HashSet)localToFieldRef.get(base);
273                         if (baseset == null)
274                         {
275                             baseset = new HashSet();
276                             localToFieldRef.put(base, baseset);
277                         }
278                         
279                         baseset.add(v);
280                         
281                         HashSet fieldset = (HashSet)fieldToFieldRef.get(field);
282                         if (fieldset == null)
283                         {
284                             fieldset = new HashSet();
285                             fieldToFieldRef.put(field, fieldset);
286                         }
287 
288                         fieldset.add(v);
289                     }
290 
291                     if (v instanceof FieldRef)
292                         allFieldRefs.add(v);
293                 }
294 
295                 if (arrayin)
296                 {
297                     // a = ...   --> kill all a[x] nodes.
298                     // a[i] = .. --> kill all array references.
299                     // m(a)      --> kill all array references 
300                     // i = ...   --> kill all array reference with index as i
301                 /*
302                 if (v instanceof ArrayRef)
303                 {
304                     Value base = ((ArrayRef)v).getBase();
305                     Value index = ((ArrayRef)v).getIndex();
306 
307                     HashSet refset = (HashSet)localToArrayRef.get(base);
308                     if (refset == null)
309                     {
310                         refset = new HashSet();
311                         localToArrayRef.put(base, refset);
312                     }
313                     refset.add(v);
314 
315                     if (index instanceof Local)
316                     {
317                         refset = (HashSet)localToArrayRef.get(index);
318                         if (refset == null)
319                         {
320                             refset = new HashSet();
321                             localToArrayRef.put(index, refset);
322                         }
323 
324                         refset.add(v);
325                     }           
326                     allArrayRefs.add(v);
327                 }
328                 */
329                 }
330             }
331         }
332     }
333     
334     private void retrieveAllArrayLocals(Body body, Set container)
335     {
336         Chain locals = body.getLocals();
337 
338         Iterator localIt = locals.iterator();
339 
340         while (localIt.hasNext())
341         {
342             Local local = (Local)localIt.next();
343             
344             Type type = local.getType();
345             
346             if (type instanceof IntType
347                 || type instanceof ArrayType)
348                 container.add(local);
349         }
350     }
351     
352     private void retrieveMultiArrayLocals(Body body, Set container)
353     {
354         Chain locals = body.getLocals();
355         
356         Iterator localIt = locals.iterator();
357         
358         while (localIt.hasNext())
359         {
360             Local local = (Local)localIt.next();
361 
362             Type type = local.getType();
363             
364             if (type instanceof ArrayType)
365             {
366                 if (((ArrayType)type).numDimensions > 1)
367                     this.multiarraylocals.add(local);
368             }
369         }
370     }
371 
372     private void getGenAndKillSetForDefnStmt(DefinitionStmt asstmt, 
373                                              HashMap absgen,
374                                              HashSet genset,
375                                              HashSet absgenset,
376                                              HashSet killset,
377                                              HashSet condset)
378     {
379         /* kill left hand side */
380         Value lhs = asstmt.getLeftOp();
381         Value rhs = asstmt.getRightOp();
382         
383         boolean killarrayrelated = false;
384         boolean killallarrayref = false;
385         
386         if (fieldin)
387         {
388             if (lhs instanceof Local)
389             {
390                 HashSet related = (HashSet)localToFieldRef.get(lhs);
391                 if (related != null)
392                     killset.addAll(related);
393             }
394             else
395                 if (lhs instanceof StaticFieldRef)
396                 {
397                     killset.add(lhs);
398                     condset.add(lhs);
399                 }
400                 else
401                     if (lhs instanceof InstanceFieldRef)
402                     {
403                         SootField field = ((InstanceFieldRef)lhs).getField();
404                         HashSet related = (HashSet)fieldToFieldRef.get(field);
405                         if (related != null)
406                             killset.addAll(related);
407                         condset.add(lhs);
408                     }
409             
410             if (asstmt.containsInvokeExpr())
411             {
412                 /*
413                 Value expr = asstmt.getInvokeExpr();
414                 List parameters = ((InvokeExpr)expr).getArgs();
415 
416                 // add the method invocation
417                 boolean killall = false;
418                 if (expr instanceof InstanceInvokeExpr)
419                     killall = true;
420                 else
421                 {
422                     for (int i=0; i<parameters.size(); i++)
423                     {
424                     Value para = (Value)parameters.get(i);
425                     if (para.getType() instanceof RefType)
426                     {
427                         killall = true;
428                         break;
429                     }
430                     }
431                 }
432     
433                 if (killall)
434                 {
435                     killset.addAll(allInstFieldRefs);
436                 }   
437                 */
438 
439                 killset.addAll(allFieldRefs);
440             } 
441         }
442         
443         if (arrayin)
444         {
445             // a = ... or i = ...
446             if (lhs instanceof Local)
447             {
448                 killarrayrelated = true;
449             }
450             else
451                 // a[i] = ...
452                 if (lhs instanceof ArrayRef)
453                 {
454                     killallarrayref = true;
455                     condset.add(lhs);
456                 }
457             
458             // invokeexpr kills all array references.
459             if (asstmt.containsInvokeExpr())
460             {
461                 killallarrayref = true;
462             }
463         }
464         
465         if (csin)
466         {
467             HashSet exprs = (HashSet)localToExpr.get(lhs);
468             if (exprs != null)
469                 killset.addAll(exprs);
470 
471             if (rhs instanceof BinopExpr)
472             {
473                 Value op1 = ((BinopExpr)rhs).getOp1();
474                 Value op2 = ((BinopExpr)rhs).getOp2();
475 
476                 if (rhs instanceof AddExpr)
477                 {
478                     if ((op1 instanceof Local) &&
479                         (op2 instanceof Local))
480                         genset.add(rhs);
481                 }
482                 else
483                     if (rhs instanceof MulExpr)
484                     {
485                         if ((op1 instanceof Local) ||
486                             (op2 instanceof Local))
487                             genset.add(rhs);
488                     }
489                     else
490                         if (rhs instanceof SubExpr)
491                         {
492                             if (op2 instanceof Local)
493                                 genset.add(rhs);
494                         }
495             }
496         }
497         
498         if ((lhs instanceof Local)&&(fullSet.contains(lhs)))
499         {
500             killset.add(lhs);
501             /* speculatively add lhs as live condition. */
502             condset.add(lhs);
503         }
504         else if (lhs instanceof ArrayRef)
505         {
506             /* a[i] generate a and i. */
507 
508             Value base = ((ArrayRef)lhs).getBase();
509             Value index = ((ArrayRef)lhs).getIndex();
510 
511             ArrayList genList = new ArrayList();
512             
513             absgenset.add(base);
514             
515             if (index instanceof Local)
516             {
517                 absgenset.add(index);
518             }
519         }
520         
521         if (rhs instanceof Local)
522         {
523             /* only lhs=rhs is valid. */
524             /*
525               if (lhs instanceof Local && fullSet.contains(rhs))
526               genset.add(rhs);
527             */
528             if (fullSet.contains(rhs))
529                 genset.add(rhs);
530             
531             /*
532               if (fieldin && (lhs instanceof FieldRef))
533               genset.add(rhs);
534             */
535         }
536         else if (rhs instanceof FieldRef)
537         {
538             if (fieldin)
539                 genset.add(rhs);
540         }
541         else if (rhs instanceof ArrayRef)
542         {
543             /* lhs=a[i]. */
544 
545             Value base = ((ArrayRef)rhs).getBase();
546             Value index = ((ArrayRef)rhs).getIndex();
547             
548             absgenset.add(base);
549             if (index instanceof Local)
550             {
551                 absgenset.add(index);
552             }
553             
554             if (arrayin)
555             {
556                 genset.add(rhs);
557 
558                 if (rectarray)
559                     genset.add(Array2ndDimensionSymbol.v(base));
560             }
561         }
562         else if (rhs instanceof NewArrayExpr)
563         {
564             /* a = new A[i]; */
565             Value size = ((NewArrayExpr)rhs).getSize();
566             if (size instanceof Local)
567                 genset.add(size);
568         }
569         else if (rhs instanceof NewMultiArrayExpr)
570         {
571             /* a = new A[i][]...;*/
572             /* More precisely, we should track other dimensions. */
573                         
574             List sizes = ((NewMultiArrayExpr)rhs).getSizes();
575             Iterator sizeIt = sizes.iterator();
576             while (sizeIt.hasNext())
577             {
578                 Value size = (Value)sizeIt.next();
579                 
580                 if (size instanceof Local)
581                     genset.add(size);
582             }
583         }
584         else if (rhs instanceof LengthExpr)
585         {
586             /* lhs = lengthof rhs */
587             Value op = ((LengthExpr)rhs).getOp();
588             genset.add(op);
589         }
590         else if (rhs instanceof JAddExpr)                        
591         {
592             /* lhs = rhs+c, lhs=c+rhs */
593             Value op1 = ((JAddExpr)rhs).getOp1();
594             Value op2 = ((JAddExpr)rhs).getOp2();
595             
596             if ((op1 instanceof IntConstant) &&
597                 (op2 instanceof Local))
598             {
599                 genset.add(op2);
600             }
601             else if ((op2 instanceof IntConstant) &&
602                      (op1 instanceof Local))
603             {
604                 genset.add(op1);
605             }
606         }
607         else if (rhs instanceof JSubExpr)
608         {
609             Value op1 = ((JSubExpr)rhs).getOp1();
610             Value op2 = ((JSubExpr)rhs).getOp2();
611             
612             if ((op1 instanceof Local) &&
613                 (op2 instanceof IntConstant))
614             {
615                 genset.add(op1);
616             }
617         }
618         
619         if (arrayin)
620         {
621             if (killarrayrelated)
622                 killArrayRelated.put(asstmt, lhs);
623             
624             if (killallarrayref)
625                 killAllArrayRef.put(asstmt, new Boolean  (true));
626         }
627     }
628 
629     private void getGenAndKillSet(Body body, HashMap absgen, HashMap gen, HashMap kill, HashMap condition)
630     {
631         Iterator unitIt = body.getUnits().iterator();
632 
633         while (unitIt.hasNext())
634         {
635             Stmt stmt = (Stmt)unitIt.next();
636 
637             HashSet genset = new HashSet();
638             HashSet absgenset = new HashSet();
639             HashSet killset = new HashSet();
640             HashSet condset = new HashSet();
641             
642             if (stmt instanceof DefinitionStmt)
643             {
644                 getGenAndKillSetForDefnStmt((DefinitionStmt)stmt, absgen,
645                                             genset, absgenset, 
646                                             killset, condset);
647 
648             }
649             else if (stmt instanceof IfStmt)
650             {
651                 /* if one of condition is living, than other one is live. */
652                 Value cmpcond = ((IfStmt)stmt).getCondition();
653                 
654                 if (cmpcond instanceof ConditionExpr)
655                 {
656                     Value op1 = ((ConditionExpr)cmpcond).getOp1();
657                     Value op2 = ((ConditionExpr)cmpcond).getOp2();
658                     
659                     if (fullSet.contains(op1) && fullSet.contains(op2))
660                     {
661                         condset.add(op1);
662                         condset.add(op2);
663                         
664                         genset.add(op1);
665                         genset.add(op2);
666                     }
667                 }
668             }
669             
670             if (genset.size() != 0)
671                 gen.put(stmt, genset);
672             if (absgenset.size() != 0)
673                 absgen.put(stmt, absgenset);
674             if (killset.size() != 0)
675                 kill.put(stmt, killset);
676             if (condset.size() != 0)
677                 condition.put(stmt, condset);
678         }
679     }
680 
681     /* It is unsafe for normal units. */
682     /* Since the initial value is safe, empty set. 
683        we do not need to do it again. */
684     protected Object   newInitialFlow()
685     {
686         return new HashSet();
687     }
688 
689     /* It is safe for end units. */
690     protected Object   entryInitialFlow()
691     {
692         return new HashSet();
693     }
694 
695     protected void flowThrough(Object   inValue, Object   unit, Object   outValue)
696     {
697         HashSet inset = (HashSet)inValue;
698         HashSet outset = (HashSet)outValue;
699         Stmt stmt = (Stmt)unit;
700         
701         /* copy in set to out set. */
702         outset.clear();
703         outset.addAll(inset);
704         
705         HashSet genset = (HashSet)genOfUnit.get(unit);
706         HashSet absgenset = (HashSet)absGenOfUnit.get(unit);
707         HashSet killset = (HashSet)killOfUnit.get(unit);
708         HashSet condset = (HashSet)conditionOfGen.get(unit);
709         
710         if (killset != null)
711             outset.removeAll(killset);
712         
713         if (arrayin)
714         {
715             Boolean   killall = (Boolean  )killAllArrayRef.get(stmt);
716             
717             if ((killall != null) && killall.booleanValue())
718             {
719                 List keylist = new ArrayList(outset);
720                 Iterator keyIt = keylist.iterator();
721                 while (keyIt.hasNext())
722                 {
723                     Object   key = keyIt.next();
724                     if (key instanceof ArrayRef)
725                         outset.remove(key);
726                 }
727             }
728             else
729             {
730                 Object   local = killArrayRelated.get(stmt);
731                 if (local != null)
732                 {
733                     List keylist = new ArrayList(outset);
734                     Iterator keyIt = keylist.iterator();
735                     while (keyIt.hasNext())
736                     {
737                         Object   key = keyIt.next();
738                         if (key instanceof ArrayRef)
739                         {
740                             Value base = ((ArrayRef)key).getBase();
741                             Value index = ((ArrayRef)key).getIndex();
742                             
743                             if (base.equals(local) || index.equals(local))
744                                 outset.remove(key);
745                         }
746                         
747                         if (rectarray)
748                         {
749                             if (key instanceof Array2ndDimensionSymbol)
750                             {
751                                 Object   base = ((Array2ndDimensionSymbol)key).getVar();
752                                 if (base.equals(local))
753                                     outset.remove(key);
754                             }
755                         }
756                     }
757                 }
758             }
759         }
760         
761         if (genset != null)
762         {
763             if (condset == null || (condset.size()==0))
764                 outset.addAll(genset);
765             else
766             {
767                 Iterator condIt = condset.iterator();
768                 while (condIt.hasNext())
769                 {
770                     if (inset.contains(condIt.next()))
771                     {
772                         outset.addAll(genset);
773                         break;
774                     }
775                 }
776             }
777         }
778         
779         if (absgenset != null)
780             outset.addAll(absgenset);
781     }
782     
783     protected void merge(Object   in1, Object   in2, Object   out)
784     {
785         HashSet inset1 = (HashSet)in1;
786         HashSet inset2 = (HashSet)in2;
787         HashSet outset = (HashSet)out;
788         
789         HashSet src = inset1;
790         
791         if (outset == inset1)
792             src = inset2;
793         else if (outset == inset2)
794             src = inset1;
795         else
796         {
797             outset.clear();
798             outset.addAll(inset2);
799         }
800         
801         outset.addAll(src);
802     }
803     
804     protected void copy(Object   source, Object   dest)
805     {
806         if (source == dest)
807             return;
808         
809         HashSet sourceSet = (HashSet)source;
810         HashSet destSet = (HashSet)dest;
811         
812         destSet.clear();
813         destSet.addAll(sourceSet);
814     }
815 }
816 
817 
818 
819 
820 
821
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags