/*	ite.c

	Basic operations on ite objects
*/

#include	"main.h"
#include	"mesg.h"
#include	"ite.h"
#include	"fsm.h"
#include	<stdio.h>

ite	ites[MAXITE];		/* ITEs */
int	itep = PEMEM;		/* First free ites[] entry */
int	bitp = 2;		/* Next bit of mem to allocate */
int	pemem = PEMEM;		/* Default PEMEM start */
int	ite1 = 1;		/* ITE of constant 1:  either 1 or NOTITE */
int	beginite = PEMEM;	/* Start of current ITE block */
int	itecounter = 0;		/* Total ites generated */

/* The following is assumed to be initialized to zero by C */
static struct _hash {	/* Unique hash table */
	int	serial;	/* Block it is valid in */
	int	itex;	/* ITE index */
} itehash[MAXBLK];

static int serial = 1;	/* Current block serial number */

#define	HASHITE(a,b,c) \
	MODBLK((a * 13) + (b * 217) + (c * 527))

static void
live(register int i)
{
	/* Walk ite DAG marking things live */
	i = POSITE(i);

	while (ites[i].op == ITEITE) {
		ites[i].op = ITELIVE;
		live(ites[i].a);
		live(ites[i].b);
		i = POSITE(ites[i].c);
	}
}

static void
packlive(void)
{
	/* Eliminate all dead ites between begin and itep-1 */
	register int i, j, k;
	register int begin = states[statep].beginite;

	/* First, mark as live any ITEs used in state control */
	for (i=0; i<states[statep].ifgos; ++i) {
		live(states[statep].ifgo[i].ifite);
	}

	/* Then do the same for ITEs used by live stores */
	for (i=begin; i<itep; ++i) {
		if (ites[i].op == ITEST) {
			live(ites[i].a);
		}
	}

	/* Renumber live using hash table to record new places...
	   this has the side effect of clobbering hash entries.
	   However, it's harmless because it never touches the
	   serial numbers and they'll mark everything as obsolete
	   before the next block gets started.
	*/
	j = begin;
	for (i=begin; i<itep; ++i) {
		switch (ites[i].op) {
		case ITELIVE:
			itehash[i-begin].itex = j;
			ites[j].op = ITEITE;
			k = POSITE(ites[i].a);
			ites[j].a = ((ites[i].a & NOTITE) |
				     (ITEISVAR(k) ? k :
				      itehash[k-begin].itex));
			k = POSITE(ites[i].b);
			ites[j].b = ((ites[i].b & NOTITE) |
				     (ITEISVAR(k) ? k :
				      itehash[k-begin].itex));
			k = POSITE(ites[i].c);
			ites[j].c = ((ites[i].c & NOTITE) |
				     (ITEISVAR(k) ? k :
				      itehash[k-begin].itex));
			++j;
			break;
		case ITEST:
			ites[j].op = ITEST;
			k = POSITE(ites[i].a);
			ites[j].a = ((ites[i].a & NOTITE) |
				     (ITEISVAR(k) ? k :
				      itehash[k-begin].itex));
			ites[j].b = ites[i].b;
			++j;
			break;
		}
	}

	/* Relocate ITEs used in state control */
	for (i=0; i<states[statep].ifgos; ++i) {
		k = states[statep].ifgo[i].ifite;
		if (!ITEISVAR(k)) {
			states[statep].ifgo[i].ifite =
				((k & NOTITE) |
				 (itehash[POSITE(k) - begin].itex));
		}
	}

	/* Everything before j is live */
	itep = j;
}

void
newblock(void)
{
	register int i;

	/* Pack the current state */
	packlive();

	/* Close the state & enter new one */
	closestate();
	mkstate();

	/* Make var values unknown */
	ites[0].a = ITE0;
	ites[0].b = ITEX;
	for (i=1; i<pemem; ++i) {
		ites[i].a = ITEX;	/* Value unknown */
		ites[i].b = ITEX;	/* No previous store */
	}

	/* Bump block serial number (really follows statep) */
	++serial;
}

