diff options
Diffstat (limited to 'lcc/src/simp.c')
-rwxr-xr-x | lcc/src/simp.c | 1174 |
1 files changed, 587 insertions, 587 deletions
diff --git a/lcc/src/simp.c b/lcc/src/simp.c index 04699bb..4d79af0 100755 --- a/lcc/src/simp.c +++ b/lcc/src/simp.c @@ -1,587 +1,587 @@ -#include "c.h"
-#include <float.h>
-
-
-#define foldcnst(TYPE,VAR,OP) \
- if (l->op == CNST+TYPE && r->op == CNST+TYPE) \
- return cnsttree(ty, l->u.v.VAR OP r->u.v.VAR)
-#define commute(L,R) \
- if (generic(R->op) == CNST && generic(L->op) != CNST) \
- do { Tree t = L; L = R; R = t; } while(0)
-#define xfoldcnst(TYPE,VAR,OP,FUNC)\
- if (l->op == CNST+TYPE && r->op == CNST+TYPE\
- && FUNC(l->u.v.VAR,r->u.v.VAR,\
- ty->u.sym->u.limits.min.VAR,\
- ty->u.sym->u.limits.max.VAR, needconst)) \
- return cnsttree(ty, l->u.v.VAR OP r->u.v.VAR)
-#define xcvtcnst(FTYPE,SRC,DST,VAR,EXPR) \
- if (l->op == CNST+FTYPE) do {\
- if (!explicitCast\
- && ((SRC) < DST->u.sym->u.limits.min.VAR || (SRC) > DST->u.sym->u.limits.max.VAR))\
- warning("overflow in converting constant expression from `%t' to `%t'\n", l->type, DST);\
- if (needconst\
- || !((SRC) < DST->u.sym->u.limits.min.VAR || (SRC) > DST->u.sym->u.limits.max.VAR))\
- return cnsttree(ty, (EXPR)); } while(0)
-#define identity(X,Y,TYPE,VAR,VAL) \
- if (X->op == CNST+TYPE && X->u.v.VAR == VAL) return Y
-#define zerofield(OP,TYPE,VAR) \
- if (l->op == FIELD \
- && r->op == CNST+TYPE && r->u.v.VAR == 0)\
- return eqtree(OP, bittree(BAND, l->kids[0],\
- cnsttree(unsignedtype, \
- (unsigned long)fieldmask(l->u.field)<<fieldright(l->u.field))), r)
-#define cfoldcnst(TYPE,VAR,OP) \
- if (l->op == CNST+TYPE && r->op == CNST+TYPE) \
- return cnsttree(inttype, (long)(l->u.v.VAR OP r->u.v.VAR))
-#define foldaddp(L,R,RTYPE,VAR) \
- if (L->op == CNST+P && R->op == CNST+RTYPE) { \
- Tree e = tree(CNST+P, ty, NULL, NULL);\
- e->u.v.p = (char *)L->u.v.p + R->u.v.VAR;\
- return e; }
-#define ufoldcnst(TYPE,EXP) if (l->op == CNST+TYPE) return EXP
-#define sfoldcnst(OP) \
- if (l->op == CNST+U && r->op == CNST+I \
- && r->u.v.i >= 0 && r->u.v.i < 8*l->type->size) \
- return cnsttree(ty, (unsigned long)(l->u.v.u OP r->u.v.i))
-#define geu(L,R,V) \
- if (R->op == CNST+U && R->u.v.u == 0) do { \
- warning("result of unsigned comparison is constant\n"); \
- return tree(RIGHT, inttype, root(L), cnsttree(inttype, (long)(V))); } while(0)
-#define idempotent(OP) if (l->op == OP) return l->kids[0]
-
-int needconst;
-int explicitCast;
-static int addi(long x, long y, long min, long max, int needconst) {
- int cond = x == 0 || y == 0
- || x < 0 && y < 0 && x >= min - y
- || x < 0 && y > 0
- || x > 0 && y < 0
- || x > 0 && y > 0 && x <= max - y;
- if (!cond && needconst) {
- warning("overflow in constant expression\n");
- cond = 1;
- }
- return cond;
-
-
-}
-
-static int addd(double x, double y, double min, double max, int needconst) {
- int cond = x == 0 || y == 0
- || x < 0 && y < 0 && x >= min - y
- || x < 0 && y > 0
- || x > 0 && y < 0
- || x > 0 && y > 0 && x <= max - y;
- if (!cond && needconst) {
- warning("overflow in constant expression\n");
- cond = 1;
- }
- return cond;
-
-
-}
-
-static Tree addrtree(Tree e, long n, Type ty) {
- Symbol p = e->u.sym, q;
-
- if (p->scope == GLOBAL
- || p->sclass == STATIC || p->sclass == EXTERN)
- NEW0(q, PERM);
- else
- NEW0(q, FUNC);
- q->name = stringd(genlabel(1));
- q->sclass = p->sclass;
- q->scope = p->scope;
- assert(isptr(ty) || isarray(ty));
- q->type = isptr(ty) ? ty->type : ty;
- q->temporary = p->temporary;
- q->generated = p->generated;
- q->addressed = p->addressed;
- q->computed = 1;
- q->defined = 1;
- q->ref = 1;
- if (p->scope == GLOBAL
- || p->sclass == STATIC || p->sclass == EXTERN) {
- if (p->sclass == AUTO)
- q->sclass = STATIC;
- (*IR->address)(q, p, n);
- } else {
- Code cp;
- addlocal(p);
- cp = code(Address);
- cp->u.addr.sym = q;
- cp->u.addr.base = p;
- cp->u.addr.offset = n;
- }
- e = tree(e->op, ty, NULL, NULL);
- e->u.sym = q;
- return e;
-}
-
-/* div[id] - return 1 if min <= x/y <= max, 0 otherwise */
-static int divi(long x, long y, long min, long max, int needconst) {
- int cond = y != 0 && !(x == min && y == -1);
- if (!cond && needconst) {
- warning("overflow in constant expression\n");
- cond = 1;
- }
- return cond;
-
-
-}
-
-static int divd(double x, double y, double min, double max, int needconst) {
- int cond;
-
- if (x < 0) x = -x;
- if (y < 0) y = -y;
- cond = y != 0 && !(y < 1 && x > max*y);
- if (!cond && needconst) {
- warning("overflow in constant expression\n");
- cond = 1;
- }
- return cond;
-
-}
-
-/* mul[id] - return 1 if min <= x*y <= max, 0 otherwise */
-static int muli(long x, long y, long min, long max, int needconst) {
- int cond = x > -1 && x <= 1 || y > -1 && y <= 1
- || x < 0 && y < 0 && -x <= max/-y
- || x < 0 && y > 0 && x >= min/y
- || x > 0 && y < 0 && y >= min/x
- || x > 0 && y > 0 && x <= max/y;
- if (!cond && needconst) {
- warning("overflow in constant expression\n");
- cond = 1;
- }
- return cond;
-
-
-}
-
-static int muld(double x, double y, double min, double max, int needconst) {
- int cond = x >= -1 && x <= 1 || y >= -1 && y <= 1
- || x < 0 && y < 0 && -x <= max/-y
- || x < 0 && y > 0 && x >= min/y
- || x > 0 && y < 0 && y >= min/x
- || x > 0 && y > 0 && x <= max/y;
- if (!cond && needconst) {
- warning("overflow in constant expression\n");
- cond = 1;
- }
- return cond;
-
-
-}
-/* sub[id] - return 1 if min <= x-y <= max, 0 otherwise */
-static int subi(long x, long y, long min, long max, int needconst) {
- return addi(x, -y, min, max, needconst);
-}
-
-static int subd(double x, double y, double min, double max, int needconst) {
- return addd(x, -y, min, max, needconst);
-}
-Tree constexpr(int tok) {
- Tree p;
-
- needconst++;
- p = expr1(tok);
- needconst--;
- return p;
-}
-
-int intexpr(int tok, int n) {
- Tree p = constexpr(tok);
-
- needconst++;
- if (p->op == CNST+I || p->op == CNST+U)
- n = cast(p, inttype)->u.v.i;
- else
- error("integer expression must be constant\n");
- needconst--;
- return n;
-}
-Tree simplify(int op, Type ty, Tree l, Tree r) {
- int n;
- Tree p;
-
- if (optype(op) == 0)
- op = mkop(op, ty);
- switch (op) {
- case ADD+U:
- foldcnst(U,u,+);
- commute(r,l);
- identity(r,l,U,u,0);
- break;
- case ADD+I:
- xfoldcnst(I,i,+,addi);
- commute(r,l);
- identity(r,l,I,i,0);
- break;
- case CVI+I:
- xcvtcnst(I,l->u.v.i,ty,i,(long)extend(l->u.v.i,ty));
- break;
- case CVU+I:
- if (l->op == CNST+U) {
- if (!explicitCast && l->u.v.u > ty->u.sym->u.limits.max.i)
- warning("overflow in converting constant expression from `%t' to `%t'\n", l->type, ty);
- if (needconst || !(l->u.v.u > ty->u.sym->u.limits.max.i))
- return cnsttree(ty, (long)extend(l->u.v.u,ty));
- }
- break;
- case CVP+U:
- xcvtcnst(P,(unsigned long)l->u.v.p,ty,u,(unsigned long)l->u.v.p);
- break;
- case CVU+P:
- xcvtcnst(U,(void*)l->u.v.u,ty,p,(void*)l->u.v.u);
- break;
- case CVP+P:
- xcvtcnst(P,l->u.v.p,ty,p,l->u.v.p);
- break;
- case CVI+U:
- xcvtcnst(I,l->u.v.i,ty,u,((unsigned long)l->u.v.i)&ones(8*ty->size));
- break;
- case CVU+U:
- xcvtcnst(U,l->u.v.u,ty,u,l->u.v.u&ones(8*ty->size));
- break;
-
- case CVI+F:
- xcvtcnst(I,l->u.v.i,ty,d,(long double)l->u.v.i);
- case CVU+F:
- xcvtcnst(U,l->u.v.u,ty,d,(long double)l->u.v.u);
- break;
- case CVF+I:
- xcvtcnst(F,l->u.v.d,ty,i,(long)l->u.v.d);
- break;
- case CVF+F: {
- float d;
- if (l->op == CNST+F)
- if (l->u.v.d < ty->u.sym->u.limits.min.d)
- d = ty->u.sym->u.limits.min.d;
- else if (l->u.v.d > ty->u.sym->u.limits.max.d)
- d = ty->u.sym->u.limits.max.d;
- else
- d = l->u.v.d;
- xcvtcnst(F,l->u.v.d,ty,d,(long double)d);
- break;
- }
- case BAND+U:
- foldcnst(U,u,&);
- commute(r,l);
- identity(r,l,U,u,ones(8*ty->size));
- if (r->op == CNST+U && r->u.v.u == 0)
- return tree(RIGHT, ty, root(l), cnsttree(ty, 0UL));
- break;
- case BAND+I:
- foldcnst(I,i,&);
- commute(r,l);
- identity(r,l,I,i,ones(8*ty->size));
- if (r->op == CNST+I && r->u.v.u == 0)
- return tree(RIGHT, ty, root(l), cnsttree(ty, 0L));
- break;
-
- case MUL+U:
- commute(l,r);
- if (l->op == CNST+U && (n = ispow2(l->u.v.u)) != 0)
- return simplify(LSH, ty, r, cnsttree(inttype, (long)n));
- foldcnst(U,u,*);
- identity(r,l,U,u,1);
- break;
- case NE+I:
- cfoldcnst(I,i,!=);
- commute(r,l);
- zerofield(NE,I,i);
- break;
-
- case EQ+I:
- cfoldcnst(I,i,==);
- commute(r,l);
- 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);
- if (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 (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 == 1) /* l%1 => (l,0) */
- return tree(RIGHT, ty, root(l), cnsttree(ty, 0L));
- 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 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;
-}
-
+#include "c.h" +#include <float.h> + + +#define foldcnst(TYPE,VAR,OP) \ + if (l->op == CNST+TYPE && r->op == CNST+TYPE) \ + return cnsttree(ty, l->u.v.VAR OP r->u.v.VAR) +#define commute(L,R) \ + if (generic(R->op) == CNST && generic(L->op) != CNST) \ + do { Tree t = L; L = R; R = t; } while(0) +#define xfoldcnst(TYPE,VAR,OP,FUNC)\ + if (l->op == CNST+TYPE && r->op == CNST+TYPE\ + && FUNC(l->u.v.VAR,r->u.v.VAR,\ + ty->u.sym->u.limits.min.VAR,\ + ty->u.sym->u.limits.max.VAR, needconst)) \ + return cnsttree(ty, l->u.v.VAR OP r->u.v.VAR) +#define xcvtcnst(FTYPE,SRC,DST,VAR,EXPR) \ + if (l->op == CNST+FTYPE) do {\ + if (!explicitCast\ + && ((SRC) < DST->u.sym->u.limits.min.VAR || (SRC) > DST->u.sym->u.limits.max.VAR))\ + warning("overflow in converting constant expression from `%t' to `%t'\n", l->type, DST);\ + if (needconst\ + || !((SRC) < DST->u.sym->u.limits.min.VAR || (SRC) > DST->u.sym->u.limits.max.VAR))\ + return cnsttree(ty, (EXPR)); } while(0) +#define identity(X,Y,TYPE,VAR,VAL) \ + if (X->op == CNST+TYPE && X->u.v.VAR == VAL) return Y +#define zerofield(OP,TYPE,VAR) \ + if (l->op == FIELD \ + && r->op == CNST+TYPE && r->u.v.VAR == 0)\ + return eqtree(OP, bittree(BAND, l->kids[0],\ + cnsttree(unsignedtype, \ + (unsigned long)fieldmask(l->u.field)<<fieldright(l->u.field))), r) +#define cfoldcnst(TYPE,VAR,OP) \ + if (l->op == CNST+TYPE && r->op == CNST+TYPE) \ + return cnsttree(inttype, (long)(l->u.v.VAR OP r->u.v.VAR)) +#define foldaddp(L,R,RTYPE,VAR) \ + if (L->op == CNST+P && R->op == CNST+RTYPE) { \ + Tree e = tree(CNST+P, ty, NULL, NULL);\ + e->u.v.p = (char *)L->u.v.p + R->u.v.VAR;\ + return e; } +#define ufoldcnst(TYPE,EXP) if (l->op == CNST+TYPE) return EXP +#define sfoldcnst(OP) \ + if (l->op == CNST+U && r->op == CNST+I \ + && r->u.v.i >= 0 && r->u.v.i < 8*l->type->size) \ + return cnsttree(ty, (unsigned long)(l->u.v.u OP r->u.v.i)) +#define geu(L,R,V) \ + if (R->op == CNST+U && R->u.v.u == 0) do { \ + warning("result of unsigned comparison is constant\n"); \ + return tree(RIGHT, inttype, root(L), cnsttree(inttype, (long)(V))); } while(0) +#define idempotent(OP) if (l->op == OP) return l->kids[0] + +int needconst; +int explicitCast; +static int addi(long x, long y, long min, long max, int needconst) { + int cond = x == 0 || y == 0 + || x < 0 && y < 0 && x >= min - y + || x < 0 && y > 0 + || x > 0 && y < 0 + || x > 0 && y > 0 && x <= max - y; + if (!cond && needconst) { + warning("overflow in constant expression\n"); + cond = 1; + } + return cond; + + +} + +static int addd(double x, double y, double min, double max, int needconst) { + int cond = x == 0 || y == 0 + || x < 0 && y < 0 && x >= min - y + || x < 0 && y > 0 + || x > 0 && y < 0 + || x > 0 && y > 0 && x <= max - y; + if (!cond && needconst) { + warning("overflow in constant expression\n"); + cond = 1; + } + return cond; + + +} + +static Tree addrtree(Tree e, long n, Type ty) { + Symbol p = e->u.sym, q; + + if (p->scope == GLOBAL + || p->sclass == STATIC || p->sclass == EXTERN) + NEW0(q, PERM); + else + NEW0(q, FUNC); + q->name = stringd(genlabel(1)); + q->sclass = p->sclass; + q->scope = p->scope; + assert(isptr(ty) || isarray(ty)); + q->type = isptr(ty) ? ty->type : ty; + q->temporary = p->temporary; + q->generated = p->generated; + q->addressed = p->addressed; + q->computed = 1; + q->defined = 1; + q->ref = 1; + if (p->scope == GLOBAL + || p->sclass == STATIC || p->sclass == EXTERN) { + if (p->sclass == AUTO) + q->sclass = STATIC; + (*IR->address)(q, p, n); + } else { + Code cp; + addlocal(p); + cp = code(Address); + cp->u.addr.sym = q; + cp->u.addr.base = p; + cp->u.addr.offset = n; + } + e = tree(e->op, ty, NULL, NULL); + e->u.sym = q; + return e; +} + +/* div[id] - return 1 if min <= x/y <= max, 0 otherwise */ +static int divi(long x, long y, long min, long max, int needconst) { + int cond = y != 0 && !(x == min && y == -1); + if (!cond && needconst) { + warning("overflow in constant expression\n"); + cond = 1; + } + return cond; + + +} + +static int divd(double x, double y, double min, double max, int needconst) { + int cond; + + if (x < 0) x = -x; + if (y < 0) y = -y; + cond = y != 0 && !(y < 1 && x > max*y); + if (!cond && needconst) { + warning("overflow in constant expression\n"); + cond = 1; + } + return cond; + +} + +/* mul[id] - return 1 if min <= x*y <= max, 0 otherwise */ +static int muli(long x, long y, long min, long max, int needconst) { + int cond = x > -1 && x <= 1 || y > -1 && y <= 1 + || x < 0 && y < 0 && -x <= max/-y + || x < 0 && y > 0 && x >= min/y + || x > 0 && y < 0 && y >= min/x + || x > 0 && y > 0 && x <= max/y; + if (!cond && needconst) { + warning("overflow in constant expression\n"); + cond = 1; + } + return cond; + + +} + +static int muld(double x, double y, double min, double max, int needconst) { + int cond = x >= -1 && x <= 1 || y >= -1 && y <= 1 + || x < 0 && y < 0 && -x <= max/-y + || x < 0 && y > 0 && x >= min/y + || x > 0 && y < 0 && y >= min/x + || x > 0 && y > 0 && x <= max/y; + if (!cond && needconst) { + warning("overflow in constant expression\n"); + cond = 1; + } + return cond; + + +} +/* sub[id] - return 1 if min <= x-y <= max, 0 otherwise */ +static int subi(long x, long y, long min, long max, int needconst) { + return addi(x, -y, min, max, needconst); +} + +static int subd(double x, double y, double min, double max, int needconst) { + return addd(x, -y, min, max, needconst); +} +Tree constexpr(int tok) { + Tree p; + + needconst++; + p = expr1(tok); + needconst--; + return p; +} + +int intexpr(int tok, int n) { + Tree p = constexpr(tok); + + needconst++; + if (p->op == CNST+I || p->op == CNST+U) + n = cast(p, inttype)->u.v.i; + else + error("integer expression must be constant\n"); + needconst--; + return n; +} +Tree simplify(int op, Type ty, Tree l, Tree r) { + int n; + Tree p; + + if (optype(op) == 0) + op = mkop(op, ty); + switch (op) { + case ADD+U: + foldcnst(U,u,+); + commute(r,l); + identity(r,l,U,u,0); + break; + case ADD+I: + xfoldcnst(I,i,+,addi); + commute(r,l); + identity(r,l,I,i,0); + break; + case CVI+I: + xcvtcnst(I,l->u.v.i,ty,i,(long)extend(l->u.v.i,ty)); + break; + case CVU+I: + if (l->op == CNST+U) { + if (!explicitCast && l->u.v.u > ty->u.sym->u.limits.max.i) + warning("overflow in converting constant expression from `%t' to `%t'\n", l->type, ty); + if (needconst || !(l->u.v.u > ty->u.sym->u.limits.max.i)) + return cnsttree(ty, (long)extend(l->u.v.u,ty)); + } + break; + case CVP+U: + xcvtcnst(P,(unsigned long)l->u.v.p,ty,u,(unsigned long)l->u.v.p); + break; + case CVU+P: + xcvtcnst(U,(void*)l->u.v.u,ty,p,(void*)l->u.v.u); + break; + case CVP+P: + xcvtcnst(P,l->u.v.p,ty,p,l->u.v.p); + break; + case CVI+U: + xcvtcnst(I,l->u.v.i,ty,u,((unsigned long)l->u.v.i)&ones(8*ty->size)); + break; + case CVU+U: + xcvtcnst(U,l->u.v.u,ty,u,l->u.v.u&ones(8*ty->size)); + break; + + case CVI+F: + xcvtcnst(I,l->u.v.i,ty,d,(long double)l->u.v.i); + case CVU+F: + xcvtcnst(U,l->u.v.u,ty,d,(long double)l->u.v.u); + break; + case CVF+I: + xcvtcnst(F,l->u.v.d,ty,i,(long)l->u.v.d); + break; + case CVF+F: { + float d; + if (l->op == CNST+F) + if (l->u.v.d < ty->u.sym->u.limits.min.d) + d = ty->u.sym->u.limits.min.d; + else if (l->u.v.d > ty->u.sym->u.limits.max.d) + d = ty->u.sym->u.limits.max.d; + else + d = l->u.v.d; + xcvtcnst(F,l->u.v.d,ty,d,(long double)d); + break; + } + case BAND+U: + foldcnst(U,u,&); + commute(r,l); + identity(r,l,U,u,ones(8*ty->size)); + if (r->op == CNST+U && r->u.v.u == 0) + return tree(RIGHT, ty, root(l), cnsttree(ty, 0UL)); + break; + case BAND+I: + foldcnst(I,i,&); + commute(r,l); + identity(r,l,I,i,ones(8*ty->size)); + if (r->op == CNST+I && r->u.v.u == 0) + return tree(RIGHT, ty, root(l), cnsttree(ty, 0L)); + break; + + case MUL+U: + commute(l,r); + if (l->op == CNST+U && (n = ispow2(l->u.v.u)) != 0) + return simplify(LSH, ty, r, cnsttree(inttype, (long)n)); + foldcnst(U,u,*); + identity(r,l,U,u,1); + break; + case NE+I: + cfoldcnst(I,i,!=); + commute(r,l); + zerofield(NE,I,i); + break; + + case EQ+I: + cfoldcnst(I,i,==); + commute(r,l); + 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); + if (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 (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 == 1) /* l%1 => (l,0) */ + return tree(RIGHT, ty, root(l), cnsttree(ty, 0L)); + 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 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; +} + |