1 package edu.berkeley.cs.megacz;
6 import soot.toolkits.scalar.*;
8 import soot.toolkits.graph.*;
11 import soot.toolkits.scalar.*;
12 import soot.toolkits.graph.*;
16 /** Tracks which locals are definitely non-null.
17 * Author: Patrick Lam (plam@sable.mcgill.ca)
18 * Based on BranchedRefVarsAnalysis by Janus Godard (janus@place.org). */
19 class JArena extends ForwardBranchedFlowAnalysis {
21 protected Object newInitialFlow() { return fullSet.clone(); }
22 protected Object entryInitialFlow() { return emptySet.clone(); }
23 private void addGen(Unit u, Value v) { ArraySparseSet l = (ArraySparseSet)unitToGenerateSet.get(u); l.add(v); }
24 private void addGensFor(DefinitionStmt u) {
25 Value lo = u.getLeftOp();
26 Value ro = u.getRightOp();
27 if (ro instanceof NewExpr ||
28 ro instanceof NewArrayExpr ||
29 ro instanceof NewMultiArrayExpr ||
30 ro instanceof ThisRef ||
31 ro instanceof CaughtExceptionRef)
35 protected void copy(Object src, Object dest) {
36 FlowSet sourceSet = (FlowSet)src, destSet = (FlowSet) dest;
37 sourceSet.copy(destSet);
40 protected void merge(Object src1, Object src2, Object dest) {
41 FlowSet srcSet1 = (FlowSet) src1;
42 FlowSet srcSet2 = (FlowSet) src2;
43 FlowSet destSet = (FlowSet) dest;
44 srcSet1.intersection(srcSet2, destSet);
47 FlowSet fullSet, emptySet;
48 FlowUniverse allRefLocals;
49 Map unitToGenerateSet;
51 protected void flowThrough(Object srcValue, Unit unit, List fallOut, List branchOuts) {
53 FlowSet src = (FlowSet) srcValue;
56 // Create working set.
57 dest = (FlowSet)src.clone();
60 Iterator boxIt = s.getDefBoxes().iterator();
61 while (boxIt.hasNext()) {
62 ValueBox box = (ValueBox) boxIt.next();
63 Value value = box.getValue();
64 if (value instanceof Local && value.getType() instanceof RefLikeType)
69 dest.union((FlowSet)unitToGenerateSet.get(unit), dest);
71 // Handle copy statements:
72 // x = y && 'y' in src => add 'x' to dest
73 if (s instanceof DefinitionStmt)
75 DefinitionStmt as = (DefinitionStmt) s;
77 Value ro = as.getRightOp();
79 // extract cast argument
80 if (ro instanceof CastExpr) ro = ((CastExpr) ro).getOp();
82 if (src.contains(ro) && as.getLeftOp() instanceof Local)
83 dest.add(as.getLeftOp());
86 // Copy the out value to the fallthrough box (don't need iterator)
88 Iterator it = fallOut.iterator();
89 while (it.hasNext()) {
90 FlowSet fs = (FlowSet) (it.next());
95 // Copy the out value to all branch boxes.
97 Iterator it = branchOuts.iterator();
98 while (it.hasNext()) {
99 FlowSet fs = (FlowSet) (it.next());
104 // Handle if statements by patching dest sets.
105 if (unit instanceof IfStmt)
107 Value cond = ((IfStmt)unit).getCondition();
108 Value op1 = ((BinopExpr) cond).getOp1();
109 Value op2 = ((BinopExpr) cond).getOp2();
110 boolean isNeg = cond instanceof NeExpr;
113 // case 1: opN is a local and opM is NullConstant
114 // => opN nonnull on ne branch.
115 if (op1 instanceof Local && op2 instanceof NullConstant)
118 if (op2 instanceof Local && op1 instanceof NullConstant)
125 // if (toGen != null) goto l1: on branch, toGen nonnull.
127 it = branchOuts.iterator();
129 it = fallOut.iterator();
131 while(it.hasNext()) {
132 FlowSet fs = (FlowSet) (it.next());
137 // case 2: both ops are local and one op is non-null and testing equality
138 if (op1 instanceof Local && op2 instanceof Local &&
139 cond instanceof EqExpr)
143 if (src.contains(op1))
145 if (src.contains(op2))
150 Iterator branchIt = branchOuts.iterator();
151 while (branchIt.hasNext()) {
152 FlowSet fs = (FlowSet) (branchIt.next());
160 public JArena(UnitGraph g) {
163 unitToGenerateSet = new HashMap();
165 Body b = g.getBody();
167 List refLocals = new LinkedList();
169 // set up universe, empty, full sets.
171 emptySet = new ArraySparseSet();
172 fullSet = new ArraySparseSet();
174 // Find all locals in body.
175 Iterator localIt = b.getLocals().iterator();
176 while (localIt.hasNext()) {
177 Local l = (Local)localIt.next();
178 if (l.getType() instanceof RefLikeType) fullSet.add(l);
182 Iterator unitIt = b.getUnits().iterator();
183 while (unitIt.hasNext()) {
184 Unit u = (Unit)unitIt.next();
185 unitToGenerateSet.put(u, new ArraySparseSet());
187 if (u instanceof DefinitionStmt) {
188 Value lo = ((DefinitionStmt)u).getLeftOp();
189 if (lo instanceof Local && lo.getType() instanceof RefLikeType)
190 addGensFor((DefinitionStmt)u);
193 Iterator boxIt = u.getUseAndDefBoxes().iterator();
194 while (boxIt.hasNext()) {
195 Value boxValue = ((ValueBox) boxIt.next()).getValue();
198 if(boxValue instanceof InstanceFieldRef) {
199 base = ((InstanceFieldRef) (boxValue)).getBase();
200 } else if (boxValue instanceof ArrayRef) {
201 base = ((ArrayRef) (boxValue)).getBase();
202 } else if (boxValue instanceof InstanceInvokeExpr) {
203 base = ((InstanceInvokeExpr) boxValue).getBase();
204 } else if (boxValue instanceof LengthExpr) {
205 base = ((LengthExpr) boxValue).getOp();
206 } else if (u instanceof ThrowStmt) {
207 base = ((ThrowStmt)u).getOp();
208 } else if (u instanceof MonitorStmt) {
209 base = ((MonitorStmt)u).getOp();
213 base instanceof Local &&
214 base.getType() instanceof RefLikeType)
219 // Call superclass method to do work.