jitopt.c

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

/*
 * @(#)jitopt.c	1.24 06/10/10
 *
 * 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/utils.h"
#include "javavm/include/bcutils.h"
#include "javavm/include/jit/jit.h"
#include "javavm/include/jit/jitcontext.h"
#include "javavm/include/jit/jitirblock.h"
#include "javavm/include/jit/jitirnode.h"
#include "javavm/include/jit/jitmemory.h"
#include "javavm/include/jit/jitutils.h"

#include "javavm/include/clib.h"

#if 0 /* Temporarily commented out. */

/* Loop descriptors */
/* Back edges go tail -> head. So pc(head) < pc(tail). */
struct CVMJITLoop {
    CVMJITIRBlock* headBlock;
    CVMJITIRBlock* tailBlock;
    CVMJITSet      loopBlocks;
    CVMUint32      numBlocks;
};

/*
 * Nested loops. Each CVMJITNestedLoop entry contains an array of loop
 * pointers, and the size of this array.
 */
struct CVMJITNestedLoop {
    CVMJITLoop**    loops;
    CVMUint32       numLoopsContained;
};

#ifdef CVM_DEBUG
/* Forward declarations for dumpers */
static void
dumpBlocks(CVMJITCompilationContext* con,
	   CVMJITIRBlock* rootblock, CVMUint32 numBlocks);

static void
dumpLoops(CVMJITCompilationContext* con);

static void
dumpNestedLoops(CVMJITCompilationContext* con);
#endif /* CVM_DEBUG */

/*
 * Iterator for DFS walk computation
 */
typedef struct DFSIter {
    CVMJITIRBlock** dfsWalk;
    CVMUint32       nextIdx;
    char*           visited;

    /* Explicit stack for iterative DFS walk */
    CVMJITStack     stack;
} DFSIter;

/*
 * Iterative DFS walker. This one is pre-order -- we visit each node
 * before we visit its successors.  
 */
static void
dfsOrderDoIt(CVMJITCompilationContext* con, DFSIter* iter);

static void
visitSucc(CVMJITCompilationContext* con, CVMUint32 succ, void* data)
{
    DFSIter* iter = (DFSIter*)data;
    
    if (!iter->visited[succ]) {
	CVMJITstackPush(con, (CVMJITIRBlock*)(con->idToBlock[succ]), 
	    &iter->stack);
    }
}

static void
dfsOrderDoIt(CVMJITCompilationContext* con, DFSIter* iter)
{
    while (!CVMJITstackIsEmpty(con, &iter->stack)) {
	CVMJITIRBlock* block;
	block = (CVMJITIRBlock*)CVMJITstackPop(con, &iter->stack);
	/* Pre-order traversal */
	iter->dfsWalk[iter->nextIdx++] = block;
	iter->visited[block->blockID]  = CVM_TRUE;
	CVMJITsetIterate(con, &block->successors, visitSucc, iter);
    }
}

static CVMJITIRBlock**
computeDfsWalkDoIt(CVMJITCompilationContext* con, 
		   CVMJITIRBlock* rootblock, CVMUint32 numBlocks)
{
    DFSIter iter;
    
    iter.visited = (char*)CVMJITmemNew(con, JIT_ALLOC_OPTIMIZER,
				       numBlocks * sizeof(char));
    iter.nextIdx = 0;
    /* Allocate one extra place to make the list NULL-terminated */
    iter.dfsWalk = (CVMJITIRBlock**)
	CVMJITmemNew(con, JIT_ALLOC_OPTIMIZER,
		     (numBlocks+1) * sizeof(CVMJITIRBlock*));
    CVMJITstackInit(con, &iter.stack, numBlocks);

    /* Start walk with root block */
    CVMJITstackPush(con, (CVMJITIRBlock*)rootblock, &iter.stack);

    /* And do the walk */
    dfsOrderDoIt(con, &iter);
    
    /* NULL-terminated */
    iter.dfsWalk[numBlocks] = NULL;

    return iter.dfsWalk;
}

/*
 * Compute DFS walk if it has not been computed already
 */
static void
computeDfsWalkIfNeeded(CVMJITCompilationContext* con,
		       CVMJITIRBlock* rootnode, CVMUint32 numBlocks)
{
    if (con->dfsWalk == NULL) {
	con->dfsWalk = computeDfsWalkDoIt(con, rootnode, numBlocks);
    }
}

/*
 * Finding dominators. Blocks are traversed in DFS order for faster
 * convergence.
 */
