1 30 31 package jbet; 32 import java.util.*; 33 import java.lang.reflect.*; 34 35 42 43 public class DagSnippit { 44 45 public static String JbetLogFacility = "dags"; 46 47 public Vector bbs; public DagMethodInfo method; public Node.param[] params; public int blflags; 52 Vector inbbs; 54 public BasicBlock blockAt (int i) { 55 return (BasicBlock) (bbs.elementAt (i)); 56 } 57 58 abstract public static class Modifier 59 { 60 abstract public void f (DagSnippit dags); 61 } 62 63 65 public DagSnippit () { } 66 67 73 public static DagSnippit graphify (MethodInfo mi) throws ClassFileException, DataFlowException, ElementNotFoundException { 74 return graphify(mi, ClassFilter.ALL); 75 } 76 77 84 85 public static DagSnippit graphify (MethodInfo mi, ClassFilter fixcons) 86 throws ClassFileException, DataFlowException, ElementNotFoundException { 87 return graphify (mi, fixcons, null, null); 88 } 89 90 public static DagSnippit graphify (MethodInfo mi, ClassFilter fixcons, DagSnippit inme, int [] permutation) 91 throws ClassFileException, DataFlowException, ElementNotFoundException { 92 93 final DagSnippit me = (inme==null) ? new DagSnippit() : inme; 94 95 Node.New.newcount = 0; 96 97 final Vector inbbs = (me.inbbs==null) ? InstrBlock.FindBasicBlocks (mi, null) : me.inbbs; 98 me.inbbs = inbbs; 99 100 if (inbbs == null) 101 return null; 102 Vector outbbs = new Vector(); 104 me.params = new Node.param 105 [ mi.descriptor.count()-1 + (mi.isStatic() ? 0 : 1) ]; 106 int param_lv = 0; 107 if (!mi.isStatic()) { 108 me.params[param_lv] = new Node.param(param_lv, new Type(mi.cr)); 109 param_lv++; 110 } 111 for (int i = 0; i < mi.descriptor.args.length; i++, param_lv++) { 112 me.params[param_lv] = new Node.param(param_lv, mi.descriptor.args[i]); 113 if (mi.descriptor.args[i].category() == 2) 114 param_lv++; 115 } 116 117 AliasDB currdb = null; 118 119 for (int i = 0; i < inbbs.size(); i++) { 121 IntFunction inserials; 122 int j; 123 if (permutation == null) { 124 currdb = new AliasDB(); 125 inserials = null; 126 j = i+1; 127 } else { 128 j = permutation[i]; 129 if (j < 0) { 130 currdb = new AliasDB(); 131 j = -j; 132 } 133 inserials = new IntFunction() { 134 public int f(int n) { 135 return (n==0) ? 1 : -1; 136 } 137 }; 138 } 139 InstrBlock ib = (InstrBlock) inbbs.elementAt (j-1); 140 if (ib.pse != null && ib.psx != null) { 141 BasicBlock newblock = me.bbs==null ? new BasicBlock() : me.blockAt(j-1); 142 newblock.model (ib, fixcons, inserials, currdb); 143 outbbs.addElement(newblock); 144 } 145 } 146 147 148 for (int i = 0; i < outbbs.size(); i++) { 149 BasicBlock sb = (BasicBlock) outbbs.elementAt (i); 150 InstrBlock in = (InstrBlock) inbbs.elementAt (i); 151 152 sb.es.op = in.es.op; 153 sb.es.stackuse = in.es.stackuse; 154 155 sb.es.primary = in.es.primary != null ? 156 (BasicBlock) outbbs.elementAt (in.es.primary.swval - 1) : null; 157 sb.es.jump = in.es.jump != null ? 158 (BasicBlock) outbbs.elementAt (in.es.jump.swval - 1) : null; 159 sb.es.ret = in.es.ret != null ? 160 (BasicBlock) outbbs.elementAt (in.es.ret.swval - 1) : null; 161 162 if (in.es.switches != null) { 163 BranchTarget[] switches = new BranchTarget [in.es.switches.length]; 164 sb.es.switches = switches; 165 sb.es.swofs = in.es.swofs; 166 167 for (int j = 0; j < switches.length; j++) 168 if (in.es.switches[j] != null) { 169 switches[j] = new BranchTarget(); 170 switches[j].key = in.es.switches[j].key; 171 switches[j].block = (BasicBlock) outbbs.elementAt (in.es.switches[j].block.swval-1); 172 } 173 } 174 175 if (in.es.exceptions != null) { 176 sb.es.exceptions = new Vector(); 177 178 for (int j = 0; j < in.es.exceptions.size(); j++) { 179 Block.ExcInfo eo = in.es.exAt (j); 180 Block.ExcInfo er = new Block.ExcInfo(); 181 182 er.handler = (BasicBlock) outbbs.elementAt (eo.handler.swval-1); 183 er.type = eo.type; 184 er.info = eo.info; 185 186 sb.es.exceptions.addElement (er); 187 } 188 } 189 } 191 Jbet.debug.println ("SUCCESSORS"); 192 193 final Vector [] pred = new Vector [ outbbs.size() ]; 194 for (int i = 0; i < pred.length; i++) 195 pred[i] = new Vector(); 196 for (int i = 0; i < outbbs.size(); i++) { 197 BasicBlock sb = (BasicBlock) outbbs.elementAt (i); 198 Jbet.debug.print(" #B" + sb.swval); 199 for (Enumeration e = sb.getSuccessors().elements(); 200 e.hasMoreElements();) { 201 BasicBlock succ = (BasicBlock) e.nextElement(); 202 Jbet.debug.print(" " + succ.swval); 203 pred[succ.swval-1].addElement(sb); 204 } 205 Jbet.debug.println(); 206 } 207 208 Jbet.debug.println(); 209 Jbet.debug.println ("PREDECESSORS"); 210 for (int i = 0; i < pred.length; i++) { 211 Vector v = pred[i]; 212 ((Block)outbbs.elementAt(i)).pred = pred[i]; 213 214 Jbet.debug.print (" #B" + (i+1)); 215 for (int j = 0; j < v.size(); j++) 216 Jbet.debug.print (" " + ((Block)v.elementAt (j)).swval); 217 Jbet.debug.println (); 218 } 219 Jbet.debug.println(); 220 221 222 final HashSet [] newouts = new HashSet [ outbbs.size() ]; 223 for (int i = 0; i < newouts.length; i++) 224 newouts[i] = new HashSet(); 225 final HashSet visited = new HashSet(); 226 227 228 class _util { 229 231 Node nontrivial; 232 int depth = 0; 233 234 void println(String s) { 235 for (int i = 0; i < depth; i++) Jbet.debug.print(" "); 236 Jbet.debug.println(s); 237 } 238 239 void in() { depth += 2; } 240 241 void out() {depth -= 2; } 242 243 void find_producers (Node.var var, BasicBlock sb) throws ClassFileException, ElementNotFoundException { 244 println ("FP: " + var + " #" + sb.swval); 245 in(); 246 try { 247 if (sb.swval == 1 && var.v < me.params.length && var.v >= 0){ 248 var.producers.add(me.params[var.v]); 249 println ("found " + me.params[var.v]); 250 } 251 if (sb.handler != null) { if (var.v == -1) { 253 var.exobject = true; 254 return; 255 } else if (var.v < 0) 256 throw new IllegalStateException ("bad stack for exception handler"); 257 } 258 for (Enumeration e = pred[sb.swval-1].elements(); 259 e.hasMoreElements();) { 260 fpHelper (var, (BasicBlock) e.nextElement()); 261 } 262 } finally { 263 out(); 264 } 265 } 266 267 void fpHelper (Node.var var, BasicBlock sb) throws ClassFileException, ElementNotFoundException { 269 println ("H: " + var + " " + sb.swval); 270 in(); 271 try { 272 if (visited.contains(sb)) { 273 println("cutoff"); 274 return; 275 } 276 visited.add(sb); 277 boolean good = false; 278 for (int i = 0; i < sb.outputs.length; i++) { 279 if (!(sb.outputs[i] instanceof Node.assign)) continue; 280 Node.assign assign = (Node.assign) sb.outputs[i]; 281 if (assign.lvt != var.v) continue; 282 var.producers.add( assign.val ); 283 println("found " + assign.val); 284 good = true; 285 break; 286 } 287 if (good) { 288 boolean bigbadexception = false; 289 if (sb.es.exceptions != null) { 290 for (Iterator i = sb.senodes.iterator(); 291 i.hasNext() && !bigbadexception ;) { 292 Node sen = (Node) i.next(); 293 MethodSignature ms1 = null; 294 if (sen instanceof Node.invokes) 295 ms1 = ((Node.invokes)sen).method; 296 if (sen instanceof Node.invokev) 297 ms1 = ((Node.invokev)sen).method; 298 if (ms1 == null) continue; 299 MethodInfo ms = ms1.resolveAny(); 300 301 for (int j = 0; j < ms.exceptions.size(); j++) { 302 String exstr = (String ) 303 ms.exceptions.elementAt(j); 304 for (int k = 0; k < sb.es.exceptions.size(); k++) { 305 Block.ExcInfo exinfo = (Block.ExcInfo) sb.es.exceptions.elementAt(k); 306 println("YAKYAK " + exinfo.type); 307 if (ClassInfo.isAncestor (exstr, exinfo.type)) 308 bigbadexception = true; 309 } 310 } 311 for (int k = 0; k < sb.es.exceptions.size(); k++) { 312 Block.ExcInfo exinfo = (Block.ExcInfo) sb.es.exceptions.elementAt(k); 313 if (ClassInfo.isAncestor (exinfo.type, "java/lang/RuntimeException") || 314 ClassInfo.isAncestor (exinfo.type, "java/lang/Error")) 315 bigbadexception = true; 316 } 317 } 318 } if (bigbadexception) { 320 println ("bad exceptoin thing!!!"); 321 find_producers (var, sb); 322 } else 323 return; 324 } 325 println ("notfound"); 326 find_producers (var, sb); 327 } finally { 328 out(); 329 } 330 } 331 332 Node uniqueProducer; 333 334 boolean setUniqueProducer(Node f) { 336 if (f == null) throw new IllegalStateException ("yak!"); 337 if (uniqueProducer != null && !uniqueProducer.equals(f)) { 338 println ("double uniqueProducer ! " + uniqueProducer + " " + f); 339 return false; 340 } else { 341 uniqueProducer = f; 342 println ("uniqueProducer set to " + uniqueProducer); 343 return true; 344 } 345 } 346 347 boolean trace (Node.var var) { 349 println("trace " + var); 350 in(); 351 try { 352 if (visited.contains(var)) { 353 println ("cutoff"); 354 return true; 355 } 356 visited.add(var); 357 for (Iterator i = var.producers.iterator(); i.hasNext();) { 358 Object o = i.next(); 359 if (o instanceof Node.var) { 360 if (!trace ((Node.var) o)) return false ; 361 } else { 362 println("setting to " + o); 363 if (!setUniqueProducer((Node) o)) return false; 364 } 365 } 366 return uniqueProducer != null; 367 } finally { out(); } 368 } 369 370 void link (Node from, Node.var to) { 372 println ("arrow " + from + " -> " + to); 373 from.addDestination(to); 374 to.producers.add(from); 375 if (from.sb != null) 376 newouts[from.sb.swval-1].add (from); 377 else if (!(from instanceof Node.param)) throw new 378 IllegalStateException ("a non-param node has no block: " + from); 379 } 380 381 void link (Node.var var) { 383 println("link " + var); 384 in(); 385 try { 386 uniqueProducer = null; 387 if ( trace (var) ) { 388 var.producers.clear(); 389 println ("linking " + uniqueProducer); 390 link (uniqueProducer, var); 391 println ("good trace " + uniqueProducer); 392 } else 393 for (Iterator i = var.producers.iterator(); 394 i.hasNext();) 395 link ((Node) i.next(), var); 396 } finally { out(); } 397 } 398 399 420 } _util util = new _util(); 422 423 for (int i = 0; i < outbbs.size(); i++) { 425 util.println("FP ==================== " + (i+1)); 426 util.in(); 427 BasicBlock sb = (BasicBlock) outbbs.elementAt (i); 428 for (int j = 0; j < sb.inputs.length; j++) 429 if (sb.inputs[j] instanceof Node.var) { 430 visited.clear(); 431 util.find_producers((Node.var) sb.inputs[j], sb); 432 } 433 util.out(); 434 } 435 436 for (int i = 0; i < outbbs.size(); i++) { 438 util.println("LINK ==================== " + (i+1)); 439 util.in(); 440 final BasicBlock sb = (BasicBlock) outbbs.elementAt (i); 441 for (int j = 0; j < sb.inputs.length; j++) { 442 final int jj = j; 443 if (sb.inputs[j] instanceof Node.var) { 444 visited.clear(); 445 util.link((Node.var) sb.inputs[j]); 446 } 447 if (false) 448 for (int k = 0; k < j; k++) { 449 final int kk = k; 450 if (sb.inputs[k].producers.equals(sb.inputs[j].producers)){ 451 util.println("double " + sb.inputs[jj] + " " + 452 sb.inputs[kk]); 453 459 } 460 } 461 462 } 463 util.out(); 464 } 466 467 468 473 474 for (int i = 0; i < outbbs.size(); i++) { 475 BasicBlock sb = (BasicBlock) outbbs.elementAt (i); 476 for (int j = 0; j < sb.outputs.length; j++) 477 if (!(sb.outputs[j] instanceof Node.assign)) 478 newouts[sb.swval-1].add (sb.outputs[j]); 479 sb.outputs = (Node[]) newouts[sb.swval-1].toArray (new Node[0]); 480 } 481 482 for (int i = 0; i < outbbs.size(); i++) { 483 BasicBlock sb = (BasicBlock) outbbs.elementAt(i); 484 Collection nodes = sb.findnodes(); 485 for (Iterator j = nodes.iterator(); j.hasNext();) { 486 Node n = (Node) j.next(); 487 if (n.destinations == null) continue; 488 for (Iterator k = n.destinations.iterator(); k.hasNext();) { 489 Node.var dest = (Node.var) k.next(); 490 if (dest.sb == sb) 491 n.requires.addElement(dest); 492 } 493 } 494 } 495 496 me.bbs = outbbs; 497 498 500 return me; 501 } 503 504 507 public void printinfo(LineWriter out) { 508 for (int i = 0; i < params.length; i++) { 509 if (params[i] == null) continue; 510 out.print("param " + params[i] + " " + params[i].type()); 511 if (params[i].destinations == null) { out.println(); continue; } 512 out.print(" -> "); 513 for (Iterator j = params[i].destinations.iterator(); j.hasNext();) 514 out.print( j.next() + " "); 515 out.println(); 516 } 517 518 out.println(); 519 for (int i = 0; i < bbs.size(); i++) 520 ((Block) bbs.elementAt (i)).printinfo (out, true); 521 522 out.println (); 523 } 524 525 528 void disableblock (BasicBlock db) { 529 db.blflags |= Block.Blc_disabled; 530 531 for (int i = 0; i < bbs.size(); i++) { 532 BasicBlock sb = (BasicBlock) bbs.elementAt (i); 533 534 for (int j = 0; j < sb.inputs.length; j++) { 535 Node.var var = (Node.var) sb.inputs[j]; 536 537 loop: for (int k = 0; k < db.outputs.length; k++) { 538 if (var.producers.contains (db.outputs[k])) { 539 Jbet.warn.println ("" + var + " has dead producer " + db.outputs[k]); 540 var.producers.remove (db.outputs[k]); 541 continue loop; 542 } else { 543 for (Iterator l = var.producers.iterator(); l.hasNext(); ) { 544 Object o = l.next(); 545 if (o.equals (db.outputs[k])) { 546 Jbet.warn.println ("" + var + " has dead producer " + db.outputs[k]); 547 var.producers.remove (o); 548 continue loop; 549 } 550 } } 552 } } } } 557 561 public void replace (Hashtable subs, Node.SubMethod sm) throws Throwable 562 { 563 for (int i = 0; i < bbs.size(); i++) 564 blockAt (i).replace (subs, sm); 565 } 566 567 public void replace_cfe (Hashtable subs, Node.SubMethod sm) throws ClassFileException 568 { 569 try { 570 for (int i = 0; i < bbs.size(); i++) 571 blockAt (i).replace (subs, sm); 572 } 573 catch (ClassFileException e) { throw e; } 574 catch (Throwable e) { e.printStackTrace (Jbet.error); throw new IllegalStateException (e.toString ()); } 575 } 576 577 580 public void findLabels () 581 { 582 Vector newbbs = new Vector(); 583 584 for (int i = 0; i < bbs.size(); i++) { 585 BasicBlock sb = (BasicBlock) bbs.elementAt (i); 586 587 if (sb.es.op == Instruction.AOP_LABEL) 588 continue; 589 590 newbbs.addElement (sb); 591 592 Collection nodes = sb.findnodes(); 593 for (Iterator j = nodes.iterator(); j.hasNext(); ) { 594 Object o = j.next(); 595 596 if (o instanceof Node.Label) 597 newbbs.addElement (new BasicBlock ((Node.Label) o)); 598 } 599 } 600 601 bbs = newbbs; 602 BasicBlock.renumber (bbs); 603 } 605 607 public void clearTmps() { 608 for (int i = 0; i < bbs.size(); i++) { 609 BasicBlock sb = blockAt (i); 610 Collection nodes = sb.findnodes (); 611 612 for (Iterator j = nodes.iterator(); j.hasNext(); ) 613 ((Node)j.next()).clocal = -1; 614 } 615 } 616 617 619 public void findRoles() { 620 for (int i = 0; i < bbs.size(); i++) { 621 BasicBlock sb = blockAt (i); 622 623 switch (sb.es.op) { 624 case 0: 625 if (sb.es.primary.pred.size() == 1) 626 sb.es.role = Block.Erol_Single; 627 break; 628 629 case Instruction.OP_RETURN: 630 case Instruction.OP_IRETURN: 631 case Instruction.OP_LRETURN: 632 case Instruction.OP_ARETURN: 633 case Instruction.OP_FRETURN: 634 case Instruction.OP_DRETURN: 635 sb.es.role = Block.Erol_Special; 636 break; 637 638 case Instruction.OP_IFNULL: 639 case Instruction.OP_IFNONNULL: 640 case Instruction.OP_IFEQ: 641 case Instruction.OP_IFNE: 642 case Instruction.OP_IFLE: 643 case Instruction.OP_IFLT: 644 case Instruction.OP_IFGT: 645 case Instruction.OP_IFGE: 646 case Instruction.OP_IF_ACMPEQ: 647 case Instruction.OP_IF_ACMPNE: 648 case Instruction.OP_IF_ICMPEQ: 649 case Instruction.OP_IF_ICMPNE: 650 case Instruction.OP_IF_ICMPLE: 651 case Instruction.OP_IF_ICMPLT: 652 case Instruction.OP_IF_ICMPGT: 653 case Instruction.OP_IF_ICMPGE: 654 if (sb.es.primary.alwaysIfLeadsTo (sb) || 655 sb.es.jump.alwaysIfLeadsTo (sb)) 656 sb.es.role = Block.Erol_LoopCond; 657 else 658 sb.es.role = Block.Erol_Cond; 659 672 break; 673 674 case Instruction.OP_TABLESWITCH: 675 case Instruction.OP_LOOKUPSWITCH: 676 sb.es.role = Block.Erol_Switch; 677 break; 678 } 679 } 680 } 682 } 683 | Popular Tags |