1 19 20 27 28 package soot.jimple.toolkits.annotation.purity; 29 import java.util.*; 30 import java.io.*; 31 import soot.*; 32 import soot.util.*; 33 import soot.util.dot.*; 34 import soot.jimple.*; 35 import soot.jimple.toolkits.callgraph.*; 36 import soot.toolkits.graph.*; 37 38 70 public abstract class AbstractInterproceduralAnalysis { 71 72 public static final boolean doCheck = false; 73 74 protected CallGraph cg; protected DirectedGraph dg; protected Map data; protected Map order; protected Map unanalysed; 80 81 82 protected abstract Object newInitialSummary(); 83 84 92 protected abstract Object summaryOfUnanalysedMethod(SootMethod method); 93 94 102 protected abstract void analyseMethod(SootMethod method, 103 Object dst); 104 105 117 protected abstract void applySummary(Object src, 118 Stmt callStmt, 119 Object summary, 120 Object dst); 121 122 127 protected abstract void merge(Object in1, Object in2, Object out); 128 129 130 protected abstract void copy(Object sr, Object dst); 131 132 139 protected void fillDotGraph(String prefix, Object o, DotGraph out) 140 { throw new Error ("abstract function AbstractInterproceduralAnalysis.fillDotGraph called but not implemented."); } 141 142 143 152 protected void analyseCall(Object src, 153 Stmt callStmt, 154 Object dst) 155 { 156 Object accum = newInitialSummary(); 157 Iterator it = cg.edgesOutOf(callStmt); 158 copy(accum, dst); 159 while (it.hasNext()) { 160 Edge edge = (Edge)it.next(); 161 SootMethod m = edge.tgt(); 162 Object elem; 163 if (data.containsKey(m)) { 164 elem = data.get(m); 166 } 167 else { 168 if (!unanalysed.containsKey(m)) 170 unanalysed.put(m, summaryOfUnanalysedMethod(m)); 171 elem = unanalysed.get(m); 172 } 173 applySummary(src, callStmt, elem, accum); 174 merge(dst, accum, dst); 175 } 176 } 177 178 179 183 public AbstractInterproceduralAnalysis(CallGraph cg, 184 SootMethodFilter filter, 185 Iterator heads, 186 boolean verbose) 187 { 188 this.cg = cg; 189 this.dg = new DirectedCallGraph(cg, filter, heads, verbose); 190 this.data = new HashMap(); 191 this.unanalysed = new HashMap(); 192 193 this.order = new HashMap(); 195 PseudoTopologicalOrderer o = new ReversePseudoTopologicalOrderer(); 196 Iterator it = (o.newList(dg)).iterator(); 197 int i = 0; 198 while (it.hasNext()) { 199 this.order.put(it.next(), new Integer (i)); 200 i++; 201 } 202 } 203 204 215 public void drawAsOneDot(String name) 216 { 217 DotGraph dot = new DotGraph(name); 218 dot.setGraphLabel(name); 219 dot.setGraphAttribute("compound","true"); 220 int id = 0; 222 Map idmap = new HashMap(); 223 224 Iterator it = dg.iterator(); 226 while (it.hasNext()) { 227 SootMethod m = (SootMethod)it.next(); 228 DotGraph sub = dot.createSubGraph("cluster"+id); 229 DotGraphNode label = sub.drawNode("head"+id); 230 idmap.put(m, new Integer (id)); 231 sub.setGraphLabel(""); 232 label.setLabel("("+order.get(m)+") "+m.toString()); 233 label.setAttribute("fontsize","18"); 234 label.setShape("box"); 235 if (data.containsKey(m)) 236 fillDotGraph("X"+id, data.get(m), sub); 237 id++; 238 } 239 240 it = dg.iterator(); 242 while (it.hasNext()) { 243 SootMethod m = (SootMethod)it.next(); 244 Iterator itt = dg.getSuccsOf(m).iterator(); 245 while (itt.hasNext()) { 246 SootMethod mm = (SootMethod)itt.next(); 247 DotGraphEdge edge = dot.drawEdge("head"+idmap.get(m), 248 "head"+idmap.get(mm)); 249 edge.setAttribute("ltail","cluster"+idmap.get(m)); 250 edge.setAttribute("lhead","cluster"+idmap.get(mm)); 251 } 252 253 } 254 255 256 File f = new File (SourceLocator.v().getOutputDir(), 257 name+DotGraph.DOT_EXTENSION); 258 dot.plot(f.getPath()); 259 } 260 261 271 public void drawAsManyDot(String prefix, boolean drawUnanalysed) 272 { 273 Iterator it = data.keySet().iterator(); 274 while (it.hasNext()) { 275 SootMethod m = (SootMethod)it.next(); 276 DotGraph dot = new DotGraph(m.toString()); 277 dot.setGraphLabel(m.toString()); 278 fillDotGraph("X", data.get(m), dot); 279 File f = new File (SourceLocator.v().getOutputDir(), 280 prefix+m.toString()+DotGraph.DOT_EXTENSION); 281 dot.plot(f.getPath()); 282 } 283 284 if (drawUnanalysed) { 285 it = unanalysed.keySet().iterator(); 286 while (it.hasNext()) { 287 SootMethod m = (SootMethod)it.next(); 288 DotGraph dot = new DotGraph(m.toString()); 289 dot.setGraphLabel(m.toString()+" (unanalysed)"); 290 fillDotGraph("X", unanalysed.get(m), dot); 291 File f = new File (SourceLocator.v().getOutputDir(), 292 prefix+m.toString()+"_u"+ 293 DotGraph.DOT_EXTENSION); 294 dot.plot(f.getPath()); 295 } 296 } 297 } 298 299 302 public Object getSummaryFor(SootMethod m) 303 { 304 if (data.containsKey(m)) return data.get(m); 305 if (unanalysed.containsKey(m)) return unanalysed.get(m); 306 return newInitialSummary(); 307 } 308 309 313 public Iterator getAnalysedMethods() 314 { return data.keySet().iterator(); } 315 316 323 protected void doAnalysis(boolean verbose) 324 { 325 class IntComparator implements Comparator { 327 public int compare(Object o1, Object o2) 328 { 329 Integer v1 = (Integer )order.get(o1); 330 Integer v2 = (Integer )order.get(o2); 331 return v1.intValue()-v2.intValue(); 332 } 333 public boolean equals(Object o1, Object o2) 334 { 335 Integer v1 = (Integer )order.get(o1); 336 Integer v2 = (Integer )order.get(o2); 337 return v1.intValue()==v2.intValue(); 338 } 339 }; 340 SortedSet queue = new TreeSet(new IntComparator()); 341 342 Iterator it = order.keySet().iterator(); 344 while (it.hasNext()) { 345 Object o = it.next(); 346 data.put(o, newInitialSummary()); 347 queue.add(o); 348 } 349 350 Map nb = new HashMap(); 352 while (!queue.isEmpty()) { 354 SootMethod m = (SootMethod)queue.first(); 355 queue.remove(m); 356 Object newSummary = newInitialSummary(); 357 Object oldSummary = data.get(m); 358 359 if (nb.containsKey(m)) nb.put(m,new Integer (((Integer )nb.get(m)).intValue()+1)); 360 else nb.put(m,new Integer (1)); 361 if (verbose) 362 G.v().out.println(" |- processing "+m.toString()+" ("+nb.get(m)+"-st time)"); 363 364 analyseMethod(m,newSummary); 365 if (!oldSummary.equals(newSummary)) { 366 data.put(m,newSummary); 368 queue.addAll(dg.getPredsOf(m)); 369 } 370 } 371 372 if (doCheck) { 374 it = order.keySet().iterator(); 375 while (it.hasNext()) { 376 SootMethod m = (SootMethod)it.next(); 377 Object newSummary = newInitialSummary(); 378 Object oldSummary = data.get(m); 379 analyseMethod(m,newSummary); 380 if (!oldSummary.equals(newSummary)) { 381 G.v().out.println("inter-procedural fixpoint not reached for method "+m.toString()); 382 DotGraph gm = new DotGraph("false_fixpoint"); 383 DotGraph gmm = new DotGraph("next_iterate"); 384 gm.setGraphLabel("false fixpoint: "+m.toString()); 385 gmm.setGraphLabel("fixpoint next iterate: "+m.toString()); 386 fillDotGraph("", oldSummary, gm); 387 fillDotGraph("", newSummary, gmm); 388 gm.plot(m.toString()+"_false_fixpoint.dot"); 389 gmm.plot(m.toString()+"_false_fixpoint_next.dot"); 390 throw new Error ("AbstractInterproceduralAnalysis sanity check failed!!!"); 391 } 392 } 393 } 394 395 } 396 } 397 398 | Popular Tags |