static inline int
splitleft(register int x,
register int m)
{
	if (ITE1 != NOTITE) {
		if (x == m) {
			return(1);
		}
		if ((!ITEISVAR(x)) &&
		    (ites[x].a == m)) {
			return(ites[x].b);
		}
		return(x);
	}

	if (POSITE(x) == POSITE(m)) {
		return((x ^ m) ^ NOTITE);
	}
	if ((!ITEISVAR(x)) &&
	    (POSITE(ites[POSITE(x)].a) == POSITE(m))) {
		return((ites[POSITE(x)].a == m) ?
		       (ites[POSITE(x)].b ^ (NOTITE & x)):
		       (ites[POSITE(x)].c ^ (NOTITE & x)));
	}
	return(x);
}

static inline int
splitright(register int x,
register int m)
{
	if (ITE1 != NOTITE) {
		if (x == m) {
			return(0);
		}
		if ((!ITEISVAR(x)) &&
		    (ites[x].a == m)) {
			return(ites[x].c);
		}
	return(x);
	}

	if (POSITE(x) == POSITE(m)) {
		return(x ^ m);
	}
	if ((!ITEISVAR(x)) &&
	    (POSITE(ites[POSITE(x)].a) == POSITE(m))) {
		return((ites[POSITE(x)].a == m) ?
		       (ites[POSITE(x)].c ^ (NOTITE & x)) :
		       (ites[POSITE(x)].b ^ (NOTITE & x)));
	}
	return(x);
}

static inline int
uniq(register int a,
register int b,
register int c)
{
	/* Use hash table to find duplicate ITE */
	register int i;

	if (ITE1 == NOTITE) {
		/* Search for negative sense version */
		i = HASHITE(a, (b ^ NOTITE), (c ^ NOTITE));

		while (itehash[i].serial == serial) {
			register int j = itehash[i].itex;

			if ((ites[j].a == a) &&
			    (ites[j].b == (b ^ NOTITE)) &&
			    (ites[j].c == (c ^ NOTITE))) {
				return(j ^ NOTITE);
			}

			/* Linear rehash */
			i = MODBLK(i + 1);
		}
	}

	/* Search for positive sense version */
	i = HASHITE(a, b, c);

	while (itehash[i].serial == serial) {
		register int j = itehash[i].itex;

		if ((ites[j].a == a) &&
		    (ites[j].b == b) &&
		    (ites[j].c == c)) {
			return(j);
		}

		/* Linear rehash */
		i = MODBLK(i + 1);
	}

	if (verbose > 2) {
		fprintf(stderr,
			"uniq(%s%d, %s%d, %s%d) -> %d\n",
			((a&NOTITE)?"~":""),POSITE(a),
			((b&NOTITE)?"~":""),POSITE(b),
			((c&NOTITE)?"~":""),POSITE(c),
			itep);
	}

	/* Make new entry */
	++itecounter;
	itehash[i].serial = serial;
	itehash[i].itex = itep;
	ites[itep].op = ITEITE;
	ites[itep].a = a;
	ites[itep].b = b;
	ites[itep].c = c;
	return(itep++);
}

static inline int
eqnot(register int x,
register int y)
{
	/* Return true iff x = NOT(y) */
	if (ITE1 == NOTITE) {
		return((x ^ y) == NOTITE);
	}

	if ((x == 0) && (y == 1)) return(1);
	if ((x == 1) && (y == 0)) return(1);
	if ((!ITEISVAR(y)) &&
	    (x == ites[y].a) &&
	    (ites[y].b == 0) &&
	    (ites[y].c == 1)) return(1);
	if ((!ITEISVAR(x)) &&
	    (y == ites[x].a) &&
	    (ites[x].b == 0) &&
	    (ites[x].c == 1)) return(1);
	if ((!ITEISVAR(x)) &&
	    (!ITEISVAR(y)) &&
	    (ites[x].a == ites[y].a)) {
		if (!eqnot(ites[x].b, ites[y].b)) return(0);
		return(eqnot(ites[x].c, ites[y].c));
	}
	return(0);
}

