DataMuseum.dk

top - metrics - download

    Length: 8609 (0x21a1)
    Types: TextFile
    Names: »blocks.c«

└─⟦9ae75bfbd⟧ Bits:30007242 EUUGD3: Starter Kit
    └─⟦3f75c1919⟧ »EurOpenD3/utils/decomp.tar.Z« 
        └─⟦510c4d5ee⟧ 
            └─⟦this⟧ »decomp/blocks.c« 

TextFile

/*
 * Module: blocks.c
 *
 * Author: J. Reuter
 *
 * The functions in this module analyze a contiguous block of code
 * comprising a function, construct a directed graph of basic blocks
 * from the code, and perform trivial simplification of the graph.
 */

#include "defs.h"
#include "machine.h"
#include "labeltab.h"
#include "objfile.h"
#include "vartab.h"
#include "nodes.h"
#include <setjmp.h>

extern jmp_buf badbranch;

static int op_argval[6];

/*
 * blocks builds an array (node_array) of the basic blocks
 * contained in the code section.  Branches to unconditional
 * branches (these happen often because of the byte-offset of
 * conditional branches) are converted into branches to the
 * final destination during this pass.  The node arcs are converted
 * from addresses to node_array indices.
 */
blocks( start_address, end_address )
register address start_address, end_address;
{
    find_blocks( start_address, end_address ); /* find the basic blocks */
    array_nodes();		/* make an array of the blocks */
    rem_ubranch();		/* remove second level branches */
}

/*
 * find_blocks makes a pass through the code and finds the basic
 * blocks by looking for branches and entry points recorded in the
 * label table by the previous pass.
 */
