| // Inferno utils/cc/scon.c |
| // http://code.google.com/p/inferno-os/source/browse/utils/cc/scon.c |
| // |
| // Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved. |
| // Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net) |
| // Portions Copyright © 1997-1999 Vita Nuova Limited |
| // Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com) |
| // Portions Copyright © 2004,2006 Bruce Ellis |
| // Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net) |
| // Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others |
| // Portions Copyright © 2009 The Go Authors. All rights reserved. |
| // |
| // Permission is hereby granted, free of charge, to any person obtaining a copy |
| // of this software and associated documentation files (the "Software"), to deal |
| // in the Software without restriction, including without limitation the rights |
| // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| // copies of the Software, and to permit persons to whom the Software is |
| // furnished to do so, subject to the following conditions: |
| // |
| // The above copyright notice and this permission notice shall be included in |
| // all copies or substantial portions of the Software. |
| // |
| // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
| // THE SOFTWARE. |
| |
| #include <u.h> |
| #include "cc.h" |
| |
| static Node* |
| acast(Type *t, Node *n) |
| { |
| if(n->type->etype != t->etype || n->op == OBIT) { |
| n = new1(OCAST, n, Z); |
| if(nocast(n->left->type, t)) |
| *n = *n->left; |
| n->type = t; |
| } |
| return n; |
| } |
| |
| |
| void |
| evconst(Node *n) |
| { |
| Node *l, *r; |
| int et, isf; |
| vlong v; |
| double d; |
| |
| if(n == Z || n->type == T) |
| return; |
| |
| et = n->type->etype; |
| isf = typefd[et]; |
| |
| l = n->left; |
| r = n->right; |
| |
| d = 0; |
| v = 0; |
| |
| switch(n->op) { |
| default: |
| return; |
| |
| case ONEG: |
| if(isf) |
| d = -l->fconst; |
| else |
| v = -l->vconst; |
| break; |
| |
| case OCOM: |
| v = ~l->vconst; |
| break; |
| |
| case OCAST: |
| if(et == TVOID) |
| return; |
| et = l->type->etype; |
| if(isf) { |
| if(typefd[et]) |
| d = l->fconst; |
| else |
| d = l->vconst; |
| } else { |
| if(typefd[et]) |
| v = l->fconst; |
| else |
| v = convvtox(l->vconst, n->type->etype); |
| } |
| break; |
| |
| case OCONST: |
| break; |
| |
| case OADD: |
| if(isf) |
| d = l->fconst + r->fconst; |
| else { |
| v = l->vconst + r->vconst; |
| } |
| break; |
| |
| case OSUB: |
| if(isf) |
| d = l->fconst - r->fconst; |
| else |
| v = l->vconst - r->vconst; |
| break; |
| |
| case OMUL: |
| if(isf) |
| d = l->fconst * r->fconst; |
| else { |
| v = l->vconst * r->vconst; |
| } |
| break; |
| |
| case OLMUL: |
| v = (uvlong)l->vconst * (uvlong)r->vconst; |
| break; |
| |
| |
| case ODIV: |
| if(vconst(r) == 0) { |
| warn(n, "divide by zero"); |
| return; |
| } |
| if(isf) |
| d = l->fconst / r->fconst; |
| else |
| v = l->vconst / r->vconst; |
| break; |
| |
| case OLDIV: |
| if(vconst(r) == 0) { |
| warn(n, "divide by zero"); |
| return; |
| } |
| v = (uvlong)l->vconst / (uvlong)r->vconst; |
| break; |
| |
| case OMOD: |
| if(vconst(r) == 0) { |
| warn(n, "modulo by zero"); |
| return; |
| } |
| v = l->vconst % r->vconst; |
| break; |
| |
| case OLMOD: |
| if(vconst(r) == 0) { |
| warn(n, "modulo by zero"); |
| return; |
| } |
| v = (uvlong)l->vconst % (uvlong)r->vconst; |
| break; |
| |
| case OAND: |
| v = l->vconst & r->vconst; |
| break; |
| |
| case OOR: |
| v = l->vconst | r->vconst; |
| break; |
| |
| case OXOR: |
| v = l->vconst ^ r->vconst; |
| break; |
| |
| case OLSHR: |
| if(l->type->width != sizeof(uvlong)) |
| v = ((uvlong)l->vconst & 0xffffffffULL) >> r->vconst; |
| else |
| v = (uvlong)l->vconst >> r->vconst; |
| break; |
| |
| case OASHR: |
| v = l->vconst >> r->vconst; |
| break; |
| |
| case OASHL: |
| v = (uvlong)l->vconst << r->vconst; |
| break; |
| |
| case OLO: |
| v = (uvlong)l->vconst < (uvlong)r->vconst; |
| break; |
| |
| case OLT: |
| if(typefd[l->type->etype]) |
| v = l->fconst < r->fconst; |
| else |
| v = l->vconst < r->vconst; |
| break; |
| |
| case OHI: |
| v = (uvlong)l->vconst > (uvlong)r->vconst; |
| break; |
| |
| case OGT: |
| if(typefd[l->type->etype]) |
| v = l->fconst > r->fconst; |
| else |
| v = l->vconst > r->vconst; |
| break; |
| |
| case OLS: |
| v = (uvlong)l->vconst <= (uvlong)r->vconst; |
| break; |
| |
| case OLE: |
| if(typefd[l->type->etype]) |
| v = l->fconst <= r->fconst; |
| else |
| v = l->vconst <= r->vconst; |
| break; |
| |
| case OHS: |
| v = (uvlong)l->vconst >= (uvlong)r->vconst; |
| break; |
| |
| case OGE: |
| if(typefd[l->type->etype]) |
| v = l->fconst >= r->fconst; |
| else |
| v = l->vconst >= r->vconst; |
| break; |
| |
| case OEQ: |
| if(typefd[l->type->etype]) |
| v = l->fconst == r->fconst; |
| else |
| v = l->vconst == r->vconst; |
| break; |
| |
| case ONE: |
| if(typefd[l->type->etype]) |
| v = l->fconst != r->fconst; |
| else |
| v = l->vconst != r->vconst; |
| break; |
| |
| case ONOT: |
| if(typefd[l->type->etype]) |
| v = !l->fconst; |
| else |
| v = !l->vconst; |
| break; |
| |
| case OANDAND: |
| if(typefd[l->type->etype]) |
| v = l->fconst && r->fconst; |
| else |
| v = l->vconst && r->vconst; |
| break; |
| |
| case OOROR: |
| if(typefd[l->type->etype]) |
| v = l->fconst || r->fconst; |
| else |
| v = l->vconst || r->vconst; |
| break; |
| } |
| if(isf) { |
| n->fconst = d; |
| } else { |
| n->vconst = convvtox(v, n->type->etype); |
| } |
| n->oldop = n->op; |
| n->op = OCONST; |
| } |
| |
| void |
| acom(Node *n) |
| { |
| Type *t; |
| Node *l, *r; |
| int i; |
| |
| switch(n->op) |
| { |
| |
| case ONAME: |
| case OCONST: |
| case OSTRING: |
| case OINDREG: |
| case OREGISTER: |
| return; |
| |
| case ONEG: |
| l = n->left; |
| if(addo(n) && addo(l)) |
| break; |
| acom(l); |
| return; |
| |
| case OADD: |
| case OSUB: |
| case OMUL: |
| l = n->left; |
| r = n->right; |
| if(addo(n)) { |
| if(addo(r)) |
| break; |
| if(addo(l)) |
| break; |
| } |
| acom(l); |
| acom(r); |
| return; |
| |
| default: |
| l = n->left; |
| r = n->right; |
| if(l != Z) |
| acom(l); |
| if(r != Z) |
| acom(r); |
| return; |
| } |
| |
| /* bust terms out */ |
| t = n->type; |
| term[0].mult = 0; |
| term[0].node = Z; |
| nterm = 1; |
| acom1(1, n); |
| if(debug['m']) |
| for(i=0; i<nterm; i++) { |
| print("%d %3lld ", i, term[i].mult); |
| prtree1(term[i].node, 1, 0); |
| } |
| if(nterm < NTERM) |
| acom2(n, t); |
| n->type = t; |
| } |
| |
| int |
| acomcmp1(const void *a1, const void *a2) |
| { |
| vlong c1, c2; |
| Term *t1, *t2; |
| |
| t1 = (Term*)a1; |
| t2 = (Term*)a2; |
| c1 = t1->mult; |
| if(c1 < 0) |
| c1 = -c1; |
| c2 = t2->mult; |
| if(c2 < 0) |
| c2 = -c2; |
| if(c1 > c2) |
| return 1; |
| if(c1 < c2) |
| return -1; |
| c1 = 1; |
| if(t1->mult < 0) |
| c1 = 0; |
| c2 = 1; |
| if(t2->mult < 0) |
| c2 = 0; |
| if(c2 -= c1) |
| return c2; |
| if(t2 > t1) |
| return 1; |
| return -1; |
| } |
| |
| int |
| acomcmp2(const void *a1, const void *a2) |
| { |
| vlong c1, c2; |
| Term *t1, *t2; |
| |
| t1 = (Term*)a1; |
| t2 = (Term*)a2; |
| c1 = t1->mult; |
| c2 = t2->mult; |
| if(c1 > c2) |
| return 1; |
| if(c1 < c2) |
| return -1; |
| if(t2 > t1) |
| return 1; |
| return -1; |
| } |
| |
| void |
| acom2(Node *n, Type *t) |
| { |
| Node *l, *r; |
| Term trm[NTERM]; |
| int et, nt, i, j; |
| vlong c1, c2; |
| |
| /* |
| * copy into automatic |
| */ |
| c2 = 0; |
| nt = nterm; |
| for(i=0; i<nt; i++) |
| trm[i] = term[i]; |
| /* |
| * recur on subtrees |
| */ |
| j = 0; |
| for(i=1; i<nt; i++) { |
| c1 = trm[i].mult; |
| if(c1 == 0) |
| continue; |
| l = trm[i].node; |
| if(l != Z) { |
| j = 1; |
| acom(l); |
| } |
| } |
| c1 = trm[0].mult; |
| if(j == 0) { |
| n->oldop = n->op; |
| n->op = OCONST; |
| n->vconst = c1; |
| return; |
| } |
| et = t->etype; |
| |
| /* |
| * prepare constant term, |
| * combine it with an addressing term |
| */ |
| if(c1 != 0) { |
| l = new1(OCONST, Z, Z); |
| l->type = t; |
| l->vconst = c1; |
| trm[0].mult = 1; |
| for(i=1; i<nt; i++) { |
| if(trm[i].mult != 1) |
| continue; |
| r = trm[i].node; |
| if(r->op != OADDR) |
| continue; |
| r->type = t; |
| l = new1(OADD, r, l); |
| l->type = t; |
| trm[i].mult = 0; |
| break; |
| } |
| trm[0].node = l; |
| } |
| /* |
| * look for factorable terms |
| * c1*i + c1*c2*j -> c1*(i + c2*j) |
| */ |
| qsort(trm+1, nt-1, sizeof(trm[0]), acomcmp1); |
| for(i=nt-1; i>=0; i--) { |
| c1 = trm[i].mult; |
| if(c1 < 0) |
| c1 = -c1; |
| if(c1 <= 1) |
| continue; |
| for(j=i+1; j<nt; j++) { |
| c2 = trm[j].mult; |
| if(c2 < 0) |
| c2 = -c2; |
| if(c2 <= 1) |
| continue; |
| if(c2 % c1) |
| continue; |
| r = trm[j].node; |
| if(r->type->etype != et) |
| r = acast(t, r); |
| c2 = trm[j].mult/trm[i].mult; |
| if(c2 != 1 && c2 != -1) { |
| r = new1(OMUL, r, new(OCONST, Z, Z)); |
| r->type = t; |
| r->right->type = t; |
| r->right->vconst = c2; |
| } |
| l = trm[i].node; |
| if(l->type->etype != et) |
| l = acast(t, l); |
| r = new1(OADD, l, r); |
| r->type = t; |
| if(c2 == -1) |
| r->op = OSUB; |
| trm[i].node = r; |
| trm[j].mult = 0; |
| } |
| } |
| if(debug['m']) { |
| print("\n"); |
| for(i=0; i<nt; i++) { |
| print("%d %3lld ", i, trm[i].mult); |
| prtree1(trm[i].node, 1, 0); |
| } |
| } |
| |
| /* |
| * put it all back together |
| */ |
| qsort(trm+1, nt-1, sizeof(trm[0]), acomcmp2); |
| l = Z; |
| for(i=nt-1; i>=0; i--) { |
| c1 = trm[i].mult; |
| if(c1 == 0) |
| continue; |
| r = trm[i].node; |
| if(r->type->etype != et || r->op == OBIT) |
| r = acast(t, r); |
| if(c1 != 1 && c1 != -1) { |
| r = new1(OMUL, r, new(OCONST, Z, Z)); |
| r->type = t; |
| r->right->type = t; |
| if(c1 < 0) { |
| r->right->vconst = -c1; |
| c1 = -1; |
| } else { |
| r->right->vconst = c1; |
| c1 = 1; |
| } |
| } |
| if(l == Z) { |
| l = r; |
| c2 = c1; |
| continue; |
| } |
| if(c1 < 0) |
| if(c2 < 0) |
| l = new1(OADD, l, r); |
| else |
| l = new1(OSUB, l, r); |
| else |
| if(c2 < 0) { |
| l = new1(OSUB, r, l); |
| c2 = 1; |
| } else |
| l = new1(OADD, l, r); |
| l->type = t; |
| } |
| if(c2 < 0) { |
| r = new1(OCONST, 0, 0); |
| r->vconst = 0; |
| r->type = t; |
| l = new1(OSUB, r, l); |
| l->type = t; |
| } |
| *n = *l; |
| } |
| |
| void |
| acom1(vlong v, Node *n) |
| { |
| Node *l, *r; |
| |
| if(v == 0 || nterm >= NTERM) |
| return; |
| if(!addo(n)) { |
| if(n->op == OCONST) |
| if(!typefd[n->type->etype]) { |
| term[0].mult += v*n->vconst; |
| return; |
| } |
| term[nterm].mult = v; |
| term[nterm].node = n; |
| nterm++; |
| return; |
| } |
| switch(n->op) { |
| |
| case OCAST: |
| acom1(v, n->left); |
| break; |
| |
| case ONEG: |
| acom1(-v, n->left); |
| break; |
| |
| case OADD: |
| acom1(v, n->left); |
| acom1(v, n->right); |
| break; |
| |
| case OSUB: |
| acom1(v, n->left); |
| acom1(-v, n->right); |
| break; |
| |
| case OMUL: |
| l = n->left; |
| r = n->right; |
| if(l->op == OCONST) |
| if(!typefd[n->type->etype]) { |
| acom1(v*l->vconst, r); |
| break; |
| } |
| if(r->op == OCONST) |
| if(!typefd[n->type->etype]) { |
| acom1(v*r->vconst, l); |
| break; |
| } |
| break; |
| |
| default: |
| diag(n, "not addo"); |
| } |
| } |
| |
| int |
| addo(Node *n) |
| { |
| |
| if(n != Z) |
| if(!typefd[n->type->etype]) |
| if(!typev[n->type->etype] || ewidth[TVLONG] == ewidth[TIND]) |
| switch(n->op) { |
| |
| case OCAST: |
| if(nilcast(n->left->type, n->type)) |
| return 1; |
| break; |
| |
| case ONEG: |
| case OADD: |
| case OSUB: |
| return 1; |
| |
| case OMUL: |
| if(n->left->op == OCONST) |
| return 1; |
| if(n->right->op == OCONST) |
| return 1; |
| } |
| return 0; |
| } |