scc

commit a794c4b02bb81b0b563d579a46bc25cf42582352
parent 28974f98e6d51b5413f0080787bf3f2d074b9589
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date:   Sat,  4 Feb 2017 21:42:12 +0100

[cc1] Rewrite fold.c

The big problem of simplify() was being no recursive, and it meant
that a lot of oportunities to fold were lost.

Diffstat:
M
cc1/cc1.h
 | 
2
+-
M
cc1/expr.c
 | 
137
++++++++++++++++++++++---------------------------------------------------------
M
cc1/fold.c
 | 
281
+++++++++++++++++++++++++++++++++++++++++++++++++------------------------------
M
cc1/init.c
 | 
16
++++++++++------

4 files changed, 222 insertions(+), 214 deletions(-)
diff --git a/cc1/cc1.h b/cc1/cc1.h
@@ -420,7 +420,7 @@ extern void freetree(Node *np);
 #define BTYPE(np) ((np)->type->op)
 
 /* fold.c */
-extern Node *simplify(int op, Type *tp, Node *lp, Node *rp);
+extern Node *simplify(Node *np);
 extern TUINT ones(int nbytes);
 
 /* expr.c */
diff --git a/cc1/expr.c b/cc1/expr.c
@@ -11,7 +11,7 @@ static char sccsid[] = "@(#) ./cc1/expr.c";
 
 #define XCHG(lp, rp, np) (np = lp, lp = rp, rp = np)
 
-Node *expr(void);
+static Node *xexpr(void);
 
 int
 cmpnode(Node *np, TUINT val)
@@ -215,7 +215,7 @@ integerop(int op, Node *lp, Node *rp)
 	if (!(lp->type->prop & TINTEGER) || !(rp->type->prop & TINTEGER))
 		error("operator requires integer operands");
 	arithconv(&lp, &rp);
-	return simplify(op, lp->type, lp, rp);
+	return node(op, lp->type, lp, rp);
 }
 
 static Node *
@@ -224,9 +224,7 @@ integeruop(int op, Node *np)
 	if (!(np->type->prop & TINTEGER))
 		error("unary operator requires integer operand");
 	np = promote(np);
-	if (op == OCPL && np->op == OCPL)
-		return np->left;
-	return simplify(op, np->type, np, NULL);
+	return node(op, np->type, np, NULL);
 }
 
 static Node *
@@ -235,68 +233,7 @@ numericaluop(int op, Node *np)
 	if (!(np->type->prop & TARITH))
 		error("unary operator requires numerical operand");
 	np = promote(np);
-	if (op == OSNEG && np->op == OSNEG)
-		return np->left;
-	if (op == OADD)
-		return np;
-	return simplify(op, np->type, np, NULL);
-}
-
-/* TODO: check validity of types */
-static Node *
-castcode(Node *np, Type *newtp)
-{
-	TUINT negmask, mask, u;
-	Type *oldtp = np->type;
-	Symbol aux, *sym, *osym = np->sym;
-
-	if (!(np->flags & NCONST))
-		goto noconstant;
-
-	switch (newtp->op) {
-	case PTR:
-	case INT:
-	case ENUM:
-		switch (oldtp->op) {
-		case PTR:
-		case INT:
-		case ENUM:
-			u = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
-			break;
-		case FLOAT:
-			oldtp = newtp;
-			u = osym->u.f;
-			break;
-		default:
-			goto noconstant;
-		}
-		mask = ones(newtp->size);
-		if (newtp->prop & TSIGNED) {
-			negmask = ~mask;
-			if (u & (negmask >> 1) & mask)
-				u |= negmask;
-			aux.u.i = u;
-		} else {
-			aux.u.u = u & mask;
-		}
-		break;
-	case FLOAT:
-		/* FIXME: The cast can be from another float type */
-		aux.u.f = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
-		break;
-	default:
-		goto noconstant;
-	}
-
-	sym = newsym(NS_IDEN, NULL);
-	np->type = sym->type = newtp;
-	np->sym = sym;
-	sym->u = aux.u;
-
-	return np;
-
-noconstant:
-	return node(OCAST, newtp, np, NULL);
+	return node(op, np->type, np, NULL);
 }
 
 Node *
@@ -345,7 +282,7 @@ convert(Node *np, Type *newtp, char iscast)
 	default:
 		return NULL;
 	}
-	return castcode(np, newtp);
+	return node(OCAST, newtp, np, NULL);
 }
 
 static Node *
@@ -375,10 +312,10 @@ parithmetic(int op, Node *lp, Node *rp)
 		goto incorrect;
 
 	rp = convert(promote(rp), sizettype, 0);