static
find_blocks( start_address, end_address )
address start_address, end_address;
{
    unsigned char ins;
    int is_if = 0;
    int prev_is_if;
    register address cur_address;
    register address prev_address;
    register address node_entry;
    register address branch_address;
    register struct node *node;
    address insaddr;
    unsigned char mode;
    register int argtype, amode, argno, argval;
    register int rn, type;
    short offset;
    struct llb *l;
    int is_branch;

    /* initialize pass */

    /* get the first (in address order) branch target */
    l = llb_first();

    cur_address = start_address;
    node_entry = cur_address;

    /* loop across all the instructions in this function */
    while ( cur_address < end_address ) {

	prev_address = cur_address;
	is_branch = FALSE;

	while ( l->l_address <= cur_address )
	    l = llb_next();

	prev_is_if = is_if;
	ins = get_byte( cur_address );
	is_if = ( ins == O_TSTF || ins == O_TSTD || ins == O_TSTB ||
		 ins == O_TSTW || ins == O_TSTL || ins == O_CMPF ||
		 ins == O_CMPD || ins == O_CMPB || ins == O_CMPW ||
		 ins == O_CMPL || ins == O_CMPV || ins == O_CMPZV );
	cur_address += 1;

	/* process each instruction operand, filling op_argval */
	for (argno = 0; argno < opcode[ins].numargs; argno++) {

	    argtype = opcode[ins].argtype[argno];
	    if (is_branch_disp(argtype)) {
		mode = 0xAF + ( (typelen(argtype) & ~T_UNSIGNED) << 4);
		is_branch = TRUE;
	    } else {
		mode = get_byte( cur_address );
		cur_address += 1;
	    }

	    rn = regnm( mode );
	    type = typelen( argtype );
	    amode = addrmode(mode);

	    switch (amode) {
	    case LITSHORT:
	    case LITUPTO31:
	    case LITUPTO47:
	    case LITUPTO63:
		argval = mode;
		break;

	    case INDEX:
		argno--;
		break;

	    case REG:
	    case REGDEF:
	    case AUTODEC:
		break;

	    case AUTOINC:
		if ( rn != PC ) {
		    ;
		} else {
		    /* immediate values */
		    switch ( type & ~T_UNSIGNED ) {
		    case TYPB:
			argval = getdisp(cur_address, 1, rn, amode);
			cur_address += 1;
			break;

		    case TYPW:
			argval = getdisp(cur_address, 2, rn, amode);
			cur_address += 2;
			break;

		    case TYPL:
			argval = getdisp(cur_address, 4, rn, amode);
			cur_address += 4;
			break;

		    default:
			printf( "ERR: strange-autoinc %d\n", type );
			break;
		    }
		}
		break;

	    case AUTOINCDEF:
		if ( rn == PC ) {
		    /* immediate deferred */
		    argval = getdisp(cur_address, 4, rn, amode);
		    cur_address += 4;
		} else {
		    ;
		}
		break;

	    case BYTEDISP:
		argval = getdisp(cur_address, 1, rn, amode);
		cur_address += 1;
		break;

	    case BYTEDISPDEF:
		argval = getdisp(cur_address, 1, rn, amode);
		cur_address += 1;
		break;

	    case WORDDISP:
		argval = getdisp(cur_address, 2, rn, amode);
		cur_address += 2;
		break;

	    case WORDDISPDEF:
		argval = getdisp(cur_address, 2, rn, amode);
		cur_address += 2;
		break;

	    case LONGDISP:
		argval = getdisp(cur_address, 4, rn, amode);
		cur_address += 4;
		break;

	    case LONGDISPDEF:
		argval = getdisp(cur_address, 4, rn, amode);
		cur_address += 4;
		break;
	    }
	    if ( is_branch_disp(argtype) )
		branch_address = argval;

	    op_argval[argno] = argval;
	}

	if (ins == O_CASEB || ins == O_CASEW || ins == O_CASEL) {

	    /* case statements */
	    /* arc 0 is flow exit, arc 1 to argno+1 are case exits */
	    node = get_node( argval + 2 );
	    insaddr = cur_address;

	    for ( argno = 0; argno <= argval; argno++ ) {
		offset = get_word( cur_address );
		cur_address += 2;
		node->arcs[argno + 1] = offset + insaddr;
	    }

	    node->node_type = N_CASE;
	    node->start_address = node_entry;
	    node->end_address = cur_address;
	    node->num_arcs = argval + 2;
	    node->arcs[0] = cur_address; /* flow exit */
	    node_entry = cur_address;
	    node->varpart[V_BASE] = op_argval[1];
	    node->varpart[V_LIMIT] = op_argval[2];

	} else if ( is_branch && ( ins == O_BRB || ins == O_BRW ) ) {

	    /* unconditional branch */
	    /* arc 0 is branch exit */

	    /* currently does not deal with JMP instructions */

	    /*
	     * if this is an unconditional branch at an entry point
	     * then start_address == end_address
	     */
	    node = get_node( 1 );
	    node->node_type = N_FLOW;
	    node->start_address = node_entry;
	    node->end_address = prev_address;
	    node->num_arcs = 1;
	    node->arcs[0] = branch_address;
	    node_entry = cur_address;

	} else if ( is_branch ) {

	    /* conditional branch */
	    /* arc 0 is flow exit, arc 1 is branch exit */

	    if (opcode[ins].coptype == BBRANCH && prev_address != node_entry) {

		node = get_node( 1 );
		node->node_type = N_FLOW;
		node->start_address = node_entry;
		node->end_address = prev_address;
		node->num_arcs = 1;
		node->arcs[0] = prev_address;
		node_entry = prev_address;
	    }

	    node = get_node( 2 );
	    if ( prev_is_if || opcode[ins].coptype == BBRANCH )
		node->node_type = N_IF;
	    else
		node->node_type = N_BRANCH;
	    node->start_address = node_entry;
	    node->end_address = cur_address;
	    node->num_arcs = 2;
	    node->arcs[THEN_ARC] = branch_address;
	    node->arcs[ELSE_ARC] = cur_address;
	    node->varpart[V_NEGATE] = FALSE;
	    node_entry = cur_address;

	} else if ( ins == O_RET || ins == O_RSB || ins == O_HALT ) {

	    /* ret or rsb instruction */
	    /* no exit arcs */

	    node = get_node( 0 );
	    node->node_type = N_END;
	    node->start_address = node_entry;
	    node->end_address = cur_address;
	    node->num_arcs = 0;
	    node_entry = cur_address;

	} else if ( cur_address == l->l_address ||
		   (is_if && prev_address != node_entry) ) {

	    /* entry point with no branch */
	    /* arc 0 is flow exit */

	    node = get_node( 1 );
	    node->node_type = N_FLOW;
	    node->start_address = node_entry;
	    if ( is_if && prev_address != node_entry ) {
		node->end_address = prev_address;
		node_entry = prev_address;
		node->arcs[0] = prev_address;
	    } else {
		node->end_address = cur_address;
		node_entry = cur_address;
		node->arcs[0] = cur_address;
	    }
	    node->num_arcs = 1;
	}
    }
    /* no more code in function */
    if ( cur_address > node_entry ) {
	fprintf( stderr, "Dangling function end\n" );
	longjmp( badbranch, 1 );
    }
}

/*
 * Print the displacement of an instruction that uses displacement
 * addressing.
 */

static int
getdisp(obj_address, nbytes, rn, mode)
register address obj_address;
register int nbytes;
register int rn;
register int mode;
{
    register int argval;

    switch (nbytes) {
    case 1:
	argval = get_byte( obj_address );
	break;

    case 2:
	argval = get_word( obj_address );
	break;

    case 4:
	argval = get_long( obj_address );
	break;
    }
    if (rn == PC && mode >= BYTEDISP) {
	argval += obj_address + nbytes;
    }
    return argval;
}

/*
 * rem_ubranch converts arcs leading to unconditional branches into
 * arcs leading to the final branch destination.
 */
static
rem_ubranch()
{
    register struct node *n, *m;
    register int i, j;

    for ( i = 0; i < node_count; i++ ) {
	n = node_array[i];
	for ( j = 0; j < n->num_arcs; j++ ) {

	    m = node_array[n->arcs[j]];
	    while ( m->start_address == m->end_address &&
		   m->node_type == N_FLOW ) {
		       n->arcs[j] = m->arcs[0];
		       m = node_array[n->arcs[j]];
	    }
	}
    }
}