1 19 20 package soot.toolkits.scalar; 21 import soot.options.*; 22 23 import soot.jimple.*; 24 import soot.toolkits.graph.*; 25 import soot.*; 26 import soot.util.*; 27 import java.util.*; 28 29 30 33 public class CombinedDUAnalysis extends BackwardFlowAnalysis implements CombinedAnalysis, LocalDefs, LocalUses, LiveLocals 34 { 35 private Map defsOfAt = new HashMap(); 37 public List getDefsOfAt(Local l, Unit s) { 38 Cons cons = new Cons(l, s); 39 List ret = (List) defsOfAt.get(cons); 40 if(ret == null) { 41 defsOfAt.put(cons, ret = new ArrayList()); 42 } 43 return ret; 44 } 45 private Map usesOf = new HashMap(); 46 public List getUsesOf(Unit u) { 47 List ret = (List) usesOf.get(u); 48 if( ret == null ) { 49 Local def = localDefed(u); 50 if( def == null ) { 51 usesOf.put(u, ret = Collections.EMPTY_LIST); 52 } else { 53 usesOf.put(u, ret = new ArrayList()); 54 for( Iterator vbIt = ((FlowSet)getFlowAfter(u)).iterator(); vbIt.hasNext(); ) { 55 final ValueBox vb = (ValueBox) vbIt.next(); 56 if( vb.getValue() != def ) continue; 57 ret.add(new UnitValueBoxPair((Unit)useBoxToUnit.get(vb), vb)); 58 } 59 } 60 } 61 return ret; 62 } 63 private Map liveLocalsBefore = new HashMap(); 64 public List getLiveLocalsBefore(Unit u) { 65 List ret = (List) liveLocalsBefore.get(u); 66 if( ret == null ) { 67 HashSet hs = new HashSet(); 68 for( Iterator vbIt = ((FlowSet)getFlowBefore(u)).iterator(); vbIt.hasNext(); ) { 69 final ValueBox vb = (ValueBox) vbIt.next(); 70 hs.add(vb.getValue()); 71 } 72 liveLocalsBefore.put(u, ret = new ArrayList(hs)); 73 } 74 return ret; 75 } 76 private Map liveLocalsAfter = new HashMap(); 77 public List getLiveLocalsAfter(Unit u) { 78 List ret = (List) liveLocalsAfter.get(u); 79 if( ret == null ) { 80 HashSet hs = new HashSet(); 81 for( Iterator vbIt = ((FlowSet)getFlowAfter(u)).iterator(); vbIt.hasNext(); ) { 82 final ValueBox vb = (ValueBox) vbIt.next(); 83 hs.add(vb.getValue()); 84 } 85 liveLocalsAfter.put(u, ret = new ArrayList(hs)); 86 } 87 return ret; 88 } 89 90 92 private final Map useBoxToUnit = new HashMap(); 93 private final Map unitToLocalDefed = new HashMap(); 94 private Local localDefed(Unit u) { return (Local) unitToLocalDefed.get(u); } 95 private final Map unitToLocalUseBoxes = new HashMap(); 96 private final MultiMap localToUseBoxes = new HashMultiMap(); 97 private final UnitGraph graph; 98 99 public static CombinedAnalysis v(final UnitGraph graph) { 100 if(true) { 101 return new CombinedDUAnalysis(graph); 102 } 103 104 return new CombinedAnalysis() { 105 CombinedDUAnalysis combined = new CombinedDUAnalysis(graph); 106 SimpleLocalDefs defs = new SimpleLocalDefs(graph); 107 SimpleLocalUses uses = new SimpleLocalUses(graph, defs); 108 SimpleLiveLocals live = new SimpleLiveLocals(graph); 109 public List getDefsOfAt(Local l, Unit s) { 110 HashSet hs1 = new HashSet(combined.getDefsOfAt(l, s)); 111 HashSet hs2 = new HashSet(defs.getDefsOfAt(l, s)); 112 if( !hs1.equals(hs2) ) throw new RuntimeException ( 113 "Defs of "+l+" in "+s+"\ncombined: "+hs1+"\nsimple: "+hs2); 114 return combined.getDefsOfAt(l, s); 115 } 116 public List getUsesOf(Unit u) { 117 HashSet hs1 = new HashSet(combined.getUsesOf(u)); 118 HashSet hs2 = new HashSet(uses.getUsesOf(u)); 119 if( !hs1.equals(hs2) ) throw new RuntimeException ( 120 "Uses of "+u+"\ncombined: "+hs1+"\nsimple: "+hs2); 121 return combined.getUsesOf(u); 122 } 123 public List getLiveLocalsBefore(Unit u) { 124 HashSet hs1 = new HashSet(combined.getLiveLocalsBefore(u)); 125 HashSet hs2 = new HashSet(live.getLiveLocalsBefore(u)); 126 if( !hs1.equals(hs2) ) throw new RuntimeException ( 127 "llb of "+u+"\ncombined: "+hs1+"\nsimple: "+hs2); 128 return combined.getLiveLocalsBefore(u); 129 } 130 public List getLiveLocalsAfter(Unit u) { 131 HashSet hs1 = new HashSet(combined.getLiveLocalsAfter(u)); 132 HashSet hs2 = new HashSet(live.getLiveLocalsAfter(u)); 133 if( !hs1.equals(hs2) ) throw new RuntimeException ( 134 "lla of "+u+"\ncombined: "+hs1+"\nsimple: "+hs2); 135 return combined.getLiveLocalsAfter(u); 136 } 137 } 138 ; 139 } 140 private CombinedDUAnalysis(UnitGraph graph) { 141 super(graph); 142 this.graph = graph; 143 144 if(Options.v().verbose()) 145 G.v().out.println("[" + graph.getBody().getMethod().getName() + 146 "] Constructing CombinedDUAnalysis..."); 147 148 for( Iterator uIt = graph.iterator(); uIt.hasNext(); ) { 149 150 final Unit u = (Unit) uIt.next(); 151 List defs = localsInBoxes(u.getDefBoxes()); 152 if( defs.size() == 1 ) unitToLocalDefed.put(u, defs.get(0)); 153 else if(defs.size() != 0) throw new RuntimeException ("Locals defed in "+u+": "+defs.size()); 154 ArraySparseSet localUseBoxes = new ArraySparseSet(); 155 for( Iterator vbIt = u.getUseBoxes().iterator(); vbIt.hasNext(); ) { 156 final ValueBox vb = (ValueBox) vbIt.next(); 157 Value v = vb.getValue(); 158 if(!(v instanceof Local)) continue; 159 localUseBoxes.add(vb); 160 if( useBoxToUnit.containsKey(vb) ) throw new RuntimeException ("Aliased ValueBox "+vb+" in Unit "+u); 161 useBoxToUnit.put(vb, u); 162 localToUseBoxes.put(v, vb); 163 } 164 unitToLocalUseBoxes.put(u, localUseBoxes); 165 } 166 167 doAnalysis(); 168 169 for( Iterator defUnitIt = graph.iterator(); defUnitIt.hasNext(); ) { 170 171 final Unit defUnit = (Unit) defUnitIt.next(); 172 177 Local localDefed = localDefed(defUnit); 178 if( localDefed == null ) continue; 179 for( Iterator vbIt = ((FlowSet)getFlowAfter(defUnit)).iterator(); vbIt.hasNext(); ) { 180 final ValueBox vb = (ValueBox) vbIt.next(); 181 if( vb.getValue() != localDefed ) continue; 182 Unit useUnit = (Unit) useBoxToUnit.get(vb); 183 getDefsOfAt(localDefed, useUnit).add(defUnit); 184 } 185 } 186 if(Options.v().verbose()) 187 G.v().out.println("[" + graph.getBody().getMethod().getName() + 188 "] Finished CombinedDUAnalysis..."); 189 190 } 191 private List localsInBoxes(List boxes) { 192 List ret = new ArrayList(); 193 for( Iterator vbIt = boxes.iterator(); vbIt.hasNext(); ) { 194 final ValueBox vb = (ValueBox) vbIt.next(); 195 Value v = vb.getValue(); 196 if( !(v instanceof Local) ) continue; 197 ret.add(v); 198 } 199 return ret; 200 } 201 202 203 protected void merge(Object inoutO, Object inO) { 216 FlowSet inout = (FlowSet) inoutO; 217 FlowSet in = (FlowSet) inO; 218 219 inout.union(in); 220 } 221 protected void merge(Object in1O, Object in2O, Object outO) { 222 FlowSet in1 = (FlowSet) in1O; 223 FlowSet in2 = (FlowSet) in2O; 224 FlowSet out = (FlowSet) outO; 225 226 in1.union(in2, out); 227 } 228 protected void flowThrough(Object outValue, Object unit, Object inValue) { 231 Unit u = (Unit) unit; 232 FlowSet in = (FlowSet) inValue; 233 FlowSet out = (FlowSet) outValue; 234 Local def = localDefed(u); 235 out.copy(in); 236 if(def != null) { 237 Collection boxesDefed = localToUseBoxes.get(def); 238 for( Iterator vbIt = in.toList().iterator(); vbIt.hasNext(); ) { 239 final ValueBox vb = (ValueBox) vbIt.next(); 240 if(boxesDefed.contains(vb)) in.remove(vb); 241 } 242 } 243 in.union((FlowSet) unitToLocalUseBoxes.get(u)); 244 } 245 246 protected Object entryInitialFlow() 252 { 253 return new ArraySparseSet(); 254 } 255 256 protected Object newInitialFlow() 257 { 258 return new ArraySparseSet(); 259 } 260 261 protected void copy(Object source, Object dest) { 262 FlowSet sourceSet = (FlowSet) source; 263 FlowSet destSet = (FlowSet) dest; 264 265 sourceSet.copy(destSet); 266 } 267 268 } 269 270 | Popular Tags |