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