ref: 137133eba02f76bebcb8548ff125f931eebb3270
dir: /cc1/fold.c/
/* See LICENSE file for copyright and license details. */ static char sccsid[] = "@(#) ./cc1/fold.c"; #include <stdio.h> #include <stdlib.h> #include "../inc/cc.h" #include "cc1.h" TUINT ones(int nbytes) { TUINT v; for (v = 0; nbytes--; v |= 255) v <<= 8; return v; } static int addi(TINT l, TINT r, Type *tp) { struct limits *lim = getlimits(tp); TINT max = lim->max.i, min = -lim->min.i; if (l < 0 && r < 0 && l >= min - r || l == 0 || r == 0 || l < 0 && r > 0 || l > 0 && r < 0 || l > 0 && r > 0 && l <= max - r) { return 1; } warn("overflow in constant expression"); return 0; } static int addf(TFLOAT l, TFLOAT r, Type *tp) { struct limits *lim = getlimits(tp); TFLOAT max = lim->max.f, min = lim->min.f; if (l < 0 && r < 0 && l >= min - r || l == 0 || r == 0 || l < 0 && r > 0 || l > 0 && r < 0 || l > 0 && r > 0 && l <= max - r) { return 1; } warn("overflow in constant expression"); return 0; } static int subi(TINT l, TINT r, Type *tp) { return addi(l, -r, tp); } static int subf(TFLOAT l, TFLOAT r, Type *tp) { return addf(l, -r, tp); } static int muli(TINT l, TINT r, Type *tp) { struct limits *lim = getlimits(tp); TINT max = lim->max.i, min = -lim->min.i; if (l > -1 && l <= 1 || r > -1 && r <= 1 || l < 0 && r < 0 && -l <= max/-r || l < 0 && r > 0 && l >= min/r || l > 0 && r < 0 && r >= min/l || l > 0 && r > 0 && l <= max/r) { return 1; } warn("overflow in constant expression"); return 0; } static int mulf(TFLOAT l, TFLOAT r, Type *tp) { struct limits *lim = getlimits(tp); TFLOAT max = lim->max.f, min = lim->min.f; if (l > -1 && l <= 1 || r > -1 && r <= 1 || l < 0 && r < 0 && -l <= max/-r || l < 0 && r > 0 && l >= min/r || l > 0 && r < 0 && r >= min/l || l > 0 && r > 0 && l <= max/r) { return 1; } warn("overflow in constant expression"); return 0; } static int divi(TINT l, TINT r, Type *tp) { struct limits *lim = getlimits(tp); if (r == 0 || l == -lim->min.i && r == -1) { warn("overflow in constant expression"); return 0; } return 1; } static int divf(TFLOAT l, TFLOAT r, Type *tp) { struct limits *lim = getlimits(tp); if (l < 0) l = -l; if (r < 0) r = -r; if (r == 0.0 || r < 1.0 && l > lim->max.f * r) { warn("overflow in constant expression"); return 0; } return 1; } static int lshi(TINT l, TINT r, Type *tp) { if (r < 0 || r >= tp->size * 8) { warn("shifting %d bits is undefined", r); return 0; } return muli(l, 1 << r, tp); } static int rshi(TINT l, TINT r, Type *tp) { if (r < 0 || r >= tp->size * 8) { warn("shifting %d bits is undefined", r); return 0; } return 1; } static int foldint(int op, Symbol *res, TINT l, TINT r) { TINT i; Type *tp = res->type; int (*validate)(TINT, TINT, Type *tp); switch (op) { case OADD: validate = addi; break; case OSUB: validate = subi; break; case OMUL: validate = muli; break; case ODIV: validate = divi; break; case OSHL: validate = lshi; break; case OSHR: validate = rshi; break; case OMOD: validate = divi; break; default: validate = NULL; break; } if (validate && !(*validate)(l, r, tp)) return 0; switch (op) { case OADD: i = l + r; break; case OSUB: i = l - r; break; case OMUL: i = l * r; break; case ODIV: i = l / r; break; case OMOD: i = l % r; break; case OSHL: i = l << r; break; case OSHR: i = l >> r; break; case OBAND: i = l & r; break; case OBXOR: i = l ^ r; break; case OBOR: i = l | r; break; case OAND: i = l && r; break; case OOR: i = l || r; break; case OLT: i = l < r; break; case OGT: i = l > r; break; case OGE: i = l >= r; break; case OLE: i = l <= r; break; case OEQ: i = l == r; break; case ONE: i = l != r; break; case ONEG: i = !l; break; case OSNEG: i = -l; break; case OCPL: i = ~l; break; default: return 0; } res->u.i = i; return 1; } static int folduint(int op, Symbol *res, TUINT l, TUINT r) { TINT i; TUINT u; switch (op) { case OADD: u = l + r; break; case OSUB: u = l - r; break; case OMUL: u = l * r; break; case ODIV: u = l / r; break; case OMOD: u = l % r; break; case OSHL: u = l << r; break; case OSHR: u = l >> r; break; case OBAND: u = l & r; break; case OBXOR: u = l ^ r; break; case OBOR: u = l | r; break; case ONEG: u = !l; break; case OSNEG: u = -l; break; case OCPL: u = ~l; break; case OAND: i = l && r; goto sign; case OOR: i = l || r; goto sign; case OLT: i = l < r; goto sign; case OGT: i = l > r; goto sign; case OGE: i = l >= r; goto sign; case OLE: i = l <= r; goto sign; case OEQ: i = l == r; goto sign; case ONE: i = l != r; goto sign; default: return 0; } res->u.u = u & ones(res->type->size); return 1; sign: res->u.i = i; return 1; } static int foldfloat(int op, Symbol *res, TFLOAT l, TFLOAT r) { TFLOAT f; TINT i; int (*validate)(TFLOAT, TFLOAT, Type *tp); switch (op) { case OADD: validate = addf; break; case OSUB: validate = subf; break; case OMUL: validate = mulf; break; case ODIV: validate = divf; break; default: validate = NULL; break; } if (validate && !(*validate)(l, r, res->type)) return 0; switch (op) { case OADD: f = l + r; break; case OSUB: f = l - r; break; case OMUL: f = l * r; break; case ODIV: f = l / r; break; case OLT: i = l < r; goto comparison; case OGT: i = l > r; goto comparison; case OGE: i = l >= r; goto comparison; case OLE: i = l <= r; goto comparison; case OEQ: i = l == r; goto comparison; case ONE: i = l != r; goto comparison; default: return 0; } res->u.f = f; return 1; comparison: res->u.i = i; return 1; } static Node * foldconst(int type, int op, Type *tp, Symbol *ls, Symbol *rs) { Symbol *sym, aux; TINT i; TUINT u; TFLOAT f; aux.type = tp; switch (type) { case INT: i = (rs) ? rs->u.i : 0; if (!foldint(op, &aux, ls->u.i, i)) return NULL; break; case UNSIGNED: u = (rs) ? rs->u.u : 0u; if (!folduint(op, &aux, ls->u.u, u)) return NULL; break; case FLOAT: f = (rs) ? rs->u.f : 0.0; if (!foldfloat(op, &aux, ls->u.f, f)) return NULL; break; } sym = newsym(NS_IDEN, NULL); sym->type = tp; sym->u = aux.u; return constnode(sym); } static Node * fold(int op, Type *tp, Node *lp, Node *rp) { Symbol *rs, *ls; Node *np; Type *optype; int type; if ((op == ODIV || op == OMOD) && cmpnode(rp, 0)) { warn("division by 0"); return NULL; } /* * Return if any of the children is no constant, * or it is a constant generated when * the address of a static variable is taken * (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; } optype = lp->type; ls = lp->sym; rs = (rp) ? rp->sym : NULL; switch (type = optype->op) { case ENUM: case INT: if (!(optype->prop & TSIGNED)) type = UNSIGNED; case PTR: case FLOAT: if ((np = foldconst(type, op, tp, ls, rs)) != NULL) break; default: return NULL; } freetree(lp); freetree(rp); return np; } static void commutative(int *op, Node **lp, Node **rp) { Node *l = *lp, *r = *rp, *aux; if (r == NULL || r->flags & NCONST || !(l->flags & NCONST)) return; switch (*op) { case OLT: case OGT: case OGE: case OLE: *op = negop(*op); case OEQ: case ONE: case OADD: case OMUL: case OBAND: case OBXOR: case OBOR: aux = l; l = r; r = aux; break; } *rp = r; *lp = l; } static Node * identity(int *op, Node *lp, Node *rp) { int iszeror, isoner, istruer; int iszerol, isonel, istruel; if (!rp) return NULL; iszeror = cmpnode(rp, 0); isoner = cmpnode(rp, 1), istruer = !iszeror && rp->flags & NCONST; iszerol = cmpnode(lp, 0); isonel = cmpnode(lp, 1), istruel = !iszerol && lp->flags & NCONST; switch (*op) { case OOR: /* * 1 || i => 1 (free right) * i || 0 => i (free right) * 0 || i => i (free left) * i || 1 => i,1 (comma) */ if (isonel | iszeror) goto free_right; if (iszerol) goto free_left; if (isoner) goto change_to_comma; return NULL; case OAND: /* * 0 && i => 0 (free right) * i && 1 => i (free right) * 1 && i => i (free left) * i && 0 => i,0 (comma) */ if (iszerol | isoner) goto free_right; if (isonel) goto free_left; if (iszeror) goto change_to_comma; return NULL; case OSHL: case OSHR: /* * i >> 0 => i (free right) * i << 0 => i (free right) * 0 >> i => 0 (free right) * 0 << i => 0 (free right) */ if (iszeror | iszerol) goto free_right; return NULL; case OBXOR: case OADD: case OBOR: case OSUB: /* * i + 0 => i * i - 0 => i * i | 0 => i * i ^ 0 => i */ if (iszeror) goto free_right; return NULL; case OMUL: /* * i * 0 => i,0 * i * 1 => i */ if (iszeror) goto change_to_comma; if (isoner) goto free_right; return NULL; case ODIV: /* i / 1 => i */ if (isoner) goto free_right; return NULL; case OBAND: /* i & ~0 => i */ if (cmpnode(rp, -1)) goto free_right; return NULL; case OMOD: /* i % 1 => i,1 */ if (isoner) goto change_to_comma; default: return NULL; } free_right: freetree(rp); return lp; free_left: freetree(lp); return rp; change_to_comma: *op = OCOMMA; return NULL; } static Node * foldternary(int op, Type *tp, Node *cond, Node *body) { Node *np; if (!(cond->flags & NCONST)) return node(op, tp, cond, body); if (cmpnode(cond, 0)) { np = body->right; freetree(body->left); } else { np = body->left; freetree(body->right); } 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 */ 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); }