generateOopMap.cpp revision 1409
844N/A * Copyright 1997-2009 Sun Microsystems, Inc. All Rights Reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 0N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 0N/A * CA 95054 USA or visit www.sun.com if you need additional information or 0N/A * have any questions. 0N/A// Compute stack layouts for each instruction in method. 0N/A// - What to do about jsr with different types of local vars? 0N/A// Need maps that are conditional on jsr path? 0N/A// - Jsr and exceptions should be done more efficiently (the retAddr stuff) 0N/A// - Could extend verifier to provide this information. 0N/A// For: one fewer abstract interpreter to maintain. Against: the verifier 0N/A// solves a bigger problem so slower (undesirable to force verification of 0N/A// Partition bytecodes into basic blocks 0N/A// For each basic block: store entry state (vars, stack). For instructions 0N/A// inside basic blocks we do not store any state (instead we recompute it 0N/A// from state produced by previous instruction). 0N/A// Perform abstract interpretation of bytecodes over this lattice: 0N/A// '#' top, result of conflict merge 0N/A// 'r' reference type 0N/A// ' ' uninitialized; never occurs on operand stack in Java 0N/A// Basic block headers are the only merge points. We use this iteration to 0N/A// compute the information: 0N/A// find basic blocks; 0N/A// initialize them with uninitialized state; 0N/A// initialize first BB according to method signature; 0N/A// mark first BB changed 0N/A// while (some BB is changed) do { 0N/A// perform abstract interpration of all bytecodes in BB; 0N/A// merge exit state of BB into entry state of all successor BBs, 0N/A// noting if any of these change; 0N/A// One additional complication is necessary. The jsr instruction pushes 0N/A// a return PC on the stack (a 'p' type in the abstract interpretation). 0N/A// To be able to process "ret" bytecodes, we keep track of these return 0N/A// PC's in a 'retAddrs' structure in abstract interpreter context (when 0N/A// processing a "ret" bytecodes, it is not sufficient to know that it gets 0N/A// an argument of the right type 'p'; we need to know which address it 0N/A// (Note this comment is borrowed form the original author of the algorithm) 0N/A#
include "incls/_precompiled.incl" 0N/A// Specialization of SignatureIterator - compute the effects of a call 0N/A//========================================================================================= 0N/A// Specialization of SignatureIterator - in order to set up first stack frame 0N/A//===================================================================================== 0N/A// Contains function to itereate through all bytecodes 0N/A// and find all return entry points 0N/A // Scan table for entry 0N/A // Allocate new entry and put in list 0N/A // Now "entry" is set. Make sure that the entry is initialized 0N/A // and has room for the new jsr. 0N/A// The instruction at bci is changing size by "delta". Update the return map. 0N/A// Commonly used constants 0N/A return '#';
// Conflict that needs to be rewritten 0N/A// Print a detailed CellTypeState. Indicate all bits that are set. If 0N/A// the CellTypeState represents an address or a reference, print the 0N/A// value of the additional information. 0N/A // Not a monitor lock reference. 0N/A// Basicblock handling methods 0N/A // First mark all exception handlers as start of a basic-block 0N/A // Then iterate through the code 0N/A /* We will also mark successors of jsr's as basic block headers. */ 0N/A *
data =
1;
// Mark basicblock as changed 0N/A int change =
1;
// int to get function pointers to work 0N/A // Mark entry basic block as alive and all exception handlers 0N/A // If block is not already alive (due to multiple exception handlers to same bb), then 0N/A // Iterate through all basic blocks until we reach a fixpoint 0N/A // Position bytecodestream at last bytecode in basicblock 0N/A // We will also mark successors of jsr's as alive. 0N/A // Mark successor as alive 0N/A/* If the current instruction in "c" has no effect on control flow, 0N/A returns "true". Otherwise, calls "jmpFct" one or more times, with 0N/A "c", an appropriate "pcDelta", and "data" as arguments, then 0N/A returns "false". There is one exception: if the current 0N/A instruction is a "ret", returns "false" without calling "jmpFct". 0N/A Arrangements for tracking the control flow of a "ret" must be made 0N/A/* Requires "pc" to be the head of a basic block; returns that basic 0N/A// Requires "pc" to be the start of an instruction; returns the basic 0N/A// block containing that instruction. */ 0N/A// CellType handling methods 0N/A// Return result of merging cts1 and cts2. 0N/A "merge of bottom values is handled elsewhere");
0N/A // If the top bit is set, we don't need to do any more work. 0N/A "only addresses and references have non-top info");
0N/A // The two values being merged are different. Raise to top. 0N/A// Merge the variable state for locals and stack from cts into bbts. 0N/A for (i =
len -
1; i >= 0; i--) {
0N/A// Merge the monitor stack state from cts into bbts. 0N/A // If there are no monitors in the program, or there has been 0N/A // a monitor matching error before this point in the program, 0N/A // then we do not merge in the monitor state. 0N/A // Can we prove that, when there has been a change, it will already 0N/A // have been detected at this point? That would make this equal 0N/A // check here unnecessary. 0N/A for (
int i = 0; i <
len; i++) {
0N/A// Merge the states for the current block and the next. As long as a 0N/A// block is reachable the locals and stack must be merged. If the 0N/A// stack heights don't match then this is a verification error and 0N/A// it's impossible to interpret the code. Simultaneously monitor 0N/A// states are being check to see if they nest statically. If monitor 0N/A// depths match up then their states are merged. Otherwise the 0N/A// mismatch is simply recorded and interpretation continues since 0N/A// monitor matching is purely informational and doesn't say anything 0N/A// about the correctness of the code. 0N/A // always merge local state even if monitors don't match. 0N/A // monitors still match so continue merging monitor states. 0N/A // When the monitor stacks are not matched, we set _monitor_top to 0N/A // bad_monitors. This signals that, from here on, the monitor stack cannot 0N/A // be trusted. In particular, monitorexit bytecodes may throw 0N/A // exceptions. We mark this block as changed so that the change 0N/A // propagates properly. 0N/A // First time we look at this BB 0N/A "wrong celltypestate");
0N/A // We have detected a pop of an empty monitor stack. 0N/A // Some monitorenter is being executed more than once. 0N/A // This means that the monitor stack cannot be simulated. 0N/A// Interpretation handling methods 0N/A // "i" is just for debugging, so we can detect cases where this loop is 0N/A // iterated more than once. 0N/A tty->
print(
"\n\nIteration #%d of do_interpretation loop, method:\n", i);
0N/A // init_state is now called from init_basic_blocks. The length of a 0N/A // state vector cannot be determined until we have made a pass through 0N/A // the bytecodes counting the possible monitor entries. 0N/A // Note: Could consider reserving only the needed space for each BB's state 0N/A // (entry stack may not be of maximal height for every basic block). 0N/A // But cumbersome since we don't know the stack heights yet. (Nor the 0N/A // monitor stack heights...) 0N/A // Make a pass through the bytecodes. Count the number of monitorenters. 0N/A // This can be used an upper bound on the monitor stack depth in programs 0N/A // which obey stack discipline with their monitor usage. Initialize the 0N/A // known information about basic blocks. 0N/A // Initialize the basicblock structure 0N/A // Remember prevous bci. 342N/A // Check that the correct number of basicblocks was found 0N/A // Now that we have a bound on the depth of the monitor stack, we can 0N/A // initialize the CellTypeState-related information. 0N/A // We allocate space for all state-vectors for all basicblocks in one huge chuck. 0N/A // Then in the next part of the code, we set a pointer in each _basic_block that 0N/A // points to each piece. 0N/A // Make a pass over the basicblocks and assign their state vectors. 0N/A // Mark all alive blocks 0N/A // Initialize all locals to 'uninit' and set stack-height to 0 0N/A // Initialize CellState type of arguments 0N/A // If some references must be pre-assigned to null, then set that up 0N/A // This is the start state 0N/A// The instruction at bci is changing size by "delta". Update the basic blocks. 0N/A "new method size is too small");
0N/A // Is it already in the set? 0N/A// Interpreration code 0N/A // We do not want to do anything in case the basic-block has not been initialized. This 0N/A // will happen in the case where there is dead-code hang around in a method. 0N/A // Set iterator interval to be the current basicblock 0N/A // Iterates through all bytecodes except the last in a basic block. 0N/A // We handle the last one special, since there is controlflow change. 0N/A // We do not need to interpret the results of exceptional 0N/A // continuation from this instruction when the method has no 0N/A // exception handlers and the monitor stack is currently 0N/A // Handle last instruction. 0N/A // Automatically handles 'wide' ret indicies 0N/A // Hit end of BB, but the instr. was a fall-through instruction, 0N/A // so perform transition as if the BB ended in a "jump". 0N/A // Only check exception edge, if bytecode can trap 0N/A // These bytecodes can trap for rewriting. We need to assume that 0N/A // they do not throw exceptions to make the monitor analysis work. 0N/A // If the monitor stack height is not zero when we leave the method, 0N/A // then we are either exiting with a non-empty stack or we have 0N/A // found monitor trouble earlier in our analysis. In either case, 0N/A // assume an exception could be taken here. 0N/A // If the monitor stack height is bad_monitors, then we have detected a 0N/A // monitor matching problem earlier in the analysis. If the 0N/A // monitor stack height is 0, we are about to pop a monitor 0N/A // off of an empty stack. In either case, the bytecode 0N/A // could throw an exception. 0N/A // Exception stacks are always the same. 0N/A // We remembered the size and first element of "cOpStck" 0N/A // above; now we temporarily set them to the appropriate 0N/A // values for an exception handler. */ 0N/A // Now undo the temporary change. 0N/A // If this is a "catch all" handler, then we do not need to 0N/A // consider any additional handlers. 0N/A // It is possible that none of the exception handlers would have caught 0N/A // the exception. In this case, we will exit the method. We must 0N/A // ensure that the monitor stack is empty in this case. 0N/A // We pessimistically assume that this exception can escape the 0N/A // method. (It is possible that it will always be caught, but 0N/A // we don't care to analyse the types of the catch clauses.) 0N/A // We don't set _monitor_top to bad_monitors because there are no successors 0N/A // to this exceptional exit. 0N/A // We check _monitor_safe so that we only report the first mismatched 0N/A // exceptional exit. 0N/A for (
int i = 0; i <
num; i++) {
0N/A// Print the state values at the current bytecode. 0N/A// Sets the current state to be the state after executing the 0N/A// current instruction, starting in the current state. 0N/A // Should we report the results? Result is reported *before* the instruction at the current bci is executed. 0N/A // However, not for calls. For calls we do not want to include the arguments, so we postpone the reporting until 0N/A // they have been popped (in method ppl). 0N/A // abstract interpretation of current opcode 0N/A // vlh(apple): do_exception_edge() does not get 0N/A // called if method has no exception handlers 0N/A "can only load refs. and values.");
0N/A // We were asked to push a reference, but the type of the 0N/A // variable can be something else 0N/A // It is a ref-uninit conflict (at least). If there are other 0N/A // problems, we'll get them in the next round 0N/A // It wasn't a ref-uninit conflict. So must be a 0N/A // ref-val or ref-pc conflict. Split the variable. 0N/A // Otherwise it is a conflict, but one that verification would 0N/A // have caught if illegal. In particular, it can't be a topCTS 0N/A // resulting from mergeing two difference pcCTS's since the verifier 0N/A // would have rejected any use of such a merge. 0N/A // pop all arguments 0N/A// Replace all occurences of the state 'match' with the state 'replace' 0N/A// in our current state vector. 0N/A for (i =
len -
1; i >= 0; i--) {
0N/A // Bail out when we get repeated locks on an identical monitor. This case 0N/A // isn't too hard to handle and can be made to work if supporting nested 0N/A // redundant synchronized statements becomes a priority. 0N/A // See also "Note" in do_monitorexit(), below. 0N/A // The monitor we are exiting is not verifiably the one 0N/A // on the top of our monitor stack. This causes a monitor 0N/A // We need to mark this basic block as changed so that 0N/A // this monitorexit will be visited again. We need to 0N/A // do this to ensure that we have accounted for the 0N/A // possibility that this bytecode will throw an 0N/A // This code is a fix for the case where we have repeated 0N/A // locking of the same object in straightline code. We clear 0N/A // out the lock when it is popped from the monitor stack 0N/A // and replace it with an unobtrusive reference value that can 0N/A // Note: when generateOopMap is fixed to properly handle repeated, 0N/A // nested, redundant locks on the same object, then this 0N/A // fix will need to be removed at that time. 0N/A // The monitor stack must be empty when we leave the method 0N/A // for the monitors to be properly matched. 0N/A // Since there are no successors to the *return bytecode, it 0N/A // isn't necessary to set _monitor_top to bad_monitors. 0N/A // We actually expected ref or pc, but we only report that we expected a ref. It does not 0N/A // really matter (at least for now) 0N/A// Copies bottom/zero terminated CTS string from "src" into "dst". 0N/A// Does NOT terminate with a bottom. Returns the number of cells copied. 0N/A // Dig up signature for field in constant pool 0N/A // Parse signature (espcially simple for fields) 0N/A // The signature is UFT8 encoded, but the first char is always ASCII for signatures. 1059N/A // Dig up signature for field in constant pool 0N/A // Parse method signature 0N/A // Compute return type 0N/A // Compute arguments 0N/A // Push return address 0N/A// This is used to parse the signature for fields, since they are very simple... 0N/A// This function assumes "bcs" is at a "ret" instruction and that the vars 0N/A// state is valid for that instruction. Furthermore, the ret instruction 0N/A// must be the last instruction in "bb" (we store information about the 0N/A // Make sure a jrtRet does not set the changed bit for dead basicblock. 0N/A// ============ Main Entry Point =========== 605N/A // We have to initialize all variables here, that can be queried directly 0N/A // If we are doing a detailed trace, include the regular trace information. 0N/A // Initialize values 0N/A // if no code - do nothing 0N/A // compiler needs info 0N/A // Step 1: Compute all jump targets and their return value 0N/A // Step 2: Find all basic blocks and count GC points 0N/A // Step 3: Calculate stack maps 0N/A // Step 4:Return results 0N/A// Error handling methods 0N/A// These methods create an exception for the current thread which is thrown 0N/A// at the bottom of the call stack, when it returns to compute_map(). The 0N/A// _got_error flag controls execution. NOT TODO: The VM exception propagation 0N/A// mechanism using TRAPS/CHECKs could be used here instead but it would need 0N/A// to be added as a parameter to every function and checked for every call. 0N/A// The tons of extra code it would generate didn't seem worth the change. 0N/A // Append method name 0N/A // We do not distinguish between different types of errors for verification 0N/A // errors. Let the verifier give a better message. 0N/A const char *
msg =
"Illegal class file encountered. Try running with -Xverify:all";
0N/A// Report result opcodes 0N/A // We now want to report the result of the parse 0N/A // Mark everything changed, then do one interpretation pass. 0N/A // Note: Since we are skipping dead-code when we are reporting results, then 0N/A // the no. of encountered gc-points might be fewer than the previously number 0N/A // we have counted. (dead-code is a pain - it should be removed before we get here) 0N/A // We now want to report the result of the parse 0N/A // Find basicblock and report results 0N/A// Conflict handling code 0N/A // Check if max. number of locals has been reached 0N/A // We can get here two ways: Either a rewrite conflict was detected, or 0N/A // an uninitialize reference was detected. In the second case, we do not 0N/A // do any rewriting, we just want to recompute the reference set with the 0N/A // Check if rewrites are allowed in this parse. 0N/A fatal(
"Rewriting method not allowed at this stage");
0N/A // This following flag is to tempoary supress rewrites. The locals that might conflict will 0N/A // all be set to contain values. This is UNSAFE - however, until the rewriting has been completely 0N/A // tested it is nice to have. 0N/A // Adjust the number of locals 0N/A // Make sure that the BytecodeStream is constructed in the loop, since 0N/A // during rewriting a new method oop is going to be used, and the next time 0N/A // around we want to use that. 0N/A/* If the current instruction is one that uses local variable "from" 0N/A in a ref way, change it to use "to". There's a subtle reason why we 0N/A renumber the ref uses and not the non-ref uses: non-ref uses may be 0N/A 2 slots wide (double, long) which would necessitate keeping track of 0N/A whether we should add one or two variables to the method. If the change 0N/A affected the width of some instruction, returns "TRUE"; otherwise, returns "FALSE". 0N/A Another reason for moving ref's value is for solving (addr, ref) conflicts, which 0N/A// The argument to this method is: 0N/A// bc : Current bytecode 0N/A// bcN : either _aload or _astore 0N/A// bc0 : either _aload_0 or _astore_0 0N/A // Original instruction was wide; keep it wide for simplicity 0N/A // If we need to relocate in order to patch the byte, we 0N/A // do the patching in a temp. buffer, that is passed to the reloc. 0N/A // The patching of the bytecode stream is then done by the Relocator. 0N/A // This is neccesary, since relocating the instruction at a certain bci, might 0N/A // also relocate that instruction, e.g., if a _goto before it gets widen to a _goto_w. 0N/A // Hence, we do not know which bci to patch after relocation. 0N/A // Relocation needed do patching in temp. buffer 0N/A // Patch either directly in methodOop or in temp. buffer 0N/A// Returns true if expanding was succesful. Otherwise, reports an error and 0N/A report_error(
"could not rewrite method - exception occurred or bytecode buffer overflow");
0N/A // Relocator returns a new method oop. 0N/A// Return true iff the top of the operand stack holds a return address at 0N/A// the current instruction 0N/A // Make sure to only check basicblocks that are reachable 0N/A // For each Basic block we check all instructions 0N/A // TDT: should this be is_good_address() ? 0N/A// =================================================================== 0N/A // Tracking and statistics