analyze.c

一款拥有一定历史的C语言编译器

/*
 * C compiler
 * ==========
 *
 * Copyright 1989, 1990, 1991 Christoph van Wuellen.
 * Credits to Matthew Brandt.
 * All commercial rights reserved.
 *
 * This compiler may be redistributed as long there is no
 * commercial interest. The compiler must not be redistributed
 * without its full sources. This notice must stay intact.
 *
 * History:
 *
 * 1989   starting an 68000 C compiler, starting with material
 *        originally by M. Brandt
 * 1990   68000 C compiler further bug fixes
 *        started i386 port (December)
 * 1991   i386 port finished (January)
 *        further corrections in the front end and in the 68000
 *        code generator.
 *        The next port will be a SPARC port
 */

/*****************************************************************************
 *
 * This module will step through the parse tree and find all optimisable
 * expressions.  At present these expressions are limited to expressions
 * that are valid throughout the scope of the function. the list of
 * optimisable expressions is:
 *
 *      constants
 *      global and static addresses
 *      auto addresses
 *      contents of auto addresses.
 *
 * Contents of auto addresses are valid only if the address is never
 * referred to without dereferencing.
 *
 * Scan() will build a list of optimisable expressions which opt1 will
 * replace during the second optimization pass.
 *
 *****************************************************************************/

#include "chdr.h"
#ifdef CPU_DEFINED
#include "expr.h"
#include "cglbdec.h"
#include "proto.h"

/********************************************************** Type Definitions */

typedef int WEIGHT;		/* weighting of expression complexity */

/********************************************************** Static Variables */

static int regptr = 0;		/* index into reglst */
static SYM *reglst[REG_LIST];
static int autoptr = 0;		/* index into autolst */
static SYM *autolst[AUTO_LIST];
static CSE *olist;		/* list of optimisable expressions */

/*********************************************** Static Function Definitions */

static BOOL is_equalsym P_ ((const SYM *, const SYM *));
static CSE *searchnode P_ ((const EXPR *));
static CSE *enternode P_ ((const EXPR *, BOOL));
static CSE *voidauto P_ ((const EXPR *));
static void scannode P_ ((const EXPR *, BOOL));
static STMT *scan P_ ((STMT *));
static void bsort P_ ((CSE **));
static EXPR *repcsenode P_ ((EXPR *));
static STMT *repcse P_ ((STMT *));
static WEIGHT swapnode P_ ((EXPR *));
static STMT *swap P_ ((STMT *));

/*****************************************************************************/

void rel_autolst P0 (void)
{
    int i;

    for (i = 0; i < AUTO_LIST; i++)
    {
	autolst [i] = NIL_SYM;
    }
    autoptr = 0;
}

void rel_reglst P0 (void)
{
    int i;

    for (i = 0; i < REG_LIST; i++)
    {
	reglst [i] = NIL_SYM;
    }
    regptr = 0;
}

void addoptinfo P2 (SYM *, sp, STORAGE, sc)
{
    TYP    *tp = typeof (sp);

    switch (tp->type) {
    case bt_pointer32:
	if (is_array_type (tp) && sc != sc_parms) {
	    break;
	}
    /*lint -fallthrough*/
    case bt_bool:
    case bt_char:
    case bt_charu:
    case bt_uchar:
    case bt_schar:
    case bt_short:
    case bt_ushort:
    case bt_int16:
    case bt_uint16:
    case bt_int32:
    case bt_uint32:
    case bt_long:
    case bt_ulong:
    case bt_float:
    case bt_double:
	if (!is_volatile_qualified (tp)) {
	    switch (storageof (sp)) {
	    case sc_register:
		if (regptr < REG_LIST) {
		    reglst[regptr++] = sp;
		    DPRINTF (
			     (DEBUG_GLOBAL, "adding '%s' to reglst\n",
			      nameof (sp)));
		}
		break;
	    case sc_parms:
	    case sc_auto:
		if (autoptr < AUTO_LIST) {
		    autolst[autoptr++] = sp;
		    DPRINTF (
			     (DEBUG_GLOBAL, "adding '%s' to autolst\n",
			      nameof (sp)));
		}
		break;
	    default:
		break;
	    }
	}
	break;
    default:
	break;
    }
}

/*
 * Remove the expression from the register lists
 */
