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


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.toolkits.scalar.* ;
31 import soot.toolkits.graph.*;
32 import soot.jimple.* ;
33 import soot.jimple.internal.* ;
34
35 import java.util.* ;
36 import soot.util.* ;
37
38 class ArrayBoundsCheckerAnalysis
39 {
40     protected Map blockToBeforeFlow;
41     protected Map unitToBeforeFlow;
42
43     private Map edgeMap;
44     private Set edgeSet;
45
46     private HashMap stableRoundOfUnits;
47     private boolean flowStable = false;
48
49     private Body body;
50     private ArrayRefBlockGraph graph;
51
52     private IntContainer zero = new IntContainer(0);
53
54     private boolean fieldin = false;
55     private HashMap localToFieldRef;
56     private HashMap fieldToFieldRef;
57     private HashSet allFieldRefs;
58     private int strictness = 2;
59
60     private boolean arrayin = false;
61     private HashMap localToArrayRef;
62     private HashSet allArrayRefs;
63
64     private boolean csin = false;
65     private HashMap localToExpr;
66
67     private boolean classfieldin = false;
68     private ClassFieldAnalysis cfield;
69
70     private boolean rectarray = false;
71     private HashSet rectarrayset;
72     private HashSet multiarraylocals;
73
74     private ArrayIndexLivenessAnalysis ailanalysis;
75
76     /* A little bit different from ForwardFlowAnalysis */
77     public ArrayBoundsCheckerAnalysis(Body body,
78                                       boolean takeClassField,
79                                       boolean takeFieldRef,
80                                       boolean takeArrayRef,
81                                       boolean takeCSE,
82                                       boolean takeRectArray)
83     {
84         classfieldin = takeClassField;
85         fieldin = takeFieldRef;
86         arrayin = takeArrayRef;
87         csin = takeCSE;
88         rectarray = takeRectArray;
89         
90         this.body = body;
91
92         SootMethod thismethod = body.getMethod();
93
94         if (Options.v().debug())
95             G.v().out.println("ArrayBoundsCheckerAnalysis started on "+thismethod.getName());
96
97         ailanalysis = new ArrayIndexLivenessAnalysis(new ExceptionalUnitGraph(body), fieldin, arrayin, csin, rectarray);
98         
99         if (fieldin)
100         {
101             this.localToFieldRef = ailanalysis.getLocalToFieldRef();
102             this.fieldToFieldRef = ailanalysis.getFieldToFieldRef();
103             this.allFieldRefs = ailanalysis.getAllFieldRefs();
104         }
105         
106         if (arrayin)
107         {
108             this.localToArrayRef = ailanalysis.getLocalToArrayRef();
109             this.allArrayRefs = ailanalysis.getAllArrayRefs();
110             if (rectarray)
111             {
112                 this.multiarraylocals = ailanalysis.getMultiArrayLocals();
113                 this.rectarrayset = new HashSet();
114
115                 RectangularArrayFinder pgbuilder = RectangularArrayFinder.v();
116
117                 Iterator localIt = multiarraylocals.iterator();
118                 while (localIt.hasNext())
119                 {
120                     Local local = (Local)localIt.next();
121                     
122                     MethodLocal mlocal = new MethodLocal(thismethod, local);
123                     
124                     if (pgbuilder.isRectangular(mlocal))
125                         this.rectarrayset.add(local);
126                 }
127             }
128         }
129         
130         if (csin)
131         {
132             this.localToExpr = ailanalysis.getLocalToExpr();
133         }
134
135         if (classfieldin)
136         {
137             this.cfield = ClassFieldAnalysis.v();
138         }
139
140         this.graph = new ArrayRefBlockGraph(body);
141
142         blockToBeforeFlow = new HashMap(graph.size()*2+1, 0.7f);
143         
144         edgeMap = new HashMap(graph.size()*2+1, 0.7f);
145         
146         edgeSet = buildEdgeSet(graph);
147         
148         doAnalysis();
149         
150         convertToUnitEntry();
151         
152         if (Options.v().debug())
153             G.v().out.println("ArrayBoundsCheckerAnalysis finished.");
154     }
155
156     private void convertToUnitEntry()
157     {
158         unitToBeforeFlow = new HashMap();
159         Iterator blockIt = blockToBeforeFlow.keySet().iterator();
160         while (blockIt.hasNext())
161         {
162             Block block = (Block)blockIt.next();
163             Unit first = block.getHead();
164             unitToBeforeFlow.put(first, blockToBeforeFlow.get(block));
165         }
166     }
167
168     /** buildEdgeSet creates a set of edges from directed graph.
169      */
170     public Set buildEdgeSet(DirectedGraph dg)
171     {
172         HashSet edges = new HashSet();
173
174         Iterator unitIt = dg.iterator();
175         while (unitIt.hasNext())
176         {
177             Object s = unitIt.next();
178
179             List preds = graph.getPredsOf(s);
180             List succs = graph.getSuccsOf(s);
181
182             /* Head units has in edge from itself to itself.*/
183             if (preds.size() == 0)
184             {
185                 edges.add(new FlowGraphEdge(s,s));
186             }
187             
188             /* End units has out edge from itself to itself.*/
189             if (succs.size() == 0)
190             {
191                 edges.add(new FlowGraphEdge(s,s));
192             }
193             else
194             {
195                 Iterator succIt = succs.iterator();
196                 while (succIt.hasNext())
197                 {
198                     edges.add(new FlowGraphEdge(s, succIt.next()));
199                 }
200             }
201         }
202         
203         return edges;
204     }
205     
206     public Object getFlowBefore(Object s)
207     {
208         return unitToBeforeFlow.get(s);
209     }
210
211     /* merge all preds' out set */
212     private void mergebunch(Object ins[], Object s, Object prevOut, Object out)
213     {
214         WeightedDirectedSparseGraph prevgraph = (WeightedDirectedSparseGraph)prevOut,
215             outgraph = (WeightedDirectedSparseGraph)out;
216
217         WeightedDirectedSparseGraph[] ingraphs
218             = new WeightedDirectedSparseGraph[ins.length];
219
220         for (int i=0; i<ins.length; i++)
221             ingraphs[i] = (WeightedDirectedSparseGraph)ins[i];
222
223         {
224             outgraph.addBoundedAll(ingraphs[0]);
225         
226             for (int i=1; i<ingraphs.length; i++)
227             {
228                 outgraph.unionSelf(ingraphs[i]);
229                 outgraph.makeShortestPathGraph();
230             }
231                 
232             // if (flowStable)
233 /*
234             Integer round = (Integer)stableRoundOfUnits.get(s);
235
236             if (round.intValue() < 2)
237             {
238                 stableRoundOfUnits.put(s, new Integer(round.intValue()+1));
239             }
240             else
241             {
242                 // To make output stable. compare with previous output value.
243                 outgraph.wideEdges((WeightedDirectedSparseGraph)prevOut);
244                 outgraph.makeShortestPathGraph();
245             }
246             */
247
248             outgraph.widenEdges(prevgraph);
249
250             // outgraph.makeShortestPathGraph();
251 /*
252             for (int i=0; i<ins.length; i++)
253             {
254                 G.v().out.println("in " + i);
255                 G.v().out.println(ins[i]);
256             }
257
258             G.v().out.println("out ");
259             G.v().out.println(out);
260             */
261         }
262     }
263
264     /* override ForwardFlowAnalysis
265      */
266     private void doAnalysis()
267     {
268         Date start = new Date();
269         if (Options.v().debug())
270             G.v().out.println("Building PseudoTopological order list on "+start);
271
272         LinkedList allUnits = (LinkedList)SlowPseudoTopologicalOrderer.v().newList(this.graph);
273                         
274         BoundedPriorityList changedUnits =
275             new BoundedPriorityList(allUnits);
276
277         // LinkedList changedUnits = new LinkedList(allUnits);
278
279         Date finish = new Date();
280         if (Options.v().debug())
281         {
282             long runtime = finish.getTime()-start.getTime();
283             long mins = runtime/60000;
284             long secs = (runtime%60000)/1000;
285             G.v().out.println("Building PseudoTopological order finished. "
286                                +"It took "+mins+" mins and "+secs+" secs.");
287         }
288
289         start = new Date();
290         if (Options.v().debug())
291             G.v().out.println("Doing analysis started on "+start);
292
293         {
294             for (int i=0; i<allUnits.size(); i++)
295             {
296                 Block block = (Block)allUnits.get(i);
297                 {
298                     Object tail = block.getTail();
299
300                     HashSet livelocals = (HashSet)ailanalysis.getFlowAfter(tail);
301         
302                     /*
303                     if (Options.v().debug())
304                     {
305                         G.v().out.println(tail);
306                         G.v().out.println(livelocals);
307                     }
308                     */
309                 }
310             }
311         }
312
313         HashSet changedUnitsSet = new HashSet(allUnits);
314
315         List changedSuccs;
316
317         /* An temporary object. */
318         FlowGraphEdge tmpEdge = new FlowGraphEdge();
319
320         /* If any output flow set has unknow value, it will be put in this set
321          */
322         HashSet unvisitedNodes = new HashSet(graph.size()*2+1, 0.7f);
323         
324         int numNodes = graph.size();
325
326         /* adjust livelocals set */
327         {
328             Iterator blockIt = graph.iterator();
329             while (blockIt.hasNext())
330             {
331                 Block block = (Block)blockIt.next();
332                 HashSet livelocals = (HashSet)ailanalysis.getFlowBefore(block.getHead());
333                 livelocals.add(zero);
334             }
335         }
336
337         /* Set initial values and nodes to visit. */
338         {
339             stableRoundOfUnits = new HashMap();
340             
341             Iterator it = graph.iterator();
342
343             while(it.hasNext())
344             {
345                 Block block = (Block)it.next();
346
347                 unvisitedNodes.add(block);
348                 stableRoundOfUnits.put(block, new Integer (0));
349
350                 /* only take out the necessary node set. */
351                 HashSet livelocals = (HashSet)ailanalysis.getFlowBefore(block.getHead());
352                 
353                 blockToBeforeFlow.put(block, new WeightedDirectedSparseGraph(livelocals, false));
354             }
355
356             Iterator edgeIt = edgeSet.iterator();
357             while (edgeIt.hasNext())
358             {
359                 FlowGraphEdge edge = (FlowGraphEdge)edgeIt.next();
360                 
361                 Block target = (Block)edge.to;
362                 HashSet livelocals = (HashSet)ailanalysis.getFlowBefore(target.getHead());
363                 
364                 edgeMap.put(edge, new WeightedDirectedSparseGraph(livelocals, false));
365             }
366         }
367
368         /* perform customized initialization. */
369         {
370             List headlist = graph.getHeads();
371             Iterator headIt = headlist.iterator();
372
373             while (headIt.hasNext())
374             {
375                 Object head = headIt.next() ;
376                 FlowGraphEdge edge = new FlowGraphEdge(head, head);
377
378                 WeightedDirectedSparseGraph initgraph =
379                     (WeightedDirectedSparseGraph)edgeMap.get(edge) ;
380
381                 initgraph.setTop();
382             }
383         }
384
385         /* Perform fixed point flow analysis.
386          */
387         {
388             WeightedDirectedSparseGraph beforeFlow =
389                 new WeightedDirectedSparseGraph(null, false);
390
391             // DebugMsg.counter1 += allUnits.size();
392
393             while(!changedUnits.isEmpty())
394             {
395                 Object s = changedUnits.removeFirst();
396                 changedUnitsSet.remove(s);
397
398                 // DebugMsg.counter2++;
399
400                 /* previousAfterFlow, old-out, it is null initially */
401                 WeightedDirectedSparseGraph previousBeforeFlow =
402                     (WeightedDirectedSparseGraph)blockToBeforeFlow.get(s);
403                 
404                 beforeFlow.setVertexes(previousBeforeFlow.getVertexes());
405
406                 // Compute and store beforeFlow
407 {
408                     List preds = graph.getPredsOf(s);
409
410                     /* the init node */
411                     if (preds.size() == 0)
412                     {
413                         tmpEdge.changeEndUnits(s,s);
414                         copy(edgeMap.get(tmpEdge), beforeFlow);
415                     }
416                     else if (preds.size() == 1)
417                     {
418                         tmpEdge.changeEndUnits(preds.get(0),s);
419                         copy(edgeMap.get(tmpEdge), beforeFlow);
420                         
421                         // widenGraphs(beforeFlow, previousBeforeFlow);
422 }
423                     else
424                     {
425                     /* has 2 or more preds, Updated by Feng. */
426                         Object predFlows[] = new Object [preds.size()] ;
427  
428                         boolean allUnvisited = true;
429                         Iterator predIt = preds.iterator();
430                         
431                         int index = 0 ;
432
433                         int lastVisited = 0;
434
435                         while(predIt.hasNext())
436                         {
437                             Object pred = predIt.next();
438
439                                   tmpEdge.changeEndUnits(pred,s);
440             
441                             if (!unvisitedNodes.contains(pred))
442                             {
443                                 allUnvisited = false;
444                                 lastVisited = index;
445                             }
446
447                             predFlows[index++] = edgeMap.get(tmpEdge);
448                               }
449                         // put the visited node as the first one
450
451                         if (allUnvisited)
452                         {
453                             G.v().out.println("Warning : see all unvisited node");
454                         }
455                         else
456                         {
457                             Object tmp = predFlows[0];
458                             predFlows[0] = predFlows[lastVisited];
459                             predFlows[lastVisited] = tmp;
460                         }
461
462                         mergebunch(predFlows, s, previousBeforeFlow, beforeFlow);
463                     }
464                     
465                     copy(beforeFlow, previousBeforeFlow);
466                 }
467
468                 /* Compute afterFlow and store it.
469                  * Now we do not have afterFlow, we only have the out edges.
470                  * Different out edges may have different flow set.
471                  * It returns back a list of succ units that edge has been
472                  * changed.
473                  */
474                 {
475                     changedSuccs = flowThrough(beforeFlow, s);
476                 }
477
478                 {
479                     for (int i = 0; i < changedSuccs.size(); i++)
480                     {
481                         Object succ = changedSuccs.get(i);
482                         if (!changedUnitsSet.contains(succ))
483                         {
484                             changedUnits.add(succ);
485                             changedUnitsSet.add(succ);
486                         }
487                     }
488                 }
489                 
490                 /* Decide to remove or add unit from/to unvisitedNodes set */
491                 {
492                     unvisitedNodes.remove(s);
493                     flowStable = unvisitedNodes.isEmpty();
494                 }
495             }
496         }
497
498         finish = new Date();
499         if (Options.v().debug())
500         {
501             long runtime = finish.getTime()-start.getTime();
502             long mins = runtime/60000;
503             long secs = (runtime/60000)/1000;
504             G.v().out.println("Doing analysis finished."
505                                + " It took "+mins+" mins and "+secs+ "secs.");
506         }
507     }
508
509     /* Flow go through a node, the output will be put into edgeMap, and also
510      * the changed succ will be in a list to return back.
511      */
512     private List flowThrough(Object inValue, Object unit)
513     {
514         ArrayList changedSuccs = new ArrayList();
515       
516         WeightedDirectedSparseGraph ingraph =
517             (WeightedDirectedSparseGraph)inValue;
518
519         Block block = (Block)unit ;
520
521         List succs = block.getSuccs();
522
523         // leave out the last element.
524 Unit s = block.getHead();
525         Unit nexts = block.getSuccOf(s);
526         while (nexts != null)
527         {
528             /* deal with array references */
529             assertArrayRef(ingraph, s);
530
531             /* deal with normal expressions. */
532             assertNormalExpr(ingraph, s);
533
534             s = nexts;
535             nexts = block.getSuccOf(nexts);
536         }
537
538         // at the end of block, it should update the out edges.
539 if (s instanceof IfStmt)
540         {
541           if (!assertBranchStmt(ingraph, s, block, succs, changedSuccs))
542             updateOutEdges(ingraph, block, succs, changedSuccs);
543         }
544         else
545         {
546             assertArrayRef(ingraph, s);
547             assertNormalExpr(ingraph, s);
548             updateOutEdges(ingraph, block, succs, changedSuccs);
549         }
550
551         return changedSuccs;
552     }
553
554     private void assertArrayRef(Object in, Unit unit)
555     {
556         if (!(unit instanceof AssignStmt))
557             return;
558
559         Stmt s = (Stmt)unit;
560
561         WeightedDirectedSparseGraph ingraph = (WeightedDirectedSparseGraph)in;
562
563         /*
564         ArrayRef op = null;
565        
566         Value leftOp = ((AssignStmt)s).getLeftOp();
567         Value rightOp = ((AssignStmt)s).getRightOp();
568
569         if (leftOp instanceof ArrayRef)
570             op = (ArrayRef)leftOp;
571
572         if (rightOp instanceof ArrayRef)
573             op = (ArrayRef)rightOp;
574
575         if (op == null)
576             return;
577         */
578         
579         if (!s.containsArrayRef())
580             return;
581
582         ArrayRef op = (ArrayRef)s.getArrayRef();
583         
584
585         Value base = ((ArrayRef)op).getBase();
586         Value index = ((ArrayRef)op).getIndex();
587
588         HashSet livelocals = (HashSet)ailanalysis.getFlowAfter(s);
589         if (!livelocals.contains(base) && !livelocals.contains(index))
590             return;
591         
592         if (index instanceof IntConstant)
593         {
594             int weight = ((IntConstant)index).value;
595             weight = -1-weight;
596
597             ingraph.addEdge(base, zero, weight);
598         }
599         else
600         {
601             // add two edges.
602 // index <= a.length -1;
603 ingraph.addEdge(base, index, -1);
604
605             // index >= 0
606 ingraph.addEdge(index, zero, 0);
607         }
608     }
609
610     private void assertNormalExpr(Object in, Unit s)
611     {
612
613         WeightedDirectedSparseGraph ingraph = (WeightedDirectedSparseGraph)in;
614
615         /* If it is a contains invoke expr, the parameter should be analyzed. */
616         if (fieldin)
617         {
618             Stmt stmt = (Stmt)s;
619             if (stmt.containsInvokeExpr())
620             {
621                 HashSet tokills = new HashSet();
622                 Value expr = stmt.getInvokeExpr();
623                 List parameters = ((InvokeExpr)expr).getArgs();
624                 
625                 /* kill only the locals in hierarchy. */
626                 if (strictness == 0)
627                 {
628                     Hierarchy hierarchy = Scene.v().getActiveHierarchy();
629
630                     for (int i=0; i<parameters.size(); i++)
631                     {
632                         Value para = (Value)parameters.get(i);
633                         Type type = para.getType();
634                         if (type instanceof RefType)
635                         {
636                             SootClass pclass = ((RefType)type).getSootClass();
637
638                             /* then we are looking for the possible types. */
639                             Iterator keyIt = localToFieldRef.keySet().iterator();
640                             while (keyIt.hasNext())
641                             {
642                                 Value local = (Value)keyIt.next();
643
644                                 Type ltype = local.getType();
645                                 
646                                 SootClass lclass = ((RefType)ltype).getSootClass();
647
648                                 if (hierarchy.isClassSuperclassOfIncluding(pclass, lclass) ||
649                                     hierarchy.isClassSuperclassOfIncluding(lclass, pclass))
650                                 {
651                                     HashSet toadd = (HashSet)localToFieldRef.get(local);
652                                     tokills.addAll(toadd);
653                                 }
654                             }
655                         }
656                     }
657                     
658                     if (expr instanceof InstanceInvokeExpr)
659                     {
660                         Value base = ((InstanceInvokeExpr)expr).getBase();
661                         Type type = base.getType();
662                         if (type instanceof RefType)
663                         {
664                             SootClass pclass = ((RefType)type).getSootClass();
665
666                             /* then we are looking for the possible types. */
667                             Iterator keyIt = localToFieldRef.keySet().iterator();
668                             while (keyIt.hasNext())
669                             {
670                                 Value local = (Value)keyIt.next();
671
672                                 Type ltype = local.getType();
673                                 
674                                 SootClass lclass = ((RefType)ltype).getSootClass();
675
676                                 if (hierarchy.isClassSuperclassOfIncluding(pclass, lclass) ||
677                                     hierarchy.isClassSuperclassOfIncluding(lclass, pclass))
678                                 {
679                                     HashSet toadd = (HashSet)localToFieldRef.get(local);
680                                     tokills.addAll(toadd);
681                                 }
682                             }
683                         }
684                     }
685                 }
686                 else
687                     /* kill all instance field reference. */
688                 if (strictness == 1)
689                 {
690                     boolean killall = false;
691                     if (expr instanceof InstanceInvokeExpr)
692                         killall = true;
693                     else
694                     {
695                         for (int i=0; i<parameters.size(); i++)
696                         {
697                             Value para = (Value)parameters.get(i);
698                             if (para.getType() instanceof RefType)
699                             {
700                                 killall = true;
701                                 break;
702                             }
703                         }
704                     }
705
706                     if (killall)
707                     {
708                         Iterator keyIt = localToFieldRef.keySet().iterator();
709                         while (keyIt.hasNext())
710                         {
711                             HashSet toadd = (HashSet)localToFieldRef.get(keyIt.next());
712                             tokills.addAll(toadd);
713                         }
714                     }
715                 }
716                 else
717                 if (strictness == 2)
718                 {
719                     // tokills.addAll(allFieldRefs);
720 HashSet vertexes = ingraph.getVertexes();
721                     Iterator nodeIt = vertexes.iterator();
722                     while (nodeIt.hasNext())
723                     {
724                         Object node = nodeIt.next();
725                         if (node instanceof FieldRef)
726                             ingraph.killNode(node);
727                     }
728                 }
729
730                 /*
731                 Iterator killIt = tokills.iterator();
732                 while (killIt.hasNext())
733                     ingraph.killNode(killIt.next());
734                 */
735             }
736         }
737
738         if (arrayin)
739         {
740             Stmt stmt = (Stmt)s;
741
742             if (stmt.containsInvokeExpr())
743             {
744                 if (strictness == 2)
745                 {
746                     /*
747                     Iterator killIt = allArrayRefs.iterator();
748                     while (killIt.hasNext())
749                     {
750                         ingraph.killNode(killIt.next());
751                     }
752                     */
753                     HashSet vertexes = ingraph.getVertexes();
754                     Iterator nodeIt = vertexes.iterator();
755                     while (nodeIt.hasNext())
756                     {
757                         Object node = nodeIt.next();
758                         if (node instanceof ArrayRef)
759                             ingraph.killNode(node);
760
761                         /*
762                         if (rectarray)
763                             if (node instanceof Array2ndDimensionSymbol)
764                                 ingraph.killNode(node);
765                         */
766                     }
767                 }
768             }
769         }
770
771         if (!(s instanceof AssignStmt))
772             return;
773
774         Value leftOp = ((AssignStmt)s).getLeftOp();
775         Value rightOp = ((AssignStmt)s).getRightOp();
776
777
778         HashSet livelocals = (HashSet)ailanalysis.getFlowAfter(s);
779
780         if (fieldin)
781         {
782             if (leftOp instanceof Local)
783             {
784                 HashSet fieldrefs = (HashSet)localToFieldRef.get(leftOp);
785                 
786                 if (fieldrefs != null)
787                 {
788                     Iterator refsIt = fieldrefs.iterator();
789                     while (refsIt.hasNext())
790                     {
791                         Object ref = refsIt.next();
792                         if (livelocals.contains(ref))
793                             ingraph.killNode(ref);
794                     }
795                 }
796             }
797             else
798             if (leftOp instanceof InstanceFieldRef)
799             {
800                 SootField field = ((InstanceFieldRef)leftOp).getField();
801                 
802                 HashSet fieldrefs = (HashSet)fieldToFieldRef.get(field);
803                 
804                 if (fieldrefs != null)
805                 {
806                     Iterator refsIt = fieldrefs.iterator();
807                     while (refsIt.hasNext())
808                     {
809                         Object ref = refsIt.next();
810                         if (livelocals.contains(ref))
811                             ingraph.killNode(ref);
812                     }
813                 }
814             }
815         }
816
817         if (arrayin)
818         {
819             /* a = ..; kill all references of a;
820                i = ..; kill all references with index i;
821             */
822             if (leftOp instanceof Local)
823             {
824                 /*
825                 HashSet arrayrefs = (HashSet)localToArrayRef.get(leftOp);
826                 
827                 if (arrayrefs != null)
828                 {
829                     Iterator refsIt = arrayrefs.iterator();
830                     while (refsIt.hasNext())
831                     {
832                         Object ref = refsIt.next();
833                         ingraph.killNode(ref);
834                     }
835                 }
836                 */
837                 HashSet vertexes = ingraph.getVertexes();
838                 Iterator nodeIt = vertexes.iterator();
839                 while (nodeIt.hasNext())
840                 {
841                     Object node = nodeIt.next();
842                     if (node instanceof ArrayRef)
843                     {
844                         Value base = ((ArrayRef)node).getBase();
845                         Value index = ((ArrayRef)node).getIndex();
846                         
847                         if (base.equals(leftOp) || index.equals(leftOp))
848                             ingraph.killNode(node);
849                     }
850
851                     if (rectarray)
852                     {
853                         if (node instanceof Array2ndDimensionSymbol)
854                         {
855                             Object base = ((Array2ndDimensionSymbol)node).getVar();
856                             if (base.equals(leftOp))
857                                 ingraph.killNode(node);
858                         }
859                     }
860                 }
861             }
862             else
863                 /* kill all array references */
864             if (leftOp instanceof ArrayRef)
865             {
866                 /*
867                 Iterator allrefsIt = allArrayRefs.iterator();
868                 while (allrefsIt.hasNext())
869                 {
870                     Object ref = allrefsIt.next();
871                     ingraph.killNode(ref);
872                 }
873                 */
874                 HashSet vertexes = (HashSet)ingraph.getVertexes();
875                 {
876                     Iterator nodeIt = vertexes.iterator();
877                     while (nodeIt.hasNext())
878                     {
879                         Object node = nodeIt.next();
880                         if (node instanceof ArrayRef)
881                             ingraph.killNode(node);
882                     }
883                 }
884
885                 /* only when multiarray was given a new value to its sub dimension, we kill all second dimensions of arrays */
886                 /*
887                 if (rectarray)
888                 {
889                     Value base = ((ArrayRef)leftOp).getBase();
890
891                     if (multiarraylocals.contains(base))
892                     {
893                         Iterator nodeIt = vertexes.iterator();
894                         while (nodeIt.hasNext())
895                         {
896                             Object node = nodeIt.next();
897                             if (node instanceof Array2ndDimensionSymbol)
898                                 ingraph.killNode(node);
899                         }
900                     }
901                 }
902                 */
903             }
904         }
905
906         if ( !livelocals.contains(leftOp) && !livelocals.contains(rightOp))
907             return;
908
909         // i = i;
910 if (rightOp.equals(leftOp))
911             return;
912
913         if (csin)
914         {
915             HashSet exprs = (HashSet)localToExpr.get(leftOp);
916             if (exprs != null)
917             {
918                 Iterator exprIt = exprs.iterator();
919                 while (exprIt.hasNext())
920                 {
921                     ingraph.killNode(exprIt.next());
922                 }
923             }
924         }
925
926
927         // i = i + c; is special
928 if (rightOp instanceof AddExpr)
929         {
930             Value op1 = ((AddExpr)rightOp).getOp1();
931             Value op2 = ((AddExpr)rightOp).getOp2();
932
933             if (op1 == leftOp && op2 instanceof IntConstant)
934             {
935                 int inc_w = ((IntConstant)op2).value;
936                 ingraph.updateWeight(leftOp, inc_w);
937                 return;
938             }
939             else
940             if (op2 == leftOp && op1 instanceof IntConstant)
941             {
942                 int inc_w = ((IntConstant)op1).value;
943                 ingraph.updateWeight(leftOp, inc_w);
944                 return;
945             }
946         }
947         
948         // i = i - c; is also special
949 if (rightOp instanceof SubExpr)
950         {
951             Value op1 = ((SubExpr)rightOp).getOp1();
952             Value op2 = ((SubExpr)rightOp).getOp2();
953
954             if ((op1 == leftOp) && (op2 instanceof IntConstant))
955             {
956                 int inc_w = - ((IntConstant)op2).value;
957                 ingraph.updateWeight(leftOp, inc_w);
958                 return;
959             }
960         }
961
962         // i = j; i = j + c; i = c + j; need two operations, kill node and add new relationship.
963 // kill left hand side,
964
965         ingraph.killNode(leftOp);
966
967         // add new relationship.
968
969         // i = c;
970 if (rightOp instanceof IntConstant)
971         {
972             int inc_w = ((IntConstant)rightOp).value;
973             ingraph.addMutualEdges(zero, leftOp, inc_w);
974             return;
975         }
976
977         // i = j;
978 if (rightOp instanceof Local)
979         {
980             ingraph.addMutualEdges(rightOp, leftOp, 0);
981             return;
982         }
983
984         if (rightOp instanceof FieldRef)
985         {
986             if (fieldin)
987             {
988                 ingraph.addMutualEdges(rightOp, leftOp, 0);
989             }
990
991             if (classfieldin)
992             {
993                 SootField field = ((FieldRef)rightOp).getField();
994                 IntValueContainer flength = (IntValueContainer)cfield.getFieldInfo(field);
995
996                 if (flength != null)
997                 {
998                     if (flength.isInteger())
999                     {
1000                        ingraph.addMutualEdges(zero, leftOp, flength.getValue());
1001                    }
1002                }
1003            }
1004
1005            return;
1006        }
1007
1008        /*
1009        if (rectarray)
1010        {
1011            Type leftType = leftOp.getType();
1012
1013            if ((leftType instanceof ArrayType) && (rightOp instanceof ArrayRef))
1014            {
1015                Local base = (Local)((ArrayRef)rightOp).getBase();
1016                
1017                SymbolArrayLength sv = (SymbolArrayLength)lra_analysis.getSymbolLengthAt(base, s);
1018                if (sv != null)
1019                {
1020                    ingraph.addMutualEdges(leftOp, sv.next(), 0);
1021                }
1022            }
1023        }
1024        */
1025
1026        if (arrayin)
1027        {
1028            if (rightOp instanceof ArrayRef)
1029            {
1030                ingraph.addMutualEdges(rightOp, leftOp, 0);
1031
1032                if (rectarray)
1033                {
1034                    Value base = ((ArrayRef)rightOp).getBase();
1035
1036                    if (rectarrayset.contains(base))
1037                    {
1038                        ingraph.addMutualEdges(leftOp, Array2ndDimensionSymbol.v(base), 0);
1039                    }
1040                }
1041
1042                return;
1043            }
1044        }
1045
1046        if (csin)
1047        {
1048            Value rhs = rightOp;
1049
1050            if (rhs instanceof BinopExpr)
1051            {
1052                Value op1 = ((BinopExpr)rhs).getOp1();
1053                Value op2 = ((BinopExpr)rhs).getOp2();
1054
1055                if (rhs instanceof AddExpr)
1056                {
1057                    if ((op1 instanceof Local) &&
1058                        (op2 instanceof Local))
1059                    {
1060                        ingraph.addMutualEdges(rhs, leftOp, 0);
1061                        return;
1062                    }
1063                }
1064                else
1065                if (rhs instanceof MulExpr)
1066                {
1067                    if ((op1 instanceof Local) ||
1068                        (op2 instanceof Local))
1069                    {
1070                        ingraph.addMutualEdges(rhs, leftOp, 0);
1071                        return;
1072                    }
1073                }
1074                else
1075                if (rhs instanceof SubExpr)
1076                {
1077                    if (op2 instanceof Local)
1078                    {
1079                        ingraph.addMutualEdges(rhs, leftOp, 0);
1080                        return;
1081                    }
1082                }
1083            }
1084        }
1085
1086
1087        // i = j + c; or i = c + j;
1088 if (rightOp instanceof AddExpr)
1089        {
1090            Value op1 = ((AddExpr)rightOp).getOp1();
1091            Value op2 = ((AddExpr)rightOp).getOp2();
1092
1093            if ( (op1 instanceof Local) && (op2 instanceof IntConstant) )
1094            {
1095                int inc_w = ((IntConstant)op2).value;
1096                ingraph.addMutualEdges(op1, leftOp, inc_w);
1097                return;
1098            }
1099
1100            if ( (op2 instanceof Local) && (op1 instanceof IntConstant) )
1101            {
1102                int inc_w = ((IntConstant)op1).value;
1103                ingraph.addMutualEdges(op2, leftOp, inc_w);
1104                return;
1105            }
1106        }
1107
1108        // only i = j - c was considered.
1109 if (rightOp instanceof SubExpr)
1110        {
1111            Value op1 = ((SubExpr)rightOp).getOp1();
1112            Value op2 = ((SubExpr)rightOp).getOp2();
1113
1114            if ((op1 instanceof Local) && (op2 instanceof IntConstant))
1115            {
1116                int inc_w = - ((IntConstant)op2).value;
1117                ingraph.addMutualEdges(op1, leftOp, inc_w);
1118                return;
1119            }
1120        }
1121        
1122        // new experessions can also generate relationship
1123 // a = new A[i]; a = new A[c];
1124 if (rightOp instanceof NewArrayExpr)
1125        {
1126            Value size = ((NewArrayExpr)rightOp).getSize();
1127            if (size instanceof Local)
1128            {
1129                ingraph.addMutualEdges(size, leftOp, 0);
1130                return;
1131            }
1132
1133            if (size instanceof IntConstant)
1134            {
1135                int inc_w = ((IntConstant)size).value;
1136                ingraph.addMutualEdges(zero, leftOp, inc_w);
1137                return;
1138            }
1139        }
1140
1141        // a = new A[i][].. ; a = new A[c]...;
1142 if (rightOp instanceof NewMultiArrayExpr)
1143        {
1144            Value size = ((NewMultiArrayExpr)rightOp).getSize(0);
1145            if (size instanceof Local)
1146            {
1147                ingraph.addMutualEdges(size, leftOp, 0);
1148            }
1149            else
1150            if (size instanceof IntConstant)
1151            {
1152                int inc_w = ((IntConstant)size).value;
1153                ingraph.addMutualEdges(zero, leftOp, inc_w);
1154            }
1155
1156            if (arrayin && rectarray)
1157            {
1158                if (((NewMultiArrayExpr)rightOp).getSizeCount() > 1)
1159                {
1160                    size = ((NewMultiArrayExpr)rightOp).getSize(1);
1161                    if (size instanceof Local)
1162                    {
1163                        ingraph.addMutualEdges(size, Array2ndDimensionSymbol.v(leftOp), 0);
1164                    }
1165                    else
1166                    if (size instanceof IntConstant)
1167                    {
1168                        int inc_w = ((IntConstant)size).value;
1169                        ingraph.addMutualEdges(zero, Array2ndDimensionSymbol.v(leftOp), inc_w);
1170                    }
1171                }
1172            }
1173
1174            return;
1175        }
1176
1177        // i = a.length
1178 if (rightOp instanceof LengthExpr)
1179        {
1180            Value base = ((LengthExpr)rightOp).getOp();
1181            ingraph.addMutualEdges(base, leftOp, 0);
1182            return;
1183        }
1184    }
1185
1186  /* assert the branch statement
1187   * return true, if the out condition changed,
1188   * false, otherwise
1189   */
1190    private boolean assertBranchStmt(Object in,
1191                                     Unit s, Block current,
1192                                     List succs,
1193                                     List changedSuccs)
1194    {
1195        IfStmt ifstmt = (IfStmt)s;
1196
1197        // take out the condition.
1198 Value cmpcond = ifstmt.getCondition();
1199
1200        if (!(cmpcond instanceof ConditionExpr))
1201            return false;
1202
1203        // how may succs?
1204 if (succs.size() != 2) {
1205          return false;
1206        }
1207
1208        Stmt targetUnit = ifstmt.getTarget();
1209        Block targetBlock = (Block)succs.get(0);
1210        Block nextBlock = (Block)succs.get(1);
1211
1212        if (!targetUnit.equals(targetBlock.getHead()))
1213        {
1214            Block swap = targetBlock;
1215            targetBlock = nextBlock;
1216            nextBlock = swap;
1217        }
1218
1219        Value op1 = ((ConditionExpr)cmpcond).getOp1();
1220        Value op2 = ((ConditionExpr)cmpcond).getOp2();
1221
1222        HashSet livelocals = (HashSet)ailanalysis.getFlowAfter(s);
1223
1224        if (!livelocals.contains(op1) && !livelocals.contains(op2))
1225            return false;
1226
1227        WeightedDirectedSparseGraph ingraph = (WeightedDirectedSparseGraph)in;
1228
1229        WeightedDirectedSparseGraph targetgraph = ingraph.dup();
1230
1231        // EqExpr, GeExpr, GtExpr, LeExpr, LtExpr, NeExpr
1232 if ((cmpcond instanceof EqExpr) ||
1233            (cmpcond instanceof NeExpr) )
1234        {
1235            Object node1 = op1, node2 = op2;
1236            int weight = 0;
1237            if (node1 instanceof IntConstant)
1238            {
1239                      weight = ((IntConstant)node1).value;
1240                node1 = zero;
1241            }
1242            if (node2 instanceof IntConstant)
1243            {
1244                weight = ((IntConstant)node2).value;
1245                node2 = zero;
1246            }
1247
1248            if (node1 == node2)
1249                return false;
1250            
1251            if (cmpcond instanceof EqExpr)
1252                targetgraph.addMutualEdges(node1, node2, weight);
1253            else
1254                ingraph.addMutualEdges(node1, node2, weight);
1255        }
1256        else
1257            // i > j
1258 if ((cmpcond instanceof GtExpr) ||
1259            // i >= j
1260 (cmpcond instanceof GeExpr) )
1261        {
1262            Object node1 = op1, node2 = op2;
1263            int weight = 0;
1264            
1265            if (node1 instanceof IntConstant)
1266            {
1267                weight += ((IntConstant)node1).value;
1268                node1 = zero;
1269            }
1270
1271            if (node2 instanceof IntConstant)
1272            {
1273                weight -= ((IntConstant)node2).value;
1274                node2 = zero;
1275            }
1276            
1277            if (node1 == node2)
1278                return false;
1279
1280            if (cmpcond instanceof GtExpr)
1281            {
1282                targetgraph.addEdge(node1, node2, weight-1);
1283                ingraph.addEdge(node2, node1, -weight);
1284            }
1285            else
1286            {
1287                targetgraph.addEdge(node1, node2, weight);
1288                ingraph.addEdge(node2, node1, -weight-1);
1289            }
1290        }
1291        else
1292            // i < j
1293 if ((cmpcond instanceof LtExpr) ||
1294            (cmpcond instanceof LeExpr) )
1295        {
1296            Object node1 = op1, node2 = op2;
1297            int weight = 0;
1298            
1299            if (node1 instanceof IntConstant)
1300            {
1301                weight -= ((IntConstant)node1).value;
1302                node1 = zero;
1303            }
1304
1305            if (node2 instanceof IntConstant)
1306            {
1307                weight += ((IntConstant)node2).value;
1308                node2 = zero;
1309            }
1310
1311            if (node1 == node2)
1312                return false;
1313            
1314            if (cmpcond instanceof LtExpr)
1315            {
1316                targetgraph.addEdge(node2, node1, weight-1);
1317                ingraph.addEdge(node1, node2, -weight);
1318            }
1319            else
1320            {
1321                targetgraph.addEdge(node2, node1, weight);
1322                ingraph.addEdge(node1, node2, -weight-1);
1323            }
1324        }
1325        else
1326            return false;
1327
1328        // update out edges and changed succs.
1329 // targetgraph -> targetBlock
1330
1331        FlowGraphEdge targetEdge = new FlowGraphEdge(current, targetBlock);
1332        WeightedDirectedSparseGraph prevtarget = (WeightedDirectedSparseGraph)edgeMap.get(targetEdge);
1333        boolean changed = false;
1334
1335               targetgraph.makeShortestPathGraph();
1336
1337        WeightedDirectedSparseGraph tmpgraph =
1338            new WeightedDirectedSparseGraph(prevtarget.getVertexes(), true);
1339
1340        copy(targetgraph, tmpgraph);
1341
1342        if (!tmpgraph.equals(prevtarget))
1343        {
1344            prevtarget.replaceAllEdges(tmpgraph);
1345            changed = true;
1346        }
1347
1348        if (changed)
1349            changedSuccs.add(targetBlock);
1350
1351        
1352        // ingraph -> nextBlock
1353 FlowGraphEdge nextEdge = new FlowGraphEdge(current, nextBlock);
1354        WeightedDirectedSparseGraph prevnext = (WeightedDirectedSparseGraph)edgeMap.get(nextEdge);
1355        changed = false;
1356
1357               ingraph.makeShortestPathGraph();
1358
1359        tmpgraph = new WeightedDirectedSparseGraph(prevnext.getVertexes(), true);
1360            
1361        copy(ingraph, tmpgraph);
1362
1363        if (!tmpgraph.equals(prevnext))
1364        {
1365            prevnext.replaceAllEdges(tmpgraph);
1366            changed = true;
1367        }
1368
1369        if (changed)
1370            changedSuccs.add(nextBlock);
1371
1372        return true;
1373
1374    }
1375
1376    private void updateOutEdges(Object in,
1377                                Block current,
1378                                List succs,
1379                                List changedSuccs)
1380    {
1381        WeightedDirectedSparseGraph ingraph = (WeightedDirectedSparseGraph)in;
1382
1383               ingraph.makeShortestPathGraph();
1384
1385        for (int i=0; i<succs.size(); i++)
1386        {
1387            Object next = succs.get(i);
1388            FlowGraphEdge nextEdge = new FlowGraphEdge(current, next);
1389            
1390            WeightedDirectedSparseGraph prevs = (WeightedDirectedSparseGraph)edgeMap.get(nextEdge);
1391            boolean changed = false;
1392
1393            /* equals should be used to take out sub graph first */
1394            
1395            WeightedDirectedSparseGraph tmpgraph =
1396                new WeightedDirectedSparseGraph(prevs.getVertexes(), true);
1397
1398            copy(ingraph, tmpgraph);
1399
1400            if (!tmpgraph.equals(prevs))
1401            {
1402                prevs.replaceAllEdges(tmpgraph);
1403                changed = true;
1404            }
1405
1406            if (changed)
1407                changedSuccs.add(next);
1408        }
1409    }
1410
1411    protected void copy(Object from, Object to)
1412    {
1413        WeightedDirectedSparseGraph fromgraph =
1414            (WeightedDirectedSparseGraph)from;
1415        WeightedDirectedSparseGraph tograph=
1416            (WeightedDirectedSparseGraph)to;
1417
1418        tograph.clear();
1419        tograph.addBoundedAll(fromgraph);
1420    }
1421
1422    protected void widenGraphs(Object current, Object before)
1423    {
1424        WeightedDirectedSparseGraph curgraphs =
1425            (WeightedDirectedSparseGraph)current;
1426        WeightedDirectedSparseGraph pregraphs =
1427            (WeightedDirectedSparseGraph)before;
1428
1429        curgraphs.widenEdges(pregraphs);
1430        curgraphs.makeShortestPathGraph();
1431    }
1432
1433    private void outputGraphs(Object graphs)
1434    {
1435        WeightedDirectedSparseGraph gs = (WeightedDirectedSparseGraph)graphs;
1436    }
1437}
1438
1439

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags