src/cmd/gc/walk.c

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 #include        <u.h>
   6 #include        <libc.h>
   7 #include        "go.h"
   8 #include        "../ld/textflag.h"
   9 #include        "../../runtime/mgc0.h"
  10
  11 static  Node*   walkprint(Node*, NodeList**);
  12 static  Node*   writebarrierfn(char*, Type*, Type*);
  13 static  Node*   applywritebarrier(Node*, NodeList**);
  14 static  Node*   mapfn(char*, Type*);
  15 static  Node*   mapfndel(char*, Type*);
  16 static  Node*   ascompatee1(int, Node*, Node*, NodeList**);
  17 static  NodeList*       ascompatee(int, NodeList*, NodeList*, NodeList**);
  18 static  NodeList*       ascompatet(int, NodeList*, Type**, int, NodeList**);
  19 static  NodeList*       ascompatte(int, Node*, int, Type**, NodeList*, int, NodeList**);
  20 static  Node*   convas(Node*, NodeList**);
  21 static  void    heapmoves(void);
  22 static  NodeList*       paramstoheap(Type **argin, int out);
  23 static  NodeList*       reorder1(NodeList*);
  24 static  NodeList*       reorder3(NodeList*);
  25 static  Node*   addstr(Node*, NodeList**);
  26 static  Node*   appendslice(Node*, NodeList**);
  27 static  Node*   append(Node*, NodeList**);
  28 static  Node*   copyany(Node*, NodeList**, int);
  29 static  Node*   sliceany(Node*, NodeList**);
  30 static  void    walkcompare(Node**, NodeList**);
  31 static  void    walkrotate(Node**);
  32 static  void    walkmul(Node**, NodeList**);
  33 static  void    walkdiv(Node**, NodeList**);
  34 static  int     bounded(Node*, int64);
  35 static  Mpint   mpzero;
  36 static  void    walkprintfunc(Node**, NodeList**);
  37
  38 void
  39 walk(Node *fn)
  40 {
  41         char s[50];
  42         NodeList *l;
  43         int lno;
  44
  45         curfn = fn;
  46
  47         if(debug['W']) {
  48                 snprint(s, sizeof(s), "\nbefore %S", curfn->nname->sym);
  49                 dumplist(s, curfn->nbody);
  50         }
  51
  52         lno = lineno;
  53
  54         // Final typecheck for any unused variables.
  55         // It's hard to be on the heap when not-used, but best to be consistent about &~PHEAP here and below.
  56         for(l=fn->dcl; l; l=l->next)
  57                 if(l->n->op == ONAME && (l->n->class&~PHEAP) == PAUTO)
  58                         typecheck(&l->n, Erv | Easgn);
  59
  60         // Propagate the used flag for typeswitch variables up to the NONAME in it's definition.
  61         for(l=fn->dcl; l; l=l->next)
  62                 if(l->n->op == ONAME && (l->n->class&~PHEAP) == PAUTO && l->n->defn && l->n->defn->op == OTYPESW && l->n->used)
  63                         l->n->defn->left->used++;
  64
  65         for(l=fn->dcl; l; l=l->next) {
  66                 if(l->n->op != ONAME || (l->n->class&~PHEAP) != PAUTO || l->n->sym->name[0] == '&' || l->n->used)
  67                         continue;
  68                 if(l->n->defn && l->n->defn->op == OTYPESW) {
  69                         if(l->n->defn->left->used)
  70                                 continue;
  71                         lineno = l->n->defn->left->lineno;
  72                         yyerror("%S declared and not used", l->n->sym);
  73                         l->n->defn->left->used = 1; // suppress repeats
  74                 } else {
  75                         lineno = l->n->lineno;
  76                         yyerror("%S declared and not used", l->n->sym);
  77                 }
  78         }
  79
  80         lineno = lno;
  81         if(nerrors != 0)
  82                 return;
  83         walkstmtlist(curfn->nbody);
  84         if(debug['W']) {
  85                 snprint(s, sizeof(s), "after walk %S", curfn->nname->sym);
  86                 dumplist(s, curfn->nbody);
  87         }
  88         heapmoves();
  89         if(debug['W'] && curfn->enter != nil) {
  90                 snprint(s, sizeof(s), "enter %S", curfn->nname->sym);
  91                 dumplist(s, curfn->enter);
  92         }
  93 }
  94
  95
  96 void
  97 walkstmtlist(NodeList *l)
  98 {
  99         for(; l; l=l->next)
 100                 walkstmt(&l->n);
 101 }
 102
 103 static int
 104 samelist(NodeList *a, NodeList *b)
 105 {
 106         for(; a && b; a=a->next, b=b->next)
 107                 if(a->n != b->n)
 108                         return 0;
 109         return a == b;
 110 }
 111
 112 static int
 113 paramoutheap(Node *fn)
 114 {
 115         NodeList *l;
 116
 117         for(l=fn->dcl; l; l=l->next) {
 118                 switch(l->n->class) {
 119                 case PPARAMOUT:
 120                 case PPARAMOUT|PHEAP:
 121                         return l->n->addrtaken;
 122                 case PAUTO:
 123                 case PAUTO|PHEAP:
 124                         // stop early - parameters are over
 125                         return 0;
 126                 }
 127         }
 128         return 0;
 129 }
 130
 131 void
 132 walkstmt(Node **np)
 133 {
 134         NodeList *init;
 135         NodeList *ll, *rl;
 136         int cl;
 137         Node *n, *f;
 138
 139         n = *np;
 140         if(n == N)
 141                 return;
 142         if(n->dodata == 2) // don't walk, generated by anylit.
 143                 return;
 144
 145         setlineno(n);
 146
 147         walkstmtlist(n->ninit);
 148
 149         switch(n->op) {
 150         default:
 151                 if(n->op == ONAME)
 152                         yyerror("%S is not a top level statement", n->sym);
 153                 else
 154                         yyerror("%O is not a top level statement", n->op);
 155                 dump("nottop", n);
 156                 break;
 157
 158         case OAS:
 159         case OASOP:
 160         case OAS2:
 161         case OAS2DOTTYPE:
 162         case OAS2RECV:
 163         case OAS2FUNC:
 164         case OAS2MAPR:
 165         case OCLOSE:
 166         case OCOPY:
 167         case OCALLMETH:
 168         case OCALLINTER:
 169         case OCALL:
 170         case OCALLFUNC:
 171         case ODELETE:
 172         case OSEND:
 173         case OPRINT:
 174         case OPRINTN:
 175         case OPANIC:
 176         case OEMPTY:
 177         case ORECOVER:
 178                 if(n->typecheck == 0)
 179                         fatal("missing typecheck: %+N", n);
 180                 init = n->ninit;
 181                 n->ninit = nil;
 182                 walkexpr(&n, &init);
 183                 addinit(&n, init);
 184                 if((*np)->op == OCOPY && n->op == OCONVNOP)
 185                         n->op = OEMPTY; // don't leave plain values as statements.
 186                 break;
 187
 188         case ORECV:
 189                 // special case for a receive where we throw away
 190                 // the value received.
 191                 if(n->typecheck == 0)
 192                         fatal("missing typecheck: %+N", n);
 193                 init = n->ninit;
 194                 n->ninit = nil;
 195
 196                 walkexpr(&n->left, &init);
 197                 n = mkcall1(chanfn("chanrecv1", 2, n->left->type), T, &init, typename(n->left->type), n->left, nodnil());
 198                 walkexpr(&n, &init);
 199
 200                 addinit(&n, init);
 201                 break;
 202
 203         case OBREAK:
 204         case ODCL:
 205         case OCONTINUE:
 206         case OFALL:
 207         case OGOTO:
 208         case OLABEL:
 209         case ODCLCONST:
 210         case ODCLTYPE:
 211         case OCHECKNIL:
 212         case OVARKILL:
 213                 break;
 214
 215         case OBLOCK:
 216                 walkstmtlist(n->list);
 217                 break;
 218
 219         case OXCASE:
 220                 yyerror("case statement out of place");
 221                 n->op = OCASE;
 222         case OCASE:
 223                 walkstmt(&n->right);
 224                 break;
 225
 226         case ODEFER:
 227                 hasdefer = 1;
 228                 switch(n->left->op) {
 229                 case OPRINT:
 230                 case OPRINTN:
 231                         walkprintfunc(&n->left, &n->ninit);
 232                         break;
 233                 case OCOPY:
 234                         n->left = copyany(n->left, &n->ninit, 1);
 235                         break;
 236                 default:
 237                         walkexpr(&n->left, &n->ninit);
 238                         break;
 239                 }
 240                 break;
 241
 242         case OFOR:
 243                 if(n->ntest != N) {
 244                         walkstmtlist(n->ntest->ninit);
 245                         init = n->ntest->ninit;
 246                         n->ntest->ninit = nil;
 247                         walkexpr(&n->ntest, &init);
 248                         addinit(&n->ntest, init);
 249                 }
 250                 walkstmt(&n->nincr);
 251                 walkstmtlist(n->nbody);
 252                 break;
 253
 254         case OIF:
 255                 walkexpr(&n->ntest, &n->ninit);
 256                 walkstmtlist(n->nbody);
 257                 walkstmtlist(n->nelse);
 258                 break;
 259
 260         case OPROC:
 261                 switch(n->left->op) {
 262                 case OPRINT:
 263                 case OPRINTN:
 264                         walkprintfunc(&n->left, &n->ninit);
 265                         break;
 266                 case OCOPY:
 267                         n->left = copyany(n->left, &n->ninit, 1);
 268                         break;
 269                 default:
 270                         walkexpr(&n->left, &n->ninit);
 271                         break;
 272                 }
 273                 break;
 274
 275         case ORETURN:
 276                 walkexprlist(n->list, &n->ninit);
 277                 if(n->list == nil)
 278                         break;
 279                 if((curfn->type->outnamed && count(n->list) > 1) || paramoutheap(curfn)) {
 280                         // assign to the function out parameters,
 281                         // so that reorder3 can fix up conflicts
 282                         rl = nil;
 283                         for(ll=curfn->dcl; ll != nil; ll=ll->next) {
 284                                 cl = ll->n->class & ~PHEAP;
 285                                 if(cl == PAUTO)
 286                                         break;
 287                                 if(cl == PPARAMOUT)
 288                                         rl = list(rl, ll->n);
 289                         }
 290                         if(samelist(rl, n->list)) {
 291                                 // special return in disguise
 292                                 n->list = nil;
 293                                 break;
 294                         }
 295                         if(count(n->list) == 1 && count(rl) > 1) {
 296                                 // OAS2FUNC in disguise
 297                                 f = n->list->n;
 298                                 if(f->op != OCALLFUNC && f->op != OCALLMETH && f->op != OCALLINTER)
 299                                         fatal("expected return of call, have %N", f);
 300                                 n->list = concat(list1(f), ascompatet(n->op, rl, &f->type, 0, &n->ninit));
 301                                 break;
 302                         }
 303
 304                         // move function calls out, to make reorder3's job easier.
 305                         walkexprlistsafe(n->list, &n->ninit);
 306                         ll = ascompatee(n->op, rl, n->list, &n->ninit);
 307                         n->list = reorder3(ll);
 308                         break;
 309                 }
 310                 ll = ascompatte(n->op, nil, 0, getoutarg(curfn->type), n->list, 1, &n->ninit);
 311                 n->list = ll;
 312                 break;
 313
 314         case ORETJMP:
 315                 break;
 316
 317         case OSELECT:
 318                 walkselect(n);
 319                 break;
 320
 321         case OSWITCH:
 322                 walkswitch(n);
 323                 break;
 324
 325         case ORANGE:
 326                 walkrange(n);
 327                 break;
 328
 329         case OXFALL:
 330                 yyerror("fallthrough statement out of place");
 331                 n->op = OFALL;
 332                 break;
 333         }
 334
 335         if(n->op == ONAME)
 336                 fatal("walkstmt ended up with name: %+N", n);
 337
 338         *np = n;
 339 }
 340
 341
 342 /*
 343  * walk the whole tree of the body of an
 344  * expression or simple statement.
 345  * the types expressions are calculated.
 346  * compile-time constants are evaluated.
 347  * complex side effects like statements are appended to init
 348  */
 349
 350 void
 351 walkexprlist(NodeList *l, NodeList **init)
 352 {
 353         for(; l; l=l->next)
 354                 walkexpr(&l->n, init);
 355 }
 356
 357 void
 358 walkexprlistsafe(NodeList *l, NodeList **init)
 359 {
 360         for(; l; l=l->next) {
 361                 l->n = safeexpr(l->n, init);
 362                 walkexpr(&l->n, init);
 363         }
 364 }
 365
 366 void
 367 walkexprlistcheap(NodeList *l, NodeList **init)
 368 {
 369         for(; l; l=l->next) {
 370                 l->n = cheapexpr(l->n, init);
 371                 walkexpr(&l->n, init);
 372         }
 373 }
 374
 375 void
 376 walkexpr(Node **np, NodeList **init)
 377 {
 378         Node *r, *l, *var, *a;
 379         Node *map, *key;
 380         NodeList *ll, *lr;
 381         Type *t;
 382         int et, old_safemode;
 383         int64 v;
 384         int32 lno;
 385         Node *n, *fn, *n1, *n2;
 386         Sym *sym;
 387         char buf[100], *p;
 388
 389         n = *np;
 390
 391         if(n == N)
 392                 return;
 393
 394         if(init == &n->ninit) {
 395                 // not okay to use n->ninit when walking n,
 396                 // because we might replace n with some other node
 397                 // and would lose the init list.
 398                 fatal("walkexpr init == &n->ninit");
 399         }
 400
 401         if(n->ninit != nil) {
 402                 walkstmtlist(n->ninit);
 403                 *init = concat(*init, n->ninit);
 404                 n->ninit = nil;
 405         }
 406
 407         // annoying case - not typechecked
 408         if(n->op == OKEY) {
 409                 walkexpr(&n->left, init);
 410                 walkexpr(&n->right, init);
 411                 return;
 412         }
 413
 414         lno = setlineno(n);
 415
 416         if(debug['w'] > 1)
 417                 dump("walk-before", n);
 418
 419         if(n->typecheck != 1)
 420                 fatal("missed typecheck: %+N\n", n);
 421
 422         switch(n->op) {
 423         default:
 424                 dump("walk", n);
 425                 fatal("walkexpr: switch 1 unknown op %+hN", n);
 426                 break;
 427
 428         case OTYPE:
 429         case ONONAME:
 430         case OINDREG:
 431         case OEMPTY:
 432                 goto ret;
 433
 434         case ONOT:
 435         case OMINUS:
 436         case OPLUS:
 437         case OCOM:
 438         case OREAL:
 439         case OIMAG:
 440         case ODOTMETH:
 441         case ODOTINTER:
 442                 walkexpr(&n->left, init);
 443                 goto ret;
 444
 445         case OIND:
 446                 walkexpr(&n->left, init);
 447                 goto ret;
 448
 449         case ODOT:
 450                 usefield(n);
 451                 walkexpr(&n->left, init);
 452                 goto ret;
 453
 454         case ODOTPTR:
 455                 usefield(n);
 456                 if(n->op == ODOTPTR && n->left->type->type->width == 0) {
 457                         // No actual copy will be generated, so emit an explicit nil check.
 458                         n->left = cheapexpr(n->left, init);
 459                         checknil(n->left, init);
 460                 }
 461                 walkexpr(&n->left, init);
 462                 goto ret;
 463
 464         case OEFACE:
 465                 walkexpr(&n->left, init);
 466                 walkexpr(&n->right, init);
 467                 goto ret;
 468
 469         case OSPTR:
 470         case OITAB:
 471                 walkexpr(&n->left, init);
 472                 goto ret;
 473
 474         case OLEN:
 475         case OCAP:
 476                 walkexpr(&n->left, init);
 477
 478                 // replace len(*[10]int) with 10.
 479                 // delayed until now to preserve side effects.
 480                 t = n->left->type;
 481                 if(isptr[t->etype])
 482                         t = t->type;
 483                 if(isfixedarray(t)) {
 484                         safeexpr(n->left, init);
 485                         nodconst(n, n->type, t->bound);
 486                         n->typecheck = 1;
 487                 }
 488                 goto ret;
 489
 490         case OLSH:
 491         case ORSH:
 492                 walkexpr(&n->left, init);
 493                 walkexpr(&n->right, init);
 494                 t = n->left->type;
 495                 n->bounded = bounded(n->right, 8*t->width);
 496                 if(debug['m'] && n->etype && !isconst(n->right, CTINT))
 497                         warn("shift bounds check elided");
 498                 goto ret;
 499
 500         case OAND:
 501         case OSUB:
 502         case OHMUL:
 503         case OLT:
 504         case OLE:
 505         case OGE:
 506         case OGT:
 507         case OADD:
 508         case OCOMPLEX:
 509         case OLROT:
 510                 // Use results from call expression as arguments for complex.
 511                 if(n->op == OCOMPLEX && n->left == N && n->right == N) {
 512                         n->left = n->list->n;
 513                         n->right = n->list->next->n;
 514                 }
 515                 walkexpr(&n->left, init);
 516                 walkexpr(&n->right, init);
 517                 goto ret;
 518
 519         case OOR:
 520         case OXOR:
 521                 walkexpr(&n->left, init);
 522                 walkexpr(&n->right, init);
 523                 walkrotate(&n);
 524                 goto ret;
 525
 526         case OEQ:
 527         case ONE:
 528                 walkexpr(&n->left, init);
 529                 walkexpr(&n->right, init);
 530                 // Disable safemode while compiling this code: the code we
 531                 // generate internally can refer to unsafe.Pointer.
 532                 // In this case it can happen if we need to generate an ==
 533                 // for a struct containing a reflect.Value, which itself has
 534                 // an unexported field of type unsafe.Pointer.
 535                 old_safemode = safemode;
 536                 safemode = 0;
 537                 walkcompare(&n, init);
 538                 safemode = old_safemode;
 539                 goto ret;
 540
 541         case OANDAND:
 542         case OOROR:
 543                 walkexpr(&n->left, init);
 544                 // cannot put side effects from n->right on init,
 545                 // because they cannot run before n->left is checked.
 546                 // save elsewhere and store on the eventual n->right.
 547                 ll = nil;
 548                 walkexpr(&n->right, &ll);
 549                 addinit(&n->right, ll);
 550                 goto ret;
 551
 552         case OPRINT:
 553         case OPRINTN:
 554                 walkexprlist(n->list, init);
 555                 n = walkprint(n, init);
 556                 goto ret;
 557
 558         case OPANIC:
 559                 n = mkcall("gopanic", T, init, n->left);
 560                 goto ret;
 561
 562         case ORECOVER:
 563                 n = mkcall("gorecover", n->type, init, nod(OADDR, nodfp, N));
 564                 goto ret;
 565
 566         case OLITERAL:
 567                 n->addable = 1;
 568                 goto ret;
 569
 570         case OCLOSUREVAR:
 571         case OCFUNC:
 572                 n->addable = 1;
 573                 goto ret;
 574
 575         case ONAME:
 576                 if(!(n->class & PHEAP) && n->class != PPARAMREF)
 577                         n->addable = 1;
 578                 goto ret;
 579
 580         case OCALLINTER:
 581                 t = n->left->type;
 582                 if(n->list && n->list->n->op == OAS)
 583                         goto ret;
 584                 walkexpr(&n->left, init);
 585                 walkexprlist(n->list, init);
 586                 ll = ascompatte(n->op, n, n->isddd, getinarg(t), n->list, 0, init);
 587                 n->list = reorder1(ll);
 588                 goto ret;
 589
 590         case OCALLFUNC:
 591                 t = n->left->type;
 592                 if(n->list && n->list->n->op == OAS)
 593                         goto ret;
 594
 595                 walkexpr(&n->left, init);
 596                 walkexprlist(n->list, init);
 597
 598                 ll = ascompatte(n->op, n, n->isddd, getinarg(t), n->list, 0, init);
 599                 n->list = reorder1(ll);
 600                 goto ret;
 601
 602         case OCALLMETH:
 603                 t = n->left->type;
 604                 if(n->list && n->list->n->op == OAS)
 605                         goto ret;
 606                 walkexpr(&n->left, init);
 607                 walkexprlist(n->list, init);
 608                 ll = ascompatte(n->op, n, 0, getthis(t), list1(n->left->left), 0, init);
 609                 lr = ascompatte(n->op, n, n->isddd, getinarg(t), n->list, 0, init);
 610                 ll = concat(ll, lr);
 611                 n->left->left = N;
 612                 ullmancalc(n->left);
 613                 n->list = reorder1(ll);
 614                 goto ret;
 615
 616         case OAS:
 617                 *init = concat(*init, n->ninit);
 618                 n->ninit = nil;
 619
 620                 walkexpr(&n->left, init);
 621                 n->left = safeexpr(n->left, init);
 622
 623                 if(oaslit(n, init))
 624                         goto ret;
 625
 626                 if(n->right == N || iszero(n->right) && !flag_race)
 627                         goto ret;
 628
 629                 switch(n->right->op) {
 630                 default:
 631                         walkexpr(&n->right, init);
 632                         break;
 633
 634                 case ORECV:
 635                         // x = <-c; n->left is x, n->right->left is c.
 636                         // orderstmt made sure x is addressable.
 637                         walkexpr(&n->right->left, init);
 638                         n1 = nod(OADDR, n->left, N);
 639                         r = n->right->left; // the channel
 640                         n = mkcall1(chanfn("chanrecv1", 2, r->type), T, init, typename(r->type), r, n1);
 641                         walkexpr(&n, init);
 642                         goto ret;
 643                 }
 644
 645                 if(n->left != N && n->right != N) {
 646                         r = convas(nod(OAS, n->left, n->right), init);
 647                         r->dodata = n->dodata;
 648                         n = r;
 649                         n = applywritebarrier(n, init);
 650                 }
 651
 652                 goto ret;
 653
 654         case OAS2:
 655                 *init = concat(*init, n->ninit);
 656                 n->ninit = nil;
 657                 walkexprlistsafe(n->list, init);
 658                 walkexprlistsafe(n->rlist, init);
 659                 ll = ascompatee(OAS, n->list, n->rlist, init);
 660                 ll = reorder3(ll);
 661                 for(lr = ll; lr != nil; lr = lr->next)
 662                         lr->n = applywritebarrier(lr->n, init);
 663                 n = liststmt(ll);
 664                 goto ret;
 665
 666         case OAS2FUNC:
 667                 // a,b,... = fn()
 668                 *init = concat(*init, n->ninit);
 669                 n->ninit = nil;
 670                 r = n->rlist->n;
 671                 walkexprlistsafe(n->list, init);
 672                 walkexpr(&r, init);
 673
 674                 ll = ascompatet(n->op, n->list, &r->type, 0, init);
 675                 for(lr = ll; lr != nil; lr = lr->next)
 676                         lr->n = applywritebarrier(lr->n, init);
 677                 n = liststmt(concat(list1(r), ll));
 678                 goto ret;
 679
 680         case OAS2RECV:
 681                 // x, y = <-c
 682                 // orderstmt made sure x is addressable.
 683                 *init = concat(*init, n->ninit);
 684                 n->ninit = nil;
 685                 r = n->rlist->n;
 686                 walkexprlistsafe(n->list, init);
 687                 walkexpr(&r->left, init);
 688                 if(isblank(n->list->n))
 689                         n1 = nodnil();
 690                 else
 691                         n1 = nod(OADDR, n->list->n, N);
 692                 n1->etype = 1; // addr does not escape
 693                 fn = chanfn("chanrecv2", 2, r->left->type);
 694                 r = mkcall1(fn, n->list->next->n->type, init, typename(r->left->type), r->left, n1);
 695                 n = nod(OAS, n->list->next->n, r);
 696                 typecheck(&n, Etop);
 697                 goto ret;
 698
 699         case OAS2MAPR:
 700                 // a,b = m[i];
 701                 *init = concat(*init, n->ninit);
 702                 n->ninit = nil;
 703                 r = n->rlist->n;
 704                 walkexprlistsafe(n->list, init);
 705                 walkexpr(&r->left, init);
 706                 walkexpr(&r->right, init);
 707                 t = r->left->type;
 708                 p = nil;
 709                 if(t->type->width <= 128) { // Check ../../runtime/hashmap.c:MAXVALUESIZE before changing.
 710                         switch(simsimtype(t->down)) {
 711                         case TINT32:
 712                         case TUINT32:
 713                                 p = "mapaccess2_fast32";
 714                                 break;
 715                         case TINT64:
 716                         case TUINT64:
 717                                 p = "mapaccess2_fast64";
 718                                 break;
 719                         case TSTRING:
 720                                 p = "mapaccess2_faststr";
 721                                 break;
 722                         }
 723                 }
 724                 if(p != nil) {
 725                         // fast versions take key by value
 726                         key = r->right;
 727                 } else {
 728                         // standard version takes key by reference
 729                         // orderexpr made sure key is addressable.
 730                         key = nod(OADDR, r->right, N);
 731                         p = "mapaccess2";
 732                 }
 733
 734                 // from:
 735                 //   a,b = m[i]
 736                 // to:
 737                 //   var,b = mapaccess2*(t, m, i)
 738                 //   a = *var
 739                 a = n->list->n;
 740                 var = temp(ptrto(t->type));
 741                 var->typecheck = 1;
 742                 fn = mapfn(p, t);
 743                 r = mkcall1(fn, getoutargx(fn->type), init, typename(t), r->left, key);
 744
 745                 // mapaccess2* returns a typed bool, but due to spec changes,
 746                 // the boolean result of i.(T) is now untyped so we make it the
 747                 // same type as the variable on the lhs.
 748                 if(!isblank(n->list->next->n))
 749                         r->type->type->down->type = n->list->next->n->type;
 750                 n->rlist = list1(r);
 751                 n->op = OAS2FUNC;
 752                 n->list->n = var;
 753                 walkexpr(&n, init);
 754                 *init = list(*init, n);
 755                 n = nod(OAS, a, nod(OIND, var, N));
 756                 typecheck(&n, Etop);
 757                 walkexpr(&n, init);
 758                 // mapaccess needs a zero value to be at least this big.
 759                 if(zerosize < t->type->width)
 760                         zerosize = t->type->width;
 761                 // TODO: ptr is always non-nil, so disable nil check for this OIND op.
 762                 goto ret;
 763
 764         case ODELETE:
 765                 *init = concat(*init, n->ninit);
 766                 n->ninit = nil;
 767                 map = n->list->n;
 768                 key = n->list->next->n;
 769                 walkexpr(&map, init);
 770                 walkexpr(&key, init);
 771                 // orderstmt made sure key is addressable.
 772                 key = nod(OADDR, key, N);
 773                 t = map->type;
 774                 n = mkcall1(mapfndel("mapdelete", t), T, init, typename(t), map, key);
 775                 goto ret;
 776
 777         case OAS2DOTTYPE:
 778                 // a,b = i.(T)
 779                 *init = concat(*init, n->ninit);
 780                 n->ninit = nil;
 781                 r = n->rlist->n;
 782                 walkexprlistsafe(n->list, init);
 783                 if(isblank(n->list->n) && !isinter(r->type)) {
 784                         strcpy(buf, "assert");
 785                         p = buf+strlen(buf);
 786                         if(isnilinter(r->left->type))
 787                                 *p++ = 'E';
 788                         else
 789                                 *p++ = 'I';
 790                         *p++ = '2';
 791                         *p++ = 'T';
 792                         *p++ = 'O';
 793                         *p++ = 'K';
 794                         *p = '\0';
 795
 796                         fn = syslook(buf, 1);
 797
 798                         // runtime.assert(E|I)2TOK returns a typed bool, but due
 799                         // to spec changes, the boolean result of i.(T) is now untyped
 800                         // so we make it the same type as the variable on the lhs.
 801                         if(!isblank(n->list->next->n))
 802                                 fn->type->type->down->type->type = n->list->next->n->type;
 803                         ll = list1(typename(r->type));
 804                         ll = list(ll, r->left);
 805                         argtype(fn, r->left->type);
 806                         n1 = nod(OCALL, fn, N);
 807                         n1->list = ll;
 808                         n = nod(OAS, n->list->next->n, n1);
 809                         typecheck(&n, Etop);
 810                         walkexpr(&n, init);
 811                         goto ret;
 812                 }
 813
 814                 r->op = ODOTTYPE2;
 815                 walkexpr(&r, init);
 816                 ll = ascompatet(n->op, n->list, &r->type, 0, init);
 817                 n = liststmt(concat(list1(r), ll));
 818                 goto ret;
 819
 820         case ODOTTYPE:
 821         case ODOTTYPE2:
 822                 // Build name of function: assertI2E2 etc.
 823                 strcpy(buf, "assert");
 824                 p = buf+strlen(buf);
 825                 if(isnilinter(n->left->type))
 826                         *p++ = 'E';
 827                 else
 828                         *p++ = 'I';
 829                 *p++ = '2';
 830                 if(isnilinter(n->type))
 831                         *p++ = 'E';
 832                 else if(isinter(n->type))
 833                         *p++ = 'I';
 834                 else
 835                         *p++ = 'T';
 836                 if(n->op == ODOTTYPE2)
 837                         *p++ = '2';
 838                 *p = '\0';
 839
 840                 fn = syslook(buf, 1);
 841                 ll = list1(typename(n->type));
 842                 ll = list(ll, n->left);
 843                 argtype(fn, n->left->type);
 844                 argtype(fn, n->type);
 845                 n = nod(OCALL, fn, N);
 846                 n->list = ll;
 847                 typecheck(&n, Erv | Efnstruct);
 848                 walkexpr(&n, init);
 849                 goto ret;
 850
 851         case OCONVIFACE:
 852                 walkexpr(&n->left, init);
 853
 854                 // Optimize convT2E as a two-word copy when T is uintptr-shaped.
 855                 if(isnilinter(n->type) && isdirectiface(n->left->type) && n->left->type->width == widthptr && isint[simsimtype(n->left->type)]) {
 856                         l = nod(OEFACE, typename(n->left->type), n->left);
 857                         l->type = n->type;
 858                         l->typecheck = n->typecheck;
 859                         n = l;
 860                         goto ret;
 861                 }
 862
 863                 // Build name of function: convI2E etc.
 864                 // Not all names are possible
 865                 // (e.g., we'll never generate convE2E or convE2I).
 866                 strcpy(buf, "conv");
 867                 p = buf+strlen(buf);
 868                 if(isnilinter(n->left->type))
 869                         *p++ = 'E';
 870                 else if(isinter(n->left->type))
 871                         *p++ = 'I';
 872                 else
 873                         *p++ = 'T';
 874                 *p++ = '2';
 875                 if(isnilinter(n->type))
 876                         *p++ = 'E';
 877                 else
 878                         *p++ = 'I';
 879                 *p = '\0';
 880
 881                 fn = syslook(buf, 1);
 882                 ll = nil;
 883                 if(!isinter(n->left->type))
 884                         ll = list(ll, typename(n->left->type));
 885                 if(!isnilinter(n->type))
 886                         ll = list(ll, typename(n->type));
 887                 if(!isinter(n->left->type) && !isnilinter(n->type)){
 888                         sym = pkglookup(smprint("%-T.%-T", n->left->type, n->type), itabpkg);
 889                         if(sym->def == N) {
 890                                 l = nod(ONAME, N, N);
 891                                 l->sym = sym;
 892                                 l->type = ptrto(types[TUINT8]);
 893                                 l->addable = 1;
 894                                 l->class = PEXTERN;
 895                                 l->xoffset = 0;
 896                                 sym->def = l;
 897                                 ggloblsym(sym, widthptr, DUPOK|NOPTR);
 898                         }
 899                         l = nod(OADDR, sym->def, N);
 900                         l->addable = 1;
 901                         ll = list(ll, l);
 902
 903                         if(isdirectiface(n->left->type) && n->left->type->width == widthptr && isint[simsimtype(n->left->type)]) {
 904                                 /* For pointer types, we can make a special form of optimization
 905                                  *
 906                                  * These statements are put onto the expression init list:
 907                                  *      Itab *tab = atomicloadtype(&cache);
 908                                  *      if(tab == nil)
 909                                  *              tab = typ2Itab(type, itype, &cache);
 910                                  *
 911                                  * The CONVIFACE expression is replaced with this:
 912                                  *      OEFACE{tab, ptr};
 913                                  */
 914                                 l = temp(ptrto(types[TUINT8]));
 915
 916                                 n1 = nod(OAS, l, sym->def);
 917                                 typecheck(&n1, Etop);
 918                                 *init = list(*init, n1);
 919
 920                                 fn = syslook("typ2Itab", 1);
 921                                 n1 = nod(OCALL, fn, N);
 922                                 n1->list = ll;
 923                                 typecheck(&n1, Erv);
 924                                 walkexpr(&n1, init);
 925
 926                                 n2 = nod(OIF, N, N);
 927                                 n2->ntest = nod(OEQ, l, nodnil());
 928                                 n2->nbody = list1(nod(OAS, l, n1));
 929                                 n2->likely = -1;
 930                                 typecheck(&n2, Etop);
 931                                 *init = list(*init, n2);
 932
 933                                 l = nod(OEFACE, l, n->left);
 934                                 l->typecheck = n->typecheck;
 935                                 l->type = n->type;
 936                                 n = l;
 937                                 goto ret;
 938                         }
 939                 }
 940                 if(isinter(n->left->type)) {
 941                         ll = list(ll, n->left);
 942                 } else {
 943                         // regular types are passed by reference to avoid C vararg calls
 944                         // orderexpr arranged for n->left to be a temporary for all
 945                         // the conversions it could see. comparison of an interface
 946                         // with a non-interface, especially in a switch on interface value
 947                         // with non-interface cases, is not visible to orderstmt, so we
 948                         // have to fall back on allocating a temp here.
 949                         if(islvalue(n->left))
 950                                 ll = list(ll, nod(OADDR, n->left, N));
 951                         else
 952                                 ll = list(ll, nod(OADDR, copyexpr(n->left, n->left->type, init), N));
 953                 }
 954                 argtype(fn, n->left->type);
 955                 argtype(fn, n->type);
 956                 dowidth(fn->type);
 957                 n = nod(OCALL, fn, N);
 958                 n->list = ll;
 959                 typecheck(&n, Erv);
 960                 walkexpr(&n, init);
 961                 goto ret;
 962
 963         case OCONV:
 964         case OCONVNOP:
 965                 if(thechar == '5') {
 966                         if(isfloat[n->left->type->etype]) {
 967                                 if(n->type->etype == TINT64) {
 968                                         n = mkcall("float64toint64", n->type, init, conv(n->left, types[TFLOAT64]));
 969                                         goto ret;
 970                                 }
 971                                 if(n->type->etype == TUINT64) {
 972                                         n = mkcall("float64touint64", n->type, init, conv(n->left, types[TFLOAT64]));
 973                                         goto ret;
 974                                 }
 975                         }
 976                         if(isfloat[n->type->etype]) {
 977                                 if(n->left->type->etype == TINT64) {
 978                                         n = mkcall("int64tofloat64", n->type, init, conv(n->left, types[TINT64]));
 979                                         goto ret;
 980                                 }
 981                                 if(n->left->type->etype == TUINT64) {
 982                                         n = mkcall("uint64tofloat64", n->type, init, conv(n->left, types[TUINT64]));
 983                                         goto ret;
 984                                 }
 985                         }
 986                 }
 987                 walkexpr(&n->left, init);
 988                 goto ret;
 989
 990         case OANDNOT:
 991                 walkexpr(&n->left, init);
 992                 n->op = OAND;
 993                 n->right = nod(OCOM, n->right, N);
 994                 typecheck(&n->right, Erv);
 995                 walkexpr(&n->right, init);
 996                 goto ret;
 997
 998         case OMUL:
 999                 walkexpr(&n->left, init);
1000                 walkexpr(&n->right, init);
1001                 walkmul(&n, init);
1002                 goto ret;
1003
1004         case ODIV:
1005         case OMOD:
1006                 walkexpr(&n->left, init);
1007                 walkexpr(&n->right, init);
1008                 /*
1009                  * rewrite complex div into function call.
1010                  */
1011                 et = n->left->type->etype;
1012                 if(iscomplex[et] && n->op == ODIV) {
1013                         t = n->type;
1014                         n = mkcall("complex128div", types[TCOMPLEX128], init,
1015                                 conv(n->left, types[TCOMPLEX128]),
1016                                 conv(n->right, types[TCOMPLEX128]));
1017                         n = conv(n, t);
1018                         goto ret;
1019                 }
1020                 // Nothing to do for float divisions.
1021                 if(isfloat[et])
1022                         goto ret;
1023
1024                 // Try rewriting as shifts or magic multiplies.
1025                 walkdiv(&n, init);
1026
1027                 /*
1028                  * rewrite 64-bit div and mod into function calls
1029                  * on 32-bit architectures.
1030                  */
1031                 switch(n->op) {
1032                 case OMOD:
1033                 case ODIV:
1034                         if(widthreg >= 8 || (et != TUINT64 && et != TINT64))
1035                                 goto ret;
1036                         if(et == TINT64)
1037                                 strcpy(namebuf, "int64");
1038                         else
1039                                 strcpy(namebuf, "uint64");
1040                         if(n->op == ODIV)
1041                                 strcat(namebuf, "div");
1042                         else
1043                                 strcat(namebuf, "mod");
1044                         n = mkcall(namebuf, n->type, init,
1045                                 conv(n->left, types[et]), conv(n->right, types[et]));
1046                         break;
1047                 default:
1048                         break;
1049                 }
1050                 goto ret;
1051
1052         case OINDEX:
1053                 walkexpr(&n->left, init);
1054                 // save the original node for bounds checking elision.
1055                 // If it was a ODIV/OMOD walk might rewrite it.
1056                 r = n->right;
1057                 walkexpr(&n->right, init);
1058
1059                 // if range of type cannot exceed static array bound,
1060                 // disable bounds check.
1061                 if(n->bounded)
1062                         goto ret;
1063                 t = n->left->type;
1064                 if(t != T && isptr[t->etype])
1065                         t = t->type;
1066                 if(isfixedarray(t)) {
1067                         n->bounded = bounded(r, t->bound);
1068                         if(debug['m'] && n->bounded && !isconst(n->right, CTINT))
1069                                 warn("index bounds check elided");
1070                         if(smallintconst(n->right) && !n->bounded)
1071                                 yyerror("index out of bounds");
1072                 } else if(isconst(n->left, CTSTR)) {
1073                         n->bounded = bounded(r, n->left->val.u.sval->len);
1074                         if(debug['m'] && n->bounded && !isconst(n->right, CTINT))
1075                                 warn("index bounds check elided");
1076                         if(smallintconst(n->right)) {
1077                                 if(!n->bounded)
1078                                         yyerror("index out of bounds");
1079                                 else {
1080                                         // replace "abc"[1] with 'b'.
1081                                         // delayed until now because "abc"[1] is not
1082                                         // an ideal constant.
1083                                         v = mpgetfix(n->right->val.u.xval);
1084                                         nodconst(n, n->type, n->left->val.u.sval->s[v]);
1085                                         n->typecheck = 1;
1086                                 }
1087                         }
1088                 }
1089
1090                 if(isconst(n->right, CTINT))
1091                 if(mpcmpfixfix(n->right->val.u.xval, &mpzero) < 0 ||
1092                    mpcmpfixfix(n->right->val.u.xval, maxintval[TINT]) > 0)
1093                         yyerror("index out of bounds");
1094                 goto ret;
1095
1096         case OINDEXMAP:
1097                 if(n->etype == 1)
1098                         goto ret;
1099                 walkexpr(&n->left, init);
1100                 walkexpr(&n->right, init);
1101
1102                 t = n->left->type;
1103                 p = nil;
1104                 if(t->type->width <= 128) {  // Check ../../runtime/hashmap.c:MAXVALUESIZE before changing.
1105                         switch(simsimtype(t->down)) {
1106                         case TINT32:
1107                         case TUINT32:
1108                                 p = "mapaccess1_fast32";
1109                                 break;
1110                         case TINT64:
1111                         case TUINT64:
1112                                 p = "mapaccess1_fast64";
1113                                 break;
1114                         case TSTRING:
1115                                 p = "mapaccess1_faststr";
1116                                 break;
1117                         }
1118                 }
1119                 if(p != nil) {
1120                         // fast versions take key by value
1121                         key = n->right;
1122                 } else {
1123                         // standard version takes key by reference.
1124                         // orderexpr made sure key is addressable.
1125                         key = nod(OADDR, n->right, N);
1126                         p = "mapaccess1";
1127                 }
1128                 n = mkcall1(mapfn(p, t), ptrto(t->type), init, typename(t), n->left, key);
1129                 n = nod(OIND, n, N);
1130                 n->type = t->type;
1131                 n->typecheck = 1;
1132                 // mapaccess needs a zero value to be at least this big.
1133                 if(zerosize < t->type->width)
1134                         zerosize = t->type->width;
1135                 goto ret;
1136
1137         case ORECV:
1138                 fatal("walkexpr ORECV"); // should see inside OAS only
1139
1140         case OSLICE:
1141                 if(n->right != N && n->right->left == N && n->right->right == N) { // noop
1142                         walkexpr(&n->left, init);
1143                         n = n->left;
1144                         goto ret;
1145                 }
1146                 // fallthrough
1147         case OSLICEARR:
1148         case OSLICESTR:
1149                 if(n->right == N) // already processed
1150                         goto ret;
1151
1152                 walkexpr(&n->left, init);
1153                 // cgen_slice can't handle string literals as source
1154                 // TODO the OINDEX case is a bug elsewhere that needs to be traced.  it causes a crash on ([2][]int{ ... })[1][lo:hi]
1155                 if((n->op == OSLICESTR && n->left->op == OLITERAL) || (n->left->op == OINDEX))
1156                         n->left = copyexpr(n->left, n->left->type, init);
1157                 else
1158                         n->left = safeexpr(n->left, init);
1159                 walkexpr(&n->right->left, init);
1160                 n->right->left = safeexpr(n->right->left, init);
1161                 walkexpr(&n->right->right, init);
1162                 n->right->right = safeexpr(n->right->right, init);
1163                 n = sliceany(n, init);  // chops n->right, sets n->list
1164                 goto ret;
1165
1166         case OSLICE3:
1167         case OSLICE3ARR:
1168                 if(n->right == N) // already processed
1169                         goto ret;
1170
1171                 walkexpr(&n->left, init);
1172                 // TODO the OINDEX case is a bug elsewhere that needs to be traced.  it causes a crash on ([2][]int{ ... })[1][lo:hi]
1173                 // TODO the comment on the previous line was copied from case OSLICE. it might not even be true.
1174                 if(n->left->op == OINDEX)
1175                         n->left = copyexpr(n->left, n->left->type, init);
1176                 else
1177                         n->left = safeexpr(n->left, init);
1178                 walkexpr(&n->right->left, init);
1179                 n->right->left = safeexpr(n->right->left, init);
1180                 walkexpr(&n->right->right->left, init);
1181                 n->right->right->left = safeexpr(n->right->right->left, init);
1182                 walkexpr(&n->right->right->right, init);
1183                 n->right->right->right = safeexpr(n->right->right->right, init);
1184                 n = sliceany(n, init);  // chops n->right, sets n->list
1185                 goto ret;
1186
1187         case OADDR:
1188                 walkexpr(&n->left, init);
1189                 goto ret;
1190
1191         case ONEW:
1192                 if(n->esc == EscNone && n->type->type->width < (1<<16)) {
1193                         r = temp(n->type->type);
1194                         r = nod(OAS, r, N);  // zero temp
1195                         typecheck(&r, Etop);
1196                         *init = list(*init, r);
1197                         r = nod(OADDR, r->left, N);
1198                         typecheck(&r, Erv);
1199                         n = r;
1200                 } else {
1201                         n = callnew(n->type->type);
1202                 }
1203                 goto ret;
1204
1205         case OCMPSTR:
1206                 // If one argument to the comparison is an empty string,
1207                 // comparing the lengths instead will yield the same result
1208                 // without the function call.
1209                 if((isconst(n->left, CTSTR) && n->left->val.u.sval->len == 0) ||
1210                    (isconst(n->right, CTSTR) && n->right->val.u.sval->len == 0)) {
1211                         r = nod(n->etype, nod(OLEN, n->left, N), nod(OLEN, n->right, N));
1212                         typecheck(&r, Erv);
1213                         walkexpr(&r, init);
1214                         r->type = n->type;
1215                         n = r;
1216                         goto ret;
1217                 }
1218
1219                 // s + "badgerbadgerbadger" == "badgerbadgerbadger"
1220                 if((n->etype == OEQ || n->etype == ONE) &&
1221                    isconst(n->right, CTSTR) &&
1222                    n->left->op == OADDSTR && count(n->left->list) == 2 &&
1223                    isconst(n->left->list->next->n, CTSTR) &&
1224                    cmpslit(n->right, n->left->list->next->n) == 0) {
1225                         r = nod(n->etype, nod(OLEN, n->left->list->n, N), nodintconst(0));
1226                         typecheck(&r, Erv);
1227                         walkexpr(&r, init);
1228                         r->type = n->type;
1229                         n = r;
1230                         goto ret;
1231                 }
1232
1233                 if(n->etype == OEQ || n->etype == ONE) {
1234                         // prepare for rewrite below
1235                         n->left = cheapexpr(n->left, init);
1236                         n->right = cheapexpr(n->right, init);
1237
1238                         r = mkcall("eqstring", types[TBOOL], init,
1239                                 conv(n->left, types[TSTRING]),
1240                                 conv(n->right, types[TSTRING]));
1241
1242                         // quick check of len before full compare for == or !=
1243                         if(n->etype == OEQ) {
1244                                 // len(left) == len(right) && eqstring(left, right)
1245                                 r = nod(OANDAND, nod(OEQ, nod(OLEN, n->left, N), nod(OLEN, n->right, N)), r);
1246                         } else {
1247                                 // len(left) != len(right) || !eqstring(left, right)
1248                                 r = nod(ONOT, r, N);
1249                                 r = nod(OOROR, nod(ONE, nod(OLEN, n->left, N), nod(OLEN, n->right, N)), r);
1250                         }
1251                         typecheck(&r, Erv);
1252                         walkexpr(&r, nil);
1253                 } else {
1254                         // sys_cmpstring(s1, s2) :: 0
1255                         r = mkcall("cmpstring", types[TINT], init,
1256                                 conv(n->left, types[TSTRING]),
1257                                 conv(n->right, types[TSTRING]));
1258                         r = nod(n->etype, r, nodintconst(0));
1259                 }
1260
1261                 typecheck(&r, Erv);
1262                 if(n->type->etype != TBOOL) fatal("cmp %T", n->type);
1263                 r->type = n->type;
1264                 n = r;
1265                 goto ret;
1266
1267         case OADDSTR:
1268                 n = addstr(n, init);
1269                 goto ret;
1270
1271         case OAPPEND:
1272                 if(n->isddd)
1273                         n = appendslice(n, init); // also works for append(slice, string).
1274                 else
1275                         n = append(n, init);
1276                 goto ret;
1277
1278         case OCOPY:
1279                 n = copyany(n, init, flag_race);
1280                 goto ret;
1281
1282         case OCLOSE:
1283                 // cannot use chanfn - closechan takes any, not chan any
1284                 fn = syslook("closechan", 1);
1285                 argtype(fn, n->left->type);
1286                 n = mkcall1(fn, T, init, n->left);
1287                 goto ret;
1288
1289         case OMAKECHAN:
1290                 n = mkcall1(chanfn("makechan", 1, n->type), n->type, init,
1291                         typename(n->type),
1292                         conv(n->left, types[TINT64]));
1293                 goto ret;
1294
1295         case OMAKEMAP:
1296                 t = n->type;
1297
1298                 fn = syslook("makemap", 1);
1299                 argtype(fn, t->down);   // any-1
1300                 argtype(fn, t->type);   // any-2
1301
1302                 n = mkcall1(fn, n->type, init,
1303                         typename(n->type),
1304                         conv(n->left, types[TINT64]));
1305                 goto ret;
1306
1307         case OMAKESLICE:
1308                 l = n->left;
1309                 r = n->right;
1310                 if(r == nil)
1311                         l = r = safeexpr(l, init);
1312                 t = n->type;
1313                 if(n->esc == EscNone
1314                         && smallintconst(l) && smallintconst(r)
1315                         && (t->type->width == 0 || mpgetfix(r->val.u.xval) < (1ULL<<16) / t->type->width)) {
1316                         // var arr [r]T
1317                         // n = arr[:l]
1318                         t = aindex(r, t->type); // [r]T
1319                         var = temp(t);
1320                         a = nod(OAS, var, N); // zero temp
1321                         typecheck(&a, Etop);
1322                         *init = list(*init, a);
1323                         r = nod(OSLICE, var, nod(OKEY, N, l)); // arr[:l]
1324                         r = conv(r, n->type); // in case n->type is named.
1325                         typecheck(&r, Erv);
1326                         walkexpr(&r, init);
1327                         n = r;
1328                 } else {
1329                         // makeslice(t *Type, nel int64, max int64) (ary []any)
1330                         fn = syslook("makeslice", 1);
1331                         argtype(fn, t->type);                   // any-1
1332                         n = mkcall1(fn, n->type, init,
1333                                 typename(n->type),
1334                                 conv(l, types[TINT64]),
1335                                 conv(r, types[TINT64]));
1336                 }
1337                 goto ret;
1338
1339         case ORUNESTR:
1340                 // sys_intstring(v)
1341                 n = mkcall("intstring", n->type, init,
1342                         conv(n->left, types[TINT64]));
1343                 goto ret;
1344
1345         case OARRAYBYTESTR:
1346                 // slicebytetostring([]byte) string;
1347                 n = mkcall("slicebytetostring", n->type, init, n->left);
1348                 goto ret;
1349
1350         case OARRAYBYTESTRTMP:
1351                 // slicebytetostringtmp([]byte) string;
1352                 n = mkcall("slicebytetostringtmp", n->type, init, n->left);
1353                 goto ret;
1354
1355         case OARRAYRUNESTR:
1356                 // slicerunetostring([]rune) string;
1357                 n = mkcall("slicerunetostring", n->type, init, n->left);
1358                 goto ret;
1359
1360         case OSTRARRAYBYTE:
1361                 // stringtoslicebyte(string) []byte;
1362                 n = mkcall("stringtoslicebyte", n->type, init, conv(n->left, types[TSTRING]));
1363                 goto ret;
1364
1365         case OSTRARRAYRUNE:
1366                 // stringtoslicerune(string) []rune
1367                 n = mkcall("stringtoslicerune", n->type, init, n->left);
1368                 goto ret;
1369
1370         case OCMPIFACE:
1371                 // ifaceeq(i1 any-1, i2 any-2) (ret bool);
1372                 if(!eqtype(n->left->type, n->right->type))
1373                         fatal("ifaceeq %O %T %T", n->op, n->left->type, n->right->type);
1374                 if(isnilinter(n->left->type))
1375                         fn = syslook("efaceeq", 1);
1376                 else
1377                         fn = syslook("ifaceeq", 1);
1378
1379                 n->right = cheapexpr(n->right, init);
1380                 n->left = cheapexpr(n->left, init);
1381                 argtype(fn, n->right->type);
1382                 argtype(fn, n->left->type);
1383                 r = mkcall1(fn, n->type, init, n->left, n->right);
1384                 if(n->etype == ONE)
1385                         r = nod(ONOT, r, N);
1386
1387                 // check itable/type before full compare.
1388                 if(n->etype == OEQ)
1389                         r = nod(OANDAND, nod(OEQ, nod(OITAB, n->left, N), nod(OITAB, n->right, N)), r);
1390                 else
1391                         r = nod(OOROR, nod(ONE, nod(OITAB, n->left, N), nod(OITAB, n->right, N)), r);
1392                 typecheck(&r, Erv);
1393                 walkexpr(&r, init);
1394                 r->type = n->type;
1395                 n = r;
1396                 goto ret;
1397
1398         case OARRAYLIT:
1399         case OMAPLIT:
1400         case OSTRUCTLIT:
1401         case OPTRLIT:
1402                 var = temp(n->type);
1403                 anylit(0, n, var, init);
1404                 n = var;
1405                 goto ret;
1406
1407         case OSEND:
1408                 n1 = n->right;
1409                 n1 = assignconv(n1, n->left->type->type, "chan send");
1410                 walkexpr(&n1, init);
1411                 n1 = nod(OADDR, n1, N);
1412                 n = mkcall1(chanfn("chansend1", 2, n->left->type), T, init, typename(n->left->type), n->left, n1);
1413                 goto ret;
1414
1415         case OCLOSURE:
1416                 n = walkclosure(n, init);
1417                 goto ret;
1418
1419         case OCALLPART:
1420                 n = walkpartialcall(n, init);
1421                 goto ret;
1422         }
1423         fatal("missing switch %O", n->op);
1424
1425 ret:
1426         // Expressions that are constant at run time but not
1427         // considered const by the language spec are not turned into
1428         // constants until walk. For example, if n is y%1 == 0, the
1429         // walk of y%1 may have replaced it by 0.
1430         // Check whether n with its updated args is itself now a constant.
1431         t = n->type;
1432         evconst(n);
1433         n->type = t;
1434         if(n->op == OLITERAL)
1435                 typecheck(&n, Erv);
1436
1437         ullmancalc(n);
1438
1439         if(debug['w'] && n != N)
1440                 dump("walk", n);
1441
1442         lineno = lno;
1443         *np = n;
1444 }
1445
1446 static Node*
1447 ascompatee1(int op, Node *l, Node *r, NodeList **init)
1448 {
1449         Node *n;
1450         USED(op);
1451
1452         // convas will turn map assigns into function calls,
1453         // making it impossible for reorder3 to work.
1454         n = nod(OAS, l, r);
1455         if(l->op == OINDEXMAP)
1456                 return n;
1457
1458         return convas(n, init);
1459 }
1460
1461 static NodeList*
1462 ascompatee(int op, NodeList *nl, NodeList *nr, NodeList **init)
1463 {
1464         NodeList *ll, *lr, *nn;
1465
1466         /*
1467          * check assign expression list to
1468          * a expression list. called in
1469          *      expr-list = expr-list
1470          */
1471
1472         // ensure order of evaluation for function calls
1473         for(ll=nl; ll; ll=ll->next)
1474                 ll->n = safeexpr(ll->n, init);
1475         for(lr=nr; lr; lr=lr->next)
1476                 lr->n = safeexpr(lr->n, init);
1477
1478         nn = nil;
1479         for(ll=nl, lr=nr; ll && lr; ll=ll->next, lr=lr->next) {
1480                 // Do not generate 'x = x' during return. See issue 4014.
1481                 if(op == ORETURN && ll->n == lr->n)
1482                         continue;
1483                 nn = list(nn, ascompatee1(op, ll->n, lr->n, init));
1484         }
1485
1486         // cannot happen: caller checked that lists had same length
1487         if(ll || lr)
1488                 yyerror("error in shape across %+H %O %+H / %d %d [%s]", nl, op, nr, count(nl), count(nr), curfn->nname->sym->name);
1489         return nn;
1490 }
1491
1492 /*
1493  * l is an lv and rt is the type of an rv
1494  * return 1 if this implies a function call
1495  * evaluating the lv or a function call
1496  * in the conversion of the types
1497  */
1498 static int
1499 fncall(Node *l, Type *rt)
1500 {
1501         Node r;
1502
1503         if(l->ullman >= UINF || l->op == OINDEXMAP)
1504                 return 1;
1505         memset(&r, 0, sizeof r);
1506         if(needwritebarrier(l, &r))
1507                 return 1;
1508         if(eqtype(l->type, rt))
1509                 return 0;
1510         return 1;
1511 }
1512
1513 static NodeList*
1514 ascompatet(int op, NodeList *nl, Type **nr, int fp, NodeList **init)
1515 {
1516         Node *l, *tmp, *a;
1517         NodeList *ll;
1518         Type *r;
1519         Iter saver;
1520         int ucount;
1521         NodeList *nn, *mm;
1522
1523         USED(op);
1524
1525         /*
1526          * check assign type list to
1527          * a expression list. called in
1528          *      expr-list = func()
1529          */
1530         r = structfirst(&saver, nr);
1531         nn = nil;
1532         mm = nil;
1533         ucount = 0;
1534         for(ll=nl; ll; ll=ll->next) {
1535                 if(r == T)
1536                         break;
1537                 l = ll->n;
1538                 if(isblank(l)) {
1539                         r = structnext(&saver);
1540                         continue;
1541                 }
1542
1543                 // any lv that causes a fn call must be
1544                 // deferred until all the return arguments
1545                 // have been pulled from the output arguments
1546                 if(fncall(l, r->type)) {
1547                         tmp = temp(r->type);
1548                         typecheck(&tmp, Erv);
1549                         a = nod(OAS, l, tmp);
1550                         a = convas(a, init);
1551                         mm = list(mm, a);
1552                         l = tmp;
1553                 }
1554
1555                 a = nod(OAS, l, nodarg(r, fp));
1556                 a = convas(a, init);
1557                 ullmancalc(a);
1558                 if(a->ullman >= UINF) {
1559                         dump("ascompatet ucount", a);
1560                         ucount++;
1561                 }
1562                 nn = list(nn, a);
1563                 r = structnext(&saver);
1564         }
1565
1566         if(ll != nil || r != T)
1567                 yyerror("ascompatet: assignment count mismatch: %d = %d",
1568                         count(nl), structcount(*nr));
1569
1570         if(ucount)
1571                 fatal("ascompatet: too many function calls evaluating parameters");
1572         return concat(nn, mm);
1573 }
1574
1575  /*
1576  * package all the arguments that match a ... T parameter into a []T.
1577  */
1578 static NodeList*
1579 mkdotargslice(NodeList *lr0, NodeList *nn, Type *l, int fp, NodeList **init, Node *ddd)
1580 {
1581         Node *a, *n;
1582         Type *tslice;
1583         int esc;
1584
1585         esc = EscUnknown;
1586         if(ddd != nil)
1587                 esc = ddd->esc;
1588
1589         tslice = typ(TARRAY);
1590         tslice->type = l->type->type;
1591         tslice->bound = -1;
1592
1593         if(count(lr0) == 0) {
1594                 n = nodnil();
1595                 n->type = tslice;
1596         } else {
1597                 n = nod(OCOMPLIT, N, typenod(tslice));
1598                 if(ddd != nil)
1599                         n->alloc = ddd->alloc; // temporary to use
1600                 n->list = lr0;
1601                 n->esc = esc;
1602                 typecheck(&n, Erv);
1603                 if(n->type == T)
1604                         fatal("mkdotargslice: typecheck failed");
1605                 walkexpr(&n, init);
1606         }
1607
1608         a = nod(OAS, nodarg(l, fp), n);
1609         nn = list(nn, convas(a, init));
1610         return nn;
1611 }
1612
1613 /*
1614  * helpers for shape errors
1615  */
1616 static char*
1617 dumptypes(Type **nl, char *what)
1618 {
1619         int first;
1620         Type *l;
1621         Iter savel;
1622         Fmt fmt;
1623
1624         fmtstrinit(&fmt);
1625         fmtprint(&fmt, "\t");
1626         first = 1;
1627         for(l = structfirst(&savel, nl); l != T; l = structnext(&savel)) {
1628                 if(first)
1629                         first = 0;
1630                 else
1631                         fmtprint(&fmt, ", ");
1632                 fmtprint(&fmt, "%T", l);
1633         }
1634         if(first)
1635                 fmtprint(&fmt, "[no arguments %s]", what);
1636         return fmtstrflush(&fmt);
1637 }
1638
1639 static char*
1640 dumpnodetypes(NodeList *l, char *what)
1641 {
1642         int first;
1643         Node *r;
1644         Fmt fmt;
1645
1646         fmtstrinit(&fmt);
1647         fmtprint(&fmt, "\t");
1648         first = 1;
1649         for(; l; l=l->next) {
1650                 r = l->n;
1651                 if(first)
1652                         first = 0;
1653                 else
1654                         fmtprint(&fmt, ", ");
1655                 fmtprint(&fmt, "%T", r->type);
1656         }
1657         if(first)
1658                 fmtprint(&fmt, "[no arguments %s]", what);
1659         return fmtstrflush(&fmt);
1660 }
1661
1662 /*
1663  * check assign expression list to
1664  * a type list. called in
1665  *      return expr-list
1666  *      func(expr-list)
1667  */
1668 static NodeList*
1669 ascompatte(int op, Node *call, int isddd, Type **nl, NodeList *lr, int fp, NodeList **init)
1670 {
1671         Type *l, *ll;
1672         Node *r, *a;
1673         NodeList *nn, *lr0, *alist;
1674         Iter savel;
1675         char *l1, *l2;
1676
1677         lr0 = lr;
1678         l = structfirst(&savel, nl);
1679         r = N;
1680         if(lr)
1681                 r = lr->n;
1682         nn = nil;
1683
1684         // f(g()) where g has multiple return values
1685         if(r != N && lr->next == nil && r->type->etype == TSTRUCT && r->type->funarg) {
1686                 // optimization - can do block copy
1687                 if(eqtypenoname(r->type, *nl)) {
1688                         a = nodarg(*nl, fp);
1689                         r = nod(OCONVNOP, r, N);
1690                         r->type = a->type;
1691                         nn = list1(convas(nod(OAS, a, r), init));
1692                         goto ret;
1693                 }
1694
1695                 // conversions involved.
1696                 // copy into temporaries.
1697                 alist = nil;
1698                 for(l=structfirst(&savel, &r->type); l; l=structnext(&savel)) {
1699                         a = temp(l->type);
1700                         alist = list(alist, a);
1701                 }
1702                 a = nod(OAS2, N, N);
1703                 a->list = alist;
1704                 a->rlist = lr;
1705                 typecheck(&a, Etop);
1706                 walkstmt(&a);
1707                 *init = list(*init, a);
1708                 lr = alist;
1709                 r = lr->n;
1710                 l = structfirst(&savel, nl);
1711         }
1712
1713 loop:
1714         if(l != T && l->isddd) {
1715                 // the ddd parameter must be last
1716                 ll = structnext(&savel);
1717                 if(ll != T)
1718                         yyerror("... must be last argument");
1719
1720                 // special case --
1721                 // only if we are assigning a single ddd
1722                 // argument to a ddd parameter then it is
1723                 // passed thru unencapsulated
1724                 if(r != N && lr->next == nil && isddd && eqtype(l->type, r->type)) {
1725                         a = nod(OAS, nodarg(l, fp), r);
1726                         a = convas(a, init);
1727                         nn = list(nn, a);
1728                         goto ret;
1729                 }
1730
1731                 // normal case -- make a slice of all
1732                 // remaining arguments and pass it to
1733                 // the ddd parameter.
1734                 nn = mkdotargslice(lr, nn, l, fp, init, call->right);
1735                 goto ret;
1736         }
1737
1738         if(l == T || r == N) {
1739                 if(l != T || r != N) {
1740                         l1 = dumptypes(nl, "expected");
1741                         l2 = dumpnodetypes(lr0, "given");
1742                         if(l != T)
1743                                 yyerror("not enough arguments to %O\n%s\n%s", op, l1, l2);
1744                         else
1745                                 yyerror("too many arguments to %O\n%s\n%s", op, l1, l2);
1746                 }
1747                 goto ret;
1748         }
1749
1750         a = nod(OAS, nodarg(l, fp), r);
1751         a = convas(a, init);
1752         nn = list(nn, a);
1753
1754         l = structnext(&savel);
1755         r = N;
1756         lr = lr->next;
1757         if(lr != nil)
1758                 r = lr->n;
1759         goto loop;
1760
1761 ret:
1762         for(lr=nn; lr; lr=lr->next)
1763                 lr->n->typecheck = 1;
1764         return nn;
1765 }
1766
1767 // generate code for print
1768 static Node*
1769 walkprint(Node *nn, NodeList **init)
1770 {
1771         Node *r;
1772         Node *n;
1773         NodeList *l, *all;
1774         Node *on;
1775         Type *t;
1776         int notfirst, et, op;
1777         NodeList *calls;
1778
1779         op = nn->op;
1780         all = nn->list;
1781         calls = nil;
1782         notfirst = 0;
1783
1784         // Hoist all the argument evaluation up before the lock.
1785         walkexprlistcheap(all, init);
1786
1787         calls = list(calls, mkcall("printlock", T, init));
1788
1789         for(l=all; l; l=l->next) {
1790                 if(notfirst) {
1791                         calls = list(calls, mkcall("printsp", T, init));
1792                 }
1793                 notfirst = op == OPRINTN;
1794
1795                 n = l->n;
1796                 if(n->op == OLITERAL) {
1797                         switch(n->val.ctype) {
1798                         case CTRUNE:
1799                                 defaultlit(&n, runetype);
1800                                 break;
1801                         case CTINT:
1802                                 defaultlit(&n, types[TINT64]);
1803                                 break;
1804                         case CTFLT:
1805                                 defaultlit(&n, types[TFLOAT64]);
1806                                 break;
1807                         }
1808                 }
1809                 if(n->op != OLITERAL && n->type && n->type->etype == TIDEAL)
1810                         defaultlit(&n, types[TINT64]);
1811                 defaultlit(&n, nil);
1812                 l->n = n;
1813                 if(n->type == T || n->type->etype == TFORW)
1814                         continue;
1815
1816                 t = n->type;
1817                 et = n->type->etype;
1818                 if(isinter(n->type)) {
1819                         if(isnilinter(n->type))
1820                                 on = syslook("printeface", 1);
1821                         else
1822                                 on = syslook("printiface", 1);
1823                         argtype(on, n->type);           // any-1
1824                 } else if(isptr[et] || et == TCHAN || et == TMAP || et == TFUNC || et == TUNSAFEPTR) {
1825                         on = syslook("printpointer", 1);
1826                         argtype(on, n->type);   // any-1
1827                 } else if(isslice(n->type)) {
1828                         on = syslook("printslice", 1);
1829                         argtype(on, n->type);   // any-1
1830                 } else if(isint[et]) {
1831                         if(et == TUINT64) {
1832                                 if((t->sym->pkg == runtimepkg || compiling_runtime) && strcmp(t->sym->name, "hex") == 0)
1833                                         on = syslook("printhex", 0);
1834                                 else
1835                                         on = syslook("printuint", 0);
1836                         } else
1837                                 on = syslook("printint", 0);
1838                 } else if(isfloat[et]) {
1839                         on = syslook("printfloat", 0);
1840                 } else if(iscomplex[et]) {
1841                         on = syslook("printcomplex", 0);
1842                 } else if(et == TBOOL) {
1843                         on = syslook("printbool", 0);
1844                 } else if(et == TSTRING) {
1845                         on = syslook("printstring", 0);
1846                 } else {
1847                         badtype(OPRINT, n->type, T);
1848                         continue;
1849                 }
1850
1851                 t = *getinarg(on->type);
1852                 if(t != nil)
1853                         t = t->type;
1854                 if(t != nil)
1855                         t = t->type;
1856
1857                 if(!eqtype(t, n->type)) {
1858                         n = nod(OCONV, n, N);
1859                         n->type = t;
1860                 }
1861
1862                 r = nod(OCALL, on, N);
1863                 r->list = list1(n);
1864                 calls = list(calls, r);
1865         }
1866
1867         if(op == OPRINTN)
1868                 calls = list(calls, mkcall("printnl", T, nil));
1869
1870         calls = list(calls, mkcall("printunlock", T, init));
1871
1872         typechecklist(calls, Etop);
1873         walkexprlist(calls, init);
1874
1875         r = nod(OEMPTY, N, N);
1876         typecheck(&r, Etop);
1877         walkexpr(&r, init);
1878         r->ninit = calls;
1879         return r;
1880 }
1881
1882 Node*
1883 callnew(Type *t)
1884 {
1885         Node *fn;
1886
1887         dowidth(t);
1888         fn = syslook("newobject", 1);
1889         argtype(fn, t);
1890         return mkcall1(fn, ptrto(t), nil, typename(t));
1891 }
1892
1893 static int
1894 isstack(Node *n)
1895 {
1896         while(n->op == ODOT || n->op == OPAREN || n->op == OCONVNOP || n->op == OINDEX && isfixedarray(n->left->type))
1897                 n = n->left;
1898
1899         switch(n->op) {
1900         case OINDREG:
1901                 // OINDREG only ends up in walk if it's indirect of SP.
1902                 return 1;
1903
1904         case ONAME:
1905                 switch(n->class) {
1906                 case PAUTO:
1907                 case PPARAM:
1908                 case PPARAMOUT:
1909                         return 1;
1910                 }
1911                 break;
1912         }
1913
1914         return 0;
1915 }
1916
1917 static int
1918 isglobal(Node *n)
1919 {
1920         while(n->op == ODOT || n->op == OPAREN || n->op == OCONVNOP || n->op == OINDEX && isfixedarray(n->left->type))
1921                 n = n->left;
1922
1923         switch(n->op) {
1924         case ONAME:
1925                 switch(n->class) {
1926                 case PEXTERN:
1927                         return 1;
1928                 }
1929                 break;
1930         }
1931
1932         return 0;
1933 }
1934
1935 // Do we need a write barrier for the assignment l = r?
1936 int
1937 needwritebarrier(Node *l, Node *r)
1938 {
1939         if(!use_writebarrier)
1940                 return 0;
1941
1942         if(l == N || isblank(l))
1943                 return 0;
1944
1945         // No write barrier for write of non-pointers.
1946         dowidth(l->type);
1947         if(!haspointers(l->type))
1948                 return 0;
1949
1950         // No write barrier for write to stack.
1951         if(isstack(l))
1952                 return 0;
1953
1954         // No write barrier for implicit or explicit zeroing.
1955         if(r == N || iszero(r))
1956                 return 0;
1957
1958         // No write barrier for initialization to constant.
1959         if(r->op == OLITERAL)
1960                 return 0;
1961
1962         // No write barrier for storing static (read-only) data.
1963         if(r->op == ONAME && strncmp(r->sym->name, "statictmp_", 10) == 0)
1964                 return 0;
1965
1966         // No write barrier for storing address of stack values,
1967         // which are guaranteed only to be written to the stack.
1968         if(r->op == OADDR && isstack(r->left))
1969                 return 0;
1970
1971         // No write barrier for storing address of global, which
1972         // is live no matter what.
1973         if(r->op == OADDR && isglobal(r->left))
1974                 return 0;
1975
1976         // No write barrier for reslice: x = x[0:y] or x = append(x, ...).
1977         // Both are compiled to modify x directly.
1978         // In the case of append, a write barrier may still be needed
1979         // if the underlying array grows, but the append code can
1980         // generate the write barrier directly in that case.
1981         // (It does not yet, but the cost of the write barrier will be
1982         // small compared to the cost of the allocation.)
1983         if(r->reslice) {
1984                 switch(r->op) {
1985                 case OSLICE:
1986                 case OSLICE3:
1987                 case OSLICESTR:
1988                 case OAPPEND:
1989                         break;
1990                 default:
1991                         dump("bad reslice-l", l);
1992                         dump("bad reslice-r", r);
1993                         break;
1994                 }
1995                 return 0;
1996         }
1997
1998         // Otherwise, be conservative and use write barrier.
1999         return 1;
2000 }
2001
2002 // TODO(rsc): Perhaps componentgen should run before this.
2003 static Node*
2004 applywritebarrier(Node *n, NodeList **init)
2005 {
2006         Node *l, *r;
2007         Type *t;
2008         vlong x;
2009         static Bvec *bv;
2010         char name[32];
2011
2012         if(n->left && n->right && needwritebarrier(n->left, n->right)) {
2013                 t = n->left->type;
2014                 l = nod(OADDR, n->left, N);
2015                 l->etype = 1; // addr does not escape
2016                 if(t->width == widthptr) {
2017                         n = mkcall1(writebarrierfn("writebarrierptr", t, n->right->type), T, init,
2018                                 l, n->right);
2019                 } else if(t->etype == TSTRING) {
2020                         n = mkcall1(writebarrierfn("writebarrierstring", t, n->right->type), T, init,
2021                                 l, n->right);
2022                 } else if(isslice(t)) {
2023                         n = mkcall1(writebarrierfn("writebarrierslice", t, n->right->type), T, init,
2024                                 l, n->right);
2025                 } else if(isinter(t)) {
2026                         n = mkcall1(writebarrierfn("writebarrieriface", t, n->right->type), T, init,
2027                                 l, n->right);
2028                 } else if(t->width <= 4*widthptr) {
2029                         x = 0;
2030                         if(bv == nil)
2031                                 bv = bvalloc(BitsPerPointer*4);
2032                         bvresetall(bv);
2033                         twobitwalktype1(t, &x, bv);
2034                         // The bvgets are looking for BitsPointer in successive slots.
2035                         enum {
2036                                 PtrBit = 1,
2037                         };
2038                         if(BitsPointer != (1<<PtrBit))
2039                                 fatal("wrong PtrBit");
2040                         switch(t->width/widthptr) {
2041                         default:
2042                                 fatal("found writebarrierfat for %d-byte object of type %T", (int)t->width, t);
2043                         case 2:
2044                                 snprint(name, sizeof name, "writebarrierfat%d%d",
2045                                         bvget(bv, PtrBit), bvget(bv, BitsPerPointer+PtrBit));
2046                                 break;
2047                         case 3:
2048                                 snprint(name, sizeof name, "writebarrierfat%d%d%d",
2049                                         bvget(bv, PtrBit), bvget(bv, BitsPerPointer+PtrBit), bvget(bv, 2*BitsPerPointer+PtrBit));
2050                                 break;
2051                         case 4:
2052                                 snprint(name, sizeof name, "writebarrierfat%d%d%d%d",
2053                                         bvget(bv, PtrBit), bvget(bv, BitsPerPointer+PtrBit), bvget(bv, 2*BitsPerPointer+PtrBit), bvget(bv, 3*BitsPerPointer+PtrBit));
2054                                 break;
2055                         }
2056                         n = mkcall1(writebarrierfn(name, t, n->right->type), T, init,
2057                                 l, nodnil(), n->right);
2058                 } else {
2059                         r = n->right;
2060                         while(r->op == OCONVNOP)
2061                                 r = r->left;
2062                         r = nod(OADDR, r, N);
2063                         r->etype = 1; // addr does not escape
2064                         //warnl(n->lineno, "writebarrierfat %T %N", t, r);
2065                         n = mkcall1(writebarrierfn("writebarrierfat", t, r->left->type), T, init,
2066                                 typename(t), l, r);
2067                 }
2068         }
2069         return n;
2070 }
2071
2072 static Node*
2073 convas(Node *n, NodeList **init)
2074 {
2075         Type *lt, *rt;
2076         Node *map, *key, *val;
2077
2078         if(n->op != OAS)
2079                 fatal("convas: not OAS %O", n->op);
2080
2081         n->typecheck = 1;
2082
2083         if(n->left == N || n->right == N)
2084                 goto out;
2085
2086         lt = n->left->type;
2087         rt = n->right->type;
2088         if(lt == T || rt == T)
2089                 goto out;
2090
2091         if(isblank(n->left)) {
2092                 defaultlit(&n->right, T);
2093                 goto out;
2094         }
2095
2096         if(n->left->op == OINDEXMAP) {
2097                 map = n->left->left;
2098                 key = n->left->right;
2099                 val = n->right;
2100                 walkexpr(&map, init);
2101                 walkexpr(&key, init);
2102                 walkexpr(&val, init);
2103                 // orderexpr made sure key and val are addressable.
2104                 key = nod(OADDR, key, N);
2105                 val = nod(OADDR, val, N);
2106                 n = mkcall1(mapfn("mapassign1", map->type), T, init,
2107                         typename(map->type), map, key, val);
2108                 goto out;
2109         }
2110
2111         if(!eqtype(lt, rt)) {
2112                 n->right = assignconv(n->right, lt, "assignment");
2113                 walkexpr(&n->right, init);
2114         }
2115
2116 out:
2117         ullmancalc(n);
2118         return n;
2119 }
2120
2121 /*
2122  * from ascompat[te]
2123  * evaluating actual function arguments.
2124  *      f(a,b)
2125  * if there is exactly one function expr,
2126  * then it is done first. otherwise must
2127  * make temp variables
2128  */
2129 static NodeList*
2130 reorder1(NodeList *all)
2131 {
2132         Node *f, *a, *n;
2133         NodeList *l, *r, *g;
2134         int c, d, t;
2135
2136         c = 0;  // function calls
2137         t = 0;  // total parameters
2138
2139         for(l=all; l; l=l->next) {
2140                 n = l->n;
2141                 t++;
2142                 ullmancalc(n);
2143                 if(n->ullman >= UINF)
2144                         c++;
2145         }
2146         if(c == 0 || t == 1)
2147                 return all;
2148
2149         g = nil;        // fncalls assigned to tempnames
2150         f = N;  // last fncall assigned to stack
2151         r = nil;        // non fncalls and tempnames assigned to stack
2152         d = 0;
2153         for(l=all; l; l=l->next) {
2154                 n = l->n;
2155                 if(n->ullman < UINF) {
2156                         r = list(r, n);
2157                         continue;
2158                 }
2159                 d++;
2160                 if(d == c) {
2161                         f = n;
2162                         continue;
2163                 }
2164
2165                 // make assignment of fncall to tempname
2166                 a = temp(n->right->type);
2167                 a = nod(OAS, a, n->right);
2168                 g = list(g, a);
2169
2170                 // put normal arg assignment on list
2171                 // with fncall replaced by tempname
2172                 n->right = a->left;
2173                 r = list(r, n);
2174         }
2175
2176         if(f != N)
2177                 g = list(g, f);
2178         return concat(g, r);
2179 }
2180
2181 static void reorder3save(Node**, NodeList*, NodeList*, NodeList**);
2182 static int aliased(Node*, NodeList*, NodeList*);
2183
2184 /*
2185  * from ascompat[ee]
2186  *      a,b = c,d
2187  * simultaneous assignment. there cannot
2188  * be later use of an earlier lvalue.
2189  *
2190  * function calls have been removed.
2191  */
2192 static NodeList*
2193 reorder3(NodeList *all)
2194 {
2195         NodeList *list, *early, *mapinit;
2196         Node *l;
2197
2198         // If a needed expression may be affected by an
2199         // earlier assignment, make an early copy of that
2200         // expression and use the copy instead.
2201         early = nil;
2202         mapinit = nil;
2203         for(list=all; list; list=list->next) {
2204                 l = list->n->left;
2205
2206                 // Save subexpressions needed on left side.
2207                 // Drill through non-dereferences.
2208                 for(;;) {
2209                         if(l->op == ODOT || l->op == OPAREN) {
2210                                 l = l->left;
2211                                 continue;
2212                         }
2213                         if(l->op == OINDEX && isfixedarray(l->left->type)) {
2214                                 reorder3save(&l->right, all, list, &early);
2215                                 l = l->left;
2216                                 continue;
2217                         }
2218                         break;
2219                 }
2220                 switch(l->op) {
2221                 default:
2222                         fatal("reorder3 unexpected lvalue %#O", l->op);
2223                 case ONAME:
2224                         break;
2225                 case OINDEX:
2226                 case OINDEXMAP:
2227                         reorder3save(&l->left, all, list, &early);
2228                         reorder3save(&l->right, all, list, &early);
2229                         if(l->op == OINDEXMAP)
2230                                 list->n = convas(list->n, &mapinit);
2231                         break;
2232                 case OIND:
2233                 case ODOTPTR:
2234                         reorder3save(&l->left, all, list, &early);
2235                 }
2236
2237                 // Save expression on right side.
2238                 reorder3save(&list->n->right, all, list, &early);
2239         }
2240
2241         early = concat(mapinit, early);
2242         return concat(early, all);
2243 }
2244
2245 static int vmatch2(Node*, Node*);
2246 static int varexpr(Node*);
2247
2248 /*
2249  * if the evaluation of *np would be affected by the
2250  * assignments in all up to but not including stop,
2251  * copy into a temporary during *early and
2252  * replace *np with that temp.
2253  */
2254 static void
2255 reorder3save(Node **np, NodeList *all, NodeList *stop, NodeList **early)
2256 {
2257         Node *n, *q;
2258
2259         n = *np;
2260         if(!aliased(n, all, stop))
2261                 return;
2262
2263         q = temp(n->type);
2264         q = nod(OAS, q, n);
2265         typecheck(&q, Etop);
2266         *early = list(*early, q);
2267         *np = q->left;
2268 }
2269
2270 /*
2271  * what's the outer value that a write to n affects?
2272  * outer value means containing struct or array.
2273  */
2274 Node*
2275 outervalue(Node *n)
2276 {
2277         for(;;) {
2278                 if(n->op == ODOT || n->op == OPAREN) {
2279                         n = n->left;
2280                         continue;
2281                 }
2282                 if(n->op == OINDEX && isfixedarray(n->left->type)) {
2283                         n = n->left;
2284                         continue;
2285                 }
2286                 break;
2287         }
2288         return n;
2289 }
2290
2291 /*
2292  * Is it possible that the computation of n might be
2293  * affected by writes in as up to but not including stop?
2294  */
2295 static int
2296 aliased(Node *n, NodeList *all, NodeList *stop)
2297 {
2298         int memwrite, varwrite;
2299         Node *a;
2300         NodeList *l;
2301
2302         if(n == N)
2303                 return 0;
2304
2305         // Look for obvious aliasing: a variable being assigned
2306         // during the all list and appearing in n.
2307         // Also record whether there are any writes to main memory.
2308         // Also record whether there are any writes to variables
2309         // whose addresses have been taken.
2310         memwrite = 0;
2311         varwrite = 0;
2312         for(l=all; l!=stop; l=l->next) {
2313                 a = outervalue(l->n->left);
2314                 if(a->op != ONAME) {
2315                         memwrite = 1;
2316                         continue;
2317                 }
2318                 switch(n->class) {
2319                 default:
2320                         varwrite = 1;
2321                         continue;
2322                 case PAUTO:
2323                 case PPARAM:
2324                 case PPARAMOUT:
2325                         if(n->addrtaken) {
2326                                 varwrite = 1;
2327                                 continue;
2328                         }
2329                         if(vmatch2(a, n)) {
2330                                 // Direct hit.
2331                                 return 1;
2332                         }
2333                 }
2334         }
2335
2336         // The variables being written do not appear in n.
2337         // However, n might refer to computed addresses
2338         // that are being written.
2339
2340         // If no computed addresses are affected by the writes, no aliasing.
2341         if(!memwrite && !varwrite)
2342                 return 0;
2343
2344         // If n does not refer to computed addresses
2345         // (that is, if n only refers to variables whose addresses
2346         // have not been taken), no aliasing.
2347         if(varexpr(n))
2348                 return 0;
2349
2350         // Otherwise, both the writes and n refer to computed memory addresses.
2351         // Assume that they might conflict.
2352         return 1;
2353 }
2354
2355 /*
2356  * does the evaluation of n only refer to variables
2357  * whose addresses have not been taken?
2358  * (and no other memory)
2359  */
2360 static int
2361 varexpr(Node *n)
2362 {
2363         if(n == N)
2364                 return 1;
2365
2366         switch(n->op) {
2367         case OLITERAL:
2368                 return 1;
2369         case ONAME:
2370                 switch(n->class) {
2371                 case PAUTO:
2372                 case PPARAM:
2373                 case PPARAMOUT:
2374                         if(!n->addrtaken)
2375                                 return 1;
2376                 }
2377                 return 0;
2378
2379         case OADD:
2380         case OSUB:
2381         case OOR:
2382         case OXOR:
2383         case OMUL:
2384         case ODIV:
2385         case OMOD:
2386         case OLSH:
2387         case ORSH:
2388         case OAND:
2389         case OANDNOT:
2390         case OPLUS:
2391         case OMINUS:
2392         case OCOM:
2393         case OPAREN:
2394         case OANDAND:
2395         case OOROR:
2396         case ODOT:  // but not ODOTPTR
2397         case OCONV:
2398         case OCONVNOP:
2399         case OCONVIFACE:
2400         case ODOTTYPE:
2401                 return varexpr(n->left) && varexpr(n->right);
2402         }
2403
2404         // Be conservative.
2405         return 0;
2406 }
2407
2408 /*
2409  * is the name l mentioned in r?
2410  */
2411 static int
2412 vmatch2(Node *l, Node *r)
2413 {
2414         NodeList *ll;
2415
2416         if(r == N)
2417                 return 0;
2418         switch(r->op) {
2419         case ONAME:
2420                 // match each right given left
2421                 return l == r;
2422         case OLITERAL:
2423                 return 0;
2424         }
2425         if(vmatch2(l, r->left))
2426                 return 1;
2427         if(vmatch2(l, r->right))
2428                 return 1;
2429         for(ll=r->list; ll; ll=ll->next)
2430                 if(vmatch2(l, ll->n))
2431                         return 1;
2432         return 0;
2433 }
2434
2435 /*
2436  * is any name mentioned in l also mentioned in r?
2437  * called by sinit.c
2438  */
2439 int
2440 vmatch1(Node *l, Node *r)
2441 {
2442         NodeList *ll;
2443
2444         /*
2445          * isolate all left sides
2446          */
2447         if(l == N || r == N)
2448                 return 0;
2449         switch(l->op) {
2450         case ONAME:
2451                 switch(l->class) {
2452                 case PPARAM:
2453                 case PPARAMREF:
2454                 case PAUTO:
2455                         break;
2456                 default:
2457                         // assignment to non-stack variable
2458                         // must be delayed if right has function calls.
2459                         if(r->ullman >= UINF)
2460                                 return 1;
2461                         break;
2462                 }
2463                 return vmatch2(l, r);
2464         case OLITERAL:
2465                 return 0;
2466         }
2467         if(vmatch1(l->left, r))
2468                 return 1;
2469         if(vmatch1(l->right, r))
2470                 return 1;
2471         for(ll=l->list; ll; ll=ll->next)
2472                 if(vmatch1(ll->n, r))
2473                         return 1;
2474         return 0;
2475 }
2476
2477 /*
2478  * walk through argin parameters.
2479  * generate and return code to allocate
2480  * copies of escaped parameters to the heap.
2481  */
2482 static NodeList*
2483 paramstoheap(Type **argin, int out)
2484 {
2485         Type *t;
2486         Iter savet;
2487         Node *v;
2488         NodeList *nn;
2489
2490         nn = nil;
2491         for(t = structfirst(&savet, argin); t != T; t = structnext(&savet)) {
2492                 v = t->nname;
2493                 if(v && v->sym && v->sym->name[0] == '~' && v->sym->name[1] == 'r') // unnamed result
2494                         v = N;
2495                 // In precisestack mode, the garbage collector assumes results
2496                 // are always live, so zero them always.
2497                 if(out && (precisestack_enabled || (v == N && hasdefer))) {
2498                         // Defer might stop a panic and show the
2499                         // return values as they exist at the time of panic.
2500                         // Make sure to zero them on entry to the function.
2501                         nn = list(nn, nod(OAS, nodarg(t, 1), N));
2502                 }
2503                 if(v == N || !(v->class & PHEAP))
2504                         continue;
2505
2506                 // generate allocation & copying code
2507                 if(compiling_runtime)
2508                         yyerror("%N escapes to heap, not allowed in runtime.", v);
2509                 if(v->alloc == nil)
2510                         v->alloc = callnew(v->type);
2511                 nn = list(nn, nod(OAS, v->heapaddr, v->alloc));
2512                 if((v->class & ~PHEAP) != PPARAMOUT)
2513                         nn = list(nn, nod(OAS, v, v->stackparam));
2514         }
2515         return nn;
2516 }
2517
2518 /*
2519  * walk through argout parameters copying back to stack
2520  */
2521 static NodeList*
2522 returnsfromheap(Type **argin)
2523 {
2524         Type *t;
2525         Iter savet;
2526         Node *v;
2527         NodeList *nn;
2528
2529         nn = nil;
2530         for(t = structfirst(&savet, argin); t != T; t = structnext(&savet)) {
2531                 v = t->nname;
2532                 if(v == N || v->class != (PHEAP|PPARAMOUT))
2533                         continue;
2534                 nn = list(nn, nod(OAS, v->stackparam, v));
2535         }
2536         return nn;
2537 }
2538
2539 /*
2540  * take care of migrating any function in/out args
2541  * between the stack and the heap.  adds code to
2542  * curfn's before and after lists.
2543  */
2544 static void
2545 heapmoves(void)
2546 {
2547         NodeList *nn;
2548         int32 lno;
2549
2550         lno = lineno;
2551         lineno = curfn->lineno;
2552         nn = paramstoheap(getthis(curfn->type), 0);
2553         nn = concat(nn, paramstoheap(getinarg(curfn->type), 0));
2554         nn = concat(nn, paramstoheap(getoutarg(curfn->type), 1));
2555         curfn->enter = concat(curfn->enter, nn);
2556         lineno = curfn->endlineno;
2557         curfn->exit = returnsfromheap(getoutarg(curfn->type));
2558         lineno = lno;
2559 }
2560
2561 static Node*
2562 vmkcall(Node *fn, Type *t, NodeList **init, va_list va)
2563 {
2564         int i, n;
2565         Node *r;
2566         NodeList *args;
2567
2568         if(fn->type == T || fn->type->etype != TFUNC)
2569                 fatal("mkcall %N %T", fn, fn->type);
2570
2571         args = nil;
2572         n = fn->type->intuple;
2573         for(i=0; i<n; i++)
2574                 args = list(args, va_arg(va, Node*));
2575
2576         r = nod(OCALL, fn, N);
2577         r->list = args;
2578         if(fn->type->outtuple > 0)
2579                 typecheck(&r, Erv | Efnstruct);
2580         else
2581                 typecheck(&r, Etop);
2582         walkexpr(&r, init);
2583         r->type = t;
2584         return r;
2585 }
2586
2587 Node*
2588 mkcall(char *name, Type *t, NodeList **init, ...)
2589 {
2590         Node *r;
2591         va_list va;
2592
2593         va_start(va, init);
2594         r = vmkcall(syslook(name, 0), t, init, va);
2595         va_end(va);
2596         return r;
2597 }
2598
2599 Node*
2600 mkcall1(Node *fn, Type *t, NodeList **init, ...)
2601 {
2602         Node *r;
2603         va_list va;
2604
2605         va_start(va, init);
2606         r = vmkcall(fn, t, init, va);
2607         va_end(va);
2608         return r;
2609 }
2610
2611 Node*
2612 conv(Node *n, Type *t)
2613 {
2614         if(eqtype(n->type, t))
2615                 return n;
2616         n = nod(OCONV, n, N);
2617         n->type = t;
2618         typecheck(&n, Erv);
2619         return n;
2620 }
2621
2622 Node*
2623 chanfn(char *name, int n, Type *t)
2624 {
2625         Node *fn;
2626         int i;
2627
2628         if(t->etype != TCHAN)
2629                 fatal("chanfn %T", t);
2630         fn = syslook(name, 1);
2631         for(i=0; i<n; i++)
2632                 argtype(fn, t->type);
2633         return fn;
2634 }
2635
2636 static Node*
2637 mapfn(char *name, Type *t)
2638 {
2639         Node *fn;
2640
2641         if(t->etype != TMAP)
2642                 fatal("mapfn %T", t);
2643         fn = syslook(name, 1);
2644         argtype(fn, t->down);
2645         argtype(fn, t->type);
2646         argtype(fn, t->down);
2647         argtype(fn, t->type);
2648         return fn;
2649 }
2650
2651 static Node*
2652 mapfndel(char *name, Type *t)
2653 {
2654         Node *fn;
2655
2656         if(t->etype != TMAP)
2657                 fatal("mapfn %T", t);
2658         fn = syslook(name, 1);
2659         argtype(fn, t->down);
2660         argtype(fn, t->type);
2661         argtype(fn, t->down);
2662         return fn;
2663 }
2664
2665 static Node*
2666 writebarrierfn(char *name, Type *l, Type *r)
2667 {
2668         Node *fn;
2669
2670         fn = syslook(name, 1);
2671         argtype(fn, l);
2672         argtype(fn, r);
2673         return fn;
2674 }
2675
2676 static Node*
2677 addstr(Node *n, NodeList **init)
2678 {
2679         Node *r, *cat, *slice;
2680         NodeList *args, *l;
2681         int c;
2682         Type *t;
2683
2684         // orderexpr rewrote OADDSTR to have a list of strings.
2685         c = count(n->list);
2686         if(c < 2)
2687                 yyerror("addstr count %d too small", c);
2688
2689         // build list of string arguments
2690         args = nil;
2691         for(l=n->list; l != nil; l=l->next)
2692                 args = list(args, conv(l->n, types[TSTRING]));
2693
2694         if(c <= 5) {
2695                 // small numbers of strings use direct runtime helpers.
2696                 // note: orderexpr knows this cutoff too.
2697                 snprint(namebuf, sizeof(namebuf), "concatstring%d", c);
2698         } else {
2699                 // large numbers of strings are passed to the runtime as a slice.
2700                 strcpy(namebuf, "concatstrings");
2701                 t = typ(TARRAY);
2702                 t->type = types[TSTRING];
2703                 t->bound = -1;
2704                 slice = nod(OCOMPLIT, N, typenod(t));
2705                 slice->alloc = n->alloc;
2706                 slice->list = args;
2707                 slice->esc = EscNone;
2708                 args = list1(slice);
2709         }
2710         cat = syslook(namebuf, 1);
2711         r = nod(OCALL, cat, N);
2712         r->list = args;
2713         typecheck(&r, Erv);
2714         walkexpr(&r, init);
2715         r->type = n->type;
2716
2717         return r;
2718 }
2719
2720 // expand append(l1, l2...) to
2721 //   init {
2722 //     s := l1
2723 //     if n := len(l1) + len(l2) - cap(s); n > 0 {
2724 //       s = growslice(s, n)
2725 //     }
2726 //     s = s[:len(l1)+len(l2)]
2727 //     memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
2728 //   }
2729 //   s
2730 //
2731 // l2 is allowed to be a string.
2732 static Node*
2733 appendslice(Node *n, NodeList **init)
2734 {
2735         NodeList *l;
2736         Node *l1, *l2, *nt, *nif, *fn;
2737         Node *nptr1, *nptr2, *nwid;
2738         Node *s;
2739
2740         walkexprlistsafe(n->list, init);
2741
2742         // walkexprlistsafe will leave OINDEX (s[n]) alone if both s
2743         // and n are name or literal, but those may index the slice we're
2744         // modifying here.  Fix explicitly.
2745         for(l=n->list; l; l=l->next)
2746                 l->n = cheapexpr(l->n, init);
2747
2748         l1 = n->list->n;
2749         l2 = n->list->next->n;
2750
2751         s = temp(l1->type); // var s []T
2752         l = nil;
2753         l = list(l, nod(OAS, s, l1)); // s = l1
2754
2755         nt = temp(types[TINT]);
2756         nif = nod(OIF, N, N);
2757         // n := len(s) + len(l2) - cap(s)
2758         nif->ninit = list1(nod(OAS, nt,
2759                 nod(OSUB, nod(OADD, nod(OLEN, s, N), nod(OLEN, l2, N)), nod(OCAP, s, N))));
2760         nif->ntest = nod(OGT, nt, nodintconst(0));
2761         // instantiate growslice(Type*, []any, int64) []any
2762         fn = syslook("growslice", 1);
2763         argtype(fn, s->type->type);
2764         argtype(fn, s->type->type);
2765
2766         // s = growslice(T, s, n)
2767         nif->nbody = list1(nod(OAS, s, mkcall1(fn, s->type, &nif->ninit,
2768                                                typename(s->type),
2769                                                s,
2770                                                conv(nt, types[TINT64]))));
2771
2772         l = list(l, nif);
2773
2774         if(flag_race) {
2775                 // rely on runtime to instrument copy.
2776                 // copy(s[len(l1):len(l1)+len(l2)], l2)
2777                 nptr1 = nod(OSLICE, s, nod(OKEY,
2778                         nod(OLEN, l1, N),
2779                         nod(OADD, nod(OLEN, l1, N), nod(OLEN, l2, N))));
2780                 nptr1->etype = 1;
2781                 nptr2 = l2;
2782                 if(l2->type->etype == TSTRING)
2783                         fn = syslook("slicestringcopy", 1);
2784                 else
2785                         fn = syslook("slicecopy", 1);
2786                 argtype(fn, l1->type);
2787                 argtype(fn, l2->type);
2788                 nt = mkcall1(fn, types[TINT], &l,
2789                                 nptr1, nptr2,
2790                                 nodintconst(s->type->type->width));
2791                 l = list(l, nt);
2792         } else {
2793                 // memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
2794                 nptr1 = nod(OINDEX, s, nod(OLEN, l1, N));
2795                 nptr1->bounded = 1;
2796                 nptr1 = nod(OADDR, nptr1, N);
2797
2798                 nptr2 = nod(OSPTR, l2, N);
2799
2800                 fn = syslook("memmove", 1);
2801                 argtype(fn, s->type->type);     // 1 old []any
2802                 argtype(fn, s->type->type);     // 2 ret []any
2803
2804                 nwid = cheapexpr(conv(nod(OLEN, l2, N), types[TUINTPTR]), &l);
2805                 nwid = nod(OMUL, nwid, nodintconst(s->type->type->width));
2806                 nt = mkcall1(fn, T, &l, nptr1, nptr2, nwid);
2807                 l = list(l, nt);
2808         }
2809
2810         // s = s[:len(l1)+len(l2)]
2811         nt = nod(OADD, nod(OLEN, l1, N), nod(OLEN, l2, N));
2812         nt = nod(OSLICE, s, nod(OKEY, N, nt));
2813         nt->etype = 1;
2814         l = list(l, nod(OAS, s, nt));
2815
2816         typechecklist(l, Etop);
2817         walkstmtlist(l);
2818         *init = concat(*init, l);
2819         return s;
2820 }
2821
2822 // expand append(src, a [, b]* ) to
2823 //
2824 //   init {
2825 //     s := src
2826 //     const argc = len(args) - 1
2827 //     if cap(s) - len(s) < argc {
2828 //          s = growslice(s, argc)
2829 //     }
2830 //     n := len(s)
2831 //     s = s[:n+argc]
2832 //     s[n] = a
2833 //     s[n+1] = b
2834 //     ...
2835 //   }
2836 //   s
2837 static Node*
2838 append(Node *n, NodeList **init)
2839 {
2840         NodeList *l, *a;
2841         Node *nsrc, *ns, *nn, *na, *nx, *fn;
2842         int argc;
2843
2844         walkexprlistsafe(n->list, init);
2845
2846         // walkexprlistsafe will leave OINDEX (s[n]) alone if both s
2847         // and n are name or literal, but those may index the slice we're
2848         // modifying here.  Fix explicitly.
2849         for(l=n->list; l; l=l->next)
2850                 l->n = cheapexpr(l->n, init);
2851
2852         nsrc = n->list->n;
2853
2854         // Resolve slice type of multi-valued return.
2855         if(istype(nsrc->type, TSTRUCT))
2856                 nsrc->type = nsrc->type->type->type;
2857         argc = count(n->list) - 1;
2858         if (argc < 1) {
2859                 return nsrc;
2860         }
2861
2862         l = nil;
2863
2864         ns = temp(nsrc->type);
2865         l = list(l, nod(OAS, ns, nsrc));  // s = src
2866
2867         na = nodintconst(argc);         // const argc
2868         nx = nod(OIF, N, N);            // if cap(s) - len(s) < argc
2869         nx->ntest = nod(OLT, nod(OSUB, nod(OCAP, ns, N), nod(OLEN, ns, N)), na);
2870
2871         fn = syslook("growslice", 1);   //   growslice(<type>, old []T, n int64) (ret []T)
2872         argtype(fn, ns->type->type);    // 1 old []any
2873         argtype(fn, ns->type->type);    // 2 ret []any
2874
2875         nx->nbody = list1(nod(OAS, ns, mkcall1(fn,  ns->type, &nx->ninit,
2876                                                typename(ns->type),
2877                                                ns,
2878                                                conv(na, types[TINT64]))));
2879         l = list(l, nx);
2880
2881         nn = temp(types[TINT]);
2882         l = list(l, nod(OAS, nn, nod(OLEN, ns, N)));     // n = len(s)
2883
2884         nx = nod(OSLICE, ns, nod(OKEY, N, nod(OADD, nn, na)));   // ...s[:n+argc]
2885         nx->etype = 1;
2886         l = list(l, nod(OAS, ns, nx));                  // s = s[:n+argc]
2887
2888         for (a = n->list->next;  a != nil; a = a->next) {
2889                 nx = nod(OINDEX, ns, nn);               // s[n] ...
2890                 nx->bounded = 1;
2891                 l = list(l, nod(OAS, nx, a->n));        // s[n] = arg
2892                 if (a->next != nil)
2893                         l = list(l, nod(OAS, nn, nod(OADD, nn, nodintconst(1))));  // n = n + 1
2894         }
2895
2896         typechecklist(l, Etop);
2897         walkstmtlist(l);
2898         *init = concat(*init, l);
2899         return ns;
2900 }
2901
2902 // Lower copy(a, b) to a memmove call or a runtime call.
2903 //
2904 // init {
2905 //   n := len(a)
2906 //   if n > len(b) { n = len(b) }
2907 //   memmove(a.ptr, b.ptr, n*sizeof(elem(a)))
2908 // }
2909 // n;
2910 //
2911 // Also works if b is a string.
2912 //
2913 static Node*
2914 copyany(Node *n, NodeList **init, int runtimecall)
2915 {
2916         Node *nl, *nr, *nfrm, *nto, *nif, *nlen, *nwid, *fn;
2917         NodeList *l;
2918
2919         if(haspointers(n->left->type->type)) {
2920                 fn = writebarrierfn("writebarriercopy", n->left->type, n->right->type);
2921                 return mkcall1(fn, n->type, init, typename(n->left->type->type), n->left, n->right);
2922         }
2923
2924         if(runtimecall) {
2925                 if(n->right->type->etype == TSTRING)
2926                         fn = syslook("slicestringcopy", 1);
2927                 else
2928                         fn = syslook("slicecopy", 1);
2929                 argtype(fn, n->left->type);
2930                 argtype(fn, n->right->type);
2931                 return mkcall1(fn, n->type, init,
2932                                 n->left, n->right,
2933                                 nodintconst(n->left->type->type->width));
2934         }
2935         walkexpr(&n->left, init);
2936         walkexpr(&n->right, init);
2937         nl = temp(n->left->type);
2938         nr = temp(n->right->type);
2939         l = nil;
2940         l = list(l, nod(OAS, nl, n->left));
2941         l = list(l, nod(OAS, nr, n->right));
2942
2943         nfrm = nod(OSPTR, nr, N);
2944         nto = nod(OSPTR, nl, N);
2945
2946         nlen = temp(types[TINT]);
2947         // n = len(to)
2948         l = list(l, nod(OAS, nlen, nod(OLEN, nl, N)));
2949         // if n > len(frm) { n = len(frm) }
2950         nif = nod(OIF, N, N);
2951         nif->ntest = nod(OGT, nlen, nod(OLEN, nr, N));
2952         nif->nbody = list(nif->nbody,
2953                 nod(OAS, nlen, nod(OLEN, nr, N)));
2954         l = list(l, nif);
2955
2956         // Call memmove.
2957         fn = syslook("memmove", 1);
2958         argtype(fn, nl->type->type);
2959         argtype(fn, nl->type->type);
2960         nwid = temp(types[TUINTPTR]);
2961         l = list(l, nod(OAS, nwid, conv(nlen, types[TUINTPTR])));
2962         nwid = nod(OMUL, nwid, nodintconst(nl->type->type->width));
2963         l = list(l, mkcall1(fn, T, init, nto, nfrm, nwid));
2964
2965         typechecklist(l, Etop);
2966         walkstmtlist(l);
2967         *init = concat(*init, l);
2968         return nlen;
2969 }
2970
2971 // Generate frontend part for OSLICE[3][ARR|STR]
2972 //
2973 static  Node*
2974 sliceany(Node* n, NodeList **init)
2975 {
2976         int bounded, slice3;
2977         Node *src, *lb, *hb, *cb, *bound, *chk, *chk0, *chk1, *chk2;
2978         int64 lbv, hbv, cbv, bv, w;
2979         Type *bt;
2980
2981 //      print("before sliceany: %+N\n", n);
2982
2983         src = n->left;
2984         lb = n->right->left;
2985         slice3 = n->op == OSLICE3 || n->op == OSLICE3ARR;
2986         if(slice3) {
2987                 hb = n->right->right->left;
2988                 cb = n->right->right->right;
2989         } else {
2990                 hb = n->right->right;
2991                 cb = N;
2992         }
2993
2994         bounded = n->etype;
2995
2996         if(n->op == OSLICESTR)
2997                 bound = nod(OLEN, src, N);
2998         else
2999                 bound = nod(OCAP, src, N);
3000
3001         typecheck(&bound, Erv);
3002         walkexpr(&bound, init);  // if src is an array, bound will be a const now.
3003
3004         // static checks if possible
3005         bv = 1LL<<50;
3006         if(isconst(bound, CTINT)) {
3007                 if(!smallintconst(bound))
3008                         yyerror("array len too large");
3009                 else
3010                         bv = mpgetfix(bound->val.u.xval);
3011         }
3012
3013         if(isconst(cb, CTINT)) {
3014                 cbv = mpgetfix(cb->val.u.xval);
3015                 if(cbv < 0 || cbv > bv)
3016                         yyerror("slice index out of bounds");
3017         }
3018         if(isconst(hb, CTINT)) {
3019                 hbv = mpgetfix(hb->val.u.xval);
3020                 if(hbv < 0 || hbv > bv)
3021                         yyerror("slice index out of bounds");
3022         }
3023         if(isconst(lb, CTINT)) {
3024                 lbv = mpgetfix(lb->val.u.xval);
3025                 if(lbv < 0 || lbv > bv) {
3026                         yyerror("slice index out of bounds");
3027                         lbv = -1;
3028                 }
3029                 if(lbv == 0)
3030                         lb = N;
3031         }
3032
3033         // Checking src[lb:hb:cb] or src[lb:hb].
3034         // if chk0 || chk1 || chk2 { panicslice() }
3035         chk = N;
3036         chk0 = N; // cap(src) < cb
3037         chk1 = N; // cb < hb for src[lb:hb:cb]; cap(src) < hb for src[lb:hb]
3038         chk2 = N; // hb < lb
3039
3040         // All comparisons are unsigned to avoid testing < 0.
3041         bt = types[simtype[TUINT]];
3042         if(cb != N && cb->type->width > 4)
3043                 bt = types[TUINT64];
3044         if(hb != N && hb->type->width > 4)
3045                 bt = types[TUINT64];
3046         if(lb != N && lb->type->width > 4)
3047                 bt = types[TUINT64];
3048
3049         bound = cheapexpr(conv(bound, bt), init);
3050
3051         if(cb != N) {
3052                 cb = cheapexpr(conv(cb, bt), init);
3053                 if(!bounded)
3054                         chk0 = nod(OLT, bound, cb);
3055         } else if(slice3) {
3056                 // When we figure out what this means, implement it.
3057                 fatal("slice3 with cb == N"); // rejected by parser
3058         }
3059
3060         if(hb != N) {
3061                 hb = cheapexpr(conv(hb, bt), init);
3062                 if(!bounded) {
3063                         if(cb != N)
3064                                 chk1 = nod(OLT, cb, hb);
3065                         else
3066                                 chk1 = nod(OLT, bound, hb);
3067                 }
3068         } else if(slice3) {
3069                 // When we figure out what this means, implement it.
3070                 fatal("slice3 with hb == N"); // rejected by parser
3071         } else if(n->op == OSLICEARR) {
3072                 hb = bound;
3073         } else {
3074                 hb = nod(OLEN, src, N);
3075                 typecheck(&hb, Erv);
3076                 walkexpr(&hb, init);
3077                 hb = cheapexpr(conv(hb, bt), init);
3078         }
3079
3080         if(lb != N) {
3081                 lb = cheapexpr(conv(lb, bt), init);
3082                 if(!bounded)
3083                         chk2 = nod(OLT, hb, lb);
3084         }
3085
3086         if(chk0 != N || chk1 != N || chk2 != N) {
3087                 chk = nod(OIF, N, N);
3088                 chk->nbody = list1(mkcall("panicslice", T, init));
3089                 chk->likely = -1;
3090                 if(chk0 != N)
3091                         chk->ntest = chk0;
3092                 if(chk1 != N) {
3093                         if(chk->ntest == N)
3094                                 chk->ntest = chk1;
3095                         else
3096                                 chk->ntest = nod(OOROR, chk->ntest, chk1);
3097                 }
3098                 if(chk2 != N) {
3099                         if(chk->ntest == N)
3100                                 chk->ntest = chk2;
3101                         else
3102                                 chk->ntest = nod(OOROR, chk->ntest, chk2);
3103                 }
3104                 typecheck(&chk, Etop);
3105                 walkstmt(&chk);
3106                 *init = concat(*init, chk->ninit);
3107                 chk->ninit = nil;
3108                 *init = list(*init, chk);
3109         }
3110
3111         // prepare new cap, len and offs for backend cgen_slice
3112         // cap = bound [ - lo ]
3113         n->right = N;
3114         n->list = nil;
3115         if(!slice3)
3116                 cb = bound;
3117         if(lb == N)
3118                 bound = conv(cb, types[simtype[TUINT]]);
3119         else
3120                 bound = nod(OSUB, conv(cb, types[simtype[TUINT]]), conv(lb, types[simtype[TUINT]]));
3121         typecheck(&bound, Erv);
3122         walkexpr(&bound, init);
3123         n->list = list(n->list, bound);
3124
3125         // len = hi [ - lo]
3126         if(lb == N)
3127                 hb = conv(hb, types[simtype[TUINT]]);
3128         else
3129                 hb = nod(OSUB, conv(hb, types[simtype[TUINT]]), conv(lb, types[simtype[TUINT]]));
3130         typecheck(&hb, Erv);
3131         walkexpr(&hb, init);
3132         n->list = list(n->list, hb);
3133
3134         // offs = [width *] lo, but omit if zero
3135         if(lb != N) {
3136                 if(n->op == OSLICESTR)
3137                         w = 1;
3138                 else
3139                         w = n->type->type->width;
3140                 lb = conv(lb, types[TUINTPTR]);
3141                 if(w > 1)
3142                         lb = nod(OMUL, nodintconst(w), lb);
3143                 typecheck(&lb, Erv);
3144                 walkexpr(&lb, init);
3145                 n->list = list(n->list, lb);
3146         }
3147
3148 //      print("after sliceany: %+N\n", n);
3149
3150         return n;
3151 }
3152
3153 static Node*
3154 eqfor(Type *t)
3155 {
3156         int a;
3157         Node *n;
3158         Node *ntype;
3159         Sym *sym;
3160
3161         // Should only arrive here with large memory or
3162         // a struct/array containing a non-memory field/element.
3163         // Small memory is handled inline, and single non-memory
3164         // is handled during type check (OCMPSTR etc).
3165         a = algtype1(t, nil);
3166         if(a != AMEM && a != -1)
3167                 fatal("eqfor %T", t);
3168
3169         if(a == AMEM) {
3170                 n = syslook("memequal", 1);
3171                 argtype(n, t);
3172                 argtype(n, t);
3173                 return n;
3174         }
3175
3176         sym = typesymprefix(".eq", t);
3177         n = newname(sym);
3178         n->class = PFUNC;
3179         ntype = nod(OTFUNC, N, N);
3180         ntype->list = list(ntype->list, nod(ODCLFIELD, N, typenod(ptrto(t))));
3181         ntype->list = list(ntype->list, nod(ODCLFIELD, N, typenod(ptrto(t))));
3182         ntype->list = list(ntype->list, nod(ODCLFIELD, N, typenod(types[TUINTPTR])));
3183         ntype->rlist = list(ntype->rlist, nod(ODCLFIELD, N, typenod(types[TBOOL])));
3184         typecheck(&ntype, Etype);
3185         n->type = ntype->type;
3186         return n;
3187 }
3188
3189 static int
3190 countfield(Type *t)
3191 {
3192         Type *t1;
3193         int n;
3194
3195         n = 0;
3196         for(t1=t->type; t1!=T; t1=t1->down)
3197                 n++;
3198         return n;
3199 }
3200
3201 static void
3202 walkcompare(Node **np, NodeList **init)
3203 {
3204         Node *n, *l, *r, *call, *a, *li, *ri, *expr, *cmpl, *cmpr;
3205         int andor, i;
3206         Type *t, *t1;
3207
3208         n = *np;
3209
3210         // Must be comparison of array or struct.
3211         // Otherwise back end handles it.
3212         t = n->left->type;
3213         switch(t->etype) {
3214         default:
3215                 return;
3216         case TARRAY:
3217                 if(isslice(t))
3218                         return;
3219                 break;
3220         case TSTRUCT:
3221                 break;
3222         }
3223
3224         cmpl = n->left;
3225         while(cmpl != N && cmpl->op == OCONVNOP)
3226                 cmpl = cmpl->left;
3227         cmpr = n->right;
3228         while(cmpr != N && cmpr->op == OCONVNOP)
3229                 cmpr = cmpr->left;
3230
3231         if(!islvalue(cmpl) || !islvalue(cmpr)) {
3232                 fatal("arguments of comparison must be lvalues - %N %N", cmpl, cmpr);
3233         }
3234
3235         l = temp(ptrto(t));
3236         a = nod(OAS, l, nod(OADDR, cmpl, N));
3237         a->right->etype = 1;  // addr does not escape
3238         typecheck(&a, Etop);
3239         *init = list(*init, a);
3240
3241         r = temp(ptrto(t));
3242         a = nod(OAS, r, nod(OADDR, cmpr, N));
3243         a->right->etype = 1;  // addr does not escape
3244         typecheck(&a, Etop);
3245         *init = list(*init, a);
3246
3247         expr = N;
3248         andor = OANDAND;
3249         if(n->op == ONE)
3250                 andor = OOROR;
3251
3252         if(t->etype == TARRAY &&
3253                 t->bound <= 4 &&
3254                 issimple[t->type->etype]) {
3255                 // Four or fewer elements of a basic type.
3256                 // Unroll comparisons.
3257                 for(i=0; i<t->bound; i++) {
3258                         li = nod(OINDEX, l, nodintconst(i));
3259                         ri = nod(OINDEX, r, nodintconst(i));
3260                         a = nod(n->op, li, ri);
3261                         if(expr == N)
3262                                 expr = a;
3263                         else
3264                                 expr = nod(andor, expr, a);
3265                 }
3266                 if(expr == N)
3267                         expr = nodbool(n->op == OEQ);
3268                 r = expr;
3269                 goto ret;
3270         }
3271
3272         if(t->etype == TSTRUCT && countfield(t) <= 4) {
3273                 // Struct of four or fewer fields.
3274                 // Inline comparisons.
3275                 for(t1=t->type; t1; t1=t1->down) {
3276                         if(isblanksym(t1->sym))
3277                                 continue;
3278                         li = nod(OXDOT, l, newname(t1->sym));
3279                         ri = nod(OXDOT, r, newname(t1->sym));
3280                         a = nod(n->op, li, ri);
3281                         if(expr == N)
3282                                 expr = a;
3283                         else
3284                                 expr = nod(andor, expr, a);
3285                 }
3286                 if(expr == N)
3287                         expr = nodbool(n->op == OEQ);
3288                 r = expr;
3289                 goto ret;
3290         }
3291
3292         // Chose not to inline.  Call equality function directly.
3293         call = nod(OCALL, eqfor(t), N);
3294         call->list = list(call->list, l);
3295         call->list = list(call->list, r);
3296         call->list = list(call->list, nodintconst(t->width));
3297         r = call;
3298         if(n->op != OEQ)
3299                 r = nod(ONOT, r, N);
3300         goto ret;
3301
3302 ret:
3303         typecheck(&r, Erv);
3304         walkexpr(&r, init);
3305         if(r->type != n->type) {
3306                 r = nod(OCONVNOP, r, N);
3307                 r->type = n->type;
3308                 r->typecheck = 1;
3309         }
3310         *np = r;
3311         return;
3312 }
3313
3314 static int
3315 samecheap(Node *a, Node *b)
3316 {
3317         Node *ar, *br;
3318         while(a != N && b != N && a->op == b->op) {
3319                 switch(a->op) {
3320                 default:
3321                         return 0;
3322                 case ONAME:
3323                         return a == b;
3324                 case ODOT:
3325                 case ODOTPTR:
3326                         ar = a->right;
3327                         br = b->right;
3328                         if(ar->op != ONAME || br->op != ONAME || ar->sym != br->sym)
3329                                 return 0;
3330                         break;
3331                 case OINDEX:
3332                         ar = a->right;
3333                         br = b->right;
3334                         if(!isconst(ar, CTINT) || !isconst(br, CTINT) || mpcmpfixfix(ar->val.u.xval, br->val.u.xval) != 0)
3335                                 return 0;
3336                         break;
3337                 }
3338                 a = a->left;
3339                 b = b->left;
3340         }
3341         return 0;
3342 }
3343
3344 static void
3345 walkrotate(Node **np)
3346 {
3347         int w, sl, sr, s;
3348         Node *l, *r;
3349         Node *n;
3350
3351         if(thechar == '9')
3352                 return;
3353
3354         n = *np;
3355
3356         // Want << | >> or >> | << or << ^ >> or >> ^ << on unsigned value.
3357         l = n->left;
3358         r = n->right;
3359         if((n->op != OOR && n->op != OXOR) ||
3360            (l->op != OLSH && l->op != ORSH) ||
3361            (r->op != OLSH && r->op != ORSH) ||
3362            n->type == T || issigned[n->type->etype] ||
3363            l->op == r->op) {
3364                 return;
3365         }
3366
3367         // Want same, side effect-free expression on lhs of both shifts.
3368         if(!samecheap(l->left, r->left))
3369                 return;
3370
3371         // Constants adding to width?
3372         w = l->type->width * 8;
3373         if(smallintconst(l->right) && smallintconst(r->right)) {
3374                 if((sl=mpgetfix(l->right->val.u.xval)) >= 0 && (sr=mpgetfix(r->right->val.u.xval)) >= 0 && sl+sr == w)
3375                         goto yes;
3376                 return;
3377         }
3378
3379         // TODO: Could allow s and 32-s if s is bounded (maybe s&31 and 32-s&31).
3380         return;
3381
3382 yes:
3383         // Rewrite left shift half to left rotate.
3384         if(l->op == OLSH)
3385                 n = l;
3386         else
3387                 n = r;
3388         n->op = OLROT;
3389
3390         // Remove rotate 0 and rotate w.
3391         s = mpgetfix(n->right->val.u.xval);
3392         if(s == 0 || s == w)
3393                 n = n->left;
3394
3395         *np = n;
3396         return;
3397 }
3398
3399 /*
3400  * walkmul rewrites integer multiplication by powers of two as shifts.
3401  */
3402 static void
3403 walkmul(Node **np, NodeList **init)
3404 {
3405         Node *n, *nl, *nr;
3406         int pow, neg, w;
3407
3408         n = *np;
3409         if(!isint[n->type->etype])
3410                 return;
3411
3412         if(n->right->op == OLITERAL) {
3413                 nl = n->left;
3414                 nr = n->right;
3415         } else if(n->left->op == OLITERAL) {
3416                 nl = n->right;
3417                 nr = n->left;
3418         } else
3419                 return;
3420
3421         neg = 0;
3422
3423         // x*0 is 0 (and side effects of x).
3424         if(mpgetfix(nr->val.u.xval) == 0) {
3425                 cheapexpr(nl, init);
3426                 nodconst(n, n->type, 0);
3427                 goto ret;
3428         }
3429
3430         // nr is a constant.
3431         pow = powtwo(nr);
3432         if(pow < 0)
3433                 return;
3434         if(pow >= 1000) {
3435                 // negative power of 2, like -16
3436                 neg = 1;
3437                 pow -= 1000;
3438         }
3439
3440         w = nl->type->width*8;
3441         if(pow+1 >= w)// too big, shouldn't happen
3442                 return;
3443
3444         nl = cheapexpr(nl, init);
3445
3446         if(pow == 0) {
3447                 // x*1 is x
3448                 n = nl;
3449                 goto ret;
3450         }
3451
3452         n = nod(OLSH, nl, nodintconst(pow));
3453
3454 ret:
3455         if(neg)
3456                 n = nod(OMINUS, n, N);
3457
3458         typecheck(&n, Erv);
3459         walkexpr(&n, init);
3460         *np = n;
3461 }
3462
3463 /*
3464  * walkdiv rewrites division by a constant as less expensive
3465  * operations.
3466  */
3467 static void
3468 walkdiv(Node **np, NodeList **init)
3469 {
3470         Node *n, *nl, *nr, *nc;
3471         Node *n1, *n2, *n3, *n4;
3472         int pow; // if >= 0, nr is 1<<pow
3473         int s; // 1 if nr is negative.
3474         int w;
3475         Type *twide;
3476         Magic m;
3477
3478         // TODO(minux)
3479         if(thechar == '9')
3480                 return;
3481
3482         n = *np;
3483         if(n->right->op != OLITERAL)
3484                 return;
3485         // nr is a constant.
3486         nl = cheapexpr(n->left, init);
3487         nr = n->right;
3488
3489         // special cases of mod/div
3490         // by a constant
3491         w = nl->type->width*8;
3492         s = 0;
3493         pow = powtwo(nr);
3494         if(pow >= 1000) {
3495                 // negative power of 2
3496                 s = 1;
3497                 pow -= 1000;
3498         }
3499
3500         if(pow+1 >= w) {
3501                 // divisor too large.
3502                 return;
3503         }
3504         if(pow < 0) {
3505                 goto divbymul;
3506         }
3507
3508         switch(pow) {
3509         case 0:
3510                 if(n->op == OMOD) {
3511                         // nl % 1 is zero.
3512                         nodconst(n, n->type, 0);
3513                 } else if(s) {
3514                         // divide by -1
3515                         n->op = OMINUS;
3516                         n->right = N;
3517                 } else {
3518                         // divide by 1
3519                         n = nl;
3520                 }
3521                 break;
3522         default:
3523                 if(issigned[n->type->etype]) {
3524                         if(n->op == OMOD) {
3525                                 // signed modulo 2^pow is like ANDing
3526                                 // with the last pow bits, but if nl < 0,
3527                                 // nl & (2^pow-1) is (nl+1)%2^pow - 1.
3528                                 nc = nod(OXXX, N, N);
3529                                 nodconst(nc, types[simtype[TUINT]], w-1);
3530                                 n1 = nod(ORSH, nl, nc); // n1 = -1 iff nl < 0.
3531                                 if(pow == 1) {
3532                                         typecheck(&n1, Erv);
3533                                         n1 = cheapexpr(n1, init);
3534                                         // n = (nl+ε)&1 -ε where ε=1 iff nl<0.
3535                                         n2 = nod(OSUB, nl, n1);
3536                                         nc = nod(OXXX, N, N);
3537                                         nodconst(nc, nl->type, 1);
3538                                         n3 = nod(OAND, n2, nc);
3539                                         n = nod(OADD, n3, n1);
3540                                 } else {
3541                                         // n = (nl+ε)&(nr-1) - ε where ε=2^pow-1 iff nl<0.
3542                                         nc = nod(OXXX, N, N);
3543                                         nodconst(nc, nl->type, (1LL<<pow)-1);
3544                                         n2 = nod(OAND, n1, nc); // n2 = 2^pow-1 iff nl<0.
3545                                         typecheck(&n2, Erv);
3546                                         n2 = cheapexpr(n2, init);
3547
3548                                         n3 = nod(OADD, nl, n2);
3549                                         n4 = nod(OAND, n3, nc);
3550                                         n = nod(OSUB, n4, n2);
3551                                 }
3552                                 break;
3553                         } else {
3554                                 // arithmetic right shift does not give the correct rounding.
3555                                 // if nl >= 0, nl >> n == nl / nr
3556                                 // if nl < 0, we want to add 2^n-1 first.
3557                                 nc = nod(OXXX, N, N);
3558                                 nodconst(nc, types[simtype[TUINT]], w-1);
3559                                 n1 = nod(ORSH, nl, nc); // n1 = -1 iff nl < 0.
3560                                 if(pow == 1) {
3561                                         // nl+1 is nl-(-1)
3562                                         n->left = nod(OSUB, nl, n1);
3563                                 } else {
3564                                         // Do a logical right right on -1 to keep pow bits.
3565                                         nc = nod(OXXX, N, N);
3566                                         nodconst(nc, types[simtype[TUINT]], w-pow);
3567                                         n2 = nod(ORSH, conv(n1, tounsigned(nl->type)), nc);
3568                                         n->left = nod(OADD, nl, conv(n2, nl->type));
3569                                 }
3570                                 // n = (nl + 2^pow-1) >> pow
3571                                 n->op = ORSH;
3572                                 nc = nod(OXXX, N, N);
3573                                 nodconst(nc, types[simtype[TUINT]], pow);
3574                                 n->right = nc;
3575                                 n->typecheck = 0;
3576                         }
3577                         if(s)
3578                                 n = nod(OMINUS, n, N);
3579                         break;
3580                 }
3581                 nc = nod(OXXX, N, N);
3582                 if(n->op == OMOD) {
3583                         // n = nl & (nr-1)
3584                         n->op = OAND;
3585                         nodconst(nc, nl->type, mpgetfix(nr->val.u.xval)-1);
3586                 } else {
3587                         // n = nl >> pow
3588                         n->op = ORSH;
3589                         nodconst(nc, types[simtype[TUINT]], pow);
3590                 }
3591                 n->typecheck = 0;
3592                 n->right = nc;
3593                 break;
3594         }
3595         goto ret;
3596
3597 divbymul:
3598         // try to do division by multiply by (2^w)/d
3599         // see hacker's delight chapter 10
3600         // TODO: support 64-bit magic multiply here.
3601         m.w = w;
3602         if(issigned[nl->type->etype]) {
3603                 m.sd = mpgetfix(nr->val.u.xval);
3604                 smagic(&m);
3605         } else {
3606                 m.ud = mpgetfix(nr->val.u.xval);
3607                 umagic(&m);
3608         }
3609         if(m.bad)
3610                 return;
3611
3612         // We have a quick division method so use it
3613         // for modulo too.
3614         if(n->op == OMOD)
3615                 goto longmod;
3616
3617         switch(simtype[nl->type->etype]) {
3618         default:
3619                 return;
3620
3621         case TUINT8:
3622         case TUINT16:
3623         case TUINT32:
3624                 // n1 = nl * magic >> w (HMUL)
3625                 nc = nod(OXXX, N, N);
3626                 nodconst(nc, nl->type, m.um);
3627                 n1 = nod(OMUL, nl, nc);
3628                 typecheck(&n1, Erv);
3629                 n1->op = OHMUL;
3630                 if(m.ua) {
3631                         // Select a Go type with (at least) twice the width.
3632                         switch(simtype[nl->type->etype]) {
3633                         default:
3634                                 return;
3635                         case TUINT8:
3636                         case TUINT16:
3637                                 twide = types[TUINT32];
3638                                 break;
3639                         case TUINT32:
3640                                 twide = types[TUINT64];
3641                                 break;
3642                         case TINT8:
3643                         case TINT16:
3644                                 twide = types[TINT32];
3645                                 break;
3646                         case TINT32:
3647                                 twide = types[TINT64];
3648                                 break;
3649                         }
3650
3651                         // add numerator (might overflow).
3652                         // n2 = (n1 + nl)
3653                         n2 = nod(OADD, conv(n1, twide), conv(nl, twide));
3654
3655                         // shift by m.s
3656                         nc = nod(OXXX, N, N);
3657                         nodconst(nc, types[TUINT], m.s);
3658                         n = conv(nod(ORSH, n2, nc), nl->type);
3659                 } else {
3660                         // n = n1 >> m.s
3661                         nc = nod(OXXX, N, N);
3662                         nodconst(nc, types[TUINT], m.s);
3663                         n = nod(ORSH, n1, nc);
3664                 }
3665                 break;
3666
3667         case TINT8:
3668         case TINT16:
3669         case TINT32:
3670                 // n1 = nl * magic >> w
3671                 nc = nod(OXXX, N, N);
3672                 nodconst(nc, nl->type, m.sm);
3673                 n1 = nod(OMUL, nl, nc);
3674                 typecheck(&n1, Erv);
3675                 n1->op = OHMUL;
3676                 if(m.sm < 0) {
3677                         // add the numerator.
3678                         n1 = nod(OADD, n1, nl);
3679                 }
3680                 // shift by m.s
3681                 nc = nod(OXXX, N, N);
3682                 nodconst(nc, types[TUINT], m.s);
3683                 n2 = conv(nod(ORSH, n1, nc), nl->type);
3684                 // add 1 iff n1 is negative.
3685                 nc = nod(OXXX, N, N);
3686                 nodconst(nc, types[TUINT], w-1);
3687                 n3 = nod(ORSH, nl, nc); // n4 = -1 iff n1 is negative.
3688                 n = nod(OSUB, n2, n3);
3689                 // apply sign.
3690                 if(m.sd < 0)
3691                         n = nod(OMINUS, n, N);
3692                 break;
3693         }
3694         goto ret;
3695
3696 longmod:
3697         // rewrite as A%B = A - (A/B*B).
3698         n1 = nod(ODIV, nl, nr);
3699         n2 = nod(OMUL, n1, nr);
3700         n = nod(OSUB, nl, n2);
3701         goto ret;
3702
3703 ret:
3704         typecheck(&n, Erv);
3705         walkexpr(&n, init);
3706         *np = n;
3707 }
3708
3709 // return 1 if integer n must be in range [0, max), 0 otherwise
3710 static int
3711 bounded(Node *n, int64 max)
3712 {
3713         int64 v;
3714         int32 bits;
3715         int sign;
3716
3717         if(n->type == T || !isint[n->type->etype])
3718                 return 0;
3719
3720         sign = issigned[n->type->etype];
3721         bits = 8*n->type->width;
3722
3723         if(smallintconst(n)) {
3724                 v = mpgetfix(n->val.u.xval);
3725                 return 0 <= v && v < max;
3726         }
3727
3728         switch(n->op) {
3729         case OAND:
3730                 v = -1;
3731                 if(smallintconst(n->left)) {
3732                         v = mpgetfix(n->left->val.u.xval);
3733                 } else if(smallintconst(n->right)) {
3734                         v = mpgetfix(n->right->val.u.xval);
3735                 }
3736                 if(0 <= v && v < max)
3737                         return 1;
3738                 break;
3739
3740         case OMOD:
3741                 if(!sign && smallintconst(n->right)) {
3742                         v = mpgetfix(n->right->val.u.xval);
3743                         if(0 <= v && v <= max)
3744                                 return 1;
3745                 }
3746                 break;
3747
3748         case ODIV:
3749                 if(!sign && smallintconst(n->right)) {
3750                         v = mpgetfix(n->right->val.u.xval);
3751                         while(bits > 0 && v >= 2) {
3752                                 bits--;
3753                                 v >>= 1;
3754                         }
3755                 }
3756                 break;
3757
3758         case ORSH:
3759                 if(!sign && smallintconst(n->right)) {
3760                         v = mpgetfix(n->right->val.u.xval);
3761                         if(v > bits)
3762                                 return 1;
3763                         bits -= v;
3764                 }
3765                 break;
3766         }
3767
3768         if(!sign && bits <= 62 && (1LL<<bits) <= max)
3769                 return 1;
3770
3771         return 0;
3772 }
3773
3774 void
3775 usefield(Node *n)
3776 {
3777         Type *field, *l;
3778
3779         if(!fieldtrack_enabled)
3780                 return;
3781
3782         switch(n->op) {
3783         default:
3784                 fatal("usefield %O", n->op);
3785         case ODOT:
3786         case ODOTPTR:
3787                 break;
3788         }
3789
3790         field = n->paramfld;
3791         if(field == T)
3792                 fatal("usefield %T %S without paramfld", n->left->type, n->right->sym);
3793         if(field->note == nil || strstr(field->note->s, "go:\"track\"") == nil)
3794                 return;
3795
3796         // dedup on list
3797         if(field->lastfn == curfn)
3798                 return;
3799         field->lastfn = curfn;
3800         field->outer = n->left->type;
3801         if(isptr[field->outer->etype])
3802                 field->outer = field->outer->type;
3803         if(field->outer->sym == S)
3804                 yyerror("tracked field must be in named struct type");
3805         if(!exportname(field->sym->name))
3806                 yyerror("tracked field must be exported (upper case)");
3807
3808         l = typ(0);
3809         l->type = field;
3810         l->down = curfn->paramfld;
3811         curfn->paramfld = l;
3812 }
3813
3814 static int
3815 candiscardlist(NodeList *l)
3816 {
3817         for(; l; l=l->next)
3818                 if(!candiscard(l->n))
3819                         return 0;
3820         return 1;
3821 }
3822
3823 int
3824 candiscard(Node *n)
3825 {
3826         if(n == N)
3827                 return 1;
3828
3829         switch(n->op) {
3830         default:
3831                 return 0;
3832
3833         case ONAME:
3834         case ONONAME:
3835         case OTYPE:
3836         case OPACK:
3837         case OLITERAL:
3838         case OADD:
3839         case OSUB:
3840         case OOR:
3841         case OXOR:
3842         case OADDSTR:
3843         case OADDR:
3844         case OANDAND:
3845         case OARRAYBYTESTR:
3846         case OARRAYRUNESTR:
3847         case OSTRARRAYBYTE:
3848         case OSTRARRAYRUNE:
3849         case OCAP:
3850         case OCMPIFACE:
3851         case OCMPSTR:
3852         case OCOMPLIT:
3853         case OMAPLIT:
3854         case OSTRUCTLIT:
3855         case OARRAYLIT:
3856         case OPTRLIT:
3857         case OCONV:
3858         case OCONVIFACE:
3859         case OCONVNOP:
3860         case ODOT:
3861         case OEQ:
3862         case ONE:
3863         case OLT:
3864         case OLE:
3865         case OGT:
3866         case OGE:
3867         case OKEY:
3868         case OLEN:
3869         case OMUL:
3870         case OLSH:
3871         case ORSH:
3872         case OAND:
3873         case OANDNOT:
3874         case ONEW:
3875         case ONOT:
3876         case OCOM:
3877         case OPLUS:
3878         case OMINUS:
3879         case OOROR:
3880         case OPAREN:
3881         case ORUNESTR:
3882         case OREAL:
3883         case OIMAG:
3884         case OCOMPLEX:
3885                 // Discardable as long as the subpieces are.
3886                 break;
3887
3888         case ODIV:
3889         case OMOD:
3890                 // Discardable as long as we know it's not division by zero.
3891                 if(isconst(n->right, CTINT) && mpcmpfixc(n->right->val.u.xval, 0) != 0)
3892                         break;
3893                 if(isconst(n->right, CTFLT) && mpcmpfltc(n->right->val.u.fval, 0) != 0)
3894                         break;
3895                 return 0;
3896
3897         case OMAKECHAN:
3898         case OMAKEMAP:
3899                 // Discardable as long as we know it won't fail because of a bad size.
3900                 if(isconst(n->left, CTINT) && mpcmpfixc(n->left->val.u.xval, 0) == 0)
3901                         break;
3902                 return 0;
3903
3904         case OMAKESLICE:
3905                 // Difficult to tell what sizes are okay.
3906                 return 0;
3907         }
3908
3909         if(!candiscard(n->left) ||
3910            !candiscard(n->right) ||
3911            !candiscard(n->ntest) ||
3912            !candiscard(n->nincr) ||
3913            !candiscardlist(n->ninit) ||
3914            !candiscardlist(n->nbody) ||
3915            !candiscardlist(n->nelse) ||
3916            !candiscardlist(n->list) ||
3917            !candiscardlist(n->rlist)) {
3918                 return 0;
3919         }
3920
3921         return 1;
3922 }
3923
3924 // rewrite
3925 //      print(x, y, z)
3926 // into
3927 //      func(a1, a2, a3) {
3928 //              print(a1, a2, a3)
3929 //      }(x, y, z)
3930 // and same for println.
3931 static void
3932 walkprintfunc(Node **np, NodeList **init)
3933 {
3934         Node *n;
3935         Node *a, *fn, *t, *oldfn;
3936         NodeList *l, *printargs;
3937         int num;
3938         char buf[100];
3939         static int prgen;
3940
3941         n = *np;
3942
3943         if(n->ninit != nil) {
3944                 walkstmtlist(n->ninit);
3945                 *init = concat(*init, n->ninit);
3946                 n->ninit = nil;
3947         }
3948
3949         t = nod(OTFUNC, N, N);
3950         num = 0;
3951         printargs = nil;
3952         for(l=n->list; l != nil; l=l->next) {
3953                 snprint(buf, sizeof buf, "a%d", num++);
3954                 a = nod(ODCLFIELD, newname(lookup(buf)), typenod(l->n->type));
3955                 t->list = list(t->list, a);
3956                 printargs = list(printargs, a->left);
3957         }
3958
3959         fn = nod(ODCLFUNC, N, N);
3960         snprint(buf, sizeof buf, "print·%d", ++prgen);
3961         fn->nname = newname(lookup(buf));
3962         fn->nname->defn = fn;
3963         fn->nname->ntype = t;
3964         declare(fn->nname, PFUNC);
3965
3966         oldfn = curfn;
3967         curfn = nil;
3968         funchdr(fn);
3969
3970         a = nod(n->op, N, N);
3971         a->list = printargs;
3972         typecheck(&a, Etop);
3973         walkstmt(&a);
3974
3975         fn->nbody = list1(a);
3976
3977         funcbody(fn);
3978
3979         typecheck(&fn, Etop);
3980         typechecklist(fn->nbody, Etop);
3981         xtop = list(xtop, fn);
3982         curfn = oldfn;
3983
3984         a = nod(OCALL, N, N);
3985         a->left = fn->nname;
3986         a->list = n->list;
3987         typecheck(&a, Etop);
3988         walkexpr(&a, init);
3989         *np = a;
3990 }