/*
 * 68K/386 32-bit C compiler.
 *
 * copyright (c) 1996, David Lindauer
 * 
 * This compiler is intended for educational use.  It may not be used
 * for profit without the express written consent of the author.
 *
 * It may be freely redistributed, as long as this notice remains intact
 * and sources are distributed along with any executables derived from them.
 *
 * The author is not responsible for damages, either direct or consequential,
 * that may arise from use of this software.
 *
 * V1.85 July 2000
 * David Lindauer, gclind01@starbase.spd.louisville.edu
 *
 * Credits to Mathew Brandt for original K&R C compiler
 *
 */
/*
 * iblock.c
 *
 * find blocks and do LCSE optimization.  Subroutine calls end blocks;
 * this allows the pointer analysis and GCSE routines to find a wider
 * range of CSEs.  LCSE pass creates lots of dead variables so,
 * we need another optimization to get rid of these later...
 *
 */
#include        <stdio.h>
#include				<malloc.h>
#include 				<string.h>
#include				"utype.h"	
#include				"cmdline.h"	
#include        "lists.h"
#include        "expr.h"
#include        "c.h"
#include				"iexpr.h"
#include				"iopt.h"
#include 				"diag.h"

extern int intsize;
extern int prm_optdead, prm_locsub;
TABLE tempsyms;
QUAD *intermed_head, *intermed_tail;
BLOCKLIST *blockhead, *blocktail;
int blocknum;
QUAD *intermed_head, *intermed_tail;
DAGLIST **name_hash=0,**ins_hash=0;
static short wasgoto = FALSE;

static void add_intermed(QUAD *new);

int equalnode(ENODE *node1, ENODE *node2)
/*
 *      equalnode will return 1 if the expressions pointed to by
 *      node1 and node2 are equivalent.
 */
{       if( node1 == 0 || node2 == 0 )
                return 0;
        if( node1->nodetype != node2->nodetype )
                return 0;
				switch (node1->nodetype) {
					case en_nalabcon: case en_nacon: case en_napccon:
						return(!strcmp(node1->v.p[0],node2->v.p[0]));
					case en_icon: case en_lcon: case en_iucon: case en_lucon: case en_ccon:
					case en_labcon: case en_autoreg: 
					case en_autocon: case en_absacon: case en_regref:
						return node1->v.i == node2->v.i;
					case en_tempref:
						return ((SYM *)(node1->v.sp))->value.i == ((SYM *)(node2->v.sp))->value.i;
					case en_fcon:
					case en_rcon:
					case en_lrcon:
						return node1->v.f == node2->v.f;
				}
        if( lvalue(node1))
					return equalnode(node1->v.p[0], node2->v.p[0]);
        return 0;
}
int equalimode(IMODE *ap1, IMODE *ap2)
/*
 * return true if the imodes match
 */
{
	if (ap1->mode && ap1->mode != ap2->mode)
		return FALSE;
	if (ap1->size && ap1->size != ap2->size)
		return FALSE;
	if ((ap1->offset->cflags | ap2->offset->cflags) & DF_VOL)
		return FALSE;
	return equalnode(ap1->offset,ap2->offset);
}
static short hash(BYTE *str, int len)
/*
 * hashing for dag nodes
 */
{
	int i;
	unsigned short v = 0;
	for (i=0; i < len; i++) {
		v = (v << 3) + (v >> 13) + (v >> 3) + (v << 13);
		v += str[i];
	}
	return v % DAGSIZE;
}
QUAD *LookupNVHash(BYTE *key, int size, DAGLIST **table)
{
	int hashval = hash(key,size);
	DAGLIST *list = table[hashval];
	while (list) {
		if (!memcmp(key,list->key,size))
			return list->rv;
		list = list->link;
	}
	return 0;
}
static void ReplaceHash(QUAD *rv, BYTE *key, int size, DAGLIST **table)
{
	int hashval = hash(key,size);
	DAGLIST **list = &table[hashval],**flist = list;
	DAGLIST *new;
	while (*list) {
		if (!memcmp(key,(*list)->key,size)) {
			(*list)->rv = rv;
			return;
		}
		list = *list;
	}
	new = oalloc(sizeof(DAGLIST));
	new->rv = rv;
	new->key = key;
	new->link = *flist;
	*flist = new;
}

