jitregman.c

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

/*
 * @(#)jitregman.c	1.9 06/10/23
 * 
 * Portions Copyright  2000-2008 Sun Microsystems, Inc. All Rights
 * Reserved.  Use is subject to license terms.
 * 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.
 */

/*
 * Register manager implementation.
 */
#include "javavm/include/defs.h"
#include "javavm/include/objects.h"
#include "javavm/include/classes.h"
#include "javavm/include/utils.h"
#include "javavm/include/bcutils.h"
#include "javavm/include/ccee.h"
#include "javavm/include/jit/jit.h"
#include "javavm/include/jit/jitir.h"
#include "javavm/include/jit/jitcontext.h"
#include "javavm/include/jit/jitcodebuffer.h"
#include "javavm/include/jit/jitirnode.h"
#include "javavm/include/jit/jitirblock.h"
#include "javavm/include/jit/jitcomments.h"
#include "javavm/include/jit/jitmemory.h"
#include "javavm/include/jit/jitirdump.h"
#include "javavm/include/jit/jitstackmap.h"
#include "javavm/include/jit/jitarchemitter.h"
#include "javavm/include/jit/jitregman.h"
#include "javavm/include/jit/jitopcodes.h"
#include "javavm/include/jit/jitstackman.h"
#include "javavm/include/jit/jitgrammar.h"

#include "javavm/include/clib.h"

#ifdef CVM_TRACE_ENABLED
#include "javavm/include/globals.h"
#endif

#ifdef CVM_DEBUG_ASSERTS
/* FIXME: undef for now */
#undef CVMJIT_STRICT_REFLOCAL_ASSERTS
#endif

#define RM_INITIAL_REF_COUNT_SIZE	64 /* more than ever needed */
#define RM_STICKY_REF_COUNT		255

#ifdef CVM_JIT_USE_FP_HARDWARE
#define RM_MAX_INTERESTING_REG	(con)->maxInteresting
#define RM_MIN_INTERESTING_REG	(con)->minInteresting
#define RM_SAFE_SET 		(con)->safeSet
#define RM_UNSAFE_SET 		(con)->unsafeSet
#define RM_ANY_SET 		(con)->anySet
#define RM_SINGLE_REG_ALIGN	(con)->singleRegAlignment
#define RM_DOUBLE_REG_ALIGN	(con)->doubleRegAlignment
#define RM_MOV_OPCODE(_con)	(_con)->movOpcode
#define RM_MAX_REG_SIZE(_con)	(_con)->maxRegSize

#else
    /* not using FP hardware */
#define RM_MAX_INTERESTING_REG	CVMCPU_MAX_INTERESTING_REG
#define RM_MIN_INTERESTING_REG	CVMCPU_MIN_INTERESTING_REG
#define RM_SAFE_SET 		CVMRM_SAFE_SET
#define RM_UNSAFE_SET 		CVMRM_UNSAFE_SET
#define RM_ANY_SET 		CVMRM_ANY_SET
#define RM_SINGLE_REG_ALIGN	CVMCPU_SINGLE_REG_ALIGNMENT
#define RM_DOUBLE_REG_ALIGN	CVMCPU_DOUBLE_REG_ALIGNMENT
#define RM_MAX_REG_SIZE(_con)	CVMCPU_MAX_REG_SIZE
#define RM_MOV_OPCODE(_con)	CVMCPU_MOV_OPCODE
#endif

#if defined(CVM_64)
#define RM_STORE_OPCODE(_con,_res)	((_con)->storeOpcode[ (CVMRMisRef((_res)) || CVMRMisAddr((_res))) ? ((_res)->size) : ((_res)->size)-1])
#define RM_LOAD_OPCODE(_con,_res)	((_con)->loadOpcode[  (CVMRMisRef((_res)) || CVMRMisAddr((_res))) ? ((_res)->size) : ((_res)->size)-1])
#else
#define RM_STORE_OPCODE(_con,_res)	((_con)->storeOpcode[((_res)->size)-1])
#define RM_LOAD_OPCODE(_con,_res)	((_con)->loadOpcode[((_res)->size)-1])
#endif   /* CVM_64 */

