stackmaps.c

来自「This is a resource based on j2me embedde」· C语言 代码 · 共 1,928 行 · 第 1/5 页

/*
 * @(#)stackmaps.c	1.111 06/10/25
 *
 * Copyright  1990-2008 Sun Microsystems, Inc. All Rights Reserved.  
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER  
 *   
 * This program is free software; you can redistribute it and/or  
 * modify it under the terms of the GNU General Public License version  
 * 2 only, as published by the Free Software Foundation.   
 *   
 * This program is distributed in the hope that it will be useful, but  
 * WITHOUT ANY WARRANTY; without even the implied warranty of  
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU  
 * General Public License version 2 for more details (a copy is  
 * included at /legal/license.txt).   
 *   
 * You should have received a copy of the GNU General Public License  
 * version 2 along with this work; if not, write to the Free Software  
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  
 * 02110-1301 USA   
 *   
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa  
 * Clara, CA 95054 or visit www.sun.com if you need additional  
 * information or have any questions. 
 *
 */

#include "javavm/include/defs.h"
#include "javavm/include/objects.h"
#include "javavm/include/classes.h"
#include "javavm/include/interpreter.h"
#include "javavm/include/stacks.h"
#include "javavm/include/bcattr.h"
#include "javavm/include/utils.h"
#include "javavm/include/typeid.h"
#include "javavm/include/opcodes.h"
#include "javavm/include/globals.h"
#include "javavm/include/stackmaps.h"
#include "javavm/include/indirectmem.h"

#ifdef CVM_JIT
#include "javavm/include/jit/jit.h"
#endif

#include "javavm/include/clib.h"
#include "javavm/include/porting/ansi/setjmp.h"
#include "javavm/include/porting/int.h"
#include "javavm/include/porting/system.h"

#ifdef CVM_JVMTI
#include "javavm/include/jvmtiExport.h"
#endif

#ifdef CVM_HW
#include "include/hw.h"
#endif

#ifdef CVM_DEBUG
static int CVMstackmapVerboseDebug = 0;
#endif

