1 /* 2 * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 package sun.jvm.hotspot.oops; 26 27 import java.io.*; 28 import java.util.*; 29 import sun.jvm.hotspot.interpreter.*; 30 import sun.jvm.hotspot.runtime.*; 31 import sun.jvm.hotspot.utilities.*; 32 33 /** Minimal port of the VM's oop map generator for interpreted frames */ 34 35 public class GenerateOopMap { 36 interface JumpClosure { process(GenerateOopMap c, int bcpDelta, int[] data)37 public void process(GenerateOopMap c, int bcpDelta, int[] data); 38 } 39 40 // Used for debugging this code 41 private static final boolean DEBUG = false; 42 43 // These two should be removed. But requires som code to be cleaned up 44 private static final int MAXARGSIZE = 256; // This should be enough 45 private static final int MAX_LOCAL_VARS = 65536; // 16-bit entry 46 private static final boolean TraceMonitorMismatch = true; 47 private static final boolean TraceOopMapRewrites = true; 48 49 // Commonly used constants 50 static CellTypeState[] epsilonCTS = { CellTypeState.bottom }; 51 static CellTypeState refCTS = CellTypeState.ref; 52 static CellTypeState valCTS = CellTypeState.value; 53 static CellTypeState[] vCTS = { CellTypeState.value, CellTypeState.bottom }; 54 static CellTypeState[] rCTS = { CellTypeState.ref, CellTypeState.bottom }; 55 static CellTypeState[] rrCTS = { CellTypeState.ref, CellTypeState.ref, CellTypeState.bottom }; 56 static CellTypeState[] vrCTS = { CellTypeState.value, CellTypeState.ref, CellTypeState.bottom }; 57 static CellTypeState[] vvCTS = { CellTypeState.value, CellTypeState.value, CellTypeState.bottom }; 58 static CellTypeState[] rvrCTS = { CellTypeState.ref, CellTypeState.value, CellTypeState.ref, CellTypeState.bottom }; 59 static CellTypeState[] vvrCTS = { CellTypeState.value, CellTypeState.value, CellTypeState.ref, CellTypeState.bottom }; 60 static CellTypeState[] vvvCTS = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.bottom }; 61 static CellTypeState[] vvvrCTS = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.ref, CellTypeState.bottom }; 62 static CellTypeState[] vvvvCTS = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.bottom }; 63 64 /** Specialization of SignatureIterator - compute the effects of a call */ 65 static class ComputeCallStack extends SignatureIterator { 66 CellTypeStateList _effect; 67 int _idx; 68 set(CellTypeState state)69 void set(CellTypeState state) { _effect.get(_idx++).set(state); } length()70 int length() { return _idx; }; 71 doBool()72 public void doBool () { set(CellTypeState.value); } doChar()73 public void doChar () { set(CellTypeState.value); } doFloat()74 public void doFloat () { set(CellTypeState.value); } doByte()75 public void doByte () { set(CellTypeState.value); } doShort()76 public void doShort () { set(CellTypeState.value); } doInt()77 public void doInt () { set(CellTypeState.value); } doVoid()78 public void doVoid () { set(CellTypeState.bottom);} doObject(int begin, int end)79 public void doObject(int begin, int end) { set(CellTypeState.ref); } doArray(int begin, int end)80 public void doArray (int begin, int end) { set(CellTypeState.ref); } 81 doDouble()82 public void doDouble() { set(CellTypeState.value); 83 set(CellTypeState.value); } doLong()84 public void doLong () { set(CellTypeState.value); 85 set(CellTypeState.value); } 86 ComputeCallStack(Symbol signature)87 ComputeCallStack(Symbol signature) { 88 super(signature); 89 } 90 91 // Compute methods computeForParameters(boolean is_static, CellTypeStateList effect)92 int computeForParameters(boolean is_static, CellTypeStateList effect) { 93 _idx = 0; 94 _effect = effect; 95 96 if (!is_static) { 97 effect.get(_idx++).set(CellTypeState.ref); 98 } 99 100 iterateParameters(); 101 102 return length(); 103 }; 104 computeForReturntype(CellTypeStateList effect)105 int computeForReturntype(CellTypeStateList effect) { 106 _idx = 0; 107 _effect = effect; 108 iterateReturntype(); 109 set(CellTypeState.bottom); // Always terminate with a bottom state, so ppush works 110 111 return length(); 112 } 113 } 114 115 /** Specialization of SignatureIterator - in order to set up first stack frame */ 116 static class ComputeEntryStack extends SignatureIterator { 117 CellTypeStateList _effect; 118 int _idx; 119 set(CellTypeState state)120 void set(CellTypeState state) { _effect.get(_idx++).set(state); } length()121 int length() { return _idx; }; 122 doBool()123 public void doBool () { set(CellTypeState.value); } doChar()124 public void doChar () { set(CellTypeState.value); } doFloat()125 public void doFloat () { set(CellTypeState.value); } doByte()126 public void doByte () { set(CellTypeState.value); } doShort()127 public void doShort () { set(CellTypeState.value); } doInt()128 public void doInt () { set(CellTypeState.value); } doVoid()129 public void doVoid () { set(CellTypeState.bottom);} doObject(int begin, int end)130 public void doObject(int begin, int end) { set(CellTypeState.makeSlotRef(_idx)); } doArray(int begin, int end)131 public void doArray (int begin, int end) { set(CellTypeState.makeSlotRef(_idx)); } 132 doDouble()133 public void doDouble() { set(CellTypeState.value); 134 set(CellTypeState.value); } doLong()135 public void doLong () { set(CellTypeState.value); 136 set(CellTypeState.value); } 137 ComputeEntryStack(Symbol signature)138 ComputeEntryStack(Symbol signature) { 139 super(signature); 140 } 141 142 // Compute methods computeForParameters(boolean is_static, CellTypeStateList effect)143 int computeForParameters(boolean is_static, CellTypeStateList effect) { 144 _idx = 0; 145 _effect = effect; 146 147 if (!is_static) { 148 effect.get(_idx++).set(CellTypeState.makeSlotRef(0)); 149 } 150 151 iterateParameters(); 152 153 return length(); 154 }; 155 computeForReturntype(CellTypeStateList effect)156 int computeForReturntype(CellTypeStateList effect) { 157 _idx = 0; 158 _effect = effect; 159 iterateReturntype(); 160 set(CellTypeState.bottom); // Always terminate with a bottom state, so ppush works 161 162 return length(); 163 } 164 } 165 166 /** Contains maping between jsr targets and there return addresses. 167 One-to-many mapping. */ 168 static class RetTableEntry { 169 private static int _init_nof_jsrs; // Default size of jsrs list 170 private int _target_bci; // Target PC address of jump (bytecode index) 171 private List/*<int>*/ _jsrs; // List of return addresses (bytecode index) 172 private RetTableEntry _next; // Link to next entry 173 RetTableEntry(int target, RetTableEntry next)174 RetTableEntry(int target, RetTableEntry next) { 175 _target_bci = target; 176 _jsrs = new ArrayList(_init_nof_jsrs); 177 _next = next; 178 } 179 180 // Query targetBci()181 int targetBci() { return _target_bci; } nofJsrs()182 int nofJsrs() { return _jsrs.size(); } jsrs(int i)183 int jsrs(int i) { return ((Integer) _jsrs.get(i)).intValue(); } 184 185 // Update entry addJsr(int return_bci)186 void addJsr (int return_bci) { _jsrs.add(new Integer(return_bci)); } addDelta(int bci, int delta)187 void addDelta(int bci, int delta) { 188 if (_target_bci > bci) { 189 _target_bci += delta; 190 } 191 192 for (int k = 0; k < nofJsrs(); k++) { 193 int jsr = jsrs(k); 194 if (jsr > bci) { 195 _jsrs.set(k, new Integer(jsr+delta)); 196 } 197 } 198 } next()199 RetTableEntry next() { return _next; } 200 } 201 202 static class RetTable { 203 private RetTableEntry _first; 204 private static int _init_nof_entries; 205 addJsr(int return_bci, int target_bci)206 private void addJsr(int return_bci, int target_bci) { 207 RetTableEntry entry = _first; 208 209 // Scan table for entry 210 for (;(entry != null) && (entry.targetBci() != target_bci); entry = entry.next()); 211 212 if (entry == null) { 213 // Allocate new entry and put in list 214 entry = new RetTableEntry(target_bci, _first); 215 _first = entry; 216 } 217 218 // Now "entry" is set. Make sure that the entry is initialized 219 // and has room for the new jsr. 220 entry.addJsr(return_bci); 221 } 222 RetTable()223 RetTable() {} computeRetTable(Method method)224 void computeRetTable(Method method) { 225 BytecodeStream i = new BytecodeStream(method); 226 int bytecode; 227 228 while( (bytecode = i.next()) >= 0) { 229 switch (bytecode) { 230 case Bytecodes._jsr: 231 addJsr(i.nextBCI(), i.dest()); 232 break; 233 case Bytecodes._jsr_w: 234 addJsr(i.nextBCI(), i.dest_w()); 235 break; 236 } 237 } 238 } updateRetTable(int bci, int delta)239 void updateRetTable(int bci, int delta) { 240 RetTableEntry cur = _first; 241 while(cur != null) { 242 cur.addDelta(bci, delta); 243 cur = cur.next(); 244 } 245 } findJsrsForTarget(int targBci)246 RetTableEntry findJsrsForTarget(int targBci) { 247 RetTableEntry cur = _first; 248 249 while(cur != null) { 250 if (Assert.ASSERTS_ENABLED) { 251 Assert.that(cur.targetBci() != -1, "sanity check"); 252 } 253 if (cur.targetBci() == targBci) { 254 return cur; 255 } 256 cur = cur.next(); 257 } 258 throw new RuntimeException("Should not reach here"); 259 } 260 } 261 262 static class BasicBlock { 263 private boolean _changed; // Reached a fixpoint or not 264 static final int _dead_basic_block = -2; 265 // Alive but not yet reached by analysis 266 static final int _unreached = -1; 267 // >=0: Alive and has a merged state 268 269 int _bci; // Start of basic block 270 int _end_bci; // Bci of last instruction in basicblock 271 int _max_locals; // Determines split between vars and stack 272 int _max_stack; // Determines split between stack and monitors 273 CellTypeStateList _state; // State (vars, stack) at entry. 274 int _stack_top; // -1 indicates bottom stack value. 275 int _monitor_top; // -1 indicates bottom monitor stack value. 276 vars()277 CellTypeStateList vars() { return _state; } stack()278 CellTypeStateList stack() { return _state.subList(_max_locals, _state.size()); } 279 changed()280 boolean changed() { return _changed; } setChanged(boolean s)281 void setChanged(boolean s) { _changed = s; } 282 283 // Analysis has reached this basicblock isReachable()284 boolean isReachable() { return _stack_top >= 0; } 285 286 // All basicblocks that are unreachable are going to have a _stack_top == _dead_basic_block. 287 // This info. is setup in a pre-parse before the real abstract interpretation starts. isDead()288 boolean isDead() { return _stack_top == _dead_basic_block; } isAlive()289 boolean isAlive() { return _stack_top != _dead_basic_block; } markAsAlive()290 void markAsAlive() { 291 if (Assert.ASSERTS_ENABLED) { 292 Assert.that(isDead(), "must be dead"); 293 _stack_top = _unreached; 294 } 295 } 296 } 297 298 //---------------------------------------------------------------------- 299 // Protected routines for GenerateOopMap 300 // 301 302 // _monitor_top is set to this constant to indicate that a monitor matching 303 // problem was encountered prior to this point in control flow. 304 protected static final int bad_monitors = -1; 305 306 // Main variables 307 Method _method; // The method we are examining 308 RetTable _rt; // Contains the return address mappings 309 int _max_locals; // Cached value of no. of locals 310 int _max_stack; // Cached value of max. stack depth 311 int _max_monitors; // Cached value of max. monitor stack depth 312 boolean _has_exceptions; // True, if exceptions exist for method 313 boolean _got_error; // True, if an error occured during interpretation. 314 String _error_msg; // Error message. Set if _got_error is true. 315 // bool _did_rewriting; // was bytecodes rewritten 316 // bool _did_relocation; // was relocation neccessary 317 boolean _monitor_safe; // The monitors in this method have been determined 318 // to be safe. 319 320 // Working Cell type state 321 int _state_len; // Size of states 322 CellTypeStateList _state; // list of states 323 char[] _state_vec_buf; // Buffer used to print a readable version of a state 324 int _stack_top; 325 int _monitor_top; 326 327 // Timing and statistics 328 // static elapsedTimer _total_oopmap_time; // Holds cumulative oopmap generation time 329 // static long _total_byte_count; // Holds cumulative number of bytes inspected 330 331 // Monitor query logic 332 int _report_for_exit_bci; 333 int _matching_enter_bci; 334 335 // Cell type methods initState()336 void initState() { 337 _state_len = _max_locals + _max_stack + _max_monitors; 338 _state = new CellTypeStateList(_state_len); 339 _state_vec_buf = new char[Math.max(_max_locals, Math.max(_max_stack, Math.max(_max_monitors, 1)))]; 340 } makeContextUninitialized()341 void makeContextUninitialized () { 342 CellTypeStateList vs = vars(); 343 344 for (int i = 0; i < _max_locals; i++) 345 vs.get(i).set(CellTypeState.uninit); 346 347 _stack_top = 0; 348 _monitor_top = 0; 349 } 350 methodsigToEffect(Symbol signature, boolean isStatic, CellTypeStateList effect)351 int methodsigToEffect (Symbol signature, boolean isStatic, CellTypeStateList effect) { 352 ComputeEntryStack ces = new ComputeEntryStack(signature); 353 return ces.computeForParameters(isStatic, effect); 354 } 355 mergeStateVectors(CellTypeStateList cts, CellTypeStateList bbts)356 boolean mergeStateVectors (CellTypeStateList cts, CellTypeStateList bbts) { 357 int i; 358 int len = _max_locals + _stack_top; 359 boolean change = false; 360 361 for (i = len - 1; i >= 0; i--) { 362 CellTypeState v = cts.get(i).merge(bbts.get(i), i); 363 change = change || !v.equal(bbts.get(i)); 364 bbts.get(i).set(v); 365 } 366 367 if (_max_monitors > 0 && _monitor_top != bad_monitors) { 368 // If there are no monitors in the program, or there has been 369 // a monitor matching error before this point in the program, 370 // then we do not merge in the monitor state. 371 372 int base = _max_locals + _max_stack; 373 len = base + _monitor_top; 374 for (i = len - 1; i >= base; i--) { 375 CellTypeState v = cts.get(i).merge(bbts.get(i), i); 376 377 // Can we prove that, when there has been a change, it will already 378 // have been detected at this point? That would make this equal 379 // check here unnecessary. 380 change = change || !v.equal(bbts.get(i)); 381 bbts.get(i).set(v); 382 } 383 } 384 385 return change; 386 } 387 copyState(CellTypeStateList dst, CellTypeStateList src)388 void copyState (CellTypeStateList dst, CellTypeStateList src) { 389 int len = _max_locals + _stack_top; 390 for (int i = 0; i < len; i++) { 391 if (src.get(i).isNonlockReference()) { 392 dst.get(i).set(CellTypeState.makeSlotRef(i)); 393 } else { 394 dst.get(i).set(src.get(i)); 395 } 396 } 397 if (_max_monitors > 0 && _monitor_top != bad_monitors) { 398 int base = _max_locals + _max_stack; 399 len = base + _monitor_top; 400 for (int i = base; i < len; i++) { 401 dst.get(i).set(src.get(i)); 402 } 403 } 404 } 405 mergeStateIntoBB(BasicBlock bb)406 void mergeStateIntoBB (BasicBlock bb) { 407 if (Assert.ASSERTS_ENABLED) { 408 Assert.that(bb.isAlive(), "merging state into a dead basicblock"); 409 } 410 411 if (_stack_top == bb._stack_top) { 412 if (_monitor_top == bb._monitor_top) { 413 if (mergeStateVectors(_state, bb._state)) { 414 bb.setChanged(true); 415 } 416 } else { 417 if (TraceMonitorMismatch) { 418 reportMonitorMismatch("monitor stack height merge conflict"); 419 } 420 // When the monitor stacks are not matched, we set _monitor_top to 421 // bad_monitors. This signals that, from here on, the monitor stack cannot 422 // be trusted. In particular, monitorexit bytecodes may throw 423 // exceptions. We mark this block as changed so that the change 424 // propagates properly. 425 bb._monitor_top = bad_monitors; 426 bb.setChanged(true); 427 _monitor_safe = false; 428 } 429 } else if (!bb.isReachable()) { 430 // First time we look at this BB 431 copyState(bb._state, _state); 432 bb._stack_top = _stack_top; 433 bb._monitor_top = _monitor_top; 434 bb.setChanged(true); 435 } else { 436 throw new RuntimeException("stack height conflict: " + 437 _stack_top + " vs. " + bb._stack_top); 438 } 439 } 440 mergeState(int bci, int[] data)441 void mergeState (int bci, int[] data) { 442 mergeStateIntoBB(getBasicBlockAt(bci)); 443 } 444 setVar(int localNo, CellTypeState cts)445 void setVar (int localNo, CellTypeState cts) { 446 if (Assert.ASSERTS_ENABLED) { 447 Assert.that(cts.isReference() || cts.isValue() || cts.isAddress(), 448 "wrong celltypestate"); 449 } 450 if (localNo < 0 || localNo > _max_locals) { 451 throw new RuntimeException("variable write error: r" + localNo); 452 } 453 vars().get(localNo).set(cts); 454 } 455 getVar(int localNo)456 CellTypeState getVar (int localNo) { 457 if (Assert.ASSERTS_ENABLED) { 458 Assert.that(localNo < _max_locals + _nof_refval_conflicts, "variable read error"); 459 } 460 if (localNo < 0 || localNo > _max_locals) { 461 throw new RuntimeException("variable read error: r" + localNo); 462 } 463 return vars().get(localNo).copy(); 464 } 465 466 CellTypeState pop () { 467 if ( _stack_top <= 0) { 468 throw new RuntimeException("stack underflow"); 469 } 470 return stack().get(--_stack_top).copy(); 471 } 472 473 void push (CellTypeState cts) { 474 if ( _stack_top >= _max_stack) { 475 if (DEBUG) { 476 System.err.println("Method: " + method().getName().asString() + method().getSignature().asString() + 477 " _stack_top: " + _stack_top + " _max_stack: " + _max_stack); 478 } 479 throw new RuntimeException("stack overflow"); 480 } 481 stack().get(_stack_top++).set(cts); 482 if (DEBUG) { 483 System.err.println("After push: _stack_top: " + _stack_top + 484 " _max_stack: " + _max_stack + 485 " just pushed: " + cts.toChar()); 486 } 487 } 488 489 CellTypeState monitorPop () { 490 if (Assert.ASSERTS_ENABLED) { 491 Assert.that(_monitor_top != bad_monitors, "monitorPop called on error monitor stack"); 492 } 493 if (_monitor_top == 0) { 494 // We have detected a pop of an empty monitor stack. 495 _monitor_safe = false; 496 _monitor_top = bad_monitors; 497 498 if (TraceMonitorMismatch) { 499 reportMonitorMismatch("monitor stack underflow"); 500 } 501 return CellTypeState.ref; // just to keep the analysis going. 502 } 503 return monitors().get(--_monitor_top).copy(); 504 } 505 506 void monitorPush (CellTypeState cts) { 507 if (Assert.ASSERTS_ENABLED) { 508 Assert.that(_monitor_top != bad_monitors, "monitorPush called on error monitor stack"); 509 } 510 if (_monitor_top >= _max_monitors) { 511 // Some monitorenter is being executed more than once. 512 // This means that the monitor stack cannot be simulated. 513 _monitor_safe = false; 514 _monitor_top = bad_monitors; 515 516 if (TraceMonitorMismatch) { 517 reportMonitorMismatch("monitor stack overflow"); 518 } 519 return; 520 } 521 monitors().get(_monitor_top++).set(cts); 522 } 523 vars()524 CellTypeStateList vars () { return _state; } stack()525 CellTypeStateList stack () { return _state.subList(_max_locals, _state.size()); } monitors()526 CellTypeStateList monitors() { return _state.subList(_max_locals+_max_stack, _state.size()); } 527 replaceAllCTSMatches(CellTypeState match, CellTypeState replace)528 void replaceAllCTSMatches (CellTypeState match, 529 CellTypeState replace) { 530 int i; 531 int len = _max_locals + _stack_top; 532 boolean change = false; 533 534 for (i = len - 1; i >= 0; i--) { 535 if (match.equal(_state.get(i))) { 536 _state.get(i).set(replace); 537 } 538 } 539 540 if (_monitor_top > 0) { 541 int base = _max_locals + _max_stack; 542 len = base + _monitor_top; 543 for (i = len - 1; i >= base; i--) { 544 if (match.equal(_state.get(i))) { 545 _state.get(i).set(replace); 546 } 547 } 548 } 549 } 550 printStates(PrintStream tty, CellTypeStateList vector, int num)551 void printStates (PrintStream tty, CellTypeStateList vector, int num) { 552 for (int i = 0; i < num; i++) { 553 vector.get(i).print(tty); 554 } 555 } 556 printCurrentState(PrintStream tty, BytecodeStream currentBC, boolean detailed)557 void printCurrentState (PrintStream tty, 558 BytecodeStream currentBC, 559 boolean detailed) { 560 if (detailed) { 561 tty.print(" " + currentBC.bci() + " vars = "); 562 printStates(tty, vars(), _max_locals); 563 tty.print(" " + Bytecodes.name(currentBC.code())); 564 switch(currentBC.code()) { 565 case Bytecodes._invokevirtual: 566 case Bytecodes._invokespecial: 567 case Bytecodes._invokestatic: 568 case Bytecodes._invokeinterface: 569 case Bytecodes._invokedynamic: 570 // FIXME: print signature of referenced method (need more 571 // accessors in ConstantPool and ConstantPoolCache) 572 int idx = currentBC.hasIndexU4() ? currentBC.getIndexU4() : currentBC.getIndexU2(); 573 tty.print(" idx " + idx); 574 /* 575 int idx = currentBC.getIndexU2(); 576 ConstantPool cp = method().getConstants(); 577 int nameAndTypeIdx = cp.name_and_type_ref_index_at(idx); 578 int signatureIdx = cp.signature_ref_index_at(nameAndTypeIdx); 579 Symbol* signature = cp.symbol_at(signatureIdx); 580 tty.print("%s", signature.as_C_string()); 581 */ 582 } 583 tty.println(); 584 tty.print(" stack = "); 585 printStates(tty, stack(), _stack_top); 586 tty.println(); 587 if (_monitor_top != bad_monitors) { 588 tty.print(" monitors = "); 589 printStates(tty, monitors(), _monitor_top); 590 } else { 591 tty.print(" [bad monitor stack]"); 592 } 593 tty.println(); 594 } else { 595 tty.print(" " + currentBC.bci() + " vars = '" + 596 stateVecToString(vars(), _max_locals) + "' "); 597 tty.print(" stack = '" + stateVecToString(stack(), _stack_top) + "' "); 598 if (_monitor_top != bad_monitors) { 599 tty.print(" monitors = '" + stateVecToString(monitors(), _monitor_top) + "' \t" + 600 Bytecodes.name(currentBC.code())); 601 } else { 602 tty.print(" [bad monitor stack]"); 603 } 604 switch(currentBC.code()) { 605 case Bytecodes._invokevirtual: 606 case Bytecodes._invokespecial: 607 case Bytecodes._invokestatic: 608 case Bytecodes._invokeinterface: 609 case Bytecodes._invokedynamic: 610 // FIXME: print signature of referenced method (need more 611 // accessors in ConstantPool and ConstantPoolCache) 612 int idx = currentBC.hasIndexU4() ? currentBC.getIndexU4() : currentBC.getIndexU2(); 613 tty.print(" idx " + idx); 614 /* 615 int idx = currentBC.getIndexU2(); 616 ConstantPool* cp = method().constants(); 617 int nameAndTypeIdx = cp.name_and_type_ref_index_at(idx); 618 int signatureIdx = cp.signature_ref_index_at(nameAndTypeIdx); 619 Symbol* signature = cp.symbol_at(signatureIdx); 620 tty.print("%s", signature.as_C_string()); 621 */ 622 } 623 tty.println(); 624 } 625 } 626 reportMonitorMismatch(String msg)627 void reportMonitorMismatch (String msg) { 628 if (Assert.ASSERTS_ENABLED) { 629 System.err.print(" Monitor mismatch in method "); 630 method().printValueOn(System.err); 631 System.err.println(": " + msg); 632 } 633 } 634 635 // Basicblock info 636 BasicBlock[] _basic_blocks; // Array of basicblock info 637 int _gc_points; 638 int _bb_count; 639 BitMap _bb_hdr_bits; 640 641 // Basicblocks methods initializeBB()642 void initializeBB () { 643 _gc_points = 0; 644 _bb_count = 0; 645 _bb_hdr_bits = new BitMap((int) _method.getCodeSize()); 646 } 647 markBBHeadersAndCountGCPoints()648 void markBBHeadersAndCountGCPoints() { 649 initializeBB(); 650 651 boolean fellThrough = false; // False to get first BB marked. 652 653 // First mark all exception handlers as start of a basic-block 654 if (method().hasExceptionTable()) { 655 ExceptionTableElement[] excps = method().getExceptionTable(); 656 for(int i = 0; i < excps.length; i++) { 657 markBB(excps[i].getHandlerPC(), null); 658 } 659 } 660 661 // Then iterate through the code 662 BytecodeStream bcs = new BytecodeStream(_method); 663 int bytecode; 664 665 while( (bytecode = bcs.next()) >= 0) { 666 int bci = bcs.bci(); 667 668 if (!fellThrough) 669 markBB(bci, null); 670 671 fellThrough = jumpTargetsDo(bcs, 672 new JumpClosure() { 673 public void process(GenerateOopMap c, int bcpDelta, int[] data) { 674 c.markBB(bcpDelta, data); 675 } 676 }, 677 null); 678 679 /* We will also mark successors of jsr's as basic block headers. */ 680 switch (bytecode) { 681 case Bytecodes._jsr: 682 if (Assert.ASSERTS_ENABLED) { 683 Assert.that(!fellThrough, "should not happen"); 684 } 685 markBB(bci + Bytecodes.lengthFor(bytecode), null); 686 break; 687 case Bytecodes._jsr_w: 688 if (Assert.ASSERTS_ENABLED) { 689 Assert.that(!fellThrough, "should not happen"); 690 } 691 markBB(bci + Bytecodes.lengthFor(bytecode), null); 692 break; 693 } 694 695 if (possibleGCPoint(bcs)) 696 _gc_points++; 697 } 698 } 699 isBBHeader(int bci)700 boolean isBBHeader (int bci) { 701 return _bb_hdr_bits.at(bci); 702 } 703 gcPoints()704 int gcPoints () { 705 return _gc_points; 706 } 707 bbCount()708 int bbCount () { 709 return _bb_count; 710 } 711 setBBMarkBit(int bci)712 void setBBMarkBit (int bci) { 713 _bb_hdr_bits.atPut(bci, true); 714 } 715 clear_bbmark_bit(int bci)716 void clear_bbmark_bit (int bci) { 717 _bb_hdr_bits.atPut(bci, false); 718 } 719 getBasicBlockAt(int bci)720 BasicBlock getBasicBlockAt (int bci) { 721 BasicBlock bb = getBasicBlockContaining(bci); 722 if (Assert.ASSERTS_ENABLED) { 723 Assert.that(bb._bci == bci, "should have found BB"); 724 } 725 return bb; 726 } 727 getBasicBlockContaining(int bci)728 BasicBlock getBasicBlockContaining (int bci) { 729 BasicBlock[] bbs = _basic_blocks; 730 int lo = 0, hi = _bb_count - 1; 731 732 while (lo <= hi) { 733 int m = (lo + hi) / 2; 734 int mbci = bbs[m]._bci; 735 int nbci; 736 737 if ( m == _bb_count-1) { 738 if (Assert.ASSERTS_ENABLED) { 739 Assert.that( bci >= mbci && bci < method().getCodeSize(), "sanity check failed"); 740 } 741 return bbs[m]; 742 } else { 743 nbci = bbs[m+1]._bci; 744 } 745 746 if ( mbci <= bci && bci < nbci) { 747 return bbs[m]; 748 } else if (mbci < bci) { 749 lo = m + 1; 750 } else { 751 if (Assert.ASSERTS_ENABLED) { 752 Assert.that(mbci > bci, "sanity check"); 753 } 754 hi = m - 1; 755 } 756 } 757 758 throw new RuntimeException("should have found BB"); 759 } 760 interpBB(BasicBlock bb)761 void interpBB (BasicBlock bb) { 762 // We do not want to do anything in case the basic-block has not been initialized. This 763 // will happen in the case where there is dead-code hang around in a method. 764 if (Assert.ASSERTS_ENABLED) { 765 Assert.that(bb.isReachable(), "should be reachable or deadcode exist"); 766 } 767 restoreState(bb); 768 769 BytecodeStream itr = new BytecodeStream(_method); 770 771 // Set iterator interval to be the current basicblock 772 int lim_bci = nextBBStartPC(bb); 773 itr.setInterval(bb._bci, lim_bci); 774 775 if (DEBUG) { 776 System.err.println("interpBB: method = " + method().getName().asString() + 777 method().getSignature().asString() + 778 ", BCI interval [" + bb._bci + ", " + lim_bci + ")"); 779 { 780 System.err.print("Bytecodes:"); 781 for (int i = bb._bci; i < lim_bci; i++) { 782 System.err.print(" 0x" + Long.toHexString(method().getBytecodeOrBPAt(i))); 783 } 784 System.err.println(); 785 } 786 } 787 788 if (Assert.ASSERTS_ENABLED) { 789 Assert.that(lim_bci != bb._bci, "must be at least one instruction in a basicblock"); 790 } 791 itr.next(); // read first instruction 792 793 // Iterates through all bytecodes except the last in a basic block. 794 // We handle the last one special, since there is controlflow change. 795 while(itr.nextBCI() < lim_bci && !_got_error) { 796 if (_has_exceptions || (_monitor_top != 0)) { 797 // We do not need to interpret the results of exceptional 798 // continuation from this instruction when the method has no 799 // exception handlers and the monitor stack is currently 800 // empty. 801 doExceptionEdge(itr); 802 } 803 interp1(itr); 804 itr.next(); 805 } 806 807 // Handle last instruction. 808 if (!_got_error) { 809 if (Assert.ASSERTS_ENABLED) { 810 Assert.that(itr.nextBCI() == lim_bci, "must point to end"); 811 } 812 if (_has_exceptions || (_monitor_top != 0)) { 813 doExceptionEdge(itr); 814 } 815 interp1(itr); 816 817 boolean fall_through = jumpTargetsDo(itr, new JumpClosure() { 818 public void process(GenerateOopMap c, int bcpDelta, int[] data) { 819 c.mergeState(bcpDelta, data); 820 } 821 }, null); 822 if (_got_error) return; 823 824 if (itr.code() == Bytecodes._ret) { 825 if (Assert.ASSERTS_ENABLED) { 826 Assert.that(!fall_through, "cannot be set if ret instruction"); 827 } 828 // Automatically handles 'wide' ret indicies 829 retJumpTargetsDo(itr, new JumpClosure() { 830 public void process(GenerateOopMap c, int bcpDelta, int[] data) { 831 c.mergeState(bcpDelta, data); 832 } 833 }, itr.getIndex(), null); 834 } else if (fall_through) { 835 // Hit end of BB, but the instr. was a fall-through instruction, 836 // so perform transition as if the BB ended in a "jump". 837 if (Assert.ASSERTS_ENABLED) { 838 Assert.that(lim_bci == _basic_blocks[bbIndex(bb) + 1]._bci, "there must be another bb"); 839 } 840 mergeStateIntoBB(_basic_blocks[bbIndex(bb) + 1]); 841 } 842 } 843 } 844 restoreState(BasicBlock bb)845 void restoreState (BasicBlock bb) { 846 for (int i = 0; i < _state_len; i++) { 847 _state.get(i).set(bb._state.get(i)); 848 } 849 _stack_top = bb._stack_top; 850 _monitor_top = bb._monitor_top; 851 } 852 nextBBStartPC(BasicBlock bb)853 int nextBBStartPC (BasicBlock bb) { 854 int bbNum = bbIndex(bb) + 1; 855 if (bbNum == _bb_count) 856 return (int) method().getCodeSize(); 857 858 return _basic_blocks[bbNum]._bci; 859 } 860 updateBasicBlocks(int bci, int delta)861 void updateBasicBlocks (int bci, int delta) { 862 BitMap bbBits = new BitMap((int) (_method.getCodeSize() + delta)); 863 for(int k = 0; k < _bb_count; k++) { 864 if (_basic_blocks[k]._bci > bci) { 865 _basic_blocks[k]._bci += delta; 866 _basic_blocks[k]._end_bci += delta; 867 } 868 bbBits.atPut(_basic_blocks[k]._bci, true); 869 } 870 _bb_hdr_bits = bbBits; 871 } 872 markBB(int bci, int[] data)873 void markBB(int bci, int[] data) { 874 if (Assert.ASSERTS_ENABLED) { 875 Assert.that(bci>= 0 && bci < method().getCodeSize(), "index out of bounds"); 876 } 877 if (isBBHeader(bci)) 878 return; 879 880 // FIXME: remove 881 // if (TraceNewOopMapGeneration) { 882 // tty.print_cr("Basicblock#%d begins at: %d", c._bb_count, bci); 883 // } 884 setBBMarkBit(bci); 885 _bb_count++; 886 } 887 888 // Dead code detection markReachableCode()889 void markReachableCode() { 890 final int[] change = new int[1]; 891 change[0] = 1; 892 893 // Mark entry basic block as alive and all exception handlers 894 _basic_blocks[0].markAsAlive(); 895 if (method().hasExceptionTable()) { 896 ExceptionTableElement[] excps = method().getExceptionTable(); 897 for(int i = 0; i < excps.length; i ++) { 898 BasicBlock bb = getBasicBlockAt(excps[i].getHandlerPC()); 899 // If block is not already alive (due to multiple exception handlers to same bb), then 900 // make it alive 901 if (bb.isDead()) 902 bb.markAsAlive(); 903 } 904 } 905 906 BytecodeStream bcs = new BytecodeStream(_method); 907 908 // Iterate through all basic blocks until we reach a fixpoint 909 while (change[0] != 0) { 910 change[0] = 0; 911 912 for (int i = 0; i < _bb_count; i++) { 913 BasicBlock bb = _basic_blocks[i]; 914 if (bb.isAlive()) { 915 // Position bytecodestream at last bytecode in basicblock 916 bcs.setStart(bb._end_bci); 917 bcs.next(); 918 int bytecode = bcs.code(); 919 int bci = bcs.bci(); 920 if (Assert.ASSERTS_ENABLED) { 921 Assert.that(bci == bb._end_bci, "wrong bci"); 922 } 923 924 boolean fell_through = jumpTargetsDo(bcs, new JumpClosure() { 925 public void process(GenerateOopMap c, int bciDelta, int[] change) { 926 c.reachableBasicblock(bciDelta, change); 927 } 928 }, change); 929 930 // We will also mark successors of jsr's as alive. 931 switch (bytecode) { 932 case Bytecodes._jsr: 933 case Bytecodes._jsr_w: 934 if (Assert.ASSERTS_ENABLED) { 935 Assert.that(!fell_through, "should not happen"); 936 } 937 reachableBasicblock(bci + Bytecodes.lengthFor(bytecode), change); 938 break; 939 } 940 if (fell_through) { 941 // Mark successor as alive 942 if (_basic_blocks[i+1].isDead()) { 943 _basic_blocks[i+1].markAsAlive(); 944 change[0] = 1; 945 } 946 } 947 } 948 } 949 } 950 } 951 reachableBasicblock(int bci, int[] data)952 void reachableBasicblock (int bci, int[] data) { 953 if (Assert.ASSERTS_ENABLED) { 954 Assert.that(bci>= 0 && bci < method().getCodeSize(), "index out of bounds"); 955 } 956 BasicBlock bb = getBasicBlockAt(bci); 957 if (bb.isDead()) { 958 bb.markAsAlive(); 959 data[0] = 1; // Mark basicblock as changed 960 } 961 } 962 963 // Interpretation methods (primary) doInterpretation()964 void doInterpretation () { 965 // "i" is just for debugging, so we can detect cases where this loop is 966 // iterated more than once. 967 int i = 0; 968 do { 969 // FIXME: remove 970 // if (TraceNewOopMapGeneration) { 971 // tty.print("\n\nIteration #%d of do_interpretation loop, method:\n", i); 972 // method().print_name(tty); 973 // tty.print("\n\n"); 974 // } 975 _conflict = false; 976 _monitor_safe = true; 977 // init_state is now called from init_basic_blocks. The length of a 978 // state vector cannot be determined until we have made a pass through 979 // the bytecodes counting the possible monitor entries. 980 if (!_got_error) initBasicBlocks(); 981 if (!_got_error) setupMethodEntryState(); 982 if (!_got_error) interpAll(); 983 if (!_got_error) rewriteRefvalConflicts(); 984 i++; 985 } while (_conflict && !_got_error); 986 } 987 initBasicBlocks()988 void initBasicBlocks () { 989 // Note: Could consider reserving only the needed space for each BB's state 990 // (entry stack may not be of maximal height for every basic block). 991 // But cumbersome since we don't know the stack heights yet. (Nor the 992 // monitor stack heights...) 993 994 _basic_blocks = new BasicBlock[_bb_count]; 995 for (int i = 0; i < _bb_count; i++) { 996 _basic_blocks[i] = new BasicBlock(); 997 } 998 999 // Make a pass through the bytecodes. Count the number of monitorenters. 1000 // This can be used an upper bound on the monitor stack depth in programs 1001 // which obey stack discipline with their monitor usage. Initialize the 1002 // known information about basic blocks. 1003 BytecodeStream j = new BytecodeStream(_method); 1004 int bytecode; 1005 1006 int bbNo = 0; 1007 int monitor_count = 0; 1008 int prev_bci = -1; 1009 while( (bytecode = j.next()) >= 0) { 1010 if (j.code() == Bytecodes._monitorenter) { 1011 monitor_count++; 1012 } 1013 1014 int bci = j.bci(); 1015 if (isBBHeader(bci)) { 1016 // Initialize the basicblock structure 1017 BasicBlock bb = _basic_blocks[bbNo]; 1018 bb._bci = bci; 1019 bb._max_locals = _max_locals; 1020 bb._max_stack = _max_stack; 1021 bb.setChanged(false); 1022 bb._stack_top = BasicBlock._dead_basic_block; // Initialize all basicblocks are dead. 1023 bb._monitor_top = bad_monitors; 1024 1025 if (bbNo > 0) { 1026 _basic_blocks[bbNo - 1]._end_bci = prev_bci; 1027 } 1028 1029 bbNo++; 1030 } 1031 // Remember prevous bci. 1032 prev_bci = bci; 1033 } 1034 // Set 1035 _basic_blocks[bbNo-1]._end_bci = prev_bci; 1036 1037 _max_monitors = monitor_count; 1038 1039 // Now that we have a bound on the depth of the monitor stack, we can 1040 // initialize the CellTypeState-related information. 1041 initState(); 1042 1043 // We allocate space for all state-vectors for all basicblocks in one huge chuck. 1044 // Then in the next part of the code, we set a pointer in each _basic_block that 1045 // points to each piece. 1046 CellTypeStateList basicBlockState = new CellTypeStateList(bbNo * _state_len); 1047 1048 // Make a pass over the basicblocks and assign their state vectors. 1049 for (int blockNum=0; blockNum < bbNo; blockNum++) { 1050 BasicBlock bb = _basic_blocks[blockNum]; 1051 bb._state = basicBlockState.subList(blockNum * _state_len, (blockNum + 1) * _state_len); 1052 1053 if (Assert.ASSERTS_ENABLED) { 1054 if (blockNum + 1 < bbNo) { 1055 int bc_len = Bytecodes.javaLengthAt(_method, bb._end_bci); 1056 Assert.that(bb._end_bci + bc_len == _basic_blocks[blockNum + 1]._bci, 1057 "unmatched bci info in basicblock"); 1058 } 1059 } 1060 } 1061 if (Assert.ASSERTS_ENABLED) { 1062 BasicBlock bb = _basic_blocks[bbNo-1]; 1063 int bc_len = Bytecodes.javaLengthAt(_method, bb._end_bci); 1064 Assert.that(bb._end_bci + bc_len == _method.getCodeSize(), "wrong end bci"); 1065 } 1066 1067 // Check that the correct number of basicblocks was found 1068 if (bbNo !=_bb_count) { 1069 if (bbNo < _bb_count) { 1070 throw new RuntimeException("jump into the middle of instruction?"); 1071 } else { 1072 throw new RuntimeException("extra basic blocks - should not happen?"); 1073 } 1074 } 1075 1076 // Mark all alive blocks 1077 markReachableCode(); 1078 } 1079 setupMethodEntryState()1080 void setupMethodEntryState () { 1081 // Initialize all locals to 'uninit' and set stack-height to 0 1082 makeContextUninitialized(); 1083 1084 // Initialize CellState type of arguments 1085 methodsigToEffect(method().getSignature(), method().isStatic(), vars()); 1086 1087 // If some references must be pre-assigned to null, then set that up 1088 initializeVars(); 1089 1090 // This is the start state 1091 mergeStateIntoBB(_basic_blocks[0]); 1092 1093 if (Assert.ASSERTS_ENABLED) { 1094 Assert.that(_basic_blocks[0].changed(), "we are not getting off the ground"); 1095 } 1096 } 1097 interpAll()1098 void interpAll () { 1099 boolean change = true; 1100 1101 while (change && !_got_error) { 1102 change = false; 1103 for (int i = 0; i < _bb_count && !_got_error; i++) { 1104 BasicBlock bb = _basic_blocks[i]; 1105 if (bb.changed()) { 1106 if (_got_error) return; 1107 change = true; 1108 bb.setChanged(false); 1109 interpBB(bb); 1110 } 1111 } 1112 } 1113 } 1114 1115 // 1116 // Interpretation methods (secondary) 1117 // 1118 1119 /** Sets the current state to be the state after executing the 1120 current instruction, starting in the current state. */ interp1(BytecodeStream itr)1121 void interp1 (BytecodeStream itr) { 1122 if (DEBUG) { 1123 System.err.println(" - bci " + itr.bci() + " " + itr.code()); 1124 printCurrentState(System.err, itr, false); 1125 } 1126 1127 // if (TraceNewOopMapGeneration) { 1128 // print_current_state(tty, itr, TraceNewOopMapGenerationDetailed); 1129 // } 1130 1131 // Should we report the results? Result is reported *before* the 1132 // instruction at the current bci is executed. However, not for 1133 // calls. For calls we do not want to include the arguments, so we 1134 // postpone the reporting until they have been popped (in method 1135 // ppl). 1136 if (_report_result == true) { 1137 switch(itr.code()) { 1138 case Bytecodes._invokevirtual: 1139 case Bytecodes._invokespecial: 1140 case Bytecodes._invokestatic: 1141 case Bytecodes._invokeinterface: 1142 case Bytecodes._invokedynamic: 1143 _itr_send = itr; 1144 _report_result_for_send = true; 1145 break; 1146 default: 1147 fillStackmapForOpcodes(itr, vars(), stack(), _stack_top); 1148 break; 1149 } 1150 } 1151 1152 // abstract interpretation of current opcode 1153 switch(itr.code()) { 1154 case Bytecodes._nop: break; 1155 case Bytecodes._goto: break; 1156 case Bytecodes._goto_w: break; 1157 case Bytecodes._iinc: break; 1158 case Bytecodes._return: doReturnMonitorCheck(); 1159 break; 1160 1161 case Bytecodes._aconst_null: 1162 case Bytecodes._new: ppush1(CellTypeState.makeLineRef(itr.bci())); 1163 break; 1164 1165 case Bytecodes._iconst_m1: 1166 case Bytecodes._iconst_0: 1167 case Bytecodes._iconst_1: 1168 case Bytecodes._iconst_2: 1169 case Bytecodes._iconst_3: 1170 case Bytecodes._iconst_4: 1171 case Bytecodes._iconst_5: 1172 case Bytecodes._fconst_0: 1173 case Bytecodes._fconst_1: 1174 case Bytecodes._fconst_2: 1175 case Bytecodes._bipush: 1176 case Bytecodes._sipush: ppush1(valCTS); break; 1177 1178 case Bytecodes._lconst_0: 1179 case Bytecodes._lconst_1: 1180 case Bytecodes._dconst_0: 1181 case Bytecodes._dconst_1: ppush(vvCTS); break; 1182 1183 case Bytecodes._ldc2_w: ppush(vvCTS); break; 1184 1185 case Bytecodes._ldc: doLdc(itr.bci()); break; 1186 case Bytecodes._ldc_w: doLdc(itr.bci()); break; 1187 1188 case Bytecodes._iload: 1189 case Bytecodes._fload: ppload(vCTS, itr.getIndex()); break; 1190 1191 case Bytecodes._lload: 1192 case Bytecodes._dload: ppload(vvCTS,itr.getIndex()); break; 1193 1194 case Bytecodes._aload: ppload(rCTS, itr.getIndex()); break; 1195 1196 case Bytecodes._iload_0: 1197 case Bytecodes._fload_0: ppload(vCTS, 0); break; 1198 case Bytecodes._iload_1: 1199 case Bytecodes._fload_1: ppload(vCTS, 1); break; 1200 case Bytecodes._iload_2: 1201 case Bytecodes._fload_2: ppload(vCTS, 2); break; 1202 case Bytecodes._iload_3: 1203 case Bytecodes._fload_3: ppload(vCTS, 3); break; 1204 1205 case Bytecodes._lload_0: 1206 case Bytecodes._dload_0: ppload(vvCTS, 0); break; 1207 case Bytecodes._lload_1: 1208 case Bytecodes._dload_1: ppload(vvCTS, 1); break; 1209 case Bytecodes._lload_2: 1210 case Bytecodes._dload_2: ppload(vvCTS, 2); break; 1211 case Bytecodes._lload_3: 1212 case Bytecodes._dload_3: ppload(vvCTS, 3); break; 1213 1214 case Bytecodes._aload_0: ppload(rCTS, 0); break; 1215 case Bytecodes._aload_1: ppload(rCTS, 1); break; 1216 case Bytecodes._aload_2: ppload(rCTS, 2); break; 1217 case Bytecodes._aload_3: ppload(rCTS, 3); break; 1218 1219 case Bytecodes._iaload: 1220 case Bytecodes._faload: 1221 case Bytecodes._baload: 1222 case Bytecodes._caload: 1223 case Bytecodes._saload: pp(vrCTS, vCTS); break; 1224 1225 case Bytecodes._laload: pp(vrCTS, vvCTS); break; 1226 case Bytecodes._daload: pp(vrCTS, vvCTS); break; 1227 1228 case Bytecodes._aaload: ppNewRef(vrCTS, itr.bci()); break; 1229 1230 case Bytecodes._istore: 1231 case Bytecodes._fstore: ppstore(vCTS, itr.getIndex()); break; 1232 1233 case Bytecodes._lstore: 1234 case Bytecodes._dstore: ppstore(vvCTS, itr.getIndex()); break; 1235 1236 case Bytecodes._astore: doAstore(itr.getIndex()); break; 1237 1238 case Bytecodes._istore_0: 1239 case Bytecodes._fstore_0: ppstore(vCTS, 0); break; 1240 case Bytecodes._istore_1: 1241 case Bytecodes._fstore_1: ppstore(vCTS, 1); break; 1242 case Bytecodes._istore_2: 1243 case Bytecodes._fstore_2: ppstore(vCTS, 2); break; 1244 case Bytecodes._istore_3: 1245 case Bytecodes._fstore_3: ppstore(vCTS, 3); break; 1246 1247 case Bytecodes._lstore_0: 1248 case Bytecodes._dstore_0: ppstore(vvCTS, 0); break; 1249 case Bytecodes._lstore_1: 1250 case Bytecodes._dstore_1: ppstore(vvCTS, 1); break; 1251 case Bytecodes._lstore_2: 1252 case Bytecodes._dstore_2: ppstore(vvCTS, 2); break; 1253 case Bytecodes._lstore_3: 1254 case Bytecodes._dstore_3: ppstore(vvCTS, 3); break; 1255 1256 case Bytecodes._astore_0: doAstore(0); break; 1257 case Bytecodes._astore_1: doAstore(1); break; 1258 case Bytecodes._astore_2: doAstore(2); break; 1259 case Bytecodes._astore_3: doAstore(3); break; 1260 1261 case Bytecodes._iastore: 1262 case Bytecodes._fastore: 1263 case Bytecodes._bastore: 1264 case Bytecodes._castore: 1265 case Bytecodes._sastore: ppop(vvrCTS); break; 1266 case Bytecodes._lastore: 1267 case Bytecodes._dastore: ppop(vvvrCTS); break; 1268 case Bytecodes._aastore: ppop(rvrCTS); break; 1269 1270 case Bytecodes._pop: ppopAny(1); break; 1271 case Bytecodes._pop2: ppopAny(2); break; 1272 1273 case Bytecodes._dup: ppdupswap(1, "11"); break; 1274 case Bytecodes._dup_x1: ppdupswap(2, "121"); break; 1275 case Bytecodes._dup_x2: ppdupswap(3, "1321"); break; 1276 case Bytecodes._dup2: ppdupswap(2, "2121"); break; 1277 case Bytecodes._dup2_x1: ppdupswap(3, "21321"); break; 1278 case Bytecodes._dup2_x2: ppdupswap(4, "214321"); break; 1279 case Bytecodes._swap: ppdupswap(2, "12"); break; 1280 1281 case Bytecodes._iadd: 1282 case Bytecodes._fadd: 1283 case Bytecodes._isub: 1284 case Bytecodes._fsub: 1285 case Bytecodes._imul: 1286 case Bytecodes._fmul: 1287 case Bytecodes._idiv: 1288 case Bytecodes._fdiv: 1289 case Bytecodes._irem: 1290 case Bytecodes._frem: 1291 case Bytecodes._ishl: 1292 case Bytecodes._ishr: 1293 case Bytecodes._iushr: 1294 case Bytecodes._iand: 1295 case Bytecodes._ior: 1296 case Bytecodes._ixor: 1297 case Bytecodes._l2f: 1298 case Bytecodes._l2i: 1299 case Bytecodes._d2f: 1300 case Bytecodes._d2i: 1301 case Bytecodes._fcmpl: 1302 case Bytecodes._fcmpg: pp(vvCTS, vCTS); break; 1303 1304 case Bytecodes._ladd: 1305 case Bytecodes._dadd: 1306 case Bytecodes._lsub: 1307 case Bytecodes._dsub: 1308 case Bytecodes._lmul: 1309 case Bytecodes._dmul: 1310 case Bytecodes._ldiv: 1311 case Bytecodes._ddiv: 1312 case Bytecodes._lrem: 1313 case Bytecodes._drem: 1314 case Bytecodes._land: 1315 case Bytecodes._lor: 1316 case Bytecodes._lxor: pp(vvvvCTS, vvCTS); break; 1317 1318 case Bytecodes._ineg: 1319 case Bytecodes._fneg: 1320 case Bytecodes._i2f: 1321 case Bytecodes._f2i: 1322 case Bytecodes._i2c: 1323 case Bytecodes._i2s: 1324 case Bytecodes._i2b: pp(vCTS, vCTS); break; 1325 1326 case Bytecodes._lneg: 1327 case Bytecodes._dneg: 1328 case Bytecodes._l2d: 1329 case Bytecodes._d2l: pp(vvCTS, vvCTS); break; 1330 1331 case Bytecodes._lshl: 1332 case Bytecodes._lshr: 1333 case Bytecodes._lushr: pp(vvvCTS, vvCTS); break; 1334 1335 case Bytecodes._i2l: 1336 case Bytecodes._i2d: 1337 case Bytecodes._f2l: 1338 case Bytecodes._f2d: pp(vCTS, vvCTS); break; 1339 1340 case Bytecodes._lcmp: pp(vvvvCTS, vCTS); break; 1341 case Bytecodes._dcmpl: 1342 case Bytecodes._dcmpg: pp(vvvvCTS, vCTS); break; 1343 1344 case Bytecodes._ifeq: 1345 case Bytecodes._ifne: 1346 case Bytecodes._iflt: 1347 case Bytecodes._ifge: 1348 case Bytecodes._ifgt: 1349 case Bytecodes._ifle: 1350 case Bytecodes._tableswitch: ppop1(valCTS); 1351 break; 1352 case Bytecodes._ireturn: 1353 case Bytecodes._freturn: doReturnMonitorCheck(); 1354 ppop1(valCTS); 1355 break; 1356 case Bytecodes._if_icmpeq: 1357 case Bytecodes._if_icmpne: 1358 case Bytecodes._if_icmplt: 1359 case Bytecodes._if_icmpge: 1360 case Bytecodes._if_icmpgt: 1361 case Bytecodes._if_icmple: ppop(vvCTS); 1362 break; 1363 1364 case Bytecodes._lreturn: doReturnMonitorCheck(); 1365 ppop(vvCTS); 1366 break; 1367 1368 case Bytecodes._dreturn: doReturnMonitorCheck(); 1369 ppop(vvCTS); 1370 break; 1371 1372 case Bytecodes._if_acmpeq: 1373 case Bytecodes._if_acmpne: ppop(rrCTS); break; 1374 1375 case Bytecodes._jsr: doJsr(itr.dest()); break; 1376 case Bytecodes._jsr_w: doJsr(itr.dest_w()); break; 1377 1378 case Bytecodes._getstatic: doField(true, true, itr.getIndexU2Cpcache(), itr.bci()); break; 1379 case Bytecodes._putstatic: doField(false, true, itr.getIndexU2Cpcache(), itr.bci()); break; 1380 case Bytecodes._getfield: doField(true, false, itr.getIndexU2Cpcache(), itr.bci()); break; 1381 case Bytecodes._putfield: doField(false, false, itr.getIndexU2Cpcache(), itr.bci()); break; 1382 1383 case Bytecodes._invokevirtual: 1384 case Bytecodes._invokespecial: doMethod(false, false, itr.getIndexU2Cpcache(), itr.bci()); break; 1385 case Bytecodes._invokestatic: doMethod(true, false, itr.getIndexU2Cpcache(), itr.bci()); break; 1386 case Bytecodes._invokedynamic: doMethod(true, false, itr.getIndexU4(), itr.bci()); break; 1387 case Bytecodes._invokeinterface: doMethod(false, true, itr.getIndexU2Cpcache(), itr.bci()); break; 1388 case Bytecodes._newarray: 1389 case Bytecodes._anewarray: ppNewRef(vCTS, itr.bci()); break; 1390 case Bytecodes._checkcast: doCheckcast(); break; 1391 case Bytecodes._arraylength: 1392 case Bytecodes._instanceof: pp(rCTS, vCTS); break; 1393 case Bytecodes._monitorenter: doMonitorenter(itr.bci()); break; 1394 case Bytecodes._monitorexit: doMonitorexit(itr.bci()); break; 1395 1396 case Bytecodes._athrow: // handled by do_exception_edge() BUT ... 1397 // vlh(apple): doExceptionEdge() does not get 1398 // called if method has no exception handlers 1399 if ((!_has_exceptions) && (_monitor_top > 0)) { 1400 _monitor_safe = false; 1401 } 1402 break; 1403 1404 case Bytecodes._areturn: doReturnMonitorCheck(); 1405 ppop1(refCTS); 1406 break; 1407 case Bytecodes._ifnull: 1408 case Bytecodes._ifnonnull: ppop1(refCTS); break; 1409 case Bytecodes._multianewarray: doMultianewarray(itr.codeAt(itr.bci() + 3), itr.bci()); break; 1410 1411 case Bytecodes._wide: throw new RuntimeException("Iterator should skip this bytecode"); 1412 case Bytecodes._ret: break; 1413 1414 // Java opcodes 1415 case Bytecodes._fast_aaccess_0: ppNewRef(rCTS, itr.bci()); break; // Pair bytecode for (aload_0, _fast_agetfield) 1416 1417 case Bytecodes._fast_iaccess_0: ppush1(valCTS); break; // Pair bytecode for (aload_0, _fast_igetfield) 1418 1419 case Bytecodes._fast_igetfield: pp(rCTS, vCTS); break; 1420 1421 case Bytecodes._fast_agetfield: ppNewRef(rCTS, itr.bci()); break; 1422 1423 case Bytecodes._fast_aload_0: ppload(rCTS, 0); break; 1424 1425 case Bytecodes._lookupswitch: 1426 case Bytecodes._fast_linearswitch: 1427 case Bytecodes._fast_binaryswitch: ppop1(valCTS); break; 1428 1429 default: 1430 throw new RuntimeException("unexpected opcode: " + itr.code()); 1431 } 1432 } 1433 doExceptionEdge(BytecodeStream itr)1434 void doExceptionEdge (BytecodeStream itr) { 1435 // Only check exception edge, if bytecode can trap 1436 if (!Bytecodes.canTrap(itr.code())) return; 1437 switch (itr.code()) { 1438 case Bytecodes._aload_0: 1439 case Bytecodes._fast_aload_0: 1440 // These bytecodes can trap for rewriting. We need to assume that 1441 // they do not throw exceptions to make the monitor analysis work. 1442 return; 1443 1444 case Bytecodes._ireturn: 1445 case Bytecodes._lreturn: 1446 case Bytecodes._freturn: 1447 case Bytecodes._dreturn: 1448 case Bytecodes._areturn: 1449 case Bytecodes._return: 1450 // If the monitor stack height is not zero when we leave the method, 1451 // then we are either exiting with a non-empty stack or we have 1452 // found monitor trouble earlier in our analysis. In either case, 1453 // assume an exception could be taken here. 1454 if (_monitor_top == 0) { 1455 return; 1456 } 1457 break; 1458 1459 case Bytecodes._monitorexit: 1460 // If the monitor stack height is bad_monitors, then we have detected a 1461 // monitor matching problem earlier in the analysis. If the 1462 // monitor stack height is 0, we are about to pop a monitor 1463 // off of an empty stack. In either case, the bytecode 1464 // could throw an exception. 1465 if (_monitor_top != bad_monitors && _monitor_top != 0) { 1466 return; 1467 } 1468 break; 1469 } 1470 1471 if (_has_exceptions) { 1472 int bci = itr.bci(); 1473 ExceptionTableElement[] exct = method().getExceptionTable(); 1474 for(int i = 0; i< exct.length; i++) { 1475 int start_pc = exct[i].getStartPC(); 1476 int end_pc = exct[i].getEndPC(); 1477 int handler_pc = exct[i].getHandlerPC(); 1478 int catch_type = exct[i].getCatchTypeIndex(); 1479 1480 if (start_pc <= bci && bci < end_pc) { 1481 BasicBlock excBB = getBasicBlockAt(handler_pc); 1482 CellTypeStateList excStk = excBB.stack(); 1483 CellTypeStateList cOpStck = stack(); 1484 CellTypeState cOpStck_0 = cOpStck.get(0).copy(); 1485 int cOpStackTop = _stack_top; 1486 1487 // Exception stacks are always the same. 1488 if (Assert.ASSERTS_ENABLED) { 1489 Assert.that(method().getMaxStack() > 0, "sanity check"); 1490 } 1491 1492 // We remembered the size and first element of "cOpStck" 1493 // above; now we temporarily set them to the appropriate 1494 // values for an exception handler. 1495 cOpStck.get(0).set(CellTypeState.makeSlotRef(_max_locals)); 1496 _stack_top = 1; 1497 1498 mergeStateIntoBB(excBB); 1499 1500 // Now undo the temporary change. 1501 cOpStck.get(0).set(cOpStck_0); 1502 _stack_top = cOpStackTop; 1503 1504 // If this is a "catch all" handler, then we do not need to 1505 // consider any additional handlers. 1506 if (catch_type == 0) { 1507 return; 1508 } 1509 } 1510 } 1511 } 1512 1513 // It is possible that none of the exception handlers would have caught 1514 // the exception. In this case, we will exit the method. We must 1515 // ensure that the monitor stack is empty in this case. 1516 if (_monitor_top == 0) { 1517 return; 1518 } 1519 1520 // We pessimistically assume that this exception can escape the 1521 // method. (It is possible that it will always be caught, but 1522 // we don't care to analyse the types of the catch clauses.) 1523 1524 // We don't set _monitor_top to bad_monitors because there are no successors 1525 // to this exceptional exit. 1526 1527 if (TraceMonitorMismatch && _monitor_safe) { 1528 // We check _monitor_safe so that we only report the first mismatched 1529 // exceptional exit. 1530 reportMonitorMismatch("non-empty monitor stack at exceptional exit"); 1531 } 1532 _monitor_safe = false; 1533 } 1534 checkType(CellTypeState expected, CellTypeState actual)1535 void checkType (CellTypeState expected, CellTypeState actual) { 1536 if (!expected.equalKind(actual)) { 1537 throw new RuntimeException("wrong type on stack (found: " + 1538 actual.toChar() + " expected: " + 1539 expected.toChar() + ")"); 1540 } 1541 } 1542 ppstore(CellTypeState[] in, int loc_no)1543 void ppstore (CellTypeState[] in, int loc_no) { 1544 for (int i = 0; i < in.length && !in[i].equal(CellTypeState.bottom); i++) { 1545 CellTypeState expected = in[i]; 1546 CellTypeState actual = pop(); 1547 checkType(expected, actual); 1548 if (Assert.ASSERTS_ENABLED) { 1549 Assert.that(loc_no >= 0, "sanity check"); 1550 } 1551 setVar(loc_no++, actual); 1552 } 1553 } 1554 ppload(CellTypeState[] out, int loc_no)1555 void ppload (CellTypeState[] out, int loc_no) { 1556 for (int i = 0; i < out.length && !out[i].equal(CellTypeState.bottom); i++) { 1557 CellTypeState out1 = out[i]; 1558 CellTypeState vcts = getVar(loc_no); 1559 if (Assert.ASSERTS_ENABLED) { 1560 Assert.that(out1.canBeReference() || out1.canBeValue(), 1561 "can only load refs. and values."); 1562 } 1563 if (out1.isReference()) { 1564 if (Assert.ASSERTS_ENABLED) { 1565 Assert.that(loc_no>=0, "sanity check"); 1566 } 1567 if (!vcts.isReference()) { 1568 // We were asked to push a reference, but the type of the 1569 // variable can be something else 1570 _conflict = true; 1571 if (vcts.canBeUninit()) { 1572 // It is a ref-uninit conflict (at least). If there are other 1573 // problems, we'll get them in the next round 1574 addToRefInitSet(loc_no); 1575 vcts = out1; 1576 } else { 1577 // It wasn't a ref-uninit conflict. So must be a 1578 // ref-val or ref-pc conflict. Split the variable. 1579 recordRefvalConflict(loc_no); 1580 vcts = out1; 1581 } 1582 push(out1); // recover... 1583 } else { 1584 push(vcts); // preserve reference. 1585 } 1586 // Otherwise it is a conflict, but one that verification would 1587 // have caught if illegal. In particular, it can't be a topCTS 1588 // resulting from mergeing two difference pcCTS's since the verifier 1589 // would have rejected any use of such a merge. 1590 } else { 1591 push(out1); // handle val/init conflict 1592 } 1593 loc_no++; 1594 } 1595 } 1596 ppush1(CellTypeState in)1597 void ppush1 (CellTypeState in) { 1598 if (Assert.ASSERTS_ENABLED) { 1599 Assert.that(in.isReference() | in.isValue(), "sanity check"); 1600 } 1601 if (DEBUG) { 1602 System.err.println(" - pushing " + in.toChar()); 1603 } 1604 push(in); 1605 } 1606 ppush(CellTypeState[] in)1607 void ppush (CellTypeState[] in) { 1608 for (int i = 0; i < in.length && !in[i].equal(CellTypeState.bottom); i++) { 1609 ppush1(in[i]); 1610 } 1611 } 1612 ppush(CellTypeStateList in)1613 void ppush (CellTypeStateList in) { 1614 for (int i = 0; i < in.size() && !in.get(i).equal(CellTypeState.bottom); i++) { 1615 ppush1(in.get(i)); 1616 } 1617 } 1618 ppop1(CellTypeState out)1619 void ppop1 (CellTypeState out) { 1620 CellTypeState actual = pop(); 1621 if (DEBUG) { 1622 System.err.println(" - popping " + actual.toChar() + ", expecting " + out.toChar()); 1623 } 1624 checkType(out, actual); 1625 } 1626 ppop(CellTypeState[] out)1627 void ppop (CellTypeState[] out) { 1628 for (int i = 0; i < out.length && !out[i].equal(CellTypeState.bottom); i++) { 1629 ppop1(out[i]); 1630 } 1631 } 1632 ppopAny(int poplen)1633 void ppopAny (int poplen) { 1634 if (_stack_top >= poplen) { 1635 _stack_top -= poplen; 1636 } else { 1637 throw new RuntimeException("stack underflow"); 1638 } 1639 } 1640 pp(CellTypeState[] in, CellTypeState[] out)1641 void pp (CellTypeState[] in, CellTypeState[] out) { 1642 ppop(in); 1643 ppush(out); 1644 } 1645 ppNewRef(CellTypeState[] in, int bci)1646 void ppNewRef (CellTypeState[] in, int bci) { 1647 ppop(in); 1648 ppush1(CellTypeState.makeLineRef(bci)); 1649 } 1650 ppdupswap(int poplen, String out)1651 void ppdupswap (int poplen, String out) { 1652 CellTypeState[] actual = new CellTypeState[5]; 1653 Assert.that(poplen < 5, "this must be less than length of actual vector"); 1654 1655 // pop all arguments 1656 for(int i = 0; i < poplen; i++) actual[i] = pop(); 1657 1658 // put them back 1659 for (int i = 0; i < out.length(); i++) { 1660 char push_ch = out.charAt(i); 1661 int idx = push_ch - '1'; 1662 if (Assert.ASSERTS_ENABLED) { 1663 Assert.that(idx >= 0 && idx < poplen, "wrong arguments"); 1664 } 1665 push(actual[idx]); 1666 } 1667 } 1668 1669 void doLdc (int bci) { 1670 BytecodeLoadConstant ldc = BytecodeLoadConstant.at(_method, bci); 1671 ConstantPool cp = method().getConstants(); 1672 BasicType bt = ldc.resultType(); 1673 CellTypeState cts = (bt == BasicType.T_OBJECT) ? CellTypeState.makeLineRef(bci) : valCTS; 1674 ppush1(cts); 1675 } 1676 1677 void doAstore (int idx) { 1678 CellTypeState r_or_p = pop(); 1679 if (!r_or_p.isAddress() && !r_or_p.isReference()) { 1680 // We actually expected ref or pc, but we only report that we expected a ref. It does not 1681 // really matter (at least for now) 1682 throw new RuntimeException("wrong type on stack (found: " + 1683 r_or_p.toChar() + ", expected: {pr})"); 1684 } 1685 setVar(idx, r_or_p); 1686 } 1687 1688 void doJsr (int targBCI) { 1689 push(CellTypeState.makeAddr(targBCI)); 1690 } 1691 1692 void doField (boolean is_get, boolean is_static, int idx, int bci) { 1693 // Dig up signature for field in constant pool 1694 ConstantPool cp = method().getConstants(); 1695 int nameAndTypeIdx = cp.getNameAndTypeRefIndexAt(idx); 1696 int signatureIdx = cp.getSignatureRefIndexAt(nameAndTypeIdx); 1697 Symbol signature = cp.getSymbolAt(signatureIdx); 1698 1699 if (DEBUG) { 1700 System.err.println("doField: signature = " + signature.asString() + ", idx = " + idx + 1701 ", nameAndTypeIdx = " + nameAndTypeIdx + ", signatureIdx = " + signatureIdx + ", bci = " + bci); 1702 } 1703 1704 // Parse signature (espcially simple for fields) 1705 // The signature is UFT8 encoded, but the first char is always ASCII for signatures. 1706 char sigch = (char) signature.getByteAt(0); 1707 CellTypeState[] temp = new CellTypeState[4]; 1708 CellTypeState[] eff = sigcharToEffect(sigch, bci, temp); 1709 1710 CellTypeState[] in = new CellTypeState[4]; 1711 CellTypeState[] out; 1712 int i = 0; 1713 1714 if (is_get) { 1715 out = eff; 1716 } else { 1717 out = epsilonCTS; 1718 i = copyCTS(in, eff); 1719 } 1720 if (!is_static) in[i++] = CellTypeState.ref; 1721 in[i] = CellTypeState.bottom; 1722 if (Assert.ASSERTS_ENABLED) { 1723 Assert.that(i<=3, "sanity check"); 1724 } 1725 pp(in, out); 1726 } 1727 1728 void doMethod (boolean is_static, boolean is_interface, int idx, int bci) { 1729 // Dig up signature for field in constant pool 1730 ConstantPool cp = _method.getConstants(); 1731 Symbol signature = cp.getSignatureRefAt(idx); 1732 1733 // Parse method signature 1734 CellTypeStateList out = new CellTypeStateList(4); 1735 CellTypeStateList in = new CellTypeStateList(MAXARGSIZE+1); // Includes result 1736 ComputeCallStack cse = new ComputeCallStack(signature); 1737 1738 // Compute return type 1739 int res_length = cse.computeForReturntype(out); 1740 1741 // Temporary hack. 1742 if (out.get(0).equal(CellTypeState.ref) && out.get(1).equal(CellTypeState.bottom)) { 1743 out.get(0).set(CellTypeState.makeLineRef(bci)); 1744 } 1745 1746 if (Assert.ASSERTS_ENABLED) { 1747 Assert.that(res_length<=4, "max value should be vv"); 1748 } 1749 1750 // Compute arguments 1751 int arg_length = cse.computeForParameters(is_static, in); 1752 if (Assert.ASSERTS_ENABLED) { 1753 Assert.that(arg_length<=MAXARGSIZE, "too many locals"); 1754 } 1755 1756 // Pop arguments 1757 for (int i = arg_length - 1; i >= 0; i--) ppop1(in.get(i));// Do args in reverse order. 1758 1759 // Report results 1760 if (_report_result_for_send == true) { 1761 fillStackmapForOpcodes(_itr_send, vars(), stack(), _stack_top); 1762 _report_result_for_send = false; 1763 } 1764 1765 // Push return address 1766 ppush(out); 1767 } 1768 1769 void doMultianewarray (int dims, int bci) { 1770 if (Assert.ASSERTS_ENABLED) { 1771 Assert.that(dims >= 1, "sanity check"); 1772 } 1773 for(int i = dims -1; i >=0; i--) { 1774 ppop1(valCTS); 1775 } 1776 ppush1(CellTypeState.makeLineRef(bci)); 1777 } 1778 1779 void doMonitorenter (int bci) { 1780 CellTypeState actual = pop(); 1781 if (_monitor_top == bad_monitors) { 1782 return; 1783 } 1784 1785 // Bail out when we get repeated locks on an identical monitor. This case 1786 // isn't too hard to handle and can be made to work if supporting nested 1787 // redundant synchronized statements becomes a priority. 1788 // 1789 // See also "Note" in do_monitorexit(), below. 1790 if (actual.isLockReference()) { 1791 _monitor_top = bad_monitors; 1792 _monitor_safe = false; 1793 1794 if (TraceMonitorMismatch) { 1795 reportMonitorMismatch("nested redundant lock -- bailout..."); 1796 } 1797 return; 1798 } 1799 1800 CellTypeState lock = CellTypeState.makeLockRef(bci); 1801 checkType(refCTS, actual); 1802 if (!actual.isInfoTop()) { 1803 replaceAllCTSMatches(actual, lock); 1804 monitorPush(lock); 1805 } 1806 } 1807 1808 void doMonitorexit (int bci) { 1809 CellTypeState actual = pop(); 1810 if (_monitor_top == bad_monitors) { 1811 return; 1812 } 1813 checkType(refCTS, actual); 1814 CellTypeState expected = monitorPop(); 1815 if (!actual.isLockReference() || !expected.equal(actual)) { 1816 // The monitor we are exiting is not verifiably the one 1817 // on the top of our monitor stack. This causes a monitor 1818 // mismatch. 1819 _monitor_top = bad_monitors; 1820 _monitor_safe = false; 1821 1822 // We need to mark this basic block as changed so that 1823 // this monitorexit will be visited again. We need to 1824 // do this to ensure that we have accounted for the 1825 // possibility that this bytecode will throw an 1826 // exception. 1827 BasicBlock bb = getBasicBlockContaining(bci); 1828 bb.setChanged(true); 1829 bb._monitor_top = bad_monitors; 1830 1831 if (TraceMonitorMismatch) { 1832 reportMonitorMismatch("improper monitor pair"); 1833 } 1834 } else { 1835 // This code is a fix for the case where we have repeated 1836 // locking of the same object in straightline code. We clear 1837 // out the lock when it is popped from the monitor stack 1838 // and replace it with an unobtrusive reference value that can 1839 // be locked again. 1840 // 1841 // Note: when generateOopMap is fixed to properly handle repeated, 1842 // nested, redundant locks on the same object, then this 1843 // fix will need to be removed at that time. 1844 replaceAllCTSMatches(actual, CellTypeState.makeLineRef(bci)); 1845 } 1846 1847 if (_report_for_exit_bci == bci) { 1848 _matching_enter_bci = expected.getMonitorSource(); 1849 } 1850 } 1851 1852 void doReturnMonitorCheck () { 1853 if (_monitor_top > 0) { 1854 // The monitor stack must be empty when we leave the method 1855 // for the monitors to be properly matched. 1856 _monitor_safe = false; 1857 1858 // Since there are no successors to the *return bytecode, it 1859 // isn't necessary to set _monitor_top to bad_monitors. 1860 1861 if (TraceMonitorMismatch) { 1862 reportMonitorMismatch("non-empty monitor stack at return"); 1863 } 1864 } 1865 } 1866 1867 void doCheckcast () { 1868 CellTypeState actual = pop(); 1869 checkType(refCTS, actual); 1870 push(actual); 1871 } 1872 1873 CellTypeState[] sigcharToEffect (char sigch, int bci, CellTypeState[] out) { 1874 // Object and array 1875 if (sigch=='L' || sigch=='[') { 1876 out[0] = CellTypeState.makeLineRef(bci); 1877 out[1] = CellTypeState.bottom; 1878 return out; 1879 } 1880 if (sigch == 'J' || sigch == 'D' ) return vvCTS; // Long and Double 1881 if (sigch == 'V' ) return epsilonCTS; // Void 1882 return vCTS; // Otherwise 1883 } 1884 1885 // Copies (optionally bottom/zero terminated) CTS string from "src" into "dst". 1886 // Does NOT terminate with a bottom. Returns the number of cells copied. 1887 int copyCTS (CellTypeState[] dst, CellTypeState[] src) { 1888 int idx = 0; 1889 for (; idx < src.length && !src[idx].isBottom(); idx++) { 1890 dst[idx] = src[idx]; 1891 } 1892 return idx; 1893 } 1894 1895 // Create result set 1896 boolean _report_result; 1897 boolean _report_result_for_send; // Unfortunatly, stackmaps for sends are special, so we need some extra 1898 BytecodeStream _itr_send; // variables to handle them properly. 1899 1900 void reportResult () { 1901 // if (TraceNewOopMapGeneration) tty.print_cr("Report result pass"); 1902 1903 // We now want to report the result of the parse 1904 _report_result = true; 1905 1906 // Prolog code 1907 fillStackmapProlog(_gc_points); 1908 1909 // Mark everything changed, then do one interpretation pass. 1910 for (int i = 0; i<_bb_count; i++) { 1911 if (_basic_blocks[i].isReachable()) { 1912 _basic_blocks[i].setChanged(true); 1913 interpBB(_basic_blocks[i]); 1914 } 1915 } 1916 1917 // Note: Since we are skipping dead-code when we are reporting results, then 1918 // the no. of encountered gc-points might be fewer than the previously number 1919 // we have counted. (dead-code is a pain - it should be removed before we get here) 1920 fillStackmapEpilog(); 1921 1922 // Report initvars 1923 fillInitVars(_init_vars); 1924 1925 _report_result = false; 1926 } 1927 1928 // Initvars 1929 List/*<Integer>*/ _init_vars; 1930 1931 void initializeVars () { 1932 for (int k = 0; k < _init_vars.size(); k++) 1933 _state.get(((Integer) _init_vars.get(k)).intValue()).set(CellTypeState.makeSlotRef(k)); 1934 } 1935 1936 void addToRefInitSet (int localNo) { 1937 // if (TraceNewOopMapGeneration) 1938 // tty.print_cr("Added init vars: %d", localNo); 1939 1940 Integer local = new Integer(localNo); 1941 1942 // Is it already in the set? 1943 if (_init_vars.contains(local)) 1944 return; 1945 1946 _init_vars.add(local); 1947 } 1948 1949 // Conflicts rewrite logic 1950 boolean _conflict; // True, if a conflict occured during interpretation 1951 int _nof_refval_conflicts; // No. of conflicts that require rewrites 1952 int[] _new_var_map; 1953 1954 void recordRefvalConflict (int varNo) { 1955 if (Assert.ASSERTS_ENABLED) { 1956 Assert.that(varNo>=0 && varNo< _max_locals, "index out of range"); 1957 } 1958 1959 if (TraceOopMapRewrites) { 1960 System.err.println("### Conflict detected (local no: " + varNo + ")"); 1961 } 1962 1963 if (_new_var_map == null) { 1964 _new_var_map = new int[_max_locals]; 1965 for (int k = 0; k < _max_locals; k++) _new_var_map[k] = k; 1966 } 1967 1968 if ( _new_var_map[varNo] == varNo) { 1969 // Check if max. number of locals has been reached 1970 if (_max_locals + _nof_refval_conflicts >= MAX_LOCAL_VARS) { 1971 throw new RuntimeException("Rewriting exceeded local variable limit"); 1972 } 1973 _new_var_map[varNo] = _max_locals + _nof_refval_conflicts; 1974 _nof_refval_conflicts++; 1975 } 1976 } 1977 1978 void rewriteRefvalConflicts () { 1979 if (_nof_refval_conflicts > 0) { 1980 if (VM.getVM().isDebugging()) { 1981 throw new RuntimeException("Should not reach here (method rewriting should have been done by the VM already)"); 1982 } else { 1983 throw new RuntimeException("Method rewriting not yet implemented in Java"); 1984 } 1985 } 1986 } 1987 // Rewriting-related routines are not needed here 1988 // void rewrite_refval_conflict (int from, int to); 1989 // bool rewrite_refval_conflict_inst (BytecodeStream *i, int from, int to); 1990 // bool rewrite_load_or_store (BytecodeStream *i, Bytecodes.Code bc, Bytecodes.Code bc0, unsigned int varNo); 1991 1992 // bool expand_current_instr (int bci, int ilen, int newIlen, u_char inst_buffer[]); 1993 // bool is_astore (BytecodeStream *itr, int *index); 1994 // bool is_aload (BytecodeStream *itr, int *index); 1995 1996 // List of bci's where a return address is on top of the stack 1997 // GrowableArray<intptr_t> *_ret_adr_tos; 1998 1999 // bool stack_top_holds_ret_addr (int bci); 2000 // void compute_ret_adr_at_TOS (); 2001 // void update_ret_adr_at_TOS (int bci, int delta); 2002 2003 String stateVecToString (CellTypeStateList vec, int len) { 2004 for (int i = 0; i < len; i++) { 2005 _state_vec_buf[i] = vec.get(i).toChar(); 2006 } 2007 return new String(_state_vec_buf, 0, len); 2008 } 2009 2010 // Helper method. Can be used in subclasses to fx. calculate gc_points. If the current instuction 2011 // is a control transfer, then calls the jmpFct all possible destinations. 2012 void retJumpTargetsDo (BytecodeStream bcs, JumpClosure closure, int varNo, int[] data) { 2013 CellTypeState ra = vars().get(varNo); 2014 if (!ra.isGoodAddress()) { 2015 throw new RuntimeException("ret returns from two jsr subroutines?"); 2016 } 2017 int target = ra.getInfo(); 2018 2019 RetTableEntry rtEnt = _rt.findJsrsForTarget(target); 2020 int bci = bcs.bci(); 2021 for (int i = 0; i < rtEnt.nofJsrs(); i++) { 2022 int target_bci = rtEnt.jsrs(i); 2023 // Make sure a jrtRet does not set the changed bit for dead basicblock. 2024 BasicBlock jsr_bb = getBasicBlockContaining(target_bci - 1); 2025 if (Assert.ASSERTS_ENABLED) { 2026 BasicBlock target_bb = _basic_blocks[1 + bbIndex(jsr_bb)]; 2027 Assert.that(target_bb == getBasicBlockAt(target_bci), "wrong calc. of successor basicblock"); 2028 } 2029 boolean alive = jsr_bb.isAlive(); 2030 // if (TraceNewOopMapGeneration) { 2031 // tty.print("pc = %d, ret . %d alive: %s\n", bci, target_bci, alive ? "true" : "false"); 2032 // } 2033 if (alive) { 2034 closure.process(this, target_bci, data); 2035 } 2036 } 2037 } 2038 2039 /** If the current instruction in "c" has no effect on control flow, 2040 returns "true". Otherwise, calls "closure.process()" one or 2041 more times, with "c", an appropriate "pcDelta", and "data" as 2042 arguments, then returns "false". There is one exception: if the 2043 current instruction is a "ret", returns "false" without calling 2044 "jmpFct". Arrangements for tracking the control flow of a "ret" 2045 must be made externally. */ 2046 boolean jumpTargetsDo (BytecodeStream bcs, JumpClosure closure, int[] data) { 2047 int bci = bcs.bci(); 2048 2049 switch (bcs.code()) { 2050 case Bytecodes._ifeq: 2051 case Bytecodes._ifne: 2052 case Bytecodes._iflt: 2053 case Bytecodes._ifge: 2054 case Bytecodes._ifgt: 2055 case Bytecodes._ifle: 2056 case Bytecodes._if_icmpeq: 2057 case Bytecodes._if_icmpne: 2058 case Bytecodes._if_icmplt: 2059 case Bytecodes._if_icmpge: 2060 case Bytecodes._if_icmpgt: 2061 case Bytecodes._if_icmple: 2062 case Bytecodes._if_acmpeq: 2063 case Bytecodes._if_acmpne: 2064 case Bytecodes._ifnull: 2065 case Bytecodes._ifnonnull: 2066 closure.process(this, bcs.dest(), data); 2067 closure.process(this, bci + 3, data); 2068 break; 2069 2070 case Bytecodes._goto: 2071 closure.process(this, bcs.dest(), data); 2072 break; 2073 case Bytecodes._goto_w: 2074 closure.process(this, bcs.dest_w(), data); 2075 break; 2076 case Bytecodes._tableswitch: 2077 { 2078 BytecodeTableswitch tableswitch = BytecodeTableswitch.at(bcs); 2079 int len = tableswitch.length(); 2080 2081 closure.process(this, bci + tableswitch.defaultOffset(), data); /* Default. jump address */ 2082 while (--len >= 0) { 2083 closure.process(this, bci + tableswitch.destOffsetAt(len), data); 2084 } 2085 break; 2086 } 2087 2088 case Bytecodes._fast_linearswitch: // Java opcodes 2089 case Bytecodes._fast_binaryswitch: // get_int_table handles conversions 2090 case Bytecodes._lookupswitch: 2091 { 2092 BytecodeLookupswitch lookupswitch = BytecodeLookupswitch.at(bcs); 2093 int npairs = lookupswitch.numberOfPairs(); 2094 closure.process(this, bci + lookupswitch.defaultOffset(), data); /* Default. */ 2095 while(--npairs >= 0) { 2096 LookupswitchPair pair = lookupswitch.pairAt(npairs); 2097 closure.process(this, bci + pair.offset(), data); 2098 } 2099 break; 2100 } 2101 case Bytecodes._jsr: 2102 Assert.that(bcs.isWide()==false, "sanity check"); 2103 closure.process(this, bcs.dest(), data); 2104 break; 2105 case Bytecodes._jsr_w: 2106 closure.process(this, bcs.dest_w(), data); 2107 break; 2108 case Bytecodes._wide: 2109 throw new RuntimeException("Should not reach here"); 2110 case Bytecodes._athrow: 2111 case Bytecodes._ireturn: 2112 case Bytecodes._lreturn: 2113 case Bytecodes._freturn: 2114 case Bytecodes._dreturn: 2115 case Bytecodes._areturn: 2116 case Bytecodes._return: 2117 case Bytecodes._ret: 2118 break; 2119 default: 2120 return true; 2121 } 2122 return false; 2123 } 2124 2125 // Monitor matching 2126 // int fill_out_arrays (int *enter, int *exit, int max); 2127 2128 // friend class RelocCallback; 2129 2130 //---------------------------------------------------------------------- 2131 // Public routines for GenerateOopMap 2132 // 2133 public GenerateOopMap(Method method) { 2134 // We have to initialize all variables here, that can be queried direcly 2135 _method = method; 2136 _max_locals=0; 2137 _init_vars = null; 2138 _rt = new RetTable(); 2139 } 2140 2141 2142 // Compute the map. 2143 public void computeMap() { 2144 if (DEBUG) { 2145 System.err.println("*** GenerateOopMap: computing for " + 2146 method().getMethodHolder().getName().asString() + "." + 2147 method().getName().asString() + 2148 method().getSignature().asString()); 2149 } 2150 2151 // Initialize values 2152 _got_error = false; 2153 _conflict = false; 2154 _max_locals = (int) method().getMaxLocals(); 2155 _max_stack = (int) method().getMaxStack(); 2156 _has_exceptions = (method().hasExceptionTable()); 2157 _nof_refval_conflicts = 0; 2158 _init_vars = new ArrayList(5); // There are seldom more than 5 init_vars 2159 _report_result = false; 2160 _report_result_for_send = false; 2161 _report_for_exit_bci = -1; 2162 _new_var_map = null; 2163 // _ret_adr_tos = new GrowableArray<intptr_t>(5); // 5 seems like a good number; 2164 // _did_rewriting = false; 2165 // _did_relocation = false; 2166 2167 // FIXME: remove 2168 /* 2169 if (TraceNewOopMapGeneration) { 2170 tty.print("Method name: %s\n", method().name().as_C_string()); 2171 if (Verbose) { 2172 _method.print_codes(); 2173 tty.print_cr("Exception table:"); 2174 typeArrayOop excps = method().exception_table(); 2175 for(int i = 0; i < excps.length(); i += 4) { 2176 tty.print_cr("[%d - %d] . %d", excps.int_at(i + 0), excps.int_at(i + 1), excps.int_at(i + 2)); 2177 } 2178 } 2179 } 2180 */ 2181 2182 // if no code - do nothing 2183 // compiler needs info 2184 if (method().getCodeSize() == 0 || _max_locals + method().getMaxStack() == 0) { 2185 fillStackmapProlog(0); 2186 fillStackmapEpilog(); 2187 return; 2188 } 2189 // Step 1: Compute all jump targets and their return value 2190 if (!_got_error) 2191 _rt.computeRetTable(_method); 2192 2193 // Step 2: Find all basic blocks and count GC points 2194 if (!_got_error) 2195 markBBHeadersAndCountGCPoints(); 2196 2197 // Step 3: Calculate stack maps 2198 if (!_got_error) 2199 doInterpretation(); 2200 2201 // Step 4:Return results 2202 if (!_got_error && reportResults()) 2203 reportResult(); 2204 2205 if (_got_error) { 2206 // We could expand this code to throw somekind of exception (e.g., VerifyException). However, 2207 // an exception thrown in this part of the code is likly to mean that we are executing some 2208 // illegal bytecodes (that the verifier should have caught if turned on), so we will just exit 2209 // with a fatal. 2210 throw new RuntimeException("Illegal bytecode sequence encountered while generating interpreter pointer maps - method should be rejected by verifier."); 2211 } 2212 } 2213 2214 // Do a callback on fill_stackmap_for_opcodes for basicblock containing bci 2215 public void resultForBasicblock(int bci) { 2216 // FIXME: remove 2217 // if (TraceNewOopMapGeneration) tty.print_cr("Report result pass for basicblock"); 2218 2219 // We now want to report the result of the parse 2220 _report_result = true; 2221 2222 // Find basicblock and report results 2223 BasicBlock bb = getBasicBlockContaining(bci); 2224 if (Assert.ASSERTS_ENABLED) { 2225 Assert.that(bb.isReachable(), "getting result from unreachable basicblock"); 2226 } 2227 bb.setChanged(true); 2228 interpBB(bb); 2229 } 2230 2231 // Query 2232 public int maxLocals() { return _max_locals; } 2233 public Method method() { return _method; } 2234 2235 // bool did_rewriting() { return _did_rewriting; } 2236 // bool did_relocation() { return _did_relocation; } 2237 2238 // static void print_time(); 2239 2240 // Monitor query 2241 public boolean monitorSafe() { return _monitor_safe; } 2242 // Takes as input the bci of a monitorexit bytecode. 2243 // Returns the bci of the corresponding monitorenter. 2244 // Can only be called safely after computeMap() is run. 2245 public int getMonitorMatch(int bci) { 2246 if (Assert.ASSERTS_ENABLED) { 2247 Assert.that(_monitor_safe, "Attempt to match monitor in broken code."); 2248 } 2249 2250 // if (TraceNewOopMapGeneration) 2251 // tty.print_cr("Report monitor match for bci : %d", bci); 2252 2253 // We want to report the line number of the monitorenter. 2254 _report_for_exit_bci = bci; 2255 _matching_enter_bci = -1; 2256 2257 // Find basicblock and report results 2258 BasicBlock bb = getBasicBlockContaining(bci); 2259 if (bb.isReachable()) { 2260 bb.setChanged(true); 2261 interpBB(bb); 2262 _report_for_exit_bci = -1; 2263 if (Assert.ASSERTS_ENABLED) { 2264 Assert.that(_matching_enter_bci != -1, "monitor matching invariant"); 2265 } 2266 } 2267 return _matching_enter_bci; 2268 } 2269 2270 // Returns a Arena allocated object that contains pairing info. 2271 // MonitorPairs* get_pairing(Arena *arena); 2272 2273 // copies monitor pairing info into area; area_count specifies maximum 2274 // possible number of monitor pairs 2275 // int copy_pairing(int pair_count, MonitorPairs* pairs); 2276 2277 private int bbIndex(BasicBlock bb) { 2278 for (int i = 0; i < _basic_blocks.length; i++) { 2279 if (_basic_blocks[i] == bb) { 2280 return i; 2281 } 2282 } 2283 throw new RuntimeException("Should have found block"); 2284 } 2285 2286 //---------------------------------------------------------------------- 2287 // Specialization methods. Intended use: 2288 // - possibleGCPoint must return true for every bci for which the 2289 // stackmaps must be returned 2290 // - fillStackmapProlog is called just before the result is 2291 // reported. The arguments tells the estimated number of gc points 2292 // - fillStackmapForOpcodes is called once for each bytecode index 2293 // in order (0...code_length-1) 2294 // - fillStackmapEpilog is called after all results has been 2295 // reported. Note: Since the algorithm does not report stackmaps for 2296 // deadcode, fewer gc_points might have been encounted than assumed 2297 // during the epilog. It is the responsibility of the subclass to 2298 // count the correct number. 2299 // - fillInitVars are called once with the result of the init_vars 2300 // computation 2301 // 2302 // All these methods are used during a call to computeMap. Note: 2303 // None of the return results are valid after computeMap returns, 2304 // since all values are allocated as resource objects. 2305 // 2306 // All virtual method must be implemented in subclasses 2307 public boolean allowRewrites () { return false; } 2308 public boolean reportResults () { return true; } 2309 public boolean reportInitVars () { return true; } 2310 public boolean possibleGCPoint (BytecodeStream bcs) { throw new RuntimeException("ShouldNotReachHere"); } 2311 public void fillStackmapProlog (int nofGCPoints) { throw new RuntimeException("ShouldNotReachHere"); } 2312 public void fillStackmapEpilog () { throw new RuntimeException("ShouldNotReachHere"); } 2313 public void fillStackmapForOpcodes (BytecodeStream bcs, 2314 CellTypeStateList vars, 2315 CellTypeStateList stack, 2316 int stackTop) { throw new RuntimeException("ShouldNotReachHere"); } 2317 public void fillInitVars (List/*<Integer>*/ init_vars) { throw new RuntimeException("ShouldNotReachHere"); } 2318 } 2319