-	rp = simplify(OMUL, sizettype, rp, size);
+	rp = node(OMUL, sizettype, rp, size);
 	rp = convert(rp, tp, 1);
 
-	return simplify(op, tp, lp, rp);
+	return node(op, tp, lp, rp);
 
 incomplete:
 	errorp("invalid use of undefined type");
@@ -396,7 +333,7 @@ arithmetic(int op, Node *lp, Node *rp)
 
 	if ((ltp->prop & TARITH) && (rtp->prop & TARITH)) {
 		arithconv(&lp, &rp);
-		return simplify(op, lp->type, lp, rp);
+		return node(op, lp->type, lp, rp);
 	} else if ((ltp->op == PTR || rtp->op == PTR)) {
 		switch (op) {
 		case OADD:
@@ -432,7 +369,7 @@ pcompare(int op, Node *lp, Node *rp)
 	}
 	if (err)
 		errorp("incompatible types in comparison");
-	return simplify(op, inttype, lp, rp);
+	return node(op, inttype, lp, rp);
 }
 
 static Node *
@@ -447,7 +384,7 @@ compare(int op, Node *lp, Node *rp)
 		return pcompare(op, rp, lp);
 	} else if ((ltp->prop & TARITH) && (rtp->prop & TARITH)) {
 		arithconv(&lp, &rp);
-		return simplify(op, inttype, lp, rp);
+		return node(op, inttype, lp, rp);
 	} else {
 		errorp("incompatible types in comparison");
 		freetree(lp);
@@ -532,7 +469,7 @@ logic(int op, Node *lp, Node *rp)
 {
 	lp = exp2cond(lp, 0);
 	rp = exp2cond(rp, 0);
-	return simplify(op, inttype, lp, rp);
+	return node(op, inttype, lp, rp);
 }
 
 static Node *
@@ -657,13 +594,7 @@ address(int op, Node *np)
 dont_check_lvalue:
 	if (np->sym && (np->sym->flags & SREGISTER))
 		errorp("address of register variable '%s' requested", yytext);
-	if (np->op == OPTR) {
-		Node *new = np->left;
-		free(np);
-		return new;
-	}
 	new = node(op, mktype(np->type, PTR, 0, NULL), np, NULL);
-
 	if (np->sym && np->sym->flags & (SGLOBAL|SLOCAL|SPRIVATE))
 		new->flags |= NCONST;
 	return new;
@@ -674,7 +605,6 @@ negation(int op, Node *np)
 {
 	if (!(np->type->prop & TARITH) && np->type->op != PTR) {
 		errorp("invalid argument of unary '!'");
-		freetree(np);
 		return constnode(zero);
 	}
 	return exp2cond(np, 1);
@@ -864,7 +794,7 @@ postfix(Node *lp)
 			switch (yytoken) {
 			case '[':
 				next();
-				rp = expr();
+				rp = xexpr();
 				expect(']');
 				lp = array(lp, rp);
 				break;
@@ -987,7 +917,7 @@ cast(int needdecay)
 		if (nested == NR_SUBEXPR)
 			error("too many expressions nested by parentheses");
 		++nested;
-		rp = expr();
+		rp = xexpr();
 		--nested;
 		expect(')');
 		rp = postfix(rp);
@@ -1155,11 +1085,11 @@ ternary(void)
 		Node *ifyes, *ifno, *np;
 
 		cond = exp2cond(cond, 0);
-		ifyes = expr();
+		ifyes = xexpr();
 		expect(':');
 		ifno = ternary();
 		np = chkternary(ifyes, ifno);
-		cond = simplify(OASK, np->type, cond, np);
+		cond = node(OASK, np->type, cond, np);
 	}
 	return cond;
 }
@@ -1193,31 +1123,38 @@ assign(void)
 	}
 }
 