/*
  The Layout of the Stackmap Buffer
  =================================
  The stackmaps for a method is made up of a list of entries: one for each
  GC point in the method.  Each entry has a bytecode PC as a unique key.

  Most stack frames tend to be relatively small.  Hence, the typical stackmap
  entry would fit within 32-bits: a 16-bit PC, and a 15-bit map.  The remaining
  bit is used to indicate whether the map actually has more than 15 locals
  and/or stack words thereby requiring more than 15 bits in the map i.e. does
  it have an extended or super extended entry that holds the real information.
  
  How to find the real entry?
  ==========================
  The stackmap entry can be found by using the PC as the unique key.
  Given the PC, CVMstackmapGetEntryForPC() will acquire a basic stack map
  entry.  A basic stackmap entry is one that fits within 32-bits.

  If bit 0 of entry->state[0] is set, then entry->state[0] actually contains
  an offset to a larger (more than 32bits) stackmap entry either in the
  extended region or the super extended region of stackmaps buffer.

  The offset value is computed as entry->state[0] >> 1, and is in units of
  CVMUint16 i.e. each offset represents a 16 bit increment.

  If the offset is less than CVM_STACKMAP_RESERVED_OFFSET, then the actual
  stackmap entry will reside in the extended region.  It's address can be
  computed using the offset to index into the extended region which resides
  at the end of the basic region.

  If the offset is equal to CVM_STACKMAP_RESERVED_OFFSET, then the actual
  stackmap entry will reside in the super extended region.  The start of the
  extended region will contain a pointer to the CVMStackMapSuperExtendedMaps
  struct (abbreviated as seMaps).  The seMaps will contain a sorted list
  of pointers to every stackmap entry in the super extended region.  To
  find the address of the actual stackmap entry that reside in the super
  extended region, we do a binary search on the entries in the seMaps
  keying off the PC.

  The memory layout
  =================

  Stackmaps buffer:
                         |----------------------------|
      CVMStackMaps       | header info                |
                         |----------------------------|
      basic region       | entry[0]                   |
                         | entry[1]                   |
                         | entry[2]                   |
                         | ...                        |
                         | entry[N]                   |
                         |----------------------------|
      extended region    | &seMaps                    |     
                         | extendedEntries[0]         |
                         | extendedEntries[1]         |
                         | ...                        |
                         | extendedEntries[nE]        |
                         |----------------------------|
      seMaps             | numOfSuperExtendedEntries  |
                         | &superExtendedEntries[0]   |
                         | &superExtendedEntries[0]   |
                         | ...                        |
                         | &superExtendedEntries[nSE] |
                         |----------------------------|
      super extended     | superExtendedEntries[0]    |
      region             | superExtendedEntries[1]    |
                         | ...                        |
                         | superExtendedEntries[nSE]  |
                         |----------------------------|

  where
      N is the total number of GC points.  For each GC point
          there is one basic entry.
      nE is the total number of entries in the extended region
          which can be reached using an offset stored in the
	  basic entry.
      nSE is the total number of entries in the super extended
          region.  Entries in this region must be looked up via
	  the seMaps table.

  Note: A given GC point can have only one of the following:
        1. a basic entry
        2. a basic entry + an extended entry
        3. a basic entry + a super extended entry

	It cannot have both an extended entry and a super extended entry.
	Hence, nE + nSE <= N.

  Note: the sizes of the entries in the extended region and super extended
        region are of variable size.  They aren't guaranteed to be uniform.

  Stackmap Context pointers
  =========================
  stackMapAreaBegin points pass the end of the basic region to the start of
  the extended region.

  stackMapAreaEnd points to the end of the entire stackmaps buffer.  If a
  super extended region is present, it will point just pass the end of the
  super extended region.  Otherwise, it will point pass the end of the
  extended region or the basic region depending on whether the extended
  region is present or not.

  stackMapAreaPtr is used to determine the next location in the stackmaps
  buffer to emit data into.  If the extended region is present, initially,
  it is pointed just pass the seMaps pointer in preparation for emitting
  the first entry in the extended region.  If the extended region is not
  present, it will set equal to stackMapAreaBegin and will never be
  incremented.

  Optional Regions
  ================
  The extended region, seMaps, and super extended region are all optional.
  They are included only when needed.  In most cases, these regions will
  not be present in the stackmaps.

  What does this mean to the GC?
  =============================
  The GC is not aware of the internal layout of the stackmap entries.  The
  GC calls CVMstackmapGetEntryForPC(), and the appropriate stackmap entry
  will be returned to it.  The returned entry may be a basic entry, an
  extended entry, or a super extended entry.  They all look the same to the
  GC.  The GC expects the entry to be of variable size.  The boundary of
  the map is not attained from the entry but rather computed from the runtime
  topOfStack pointer of the stack frame.

 */

/* CVM_STACKMAP_ENTRY_MIN_NUMBER_OF_CHUNKS is the number of CVMUint16 chunks
   that is available to store map bits in a basic stackmap entry.  In the
   current implementation, this is always 1 and is determined by the
   definition of the CVMStackMapEntry struct in classes.h.
*/
#define CVM_STACKMAP_ENTRY_MIN_NUMBER_OF_CHUNKS    1

/* CVM_STACKMAP_ENTRY_NUMBER_OF_BASIC_BITS is the number of map bits available
   in a basic stackmap entry.  For a CVM_STACKMAP_ENTRY_MIN_NUMBER_OF_CHUNKS
   value of 1, the number of bits will be 15 (i.e. 16 - 1 bit reserved to
   indicate the presence/absence of an extended entry.
*/
#define CVM_STACKMAP_ENTRY_NUMBER_OF_BASIC_BITS \
    ((CVM_STACKMAP_ENTRY_MIN_NUMBER_OF_CHUNKS * sizeof(CVMUint16) * 8) - 1)