int
mkite(register int a,
register int b,
register int c)
{
	register int t, u, am, bm, cm, m, left, right;
	register int notmask = 0;

	if (verbose > 2) {
		fprintf(stderr,
			"mkite(%s%d, %s%d, %s%d)\n",
			((a&NOTITE)?"~":""),POSITE(a),
			((b&NOTITE)?"~":""),POSITE(b),
			((c&NOTITE)?"~":""),POSITE(c));
	}

	/* Simplifications */
	if (a == b) b = ITE1;
	if (a == c) c = ITE0;
	if (eqnot(a, b)) b = ITE0;
	if (eqnot(a, c)) c = ITE1;

	/* Stopping conditions */
	if (a == ITE1) return(b);	/* Karplus condition 5 */
	if (a == ITE0) return(c);	/* Karplus condition 5 */
	if (b == c) return(b);		/* Karplus condition 2 */
	if ((b == ITE1) && (c == ITE0)) return(a);		/* condition 4 */
	if (ITE1 == NOTITE) {
		/* condition 4 */
		if ((b == ITE0) && (c == ITE1)) return(a ^ NOTITE);
	}

	/* Karplus normal form condition 1 */
	am = (ITEISVAR(a) ? a : ites[POSITE(a)].a);
	bm = (ITEISVAR(b) ? b : ites[POSITE(b)].a);
	cm = (ITEISVAR(c) ? c : ites[POSITE(c)].a);
	m = ((POSITE(am) > POSITE(bm)) ? am : bm);
	m = ((POSITE(m) > POSITE(cm)) ? m : cm);
	if (ITE1 != NOTITE) {
		left = mkite(splitleft(a, m),
			     splitleft(b, m),
			     splitleft(c,m));
		right = mkite(splitright(a, m),
			      splitright(b, m),
			      splitright(c, m));
		if ((m != a) ||
		    (left != b) ||
		    (right != c)) return(mkite(m, left, right));
	} else {
		if (POSITE(m) != POSITE(am)) {
			/* Order is wrong, do like Bryant */
			left = mkite(splitleft(a, m),
				     splitleft(b, m),
				     splitleft(c,m));
			right = mkite(splitright(a, m),
				      splitright(b, m),
				      splitright(c, m));

			/* Bryant's normal form didn't use not,
			   so he didn't need to order left and right...
			   but Karplus does....  force condition 3
			*/
			t = (ITEISVAR(left) ? left : ites[POSITE(left)].a);
			u = (ITEISVAR(right) ? right : ites[POSITE(right)].a);
			if ((POSITE(t) < POSITE(u)) ||
			    ((POSITE(t) == POSITE(u)) && (t < u))) {
				t = left;
				left = right;
				right = t;
				m ^= NOTITE;
			}
		} else {
			m = a;
			left = b;
			right = c;
		}

		/* Condition 6 */
		if ((!ITEISVAR(left)) &&
		    (!ITEISVAR(right)) &&
		    (ites[left].b == ites[right].b) &&
		    (ites[left].c == ites[right].c)) {
			m = mkite(m, ites[left].a, ites[right].b);
			left = ites[left].b;
			right = ites[right].c;
		}

		/* Condition 7 */
		if (!ITEISVAR(left)) {
			if (ites[left].c == right) {
				m = mkite(m, ites[left].a, ITE0);
				left = ites[left].b;
			} else if (ites[left].b == right) {
				m = mkite(m, ites[left].a, ITE1);
				right = ites[left].c;
				left = ites[left].b;
			}
		}

		/* Not needed? */
		if ((left & right) & NOTITE) {
			notmask = NOTITE;
			left = POSITE(left);
			right = POSITE(right);
		}
	}

	if (verbose > 1) {
		fprintf(stderr,
			"uniq(%s%d, %s%d, %s%d)\n",
			((m&NOTITE)?"~":""),POSITE(m),
			((left&NOTITE)?"~":""),POSITE(left),
			((right&NOTITE)?"~":""),POSITE(right));
	}

	return(uniq(m, left, right) ^ notmask);
}