void deloptinfo P1 (const EXPR *, ep)
{
    int     i;

    assert (is_sym (ep));
    for (i = 0; i < autoptr; i++) {
	if (is_equalsym (autolst[i], ep->v.sp)) {
	    autolst[i] = NIL_SYM;
	    DPRINTF (
		     (DEBUG_GLOBAL, "removing '%s' from autolst\n",
		      nameof (ep->v.sp)));
	}
    }
    for (i = 0; i < regptr; i++) {
	if (is_equalsym (reglst[i], ep->v.sp)) {
#ifndef SYNTAX_CORRECT
	    message (ERR_ADDREGVAR, reglst[i]->name);
#endif /* SYNTAX_CORRECT */
	    reglst[i] = NIL_SYM;
	    DPRINTF ((DEBUG_GLOBAL, "removing '%s' from reglst\n",
		      nameof (ep->v.sp)));
	}
    }
}

/*****************************************************************************/

/*
 *   used as a parameter to walkstmt() when no action is to be
 *   performed on the expressions.
 */
static EXPR *null_expr P1 (EXPR *, ep)
{
    return ep;
}

/*
 *   used as a paremeter to walkstmt() when no action is to be
 *   performed on the statement.
 */
static STMT *null_stmt P1 (STMT *, stmt)
{
    return stmt;
}

/*****************************************************************************/

/*
 *   is_equalsym() will return TRUE if the symbols pointed to by sp1
 *   and sp2 are equivalent.
 */

static BOOL is_equalsym P2 (const SYM *, sp1, const SYM *, sp2)
{
    if (sp1 == NIL_SYM || sp2 == NIL_SYM) {
	return FALSE;
    }
    if (sp1 == sp2) {
	return TRUE;
    }
    if (storageof (sp1) != storageof (sp2)) {
	return FALSE;
    }
    switch (storageof (sp1)) {
    case sc_auto:
    case sc_parms:
    case sc_register:
	return (sp1->value.i == sp2->value.i);
    case sc_external:
    case sc_global:
	return (nameof (sp1) == nameof (sp2));
    default:
	return FALSE;
    }
}

/*
 *   is_equalnode() will return TRUE if the expressions pointed to by ep1
 *   and ep2 are equivalent.
 */
BOOL is_equalnode P2 (const EXPR *, ep1, const EXPR *, ep2)
{
    if (ep1 == NIL_EXPR || ep2 == NIL_EXPR) {
	return FALSE;
    }
    if (ep1->nodetype != ep2->nodetype) {
	return FALSE;
    }
    switch (ep1->nodetype) {
    case en_icon:
    case en_autocon:
	return (ep1->v.i == ep2->v.i);
    case en_labcon:
	return (ep1->v.l == ep2->v.l);
    case en_nacon:
    case en_global:
	return (ep1->v.str == ep2->v.str);
    case en_sym:
	return is_equalsym (ep1->v.sp, ep2->v.sp);
    case en_ref:
    case en_fieldref:
    case en_uminus:
    case en_cast:
	return is_equalnode (ep1->v.p[0], ep2->v.p[0]);
    case en_add:
    case en_sub:
	return is_equalnode (ep1->v.p[1], ep2->v.p[1]) &&
	    is_equalnode (ep1->v.p[0], ep2->v.p[0]);
    default:
	return FALSE;
    }
}


/*
 *   searchnode will search the common expression table for an entry that
 *   matches the node passed and return a pointer to it.
 */
static CSE *searchnode P1 (const EXPR *, ep)
{
    register CSE *csp;

    if (ep == NIL_EXPR) {
	return NIL_CSE;
    }
    for (csp = olist; csp != NIL_CSE; csp = csp->next) {
	if (is_equalnode (ep, csp->exp)) {
	    return csp;
	}
    }
    return NIL_CSE;
}

/*****************************************************************************/

/*
 *   returns the desirability of optimization for a subexpression.
 */
USES desire P1 (const CSE *, csp)
{
    const EXPR *ep = csp->exp;

    if (csp->voidf || (is_icon (ep) && ep->v.i < 32L && ep->v.i >= 0L))
	return (USES) 0;
    if (is_lvalue (ep)) {
	return (USES) ((int) csp->uses * 2);
    }
    return csp->uses;
}

/*
 *   bsort() implements a bubble sort on the expression list.
 */
static void bsort P1 (CSE **, lst)
{
    CSE    *csp1, *csp2;
    register USES uses;

    csp1 = *lst;
    if (csp1 == NIL_CSE || csp1->next == NIL_CSE) {
	return;
    }
    bsort (&(csp1->next));
    uses = desire (csp1);
    while ((csp1 != NIL_CSE) &&
	   (csp2 = csp1->next) != NIL_CSE && uses < desire (csp2)) {
	*lst = csp2;
	csp1->next = csp2->next;
	csp2->next = csp1;
	lst = &(csp2->next);
    }
}