/* CVM_STACKMAP_RESERVED_OFFSET is the reserved offset to indicate that
   the stackmap entry is located in the super extended region of the
   stackmaps buffer.  See comment above for more details. */
#define CVM_STACKMAP_RESERVED_OFFSET   (0x7fff)

/* CVMStackMapSuperExtendedMaps is used to store a table of pointers to
   CVMStackMapEntry structs that reside in the super extended region of
   the stackmaps buffer.  See comment above on the layout of the stackmaps
   buffer for more details. */
typedef struct CVMStackMapSuperExtendedMaps CVMStackMapSuperExtendedMaps;
struct CVMStackMapSuperExtendedMaps
{
    CVMUint32 numberOfEntries;
    CVMStackMapEntry *entries[1];
};


#define WRITE_INT16( pc, val ) { \
	(pc)[0] = (val) >> 8;    \
	(pc)[1] = val & 0xff;    \
    }
#define WRITE_INT32( pc, val ) {   \
	(pc)[0] = (val) >> 24;     \
	(pc)[1] = (val >>16)&0xff; \
	(pc)[2] = (val >>8)&0xff;  \
	(pc)[3] = val & 0xff;      \
    }

#define CVMalign4( n ) (( (n)+3)&~3)
/*
 * This file contains routines to generate stackmaps for GC points.
 *
 * ASSUMPTION: The code for the method we are analyzing has already
 * been verified.
 */
typedef CVMUint32 CVMCellTypeState;

/*
 * Each cell (a local variable or a stack slot) can hold one of the
 * following values. 
 *
 * (The program counter is used to track a JSR block,
 *  and holds the *target* of a JSR, and not the return value).
 */
#define CVM_MAP_BIT(n)    ((CVMCellTypeState)1 << (n))
#define CVMctsBottom      ((CVMCellTypeState)0)
#define CVMctsUninit      CVM_MAP_BIT(31) /* The initial state of all locals 
					     (except the args) */
#define CVMctsRef         CVM_MAP_BIT(30) /* A reference type */
#define CVMctsVal         CVM_MAP_BIT(29) /* A value type */
#define CVMctsPC          CVM_MAP_BIT(28) /* A JSR PC type. The rest of the
					     bits of the state contain the
					     target PC of the JSR */
#define CVMctsAll         (CVMctsUninit | CVMctsRef | CVMctsVal | CVMctsPC)

#define CVMctsIsUninit(cts)  (((cts) & CVM_MAP_BIT(31)) != 0)
#define CVMctsIsRef(cts)     (((cts) & CVM_MAP_BIT(30)) != 0)
#define CVMctsIsVal(cts)     (((cts) & CVM_MAP_BIT(29)) != 0)
#define CVMctsIsPC(cts)      (((cts) & CVM_MAP_BIT(28)) != 0)

#define CVMctsGetPC(cts)     ((cts) & ~CVMctsAll)
/*
 * In a 'CVMCellTypeState' the (relative) PC is only 28 bits wide anyway.
 * So there's no need to worry about losing bits and we can safely cast
 * our (on 64 bit platforms 64 bit wide) expression to 'CVMCellTypeState'. 
 */
#define CVMctsMakePC(pc)     ((CVMCellTypeState)(CVMctsPC | (pc)))
#define CVMctsGetFlags(cts)  ((cts) & CVMctsAll)

typedef struct CVMBasicBlock    CVMBasicBlock;
typedef struct CVMJsrTableEntry CVMJsrTableEntry;

/*
 * The representation of a basic block. 
 */
