| // Inferno utils/8c/sgen.c |
| // http://code.google.com/p/inferno-os/source/browse/utils/8c/sgen.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 "gc.h" |
| |
| int32 |
| argsize(void) |
| { |
| Type *t; |
| int32 s; |
| |
| //print("t=%T\n", thisfn); |
| s = 0; |
| for(t=thisfn->down; t!=T; t=t->down) { |
| switch(t->etype) { |
| case TVOID: |
| break; |
| case TDOT: |
| s += 64; |
| break; |
| default: |
| s = align(s, t, Aarg1); |
| s = align(s, t, Aarg2); |
| break; |
| } |
| //print(" %d %T\n", s, t); |
| } |
| return (s+7) & ~7; |
| } |
| |
| void |
| codgen(Node *n, Node *nn) |
| { |
| Prog *sp; |
| Node *n1, nod, nod1; |
| |
| cursafe = 0; |
| curarg = 0; |
| maxargsafe = 0; |
| |
| /* |
| * isolate name |
| */ |
| for(n1 = nn;; n1 = n1->left) { |
| if(n1 == Z) { |
| diag(nn, "cant find function name"); |
| return; |
| } |
| if(n1->op == ONAME) |
| break; |
| } |
| nearln = nn->lineno; |
| |
| gpseudo(ATEXT, n1->sym, nodconst(stkoff)); |
| p->to.type = D_CONST2; |
| p->to.offset2 = argsize(); |
| |
| /* |
| * isolate first argument |
| */ |
| if(REGARG) { |
| if(typesuv[thisfn->link->etype]) { |
| nod1 = *nodret->left; |
| nodreg(&nod, &nod1, REGARG); |
| gmove(&nod, &nod1); |
| } else |
| if(firstarg && typechlp[firstargtype->etype]) { |
| nod1 = *nodret->left; |
| nod1.sym = firstarg; |
| nod1.type = firstargtype; |
| nod1.xoffset = align(0, firstargtype, Aarg1); |
| nod1.etype = firstargtype->etype; |
| nodreg(&nod, &nod1, REGARG); |
| gmove(&nod, &nod1); |
| } |
| } |
| |
| sp = p; |
| retok = 0; |
| gen(n); |
| if(!retok) |
| if(thisfn->link->etype != TVOID) |
| warn(Z, "no return at end of function: %s", n1->sym->name); |
| noretval(3); |
| if(thisfn && thisfn->link && typefd[thisfn->link->etype]) |
| gins(AFLDZ, Z, Z); |
| gbranch(ORETURN); |
| |
| if(!debug['N'] || debug['R'] || debug['P']) |
| regopt(sp); |
| sp->to.offset += maxargsafe; |
| } |
| |
| void |
| supgen(Node *n) |
| { |
| int32 spc; |
| Prog *sp; |
| |
| if(n == Z) |
| return; |
| suppress++; |
| spc = pc; |
| sp = lastp; |
| gen(n); |
| lastp = sp; |
| pc = spc; |
| sp->link = nil; |
| suppress--; |
| } |
| |
| void |
| gen(Node *n) |
| { |
| Node *l, nod; |
| Prog *sp, *spc, *spb; |
| Case *cn; |
| int32 sbc, scc; |
| int f, o; |
| |
| loop: |
| if(n == Z) |
| return; |
| nearln = n->lineno; |
| o = n->op; |
| if(debug['G']) |
| if(o != OLIST) |
| print("%L %O\n", nearln, o); |
| |
| retok = 0; |
| switch(o) { |
| |
| default: |
| complex(n); |
| cgen(n, Z); |
| break; |
| |
| case OLIST: |
| gen(n->left); |
| |
| rloop: |
| n = n->right; |
| goto loop; |
| |
| case ORETURN: |
| retok = 1; |
| complex(n); |
| if(n->type == T) |
| break; |
| l = n->left; |
| if(l == Z) { |
| noretval(3); |
| if(typefd[n->type->etype]) |
| gins(AFLDZ, Z, Z); |
| gbranch(ORETURN); |
| break; |
| } |
| if(typesuv[n->type->etype]) { |
| sugen(l, nodret, n->type->width); |
| noretval(3); |
| gbranch(ORETURN); |
| break; |
| } |
| regret(&nod, n); |
| cgen(l, &nod); |
| regfree(&nod); |
| if(typefd[n->type->etype]) |
| noretval(1); |
| else |
| noretval(2); |
| gbranch(ORETURN); |
| break; |
| |
| case OLABEL: |
| l = n->left; |
| if(l) { |
| l->xoffset = pc; |
| if(l->label) |
| patch(l->label, pc); |
| } |
| gbranch(OGOTO); /* prevent self reference in reg */ |
| patch(p, pc); |
| goto rloop; |
| |
| case OGOTO: |
| retok = 1; |
| n = n->left; |
| if(n == Z) |
| return; |
| if(n->complex == 0) { |
| diag(Z, "label undefined: %s", n->sym->name); |
| return; |
| } |
| if(suppress) |
| return; |
| gbranch(OGOTO); |
| if(n->xoffset) { |
| patch(p, n->xoffset); |
| return; |
| } |
| if(n->label) |
| patch(n->label, pc-1); |
| n->label = p; |
| return; |
| |
| case OCASE: |
| l = n->left; |
| if(cases == C) |
| diag(n, "case/default outside a switch"); |
| if(l == Z) { |
| cas(); |
| cases->val = 0; |
| cases->def = 1; |
| cases->label = pc; |
| goto rloop; |
| } |
| complex(l); |
| if(l->type == T) |
| goto rloop; |
| if(l->op == OCONST) |
| if(typechl[l->type->etype]) { |
| cas(); |
| cases->val = l->vconst; |
| cases->def = 0; |
| cases->label = pc; |
| goto rloop; |
| } |
| diag(n, "case expression must be integer constant"); |
| goto rloop; |
| |
| case OSWITCH: |
| l = n->left; |
| complex(l); |
| if(l->type == T) |
| break; |
| if(!typechl[l->type->etype]) { |
| diag(n, "switch expression must be integer"); |
| break; |
| } |
| |
| gbranch(OGOTO); /* entry */ |
| sp = p; |
| |
| cn = cases; |
| cases = C; |
| cas(); |
| |
| sbc = breakpc; |
| breakpc = pc; |
| gbranch(OGOTO); |
| spb = p; |
| |
| gen(n->right); |
| gbranch(OGOTO); |
| patch(p, breakpc); |
| |
| patch(sp, pc); |
| regalloc(&nod, l, Z); |
| nod.type = types[TLONG]; |
| cgen(l, &nod); |
| doswit(&nod); |
| regfree(&nod); |
| patch(spb, pc); |
| |
| cases = cn; |
| breakpc = sbc; |
| break; |
| |
| case OWHILE: |
| case ODWHILE: |
| l = n->left; |
| gbranch(OGOTO); /* entry */ |
| sp = p; |
| |
| scc = continpc; |
| continpc = pc; |
| gbranch(OGOTO); |
| spc = p; |
| |
| sbc = breakpc; |
| breakpc = pc; |
| gbranch(OGOTO); |
| spb = p; |
| |
| patch(spc, pc); |
| if(n->op == OWHILE) |
| patch(sp, pc); |
| bcomplex(l, Z); /* test */ |
| patch(p, breakpc); |
| |
| if(n->op == ODWHILE) |
| patch(sp, pc); |
| gen(n->right); /* body */ |
| gbranch(OGOTO); |
| patch(p, continpc); |
| |
| patch(spb, pc); |
| continpc = scc; |
| breakpc = sbc; |
| break; |
| |
| case OFOR: |
| l = n->left; |
| gen(l->right->left); /* init */ |
| gbranch(OGOTO); /* entry */ |
| sp = p; |
| |
| scc = continpc; |
| continpc = pc; |
| gbranch(OGOTO); |
| spc = p; |
| |
| sbc = breakpc; |
| breakpc = pc; |
| gbranch(OGOTO); |
| spb = p; |
| |
| patch(spc, pc); |
| gen(l->right->right); /* inc */ |
| patch(sp, pc); |
| if(l->left != Z) { /* test */ |
| bcomplex(l->left, Z); |
| patch(p, breakpc); |
| } |
| gen(n->right); /* body */ |
| gbranch(OGOTO); |
| patch(p, continpc); |
| |
| patch(spb, pc); |
| continpc = scc; |
| breakpc = sbc; |
| break; |
| |
| case OCONTINUE: |
| if(continpc < 0) { |
| diag(n, "continue not in a loop"); |
| break; |
| } |
| gbranch(OGOTO); |
| patch(p, continpc); |
| break; |
| |
| case OBREAK: |
| if(breakpc < 0) { |
| diag(n, "break not in a loop"); |
| break; |
| } |
| gbranch(OGOTO); |
| patch(p, breakpc); |
| break; |
| |
| case OIF: |
| l = n->left; |
| if(bcomplex(l, n->right)) { |
| if(typefd[l->type->etype]) |
| f = !l->fconst; |
| else |
| f = !l->vconst; |
| if(debug['c']) |
| print("%L const if %s\n", nearln, f ? "false" : "true"); |
| if(f) { |
| supgen(n->right->left); |
| gen(n->right->right); |
| } |
| else { |
| gen(n->right->left); |
| supgen(n->right->right); |
| } |
| } |
| else { |
| sp = p; |
| if(n->right->left != Z) |
| gen(n->right->left); |
| if(n->right->right != Z) { |
| gbranch(OGOTO); |
| patch(sp, pc); |
| sp = p; |
| gen(n->right->right); |
| } |
| patch(sp, pc); |
| } |
| break; |
| |
| case OSET: |
| case OUSED: |
| usedset(n->left, o); |
| break; |
| } |
| } |
| |
| void |
| usedset(Node *n, int o) |
| { |
| if(n->op == OLIST) { |
| usedset(n->left, o); |
| usedset(n->right, o); |
| return; |
| } |
| complex(n); |
| switch(n->op) { |
| case OADDR: /* volatile */ |
| gins(ANOP, n, Z); |
| break; |
| case ONAME: |
| if(o == OSET) |
| gins(ANOP, Z, n); |
| else |
| gins(ANOP, n, Z); |
| break; |
| } |
| } |
| |
| void |
| noretval(int n) |
| { |
| |
| if(n & 1) { |
| gins(ANOP, Z, Z); |
| p->to.type = REGRET; |
| } |
| if(n & 2) { |
| gins(ANOP, Z, Z); |
| p->to.type = FREGRET; |
| } |
| } |
| |
| /* welcome to commute */ |
| static void |
| commute(Node *n) |
| { |
| Node *l, *r; |
| |
| l = n->left; |
| r = n->right; |
| if(r->complex > l->complex) { |
| n->left = r; |
| n->right = l; |
| } |
| } |
| |
| void |
| indexshift(Node *n) |
| { |
| int g; |
| |
| if(!typechlp[n->type->etype]) |
| return; |
| simplifyshift(n); |
| if(n->op == OASHL && n->right->op == OCONST){ |
| g = vconst(n->right); |
| if(g >= 0 && g < 4) |
| n->addable = 7; |
| } |
| } |
| |
| /* |
| * calculate addressability as follows |
| * NAME ==> 10/11 name+value(SB/SP) |
| * REGISTER ==> 12 register |
| * CONST ==> 20 $value |
| * *(20) ==> 21 value |
| * &(10) ==> 13 $name+value(SB) |
| * &(11) ==> 1 $name+value(SP) |
| * (13) + (20) ==> 13 fold constants |
| * (1) + (20) ==> 1 fold constants |
| * *(13) ==> 10 back to name |
| * *(1) ==> 11 back to name |
| * |
| * (20) * (X) ==> 7 multiplier in indexing |
| * (X,7) + (13,1) ==> 8 adder in indexing (addresses) |
| * (8) ==> &9(OINDEX) index, almost addressable |
| * |
| * calculate complexity (number of registers) |
| */ |
| void |
| xcom(Node *n) |
| { |
| Node *l, *r; |
| int g; |
| |
| if(n == Z) |
| return; |
| l = n->left; |
| r = n->right; |
| n->complex = 0; |
| n->addable = 0; |
| switch(n->op) { |
| case OCONST: |
| n->addable = 20; |
| break; |
| |
| case ONAME: |
| n->addable = 10; |
| if(n->class == CPARAM || n->class == CAUTO) |
| n->addable = 11; |
| break; |
| |
| case OEXREG: |
| n->addable = 10; |
| break; |
| |
| case OREGISTER: |
| n->addable = 12; |
| break; |
| |
| case OINDREG: |
| n->addable = 12; |
| break; |
| |
| case OADDR: |
| xcom(l); |
| if(l->addable == 10) |
| n->addable = 13; |
| else |
| if(l->addable == 11) |
| n->addable = 1; |
| break; |
| |
| case OADD: |
| xcom(l); |
| xcom(r); |
| if(n->type->etype != TIND) |
| break; |
| |
| switch(r->addable) { |
| case 20: |
| switch(l->addable) { |
| case 1: |
| case 13: |
| commadd: |
| l->type = n->type; |
| *n = *l; |
| l = new(0, Z, Z); |
| *l = *(n->left); |
| l->xoffset += r->vconst; |
| n->left = l; |
| r = n->right; |
| goto brk; |
| } |
| break; |
| |
| case 1: |
| case 13: |
| case 10: |
| case 11: |
| /* l is the base, r is the index */ |
| if(l->addable != 20) |
| n->addable = 8; |
| break; |
| } |
| switch(l->addable) { |
| case 20: |
| switch(r->addable) { |
| case 13: |
| case 1: |
| r = n->left; |
| l = n->right; |
| n->left = l; |
| n->right = r; |
| goto commadd; |
| } |
| break; |
| |
| case 13: |
| case 1: |
| case 10: |
| case 11: |
| /* r is the base, l is the index */ |
| if(r->addable != 20) |
| n->addable = 8; |
| break; |
| } |
| if(n->addable == 8 && !side(n)) { |
| indx(n); |
| l = new1(OINDEX, idx.basetree, idx.regtree); |
| l->scale = idx.scale; |
| l->addable = 9; |
| l->complex = l->right->complex; |
| l->type = l->left->type; |
| n->op = OADDR; |
| n->left = l; |
| n->right = Z; |
| n->addable = 8; |
| break; |
| } |
| break; |
| |
| case OINDEX: |
| xcom(l); |
| xcom(r); |
| n->addable = 9; |
| break; |
| |
| case OIND: |
| xcom(l); |
| if(l->op == OADDR) { |
| l = l->left; |
| l->type = n->type; |
| *n = *l; |
| return; |
| } |
| switch(l->addable) { |
| case 20: |
| n->addable = 21; |
| break; |
| case 1: |
| n->addable = 11; |
| break; |
| case 13: |
| n->addable = 10; |
| break; |
| } |
| break; |
| |
| case OASHL: |
| xcom(l); |
| xcom(r); |
| indexshift(n); |
| break; |
| |
| case OMUL: |
| case OLMUL: |
| xcom(l); |
| xcom(r); |
| g = vlog(l); |
| if(g >= 0) { |
| n->left = r; |
| n->right = l; |
| l = r; |
| r = n->right; |
| } |
| g = vlog(r); |
| if(g >= 0) { |
| n->op = OASHL; |
| r->vconst = g; |
| r->type = types[TINT]; |
| indexshift(n); |
| break; |
| } |
| commute(n); |
| break; |
| |
| case OASLDIV: |
| xcom(l); |
| xcom(r); |
| g = vlog(r); |
| if(g >= 0) { |
| n->op = OASLSHR; |
| r->vconst = g; |
| r->type = types[TINT]; |
| } |
| break; |
| |
| case OLDIV: |
| xcom(l); |
| xcom(r); |
| g = vlog(r); |
| if(g >= 0) { |
| n->op = OLSHR; |
| r->vconst = g; |
| r->type = types[TINT]; |
| indexshift(n); |
| break; |
| } |
| break; |
| |
| case OASLMOD: |
| xcom(l); |
| xcom(r); |
| g = vlog(r); |
| if(g >= 0) { |
| n->op = OASAND; |
| r->vconst--; |
| } |
| break; |
| |
| case OLMOD: |
| xcom(l); |
| xcom(r); |
| g = vlog(r); |
| if(g >= 0) { |
| n->op = OAND; |
| r->vconst--; |
| } |
| break; |
| |
| case OASMUL: |
| case OASLMUL: |
| xcom(l); |
| xcom(r); |
| g = vlog(r); |
| if(g >= 0) { |
| n->op = OASASHL; |
| r->vconst = g; |
| } |
| break; |
| |
| case OLSHR: |
| case OASHR: |
| xcom(l); |
| xcom(r); |
| indexshift(n); |
| break; |
| |
| default: |
| if(l != Z) |
| xcom(l); |
| if(r != Z) |
| xcom(r); |
| break; |
| } |
| brk: |
| if(n->addable >= 10) |
| return; |
| if(l != Z) |
| n->complex = l->complex; |
| if(r != Z) { |
| if(r->complex == n->complex) |
| n->complex = r->complex+1; |
| else |
| if(r->complex > n->complex) |
| n->complex = r->complex; |
| } |
| if(n->complex == 0) |
| n->complex++; |
| |
| if(com64(n)) |
| return; |
| |
| switch(n->op) { |
| |
| case OFUNC: |
| n->complex = FNX; |
| break; |
| |
| case OLMOD: |
| case OMOD: |
| case OLMUL: |
| case OLDIV: |
| case OMUL: |
| case ODIV: |
| case OASLMUL: |
| case OASLDIV: |
| case OASLMOD: |
| case OASMUL: |
| case OASDIV: |
| case OASMOD: |
| if(r->complex >= l->complex) { |
| n->complex = l->complex + 3; |
| if(r->complex > n->complex) |
| n->complex = r->complex; |
| } else { |
| n->complex = r->complex + 3; |
| if(l->complex > n->complex) |
| n->complex = l->complex; |
| } |
| break; |
| |
| case OLSHR: |
| case OASHL: |
| case OASHR: |
| case OASLSHR: |
| case OASASHL: |
| case OASASHR: |
| if(r->complex >= l->complex) { |
| n->complex = l->complex + 2; |
| if(r->complex > n->complex) |
| n->complex = r->complex; |
| } else { |
| n->complex = r->complex + 2; |
| if(l->complex > n->complex) |
| n->complex = l->complex; |
| } |
| break; |
| |
| case OADD: |
| case OXOR: |
| case OAND: |
| case OOR: |
| /* |
| * immediate operators, make const on right |
| */ |
| if(l->op == OCONST) { |
| n->left = r; |
| n->right = l; |
| } |
| break; |
| |
| case OEQ: |
| case ONE: |
| case OLE: |
| case OLT: |
| case OGE: |
| case OGT: |
| case OHI: |
| case OHS: |
| case OLO: |
| case OLS: |
| /* |
| * compare operators, make const on left |
| */ |
| if(r->op == OCONST) { |
| n->left = r; |
| n->right = l; |
| n->op = invrel[relindex(n->op)]; |
| } |
| break; |
| } |
| } |
| |
| void |
| indx(Node *n) |
| { |
| Node *l, *r; |
| |
| if(debug['x']) |
| prtree(n, "indx"); |
| |
| l = n->left; |
| r = n->right; |
| if(l->addable == 1 || l->addable == 13 || r->complex > l->complex) { |
| n->right = l; |
| n->left = r; |
| l = r; |
| r = n->right; |
| } |
| if(l->addable != 7) { |
| idx.regtree = l; |
| idx.scale = 1; |
| } else |
| if(l->right->addable == 20) { |
| idx.regtree = l->left; |
| idx.scale = 1 << l->right->vconst; |
| } else |
| if(l->left->addable == 20) { |
| idx.regtree = l->right; |
| idx.scale = 1 << l->left->vconst; |
| } else |
| diag(n, "bad index"); |
| |
| idx.basetree = r; |
| if(debug['x']) { |
| print("scale = %d\n", idx.scale); |
| prtree(idx.regtree, "index"); |
| prtree(idx.basetree, "base"); |
| } |
| } |
| |
| int |
| bcomplex(Node *n, Node *c) |
| { |
| Node *b, nod; |
| |
| complex(n); |
| if(n->type != T) |
| if(tcompat(n, T, n->type, tnot)) |
| n->type = T; |
| if(n->type != T) { |
| if(c != Z && n->op == OCONST && deadheads(c)) |
| return 1; |
| if(typev[n->type->etype] && machcap(Z)) { |
| b = &nod; |
| b->op = ONE; |
| b->left = n; |
| b->right = new(0, Z, Z); |
| *b->right = *nodconst(0); |
| b->right->type = n->type; |
| b->type = types[TLONG]; |
| cgen64(b, Z); |
| return 0; |
| } |
| bool64(n); |
| boolgen(n, 1, Z); |
| } else |
| gbranch(OGOTO); |
| return 0; |
| } |