verify3b.c

linux下建立JAVA虚拟机的源码KAFFE

/**
 * verify3b.c
 *
 * Copyright 2004
 *   Kaffe.org contributors. See ChangeLog for details. All rights reserved.
 *
 * See the file "license.terms" for information on usage and redistribution
 * of this file.
 */

#include "baseClasses.h"
#include "bytecode.h"
#include "classMethod.h"
#include "code.h"
#include "constants.h"
#include "exception.h"
#include "errors.h"
#include "debug.h"
#include "gc.h"

#include "verify.h"
#include "verify-block.h"
#include "verify-debug.h"
#include "verify-errors.h"
#include "verify-type.h"


static inline bool verifyErrorInVerifyMethod3b(Verifier* v,
					       BlockInfo* curBlock,
					       const char * msg);
static        bool mergeBasicBlocks(Verifier* v,
				    BlockInfo* fromBlock,
				    BlockInfo* toBlock);


/**
 * Helper function for error reporting in verifyMethod3b
 */
static inline 
bool
verifyErrorInVerifyMethod3b(Verifier* v, BlockInfo* curBlock, const char * msg)
{
        gc_free(curBlock);
	return verifyError(v, msg);
}

/*
 * verifyMethod3b()
 *    The Data-flow Analyzer
 *
 * The data-flow algorithm is taken from the JVM 2 spec, which describes it more or less as follows:
 *
 *  0  data-flow analyzer is initialised
 *       - for the first instruction of the method, the local variables that represent parameters
 *         initially contain values of the types indicated by the method's type descriptor.
 *       - the operand stack is empty.
 *       - all local variables contain an illegal value.
 *       - for the other instructions, which have not been examined yet, no information is available
 *         regarding the operand stack or local variables.
 *       - the "changed" bit is only set for the first instruction.
 *
 *  1  select a VM instruction whose "changed" bit is set
 *
 *       - if no such instruction remains, the method has successfully been verified.
 *       - otherwise, turn off the "changed" bit of the selected instruction.
 *
 *  2  model the effect of the instruction on the operand stack and local variable array by:
 *
 *       - if the instruction uses values from the operand stack, ensure that there are a
 *         sufficient number of values on the stack and that the top values on the stack are
 *         of an appropriate type.
 *       - if the instruction uses a local variable, ensure that the specified local variable
 *         contains a value of the appropriate type.
 *       - if the instruction pushes values onto the operand stack, ensure that there is sufficient
 *         room on the operand stack for the new values.  add the indicated types to the type of the
 *         modeled operand stack.
 *       - if the instruction modifies a local variable, record that the local variable now contains
 *         a type.
 *
 *  3  determine the instructions that can follow the current instruction.  successor instructions
 *     can be one of the following:
 *
 *       - the next instruction, if the current instruction is not an unconditional control tranfer
 *         instruction (ie - goto, return, or athrow).  basically check to make sure you don't
 *         "fall off" the last instruction of the method.
 *       - the target of a conditional or unconditional branch or switch.
 *       - any exception handlers for this instruction.
 *
 *  4  merge the state of the operand stack and local variable array at the end of the execution of the
 *     current instruction into each of the successor instructions.
 *
 *     (see merge function below)
 *
 *  5  continue at step 1.
 */
