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