/*****************************************************************************/

/*
 *   enternode() will enter a reference to an expression node into
 *   the common expression table.
 *
 *   duse is a flag indicating whether or not this reference will be
 *   dereferenced.
 */
static CSE *enternode P2 (const EXPR *, ep, BOOL, duse)
{
    CSE    *csp;

    if ((csp = searchnode (ep)) == NIL_CSE) {	/* add to tree */
	csp = (CSE *) xalloc (sizeof (CSE));

	csp->next = olist;
	csp->uses = (USES) 0;
	csp->duses = (USES) 0;
	csp->exp = copynode (ep);
	csp->voidf = FALSE;
	csp->reg = NO_REG;
	olist = csp;
	return csp;
    }
    /*
     *       Integer constants may be in the table with different sizes --
     *       keep the maximum size
     */
    if (is_icon (ep) && ep->etp->size > csp->exp->etp->size) {
	csp->exp->etp = ep->etp;
    }
    ++(csp->uses);
    if (duse) {
	++(csp->duses);
    }
    return csp;
}


/*
 *   voidauto() will void an auto dereference node which points to the
 *   same auto constant as ep.
 */

static CSE *voidauto P1 (const EXPR *, ep)
{
    CSE    *csp;

    for (csp = olist; csp != NIL_CSE; csp = csp->next) {
	if (is_lvalue (csp->exp) && is_equalnode (ep, csp->exp->v.p[0])) {
	    if (csp->voidf) {
		return NIL_CSE;
	    }
	    csp->voidf = TRUE;
	    return csp;
	}
    }
    return NIL_CSE;
}


/*
 *   scannode() will scan the expression pointed to by node for
 *   optimisable subexpressions.
 *
 *   When an optimisable expression is found it is entered into the tree.
 *   If a reference to an auto node is scanned the corresponding
 *   auto dereferenced node will be voided.
 *
 *   duse should be set if the expression will be dereferenced.
 */

static void scannode P2 (const EXPR *, ep, BOOL, duse)
{
    EXPR   *ep0;
    CSE    *csp, *csp1;

    if (ep == NIL_EXPR) {
	return;
    }
    switch (ep->nodetype) {
    case en_fcon:
    case en_str:
	break;
    case en_icon:
    case en_autocon:
    case en_sym:
	/*
	 *   look if the dereferenced use of the node is in the
	 *   list, remove it in this case.
	 */
	if ((csp = voidauto (ep)) != NIL_CSE) {
	    csp1 = enternode (ep, duse);
	    csp1->duses += csp->uses;
	    break;
	}
    /*lint -fallthrough*/
    case en_labcon:
    case en_global:
    case en_nacon:
	VOIDCAST enternode (ep, duse);
	break;
    case en_ref:
    case en_fieldref:
	ep0 = ep->v.p[0];
	if (is_sym (ep0) &&
	    (is_auto (ep0->v.sp) ||
	     is_parms (ep0->v.sp) || is_register (ep0->v.sp))) {
	    BOOL    first = (searchnode (ep) == NIL_CSE);

	    csp = enternode (ep, duse);
	    if (searchnode (ep0) != NIL_CSE) {
		/*
		 *   the non-dereferenced use of the auto node
		 *   is already in the list.
		 */
		csp->voidf = TRUE;
		scannode (ep0, TRUE);
	    } else if (first) {
		/*
		 *   look for register nodes
		 */
		int     i;
		SYM    *sp = ep0->v.sp;

		for (i = 0; i < regptr; ++i) {
		    if (is_equalsym (reglst[i], sp)) {
			csp->voidf--;	/* this is not in auto_lst */
			csp->uses += (USES) (90 * (100 - i));
			csp->duses += (USES) (30 * (100 - i));
			break;
		    }
		}

		/*
		 *   set voidf if the node is not in autolst
		 */
		csp->voidf++;
		for (i = 0; i < autoptr; ++i) {
		    if (is_equalsym (autolst[i], sp)) {
			csp->voidf--;
			break;
		    }
		}

		/*
		 *   Even if that item must not be put in a register,
		 *   it is legal to put its address therein
		 */
		if (csp->voidf) {
		    scannode (ep0, TRUE);
		}
	    }
	} else {
	    scannode (ep0, TRUE);
	}
	break;
    case en_add: