// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
#include <u.h>
#include <libc.h>
#include "go.h"
static Node* walkprint(Node*, NodeList**, int);
static Node* mapfn(char*, Type*);
static Node* mapfndel(char*, Type*);
static Node* ascompatee1(int, Node*, Node*, NodeList**);
static NodeList* ascompatee(int, NodeList*, NodeList*, NodeList**);
static NodeList* ascompatet(int, NodeList*, Type**, int, NodeList**);
static NodeList* ascompatte(int, Node*, int, Type**, NodeList*, int, NodeList**);
static Node* convas(Node*, NodeList**);
static void heapmoves(void);
static NodeList* paramstoheap(Type **argin, int out);
static NodeList* reorder1(NodeList*);
static NodeList* reorder3(NodeList*);
static Node* addstr(Node*, NodeList**);
static Node* appendslice(Node*, NodeList**);
static Node* append(Node*, NodeList**);
static Node* copyany(Node*, NodeList**, int);
static Node* sliceany(Node*, NodeList**);
static void walkcompare(Node**, NodeList**);
static void walkrotate(Node**);
static void walkmul(Node**, NodeList**);
static void walkdiv(Node**, NodeList**);
static int bounded(Node*, int64);
static Mpint mpzero;
void
walk(Node *fn)
{
char s[50];
NodeList *l;
int lno;
curfn = fn;
if(debug['W']) {
snprint(s, sizeof(s), "\nbefore %S", curfn->nname->sym);
dumplist(s, curfn->nbody);
}
lno = lineno;
// Final typecheck for any unused variables.
// It's hard to be on the heap when not-used, but best to be consistent about &~PHEAP here and below.
for(l=fn->dcl; l; l=l->next)
if(l->n->op == ONAME && (l->n->class&~PHEAP) == PAUTO)
typecheck(&l->n, Erv | Easgn);
// Propagate the used flag for typeswitch variables up to the NONAME in it's definition.
for(l=fn->dcl; l; l=l->next)
if(l->n->op == ONAME && (l->n->class&~PHEAP) == PAUTO && l->n->defn && l->n->defn->op == OTYPESW && l->n->used)
l->n->defn->left->used++;
for(l=fn->dcl; l; l=l->next) {
if(l->n->op != ONAME || (l->n->class&~PHEAP) != PAUTO || l->n->sym->name[0] == '&' || l->n->used)
continue;
if(l->n->defn && l->n->defn->op == OTYPESW) {
if(l->n->defn->left->used)
continue;
lineno = l->n->defn->left->lineno;
yyerror("%S declared and not used", l->n->sym);
l->n->defn->left->used = 1; // suppress repeats
} else {
lineno = l->n->lineno;
yyerror("%S declared and not used", l->n->sym);
}
}
lineno = lno;
if(nerrors != 0)
return;
walkstmtlist(curfn->nbody);
if(debug['W']) {
snprint(s, sizeof(s), "after walk %S", curfn->nname->sym);
dumplist(s, curfn->nbody);
}
heapmoves();
if(debug['W'] && curfn->enter != nil) {
snprint(s, sizeof(s), "enter %S", curfn->nname->sym);
dumplist(s, curfn->enter);
}
}
void
walkstmtlist(NodeList *l)
{
for(; l; l=l->next)
walkstmt(&l->n);
}
static int
samelist(NodeList *a, NodeList *b)
{
for(; a && b; a=a->next, b=b->next)
if(a->n != b->n)
return 0;
return a == b;
}
static int
paramoutheap(Node *fn)
{
NodeList *l;
for(l=fn->dcl; l; l=l->next) {
switch(l->n->class) {
case PPARAMOUT:
case PPARAMOUT|PHEAP:
return l->n->addrtaken;
case PAUTO:
case PAUTO|PHEAP:
// stop early - parameters are over
return 0;
}
}
return 0;
}
void
walkstmt(Node **np)
{
NodeList *init;
NodeList *ll, *rl;
int cl;
Node *n, *f;
n = *np;
if(n == N)
return;
setlineno(n);
walkstmtlist(n->ninit);
switch(n->op) {
default:
if(n->op == ONAME)
yyerror("%S is not a top level statement", n->sym);
else
yyerror("%O is not a top level statement", n->op);
dump("nottop", n);
break;
case OAS:
case OASOP:
case OAS2:
case OAS2DOTTYPE:
case OAS2RECV:
case OAS2FUNC:
case OAS2MAPR:
case OCLOSE:
case OCOPY:
case OCALLMETH:
case OCALLINTER:
case OCALL:
case OCALLFUNC:
case ODELETE:
case OSEND:
case OPRINT:
case OPRINTN:
case OPANIC:
case OEMPTY:
case ORECOVER:
if(n->typecheck == 0)
fatal("missing typecheck: %+N", n);
init = n->ninit;
n->ninit = nil;
walkexpr(&n, &init);
addinit(&n, init);
if((*np)->op == OCOPY && n->op == OCONVNOP)
n->op = OEMPTY; // don't leave plain values as statements.
break;
case ORECV:
// special case for a receive where we throw away
// the value received.
if(n->typecheck == 0)
fatal("missing typecheck: %+N", n);
init = n->ninit;
n->ninit = nil;
walkexpr(&n->left, &init);
n = mkcall1(chanfn("chanrecv1", 2, n->left->type), T, &init, typename(n->left->type), n->left, nodnil());
walkexpr(&n, &init);
addinit(&n, init);
break;
case OBREAK:
case ODCL:
case OCONTINUE:
case OFALL:
case OGOTO:
case OLABEL:
case ODCLCONST:
case ODCLTYPE:
case OCHECKNIL:
case OVARKILL:
break;
case OBLOCK:
walkstmtlist(n->list);
break;
case OXCASE:
yyerror("case statement out of place");
n->op = OCASE;
case OCASE:
walkstmt(&n->right);
break;
case ODEFER:
hasdefer = 1;
switch(n->left->op) {
case OPRINT:
case OPRINTN:
walkexprlist(n->left->list, &n->ninit);
n->left = walkprint(n->left, &n->ninit, 1);
break;
case OCOPY:
n->left = copyany(n->left, &n->ninit, 1);
break;
default:
walkexpr(&n->left, &n->ninit);
break;
}
break;
case OFOR:
if(n->ntest != N) {
walkstmtlist(n->ntest->ninit);
init = n->ntest->ninit;
n->ntest->ninit = nil;
walkexpr(&n->ntest, &init);
addinit(&n->ntest, init);
}
walkstmt(&n->nincr);
walkstmtlist(n->nbody);
break;
case OIF:
walkexpr(&n->ntest, &n->ninit);
walkstmtlist(n->nbody);
walkstmtlist(n->nelse);
break;
case OPROC:
switch(n->left->op) {
case OPRINT:
case OPRINTN:
walkexprlist(n->left->list, &n->ninit);
n->left = walkprint(n->left, &n->ninit, 1);
break;
case OCOPY:
n->left = copyany(n->left, &n->ninit, 1);
break;
default:
walkexpr(&n->left, &n->ninit);
break;
}
break;
case ORETURN:
walkexprlist(n->list, &n->ninit);
if(n->list == nil)
break;
if((curfn->type->outnamed && count(n->list) > 1) || paramoutheap(curfn)) {
// assign to the function out parameters,
// so that reorder3 can fix up conflicts
rl = nil;
for(ll=curfn->dcl; ll != nil; ll=ll->next) {
cl = ll->n->class & ~PHEAP;
if(cl == PAUTO)
break;
if(cl == PPARAMOUT)
rl = list(rl, ll->n);
}
if(samelist(rl, n->list)) {
// special return in disguise
n->list = nil;
break;
}
if(count(n->list) == 1 && count(rl) > 1) {
// OAS2FUNC in disguise
f = n->list->n;
if(f->op != OCALLFUNC && f->op != OCALLMETH && f->op != OCALLINTER)
fatal("expected return of call, have %N", f);
n->list = concat(list1(f), ascompatet(n->op, rl, &f->type, 0, &n->ninit));
break;
}
// move function calls out, to make reorder3's job easier.
walkexprlistsafe(n->list, &n->ninit);
ll = ascompatee(n->op, rl, n->list, &n->ninit);
n->list = reorder3(ll);
break;
}
ll = ascompatte(n->op, nil, 0, getoutarg(curfn->type), n->list, 1, &n->ninit);
n->list = ll;
break;
case ORETJMP:
break;
case OSELECT:
walkselect(n);
break;
case OSWITCH:
walkswitch(n);
break;
case ORANGE:
walkrange(n);
break;
case OXFALL:
yyerror("fallthrough statement out of place");
n->op = OFALL;
break;
}
if(n->op == ONAME)
fatal("walkstmt ended up with name: %+N", n);
*np = n;
}
/*
* walk the whole tree of the body of an
* expression or simple statement.
* the types expressions are calculated.
* compile-time constants are evaluated.
* complex side effects like statements are appended to init
*/
void
walkexprlist(NodeList *l, NodeList **init)
{
for(; l; l=l->next)
walkexpr(&l->n, init);
}
void
walkexprlistsafe(NodeList *l, NodeList **init)
{
for(; l; l=l->next) {
l->n = safeexpr(l->n, init);
walkexpr(&l->n, init);
}
}
void
walkexpr(Node **np, NodeList **init)
{
Node *r, *l, *var, *a;
Node *map, *key;
NodeList *ll, *lr;
Type *t;
int et, old_safemode;
int64 v;
int32 lno;
Node *n, *fn, *n1, *n2;
Sym *sym;
char buf[100], *p;
n = *np;
if(n == N)
return;
if(init == &n->ninit) {
// not okay to use n->ninit when walking n,
// because we might replace n with some other node
// and would lose the init list.
fatal("walkexpr init == &n->ninit");
}
if(n->ninit != nil) {
walkstmtlist(n->ninit);
*init = concat(*init, n->ninit);
n->ninit = nil;
}
// annoying case - not typechecked
if(n->op == OKEY) {
walkexpr(&n->left, init);
walkexpr(&n->right, init);
return;
}
lno = setlineno(n);
if(debug['w'] > 1)
dump("walk-before", n);
if(n->typecheck != 1)
fatal("missed typecheck: %+N\n", n);
switch(n->op) {
default:
dump("walk", n);
fatal("walkexpr: switch 1 unknown op %+hN", n);
break;
case OTYPE:
case ONONAME:
case OINDREG:
case OEMPTY:
goto ret;
case ONOT:
case OMINUS:
case OPLUS:
case OCOM:
case OREAL:
case OIMAG:
case ODOTMETH:
case ODOTINTER:
walkexpr(&n->left, init);
goto ret;
case OIND:
walkexpr(&n->left, init);
goto ret;
case ODOT:
usefield(n);
walkexpr(&n->left, init);
goto ret;
case ODOTPTR:
usefield(n);
if(n->op == ODOTPTR && n->left->type->type->width == 0) {
// No actual copy will be generated, so emit an explicit nil check.
n->left = cheapexpr(n->left, init);
checknil(n->left, init);
}
walkexpr(&n->left, init);
goto ret;
case OEFACE:
walkexpr(&n->left, init);
walkexpr(&n->right, init);
goto ret;
case OSPTR:
case OITAB:
walkexpr(&n->left, init);
goto ret;
case OLEN:
case OCAP:
walkexpr(&n->left, init);
// replace len(*[10]int) with 10.
// delayed until now to preserve side effects.
t = n->left->type;
if(isptr[t->etype])
t = t->type;
if(isfixedarray(t)) {
safeexpr(n->left, init);
nodconst(n, n->type, t->bound);
n->typecheck = 1;
}
goto ret;
case OLSH:
case ORSH:
walkexpr(&n->left, init);
walkexpr(&n->right, init);
t = n->left->type;
n->bounded = bounded(n->right, 8*t->width);
if(debug['m'] && n->etype && !isconst(n->right, CTINT))
warn("shift bounds check elided");
goto ret;
case OAND:
case OSUB:
case OHMUL:
case OLT:
case OLE:
case OGE:
case OGT:
case OADD:
case OCOMPLEX:
case OLROT:
// Use results from call expression as arguments for complex.
if(n->op == OCOMPLEX && n->left == N && n->right == N) {
n->left = n->list->n;
n->right = n->list->next->n;
}
walkexpr(&n->left, init);
walkexpr(&n->right, init);
goto ret;
case OOR:
case OXOR:
walkexpr(&n->left, init);
walkexpr(&n->right, init);
walkrotate(&n);
goto ret;
case OEQ:
case ONE:
walkexpr(&n->left, init);
walkexpr(&n->right, init);
// Disable safemode while compiling this code: the code we
// generate internally can refer to unsafe.Pointer.
// In this case it can happen if we need to generate an ==
// for a struct containing a reflect.Value, which itself has
// an unexported field of type unsafe.Pointer.
old_safemode = safemode;
safemode = 0;
walkcompare(&n, init);
safemode = old_safemode;
goto ret;
case OANDAND:
case OOROR:
walkexpr(&n->left, init);
// cannot put side effects from n->right on init,
// because they cannot run before n->left is checked.
// save elsewhere and store on the eventual n->right.
ll = nil;
walkexpr(&n->right, &ll);
addinit(&n->right, ll);
goto ret;
case OPRINT:
case OPRINTN:
walkexprlist(n->list, init);
n = walkprint(n, init, 0);
goto ret;
case OPANIC:
n = mkcall("panic", T, init, n->left);
goto ret;
case ORECOVER:
n = mkcall("recover", n->type, init, nod(OADDR, nodfp, N));
goto ret;
case OLITERAL:
n->addable = 1;
goto ret;
case OCLOSUREVAR:
case OCFUNC:
n->addable = 1;
goto ret;
case ONAME:
if(!(n->class & PHEAP) && n->class != PPARAMREF)
n->addable = 1;
goto ret;
case OCALLINTER:
t = n->left->type;
if(n->list && n->list->n->op == OAS)
goto ret;
walkexpr(&n->left, init);
walkexprlist(n->list, init);
ll = ascompatte(n->op, n, n->isddd, getinarg(t), n->list, 0, init);
n->list = reorder1(ll);
goto ret;
case OCALLFUNC:
t = n->left->type;
if(n->list && n->list->n->op == OAS)
goto ret;
walkexpr(&n->left, init);
walkexprlist(n->list, init);
ll = ascompatte(n->op, n, n->isddd, getinarg(t), n->list, 0, init);
n->list = reorder1(ll);
goto ret;
case OCALLMETH:
t = n->left->type;
if(n->list && n->list->n->op == OAS)
goto ret;
walkexpr(&n->left, init);
walkexprlist(n->list, init);
ll = ascompatte(n->op, n, 0, getthis(t), list1(n->left->left), 0, init);
lr = ascompatte(n->op, n, n->isddd, getinarg(t), n->list, 0, init);
ll = concat(ll, lr);
n->left->left = N;
ullmancalc(n->left);
n->list = reorder1(ll);
goto ret;
case OAS:
*init = concat(*init, n->ninit);
n->ninit = nil;
walkexpr(&n->left, init);
n->left = safeexpr(n->left, init);
if(oaslit(n, init))
goto ret;
if(n->right == N)
goto ret;
switch(n->right->op) {
default:
walkexpr(&n->right, init);
break;
case ORECV:
// x = <-c; n->left is x, n->right->left is c.
// orderstmt made sure x is addressable.
walkexpr(&n->right->left, init);
n1 = nod(OADDR, n->left, N);
r = n->right->left; // the channel
n = mkcall1(chanfn("chanrecv1", 2, r->type), T, init, typename(r->type), r, n1);
walkexpr(&n, init);
goto ret;
}
if(n->left != N && n->right != N) {
r = convas(nod(OAS, n->left, n->right), init);
r->dodata = n->dodata;
n = r;
}
goto ret;
case OAS2:
*init = concat(*init, n->ninit);
n->ninit = nil;
walkexprlistsafe(n->list, init);
walkexprlistsafe(n->rlist, init);
ll = ascompatee(OAS, n->list, n->rlist, init);
ll = reorder3(ll);
n = liststmt(ll);
goto ret;
case OAS2FUNC:
// a,b,... = fn()
*init = concat(*init, n->ninit);
n->ninit = nil;
r = n->rlist->n;
walkexprlistsafe(n->list, init);
walkexpr(&r, init);
ll = ascompatet(n->op, n->list, &r->type, 0, init);
n = liststmt(concat(list1(r), ll));
goto ret;
case OAS2RECV:
// x, y = <-c
// orderstmt made sure x is addressable.
*init = concat(*init, n->ninit);
n->ninit = nil;
r = n->rlist->n;
walkexprlistsafe(n->list, init);
walkexpr(&r->left, init);
if(isblank(n->list->n))
n1 = nodnil();
else
n1 = nod(OADDR, n->list->n, N);
n1->etype = 1; // addr does not escape
fn = chanfn("chanrecv2", 2, r->left->type);
r = mkcall1(fn, types[TBOOL], init, typename(r->left->type), r->left, n1);
n = nod(OAS, n->list->next->n, r);
typecheck(&n, Etop);
goto ret;
case OAS2MAPR:
// a,b = m[i];
*init = concat(*init, n->ninit);
n->ninit = nil;
r = n->rlist->n;
walkexprlistsafe(n->list, init);
walkexpr(&r->left, init);
walkexpr(&r->right, init);
t = r->left->type;
p = nil;
if(t->type->width <= 128) { // Check ../../pkg/runtime/hashmap.c:MAXVALUESIZE before changing.
switch(simsimtype(t->down)) {
case TINT32:
case TUINT32:
p = "mapaccess2_fast32";
break;
case TINT64:
case TUINT64:
p = "mapaccess2_fast64";
break;
case TSTRING:
p = "mapaccess2_faststr";
break;
}
}
if(p != nil) {
// fast versions take key by value
key = r->right;
} else {
// standard version takes key by reference
// orderexpr made sure key is addressable.
key = nod(OADDR, r->right, N);
p = "mapaccess2";
}
// from:
// a,b = m[i]
// to:
// var,b = mapaccess2*(t, m, i)
// a = *var
a = n->list->n;
var = temp(ptrto(t->type));
var->typecheck = 1;
fn = mapfn(p, t);
r = mkcall1(fn, getoutargx(fn->type), init, typename(t), r->left, key);
n->rlist = list1(r);
n->op = OAS2FUNC;
n->list->n = var;
walkexpr(&n, init);
*init = list(*init, n);
n = nod(OAS, a, nod(OIND, var, N));
typecheck(&n, Etop);
walkexpr(&n, init);
// mapaccess needs a zero value to be at least this big.
if(zerosize < t->type->width)
zerosize = t->type->width;
// TODO: ptr is always non-nil, so disable nil check for this OIND op.
goto ret;
case ODELETE:
*init = concat(*init, n->ninit);
n->ninit = nil;
map = n->list->n;
key = n->list->next->n;
walkexpr(&map, init);
walkexpr(&key, init);
// orderstmt made sure key is addressable.
key = nod(OADDR, key, N);
t = map->type;
n = mkcall1(mapfndel("mapdelete", t), T, init, typename(t), map, key);
goto ret;
case OAS2DOTTYPE:
// a,b = i.(T)
*init = concat(*init, n->ninit);
n->ninit = nil;
r = n->rlist->n;
walkexprlistsafe(n->list, init);
if(isblank(n->list->n) && !isinter(r->type)) {
strcpy(buf, "assert");
p = buf+strlen(buf);
if(isnilinter(r->left->type))
*p++ = 'E';
else
*p++ = 'I';
*p++ = '2';
*p++ = 'T';
*p++ = 'O';
*p++ = 'K';
*p = '\0';
fn = syslook(buf, 1);
ll = list1(typename(r->type));
ll = list(ll, r->left);
argtype(fn, r->left->type);
n1 = nod(OCALL, fn, N);
n1->list = ll;
n = nod(OAS, n->list->next->n, n1);
typecheck(&n, Etop);
walkexpr(&n, init);
goto ret;
}
r->op = ODOTTYPE2;
walkexpr(&r, init);
ll = ascompatet(n->op, n->list, &r->type, 0, init);
n = liststmt(concat(list1(r), ll));
goto ret;
case ODOTTYPE:
case ODOTTYPE2:
// Build name of function: assertI2E2 etc.
strcpy(buf, "assert");
p = buf+strlen(buf);
if(isnilinter(n->left->type))
*p++ = 'E';
else
*p++ = 'I';
*p++ = '2';
if(isnilinter(n->type))
*p++ = 'E';
else if(isinter(n->type))
*p++ = 'I';
else
*p++ = 'T';
if(n->op == ODOTTYPE2)
*p++ = '2';
*p = '\0';
fn = syslook(buf, 1);
ll = list1(typename(n->type));
ll = list(ll, n->left);
argtype(fn, n->left->type);
argtype(fn, n->type);
n = nod(OCALL, fn, N);
n->list = ll;
typecheck(&n, Erv | Efnstruct);
walkexpr(&n, init);
goto ret;
case OCONVIFACE:
walkexpr(&n->left, init);
// Optimize convT2E as a two-word copy when T is uintptr-shaped.
if(!isinter(n->left->type) && isnilinter(n->type) &&
(n->left->type->width == widthptr) &&
isint[simsimtype(n->left->type)]) {
l = nod(OEFACE, typename(n->left->type), n->left);
l->type = n->type;
l->typecheck = n->typecheck;
n = l;
goto ret;
}
// Build name of function: convI2E etc.
// Not all names are possible
// (e.g., we'll never generate convE2E or convE2I).
strcpy(buf, "conv");
p = buf+strlen(buf);
if(isnilinter(n->left->type))
*p++ = 'E';
else if(isinter(n->left->type))
*p++ = 'I';
else
*p++ = 'T';
*p++ = '2';
if(isnilinter(n->type))
*p++ = 'E';
else
*p++ = 'I';
*p = '\0';
fn = syslook(buf, 1);
ll = nil;
if(!isinter(n->left->type))
ll = list(ll, typename(n->left->type));
if(!isnilinter(n->type))
ll = list(ll, typename(n->type));
if(!isinter(n->left->type) && !isnilinter(n->type)){
sym = pkglookup(smprint("%-T.%-T", n->left->type, n->type), itabpkg);
if(sym->def == N) {
l = nod(ONAME, N, N);
l->sym = sym;
l->type = ptrto(types[TUINT8]);
l->addable = 1;
l->class = PEXTERN;
l->xoffset = 0;
sym->def = l;
ggloblsym(sym, widthptr, 1, 0);
}
l = nod(OADDR, sym->def, N);
l->addable = 1;
ll = list(ll, l);
if(n->left->type->width == widthptr &&
isint[simsimtype(n->left->type)]) {
/* For pointer types, we can make a special form of optimization
*
* These statements are put onto the expression init list:
* Itab *tab = atomicloadtype(&cache);
* if(tab == nil)
* tab = typ2Itab(type, itype, &cache);
*
* The CONVIFACE expression is replaced with this:
* OEFACE{tab, ptr};
*/
l = temp(ptrto(types[TUINT8]));
n1 = nod(OAS, l, sym->def);
typecheck(&n1, Etop);
*init = list(*init, n1);
fn = syslook("typ2Itab", 1);
n1 = nod(OCALL, fn, N);
n1->list = ll;
typecheck(&n1, Erv);
walkexpr(&n1, init);
n2 = nod(OIF, N, N);
n2->ntest = nod(OEQ, l, nodnil());
n2->nbody = list1(nod(OAS, l, n1));
n2->likely = -1;
typecheck(&n2, Etop);
*init = list(*init, n2);
l = nod(OEFACE, l, n->left);
l->typecheck = n->typecheck;
l->type = n->type;
n = l;
goto ret;
}
}
if(isinter(n->left->type)) {
ll = list(ll, n->left);
} else {
// regular types are passed by reference to avoid C vararg calls
// orderexpr arranged for n->left to be a temporary for all
// the conversions it could see. comparison of an interface
// with a non-interface, especially in a switch on interface value
// with non-interface cases, is not visible to orderstmt, so we
// have to fall back on allocating a temp here.
if(islvalue(n->left))
ll = list(ll, nod(OADDR, n->left, N));
else
ll = list(ll, nod(OADDR, copyexpr(n->left, n->left->type, init), N));
}
argtype(fn, n->left->type);
argtype(fn, n->type);
dowidth(fn->type);
n = nod(OCALL, fn, N);
n->list = ll;
typecheck(&n, Erv);
walkexpr(&n, init);
goto ret;
case OCONV:
case OCONVNOP:
if(thechar == '5') {
if(isfloat[n->left->type->etype]) {
if(n->type->etype == TINT64) {
n = mkcall("float64toint64", n->type, init, conv(n->left, types[TFLOAT64]));
goto ret;
}
if(n->type->etype == TUINT64) {
n = mkcall("float64touint64", n->type, init, conv(n->left, types[TFLOAT64]));
goto ret;
}
}
if(isfloat[n->type->etype]) {
if(n->left->type->etype == TINT64) {
n = mkcall("int64tofloat64", n->type, init, conv(n->left, types[TINT64]));
goto ret;
}
if(n->left->type->etype == TUINT64) {
n = mkcall("uint64tofloat64", n->type, init, conv(n->left, types[TUINT64]));
goto ret;
}
}
}
walkexpr(&n->left, init);
goto ret;
case OANDNOT:
walkexpr(&n->left, init);
n->op = OAND;
n->right = nod(OCOM, n->right, N);
typecheck(&n->right, Erv);
walkexpr(&n->right, init);
goto ret;
case OMUL:
walkexpr(&n->left, init);
walkexpr(&n->right, init);
walkmul(&n, init);
goto ret;
case ODIV:
case OMOD:
walkexpr(&n->left, init);
walkexpr(&n->right, init);
/*
* rewrite complex div into function call.
*/
et = n->left->type->etype;
if(iscomplex[et] && n->op == ODIV) {
t = n->type;
n = mkcall("complex128div", types[TCOMPLEX128], init,
conv(n->left, types[TCOMPLEX128]),
conv(n->right, types[TCOMPLEX128]));
n = conv(n, t);
goto ret;
}
// Nothing to do for float divisions.
if(isfloat[et])
goto ret;
// Try rewriting as shifts or magic multiplies.
walkdiv(&n, init);
/*
* rewrite 64-bit div and mod into function calls
* on 32-bit architectures.
*/
switch(n->op) {
case OMOD:
case ODIV:
if(widthreg >= 8 || (et != TUINT64 && et != TINT64))
goto ret;
if(et == TINT64)
strcpy(namebuf, "int64");
else
strcpy(namebuf, "uint64");
if(n->op == ODIV)
strcat(namebuf, "div");
else
strcat(namebuf, "mod");
n = mkcall(namebuf, n->type, init,
conv(n->left, types[et]), conv(n->right, types[et]));
break;
default:
break;
}
goto ret;
case OINDEX:
walkexpr(&n->left, init);
// save the original node for bounds checking elision.
// If it was a ODIV/OMOD walk might rewrite it.
r = n->right;
walkexpr(&n->right, init);
// if range of type cannot exceed static array bound,
// disable bounds check.
if(n->bounded)
goto ret;
t = n->left->type;
if(t != T && isptr[t->etype])
t = t->type;
if(isfixedarray(t)) {
n->bounded = bounded(r, t->bound);
if(debug['m'] && n->bounded && !isconst(n->right, CTINT))
warn("index bounds check elided");
if(smallintconst(n->right) && !n->bounded)
yyerror("index out of bounds");
} else if(isconst(n->left, CTSTR)) {
n->bounded = bounded(r, n->left->val.u.sval->len);
if(debug['m'] && n->bounded && !isconst(n->right, CTINT))
warn("index bounds check elided");
if(smallintconst(n->right)) {
if(!n->bounded)
yyerror("index out of bounds");
else {
// replace "abc"[1] with 'b'.
// delayed until now because "abc"[1] is not
// an ideal constant.
v = mpgetfix(n->right->val.u.xval);
nodconst(n, n->type, n->left->val.u.sval->s[v]);
n->typecheck = 1;
}
}
}
if(isconst(n->right, CTINT))
if(mpcmpfixfix(n->right->val.u.xval, &mpzero) < 0 ||
mpcmpfixfix(n->right->val.u.xval, maxintval[TINT]) > 0)
yyerror("index out of bounds");
goto ret;
case OINDEXMAP:
if(n->etype == 1)
goto ret;
walkexpr(&n->left, init);
walkexpr(&n->right, init);
t = n->left->type;
p = nil;
if(t->type->width <= 128) { // Check ../../pkg/runtime/hashmap.c:MAXVALUESIZE before changing.
switch(simsimtype(t->down)) {
case TINT32:
case TUINT32:
p = "mapaccess1_fast32";
break;
case TINT64:
case TUINT64:
p = "mapaccess1_fast64";
break;
case TSTRING:
p = "mapaccess1_faststr";
break;
}
}
if(p != nil) {
// fast versions take key by value
key = n->right;
} else {
// standard version takes key by reference.
// orderexpr made sure key is addressable.
key = nod(OADDR, n->right, N);
p = "mapaccess1";
}
n = mkcall1(mapfn(p, t), ptrto(t->type), init, typename(t), n->left, key);
n = nod(OIND, n, N);
n->type = t->type;
n->typecheck = 1;
// mapaccess needs a zero value to be at least this big.
if(zerosize < t->type->width)
zerosize = t->type->width;
goto ret;
case ORECV:
fatal("walkexpr ORECV"); // should see inside OAS only
case OSLICE:
if(n->right != N && n->right->left == N && n->right->right == N) { // noop
walkexpr(&n->left, init);
n = n->left;
goto ret;
}
// fallthrough
case OSLICEARR:
case OSLICESTR:
if(n->right == N) // already processed
goto ret;
walkexpr(&n->left, init);
// cgen_slice can't handle string literals as source
// TODO the OINDEX case is a bug elsewhere that needs to be traced. it causes a crash on ([2][]int{ ... })[1][lo:hi]
if((n->op == OSLICESTR && n->left->op == OLITERAL) || (n->left->op == OINDEX))
n->left = copyexpr(n->left, n->left->type, init);
else
n->left = safeexpr(n->left, init);
walkexpr(&n->right->left, init);
n->right->left = safeexpr(n->right->left, init);
walkexpr(&n->right->right, init);
n->right->right = safeexpr(n->right->right, init);
n = sliceany(n, init); // chops n->right, sets n->list
goto ret;
case OSLICE3:
case OSLICE3ARR:
if(n->right == N) // already processed
goto ret;
walkexpr(&n->left, init);
// TODO the OINDEX case is a bug elsewhere that needs to be traced. it causes a crash on ([2][]int{ ... })[1][lo:hi]
// TODO the comment on the previous line was copied from case OSLICE. it might not even be true.
if(n->left->op == OINDEX)
n->left = copyexpr(n->left, n->left->type, init);
else
n->left = safeexpr(n->left, init);
walkexpr(&n->right->left, init);
n->right->left = safeexpr(n->right->left, init);
walkexpr(&n->right->right->left, init);
n->right->right->left = safeexpr(n->right->right->left, init);
walkexpr(&n->right->right->right, init);
n->right->right->right = safeexpr(n->right->right->right, init);
n = sliceany(n, init); // chops n->right, sets n->list
goto ret;
case OADDR:
walkexpr(&n->left, init);
goto ret;
case ONEW:
if(n->esc == EscNone && n->type->type->width < (1<<16)) {
r = temp(n->type->type);
r = nod(OAS, r, N); // zero temp
typecheck(&r, Etop);
*init = list(*init, r);
r = nod(OADDR, r->left, N);
typecheck(&r, Erv);
n = r;
} else {
n = callnew(n->type->type);
}
goto ret;
case OCMPSTR:
// If one argument to the comparison is an empty string,
// comparing the lengths instead will yield the same result
// without the function call.
if((isconst(n->left, CTSTR) && n->left->val.u.sval->len == 0) ||
(isconst(n->right, CTSTR) && n->right->val.u.sval->len == 0)) {
r = nod(n->etype, nod(OLEN, n->left, N), nod(OLEN, n->right, N));
typecheck(&r, Erv);
walkexpr(&r, init);
r->type = n->type;
n = r;
goto ret;
}
// s + "badgerbadgerbadger" == "badgerbadgerbadger"
if((n->etype == OEQ || n->etype == ONE) &&
isconst(n->right, CTSTR) &&
n->left->op == OADDSTR && count(n->left->list) == 2 &&
isconst(n->left->list->next->n, CTSTR) &&
cmpslit(n->right, n->left->list->next->n) == 0) {
r = nod(n->etype, nod(OLEN, n->left->list->n, N), nodintconst(0));
typecheck(&r, Erv);
walkexpr(&r, init);
r->type = n->type;
n = r;
goto ret;
}
if(n->etype == OEQ || n->etype == ONE) {
// prepare for rewrite below
n->left = cheapexpr(n->left, init);
n->right = cheapexpr(n->right, init);
r = mkcall("eqstring", types[TBOOL], init,
conv(n->left, types[TSTRING]),
conv(n->right, types[TSTRING]));
// quick check of len before full compare for == or !=
if(n->etype == OEQ) {
// len(left) == len(right) && eqstring(left, right)
r = nod(OANDAND, nod(OEQ, nod(OLEN, n->left, N), nod(OLEN, n->right, N)), r);
} else {
// len(left) != len(right) || !eqstring(left, right)
r = nod(ONOT, r, N);
r = nod(OOROR, nod(ONE, nod(OLEN, n->left, N), nod(OLEN, n->right, N)), r);
}
typecheck(&r, Erv);
walkexpr(&r, nil);
} else {
// sys_cmpstring(s1, s2) :: 0
r = mkcall("cmpstring", types[TINT], init,
conv(n->left, types[TSTRING]),
conv(n->right, types[TSTRING]));
r = nod(n->etype, r, nodintconst(0));
}
typecheck(&r, Erv);
if(n->type->etype != TBOOL) fatal("cmp %T", n->type);
r->type = n->type;
n = r;
goto ret;
case OADDSTR:
n = addstr(n, init);
goto ret;
case OAPPEND:
if(n->isddd)
n = appendslice(n, init); // also works for append(slice, string).
else
n = append(n, init);
goto ret;
case OCOPY:
n = copyany(n, init, flag_race);
goto ret;
case OCLOSE:
// cannot use chanfn - closechan takes any, not chan any
fn = syslook("closechan", 1);
argtype(fn, n->left->type);
n = mkcall1(fn, T, init, n->left);
goto ret;
case OMAKECHAN:
n = mkcall1(chanfn("makechan", 1, n->type), n->type, init,
typename(n->type),
conv(n->left, types[TINT64]));
goto ret;
case OMAKEMAP:
t = n->type;
fn = syslook("makemap", 1);
argtype(fn, t->down); // any-1
argtype(fn, t->type); // any-2
n = mkcall1(fn, n->type, init,
typename(n->type),
conv(n->left, types[TINT64]));
goto ret;
case OMAKESLICE:
l = n->left;
r = n->right;
if(r == nil)
l = r = safeexpr(l, init);
t = n->type;
if(n->esc == EscNone
&& smallintconst(l) && smallintconst(r)
&& (t->type->width == 0 || mpgetfix(r->val.u.xval) < (1ULL<<16) / t->type->width)) {
// var arr [r]T
// n = arr[:l]
t = aindex(r, t->type); // [r]T
var = temp(t);
a = nod(OAS, var, N); // zero temp
typecheck(&a, Etop);
*init = list(*init, a);
r = nod(OSLICE, var, nod(OKEY, N, l)); // arr[:l]
r = conv(r, n->type); // in case n->type is named.
typecheck(&r, Erv);
walkexpr(&r, init);
n = r;
} else {
// makeslice(t *Type, nel int64, max int64) (ary []any)
fn = syslook("makeslice", 1);
argtype(fn, t->type); // any-1
n = mkcall1(fn, n->type, init,
typename(n->type),
conv(l, types[TINT64]),
conv(r, types[TINT64]));
}
goto ret;
case ORUNESTR:
// sys_intstring(v)
n = mkcall("intstring", n->type, init,
conv(n->left, types[TINT64]));
goto ret;
case OARRAYBYTESTR:
// slicebytetostring([]byte) string;
n = mkcall("slicebytetostring", n->type, init, n->left);
goto ret;
case OARRAYBYTESTRTMP:
// slicebytetostringtmp([]byte) string;
n = mkcall("slicebytetostringtmp", n->type, init, n->left);
goto ret;
case OARRAYRUNESTR:
// slicerunetostring([]rune) string;
n = mkcall("slicerunetostring", n->type, init, n->left);
goto ret;
case OSTRARRAYBYTE:
// stringtoslicebyte(string) []byte;
n = mkcall("stringtoslicebyte", n->type, init, conv(n->left, types[TSTRING]));
goto ret;
case OSTRARRAYRUNE:
// stringtoslicerune(string) []rune
n = mkcall("stringtoslicerune", n->type, init, n->left);
goto ret;
case OCMPIFACE:
// ifaceeq(i1 any-1, i2 any-2) (ret bool);
if(!eqtype(n->left->type, n->right->type))
fatal("ifaceeq %O %T %T", n->op, n->left->type, n->right->type);
if(isnilinter(n->left->type))
fn = syslook("efaceeq", 1);
else
fn = syslook("ifaceeq", 1);
n->right = cheapexpr(n->right, init);
n->left = cheapexpr(n->left, init);
argtype(fn, n->right->type);
argtype(fn, n->left->type);
r = mkcall1(fn, n->type, init, n->left, n->right);
if(n->etype == ONE)
r = nod(ONOT, r, N);
// check itable/type before full compare.
if(n->etype == OEQ)
r = nod(OANDAND, nod(OEQ, nod(OITAB, n->left, N), nod(OITAB, n->right, N)), r);
else
r = nod(OOROR, nod(ONE, nod(OITAB, n->left, N), nod(OITAB, n->right, N)), r);
typecheck(&r, Erv);
walkexpr(&r, init);
r->type = n->type;
n = r;
goto ret;
case OARRAYLIT:
case OMAPLIT:
case OSTRUCTLIT:
case OPTRLIT:
// XXX TODO do we need to clear var?
var = temp(n->type);
anylit(0, n, var, init);
n = var;
goto ret;
case OSEND:
n1 = n->right;
n1 = assignconv(n1, n->left->type->type, "chan send");
walkexpr(&n1, init);
n1 = nod(OADDR, n1, N);
n = mkcall1(chanfn("chansend1", 2, n->left->type), T, init, typename(n->left->type), n->left, n1);
goto ret;
case OCLOSURE:
n = walkclosure(n, init);
goto ret;
case OCALLPART:
n = walkpartialcall(n, init);
goto ret;
}
fatal("missing switch %O", n->op);
ret:
// Expressions that are constant at run time but not
// considered const by the language spec are not turned into
// constants until walk. For example, if n is y%1 == 0, the
// walk of y%1 may have replaced it by 0.
// Check whether n with its updated args is itself now a constant.
t = n->type;
evconst(n);
n->type = t;
if(n->op == OLITERAL)
typecheck(&n, Erv);
ullmancalc(n);
if(debug['w'] && n != N)
dump("walk", n);
lineno = lno;
*np = n;
}
static Node*
ascompatee1(int op, Node *l, Node *r, NodeList **init)
{
Node *n;
USED(op);
// convas will turn map assigns into function calls,
// making it impossible for reorder3 to work.
n = nod(OAS, l, r);
if(l->op == OINDEXMAP)
return n;
return convas(n, init);
}
static NodeList*
ascompatee(int op, NodeList *nl, NodeList *nr, NodeList **init)
{
NodeList *ll, *lr, *nn;
/*
* check assign expression list to
* a expression list. called in
* expr-list = expr-list
*/
// ensure order of evaluation for function calls
for(ll=nl; ll; ll=ll->next)
ll->n = safeexpr(ll->n, init);
for(lr=nr; lr; lr=lr->next)
lr->n = safeexpr(lr->n, init);
nn = nil;
for(ll=nl, lr=nr; ll && lr; ll=ll->next, lr=lr->next) {
// Do not generate 'x = x' during return. See issue 4014.
if(op == ORETURN && ll->n == lr->n)
continue;
nn = list(nn, ascompatee1(op, ll->n, lr->n, init));
}
// cannot happen: caller checked that lists had same length
if(ll || lr)
yyerror("error in shape across %+H %O %+H / %d %d [%s]", nl, op, nr, count(nl), count(nr), curfn->nname->sym->name);
return nn;
}
/*
* l is an lv and rt is the type of an rv
* return 1 if this implies a function call
* evaluating the lv or a function call
* in the conversion of the types
*/
static int
fncall(Node *l, Type *rt)
{
if(l->ullman >= UINF || l->op == OINDEXMAP)
return 1;
if(eqtype(l->type, rt))
return 0;
return 1;
}
static NodeList*
ascompatet(int op, NodeList *nl, Type **nr, int fp, NodeList **init)
{
Node *l, *tmp, *a;
NodeList *ll;
Type *r;
Iter saver;
int ucount;
NodeList *nn, *mm;
USED(op);
/*
* check assign type list to
* a expression list. called in
* expr-list = func()
*/
r = structfirst(&saver, nr);
nn = nil;
mm = nil;
ucount = 0;
for(ll=nl; ll; ll=ll->next) {
if(r == T)
break;
l = ll->n;
if(isblank(l)) {
r = structnext(&saver);
continue;
}
// any lv that causes a fn call must be
// deferred until all the return arguments
// have been pulled from the output arguments
if(fncall(l, r->type)) {
tmp = temp(r->type);
typecheck(&tmp, Erv);
a = nod(OAS, l, tmp);
a = convas(a, init);
mm = list(mm, a);
l = tmp;
}
a = nod(OAS, l, nodarg(r, fp));
a = convas(a, init);
ullmancalc(a);
if(a->ullman >= UINF)
ucount++;
nn = list(nn, a);
r = structnext(&saver);
}
if(ll != nil || r != T)
yyerror("ascompatet: assignment count mismatch: %d = %d",
count(nl), structcount(*nr));
if(ucount)
fatal("ascompatet: too many function calls evaluating parameters");
return concat(nn, mm);
}
/*
* package all the arguments that match a ... T parameter into a []T.
*/
static NodeList*
mkdotargslice(NodeList *lr0, NodeList *nn, Type *l, int fp, NodeList **init, Node *ddd)
{
Node *a, *n;
Type *tslice;
int esc;
esc = EscUnknown;
if(ddd != nil)
esc = ddd->esc;
tslice = typ(TARRAY);
tslice->type = l->type->type;
tslice->bound = -1;
if(count(lr0) == 0) {
n = nodnil();
n->type = tslice;
} else {
n = nod(OCOMPLIT, N, typenod(tslice));
if(ddd != nil)
n->alloc = ddd->alloc; // temporary to use
n->list = lr0;
n->esc = esc;
typecheck(&n, Erv);
if(n->type == T)
fatal("mkdotargslice: typecheck failed");
walkexpr(&n, init);
}
a = nod(OAS, nodarg(l, fp), n);
nn = list(nn, convas(a, init));
return nn;
}
/*
* helpers for shape errors
*/
static char*
dumptypes(Type **nl, char *what)
{
int first;
Type *l;
Iter savel;
Fmt fmt;
fmtstrinit(&fmt);
fmtprint(&fmt, "\t");
first = 1;
for(l = structfirst(&savel, nl); l != T; l = structnext(&savel)) {
if(first)
first = 0;
else
fmtprint(&fmt, ", ");
fmtprint(&fmt, "%T", l);
}
if(first)
fmtprint(&fmt, "[no arguments %s]", what);
return fmtstrflush(&fmt);
}
static char*
dumpnodetypes(NodeList *l, char *what)
{
int first;
Node *r;
Fmt fmt;
fmtstrinit(&fmt);
fmtprint(&fmt, "\t");
first = 1;
for(; l; l=l->next) {
r = l->n;
if(first)
first = 0;
else
fmtprint(&fmt, ", ");
fmtprint(&fmt, "%T", r->type);
}
if(first)
fmtprint(&fmt, "[no arguments %s]", what);
return fmtstrflush(&fmt);
}
/*
* check assign expression list to
* a type list. called in
* return expr-list
* func(expr-list)
*/
static NodeList*
ascompatte(int op, Node *call, int isddd, Type **nl, NodeList *lr, int fp, NodeList **init)
{
Type *l, *ll;
Node *r, *a;
NodeList *nn, *lr0, *alist;
Iter savel;
char *l1, *l2;
lr0 = lr;
l = structfirst(&savel, nl);
r = N;
if(lr)
r = lr->n;
nn = nil;
// f(g()) where g has multiple return values
if(r != N && lr->next == nil && r->type->etype == TSTRUCT && r->type->funarg) {
// optimization - can do block copy
if(eqtypenoname(r->type, *nl)) {
a = nodarg(*nl, fp);
r = nod(OCONVNOP, r, N);
r->type = a->type;
nn = list1(convas(nod(OAS, a, r), init));
goto ret;
}
// conversions involved.
// copy into temporaries.
alist = nil;
for(l=structfirst(&savel, &r->type); l; l=structnext(&savel)) {
a = temp(l->type);
alist = list(alist, a);
}
a = nod(OAS2, N, N);
a->list = alist;
a->rlist = lr;
typecheck(&a, Etop);
walkstmt(&a);
*init = list(*init, a);
lr = alist;
r = lr->n;
l = structfirst(&savel, nl);
}
loop:
if(l != T && l->isddd) {
// the ddd parameter must be last
ll = structnext(&savel);
if(ll != T)
yyerror("... must be last argument");
// special case --
// only if we are assigning a single ddd
// argument to a ddd parameter then it is
// passed thru unencapsulated
if(r != N && lr->next == nil && isddd && eqtype(l->type, r->type)) {
a = nod(OAS, nodarg(l, fp), r);
a = convas(a, init);
nn = list(nn, a);
goto ret;
}
// normal case -- make a slice of all
// remaining arguments and pass it to
// the ddd parameter.
nn = mkdotargslice(lr, nn, l, fp, init, call->right);
goto ret;
}
if(l == T || r == N) {
if(l != T || r != N) {
l1 = dumptypes(nl, "expected");
l2 = dumpnodetypes(lr0, "given");
if(l != T)
yyerror("not enough arguments to %O\n%s\n%s", op, l1, l2);
else
yyerror("too many arguments to %O\n%s\n%s", op, l1, l2);
}
goto ret;
}
a = nod(OAS, nodarg(l, fp), r);
a = convas(a, init);
nn = list(nn, a);
l = structnext(&savel);
r = N;
lr = lr->next;
if(lr != nil)
r = lr->n;
goto loop;
ret:
for(lr=nn; lr; lr=lr->next)
lr->n->typecheck = 1;
return nn;
}
// generate code for print
static Node*
walkprint(Node *nn, NodeList **init, int defer)
{
Node *r;
Node *n;
NodeList *l, *all;
Node *on;
Type *t;
int notfirst, et, op;
NodeList *calls, *intypes, *args;
Fmt fmt;
on = nil;
op = nn->op;
all = nn->list;
calls = nil;
notfirst = 0;
intypes = nil;
args = nil;
memset(&fmt, 0, sizeof fmt);
if(defer) {
// defer print turns into defer printf with format string
fmtstrinit(&fmt);
intypes = list(intypes, nod(ODCLFIELD, N, typenod(types[TSTRING])));
args = list1(nod(OXXX, N, N));
}
for(l=all; l; l=l->next) {
if(notfirst) {
if(defer)
fmtprint(&fmt, " ");
else
calls = list(calls, mkcall("printsp", T, init));
}
notfirst = op == OPRINTN;
n = l->n;
if(n->op == OLITERAL) {
switch(n->val.ctype) {
case CTRUNE:
defaultlit(&n, runetype);
break;
case CTINT:
defaultlit(&n, types[TINT64]);
break;
case CTFLT:
defaultlit(&n, types[TFLOAT64]);
break;
}
}
if(n->op != OLITERAL && n->type && n->type->etype == TIDEAL)
defaultlit(&n, types[TINT64]);
defaultlit(&n, nil);
l->n = n;
if(n->type == T || n->type->etype == TFORW)
continue;
t = n->type;
et = n->type->etype;
if(isinter(n->type)) {
if(defer) {
if(isnilinter(n->type))
fmtprint(&fmt, "%%e");
else
fmtprint(&fmt, "%%i");
} else {
if(isnilinter(n->type))
on = syslook("printeface", 1);
else
on = syslook("printiface", 1);
argtype(on, n->type); // any-1
}
} else if(isptr[et] || et == TCHAN || et == TMAP || et == TFUNC || et == TUNSAFEPTR) {
if(defer) {
fmtprint(&fmt, "%%p");
} else {
on = syslook("printpointer", 1);
argtype(on, n->type); // any-1
}
} else if(isslice(n->type)) {
if(defer) {
fmtprint(&fmt, "%%a");
} else {
on = syslook("printslice", 1);
argtype(on, n->type); // any-1
}
} else if(isint[et]) {
if(defer) {
if(et == TUINT64)
fmtprint(&fmt, "%%U");
else {
fmtprint(&fmt, "%%D");
t = types[TINT64];
}
} else {
if(et == TUINT64)
on = syslook("printuint", 0);
else
on = syslook("printint", 0);
}
} else if(isfloat[et]) {
if(defer) {
fmtprint(&fmt, "%%f");
t = types[TFLOAT64];
} else
on = syslook("printfloat", 0);
} else if(iscomplex[et]) {
if(defer) {
fmtprint(&fmt, "%%C");
t = types[TCOMPLEX128];
} else
on = syslook("printcomplex", 0);
} else if(et == TBOOL) {
if(defer)
fmtprint(&fmt, "%%t");
else
on = syslook("printbool", 0);
} else if(et == TSTRING) {
if(defer)
fmtprint(&fmt, "%%S");
else
on = syslook("printstring", 0);
} else {
badtype(OPRINT, n->type, T);
continue;
}
if(!defer) {
t = *getinarg(on->type);
if(t != nil)
t = t->type;
if(t != nil)
t = t->type;
}
if(!eqtype(t, n->type)) {
n = nod(OCONV, n, N);
n->type = t;
}
if(defer) {
intypes = list(intypes, nod(ODCLFIELD, N, typenod(t)));
args = list(args, n);
} else {
r = nod(OCALL, on, N);
r->list = list1(n);
calls = list(calls, r);
}
}
if(defer) {
if(op == OPRINTN)
fmtprint(&fmt, "\n");
on = syslook("goprintf", 1);
on->type = functype(nil, intypes, nil);
args->n = nod(OLITERAL, N, N);
args->n->val.ctype = CTSTR;
args->n->val.u.sval = strlit(fmtstrflush(&fmt));
r = nod(OCALL, on, N);
r->list = args;
typecheck(&r, Etop);
walkexpr(&r, init);
} else {
if(op == OPRINTN)
calls = list(calls, mkcall("printnl", T, nil));
typechecklist(calls, Etop);
walkexprlist(calls, init);
r = nod(OEMPTY, N, N);
typecheck(&r, Etop);
walkexpr(&r, init);
r->ninit = calls;
}
return r;
}
Node*
callnew(Type *t)
{
Node *fn;
dowidth(t);
fn = syslook("new", 1);
argtype(fn, t);
return mkcall1(fn, ptrto(t), nil, typename(t));
}
static Node*
convas(Node *n, NodeList **init)
{
Type *lt, *rt;
Node *map, *key, *val;
if(n->op != OAS)
fatal("convas: not OAS %O", n->op);
n->typecheck = 1;
if(n->left == N || n->right == N)
goto out;
lt = n->left->type;
rt = n->right->type;
if(lt == T || rt == T)
goto out;
if(isblank(n->left)) {
defaultlit(&n->right, T);
goto out;
}
if(n->left->op == OINDEXMAP) {
map = n->left->left;
key = n->left->right;
val = n->right;
walkexpr(&map, init);
walkexpr(&key, init);
walkexpr(&val, init);
// orderexpr made sure key and val are addressable.
key = nod(OADDR, key, N);
val = nod(OADDR, val, N);
n = mkcall1(mapfn("mapassign1", map->type), T, init,
typename(map->type), map, key, val);
goto out;
}
if(eqtype(lt, rt))
goto out;
n->right = assignconv(n->right, lt, "assignment");
walkexpr(&n->right, init);
out:
ullmancalc(n);
return n;
}
/*
* from ascompat[te]
* evaluating actual function arguments.
* f(a,b)
* if there is exactly one function expr,
* then it is done first. otherwise must
* make temp variables
*/
static NodeList*
reorder1(NodeList *all)
{
Node *f, *a, *n;
NodeList *l, *r, *g;
int c, d, t;
c = 0; // function calls
t = 0; // total parameters
for(l=all; l; l=l->next) {
n = l->n;
t++;
ullmancalc(n);
if(n->ullman >= UINF)
c++;
}
if(c == 0 || t == 1)
return all;
g = nil; // fncalls assigned to tempnames
f = N; // last fncall assigned to stack
r = nil; // non fncalls and tempnames assigned to stack
d = 0;
for(l=all; l; l=l->next) {
n = l->n;
if(n->ullman < UINF) {
r = list(r, n);
continue;
}
d++;
if(d == c) {
f = n;
continue;
}
// make assignment of fncall to tempname
a = temp(n->right->type);
a = nod(OAS, a, n->right);
g = list(g, a);
// put normal arg assignment on list
// with fncall replaced by tempname
n->right = a->left;
r = list(r, n);
}
if(f != N)
g = list(g, f);
return concat(g, r);
}
static void reorder3save(Node**, NodeList*, NodeList*, NodeList**);
static int aliased(Node*, NodeList*, NodeList*);
/*
* from ascompat[ee]
* a,b = c,d
* simultaneous assignment. there cannot
* be later use of an earlier lvalue.
*
* function calls have been removed.
*/
static NodeList*
reorder3(NodeList *all)
{
NodeList *list, *early, *mapinit;
Node *l;
// If a needed expression may be affected by an
// earlier assignment, make an early copy of that
// expression and use the copy instead.
early = nil;
mapinit = nil;
for(list=all; list; list=list->next) {
l = list->n->left;
// Save subexpressions needed on left side.
// Drill through non-dereferences.
for(;;) {
if(l->op == ODOT || l->op == OPAREN) {
l = l->left;
continue;
}
if(l->op == OINDEX && isfixedarray(l->left->type)) {
reorder3save(&l->right, all, list, &early);
l = l->left;
continue;
}
break;
}
switch(l->op) {
default:
fatal("reorder3 unexpected lvalue %#O", l->op);
case ONAME:
break;
case OINDEX:
case OINDEXMAP:
reorder3save(&l->left, all, list, &early);
reorder3save(&l->right, all, list, &early);
if(l->op == OINDEXMAP)
list->n = convas(list->n, &mapinit);
break;
case OIND:
case ODOTPTR:
reorder3save(&l->left, all, list, &early);
}
// Save expression on right side.
reorder3save(&list->n->right, all, list, &early);
}
early = concat(mapinit, early);
return concat(early, all);
}
static int vmatch2(Node*, Node*);
static int varexpr(Node*);
/*
* if the evaluation of *np would be affected by the
* assignments in all up to but not including stop,
* copy into a temporary during *early and
* replace *np with that temp.
*/
static void
reorder3save(Node **np, NodeList *all, NodeList *stop, NodeList **early)
{
Node *n, *q;
n = *np;
if(!aliased(n, all, stop))
return;
q = temp(n->type);
q = nod(OAS, q, n);
typecheck(&q, Etop);
*early = list(*early, q);
*np = q->left;
}
/*
* what's the outer value that a write to n affects?
* outer value means containing struct or array.
*/
Node*
outervalue(Node *n)
{
for(;;) {
if(n->op == ODOT || n->op == OPAREN) {
n = n->left;
continue;
}
if(n->op == OINDEX && isfixedarray(n->left->type)) {
n = n->left;
continue;
}
break;
}
return n;
}
/*
* Is it possible that the computation of n might be
* affected by writes in as up to but not including stop?
*/
static int
aliased(Node *n, NodeList *all, NodeList *stop)
{
int memwrite, varwrite;
Node *a;
NodeList *l;
if(n == N)
return 0;
// Look for obvious aliasing: a variable being assigned
// during the all list and appearing in n.
// Also record whether there are any writes to main memory.
// Also record whether there are any writes to variables
// whose addresses have been taken.
memwrite = 0;
varwrite = 0;
for(l=all; l!=stop; l=l->next) {
a = outervalue(l->n->left);
if(a->op != ONAME) {
memwrite = 1;
continue;
}
switch(n->class) {
default:
varwrite = 1;
continue;
case PAUTO:
case PPARAM:
case PPARAMOUT:
if(n->addrtaken) {
varwrite = 1;
continue;
}
if(vmatch2(a, n)) {
// Direct hit.
return 1;
}
}
}
// The variables being written do not appear in n.
// However, n might refer to computed addresses
// that are being written.
// If no computed addresses are affected by the writes, no aliasing.
if(!memwrite && !varwrite)
return 0;
// If n does not refer to computed addresses
// (that is, if n only refers to variables whose addresses
// have not been taken), no aliasing.
if(varexpr(n))
return 0;
// Otherwise, both the writes and n refer to computed memory addresses.
// Assume that they might conflict.
return 1;
}
/*
* does the evaluation of n only refer to variables
* whose addresses have not been taken?
* (and no other memory)
*/
static int
varexpr(Node *n)
{
if(n == N)
return 1;
switch(n->op) {
case OLITERAL:
return 1;
case ONAME:
switch(n->class) {
case PAUTO:
case PPARAM:
case PPARAMOUT:
if(!n->addrtaken)
return 1;
}
return 0;
case OADD:
case OSUB:
case OOR:
case OXOR:
case OMUL:
case ODIV:
case OMOD:
case OLSH:
case ORSH:
case OAND:
case OANDNOT:
case OPLUS:
case OMINUS:
case OCOM:
case OPAREN:
case OANDAND:
case OOROR:
case ODOT: // but not ODOTPTR
case OCONV:
case OCONVNOP:
case OCONVIFACE:
case ODOTTYPE:
return varexpr(n->left) && varexpr(n->right);
}
// Be conservative.
return 0;
}
/*
* is the name l mentioned in r?
*/
static int
vmatch2(Node *l, Node *r)
{
NodeList *ll;
if(r == N)
return 0;
switch(r->op) {
case ONAME:
// match each right given left
return l == r;
case OLITERAL:
return 0;
}
if(vmatch2(l, r->left))
return 1;
if(vmatch2(l, r->right))
return 1;
for(ll=r->list; ll; ll=ll->next)
if(vmatch2(l, ll->n))
return 1;
return 0;
}
/*
* is any name mentioned in l also mentioned in r?
* called by sinit.c
*/
int
vmatch1(Node *l, Node *r)
{
NodeList *ll;
/*
* isolate all left sides
*/
if(l == N || r == N)
return 0;
switch(l->op) {
case ONAME:
switch(l->class) {
case PPARAM:
case PPARAMREF:
case PAUTO:
break;
default:
// assignment to non-stack variable
// must be delayed if right has function calls.
if(r->ullman >= UINF)
return 1;
break;
}
return vmatch2(l, r);
case OLITERAL:
return 0;
}
if(vmatch1(l->left, r))
return 1;
if(vmatch1(l->right, r))
return 1;
for(ll=l->list; ll; ll=ll->next)
if(vmatch1(ll->n, r))
return 1;
return 0;
}
/*
* walk through argin parameters.
* generate and return code to allocate
* copies of escaped parameters to the heap.
*/
static NodeList*
paramstoheap(Type **argin, int out)
{
Type *t;
Iter savet;
Node *v;
NodeList *nn;
nn = nil;
for(t = structfirst(&savet, argin); t != T; t = structnext(&savet)) {
v = t->nname;
if(v && v->sym && v->sym->name[0] == '~' && v->sym->name[1] == 'r') // unnamed result
v = N;
// In precisestack mode, the garbage collector assumes results
// are always live, so zero them always.
if(out && (precisestack_enabled || (v == N && hasdefer))) {
// Defer might stop a panic and show the
// return values as they exist at the time of panic.
// Make sure to zero them on entry to the function.
nn = list(nn, nod(OAS, nodarg(t, 1), N));
}
if(v == N || !(v->class & PHEAP))
continue;
// generate allocation & copying code
if(v->alloc == nil)
v->alloc = callnew(v->type);
nn = list(nn, nod(OAS, v->heapaddr, v->alloc));
if((v->class & ~PHEAP) != PPARAMOUT)
nn = list(nn, nod(OAS, v, v->stackparam));
}
return nn;
}
/*
* walk through argout parameters copying back to stack
*/
static NodeList*
returnsfromheap(Type **argin)
{
Type *t;
Iter savet;
Node *v;
NodeList *nn;
nn = nil;
for(t = structfirst(&savet, argin); t != T; t = structnext(&savet)) {
v = t->nname;
if(v == N || v->class != (PHEAP|PPARAMOUT))
continue;
nn = list(nn, nod(OAS, v->stackparam, v));
}
return nn;
}
/*
* take care of migrating any function in/out args
* between the stack and the heap. adds code to
* curfn's before and after lists.
*/
static void
heapmoves(void)
{
NodeList *nn;
int32 lno;
lno = lineno;
lineno = curfn->lineno;
nn = paramstoheap(getthis(curfn->type), 0);
nn = concat(nn, paramstoheap(getinarg(curfn->type), 0));
nn = concat(nn, paramstoheap(getoutarg(curfn->type), 1));
curfn->enter = concat(curfn->enter, nn);
lineno = curfn->endlineno;
curfn->exit = returnsfromheap(getoutarg(curfn->type));
lineno = lno;
}
static Node*
vmkcall(Node *fn, Type *t, NodeList **init, va_list va)
{
int i, n;
Node *r;
NodeList *args;
if(fn->type == T || fn->type->etype != TFUNC)
fatal("mkcall %N %T", fn, fn->type);
args = nil;
n = fn->type->intuple;
for(i=0; i<n; i++)
args = list(args, va_arg(va, Node*));
r = nod(OCALL, fn, N);
r->list = args;
if(fn->type->outtuple > 0)
typecheck(&r, Erv | Efnstruct);
else
typecheck(&r, Etop);
walkexpr(&r, init);
r->type = t;
return r;
}
Node*
mkcall(char *name, Type *t, NodeList **init, ...)
{
Node *r;
va_list va;
va_start(va, init);
r = vmkcall(syslook(name, 0), t, init, va);
va_end(va);
return r;
}
Node*
mkcall1(Node *fn, Type *t, NodeList **init, ...)
{
Node *r;
va_list va;
va_start(va, init);
r = vmkcall(fn, t, init, va);
va_end(va);
return r;
}
Node*
conv(Node *n, Type *t)
{
if(eqtype(n->type, t))
return n;
n = nod(OCONV, n, N);
n->type = t;
typecheck(&n, Erv);
return n;
}
Node*
chanfn(char *name, int n, Type *t)
{
Node *fn;
int i;
if(t->etype != TCHAN)
fatal("chanfn %T", t);
fn = syslook(name, 1);
for(i=0; i<n; i++)
argtype(fn, t->type);
return fn;
}
static Node*
mapfn(char *name, Type *t)
{
Node *fn;
if(t->etype != TMAP)
fatal("mapfn %T", t);
fn = syslook(name, 1);
argtype(fn, t->down);
argtype(fn, t->type);
argtype(fn, t->down);
argtype(fn, t->type);
return fn;
}
static Node*
mapfndel(char *name, Type *t)
{
Node *fn;
if(t->etype != TMAP)
fatal("mapfn %T", t);
fn = syslook(name, 1);
argtype(fn, t->down);
argtype(fn, t->type);
argtype(fn, t->down);
return fn;
}
static Node*
addstr(Node *n, NodeList **init)
{
Node *r, *cat, *slice;
NodeList *args, *l;
int c;
Type *t;
// orderexpr rewrote OADDSTR to have a list of strings.
c = count(n->list);
if(c < 2)
yyerror("addstr count %d too small", c);
// build list of string arguments
args = nil;
for(l=n->list; l != nil; l=l->next)
args = list(args, conv(l->n, types[TSTRING]));
if(c <= 5) {
// small numbers of strings use direct runtime helpers.
// note: orderexpr knows this cutoff too.
snprint(namebuf, sizeof(namebuf), "concatstring%d", c);
} else {
// large numbers of strings are passed to the runtime as a slice.
strcpy(namebuf, "concatstrings");
t = typ(TARRAY);
t->type = types[TSTRING];
t->bound = -1;
slice = nod(OCOMPLIT, N, typenod(t));
slice->alloc = n->alloc;
slice->list = args;
slice->esc = EscNone;
args = list1(slice);
}
cat = syslook(namebuf, 1);
r = nod(OCALL, cat, N);
r->list = args;
typecheck(&r, Erv);
walkexpr(&r, init);
r->type = n->type;
return r;
}
// expand append(l1, l2...) to
// init {
// s := l1
// if n := len(l1) + len(l2) - cap(s); n > 0 {
// s = growslice(s, n)
// }
// s = s[:len(l1)+len(l2)]
// memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
// }
// s
//
// l2 is allowed to be a string.
static Node*
appendslice(Node *n, NodeList **init)
{
NodeList *l;
Node *l1, *l2, *nt, *nif, *fn;
Node *nptr1, *nptr2, *nwid;
Node *s;
walkexprlistsafe(n->list, init);
// walkexprlistsafe will leave OINDEX (s[n]) alone if both s
// and n are name or literal, but those may index the slice we're
// modifying here. Fix explicitly.
for(l=n->list; l; l=l->next)
l->n = cheapexpr(l->n, init);
l1 = n->list->n;
l2 = n->list->next->n;
s = temp(l1->type); // var s []T
l = nil;
l = list(l, nod(OAS, s, l1)); // s = l1
nt = temp(types[TINT]);
nif = nod(OIF, N, N);
// n := len(s) + len(l2) - cap(s)
nif->ninit = list1(nod(OAS, nt,
nod(OSUB, nod(OADD, nod(OLEN, s, N), nod(OLEN, l2, N)), nod(OCAP, s, N))));
nif->ntest = nod(OGT, nt, nodintconst(0));
// instantiate growslice(Type*, []any, int64) []any
fn = syslook("growslice", 1);
argtype(fn, s->type->type);
argtype(fn, s->type->type);
// s = growslice(T, s, n)
nif->nbody = list1(nod(OAS, s, mkcall1(fn, s->type, &nif->ninit,
typename(s->type),
s,
conv(nt, types[TINT64]))));
l = list(l, nif);
if(flag_race) {
// rely on runtime to instrument copy.
// copy(s[len(l1):len(l1)+len(l2)], l2)
nptr1 = nod(OSLICE, s, nod(OKEY,
nod(OLEN, l1, N),
nod(OADD, nod(OLEN, l1, N), nod(OLEN, l2, N))));
nptr1->etype = 1;
nptr2 = l2;
if(l2->type->etype == TSTRING)
fn = syslook("slicestringcopy", 1);
else
fn = syslook("copy", 1);
argtype(fn, l1->type);
argtype(fn, l2->type);
nt = mkcall1(fn, types[TINT], &l,
nptr1, nptr2,
nodintconst(s->type->type->width));
l = list(l, nt);
} else {
// memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
nptr1 = nod(OINDEX, s, nod(OLEN, l1, N));
nptr1->bounded = 1;
nptr1 = nod(OADDR, nptr1, N);
nptr2 = nod(OSPTR, l2, N);
fn = syslook("memmove", 1);
argtype(fn, s->type->type); // 1 old []any
argtype(fn, s->type->type); // 2 ret []any
nwid = cheapexpr(conv(nod(OLEN, l2, N), types[TUINTPTR]), &l);
nwid = nod(OMUL, nwid, nodintconst(s->type->type->width));
nt = mkcall1(fn, T, &l, nptr1, nptr2, nwid);
l = list(l, nt);
}
// s = s[:len(l1)+len(l2)]
nt = nod(OADD, nod(OLEN, l1, N), nod(OLEN, l2, N));
nt = nod(OSLICE, s, nod(OKEY, N, nt));
nt->etype = 1;
l = list(l, nod(OAS, s, nt));
typechecklist(l, Etop);
walkstmtlist(l);
*init = concat(*init, l);
return s;
}
// expand append(src, a [, b]* ) to
//
// init {
// s := src
// const argc = len(args) - 1
// if cap(s) - len(s) < argc {
// s = growslice(s, argc)
// }
// n := len(s)
// s = s[:n+argc]
// s[n] = a
// s[n+1] = b
// ...
// }
// s
static Node*
append(Node *n, NodeList **init)
{
NodeList *l, *a;
Node *nsrc, *ns, *nn, *na, *nx, *fn;
int argc;
walkexprlistsafe(n->list, init);
// walkexprlistsafe will leave OINDEX (s[n]) alone if both s
// and n are name or literal, but those may index the slice we're
// modifying here. Fix explicitly.
for(l=n->list; l; l=l->next)
l->n = cheapexpr(l->n, init);
nsrc = n->list->n;
// Resolve slice type of multi-valued return.
if(istype(nsrc->type, TSTRUCT))
nsrc->type = nsrc->type->type->type;
argc = count(n->list) - 1;
if (argc < 1) {
return nsrc;
}
l = nil;
ns = temp(nsrc->type);
l = list(l, nod(OAS, ns, nsrc)); // s = src
na = nodintconst(argc); // const argc
nx = nod(OIF, N, N); // if cap(s) - len(s) < argc
nx->ntest = nod(OLT, nod(OSUB, nod(OCAP, ns, N), nod(OLEN, ns, N)), na);
fn = syslook("growslice", 1); // growslice(<type>, old []T, n int64) (ret []T)
argtype(fn, ns->type->type); // 1 old []any
argtype(fn, ns->type->type); // 2 ret []any
nx->nbody = list1(nod(OAS, ns, mkcall1(fn, ns->type, &nx->ninit,
typename(ns->type),
ns,
conv(na, types[TINT64]))));
l = list(l, nx);
nn = temp(types[TINT]);
l = list(l, nod(OAS, nn, nod(OLEN, ns, N))); // n = len(s)
nx = nod(OSLICE, ns, nod(OKEY, N, nod(OADD, nn, na))); // ...s[:n+argc]
nx->etype = 1;
l = list(l, nod(OAS, ns, nx)); // s = s[:n+argc]
for (a = n->list->next; a != nil; a = a->next) {
nx = nod(OINDEX, ns, nn); // s[n] ...
nx->bounded = 1;
l = list(l, nod(OAS, nx, a->n)); // s[n] = arg
if (a->next != nil)
l = list(l, nod(OAS, nn, nod(OADD, nn, nodintconst(1)))); // n = n + 1
}
typechecklist(l, Etop);
walkstmtlist(l);
*init = concat(*init, l);
return ns;
}
// Lower copy(a, b) to a memmove call or a runtime call.
//
// init {
// n := len(a)
// if n > len(b) { n = len(b) }
// memmove(a.ptr, b.ptr, n*sizeof(elem(a)))
// }
// n;
//
// Also works if b is a string.
//
static Node*
copyany(Node *n, NodeList **init, int runtimecall)
{
Node *nl, *nr, *nfrm, *nto, *nif, *nlen, *nwid, *fn;
NodeList *l;
if(runtimecall) {
if(n->right->type->etype == TSTRING)
fn = syslook("slicestringcopy", 1);
else
fn = syslook("copy", 1);
argtype(fn, n->left->type);
argtype(fn, n->right->type);
return mkcall1(fn, n->type, init,
n->left, n->right,
nodintconst(n->left->type->type->width));
}
walkexpr(&n->left, init);
walkexpr(&n->right, init);
nl = temp(n->left->type);
nr = temp(n->right->type);
l = nil;
l = list(l, nod(OAS, nl, n->left));
l = list(l, nod(OAS, nr, n->right));
nfrm = nod(OSPTR, nr, N);
nto = nod(OSPTR, nl, N);
nlen = temp(types[TINT]);
// n = len(to)
l = list(l, nod(OAS, nlen, nod(OLEN, nl, N)));
// if n > len(frm) { n = len(frm) }
nif = nod(OIF, N, N);
nif->ntest = nod(OGT, nlen, nod(OLEN, nr, N));
nif->nbody = list(nif->nbody,
nod(OAS, nlen, nod(OLEN, nr, N)));
l = list(l, nif);
// Call memmove.
fn = syslook("memmove", 1);
argtype(fn, nl->type->type);
argtype(fn, nl->type->type);
nwid = temp(types[TUINTPTR]);
l = list(l, nod(OAS, nwid, conv(nlen, types[TUINTPTR])));
nwid = nod(OMUL, nwid, nodintconst(nl->type->type->width));
l = list(l, mkcall1(fn, T, init, nto, nfrm, nwid));
typechecklist(l, Etop);
walkstmtlist(l);
*init = concat(*init, l);
return nlen;
}
// Generate frontend part for OSLICE[3][ARR|STR]
//
static Node*
sliceany(Node* n, NodeList **init)
{
int bounded, slice3;
Node *src, *lb, *hb, *cb, *bound, *chk, *chk0, *chk1, *chk2;
int64 lbv, hbv, cbv, bv, w;
Type *bt;
// print("before sliceany: %+N\n", n);
src = n->left;
lb = n->right->left;
slice3 = n->op == OSLICE3 || n->op == OSLICE3ARR;
if(slice3) {
hb = n->right->right->left;
cb = n->right->right->right;
} else {
hb = n->right->right;
cb = N;
}
bounded = n->etype;
if(n->op == OSLICESTR)
bound = nod(OLEN, src, N);
else
bound = nod(OCAP, src, N);
typecheck(&bound, Erv);
walkexpr(&bound, init); // if src is an array, bound will be a const now.
// static checks if possible
bv = 1LL<<50;
if(isconst(bound, CTINT)) {
if(!smallintconst(bound))
yyerror("array len too large");
else
bv = mpgetfix(bound->val.u.xval);
}
if(isconst(cb, CTINT)) {
cbv = mpgetfix(cb->val.u.xval);
if(cbv < 0 || cbv > bv)
yyerror("slice index out of bounds");
}
if(isconst(hb, CTINT)) {
hbv = mpgetfix(hb->val.u.xval);
if(hbv < 0 || hbv > bv)
yyerror("slice index out of bounds");
}
if(isconst(lb, CTINT)) {
lbv = mpgetfix(lb->val.u.xval);
if(lbv < 0 || lbv > bv) {
yyerror("slice index out of bounds");
lbv = -1;
}
if(lbv == 0)
lb = N;
}
// dynamic checks convert all bounds to unsigned to save us the bound < 0 comparison
// generate
// if hb > bound || lb > hb { panicslice() }
chk = N;
chk0 = N;
chk1 = N;
chk2 = N;
bt = types[simtype[TUINT]];
if(cb != N && cb->type->width > 4)
bt = types[TUINT64];
if(hb != N && hb->type->width > 4)
bt = types[TUINT64];
if(lb != N && lb->type->width > 4)
bt = types[TUINT64];
bound = cheapexpr(conv(bound, bt), init);
if(cb != N) {
cb = cheapexpr(conv(cb, bt), init);
if(!bounded)
chk0 = nod(OLT, bound, cb);
} else if(slice3) {
// When we figure out what this means, implement it.
fatal("slice3 with cb == N"); // rejected by parser
}
if(hb != N) {
hb = cheapexpr(conv(hb, bt), init);
if(!bounded) {
if(cb != N)
chk1 = nod(OLT, cb, hb);
else
chk1 = nod(OLT, bound, hb);
}
} else if(slice3) {
// When we figure out what this means, implement it.
fatal("slice3 with hb == N"); // rejected by parser
} else if(n->op == OSLICEARR) {
hb = bound;
} else {
hb = nod(OLEN, src, N);
typecheck(&hb, Erv);
walkexpr(&hb, init);
hb = cheapexpr(conv(hb, bt), init);
}
if(lb != N) {
lb = cheapexpr(conv(lb, bt), init);
if(!bounded)
chk2 = nod(OLT, hb, lb);
}
if(chk0 != N || chk1 != N || chk2 != N) {
chk = nod(OIF, N, N);
chk->nbody = list1(mkcall("panicslice", T, init));
chk->likely = -1;
if(chk0 != N)
chk->ntest = chk0;
if(chk1 != N) {
if(chk->ntest == N)
chk->ntest = chk1;
else
chk->ntest = nod(OOROR, chk->ntest, chk1);
}
if(chk2 != N) {
if(chk->ntest == N)
chk->ntest = chk2;
else
chk->ntest = nod(OOROR, chk->ntest, chk2);
}
typecheck(&chk, Etop);
walkstmt(&chk);
*init = concat(*init, chk->ninit);
chk->ninit = nil;
*init = list(*init, chk);
}
// prepare new cap, len and offs for backend cgen_slice
// cap = bound [ - lo ]
n->right = N;
n->list = nil;
if(!slice3)
cb = bound;
if(lb == N)
bound = conv(cb, types[simtype[TUINT]]);
else
bound = nod(OSUB, conv(cb, types[simtype[TUINT]]), conv(lb, types[simtype[TUINT]]));
typecheck(&bound, Erv);
walkexpr(&bound, init);
n->list = list(n->list, bound);
// len = hi [ - lo]
if(lb == N)
hb = conv(hb, types[simtype[TUINT]]);
else
hb = nod(OSUB, conv(hb, types[simtype[TUINT]]), conv(lb, types[simtype[TUINT]]));
typecheck(&hb, Erv);
walkexpr(&hb, init);
n->list = list(n->list, hb);
// offs = [width *] lo, but omit if zero
if(lb != N) {
if(n->op == OSLICESTR)
w = 1;
else
w = n->type->type->width;
lb = conv(lb, types[TUINTPTR]);
if(w > 1)
lb = nod(OMUL, nodintconst(w), lb);
typecheck(&lb, Erv);
walkexpr(&lb, init);
n->list = list(n->list, lb);
}
// print("after sliceany: %+N\n", n);
return n;
}
static Node*
eqfor(Type *t)
{
int a;
Node *n;
Node *ntype;
Sym *sym;
// Should only arrive here with large memory or
// a struct/array containing a non-memory field/element.
// Small memory is handled inline, and single non-memory
// is handled during type check (OCMPSTR etc).
a = algtype1(t, nil);
if(a != AMEM && a != -1)
fatal("eqfor %T", t);
if(a == AMEM) {
n = syslook("memequal", 1);
argtype(n, t);
argtype(n, t);
return n;
}
sym = typesymprefix(".eq", t);
n = newname(sym);
n->class = PFUNC;
ntype = nod(OTFUNC, N, N);
ntype->list = list(ntype->list, nod(ODCLFIELD, N, typenod(ptrto(types[TBOOL]))));
ntype->list = list(ntype->list, nod(ODCLFIELD, N, typenod(types[TUINTPTR])));
ntype->list = list(ntype->list, nod(ODCLFIELD, N, typenod(ptrto(t))));
ntype->list = list(ntype->list, nod(ODCLFIELD, N, typenod(ptrto(t))));
typecheck(&ntype, Etype);
n->type = ntype->type;
return n;
}
static int
countfield(Type *t)
{
Type *t1;
int n;
n = 0;
for(t1=t->type; t1!=T; t1=t1->down)
n++;
return n;
}
static void
walkcompare(Node **np, NodeList **init)
{
Node *n, *l, *r, *fn, *call, *a, *li, *ri, *expr;
int andor, i;
Type *t, *t1;
static Node *tempbool;
n = *np;
// Must be comparison of array or struct.
// Otherwise back end handles it.
t = n->left->type;
switch(t->etype) {
default:
return;
case TARRAY:
if(isslice(t))
return;
break;
case TSTRUCT:
break;
}
if(!islvalue(n->left) || !islvalue(n->right))
goto hard;
l = temp(ptrto(t));
a = nod(OAS, l, nod(OADDR, n->left, N));
a->right->etype = 1; // addr does not escape
typecheck(&a, Etop);
*init = list(*init, a);
r = temp(ptrto(t));
a = nod(OAS, r, nod(OADDR, n->right, N));
a->right->etype = 1; // addr does not escape
typecheck(&a, Etop);
*init = list(*init, a);
expr = N;
andor = OANDAND;
if(n->op == ONE)
andor = OOROR;
if(t->etype == TARRAY &&
t->bound <= 4 &&
issimple[t->type->etype]) {
// Four or fewer elements of a basic type.
// Unroll comparisons.
for(i=0; i<t->bound; i++) {
li = nod(OINDEX, l, nodintconst(i));
ri = nod(OINDEX, r, nodintconst(i));
a = nod(n->op, li, ri);
if(expr == N)
expr = a;
else
expr = nod(andor, expr, a);
}
if(expr == N)
expr = nodbool(n->op == OEQ);
r = expr;
goto ret;
}
if(t->etype == TSTRUCT && countfield(t) <= 4) {
// Struct of four or fewer fields.
// Inline comparisons.
for(t1=t->type; t1; t1=t1->down) {
if(isblanksym(t1->sym))
continue;
li = nod(OXDOT, l, newname(t1->sym));
ri = nod(OXDOT, r, newname(t1->sym));
a = nod(n->op, li, ri);
if(expr == N)
expr = a;
else
expr = nod(andor, expr, a);
}
if(expr == N)
expr = nodbool(n->op == OEQ);
r = expr;
goto ret;
}
// Chose not to inline, but still have addresses.
// Call equality function directly.
// The equality function requires a bool pointer for
// storing its address, because it has to be callable
// from C, and C can't access an ordinary Go return value.
// To avoid creating many temporaries, cache one per function.
if(tempbool == N || tempbool->curfn != curfn)
tempbool = temp(types[TBOOL]);
call = nod(OCALL, eqfor(t), N);
a = nod(OADDR, tempbool, N);
a->etype = 1; // does not escape
call->list = list(call->list, a);
call->list = list(call->list, nodintconst(t->width));
call->list = list(call->list, l);
call->list = list(call->list, r);
typecheck(&call, Etop);
walkstmt(&call);
*init = list(*init, call);
// tempbool cannot be used directly as multiple comparison
// expressions may exist in the same statement. Create another
// temporary to hold the value (its address is not taken so it can
// be optimized away).
r = temp(types[TBOOL]);
a = nod(OAS, r, tempbool);
typecheck(&a, Etop);
walkstmt(&a);
*init = list(*init, a);
if(n->op != OEQ)
r = nod(ONOT, r, N);
goto ret;
hard:
// Cannot take address of one or both of the operands.
// Instead, pass directly to runtime helper function.
// Easier on the stack than passing the address
// of temporary variables, because we are better at reusing
// the argument space than temporary variable space.
fn = syslook("equal", 1);
l = n->left;
r = n->right;
argtype(fn, n->left->type);
argtype(fn, n->left->type);
r = mkcall1(fn, n->type, init, typename(n->left->type), l, r);
if(n->op == ONE) {
r = nod(ONOT, r, N);
}
goto ret;
ret:
typecheck(&r, Erv);
walkexpr(&r, init);
if(r->type != n->type) {
r = nod(OCONVNOP, r, N);
r->type = n->type;
r->typecheck = 1;
}
*np = r;
return;
}
static int
samecheap(Node *a, Node *b)
{
Node *ar, *br;
while(a != N && b != N && a->op == b->op) {
switch(a->op) {
default:
return 0;
case ONAME:
return a == b;
case ODOT:
case ODOTPTR:
ar = a->right;
br = b->right;
if(ar->op != ONAME || br->op != ONAME || ar->sym != br->sym)
return 0;
break;
case OINDEX:
ar = a->right;
br = b->right;
if(!isconst(ar, CTINT) || !isconst(br, CTINT) || mpcmpfixfix(ar->val.u.xval, br->val.u.xval) != 0)
return 0;
break;
}
a = a->left;
b = b->left;
}
return 0;
}
static void
walkrotate(Node **np)
{
int w, sl, sr, s;
Node *l, *r;
Node *n;
n = *np;
// Want << | >> or >> | << or << ^ >> or >> ^ << on unsigned value.
l = n->left;
r = n->right;
if((n->op != OOR && n->op != OXOR) ||
(l->op != OLSH && l->op != ORSH) ||
(r->op != OLSH && r->op != ORSH) ||
n->type == T || issigned[n->type->etype] ||
l->op == r->op) {
return;
}
// Want same, side effect-free expression on lhs of both shifts.
if(!samecheap(l->left, r->left))
return;
// Constants adding to width?
w = l->type->width * 8;
if(smallintconst(l->right) && smallintconst(r->right)) {
if((sl=mpgetfix(l->right->val.u.xval)) >= 0 && (sr=mpgetfix(r->right->val.u.xval)) >= 0 && sl+sr == w)
goto yes;
return;
}
// TODO: Could allow s and 32-s if s is bounded (maybe s&31 and 32-s&31).
return;
yes:
// Rewrite left shift half to left rotate.
if(l->op == OLSH)
n = l;
else
n = r;
n->op = OLROT;
// Remove rotate 0 and rotate w.
s = mpgetfix(n->right->val.u.xval);
if(s == 0 || s == w)
n = n->left;
*np = n;
return;
}
/*
* walkmul rewrites integer multiplication by powers of two as shifts.
*/
static void
walkmul(Node **np, NodeList **init)
{
Node *n, *nl, *nr;
int pow, neg, w;
n = *np;
if(!isint[n->type->etype])
return;
if(n->right->op == OLITERAL) {
nl = n->left;
nr = n->right;
} else if(n->left->op == OLITERAL) {
nl = n->right;
nr = n->left;
} else
return;
neg = 0;
// x*0 is 0 (and side effects of x).
if(mpgetfix(nr->val.u.xval) == 0) {
cheapexpr(nl, init);
nodconst(n, n->type, 0);
goto ret;
}
// nr is a constant.
pow = powtwo(nr);
if(pow < 0)
return;
if(pow >= 1000) {
// negative power of 2, like -16
neg = 1;
pow -= 1000;
}
w = nl->type->width*8;
if(pow+1 >= w)// too big, shouldn't happen
return;
nl = cheapexpr(nl, init);
if(pow == 0) {
// x*1 is x
n = nl;
goto ret;
}
n = nod(OLSH, nl, nodintconst(pow));
ret:
if(neg)
n = nod(OMINUS, n, N);
typecheck(&n, Erv);
walkexpr(&n, init);
*np = n;
}
/*
* walkdiv rewrites division by a constant as less expensive
* operations.
*/
static void
walkdiv(Node **np, NodeList **init)
{
Node *n, *nl, *nr, *nc;
Node *n1, *n2, *n3, *n4;
int pow; // if >= 0, nr is 1<<pow
int s; // 1 if nr is negative.
int w;
Type *twide;
Magic m;
n = *np;
if(n->right->op != OLITERAL)
return;
// nr is a constant.
nl = cheapexpr(n->left, init);
nr = n->right;
// special cases of mod/div
// by a constant
w = nl->type->width*8;
s = 0;
pow = powtwo(nr);
if(pow >= 1000) {
// negative power of 2
s = 1;
pow -= 1000;
}
if(pow+1 >= w) {
// divisor too large.
return;
}
if(pow < 0) {
goto divbymul;
}
switch(pow) {
case 0:
if(n->op == OMOD) {
// nl % 1 is zero.
nodconst(n, n->type, 0);
} else if(s) {
// divide by -1
n->op = OMINUS;
n->right = N;
} else {
// divide by 1
n = nl;
}
break;
default:
if(issigned[n->type->etype]) {
if(n->op == OMOD) {
// signed modulo 2^pow is like ANDing
// with the last pow bits, but if nl < 0,
// nl & (2^pow-1) is (nl+1)%2^pow - 1.
nc = nod(OXXX, N, N);
nodconst(nc, types[simtype[TUINT]], w-1);
n1 = nod(ORSH, nl, nc); // n1 = -1 iff nl < 0.
if(pow == 1) {
typecheck(&n1, Erv);
n1 = cheapexpr(n1, init);
// n = (nl+ε)&1 -ε where ε=1 iff nl<0.
n2 = nod(OSUB, nl, n1);
nc = nod(OXXX, N, N);
nodconst(nc, nl->type, 1);
n3 = nod(OAND, n2, nc);
n = nod(OADD, n3, n1);
} else {
// n = (nl+ε)&(nr-1) - ε where ε=2^pow-1 iff nl<0.
nc = nod(OXXX, N, N);
nodconst(nc, nl->type, (1LL<<pow)-1);
n2 = nod(OAND, n1, nc); // n2 = 2^pow-1 iff nl<0.
typecheck(&n2, Erv);
n2 = cheapexpr(n2, init);
n3 = nod(OADD, nl, n2);
n4 = nod(OAND, n3, nc);
n = nod(OSUB, n4, n2);
}
break;
} else {
// arithmetic right shift does not give the correct rounding.
// if nl >= 0, nl >> n == nl / nr
// if nl < 0, we want to add 2^n-1 first.
nc = nod(OXXX, N, N);
nodconst(nc, types[simtype[TUINT]], w-1);
n1 = nod(ORSH, nl, nc); // n1 = -1 iff nl < 0.
if(pow == 1) {
// nl+1 is nl-(-1)
n->left = nod(OSUB, nl, n1);
} else {
// Do a logical right right on -1 to keep pow bits.
nc = nod(OXXX, N, N);
nodconst(nc, types[simtype[TUINT]], w-pow);
n2 = nod(ORSH, conv(n1, tounsigned(nl->type)), nc);
n->left = nod(OADD, nl, conv(n2, nl->type));
}
// n = (nl + 2^pow-1) >> pow
n->op = ORSH;
nc = nod(OXXX, N, N);
nodconst(nc, types[simtype[TUINT]], pow);
n->right = nc;
n->typecheck = 0;
}
if(s)
n = nod(OMINUS, n, N);
break;
}
nc = nod(OXXX, N, N);
if(n->op == OMOD) {
// n = nl & (nr-1)
n->op = OAND;
nodconst(nc, nl->type, mpgetfix(nr->val.u.xval)-1);
} else {
// n = nl >> pow
n->op = ORSH;
nodconst(nc, types[simtype[TUINT]], pow);
}
n->typecheck = 0;
n->right = nc;
break;
}
goto ret;
divbymul:
// try to do division by multiply by (2^w)/d
// see hacker's delight chapter 10
// TODO: support 64-bit magic multiply here.
m.w = w;
if(issigned[nl->type->etype]) {
m.sd = mpgetfix(nr->val.u.xval);
smagic(&m);
} else {
m.ud = mpgetfix(nr->val.u.xval);
umagic(&m);
}
if(m.bad)
return;
// We have a quick division method so use it
// for modulo too.
if(n->op == OMOD)
goto longmod;
switch(simtype[nl->type->etype]) {
default:
return;
case TUINT8:
case TUINT16:
case TUINT32:
// n1 = nl * magic >> w (HMUL)
nc = nod(OXXX, N, N);
nodconst(nc, nl->type, m.um);
n1 = nod(OMUL, nl, nc);
typecheck(&n1, Erv);
n1->op = OHMUL;
if(m.ua) {
// Select a Go type with (at least) twice the width.
switch(simtype[nl->type->etype]) {
default:
return;
case TUINT8:
case TUINT16:
twide = types[TUINT32];
break;
case TUINT32:
twide = types[TUINT64];
break;
case TINT8:
case TINT16:
twide = types[TINT32];
break;
case TINT32:
twide = types[TINT64];
break;
}
// add numerator (might overflow).
// n2 = (n1 + nl)
n2 = nod(OADD, conv(n1, twide), conv(nl, twide));
// shift by m.s
nc = nod(OXXX, N, N);
nodconst(nc, types[TUINT], m.s);
n = conv(nod(ORSH, n2, nc), nl->type);
} else {
// n = n1 >> m.s
nc = nod(OXXX, N, N);
nodconst(nc, types[TUINT], m.s);
n = nod(ORSH, n1, nc);
}
break;
case TINT8:
case TINT16:
case TINT32:
// n1 = nl * magic >> w
nc = nod(OXXX, N, N);
nodconst(nc, nl->type, m.sm);
n1 = nod(OMUL, nl, nc);
typecheck(&n1, Erv);
n1->op = OHMUL;
if(m.sm < 0) {
// add the numerator.
n1 = nod(OADD, n1, nl);
}
// shift by m.s
nc = nod(OXXX, N, N);
nodconst(nc, types[TUINT], m.s);
n2 = conv(nod(ORSH, n1, nc), nl->type);
// add 1 iff n1 is negative.
nc = nod(OXXX, N, N);
nodconst(nc, types[TUINT], w-1);
n3 = nod(ORSH, nl, nc); // n4 = -1 iff n1 is negative.
n = nod(OSUB, n2, n3);
// apply sign.
if(m.sd < 0)
n = nod(OMINUS, n, N);
break;
}
goto ret;
longmod:
// rewrite as A%B = A - (A/B*B).
n1 = nod(ODIV, nl, nr);
n2 = nod(OMUL, n1, nr);
n = nod(OSUB, nl, n2);
goto ret;
ret:
typecheck(&n, Erv);
walkexpr(&n, init);
*np = n;
}
// return 1 if integer n must be in range [0, max), 0 otherwise
static int
bounded(Node *n, int64 max)
{
int64 v;
int32 bits;
int sign;
if(n->type == T || !isint[n->type->etype])
return 0;
sign = issigned[n->type->etype];
bits = 8*n->type->width;
if(smallintconst(n)) {
v = mpgetfix(n->val.u.xval);
return 0 <= v && v < max;
}
switch(n->op) {
case OAND:
v = -1;
if(smallintconst(n->left)) {
v = mpgetfix(n->left->val.u.xval);
} else if(smallintconst(n->right)) {
v = mpgetfix(n->right->val.u.xval);
}
if(0 <= v && v < max)
return 1;
break;
case OMOD:
if(!sign && smallintconst(n->right)) {
v = mpgetfix(n->right->val.u.xval);
if(0 <= v && v <= max)
return 1;
}
break;
case ODIV:
if(!sign && smallintconst(n->right)) {
v = mpgetfix(n->right->val.u.xval);
while(bits > 0 && v >= 2) {
bits--;
v >>= 1;
}
}
break;
case ORSH:
if(!sign && smallintconst(n->right)) {
v = mpgetfix(n->right->val.u.xval);
if(v > bits)
return 1;
bits -= v;
}
break;
}
if(!sign && bits <= 62 && (1LL<<bits) <= max)
return 1;
return 0;
}
void
usefield(Node *n)
{
Type *field, *l;
if(!fieldtrack_enabled)
return;
switch(n->op) {
default:
fatal("usefield %O", n->op);
case ODOT:
case ODOTPTR:
break;
}
field = n->paramfld;
if(field == T)
fatal("usefield %T %S without paramfld", n->left->type, n->right->sym);
if(field->note == nil || strstr(field->note->s, "go:\"track\"") == nil)
return;
// dedup on list
if(field->lastfn == curfn)
return;
field->lastfn = curfn;
field->outer = n->left->type;
if(isptr[field->outer->etype])
field->outer = field->outer->type;
if(field->outer->sym == S)
yyerror("tracked field must be in named struct type");
if(!exportname(field->sym->name))
yyerror("tracked field must be exported (upper case)");
l = typ(0);
l->type = field;
l->down = curfn->paramfld;
curfn->paramfld = l;
}
static int
candiscardlist(NodeList *l)
{
for(; l; l=l->next)
if(!candiscard(l->n))
return 0;
return 1;
}
int
candiscard(Node *n)
{
if(n == N)
return 1;
switch(n->op) {
default:
return 0;
case ONAME:
case ONONAME:
case OTYPE:
case OPACK:
case OLITERAL:
case OADD:
case OSUB:
case OOR:
case OXOR:
case OADDSTR:
case OADDR:
case OANDAND:
case OARRAYBYTESTR:
case OARRAYRUNESTR:
case OSTRARRAYBYTE:
case OSTRARRAYRUNE:
case OCAP:
case OCMPIFACE:
case OCMPSTR:
case OCOMPLIT:
case OMAPLIT:
case OSTRUCTLIT:
case OARRAYLIT:
case OPTRLIT:
case OCONV:
case OCONVIFACE:
case OCONVNOP:
case ODOT:
case OEQ:
case ONE:
case OLT:
case OLE:
case OGT:
case OGE:
case OKEY:
case OLEN:
case OMUL:
case OLSH:
case ORSH:
case OAND:
case OANDNOT:
case ONEW:
case ONOT:
case OCOM:
case OPLUS:
case OMINUS:
case OOROR:
case OPAREN:
case ORUNESTR:
case OREAL:
case OIMAG:
case OCOMPLEX:
// Discardable as long as the subpieces are.
break;
case ODIV:
case OMOD:
// Discardable as long as we know it's not division by zero.
if(isconst(n->right, CTINT) && mpcmpfixc(n->right->val.u.xval, 0) != 0)
break;
if(isconst(n->right, CTFLT) && mpcmpfltc(n->right->val.u.fval, 0) != 0)
break;
return 0;
case OMAKECHAN:
case OMAKEMAP:
// Discardable as long as we know it won't fail because of a bad size.
if(isconst(n->left, CTINT) && mpcmpfixc(n->left->val.u.xval, 0) == 0)
break;
return 0;
case OMAKESLICE:
// Difficult to tell what sizes are okay.
return 0;
}
if(!candiscard(n->left) ||
!candiscard(n->right) ||
!candiscard(n->ntest) ||
!candiscard(n->nincr) ||
!candiscardlist(n->ninit) ||
!candiscardlist(n->nbody) ||
!candiscardlist(n->nelse) ||
!candiscardlist(n->list) ||
!candiscardlist(n->rlist)) {
return 0;
}
return 1;
}