static void add_intermed(QUAD *new)
/*
 *      add the icode quad to the icode list
 */
{       if( intermed_head == 0 )
                {
                intermed_head = intermed_tail = new;
                new->fwd = 0;
                new->back = 0;
                }
        else
                {
                new->fwd = 0;
                new->back = intermed_tail;
                intermed_tail->fwd = new;
                intermed_tail = new;
                }
}
QUAD *liveout(QUAD *node)
{
	QUAD *outnode;
	outnode = xalloc(sizeof(QUAD));
	outnode->dc.opcode = node->dc.opcode;
	outnode->ans = node->ans;
	outnode->dc.v = node->dc.v;
	outnode->dc.label = node->dc.label;
	if (node->livein & IM_LIVELEFT)
		outnode->dc.left = node->dc.left;
	else
		outnode->dc.left = ((QUAD *)node->dc.left)->ans;
	if (node->livein & IM_LIVERIGHT)
		outnode->dc.right = node->dc.right;
	else
		outnode->dc.right = ((QUAD *)node->dc.right)->ans;
	return outnode;
}
/*
 * this is the primary local CSE subroutine
 *
 * The steps are:
 *  1) replace any named operand IMODE with the QUAD it refers to.  Otherwise
 *     if there is none set the livein flag for the IMODE so it
 *     can be distinguished from quads later
 *  2) constant fold and algebra
 *  3) look up the resulting quad in the CSE table and replace the
 *     instruction with an assigment if it is there, otherwise
 *     enter the quad in the CSE table
 *  4) convert the resulting quad QUAD members back to IMODE members
 *  5) save the final QUAD back to the names table for use in step 1 of
 *     subsequent instructions
 *     
 * if local CSEs are disabled we simply don't put anything in the lookup
 * tables.
 *
 * if a volatile var is on the right-hand side we don't put the
 * CSE in the CSE table.
 *
 * if a variable on the left is volatile we create a temp variable
 * for the result and then assign the volatile to the temp.  This
 * prevents us from using a volatile as an intermediate.
 *
 *
 * by the time we get here, casts will have been assigned unique
 * operand values so they won't be CSE'd.  I may fix it some time in
 * the future.
 */
static void add_dag(QUAD *new)
{
	QUAD *node;
	QUAD *outnode;

	/* if the left-hand side is volatile, insert a temp so we can keep
	 * going with CSEs
	 */
	if (new->ans && new->ans->vol) {
		QUAD *tquad;
		IMODE *treg;
		treg = tempreg(new->ans->size,0);
		tquad = xalloc(sizeof(QUAD));
		tquad->ans = new->ans;
		tquad->dc.left = treg;
		tquad->dc.opcode = i_assn;
		new->ans = treg;
		add_dag(new);
		new = tquad;
	}
	if (!name_hash) {
		name_hash = oalloc(sizeof(void *)*DAGSIZE);
		ins_hash = oalloc(sizeof(void *)*DAGSIZE);
	}

	/* Transform the quad structure members from imodes to quads */
	node = LookupNVHash(&new->dc.left, sizeof(void*),name_hash);
	if (node) {
		new->dc.left = node;
	}
	else new->livein |= IM_LIVELEFT;
	node = LookupNVHash(&new->dc.right, sizeof(void*),name_hash);
	if (node) {
		new->dc.right = node;
	}
	else new->livein |= IM_LIVERIGHT;

	/* constant folding, now! */
	ConstantFold(new);

	/* Now replace the CSE or enter it into the table */
	node = LookupNVHash(new, sizeof(struct _basic_dag),ins_hash);
	if (!node) {
		if (prm_locsub)
			/* take care of volatiles by not registering volatile expressions
			 * in the CSE table.  At this point a temp var will already exist
			 * in the case that a volatile exists as the answer.
			 */
			if (new->ans && !(new->ans->vol || (new->dc.left && new->dc.left->vol && (new->livein & IM_LIVELEFT))
					|| (new->dc.right && new->dc.right->vol && (new->livein & IM_LIVERIGHT))))
		 		ReplaceHash(new, new, sizeof(struct _basic_dag),ins_hash);
		/* convert back to a quad structure and generate code */
		node = new;
		outnode = liveout(node);
		add_intermed(outnode);
	}
	else {
		outnode = xalloc(sizeof(QUAD));
		outnode->dc.opcode = i_assn;
		outnode->ans = new->ans;
		outnode->dc.left = node->ans;
		add_intermed(outnode);
	}
	/* Save the new node structure for later lookups 
   * always save constants even when no LCSE is to be done because it
   * is needed for constant-folding in subsequent instructions
   */
	if (new->ans && (prm_locsub || node->dc.opcode == i_icon || node->dc.opcode == i_fcon))
		ReplaceHash(node,&new->ans,sizeof(void *),name_hash);

}
static void flush_dag(void)
{
	int i;
	name_hash = ins_hash = 0;
	release_opt();
}

void addblock(int val)
/*
 * create a block
 */
{
	BLOCKLIST *list;
	BLOCK *block;

	QUAD *q;
	if (blockhead) {
		blocktail->block->tail = intermed_tail;
	}
	switch (val) {
		case i_ret:
		case i_rett:
			return;
	}		
	
	/* block statement gets included */
	q = xalloc(sizeof(QUAD));
	q->dc.opcode = i_block;
	q->ans = q->dc.right = 0;
	q->dc.label = blocknum;
	add_intermed(q);
	/* now make a basic block and add to the blocklist */
	block = xalloc(sizeof(BLOCK));
	list = xalloc(sizeof(BLOCK));
	list->link = 0;
	list->block = block;
  block->flowback = 0;
	block->flowfwd = 0;
	block->blocknum = blocknum++;
	if (blockhead == 0)
		blockhead = blocktail = list;
	else
		blocktail = blocktail->link = list;
	block->head = intermed_tail;
}
/*
 * intermed code poitners 
 */