#if ((CVMCPU_MAX_REG_SIZE != 1) || \
	(defined(CVM_JIT_USE_FP_HARDWARE) && (CVMCPU_FP_MAX_REG_SIZE != 1)))
/* there are some double-word registers */
#define RM_NREGISTERS(_con,_size)	((_size) <= RM_MAX_REG_SIZE(_con) ? 1 : 2)
#else
/* all the registers are single-word */
#define RM_NREGISTERS(_con,_size) 	(_size)
#endif


#ifdef  CVM_DEBUG_ASSERTS
#define RM_INT_KEY	1
#define RM_FP_KEY	2
#define CVMRMassertContextMatch(cx,rp) CVMassert((cx) == (rp)->rmContext)
#else
#define CVMRMassertContextMatch(cx,rp)
#endif

typedef enum {
    CVMRM_REGPREF_TARGET,
    CVMRM_REGPREF_SCRATCH,
    CVMRM_REGPREF_PERSISTENT
} CVMRMRegisterPreference;

#define DEFAULT_CONSTANT_PREF	CVMRM_REGPREF_PERSISTENT
#define DEFAULT_LOCAL_PREF	CVMRM_REGPREF_PERSISTENT
#ifndef CVMCPU_NO_REGPREF_PERSISTENT
#define DEFAULT_RESOURCE_PREF	CVMRM_REGPREF_PERSISTENT
#else
#define DEFAULT_RESOURCE_PREF  CVMRM_REGPREF_TARGET
#endif

static void
CVMRMpinResource0(CVMJITRMContext*, CVMRMResource*,
    CVMRMregset target, CVMRMregset avoid,
    CVMRMRegisterPreference pref, CVMBool strict);

#ifdef CVM_JIT_REGISTER_LOCALS
static void
CVMRMbindAllIncomingLocalNodes(CVMJITCompilationContext* con,
			       CVMJITIRBlock* b);
#endif

static void
CVMRMbindAllUsedNodes(CVMJITCompilationContext* con, CVMJITIRBlock* b);

static void
CVMRMbindUseToResource(CVMJITCompilationContext* con, CVMJITIRNode* expr);

/* Purpose: Gets an available reg from the specified register set. */
static int
findMaxRegInSet(
    CVMJITRMContext* con, 
    CVMRMregset target,
    int minInteresting,
    int maxInteresting,
    int alignment)
{
    int i;

#ifdef CVM_JIT_ROUND_ROBIN_REGISTER_SELECTION
    {
       /* SVMC_JIT c5041613 (dk) 2004-01-26.  round robin-based
	* register selection.  The original naive strategy lead to
	* massive register reuse of the largest available registers
	* causing tremendous spilling overhead.
	*
	* Improved register selection variant is based on a round
	* robin strategy.  The idea is to select that register which
	* had not been selected for the longest time among all
	* registers between which to choose.  This is context and flow
	* insensitive, but should yield a better register utilization
	* and prevent bottlenecks in register usage.  The selection is
	* done in two stages: first we try to find an unoccupied
	* register - subject to the round robin strategy. If none can
	* be found, then we just select one and have to generate spill
	* code later on. */
       /* SVMC_JIT d022609 (ML) 2004-05-18. improved code. */
       CVMRMResource* rp;
       int mru = con->lastRegNo;
       CVMRMregset o = con->occupiedRegisters; 
       CVMassert((minInteresting <= mru) && (mru <= maxInteresting));
       if (alignment == 2) {
	  minInteresting = (1 + minInteresting) & ~1 /* round up to even */;  
	  maxInteresting = maxInteresting & ~1 /* round down to even */;
	  mru = mru & ~1 /* round down to even */;
       }
       for (i = mru - alignment; i >= minInteresting; i -= alignment) {
	  if (target & (1U<<i)) {
	     rp = con->reg2res[i];
	     if (rp == NULL) {
		if (!(o & (1U<<i)))
		   return i;
	     }
	     else {
		CVMassert(!(rp->flags & CVMRMpinned));
		if (!((o & (1U<<i)) && (rp->flags & CVMRMdirty)))
		   return i;
	     }
	  }
       }
       for (i = maxInteresting; i >= mru; i -= alignment) {
	  if (target & (1U<<i)) {
	     rp = con->reg2res[i];
	     if (rp == NULL) {
		if (!(o & (1U<<i)))
		   return i;
	     }
	     else {
		CVMassert(!(rp->flags & CVMRMpinned));
		if (!((o & (1U<<i)) 
		      && (rp->flags & CVMRMdirty)))
		   return i;
	     }
	  }
       }
       /* We did not find an unoccupied register. So now we try to
	  select one we have to generate spill code for. */
       for (i = mru - alignment; i >= minInteresting; i -= alignment) {
	  if (target & (1U<<i))
	     return i;
       }
       for (i = maxInteresting; i >= mru; i -= alignment) {
	  if (target & (1U<<i))
	     return i;
       }
    }
#else /* CVM_JIT_ROUND_ROBIN_REGISTER_SELECTION */
    /* The register with the highest ID value in the specified set
       will be selected first: */
    if (alignment == 2 )
	maxInteresting &= ~1; /* round down to even */
    for (i=maxInteresting; i>=minInteresting; i-= alignment ) {
	if ((target & (1U<<i)) != 0)
	    return i;
    }
#endif /* CVM_JIT_ROUND_ROBIN_REGISTER_SELECTION */
    return -1;
}