bool
verifyMethod3b(Verifier* v)
{
	const uint32 codelen      = METHOD_BYTECODE_LEN(v->method);
	const unsigned char* code = METHOD_BYTECODE_CODE(v->method);
	
	
	BlockInfo** blocks = v->blocks; /* aliased for convenience */
	uint32 curIndex;
	BlockInfo* curBlock;
	BlockInfo* nextBlock;

	uint32 pc = 0, newpc = 0, n = 0;
	int32 high = 0, low = 0;  /* for the switching instructions */
	
	
	
	DBG(VERIFY3, dprintf("    Verifier Pass 3b: Data Flow Analysis and Type Checking...\n"); );
	DBG(VERIFY3, dprintf("        memory allocation...\n"); );
	curBlock = createBlock(v->method);
	
	
	DBG(VERIFY3, dprintf("        doing the dirty data flow analysis...\n"); );
	blocks[0]->status |= CHANGED;
	curIndex = 0;
	while(curIndex < v->numBlocks) {
		DBG(VERIFY3,
		    dprintf("      blockNum/first pc/changed/stksz = %d / %d / %d / %d\n",
			    curIndex,
			    blocks[curIndex]->startAddr,
			    blocks[curIndex]->status & CHANGED,
			    blocks[curIndex]->stacksz);
		    dprintf("          before:\n");
		    printBlock(v->method, blocks[curIndex], "                 ");
		    );
		
		if (!(blocks[curIndex]->status & CHANGED)) {
			DBG(VERIFY3, dprintf("        not changed...skipping\n"); );
			curIndex++;
			continue;
		}
		
		blocks[curIndex]->status ^= CHANGED; /* unset CHANGED bit */
		blocks[curIndex]->status |= VISITED; /* make sure we've visited it...important for merging */
		copyBlockData(v->method, blocks[curIndex], curBlock);
		
		if (curBlock->status & EXCEPTION_HANDLER && curBlock->stacksz > 0) {
			return verifyErrorInVerifyMethod3b(v, curBlock, "it's possible to reach an exception handler with a nonempty stack");
		}
		
		
		if (!verifyBasicBlock(v, curBlock)) {
			return verifyErrorInVerifyMethod3b(v, curBlock, "failure to verify basic block");
		}
		
		
		DBG(VERIFY3, dprintf("          after:\n"); printBlock(v->method, curBlock, "                 "); );
		
		
		/*
		 * merge this block's information into the next block
		 */
		pc = curBlock->lastAddr;
		if (code[pc] == WIDE && code[getNextPC(code, pc)] == RET)
			pc = getNextPC(code, pc);
		switch(code[pc])
			{
			case GOTO:
				newpc = pc + 1;
				newpc = pc + getWord(code, newpc);
				nextBlock = inWhichBlock(newpc, blocks, v->numBlocks);
				
				if (!mergeBasicBlocks(v, curBlock, nextBlock)) {
					return verifyErrorInVerifyMethod3b(v, curBlock, "error merging operand stacks");
				}
				break;
				
			case GOTO_W:
				newpc = pc + 1;
				newpc = pc + getDWord(code, newpc);
				nextBlock = inWhichBlock(newpc, blocks, v->numBlocks);
				
				if (!mergeBasicBlocks(v, curBlock, nextBlock)) {
					return verifyErrorInVerifyMethod3b(v, curBlock, "error merging operand stacks");
				}
				break;
					
			case JSR:
				newpc = pc + 1;
				newpc = pc + getWord(code, newpc);
				goto JSR_common;
			case JSR_W:
				newpc = pc + 1;
				newpc = pc + getDWord(code, newpc);
			JSR_common:
				nextBlock = inWhichBlock(newpc, blocks, v->numBlocks);
				
				if (!mergeBasicBlocks(v, curBlock, nextBlock)) {
					return verifyErrorInVerifyMethod3b(v, curBlock, "jsr: error merging operand stacks");
				}
	
				/* TODO:
				 * args, we need to verify the RET block first ...
				 */
				for (;curIndex < v->numBlocks && blocks[curIndex] != nextBlock; curIndex++);
				assert (curIndex < v->numBlocks);
				continue;
				
			case RET:
				if (v->status[pc] & WIDE_MODDED) {
					n = pc + 1;
					n = getWord(code, n);
				} else {
					n = code[pc + 1];
				}
				
				if (!IS_ADDRESS(&curBlock->locals[n])) {
					return verifyErrorInVerifyMethod3b(v, curBlock, "ret instruction does not refer to a variable with type returnAddress");
				}
				
				newpc = curBlock->locals[n].tinfo;
				
				/* each instance of return address can only be used once */
				curBlock->locals[n] = *getTUNSTABLE();
				
				nextBlock = inWhichBlock(newpc, blocks, v->numBlocks);
				if (!mergeBasicBlocks(v, curBlock, nextBlock)) {
					return verifyErrorInVerifyMethod3b(v, curBlock, "error merging opstacks when returning from a subroutine");
				}

				/* 
				 * unmark this block as visited, so that the next
				 * entry is treated as a first time merge.
				 */
				blocks[curIndex]->status ^= VISITED;