struct CVMBasicBlock {
    CVMUint8*              startPC;      /* The absolute (ptr) start PC */
    CVMCellTypeState*      varState;     /* The vars state on entry */
    CVMCellTypeState*      stackState;   /* The stack state on entry */
    CVMBool                changed;      /* Has the entry state changed? */
    CVMInt32               topOfStack;   /* The topOfStack for interpreting */
    CVMBool		   isLive;	 /* Is this block reachable? */
    CVMBool		   endsWithJsr;  /* The bb ends with a JSR opcode? */
    struct CVMBasicBlock*  liveNext;	 /* Next on liveness analysis list */
#ifdef CVM_JIT
    CVMBool                endsWithRet;  /* The bb ends with a ret opcode? */
    CVMInt32               endTopOfStack;/* The topOfStack at the end of bb. */
#endif
    struct CVMBasicBlock** successors;   /* Successor BB's (0-terminated) */
};

/*
 * The representation of a JSR table. Keeps track of all JSR targets,
 * and for each, its callers. That way, we know who the possible callers
 * of a jsr block are when we encounter a 'ret' instruction during
 * abstract interpretation
 */
struct CVMJsrTableEntry {
    CVMUint32        jsrPC;      /* The start of the jsr block (relative) */
    CVMUint32        jsrNoCalls; /* No of callers for this jsr target */
    CVMBasicBlock**  jsrCallers; /* Caller BB's of this jsr */
};

/*
 * When code is rewritten due to conflicts, it can change sizes.
 * The remapping of relative addresses is tracked using this.
 * It must be kept sorted by address.
 */
typedef struct CVMstackmapPCMapEntry{
    int addr;
    int adjustment;
}CVMstackmapPCMapEntry;

typedef struct CVMstackmapPCMap {
    int nAdjustments;
    int mapSize;
    struct CVMstackmapPCMapEntry map[1];
} CVMstackmapPCMap;

/*
 * The context for the current stackmap generation
 */
typedef struct {
    CVMExecEnv*        ee;

    /* Error handler context to longjmp to */
    jmp_buf errorHandlerContext;

    /* Method information */
    CVMMethodBlock*    mb;
    CVMJavaMethodDescriptor* jmd;
    CVMClassBlock*     cb;
    CVMConstantPool*   cp;
    CVMUint8*          code;
    CVMUint16          codeLen;
    CVMUint32          stateSize; /* Total 'state' size */
    CVMUint16          nVars;     /* No of locals */
    CVMUint16          maxStack;  /* Maximum number of stack slots */

    /* Created data structures */

    /* The first three are the heads of all allocated memory.
       We free them when done, or on error. */
    CVMBasicBlock*     basicBlocks;
    void*              mapsArea;
    CVMStackMaps*      stackMaps;

    CVMUint32          nBasicBlocks;
    CVMUint32          nGCPoints;
    CVMUint32*         gcPointsBitmap;
    CVMBasicBlock**    successorsArea;
    CVMBasicBlock*     liveStack; /* liveness analysis stack */

    /* Mapping from exception handler to basic block */
    CVMUint32          nExceptionHandlers;
    CVMBasicBlock**    exceptionsArea; 

    /* Jsr table */
    CVMJsrTableEntry*  jsrTable;
    CVMUint32          jsrTableSize;

    /* The state of the interpretation of the current basic block.
       We need this because we don't want to destroy the entry state of
       a basic block. */
    CVMCellTypeState*  varState;
    CVMCellTypeState*  stackState;

    /*
     * The memory area that holds the stackmaps. 
     */
    CVMUint16*         stackMapAreaEnd;
    CVMUint16*         stackMapAreaBegin; /* The allocation pointer */
    CVMUint16*         stackMapAreaPtr; /* The allocation pointer */
    CVMUint32          stackMapLongFormatNumBytes; /* # of long format bytes */
     
    /* Tracking info for the super extended region: */
    CVMUint32          numberOfSuperExtendedEntries;
    CVMStackMapSuperExtendedMaps *seMaps;
    CVMUint32          currentNumberOfSEEntries;

    /*
     * Ref-uninit conflict uses of local variables
     */