#include "c.h"
#define iscall(p) (generic((p)->op) == CALL \
	|| IR->mulops_calls \
	&& ((p)->op==DIV+I || (p)->op==MOD+I || (p)->op==MUL+I \
	||  (p)->op==DIV+U || (p)->op==MOD+U || (p)->op==MUL+U))
static Node     forest;
static struct dag {
	struct node     node;
	struct dag     *hlink;
}              *buckets[16];
int             nodecount,FunctionNodes;
static int      depth = 0;
static Tree     firstarg;
static Node    *tail;

static Node asgnnode ARGS((Symbol, Node));
static struct dag *dagnode ARGS((int, Node, Node, Symbol));
static void fixup ARGS((Node));
static void labelnode ARGS((int));
static void list ARGS((Node));
static void kill ARGS((Symbol));
static Node node ARGS((int, Node, Node, Symbol));
static void printdag1 ARGS((Node, int, int));
static void printnode ARGS((Node, int, int));
void reset ARGS((void));
static Node tmpnode ARGS((Node));
static void Dagtypestab ARGS((Symbol, void *));
static Node undag ARGS((Node));
static Node visit ARGS((Node, int));
static void unlist ARGS((void));
Symbol   equated(Symbol p);

void            walk(Tree tp, int tlab, int flab)
{
	listnodes(tp, tlab, flab);
	if (forest) {
		code(Gen)->u.forest = forest->link;
		forest->link = NULL;
		forest = NULL;
	}
	reset();
	deallocate(STMT);
}

static Node     node(int op,Node l,Node r,Symbol sym)
{
	int             i;
	struct dag     *p;

	i = (opindex(op) ^ ((unsigned) sym >> 2)) & (NELEMS(buckets) - 1);
	for (p = buckets[i]; p; p = p->hlink)
		if (p->node.op == op && p->node.syms[0] == sym
				&& p->node.kids[0] == l && p->node.kids[1] == r)
			return &p->node;
	p = dagnode(op, l, r, sym);
	p->hlink = buckets[i];
	buckets[i] = p;
	++nodecount;
	return &p->node;
}

static struct dag *dagnode(int op,Node l,Node r,Symbol sym)
{
	struct dag     *p;

	NEW0(p, FUNC);
	p->node.op = (short)op;
	if ((p->node.kids[0] = l) != NULL)
		++l->count;
	if ((p->node.kids[1] = r) != NULL)
		++r->count;
	p->node.syms[0] = sym;
	return p;
}

static void SimplifyCond(Tree p)
{
	if (p->kids[1] && p->kids[1]->op == RIGHT && p->kids[1]->kids[0] &&
		p->kids[1]->kids[0]->op == ASGNI && p->kids[1]->kids[1] &&
		p->kids[1]->kids[1]->op == ASGNI) {
		/*
		Try to optimize the constructs of nested ?:
		a = (cond) ? (cond ? expr1 : expr2) : expr3;
		*/
		Tree tmp10 = p->kids[1]->kids[0];
		Tree tmp11 = p->kids[1]->kids[1];
//			printtree(tmp10,2);
//			printtree(tmp11,2);
		if (tmp10->kids[1] && tmp10->kids[1]->op == COND) {
			Tree tmp101 = tmp10->kids[1];
			if (tmp101->kids[1] && tmp101->kids[1]->op == RIGHT) {
				Tree tmp1010 = tmp101->kids[1]->kids[0];
				Tree tmp1011 = tmp101->kids[1]->kids[1];
				Symbol s1 = tmp10->kids[0]->u.sym;
				Symbol s2 = tmp11->kids[0]->u.sym;
				Symbol s0 = p->u.sym;

				if (s1 == s2 && s1->temporary && s1->generated) {
					if (s0)
						s1 = s0;
					tmp1010->kids[0]->u.sym = s1;
					tmp1011->kids[0]->u.sym = s1;
					tmp101->u.sym = s1;
//						printf("toto\n");
				}
			}
		}
		else if (tmp11->kids[1] && tmp11->kids[1]->op == COND) {
			Tree tmp101 = tmp11->kids[1];
			if (tmp101->kids[1] && tmp101->kids[1]->op == RIGHT) {
				Tree tmp1010 = tmp101->kids[1]->kids[0];
				Tree tmp1011 = tmp101->kids[1]->kids[1];
				Symbol s1 = tmp10->kids[0]->u.sym;
				Symbol s2 = tmp11->kids[0]->u.sym;
				Symbol s0 = p->u.sym;

				if (s1 == s2 && s1->temporary && s1->generated) {
					if (s0)
						s1 = s0;
					tmp1010->kids[0]->u.sym = s1;
					tmp1011->kids[0]->u.sym = s1;
					tmp101->u.sym = s1;
//						printf("toto *1*\n");
				}
			}
		}
	}
}