/* Purpose: Gets an available reg from the specified register set. */
static int
findMinRegInSet(
    CVMRMregset target,
    int minInteresting,
    int maxInteresting,
    int alignment,
    int nregs)
{
    int i;

    /*
     * Make search easier if a 32-bit pair is needed by masking off the upper
     * register of each pair if the lower register is not available. 
     * This way we know if any bit is set, then the following bit is also set.
     */
    if (nregs > 1) {
	target = target & (target >> 1);
    }

    /* The register with the lowest ID value in the specified set
       will be selected first: */
    CVMassert(alignment > 0);
    if (alignment != 1) {
	int left = (minInteresting % alignment);
	if (left > 0) {
	    /* round up to alignment */
	    minInteresting += alignment - left;
	}
    }
    CVMassert(minInteresting % alignment == 0);
    for (i=minInteresting; i<=maxInteresting; i+= alignment ) {
	if ((target & (1U<<i)) != 0)
	    return i;
    }
    return -1;
}

/*
 * Spill Location Management. Finding and relinquishing spill locations
 * using CVMJITSet structures
 */

static void
resizeSpillRefCount(CVMJITCompilationContext* con, int needed)
{
    int newsize = needed;
    CVMUint8* newallocation;
    /* round up to multiple of 64 */
    newsize = (newsize+63) & ~63;
    CVMassert(newsize > con->RMcommonContext.spillBusyRefSize);

    newallocation = CVMJITmemNew(con, JIT_ALLOC_CGEN_REGMAN,
				 newsize*sizeof(CVMUint8));
    memcpy(newallocation, con->RMcommonContext.spillBusyRefCount,
	   con->RMcommonContext.spillBusyRefSize*sizeof(CVMUint8));
    con->RMcommonContext.spillBusyRefCount = newallocation;
    con->RMcommonContext.spillBusyRefSize = newsize;
}


static void
resetSpillMap(CVMJITCompilationContext* con, CVMJITIRBlock* b)
{
	CVMJITRMCommonContext* common = &(con->RMcommonContext);
	/* reset the spill set */
	CVMJITsetClear(con, &(common->spillBusySet));
	memset(common->spillBusyRefCount, 0,
	       common->spillBusyRefSize * sizeof(CVMUint8));
	/* mark all phiWords as busy */
	if (con->maxPhiSize > 0){
	    int i;
	    int maxPhi = con->maxPhiSize;
	    CVMUint8* refElement;
	    CVMJITsetPopulate(con, &(common->spillBusySet),
			      maxPhi);
	    if (maxPhi > common->spillBusyRefSize){
		resizeSpillRefCount(con, maxPhi);
	    }
	    refElement = common->spillBusyRefCount;
	    for( i = 0; i < maxPhi; i++){
		*(refElement++) = RM_STICKY_REF_COUNT;
	    }
		
	}

	/* initialize the spill ref set */
	CVMJITsetClear(con, &(con->RMcommonContext.spillRefSet));
	con->RMcommonContext.maxPhiSize     = con->maxPhiSize;
	con->RMcommonContext.maxSpillNumber = con->maxPhiSize-1;
}