void gen_label(int labno)
/*
 *      add a compiler generated label to the intermediate list.
 */
{       QUAD    *new;
				flush_dag();
				if (!wasgoto)
					addblock(i_label);
				wasgoto = FALSE;
        new = xalloc(sizeof(QUAD));
        new->dc.opcode = i_label;
        new->dc.label = labno;
        add_intermed(new);
}

void gen_icode(int op,IMODE *res,IMODE *left,IMODE *right)
/*
 *      generate a code sequence into the peep list.
 */
{       QUAD    *new;
				switch (op) {
					case i_ret:
					case i_rett:
						flush_dag();
					  break;
				}
	      new = xalloc(sizeof(QUAD));
        new->dc.opcode = op;
        new->dc.left = left;
        new->dc.right = right;
				new->ans = res;
        add_dag(new);
				switch (op) {
					case i_ret:
					case i_rett:
						flush_dag();
						addblock(op);
				}
				wasgoto = FALSE;

}
void gen_iiconst(IMODE *res,long val)
/*
 *      generate an integer constant sequence into the peep list.
 */
{       QUAD    *new;
	      new = xalloc(sizeof(QUAD));
        new->dc.opcode = i_icon;
				new->dc.v.i = val;
				new->ans = res;
        add_dag(new);
				wasgoto = FALSE;
}
void gen_ifconst(IMODE *res,double val)
/*
 *      generate an integer constant sequence into the peep list.
 */
{       QUAD    *new;
	      new = xalloc(sizeof(QUAD));
        new->dc.opcode = i_fcon;
				new->dc.v.f = val;
				new->ans = res;
        add_dag(new);
				wasgoto = FALSE;
}
void gen_igoto(long label)
/*
 *      generate a code sequence into the peep list.
 */
{       QUAD    *new;
				flush_dag();
        new = xalloc(sizeof(QUAD));
        new->dc.opcode = i_goto;
        new->dc.left = new->dc.right = new->ans = 0;
				new->dc.label = label;
        add_intermed(new);
				addblock(i_goto);
				wasgoto = TRUE;
}
void gen_idc(long label)
/*
 *      generate a code sequence into the peep list.
 */
{       QUAD   *new;
				flush_dag();
        new = xalloc(sizeof(QUAD));
        new->dc.opcode = i_dc;
        new->dc.left = new->dc.right = new->ans = 0;
				new->dc.label = label;
        add_intermed(new);
				wasgoto = FALSE;
}
void gen_icgoto(int op,long label,IMODE *left, IMODE *right)
/*
 *      generate a code sequence into the peep list.
 */
{       QUAD    *new;

        new = xalloc(sizeof(QUAD));
        new->dc.opcode = op;
        new->dc.left = left;
				new->dc.right = right;
				new->ans = 0;
				new->dc.label = label;
        add_dag(new);
				flush_dag();
				addblock(op);
				wasgoto = TRUE;
}
void gen_igosub(int op,IMODE *left)
/*
 *      generate a code sequence into the peep list.
 */
{       QUAD    *new;

        new = xalloc(sizeof(QUAD));
        new->dc.opcode = op;
        new->dc.left = left;
				new->dc.right = 0;
				new->ans = 0;
				new->dc.label = 0;
        add_dag(new);
				flush_dag();
				addblock(op);
				wasgoto = TRUE;
}
void gen_icode2(int op,IMODE *res,IMODE *left,IMODE *right,int label)
/*
 *      generate a code sequence into the peep list.
 */
{       QUAD    *new;
        new = xalloc(sizeof(QUAD));
        new->dc.opcode = op;
        new->dc.left = left;
        new->dc.right = right;
				new->ans = res;
				new->dc.label = label;
        add_dag(new);
				flush_dag();
				wasgoto = FALSE;
}
void gen_line(SNODE *stmt)
/*
 * generate a line number statement 
 */
{
				QUAD *new;
        new = xalloc(sizeof(QUAD));
				new->dc.opcode = i_line;
				new->dc.left = (IMODE *)stmt->label;
				new->dc.label = (long)stmt->exp;
				add_intermed(new);
}
void gen_asm(SNODE *stmt)
/*
 * generate an ASM statement
 */
{
				QUAD *new;
        new = xalloc(sizeof(QUAD));
				new->dc.opcode = i_passthrough;
				new->dc.left = (IMODE *)stmt->exp;
				flush_dag();
				add_intermed(new);
}
void gen_nodag(int op,IMODE *res,IMODE *left,IMODE *right)
/*
 *      generate a code sequence into the peep list.
 */
{       QUAD    *new;
	      new = xalloc(sizeof(QUAD));
        new->dc.opcode = op;
        new->dc.left = left;
        new->dc.right = right;
				new->ans = res;
        add_intermed(new);
				wasgoto = FALSE;

}