Node            newnode(int op,Node l,Node r,Symbol sym)
{
	return &dagnode(op, l, r, sym)->node;
}
static void     kill(Symbol p)
{
	int             i;
	struct dag    **q;

	for (i = 0; i < NELEMS(buckets); i++)
		for (q = &buckets[i]; *q;)
			if (generic((*q)->node.op) == INDIR &&
					(!isaddrop((*q)->node.kids[0]->op)
					|| (*q)->node.kids[0]->syms[0] == p)) {
				*q = (*q)->hlink;
				--nodecount;
			}
			else
				q = &(*q)->hlink;
}
void     reset(void)
{
	if (nodecount > 0)
		memset(buckets, 0, sizeof buckets);
	FunctionNodes += nodecount;
	nodecount = 0;
}

int hasArgs =0;
Node            listnodes(Tree tp, int tlab, int flab)
{
	Node            p = NULL, l, r;

	assert(tlab || flab || tlab == 0 && flab == 0);
	if (tp == NULL)
		return NULL;
	if (tp->node)
		return tp->node;
	switch (generic(tp->op)) {
	case AND:{
			if (depth++ == 0)
				reset();
			if (flab) {
				listnodes(tp->kids[0], 0, flab);
				listnodes(tp->kids[1], 0, flab);
			}
			else {
				flab = genlabel(1);
				listnodes(tp->kids[0], 0, flab);
				listnodes(tp->kids[1], tlab, 0);
				labelnode(flab);
			}
			depth--;
		} break;
	case OR:{
			if (depth++ == 0)
				reset();
			if (tlab) {
				listnodes(tp->kids[0], tlab, 0);
				listnodes(tp->kids[1], tlab, 0);
			}
			else {
				tlab = genlabel(1);
				listnodes(tp->kids[0], tlab, 0);
				listnodes(tp->kids[1], 0, flab);
				labelnode(tlab);
			}
			depth--;
		} break;
	case NOT:{
			return listnodes(tp->kids[0], flab, tlab);
		}
	case COND:{
			Tree            q = tp->kids[1];
			assert(tlab == 0 && flab == 0);
			if (OptimizeFlag)
				SimplifyCond(tp);
			if (tp->u.sym)
				addlocal(tp->u.sym);
			flab = genlabel(2);
			listnodes(tp->kids[0], 0, flab);
			assert(q && q->op == RIGHT);
			reset();
			listnodes(q->kids[0], 0, 0);
			if (forest->op == LABELV) {
				equatelab(forest->syms[0], findlabel(flab + 1));
				unlist();
			}
			list(jump(flab + 1));
			labelnode(flab);
			listnodes(q->kids[1], 0, 0);
			if (forest->op == LABELV) {
				equatelab(forest->syms[0], findlabel(flab + 1));
				unlist();
			}
			labelnode(flab + 1);

			if (tp->u.sym)
				p = listnodes(idtree(tp->u.sym), 0, 0);
		} break;
	case CNST:{
			Type            ty = unqual(tp->type);
			assert(ty->u.sym);
			if (tlab || flab) {
				assert(ty == inttype);
				if (tlab && tp->u.v.i != 0)
					list(jump(tlab));
				else if (flab && tp->u.v.i == 0)
					list(jump(flab));
			}
			else if (ty->u.sym->addressed) {
				if ((tp->op == CNST+D) &&
					(tp->u.v.d == 0.0 || tp->u.v.d == 1.0)) {
					p = node(tp->op,NULL,NULL,constant(ty,tp->u.v));
				}
				else if (tp->op == CNST+F &&
					(tp->u.v.f == 0.0 || tp->u.v.f == 1.0)) {
					p = node(tp->op,NULL,NULL,constant(ty,tp->u.v));
				}
				else
				p = listnodes(cvtconst(tp), 0, 0);
			}
			else
				p = node(tp->op, NULL, NULL, constant(ty, tp->u.v));
		} break;
	case RIGHT:{
			if (tp->kids[0] && tp->kids[1]
					&& generic(tp->kids[1]->op) == ASGN
					&& (generic(tp->kids[0]->op) == INDIR
						&& tp->kids[0]->kids[0] == tp->kids[1]->kids[0]
						|| (tp->kids[0]->op == FIELD
							&& tp->kids[0] == tp->kids[1]->kids[0]))) {
				assert(tlab == 0 && flab == 0);
				if (generic(tp->kids[0]->op) == INDIR) {
					p = listnodes(tp->kids[0], 0, 0);
					list(p);
					listnodes(tp->kids[1], 0, 0);
				}
				else {
					assert(generic(tp->kids[0]->kids[0]->op) == INDIR);
					list(listnodes(tp->kids[0]->kids[0], 0, 0));
					p = listnodes(tp->kids[0], 0, 0);
					listnodes(tp->kids[1], 0, 0);
				}
			}
			else if (tp->kids[1]) {
				listnodes(tp->kids[0], 0, 0);
				p = listnodes(tp->kids[1], tlab, flab);
			}
			else
				p = listnodes(tp->kids[0], tlab, flab);
		} break;
	case JUMP:{
			assert(tlab == 0 && flab == 0);
			assert(tp->u.sym == 0);
			assert(tp->kids[0]);
			l = listnodes(tp->kids[0], 0, 0);
			list(newnode(JUMPV, l, NULL, NULL));
			reset();
		} break;
	case CALL:{
			Tree            save = firstarg;
			if (hasArgs)
				FunctionInfo.NestedCalls = 1;
			firstarg = NULL;
			assert(tlab == 0 && flab == 0);
			if (tp->op == CALL + B && !IR->wants_callb) {
				Tree            arg0 = tree(ARG + P, tp->kids[1]->type,
											tp->kids[1], NULL);
				if (IR->left_to_right)
					firstarg = arg0;
				l = listnodes(tp->kids[0], 0, 0);
				if (!IR->left_to_right || firstarg) {
					firstarg = NULL;
					listnodes(arg0, 0, 0);
				}
				p = newnode(CALLV, l, NULL, NULL);
			}
			else {
				l = listnodes(tp->kids[0], 0, 0);
				r = listnodes(tp->kids[1], 0, 0);
				p = newnode(tp->op, l, r, NULL);
			}
			if (tp->Flags) {
				p->x.Flags = 1;
				if (tp->intrinsic) {
					p->x.intrinsic = tp->intrinsic;
					p->x.nestedCall = tp->nestedCall;
				}
			}
			list(p);
			reset();
			firstarg = save;
			if (tp->intrinsic == 0) {
				cfunc->u.f.ncalls++;
				FunctionInfo.hasCalls = 1;
				FunctionInfo.NrOfCalls++;
			}
		} break;
	case ARG:{
		int oldhasArgs = hasArgs;
		hasArgs = 1;
			assert(tlab == 0 && flab == 0);
			if (IR->left_to_right)
				listnodes(tp->kids[1], 0, 0);
			if (firstarg) {
				Tree            arg = firstarg;
				firstarg = NULL;
				listnodes(arg, 0, 0);
			}
			l = listnodes(tp->kids[0], 0, 0);
			if (tp->intrinsicArg ) {
				if (tp->nestedCall == 0 || nrOfIntrinsicArgs(tp->intrinsicArg) < 2)
					r = newnode(LOAD+optype(tp->op),l,NULL,NULL);
				else
					r = newnode(tp->op, l, NULL, NULL);
				r->x.intrinsicArg = tp->intrinsicArg;
				r->x.nestedCall = tp->nestedCall;
				list(r);
			}
			else list(newnode(tp->op, l, NULL, NULL));
			forest->syms[0] = intconst(tp->type->size);
			forest->syms[1] = intconst(tp->type->align);
			if (!IR->left_to_right)
				listnodes(tp->kids[1], 0, 0);
			if (tp->intrinsicArg == 0) {
				FunctionInfo.hasCalls = 1;
				FunctionInfo.NrOfCalls++;
			}
			if (tp->op == ARGB)
				FunctionInfo.hasBlockMove = 1;
			hasArgs = oldhasArgs;
		} break;
	case EQ:
	case NE:
	case GT:
	case GE:
	case LE:
	case LT:{
			assert(tp->u.sym == 0);
			assert(errcnt || tlab || flab);
			l = listnodes(tp->kids[0], 0, 0);
			r = listnodes(tp->kids[1], 0, 0);

			if (tlab)
#ifndef NDEBUG
				assert(flab == 0),
#endif
					list(newnode(tp->op, l, r, findlabel(tlab)));
			else if (flab) {
				int             op = generic(tp->op);
				switch (generic(op)) {
				case EQ:
					op = NE + optype(tp->op);
					break;
				case NE:
					op = EQ + optype(tp->op);
					break;
				case GT:
					op = LE + optype(tp->op);
					break;
				case LT:
					op = GE + optype(tp->op);
					break;
				case GE:
					op = LT + optype(tp->op);
					break;
				case LE:
					op = GT + optype(tp->op);
					break;
				default:
					assert(0);
				}
				list(newnode(op, l, r, findlabel(flab)));
			}
			if (forest && forest->syms[0]) {
				IncrementReferences(forest->syms[0]);
			}
		} break;
	case ASGN:{
			int kidsidx;
			assert(tlab == 0 && flab == 0);
			if (tp->kids[0]->op == FIELD) {
				Tree            x = tp->kids[0]->kids[0];
				Field           f = tp->kids[0]->u.field;
				assert(generic(x->op) == INDIR);
				reset();
				l = listnodes(lvalue(x), 0, 0);
				if (fieldsize(f) < 8 * f->type->size) {
					unsigned int    fmask = fieldmask(f);
					unsigned int    mask = fmask << fieldright(f);
					Tree            q = tp->kids[1];
					if (q->op == CNST + I && q->u.v.i == 0
							|| q->op == CNST + U && q->u.v.u == 0)
						q = bittree(BAND, x, consttree(~mask, unsignedtype));
					else if (q->op == CNST + I && (q->u.v.i & fmask) == fmask
						|| q->op == CNST + U && (q->u.v.u & fmask) == fmask)
						q = bittree(BOR, x, consttree(mask, unsignedtype));
					else {
						listnodes(q, 0, 0);
						q = bittree(BOR,
									bittree(BAND, rvalue(lvalue(x)),
											consttree(~mask, unsignedtype)),
							bittree(BAND, shtree(LSH, cast(q, unsignedtype),
										consttree(fieldright(f), inttype)),
									consttree(mask, unsignedtype)));
					}
					r = listnodes(q, 0, 0);
				}
				else
					r = listnodes(tp->kids[1], 0, 0);
			}
			else {
				l = listnodes(tp->kids[0], 0, 0);
				r = listnodes(tp->kids[1], 0, 0);
			}
			if (l->syms[0]) {
				l->syms[0]->assigned = 1;
			}
			for (kidsidx=0; kidsidx < 2; kidsidx++) {
				Node kid = r->kids[kidsidx];
				if (kid) {
					Symbol sy = (kid)? kid->syms[0] : NULL;
					if (sy && sy->assigned == 0
						&& sy->scope == LOCAL && sy->sclass != EXTERN) {
						if (sy->type && sy->type->op != ARRAY && sy->temporary == 0) {
							warning(StrTab[387],sy->name);// < possible usage of %s before definition\n>
							sy->assigned = 1;
						}
					}
				}
			}
			list(newnode(tp->op, l, r, NULL));
			forest->syms[0] = intconst(tp->kids[1]->type->size);
			forest->syms[1] = intconst(tp->kids[1]->type->align);
			if (isaddrop(tp->kids[0]->op)
					&& !tp->kids[0]->u.sym->computed)
				kill(tp->kids[0]->u.sym);
			else
				reset();
			p = listnodes(tp->kids[1], 0, 0);
			if (tp->op == ASGNB)
				FunctionInfo.hasBlockMove = 1;
		} break;
	case BOR:
	case BAND:
	case BXOR:
	case ADD:
	case SUB:
	case RSH:
	case LSH:{
			assert(tlab == 0 && flab == 0);
			l = listnodes(tp->kids[0], 0, 0);
			r = listnodes(tp->kids[1], 0, 0);
			p = node(tp->op, l, r, NULL);
		} break;
	case DIV:
	case MUL:
	case MOD:{
			assert(tlab == 0 && flab == 0);
			l = listnodes(tp->kids[0], 0, 0);
			r = listnodes(tp->kids[1], 0, 0);
			p = node(tp->op, l, r, NULL);
			if (IR->mulops_calls && isint(tp->type))
				list(p);
			if (generic(tp->op) == DIV || generic(tp->op) == MOD)
				FunctionInfo.hasDiv = 1;
		} break;
	case RET:{
			assert(tlab == 0 && flab == 0);
			l = listnodes(tp->kids[0], 0, 0);
#if 0
			if (generic(l->op) == INDIR &&
				l->kids[0] && l->kids[0]->op == ADDRLP) {
				FunctionInfo.returnSymbol = l->kids[0]->syms[0];
			}
#endif
			if (tp->kids[0]->op != CALLI)
			list(newnode(tp->op, l, NULL, NULL));
		} break;
	case CVC:
	case CVD:
	case CVF:
	case CVI:
	case CVP:
	case CVS:
	case CVU:
	case CVL:
	case BCOM:
	case NEG:{
			assert(tlab == 0 && flab == 0);
			l = listnodes(tp->kids[0], 0, 0);
			if ((tp->op == CVUI || tp->op == CVIU || 
				tp->op == CVPU || tp->op == CVUP ))
				p = l;
			else p = node(tp->op, l, NULL, NULL);
		} break;
	case INDIR:{
			Type            ty = tp->kids[0]->type;
			Symbol			sym;