NullnessAnalysis


1   import soot.*;
2   import soot.jimple.*;
3   import soot.toolkits.scalar.*;
4   import soot.toolkits.graph.*;
5   import soot.util.*;
6   
7   import java.util.*;
8   
9   /** Tracks which locals are definitely non-null.
10   * Author: Patrick Lam (plam@sable.mcgill.ca)
11   * Based on BranchedRefVarsAnalysis by Janus Godard (janus@place.org). */
12  class NullnessAnalysis extends ForwardBranchedFlowAnalysis
13  {
14      protected void copy(Object   src, 
15                          Object   dest) {
16          FlowSet sourceSet = (FlowSet)src,
17              destSet = (FlowSet) dest;
18          
19          sourceSet.copy(destSet);
20      }
21  
22  
23      protected void merge(Object   src1, Object   src2, Object   dest)
24      {
25          FlowSet srcSet1 = (FlowSet) src1;
26          FlowSet srcSet2 = (FlowSet) src2;
27          FlowSet destSet = (FlowSet) dest;
28  
29          srcSet1.intersection(srcSet2, destSet);
30      }
31  
32      FlowSet fullSet, emptySet;
33      FlowUniverse allRefLocals;
34      Map unitToGenerateSet;
35  
36      protected void flowThrough(Object   srcValue, Unit unit,
37                                 List fallOut, List branchOuts)
38      {
39          FlowSet dest;
40          FlowSet src  = (FlowSet) srcValue;
41          Unit    s    = (Unit)    unit;
42  
43          // Create working set.
44          dest = (FlowSet)src.clone();
45  
46          // Take out kill set.
47          Iterator boxIt = s.getDefBoxes().iterator();
48          while (boxIt.hasNext()) {
49              ValueBox box = (ValueBox) boxIt.next();
50              Value value = box.getValue();
51              if (value instanceof Local && 
52                      value.getType() instanceof RefLikeType)
53                  dest.remove(value);
54          }
55  
56          // Perform gen.
57          dest.union((FlowSet)unitToGenerateSet.get(unit), dest);
58  
59          // Handle copy statements: 
60          //    x = y && 'y' in src => add 'x' to dest
61          if (s instanceof DefinitionStmt)
62          {
63              DefinitionStmt as = (DefinitionStmt) s;
64  
65              Value ro = as.getRightOp();
66  
67              // extract cast argument
68              if (ro instanceof CastExpr)
69                  ro = ((CastExpr) ro).getOp();
70          
71              if (src.contains(ro) &&
72                    as.getLeftOp() instanceof Local)
73                  dest.add(as.getLeftOp());
74          }
75  
76          // Copy the out value to the fallthrough box (don't need iterator)
77          {
78              Iterator it = fallOut.iterator();
79              while (it.hasNext()) {
80                  FlowSet fs = (FlowSet) (it.next());
81                  copy(dest, fs);
82              }
83          }
84          
85          // Copy the out value to all branch boxes.
86          {
87              Iterator it = branchOuts.iterator();
88              while (it.hasNext()) {
89                  FlowSet fs = (FlowSet) (it.next());
90                  copy(dest, fs);
91              }
92          }
93  
94          // Handle if statements by patching dest sets.
95          if (unit instanceof IfStmt)
96          {
97              Value cond = ((IfStmt)unit).getCondition();
98              Value op1 = ((BinopExpr) cond).getOp1();
99              Value op2 = ((BinopExpr) cond).getOp2();
100             boolean isNeg = cond instanceof NeExpr;
101             Value toGen = null;
102 
103             // case 1: opN is a local and opM is NullConstant
104             //          => opN nonnull on ne branch.
105             if (op1 instanceof Local && op2 instanceof NullConstant)
106                 toGen = op1;
107 
108             if (op2 instanceof Local && op1 instanceof NullConstant)
109                 toGen = op2;
110 
111             if (toGen != null)
112             {
113                 Iterator it = null;
114 
115                 // if (toGen != null) goto l1: on branch, toGen nonnull.
116                 if (isNeg)
117                     it = branchOuts.iterator();
118                 else
119                     it = fallOut.iterator();
120 
121                 while(it.hasNext()) {
122                     FlowSet fs = (FlowSet) (it.next());
123                     fs.add(toGen);
124                 }
125             }
126 
127             // case 2: both ops are local and one op is non-null and testing equality
128             if (op1 instanceof Local && op2 instanceof Local && 
129                 cond instanceof EqExpr)
130             {
131                 toGen = null;
132 
133                 if (src.contains(op1))
134                     toGen = op2;
135                 if (src.contains(op2))
136                     toGen = op1;
137 
138                 if (toGen != null)
139                 {
140                     Iterator branchIt = branchOuts.iterator();
141                     while (branchIt.hasNext()) {
142                         FlowSet fs = (FlowSet) (branchIt.next());
143                         fs.add(toGen);
144                     }
145                 }
146             }    
147         }
148     }
149 
150     protected Object   newInitialFlow()
151     {
152         return fullSet.clone();
153     }
154 
155     protected Object   entryInitialFlow()
156     {
157         // everything could be null
158         return emptySet.clone();
159     }
160 
161     private void addGen(Unit u, Value v)
162     {
163         ArraySparseSet l = (ArraySparseSet)unitToGenerateSet.get(u);
164         l.add(v);
165     }
166 
167     private void addGensFor(DefinitionStmt u)
168     {
169         Value lo = u.getLeftOp();
170         Value ro = u.getRightOp();
171 
172         if (ro instanceof NewExpr ||
173              ro instanceof NewArrayExpr ||
174              ro instanceof NewMultiArrayExpr ||
175              ro instanceof ThisRef ||
176              ro instanceof CaughtExceptionRef)
177             addGen(u, lo);
178     }
179 
180     public NullnessAnalysis(UnitGraph g)
181     {
182         super(g);
183 
184         unitToGenerateSet = new HashMap();
185 
186         Body b = g.getBody();
187 
188         List refLocals = new LinkedList();
189 
190         // set up universe, empty, full sets.
191 
192         emptySet = new ArraySparseSet();
193         fullSet = new ArraySparseSet();
194 
195         // Find all locals in body.
196         Iterator localIt = b.getLocals().iterator();
197         while (localIt.hasNext())
198         {
199             Local l = (Local)localIt.next();
200             if (l.getType() instanceof RefLikeType)
201                 fullSet.add(l);
202         }
203 
204         // Create gen sets.
205         Iterator unitIt = b.getUnits().iterator();
206         while (unitIt.hasNext())
207         {
208             Unit u = (Unit)unitIt.next();
209             unitToGenerateSet.put(u, new ArraySparseSet());
210 
211             if (u instanceof DefinitionStmt)
212             {
213                 Value lo = ((DefinitionStmt)u).getLeftOp();
214                 if (lo instanceof Local && 
215                        lo.getType() instanceof RefLikeType)
216                     addGensFor((DefinitionStmt)u);
217             }
218 
219             Iterator boxIt = u.getUseAndDefBoxes().iterator();
220             while (boxIt.hasNext())
221             {
222                 Value boxValue = ((ValueBox) boxIt.next()).getValue();
223                 Value base = null;
224                     
225                 if(boxValue instanceof InstanceFieldRef) {
226                     base = ((InstanceFieldRef) (boxValue)).getBase();
227                 } else if (boxValue instanceof ArrayRef) {
228                     base = ((ArrayRef) (boxValue)).getBase();
229                 } else if (boxValue instanceof InstanceInvokeExpr) {
230                     base = ((InstanceInvokeExpr) boxValue).getBase();
231                 } else if (boxValue instanceof LengthExpr) {
232                     base = ((LengthExpr) boxValue).getOp();
233                 } else if (u instanceof ThrowStmt) {
234                     base = ((ThrowStmt)u).getOp();
235                 } else if (u instanceof MonitorStmt) {
236                     base = ((MonitorStmt)u).getOp();
237                 }
238 
239                 if (base != null && 
240                       base instanceof Local && 
241                       base.getType() instanceof RefLikeType)
242                     addGen(u, base);
243             }
244         }
245 
246         // Call superclass method to do work.
247         doAnalysis();
248     }
249 }
250 
251
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags