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