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