src/cmd/compile/internal/gc/walk.go

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