+static Node *
+xexpr(void)
+{
+	Node *lp, *rp;
+
+	lp = assign();
+	while (accept(',')) {
+		rp = assign();
+		lp = node(OCOMMA, rp->type, lp, rp);
+	}
+	return lp;
+}
+
 Node *
 constexpr(void)
 {
 	Node *np;
 
 	np = ternary();
-	if (!np || !(np->flags & NCONST) || np->type->op != INT) {
-		freetree(np);
-		return NULL;
+	if (np && np->type->op == INT) {
+		np = simplify(convert(np, inttype, 0));
+		if (np->flags & NCONST)
+			return np;
 	}
-	return convert(np, inttype, 0);
+	freetree(np);
+	return NULL;
 }
 
 Node *
 expr(void)
 {
-	Node *lp, *rp;
-
-	lp = assign();
-	while (accept(',')) {
-		rp = assign();
-		lp = node(OCOMMA, rp->type, lp, rp);
-	}
-
-	return lp;
+	return simplify(xexpr());
 }
 
 Node *
@@ -1225,8 +1162,8 @@ condexpr(void)
 {
 	Node *np;
 
-	np = exp2cond(expr(), 0);
+	np = exp2cond(xexpr(), 0);
 	if (np->flags & NCONST)
 		warn("conditional expression is constant");
-	return np;
+	return simplify(np);
 }
diff --git a/cc1/fold.c b/cc1/fold.c
@@ -195,7 +195,7 @@ foldint(int op, Symbol *res, TINT l, TINT r)
 	}
 	res->u.i = i;
 
-	DBG("FOLD %lld %d %lld = %lld", l, op, r, i);
+	DBG("FOLD i l=%lld %d r=%lld = %lld", l, op, r, i);
 	return 1;
 }
 
@@ -231,13 +231,13 @@ folduint(int op, Symbol *res, TUINT l, TUINT r)
 	}
 	res->u.u = u & ones(res->type->size);
 
-	DBG("FOLD %llu %d %llu = %llu", l, op, r, i);
+	DBG("FOLD ui l=%llu %d r=%llu = %llu", l, op, r, i);
 	return 1;
 
 sign:
 	res->u.i = i;
 
-	DBG("FOLD %llu %d %llu = %llu", l, op, r, i);
+	DBG("FOLD sui %llu %d %llu = %llu", l, op, r, i);
 	return 1;
 }
 
@@ -273,10 +273,14 @@ foldfloat(int op, Symbol *res, TFLOAT l, TFLOAT r)
 	default:   return 0;
 	}
 	res->u.f = f;
+
+	DBG("FOLD f l=%lf %d r=%lf = %lf", l, op, r, f);
 	return 1;
 
 comparison:
 	res->u.i = i;
+
+	DBG("FOLD if l=%lf %d r=%lf = %lld", l, op, r, i);
 	return 1;
 }
 
@@ -307,19 +311,122 @@ foldconst(int type, int op, Type *tp, Symbol *ls, Symbol *rs)
 		break;
 	}
 	sym = newsym(NS_IDEN, NULL);
+	sym->flags |= SCONSTANT;
 	sym->type = tp;
 	sym->u = aux.u;
 	return constnode(sym);
 }
 
 static Node *