void
mkst(register int var,
register int val)
{
	register int i = itep;

	if (!ITEISVAR(var)) {
		error("attempt to store into a value");
	}
	if (POSITE(var) == ITE0) {
		error("attempt to store into a constant");
	}
	if (var & NOTITE) {
		error("attempt to store into complement of a register");
	}

	/* Another ITE...  well, sort-of */
	++itecounter;

	/* All stores into IO devices are live */
	if (ites[var].op == ITEIO) {
		ites[itep].op = ITEST;
		ites[itep].a = val;
		ites[itep].b = var;
		ites[var].a = var;
		ites[var].b = itep;
		++itep;
	} else {
		/* Store into a var kills previous store */
		if (ites[var].b != ITEX) {
			ites[ites[var].b].op = ITENULL;
			ites[var].b = ITEX;
		}

		/* Don't load your value just to store into yourself */
		if (val != var) {
			/* Make new entry */
			ites[itep].op = ITEST;
			ites[itep].a = val;
			ites[itep].b = var;
			ites[var].a = val;
			ites[var].b = itep;
			++itep;
		} else {
			ites[var].a = var;
		}
	}
}

void
mkkill(register int var)
{
	if (ITEISVAR(var)) {
		var = POSITE(var);
		if (ites[var].b != ITEX) {
			ites[POSITE(ites[var].b)].op = ITENULL;
			ites[var].b = ITEX;
		}
	}
}

void
codegen(void)
{
	++serial;
	if (verbose > -1) {
		fprintf(stderr,
			"Total of %d ITEs created, %d kept\n",
			itecounter,
			(itep - pemem));
	}
}

int
itenot(register int a)
{
	if (ITE1 == NOTITE) {
		/* Very easy... and no code needed! */
		return(a ^ NOTITE);
	}

	/* Apply simplifications if we can */
	if (a == 0) return(1);
	if (a == 1) return(0);

	/* Double negative? */
	if ((!ITEISVAR(a)) &&
	    (ites[a].b == 0) &&
	    (ites[a].c == 1)) {
		return(ites[a].a);
	}

	/* Oh well; just do it */
	return(mkite(a, 0 , 1));
}

int
iteor(register int a,
register int b)
{
	/* Apply simplifications if we can */
	if ((a == ITE1) || (b == ITE1)) return(ITE1);
	if (a == ITE0) return(b);
	if (b == ITE0) return(a);
	if (a == b) return(a);

	/* Otherwise, make ite using prefered order */
	if (POSITE(a) > POSITE(b)) {
		return(mkite(a, ITE1, b));
	}
	return(mkite(b, ITE1, a));
}

int
itexor(register int a,
register int b)
{
	/* Apply simplifications if we can */
	if (a == ITE0) return(b);
	if (b == ITE0) return(a);
	if (a == ITE1) return(itenot(b));
	if (b == ITE1) return(itenot(a));
	if (a == b) return(ITE0);

	/* Otherwise, make ite using prefered order */
	if (POSITE(a) > POSITE(b)) {
		return(mkite(a, itenot(b), b));
	}
	return(mkite(b, itenot(a), a));
}

int
iteand(register int a,
register int b)
{
	/* Apply simplifications if we can */
	if ((a == ITE0) || (b == ITE0)) return(ITE0);
	if (a == ITE1) return(b);
	if (b == ITE1) return(a);
	if (a == b) return(a);

	/* Otherwise, make ite using prefered order */
	if (POSITE(a) > POSITE(b)) {
		return(mkite(a, b, 0));
	}
	return(mkite(b, a, 0));
}