src/edu/berkeley/cs/megacz/JArena.java

   1 package edu.berkeley.cs.megacz;
   2
   3 import soot.*;
   4 import soot.util.*;
   5 import java.util.*;
   6 import soot.toolkits.scalar.*;
   7 import soot.jimple.*;
   8 import soot.toolkits.graph.*;
   9 import soot.*;
  10 import soot.jimple.*;
  11 import soot.toolkits.scalar.*;
  12 import soot.toolkits.graph.*;
  13 import soot.util.*;
  14 import java.util.*;
  15
  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 {
  20
  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)
  32             addGen(u, lo);
  33     }
  34
  35     protected void copy(Object src, Object dest) {
  36         FlowSet sourceSet = (FlowSet)src, destSet = (FlowSet) dest;
  37         sourceSet.copy(destSet);
  38     }
  39
  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);
  45     }
  46
  47     FlowSet fullSet, emptySet;
  48     FlowUniverse allRefLocals;
  49     Map unitToGenerateSet;
  50
  51     protected void flowThrough(Object srcValue, Unit unit, List fallOut, List branchOuts) {
  52         FlowSet dest;
  53         FlowSet src  = (FlowSet) srcValue;
  54         Unit    s    = (Unit)    unit;
  55
  56         // Create working set.
  57         dest = (FlowSet)src.clone();
  58
  59         // Take out kill set.
  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)
  65                 dest.remove(value);
  66         }
  67
  68         // Perform gen.
  69         dest.union((FlowSet)unitToGenerateSet.get(unit), dest);
  70
  71         // Handle copy statements:
  72         //    x = y && 'y' in src => add 'x' to dest
  73         if (s instanceof DefinitionStmt)
  74         {
  75             DefinitionStmt as = (DefinitionStmt) s;
  76
  77             Value ro = as.getRightOp();
  78
  79             // extract cast argument
  80             if (ro instanceof CastExpr) ro = ((CastExpr) ro).getOp();
  81
  82             if (src.contains(ro) && as.getLeftOp() instanceof Local)
  83                 dest.add(as.getLeftOp());
  84         }
  85
  86         // Copy the out value to the fallthrough box (don't need iterator)
  87         {
  88             Iterator it = fallOut.iterator();
  89             while (it.hasNext()) {
  90                 FlowSet fs = (FlowSet) (it.next());
  91                 copy(dest, fs);
  92             }
  93         }
  94
  95         // Copy the out value to all branch boxes.
  96         {
  97             Iterator it = branchOuts.iterator();
  98             while (it.hasNext()) {
  99                 FlowSet fs = (FlowSet) (it.next());
 100                 copy(dest, fs);
 101             }
 102         }
 103
 104         // Handle if statements by patching dest sets.
 105         if (unit instanceof IfStmt)
 106         {
 107             Value cond = ((IfStmt)unit).getCondition();
 108             Value op1 = ((BinopExpr) cond).getOp1();
 109             Value op2 = ((BinopExpr) cond).getOp2();
 110             boolean isNeg = cond instanceof NeExpr;
 111             Value toGen = null;
 112
 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)
 116                 toGen = op1;
 117
 118             if (op2 instanceof Local && op1 instanceof NullConstant)
 119                 toGen = op2;
 120
 121             if (toGen != null)
 122             {
 123                 Iterator it = null;
 124
 125                 // if (toGen != null) goto l1: on branch, toGen nonnull.
 126                 if (isNeg)
 127                     it = branchOuts.iterator();
 128                 else
 129                     it = fallOut.iterator();
 130
 131                 while(it.hasNext()) {
 132                     FlowSet fs = (FlowSet) (it.next());
 133                     fs.add(toGen);
 134                 }
 135             }
 136
 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)
 140             {
 141                 toGen = null;
 142
 143                 if (src.contains(op1))
 144                     toGen = op2;
 145                 if (src.contains(op2))
 146                     toGen = op1;
 147
 148                 if (toGen != null)
 149                 {
 150                     Iterator branchIt = branchOuts.iterator();
 151                     while (branchIt.hasNext()) {
 152                         FlowSet fs = (FlowSet) (branchIt.next());
 153                         fs.add(toGen);
 154                     }
 155                 }
 156             }
 157         }
 158     }
 159
 160     public JArena(UnitGraph g) {
 161         super(g);
 162
 163         unitToGenerateSet = new HashMap();
 164
 165         Body b = g.getBody();
 166
 167         List refLocals = new LinkedList();
 168
 169         // set up universe, empty, full sets.
 170
 171         emptySet = new ArraySparseSet();
 172         fullSet = new ArraySparseSet();
 173
 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);
 179         }
 180
 181         // Create gen sets.
 182         Iterator unitIt = b.getUnits().iterator();
 183         while (unitIt.hasNext()) {
 184             Unit u = (Unit)unitIt.next();
 185             unitToGenerateSet.put(u, new ArraySparseSet());
 186
 187             if (u instanceof DefinitionStmt) {
 188                 Value lo = ((DefinitionStmt)u).getLeftOp();
 189                 if (lo instanceof Local && lo.getType() instanceof RefLikeType)
 190                     addGensFor((DefinitionStmt)u);
 191             }
 192
 193             Iterator boxIt = u.getUseAndDefBoxes().iterator();
 194             while (boxIt.hasNext()) {
 195                 Value boxValue = ((ValueBox) boxIt.next()).getValue();
 196                 Value base = null;
 197
 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();
 210                 }
 211
 212                 if (base != null &&
 213                       base instanceof Local &&
 214                       base.getType() instanceof RefLikeType)
 215                     addGen(u, base);
 216             }
 217         }
 218
 219         // Call superclass method to do work.
 220         doAnalysis();
 221     }
 222 }
 223