-fold(int op, Type *tp, Node *lp, Node *rp)
+foldcast(Node *np, Node *l)
+{
+	TUINT negmask, mask, u;
+	Type *newtp = np->type, *oldtp = l->type;
+	Symbol aux, *sym, *osym = l->sym;
+
+	if (!(l->flags & NCONST))
+		return np;
+
+	switch (newtp->op) {
+	case PTR:
+	case INT:
+	case ENUM:
+		switch (oldtp->op) {
+		case PTR:
+		case INT:
+		case ENUM:
+			u = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
+			break;
+		case FLOAT:
+			oldtp = newtp;
+			u = osym->u.f;
+			break;
+		default:
+			return  np;
+		}
+		mask = ones(newtp->size);
+		if (newtp->prop & TSIGNED) {
+			negmask = ~mask;
+			if (u & (negmask >> 1) & mask)
+				u |= negmask;
+			aux.u.i = u;
+		} else {
+			aux.u.u = u & mask;
+		}
+		break;
+	case FLOAT:
+		/* FIXME: The cast can be from another float type */
+		aux.u.f = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
+		break;
+	default:
+		return np;
+	}
+	DBG("FOLD cast %c->%c", oldtp->letter, newtp->letter);
+	freetree(np);
+	sym = newsym(NS_IDEN, NULL);
+	sym->flags |= SCONSTANT;
+	sym->type = newtp;
+	sym->u = aux.u;
+	return constnode(sym);
+}
+
+static Node *
+foldunary(Node *np, Node *l)
+{
+	int op = l->op;
+	Node *aux;
+
+	switch (np->op) {
+	case OADD:
+		DBG("FOLD unary delete %d", np->op);
+		np->left = NULL;
+		freetree(np);
+		return l;
+	case OCAST:
+		if (op != OCAST)
+			return foldcast(np, l);
+		DBG("FOLD unary collapse %d", np->op);
+		np->left = l->left;
+		l->left = NULL;
+		freetree(l);
+		return np;
+	case OSNEG:
+	case OCPL:
+		if (op != np->op)
+			return NULL;
+		break;
+	case OPTR:
+		if (op != OADDR)
+			return NULL;
+		break;
+	case OADDR:
+		if (op != OPTR)
+			return NULL;
+		break;
+	default:
+		return NULL;
+	}
+	DBG("FOLD unary cancel %d", np->op);
+	aux = l->left;
+	l->left = NULL;
+	freetree(np);
+	return aux;
+}
+
+static Node *
+fold(Node *np)
 {
 	Symbol *rs, *ls;
-	Node *np;
 	Type *optype;
 	int type;
+	int op = np->op;
+	Node *p, *lp = np->left, *rp = np->right;
+	Type *tp = np->type;
 
+	if (!lp && !rp)
+		return np;
+	if (!rp && (p = foldunary(np, lp)) != NULL)
+		return p;
 	if ((op == ODIV || op == OMOD) && cmpnode(rp, 0)) {
 		warn("division by 0");
 		return NULL;
@@ -331,13 +438,18 @@ fold(int op, Type *tp, Node *lp, Node *rp)
 	 * (when we don't know the physical address so
 	 * we cannot fold it)
 	 */
-	if (!(lp->flags & NCONST) || !lp->sym ||
-	    rp && (!(rp->flags & NCONST) || !rp->sym)) {
-		return NULL;
+	if (!rp) {
+		rs = NULL;
+	} else {
+		if (!(rp->flags & NCONST) || !rp->sym)
+			return NULL;
+		rs = rp->sym;
 	}
+
+	if (!(lp->flags & NCONST) || !lp->sym)
+		return NULL;
 	optype = lp->type;
 	ls = lp->sym;
-	rs = (rp) ? rp->sym : NULL;
 
 	switch (type = optype->op) {
 	case ENUM:
@@ -346,31 +458,30 @@ fold(int op, Type *tp, Node *lp, Node *rp)
 			type = UNSIGNED;
 	case PTR:
 	case FLOAT:
-		if ((np = foldconst(type, op, tp, ls, rs)) != NULL)
-			break;
+		if ((p = foldconst(type, op, tp, ls, rs)) == NULL)
+			return NULL;
+		freetree(np);
+		return p;
 	default:
 		return NULL;
 	}
-
-	freetree(lp);
-	freetree(rp);
-	return np;
 }
 
 static void
-commutative(int *op, Node **lp, Node **rp)
+commutative(Node *np, Node *l, Node *r)
 {
-	Node *l = *lp, *r = *rp, *aux;
+	int op = np->op;
 
-	if (r == NULL || r->flags & NCONST || !(l->flags & NCONST))
+	if (r == NULL || r->flags&NCONST || !(l->flags&NCONST))
 		return;
 
-	switch (*op) {
+	switch (op) {
 	case OLT:
 	case OGT:
 	case OGE:
 	case OLE:
-		*op = negop(*op);
+		DBG("FOLD neg commutative %d", np->op);
+		np->op = negop(op);
 	case OEQ:
 	case ONE:
 	case OADD:
@@ -378,20 +489,19 @@ commutative(int *op, Node **lp, Node **rp)
 	case OBAND:
 	case OBXOR:
 	case OBOR:
-		aux = l;
-		l = r;
-		r = aux;
+		DBG("FOLD commutative %d", np->op);
+		np->left = r;
+		np->right = l;
 		break;
 	}
-	*rp = r;
-	*lp = l;
 }
 
 static Node *
-identity(int *op, Node *lp, Node *rp)
+identity(Node *np)
 {
 	int iszeror, isoner, istruer;
 	int iszerol, isonel, istruel;
+	Node *lp = np->left, *rp = np->right;
 
 	if (!rp)
 		return NULL;
@@ -403,7 +513,7 @@ identity(int *op, Node *lp, Node *rp)
 	isonel = cmpnode(lp, 1),
 	istruel = !iszerol && lp->flags & NCONST;
 
-	switch (*op) {
+	switch (np->op) {
 	case OOR:
 		/*
 		 * 1 || i => 1    (free right)
@@ -485,28 +595,28 @@ identity(int *op, Node *lp, Node *rp)
 	}
 
 free_right:
-	DBG("FOLD identity %d", op);
-	freetree(rp);
+	DBG("FOLD identity %d", np->op);
+	np->left = NULL;
+	freetree(np);
 	return lp;
 
 free_left:
-	DBG("FOLD identity %d", op);
-	freetree(lp);
+	DBG("FOLD identity %d", np->op);
+	np->right = NULL;
+	freetree(np);
 	return rp;
 
 change_to_comma:
-	DBG("FOLD identity %d", op);
-	*op = OCOMMA;
-	return NULL;
+	DBG("FOLD identity %d", np->op);
+	np->op = OCOMMA;
+	return np;
 }
 
 static Node *
-foldternary(int op, Type *tp, Node *cond, Node *body)
+foldternary(Node *np, Node *cond, Node *body)
 {
-	Node *np;
-
 	if (!(cond->flags & NCONST))
-		return node(op, tp, cond, body);
+		return np;
 	if (cmpnode(cond, 0)) {
 		np = body->right;
 		freetree(body->left);
@@ -514,86 +624,43 @@ foldternary(int op, Type *tp, Node *cond, Node *body)
 		np = body->left;
 		freetree(body->right);
 	}
+
 	DBG("FOLD ternary");
+	body->left = NULL;
+	body->right = NULL;
 	freetree(cond);
 	free(body);
 	return np;
 }
 
-/*
- * TODO: transform simplify in a recursivity
- * function, because we are losing optimization
- * chances
- */
-Node *
-simplify(int op, Type *tp, Node *lp, Node *rp)
-{
-	Node *np;
-
-	if (op == OASK)
-		return foldternary(op, tp, lp, rp);
-	commutative(&op, &lp, &rp);
-	if ((np = fold(op, tp, lp, rp)) != NULL)
-		return np;
-	if ((np = identity(&op, lp, rp)) != NULL)
-		return np;
-	return node(op, tp, lp, rp);
-}
-
-/* TODO: check validity of types */
+/* TODO: fold OCOMMA */
 
 Node *
-castcode(Node *np, Type *newtp)
+simplify(Node *np)
 {
-	TUINT negmask, mask, u;
-	Type *oldtp = np->type;
-	Symbol aux, *sym, *osym = np->sym;
+	Node *p, *l, *r;
+	extern int debug;
 
-	if (!(np->flags & NCONST))
-		goto noconstant;
+	if (!np)
+		return NULL;
+	if (debug)
+		prtree(np);
 
-	switch (newtp->op) {
-	case PTR:
-	case INT:
-	case ENUM:
-		switch (oldtp->op) {
-		case PTR:
-		case INT:
-		case ENUM:
-			u = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
-			break;
-		case FLOAT:
-			oldtp = newtp;
-			u = osym->u.f;
-			break;
-		default:
-			goto noconstant;
-		}
-		mask = ones(newtp->size);
-		if (newtp->prop & TSIGNED) {
-			negmask = ~mask;
-			if (u & (negmask >> 1) & mask)
-				u |= negmask;
-			aux.u.i = u;
-		} else {
-			aux.u.u = u & mask;
-		}
-		break;
-	case FLOAT:
-		/* FIXME: The cast can be from another float type */
-		aux.u.f = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
-		break;
+	l = np->left = simplify(np->left);
+	r = np->right = simplify(np->right);
+
+	switch (np->op) {
+	case OASK:
+		return foldternary(np, l, r);
+	case OCALL:
+	case OPAR:
+		return np;
 	default:
-		goto noconstant;
+		commutative(np, l, r);
+		if ((p = fold(np)) != NULL)
+			return p;
+		if ((p = identity(np)) != NULL)
+			return p;
+		return np;
 	}
-
-	sym = newsym(NS_IDEN, NULL);
-	np->type = sym->type = newtp;
-	np->sym = sym;
-	sym->u = aux.u;
-
-	return np;
-
-noconstant:
-	return node(OCAST, newtp, np, NULL);
 }
diff --git a/cc1/init.c b/cc1/init.c
@@ -94,7 +94,7 @@ designation(Init *ip)
 static Node *
 initialize(Type *tp)
 {
-	Node *np, *aux;
+	Node *np;
 	Symbol *sym;
 	Type *btp;
 	size_t len;
@@ -133,12 +133,16 @@ initialize(Type *tp)
 		np->type = sym->type;
 
 		return np;
+	} else {
+		if (eqtype(tp, np->type, 1))
+			return np;
+		np = convert(decay(np), tp, 0);
+		if (!np) {
+			errorp("incorrect initializer");
+			goto return_zero;
+		}
 	}
-	if (eqtype(tp, np->type, 1))
-		return np;
-	if ((aux = convert(decay(np), tp, 0)) != NULL)
-		return aux;
-	errorp("incorrect initializer");
+	return simplify(np);
 
 return_zero:
 	return constnode(zero);