static void
addDominators(CVMJITCompilationContext* con, CVMUint32 elem, void* data)
{
    CVMJITSet*     tempSet   = (CVMJITSet*)data;
    CVMJITIRBlock* predBlock = con->idToBlock[elem];
    
    CVMJITsetIntersection(con, tempSet, &predBlock->dominators);
}

void
findDominators(CVMJITCompilationContext* con,
	       CVMJITIRBlock* rootblock, CVMUint32 numBlocks)
{
    CVMJITSet temp;
    CVMJITIRBlock* block;
    CVMJITIRBlock** dfsWalk;
    CVMBool change;
#ifdef CVM_DEBUG
    CVMUint32 numIter = 0;
#endif

    CVMJITsetInit(con, &temp);

    /*
     * Initially, the dominator set for each block but the root is
     * all the blocks.
     */
    for (block = rootblock->next; block != NULL; block = block->next) {
	CVMJITsetInit(con, &block->dominators);
	CVMJITsetPopulate(con, &block->dominators, numBlocks);
    }
    /*
     * And the root block dominates only itself
     */
    CVMJITsetInit(con, &rootblock->dominators);
    CVMJITsetAdd(con, &rootblock->dominators, rootblock->blockID);

    /* Compute pre-order DFS traversal of the blocks */
    computeDfsWalkIfNeeded(con, rootblock, numBlocks);
    CVMassert(*con->dfsWalk == rootblock);

    /*
     * Compute until there are no changes
     */
    do {
	dfsWalk = con->dfsWalk;

	change = CVM_FALSE;
	
	/* The pre-increment neatly skips over the root block */
	while ((block = *(++dfsWalk)) != NULL) {
	    CVMBool equals;
	    
	    /* Temp has all the blocks for a start */
	    CVMJITsetPopulate(con, &temp, numBlocks);
	    /*
	     * Find the intersection of the dominators of all
	     * predecessors of this block
	     */
	    CVMJITsetIterate(con, &block->predecessors, addDominators, &temp);
	    /* And add the current block as a dominator */
	    CVMJITsetAdd(con, &temp, block->blockID);
	    /* Had we already set the dominators of this block to the
	       accumulated value? If so, no change happened */
	    CVMJITsetEquals(con, &temp, &block->dominators, equals);
	    if (!equals) {
		change = CVM_TRUE;
		CVMJITsetCopy(con, &block->dominators, &temp);
	    }
	}

#ifdef CVM_DEBUG
	numIter++;
#endif

    } while (change);

    CVMtraceJITIROPT(("JO: Computed dominators in %d iterations\n", numIter));
}

/*
 * Loop finder help.
 */
typedef struct BackEdgeIter {
    CVMJITGrowableArray loops;

    CVMUint32     tail;     /* The blockID of the tail node */

    /* To be used in natural loop computation */
    CVMJITStack  stack;
    CVMJITLoop*  currentLoop;
} BackEdgeIter;

static CVMJITLoop*
newLoopStruct(CVMJITCompilationContext* con, BackEdgeIter* iter)
{
    void* elem;
    
    CVMJITgarrNewElem(con, &iter->loops, elem);
    return (CVMJITLoop*)elem;
}

/*
 * Visit predecessor for loop computation purposes
 */
static void
visitPred(CVMJITCompilationContext* con, CVMUint32 pred, void* data)
{
    CVMBool contains;
    BackEdgeIter* iter = (BackEdgeIter*)data;
    
    CVMJITLoop* loop = iter->currentLoop;
    CVMJITSet*  loopBlocks = &loop->loopBlocks;
    
    CVMJITsetContains(loopBlocks, pred, contains);
    if (!contains) {
	CVMJITsetAdd(con, loopBlocks, pred);
	loop->numBlocks++;
	CVMJITstackPush(con, (CVMJITIRBlock*)(con->idToBlock[pred]), 
	    &iter->stack);
    }
}

/*
 * Find natural loop of the current back edge
 */
static void
findNaturalLoop(CVMJITCompilationContext* con, CVMJITLoop* loop,
		BackEdgeIter* iter)
{
    CVMJITIRBlock* headBlock = loop->headBlock;
    CVMJITIRBlock* tailBlock = loop->tailBlock;

    iter->currentLoop = loop;
    
    loop->numBlocks = 1;
    CVMJITsetAdd(con, &loop->loopBlocks, headBlock->blockID);
    
    if (headBlock != tailBlock) {
	CVMJITsetAdd(con, &loop->loopBlocks, tailBlock->blockID);
	loop->numBlocks++;
	CVMJITstackPush(con, (CVMJITIRBlock*)tailBlock, &iter->stack);
    }
    while (!CVMJITstackIsEmpty(con, &iter->stack)) {
	CVMJITIRBlock* block;
	block = (CVMJITIRBlock*)CVMJITstackPop(con, &iter->stack);
	CVMJITsetIterate(con, &block->predecessors, visitPred, iter);
    }
}

