simp.c

lcc,一个可变目标c语言编译器的源码

			zerofield(EQ,I,i);
			break;
		case ADD+P:
			foldaddp(l,r,I,i);
			foldaddp(l,r,U,u);
			foldaddp(r,l,I,i);
			foldaddp(r,l,U,u);
			commute(r,l);
			identity(r,retype(l,ty),I,i,0);
			identity(r,retype(l,ty),U,u,0);
			/*
			Some assemblers, e.g., the MIPS, can't handle offsets
			larger than 16 bits. A better solution would be to change
			the interface so that address() could fail.
			*/
			if (l->op == ADDRG+P && l->u.sym->generated
			&& (r->op == CNST+I && (r->u.v.i > 32767 || r->u.v.i < -32768)
			||  r->op == CNST+U && r->u.v.u > 65536))
				break;
			if (IR->address
			&&  isaddrop(l->op)
			&& (r->op == CNST+I && r->u.v.i <= longtype->u.sym->u.limits.max.i
			    && r->u.v.i >= longtype->u.sym->u.limits.min.i
			||  r->op == CNST+U && r->u.v.u <= longtype->u.sym->u.limits.max.i))
				return addrtree(l, cast(r, longtype)->u.v.i, ty);
			if (IR->address
			&&  l->op == ADD+P && isaddrop(l->kids[1]->op)
			&& (r->op == CNST+I && r->u.v.i <= longtype->u.sym->u.limits.max.i
			    && r->u.v.i >= longtype->u.sym->u.limits.min.i
			||  r->op == CNST+U && r->u.v.u <= longtype->u.sym->u.limits.max.i))
				return simplify(ADD+P, ty, l->kids[0],
					addrtree(l->kids[1], cast(r, longtype)->u.v.i, ty));
			if ((l->op == ADD+I || l->op == SUB+I)
			&& l->kids[1]->op == CNST+I && isaddrop(r->op))
				return simplify(ADD+P, ty, l->kids[0],
					simplify(generic(l->op)+P, ty, r, l->kids[1]));
			if (l->op == ADD+P && generic(l->kids[1]->op) == CNST
			&& generic(r->op) == CNST)
				return simplify(ADD+P, ty, l->kids[0],
					simplify(ADD, l->kids[1]->type, l->kids[1], r));
			if (l->op == ADD+I && generic(l->kids[1]->op) == CNST
			&&  r->op == ADD+P && generic(r->kids[1]->op) == CNST)
				return simplify(ADD+P, ty, l->kids[0],
					simplify(ADD+P, ty, r->kids[0],
					simplify(ADD, r->kids[1]->type, l->kids[1], r->kids[1])));
			if (l->op == RIGHT && l->kids[1])
				return tree(RIGHT, ty, l->kids[0],
					simplify(ADD+P, ty, l->kids[1], r));
			else if (l->op == RIGHT && l->kids[0])
				return tree(RIGHT, ty,
					simplify(ADD+P, ty, l->kids[0], r), NULL);
			break;

		case ADD+F:
			xfoldcnst(F,d,+,addd);
			commute(r,l);
			break;
		case AND+I:
			op = AND;
			ufoldcnst(I,l->u.v.i ? cond(r) : l);	/* 0&&r => 0, 1&&r => r */
			break;
		case OR+I:
			op = OR;
			/* 0||r => r, 1||r => 1 */
			ufoldcnst(I,l->u.v.i ? cnsttree(ty, 1L) : cond(r));
			break;
		case BCOM+I:
			ufoldcnst(I,cnsttree(ty, (long)extend((~l->u.v.i)&ones(8*ty->size), ty)));
			idempotent(BCOM+U);
			break;
		case BCOM+U:
			ufoldcnst(U,cnsttree(ty, (unsigned long)((~l->u.v.u)&ones(8*ty->size))));
			idempotent(BCOM+U);
			break;
		case BOR+U:
			foldcnst(U,u,|);
			commute(r,l);
			identity(r,l,U,u,0);
			break;
		case BOR+I:
			foldcnst(I,i,|);
			commute(r,l);
			identity(r,l,I,i,0);
			break;
		case BXOR+U:
			foldcnst(U,u,^);
			commute(r,l);
			identity(r,l,U,u,0);
			break;
		case BXOR+I:
			foldcnst(I,i,^);
			commute(r,l);
			identity(r,l,I,i,0);
			break;
		case DIV+F:
			xfoldcnst(F,d,/,divd);
			break;
		case DIV+I:
			identity(r,l,I,i,1);
			if (r->op == CNST+I && r->u.v.i == 0
			||  l->op == CNST+I && l->u.v.i == ty->u.sym->u.limits.min.i
			&&  r->op == CNST+I && r->u.v.i == -1)
				break;
			xfoldcnst(I,i,/,divi);
			break;
		case DIV+U:		
			identity(r,l,U,u,1);
			if (r->op == CNST+U && r->u.v.u == 0)
				break;
			if (r->op == CNST+U && (n = ispow2(r->u.v.u)) != 0)
				return simplify(RSH, ty, l, cnsttree(inttype, (long)n));
			foldcnst(U,u,/);
			break;
		case EQ+F:
			cfoldcnst(F,d,==);
			commute(r,l);
			break;
		case EQ+U:
			cfoldcnst(U,u,==);
			commute(r,l);
			zerofield(EQ,U,u);
			break;
		case GE+F: cfoldcnst(F,d,>=); break;
		case GE+I: cfoldcnst(I,i,>=); break;
		case GE+U:
			geu(l,r,1);	/* l >= 0 => (l,1) */
			cfoldcnst(U,u,>=);
			if (l->op == CNST+U && l->u.v.u == 0)	/* 0 >= r => r == 0 */
				return eqtree(EQ, r, l);
			break;
		case GT+F: cfoldcnst(F,d, >); break;
		case GT+I: cfoldcnst(I,i, >); break;
		case GT+U:
			geu(r,l,0);	/* 0 > r => (r,0) */
			cfoldcnst(U,u, >);
			if (r->op == CNST+U && r->u.v.u == 0)	/* l > 0 => l != 0 */
				return eqtree(NE, l, r);
			break;
		case LE+F: cfoldcnst(F,d,<=); break;
		case LE+I: cfoldcnst(I,i,<=); break;
		case LE+U:
			geu(r,l,1);	/* 0 <= r => (r,1) */
			cfoldcnst(U,u,<=);
			if (r->op == CNST+U && r->u.v.u == 0)	/* l <= 0 => l == 0 */
				return eqtree(EQ, l, r);
			break;
		case LSH+I:
			identity(r,l,I,i,0);
			if (l->op == CNST+I && r->op == CNST+I
			&& r->u.v.i >= 0 && r->u.v.i < 8*l->type->size
			&& muli(l->u.v.i, 1<<r->u.v.i, ty->u.sym->u.limits.min.i, ty->u.sym->u.limits.max.i, needconst))
				return cnsttree(ty, (long)(l->u.v.i<<r->u.v.i));
			if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) {
				warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i);
				break;
			}

			break;
		case LSH+U:
			identity(r,l,I,i,0);
			sfoldcnst(<<);
			if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) {
				warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i);
				break;
			}

			break;

		case LT+F: cfoldcnst(F,d, <); break;
		case LT+I: cfoldcnst(I,i, <); break;
		case LT+U:
			geu(l,r,0);	/* l < 0 => (l,0) */
			cfoldcnst(U,u, <);
			if (l->op == CNST+U && l->u.v.u == 0)	/* 0 < r => r != 0 */
				return eqtree(NE, r, l);
			break;
		case MOD+I:
			if (r->op == CNST+I && r->u.v.i == 0
			||  l->op == CNST+I && l->u.v.i == ty->u.sym->u.limits.min.i
			&&  r->op == CNST+I && r->u.v.i == -1)
				break;
			xfoldcnst(I,i,%,divi);
			if (r->op == CNST+I && r->u.v.i == 1)	/* l%1 => (l,0) */
				return tree(RIGHT, ty, root(l), cnsttree(ty, 0L));
			break;
		case MOD+U:		
			if (r->op == CNST+U && ispow2(r->u.v.u)) /* l%2^n => l&(2^n-1) */
				return bittree(BAND, l, cnsttree(ty, r->u.v.u - 1));
			if (r->op == CNST+U && r->u.v.u == 0)
				break;
			foldcnst(U,u,%);
			break;
		case MUL+F:
			xfoldcnst(F,d,*,muld);
			commute(l,r);
			break;
		case MUL+I:
			commute(l,r);
			xfoldcnst(I,i,*,muli);
			if (l->op == CNST+I && r->op == ADD+I && r->kids[1]->op == CNST+I)
				/* c1*(x + c2) => c1*x + c1*c2 */
				return simplify(ADD, ty, simplify(MUL, ty, l, r->kids[0]),
					simplify(MUL, ty, l, r->kids[1]));
			if (l->op == CNST+I && r->op == SUB+I && r->kids[1]->op == CNST+I)
				/* c1*(x - c2) => c1*x - c1*c2 */
				return simplify(SUB, ty, simplify(MUL, ty, l, r->kids[0]),
					simplify(MUL, ty, l, r->kids[1]));
			if (l->op == CNST+I && l->u.v.i > 0 && (n = ispow2(l->u.v.i)) != 0)
				/* 2^n * r => r<<n */
				return simplify(LSH, ty, r, cnsttree(inttype, (long)n));
			identity(r,l,I,i,1);
			break;
		case NE+F:
			cfoldcnst(F,d,!=);
			commute(r,l);
			break;
		case NE+U:
			cfoldcnst(U,u,!=);
			commute(r,l);
			zerofield(NE,U,u);
			break;
		case NEG+F:
			ufoldcnst(F,cnsttree(ty, -l->u.v.d));
			idempotent(NEG+F);
			break;
		case NEG+I:
			if (l->op == CNST+I) {
				if (needconst && l->u.v.i == ty->u.sym->u.limits.min.i)
					warning("overflow in constant expression\n");
				if (needconst || l->u.v.i != ty->u.sym->u.limits.min.i)
					return cnsttree(ty, -l->u.v.i);
			}
			idempotent(NEG+I);
			break;
		case NOT+I:
			op = NOT;
			ufoldcnst(I,cnsttree(ty, !l->u.v.i));
			break;
		case RSH+I:
			identity(r,l,I,i,0);
			if (l->op == CNST+I && r->op == CNST+I
			&& r->u.v.i >= 0 && r->u.v.i < 8*l->type->size) {
				long n = l->u.v.i>>r->u.v.i;
				if (l->u.v.i < 0)
					n |= ~0UL<<(8*l->type->size - r->u.v.i);
				return cnsttree(ty, n);
			}
			if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) {
				warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i);
				break;
			}

			break;
		case RSH+U:
			identity(r,l,I,i,0);
			sfoldcnst(>>);
			if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) {
				warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i);
				break;
			}

			break;
		case SUB+F:
			xfoldcnst(F,d,-,subd);
			break;
		case SUB+I:
			xfoldcnst(I,i,-,subi);
			identity(r,l,I,i,0);
			break;
		case SUB+U:
			foldcnst(U,u,-);
			identity(r,l,U,u,0);
			break;
		case SUB+P:
			if (l->op == CNST+P && r->op == CNST+P)
				return cnsttree(ty, (long)((char *)l->u.v.p - (char *)r->u.v.p));
			if (r->op == CNST+I || r->op == CNST+U)
				return simplify(ADD, ty, l,
					cnsttree(inttype, r->op == CNST+I ? -r->u.v.i : -(long)r->u.v.u));
			if (isaddrop(l->op) && r->op == ADD+I && r->kids[1]->op == CNST+I)
				/* l - (x + c) => l-c - x */
				return simplify(SUB, ty,
					simplify(SUB, ty, l, r->kids[1]), r->kids[0]);
			break;
		default:assert(0);
	}
	return tree(op, ty, l, r);
}
/* ispow2 - if u > 1 && u == 2^n, return n, otherwise return 0 */
int ispow2(unsigned long u) {
	int n;

	if (u > 1 && (u&(u-1)) == 0)
		for (n = 0; u; u >>= 1, n++)
			if (u&1)
				return n;
	return 0;
}