int findSpillLoc(
    CVMJITCompilationContext* con,
    int                       size,
    CVMBool                   isRef)
{
    int spilloff, topoff; 
    CVMBool isBusy;
    CVMJITSet*	busySet = &con->RMcommonContext.spillBusySet;
    CVMUint8*   refCount=  con->RMcommonContext.spillBusyRefCount;
    CVMJITSet*	refSet  = &con->RMcommonContext.spillRefSet;
    CVMassert((size == 1) || (size == 2));
    CVMassert((size == 1) || !isRef);
    for ( spilloff = con->maxPhiSize; ;spilloff += 1){
	CVMJITsetContains(busySet, spilloff, isBusy);
	if (!isBusy){
	    /* this one is available. If double word, look for next, too. */
	    if (size > 1){
		CVMJITsetContains(busySet, (spilloff+1), isBusy);
		if (!isBusy){
		    /* a pair of winners */
		    CVMJITsetAdd(con, busySet, spilloff);
		    CVMJITsetAdd(con, busySet, spilloff+1);
		    CVMJITsetRemove(con, refSet, spilloff);
		    CVMJITsetRemove(con, refSet, spilloff+1);
		    break;
		}
		/* else keep trying */
	    } else {
		/* a winner */
		CVMJITsetAdd(con, busySet, spilloff);
		if (isRef){
		    CVMJITsetAdd(con, refSet, spilloff);
		} else {
		    CVMJITsetRemove(con, refSet, spilloff);
		}
		break;
	    }
	}
    }
    /* location spilloff is available. see if it is a new hight water mark */
    topoff = spilloff+size-1;
    if (topoff > con->RMcommonContext.maxSpillNumber){
	con->RMcommonContext.maxSpillNumber = topoff;
    }
    if (topoff >= con->RMcommonContext.spillBusyRefSize){
	resizeSpillRefCount(con, topoff+1);
	refCount=  con->RMcommonContext.spillBusyRefCount;
    }
    refCount[spilloff] = 1;
    if (size > 1){
	refCount[spilloff+1] = 1;
    }
    
    if (spilloff > CVMRM_MAX_SPILL_LOCATION) {
        CVMJITlimitExceeded(con, "exceeding max spill locations");
    }

    return spilloff;
}

static void
relinquishSpillLoc(CVMJITCompilationContext*con, int loc, int size)
{
    CVMJITSet*	busySet = &con->RMcommonContext.spillBusySet;
    CVMUint8*   refCount=  con->RMcommonContext.spillBusyRefCount;
    CVMassert(loc>=0);
    CVMassert((size == 1) || (size == 2));
#ifdef CVM_DEBUG_ASSERTS
    {
	CVMBool isBusy;
	CVMJITsetContains(busySet, loc, isBusy);
	CVMassert(isBusy);
	CVMassert((loc+size) <= con->RMcommonContext.spillBusyRefSize);
	CVMassert(refCount[loc] > 0);
	if (size > 1){
	    CVMJITsetContains(busySet, (loc+1), isBusy);
	    CVMassert(isBusy);
	    CVMassert(refCount[loc+1] == refCount[loc]);
	}
    }
#endif
    if (refCount[loc] == RM_STICKY_REF_COUNT)
	return; /* cannot deallocate */
    if ((refCount[loc] -= 1) == 0){
	CVMJITsetRemove(con, busySet, loc);
	if (size > 1){
	    CVMJITsetRemove(con, busySet, (loc+1));
	}
    }
    if (size > 1){
	refCount[loc+1] -= 1;
    }
}

static void
incrementSpillCount(CVMJITCompilationContext*con, int loc, int size)
{
    CVMUint8*   refCount= con->RMcommonContext.spillBusyRefCount;
    CVMassert((loc+size) <= con->RMcommonContext.spillBusyRefSize);
    if (refCount[loc] == RM_STICKY_REF_COUNT)
	return; /* maxed out */
    refCount[loc] += 1;
    if (size > 1)
	refCount[loc+1] += 1;
}

static void
flushResource(CVMJITRMContext* con, CVMRMResource* rp)
{