/* Back edges go tail -> head. So pc(head) < pc(tail). 
 * During each set iteration, tail is constant, and head changes
 *
 * Add this back edge and find its natural loop
 */
static void
handleBackEdge(CVMJITCompilationContext* con, CVMUint32 head, void* data)
{
    BackEdgeIter* iter = (BackEdgeIter*)data;
    /*
     * Each back edge corresponds to a loop. Allocate space.
     */
    CVMJITLoop* loop = newLoopStruct(con, iter);

    CVMtraceJITIROPT(("JO: Found back edge: head=%d, tail=%d\n",
		      head, iter->tail));
    loop->tailBlock = con->idToBlock[iter->tail];
    loop->headBlock = con->idToBlock[head];
    CVMJITsetInit(con, &loop->loopBlocks);

    /* Find out which blocks are included in the natural loop for the
       current back edge */
    findNaturalLoop(con, loop, iter);
    /* Make sure the stack in iter is empty after each natural loop
       computation */
    CVMassert(iter->stack.todoIdx == 0);
}

/*
 * Given loop data, find nested loops and order them.
 */
typedef struct NestedLoopIter {
    CVMJITGrowableArray nestedLoops;
} NestedLoopIter;

static void
findNestedLoops(CVMJITCompilationContext* con, NestedLoopIter* iter);

#ifdef CVM_DEBUG

static void
findLoops(CVMJITCompilationContext* con, CVMJITIRBlock* rootblock,
	  CVMUint32 numBlocks)
{
    CVMJITIRBlock* block;
    CVMJITSet temp;
    BackEdgeIter iterBE;
    NestedLoopIter iterNL;

    findDominators(con, rootblock, numBlocks);
    CVMtraceJITIROPTExec(dumpBlocks(con, rootblock, numBlocks));
    
    /* no loops yet */
    CVMJITgarrInit(con, &iterBE.loops, sizeof(CVMJITLoop));

    /* This stack will be used in natural loop computation */
    CVMJITstackInit(con, &iterBE.stack, numBlocks);
    
    /* We have the dominators. Now look for back edges. */
    CVMJITsetInit(con, &temp);
    for (block = rootblock; block != NULL; block = block->next) {
	CVMBool isEmpty;
	/* The intersection of the successors and the dominators gives
	   you the loop closing branches, otherwise known 
	   as "back edges". */
	CVMJITsetClear(con, &temp);
	
	CVMJITsetCopy(con, &temp, &block->successors);
	CVMJITsetIntersection(con, &temp, &block->dominators);
	CVMJITsetIsEmpty(con, &temp, isEmpty);
	if (!isEmpty) {
	    /* We found some back edges. Record each, and compute
	       its natural loops */
	    iterBE.tail = block->blockID;
	    
	    CVMJITsetIterate(con, &temp, handleBackEdge, &iterBE);

	    CVMtraceJITIROPT(("JO: Loop closing branches from block #%d: ",
			      block->blockID));
	    CVMtraceJITIROPTExec(CVMJITsetDumpElements(con, &temp));
	    CVMtraceJITIROPT(("\n"));
	}
    }
    CVMJITsetDestroy(con, &temp);

    /*
     * We have collected the loops in iterBE.loops. Pass info to con
     */
    con->loops    = (CVMJITLoop*)CVMJITgarrGetElems(con, &iterBE.loops);
    con->numLoops = CVMJITgarrGetNumElems(con, &iterBE.loops);

    CVMtraceJITIROPTExec(dumpLoops(con));

    /*
     * We'll now be collecting nested loops
     */
    CVMJITgarrInit(con, &iterNL.nestedLoops, sizeof(CVMJITNestedLoop));
    
    findNestedLoops(con, &iterNL);
    
    /*
     * We have collected the loops in iterNL.nestedLoops. Pass info to con
     */
    con->nestedLoops    = (CVMJITNestedLoop*)
	CVMJITgarrGetElems(con, &iterNL.nestedLoops);
    con->numNestedLoops = CVMJITgarrGetNumElems(con, &iterNL.nestedLoops);

    CVMtraceJITIROPTExec(dumpNestedLoops(con));