#include "c.h"static char rcsid[] = "$Id: dag.nw,v 2.30 1998/09/21 21:24:47 drh Exp $";#define iscall(op) (generic(op) == CALL || IR->mulops_calls && IR->mulops_calls(op))static Node forest;static struct dag {	struct node node;	struct dag *hlink;} *buckets[16];int nodecount;static Tree firstarg;int assignargs = 1;int prunetemps = -1;static Node *tail;#ifdef __hpux#define	kill(s)		 _kill(s)#endifstatic int depth = 0;static Node replace(Node);static Node prune(Node);static Node asgnnode(Symbol, Node);static struct dag *dagnode(int, Node, Node, Symbol);static Symbol equated(Symbol);static void fixup(Node);static void labelnode(int);static void list(Node);static void kill(Symbol);static Node node(int, Node, Node, Symbol);static void printdag1(Node, int, int);static void printnode(Node, int, int);static void reset(void);static Node tmpnode(Node);static void typestab(Symbol, void *);static Node undag(Node);static Node visit(Node, int);static void unlist(void);void walk(Tree tp, int tlab, int flab) {	listnodes(tp, tlab, flab);	if (forest) {		Node list = forest->link;		forest->link = NULL;		if (!IR->wants_dag)			list = undag(list);		code(Gen)->u.forest = list;		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 long)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 = 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;}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;}static void reset(void) {	if (nodecount > 0)		memset(buckets, 0, sizeof buckets);	nodecount = 0;}Node listnodes(Tree tp, int tlab, int flab) {	Node p = NULL, l, r;	int op;	assert(tlab || flab || tlab == 0 && flab == 0);	if (tp == NULL)		return NULL;	if (tp->node)		return tp->node;	op = tp->op + sizeop(tp->type->size);#define	XXX 	if (IR->mulops_calls && IR->mulops_calls(p->op)) { \                        list(p); \                        cfunc->u.f.ncalls++; \                }	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 {		      	listnodes(tp->kids[0], 0, flab = genlabel(1));		      	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 (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 == LABEL+V) {		      	equatelab(forest->syms[0], findlabel(flab + 1));		      	unlist();		      }		      list(jump(flab + 1));		      labelnode(flab);		      listnodes(q->kids[1], 0, 0);		      if (forest->op == LABEL+V) {		      	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)		      	p = listnodes(cvtconst(tp), 0, 0);		      else		      	p = node(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(JUMP+V, l, NULL, NULL));		      reset(); } break;	case CALL:  { Tree save = firstarg;		      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(CALL+V, l, NULL, NULL);		      } else {		      	l = listnodes(tp->kids[0], 0, 0);		      	r = listnodes(tp->kids[1], 0, 0);		      	p = newnode(tp->op == CALL+B ? tp->op : op, l, r, NULL);		      }		      NEW0(p->syms[0], FUNC);		      assert(isptr(tp->kids[0]->type));		      assert(isfunc(tp->kids[0]->type->type));		      p->syms[0]->type = tp->kids[0]->type->type;		      list(p);		      reset();		      cfunc->u.f.ncalls++;		      firstarg = save; } break;	case ARG:   { 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);		      list(newnode(tp->op == ARG+B ? tp->op : 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); } 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);		      assert(errcnt || opkind(l->op) == opkind(r->op));		      assert(errcnt || optype(op) == optype(l->op));		      if (tlab)		      	assert(flab == 0),		      	list(newnode(generic(tp->op) + opkind(l->op), l, r, findlabel(tlab)));		      else if (flab) {		      	switch (generic(tp->op)) {		      	case EQ: op = NE; break;		      	case NE: op = EQ; break;		      	case GT: op = LE; break;		      	case LT: op = GE; break;		      	case GE: op = LT; break;		      	case LE: op = GT; break;		      	default: assert(0);		      	}		      	list(newnode(op + opkind(l->op), l, r, findlabel(flab)));		      }		      if (forest && forest->syms[0])		      	forest->syms[0]->ref++; } break;	case ASGN:  { 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, cnsttree(unsignedtype, (unsigned long)~mask));				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, cnsttree(unsignedtype, (unsigned long)mask));				else {					listnodes(q, 0, 0);					q = bittree(BOR,						bittree(BAND, rvalue(lvalue(x)),							cnsttree(unsignedtype, (unsigned long)~mask)),						bittree(BAND, shtree(LSH, cast(q, unsignedtype),							cnsttree(unsignedtype, (unsigned long)fieldright(f))),							cnsttree(unsignedtype, (unsigned long)mask)));				}				r = listnodes(q, 0, 0);				op = ASGN + ttob(q->type);			} else {				r = listnodes(tp->kids[1], 0, 0);				op = ASGN + ttob(tp->kids[1]->type);			}		      } else {		      	l = listnodes(tp->kids[0], 0, 0);		      	r = listnodes(tp->kids[1], 0, 0);		      }		      list(newnode(tp->op == ASGN+B ? tp->op : 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); } 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(op, l, r, NULL); XXX } 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(op, l, r, NULL); XXX } break;	case RET:   { assert(tlab == 0 && flab == 0);		      l = listnodes(tp->kids[0], 0, 0);		      list(newnode(op, l, NULL, NULL)); } break;	case CVF: case CVI: case CVP:	case CVU:   { assert(tlab == 0 && flab == 0);		      assert(optype(tp->kids[0]->op) != optype(tp->op) || tp->kids[0]->type->size != tp->type->size);		      l = listnodes(tp->kids[0], 0, 0);		      p = node(op, l, NULL, intconst(tp->kids[0]->type->size)); XXX } break;	case BCOM:	case NEG:   { assert(tlab == 0 && flab == 0);		      l = listnodes(tp->kids[0], 0, 0);		      p = node(op, l, NULL, NULL); XXX } break;	case INDIR: { Type ty = tp->kids[0]->type;		      assert(tlab == 0 && flab == 0);		      l = listnodes(tp->kids[0], 0, 0);		      if (isptr(ty))		      	ty = unqual(ty)->type;		      if (isvolatile(ty)		      || (isstruct(ty) && unqual(ty)->u.sym->u.s.vfields))		      	p = newnode(tp->op == INDIR+B ? tp->op : op, l, NULL, NULL);		      else		      	p = node(tp->op == INDIR+B ? tp->op : op, l, NULL, NULL); } break;	case FIELD: { Tree q = tp->kids[0];		      if (tp->type == inttype) {		      	long n = fieldleft(tp->u.field);		      	q = shtree(RSH,		      		shtree(LSH, q, cnsttree(inttype, n)),		      		cnsttree(inttype, n + fieldright(tp->u.field)));		      } else if (fieldsize(tp->u.field) < 8*tp->u.field->type->size)		      	q = bittree(BAND,		      		shtree(RSH, q, cnsttree(inttype, (long)fieldright(tp->u.field))),		      		cnsttree(unsignedtype, (unsigned long)fieldmask(tp->u.field)));		      assert(tlab == 0 && flab == 0);		      p = listnodes(q, 0, 0); } break;	case ADDRG:	case ADDRF: { assert(tlab == 0 && flab == 0);		      p = node(tp->op + sizeop(voidptype->size), NULL, NULL, tp->u.sym); } break;	case ADDRL: { assert(tlab == 0 && flab == 0);