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

   1 // Copyright 2012 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         "fmt"
   9         "strings"
  10 )
  11
  12 // Rewrite tree to use separate statements to enforce
  13 // order of evaluation.  Makes walk easier, because it
  14 // can (after this runs) reorder at will within an expression.
  15 //
  16 // Rewrite x op= y into x = x op y.
  17 //
  18 // Introduce temporaries as needed by runtime routines.
  19 // For example, the map runtime routines take the map key
  20 // by reference, so make sure all map keys are addressable
  21 // by copying them to temporaries as needed.
  22 // The same is true for channel operations.
  23 //
  24 // Arrange that map index expressions only appear in direct
  25 // assignments x = m[k] or m[k] = x, never in larger expressions.
  26 //
  27 // Arrange that receive expressions only appear in direct assignments
  28 // x = <-c or as standalone statements <-c, never in larger expressions.
  29
  30 // TODO(rsc): The temporary introduction during multiple assignments
  31 // should be moved into this file, so that the temporaries can be cleaned
  32 // and so that conversions implicit in the OAS2FUNC and OAS2RECV
  33 // nodes can be made explicit and then have their temporaries cleaned.
  34
  35 // TODO(rsc): Goto and multilevel break/continue can jump over
  36 // inserted VARKILL annotations. Work out a way to handle these.
  37 // The current implementation is safe, in that it will execute correctly.
  38 // But it won't reuse temporaries as aggressively as it might, and
  39 // it can result in unnecessary zeroing of those variables in the function
  40 // prologue.
  41
  42 // Order holds state during the ordering process.
  43 type Order struct {
  44         out  *NodeList // list of generated statements
  45         temp []*Node   // stack of temporary variables
  46 }
  47
  48 // Order rewrites fn->nbody to apply the ordering constraints
  49 // described in the comment at the top of the file.
  50 func order(fn *Node) {
  51         if Debug['W'] > 1 {
  52                 s := fmt.Sprintf("\nbefore order %v", fn.Func.Nname.Sym)
  53                 dumplist(s, fn.Nbody)
  54         }
  55
  56         orderblock(&fn.Nbody)
  57 }
  58
  59 // Ordertemp allocates a new temporary with the given type,
  60 // pushes it onto the temp stack, and returns it.
  61 // If clear is true, ordertemp emits code to zero the temporary.
  62 func ordertemp(t *Type, order *Order, clear bool) *Node {
  63         var_ := temp(t)
  64         if clear {
  65                 a := Nod(OAS, var_, nil)
  66                 typecheck(&a, Etop)
  67                 order.out = list(order.out, a)
  68         }
  69
  70         order.temp = append(order.temp, var_)
  71         return var_
  72 }
  73
  74 // Ordercopyexpr behaves like ordertemp but also emits
  75 // code to initialize the temporary to the value n.
  76 //
  77 // The clear argument is provided for use when the evaluation
  78 // of tmp = n turns into a function call that is passed a pointer
  79 // to the temporary as the output space. If the call blocks before
  80 // tmp has been written, the garbage collector will still treat the
  81 // temporary as live, so we must zero it before entering that call.
  82 // Today, this only happens for channel receive operations.
  83 // (The other candidate would be map access, but map access
  84 // returns a pointer to the result data instead of taking a pointer
  85 // to be filled in.)
  86 func ordercopyexpr(n *Node, t *Type, order *Order, clear int) *Node {
  87         var_ := ordertemp(t, order, clear != 0)
  88         a := Nod(OAS, var_, n)
  89         typecheck(&a, Etop)
  90         order.out = list(order.out, a)
  91         return var_
  92 }
  93
  94 // Ordercheapexpr returns a cheap version of n.
  95 // The definition of cheap is that n is a variable or constant.
  96 // If not, ordercheapexpr allocates a new tmp, emits tmp = n,
  97 // and then returns tmp.
  98 func ordercheapexpr(n *Node, order *Order) *Node {
  99         if n == nil {
 100                 return nil
 101         }
 102         switch n.Op {
 103         case ONAME, OLITERAL:
 104                 return n
 105         case OLEN, OCAP:
 106                 l := ordercheapexpr(n.Left, order)
 107                 if l == n.Left {
 108                         return n
 109                 }
 110                 a := Nod(OXXX, nil, nil)
 111                 *a = *n
 112                 a.Orig = a
 113                 a.Left = l
 114                 typecheck(&a, Erv)
 115                 return a
 116         }
 117
 118         return ordercopyexpr(n, n.Type, order, 0)
 119 }
 120
 121 // Ordersafeexpr returns a safe version of n.
 122 // The definition of safe is that n can appear multiple times
 123 // without violating the semantics of the original program,
 124 // and that assigning to the safe version has the same effect
 125 // as assigning to the original n.
 126 //
 127 // The intended use is to apply to x when rewriting x += y into x = x + y.
 128 func ordersafeexpr(n *Node, order *Order) *Node {
 129         switch n.Op {
 130         case ONAME, OLITERAL:
 131                 return n
 132
 133         case ODOT, OLEN, OCAP:
 134                 l := ordersafeexpr(n.Left, order)
 135                 if l == n.Left {
 136                         return n
 137                 }
 138                 a := Nod(OXXX, nil, nil)
 139                 *a = *n
 140                 a.Orig = a
 141                 a.Left = l
 142                 typecheck(&a, Erv)
 143                 return a
 144
 145         case ODOTPTR, OIND:
 146                 l := ordercheapexpr(n.Left, order)
 147                 if l == n.Left {
 148                         return n
 149                 }
 150                 a := Nod(OXXX, nil, nil)
 151                 *a = *n
 152                 a.Orig = a
 153                 a.Left = l
 154                 typecheck(&a, Erv)
 155                 return a
 156
 157         case OINDEX, OINDEXMAP:
 158                 var l *Node
 159                 if Isfixedarray(n.Left.Type) {
 160                         l = ordersafeexpr(n.Left, order)
 161                 } else {
 162                         l = ordercheapexpr(n.Left, order)
 163                 }
 164                 r := ordercheapexpr(n.Right, order)
 165                 if l == n.Left && r == n.Right {
 166                         return n
 167                 }
 168                 a := Nod(OXXX, nil, nil)
 169                 *a = *n
 170                 a.Orig = a
 171                 a.Left = l
 172                 a.Right = r
 173                 typecheck(&a, Erv)
 174                 return a
 175         }
 176
 177         Fatalf("ordersafeexpr %v", Oconv(int(n.Op), 0))
 178         return nil // not reached
 179 }
 180
 181 // Istemp reports whether n is a temporary variable.
 182 func istemp(n *Node) bool {
 183         if n.Op != ONAME {
 184                 return false
 185         }
 186         return strings.HasPrefix(n.Sym.Name, "autotmp_")
 187 }
 188
 189 // Isaddrokay reports whether it is okay to pass n's address to runtime routines.
 190 // Taking the address of a variable makes the liveness and optimization analyses
 191 // lose track of where the variable's lifetime ends. To avoid hurting the analyses
 192 // of ordinary stack variables, those are not 'isaddrokay'. Temporaries are okay,
 193 // because we emit explicit VARKILL instructions marking the end of those
 194 // temporaries' lifetimes.
 195 func isaddrokay(n *Node) bool {
 196         return islvalue(n) && (n.Op != ONAME || n.Class == PEXTERN || istemp(n))
 197 }
 198
 199 // Orderaddrtemp ensures that *np is okay to pass by address to runtime routines.
 200 // If the original argument *np is not okay, orderaddrtemp creates a tmp, emits
 201 // tmp = *np, and then sets *np to the tmp variable.
 202 func orderaddrtemp(np **Node, order *Order) {
 203         n := *np
 204         if isaddrokay(n) {
 205                 return
 206         }
 207         *np = ordercopyexpr(n, n.Type, order, 0)
 208 }
 209
 210 type ordermarker int
 211
 212 // Marktemp returns the top of the temporary variable stack.
 213 func marktemp(order *Order) ordermarker {
 214         return ordermarker(len(order.temp))
 215 }
 216
 217 // Poptemp pops temporaries off the stack until reaching the mark,
 218 // which must have been returned by marktemp.
 219 func poptemp(mark ordermarker, order *Order) {
 220         order.temp = order.temp[:mark]
 221 }
 222
 223 // Cleantempnopop emits to *out VARKILL instructions for each temporary
 224 // above the mark on the temporary stack, but it does not pop them
 225 // from the stack.
 226 func cleantempnopop(mark ordermarker, order *Order, out **NodeList) {
 227         var kill *Node
 228
 229         for i := len(order.temp) - 1; i >= int(mark); i-- {
 230                 n := order.temp[i]
 231                 if n.Name.Keepalive {
 232                         n.Name.Keepalive = false
 233                         n.Addrtaken = true // ensure SSA keeps the n variable
 234                         kill = Nod(OVARLIVE, n, nil)
 235                         typecheck(&kill, Etop)
 236                         *out = list(*out, kill)
 237                 }
 238                 kill = Nod(OVARKILL, n, nil)
 239                 typecheck(&kill, Etop)
 240                 *out = list(*out, kill)
 241         }
 242 }
 243
 244 // Cleantemp emits VARKILL instructions for each temporary above the
 245 // mark on the temporary stack and removes them from the stack.
 246 func cleantemp(top ordermarker, order *Order) {
 247         cleantempnopop(top, order, &order.out)
 248         poptemp(top, order)
 249 }
 250
 251 // Orderstmtlist orders each of the statements in the list.
 252 func orderstmtlist(l *NodeList, order *Order) {
 253         for ; l != nil; l = l.Next {
 254                 orderstmt(l.N, order)
 255         }
 256 }
 257
 258 // Orderblock orders the block of statements *l onto a new list,
 259 // and then replaces *l with that list.
 260 func orderblock(l **NodeList) {
 261         var order Order
 262         mark := marktemp(&order)
 263         orderstmtlist(*l, &order)
 264         cleantemp(mark, &order)
 265         *l = order.out
 266 }
 267
 268 // Orderexprinplace orders the side effects in *np and
 269 // leaves them as the init list of the final *np.
 270 func orderexprinplace(np **Node, outer *Order) {
 271         n := *np
 272         var order Order
 273         orderexpr(&n, &order, nil)
 274         addinit(&n, order.out)
 275
 276         // insert new temporaries from order
 277         // at head of outer list.
 278         outer.temp = append(outer.temp, order.temp...)
 279
 280         *np = n
 281 }
 282
 283 // Orderstmtinplace orders the side effects of the single statement *np
 284 // and replaces it with the resulting statement list.
 285 func orderstmtinplace(np **Node) {
 286         n := *np
 287         var order Order
 288         mark := marktemp(&order)
 289         orderstmt(n, &order)
 290         cleantemp(mark, &order)
 291         *np = liststmt(order.out)
 292 }
 293
 294 // Orderinit moves n's init list to order->out.
 295 func orderinit(n *Node, order *Order) {
 296         orderstmtlist(n.Ninit, order)
 297         n.Ninit = nil
 298 }
 299
 300 // Ismulticall reports whether the list l is f() for a multi-value function.
 301 // Such an f() could appear as the lone argument to a multi-arg function.
 302 func ismulticall(l *NodeList) bool {
 303         // one arg only
 304         if l == nil || l.Next != nil {
 305                 return false
 306         }
 307         n := l.N
 308
 309         // must be call
 310         switch n.Op {
 311         default:
 312                 return false
 313
 314         case OCALLFUNC, OCALLMETH, OCALLINTER:
 315                 break
 316         }
 317
 318         // call must return multiple values
 319         return n.Left.Type.Outtuple > 1
 320 }
 321
 322 // Copyret emits t1, t2, ... = n, where n is a function call,
 323 // and then returns the list t1, t2, ....
 324 func copyret(n *Node, order *Order) *NodeList {
 325         if n.Type.Etype != TSTRUCT || !n.Type.Funarg {
 326                 Fatalf("copyret %v %d", n.Type, n.Left.Type.Outtuple)
 327         }
 328
 329         var l1 *NodeList
 330         var l2 *NodeList
 331         var tl Iter
 332         var tmp *Node
 333         for t := Structfirst(&tl, &n.Type); t != nil; t = structnext(&tl) {
 334                 tmp = temp(t.Type)
 335                 l1 = list(l1, tmp)
 336                 l2 = list(l2, tmp)
 337         }
 338
 339         as := Nod(OAS2, nil, nil)
 340         as.List = l1
 341         as.Rlist = list1(n)
 342         typecheck(&as, Etop)
 343         orderstmt(as, order)
 344
 345         return l2
 346 }
 347
 348 // Ordercallargs orders the list of call arguments *l.
 349 func ordercallargs(l **NodeList, order *Order) {
 350         if ismulticall(*l) {
 351                 // return f() where f() is multiple values.
 352                 *l = copyret((*l).N, order)
 353         } else {
 354                 orderexprlist(*l, order)
 355         }
 356 }
 357
 358 // Ordercall orders the call expression n.
 359 // n->op is OCALLMETH/OCALLFUNC/OCALLINTER or a builtin like OCOPY.
 360 func ordercall(n *Node, order *Order) {
 361         orderexpr(&n.Left, order, nil)
 362         orderexpr(&n.Right, order, nil) // ODDDARG temp
 363         ordercallargs(&n.List, order)
 364
 365         if n.Op == OCALLFUNC {
 366                 for l, t := n.List, getinargx(n.Left.Type).Type; l != nil && t != nil; l, t = l.Next, t.Down {
 367                         // Check for "unsafe-uintptr" tag provided by escape analysis.
 368                         // If present and the argument is really a pointer being converted
 369                         // to uintptr, arrange for the pointer to be kept alive until the call
 370                         // returns, by copying it into a temp and marking that temp
 371                         // still alive when we pop the temp stack.
 372                         if t.Note != nil && *t.Note == unsafeUintptrTag {
 373                                 xp := &l.N
 374                                 for (*xp).Op == OCONVNOP && !Isptr[(*xp).Type.Etype] {
 375                                         xp = &(*xp).Left
 376                                 }
 377                                 x := *xp
 378                                 if Isptr[x.Type.Etype] {
 379                                         x = ordercopyexpr(x, x.Type, order, 0)
 380                                         x.Name.Keepalive = true
 381                                         *xp = x
 382                                 }
 383                         }
 384                 }
 385         }
 386 }
 387
 388 // Ordermapassign appends n to order->out, introducing temporaries
 389 // to make sure that all map assignments have the form m[k] = x,
 390 // where x is addressable.
 391 // (Orderexpr has already been called on n, so we know k is addressable.)
 392 //
 393 // If n is m[k] = x where x is not addressable, the rewrite is:
 394 //      tmp = x
 395 //      m[k] = tmp
 396 //
 397 // If n is the multiple assignment form ..., m[k], ... = ..., the rewrite is
 398 //      t1 = m
 399 //      t2 = k
 400 //      ...., t3, ... = x
 401 //      t1[t2] = t3
 402 //
 403 // The temporaries t1, t2 are needed in case the ... being assigned
 404 // contain m or k. They are usually unnecessary, but in the unnecessary
 405 // cases they are also typically registerizable, so not much harm done.
 406 // And this only applies to the multiple-assignment form.
 407 // We could do a more precise analysis if needed, like in walk.go.
 408 //
 409 // Ordermapassign also inserts these temporaries if needed for
 410 // calling writebarrierfat with a pointer to n->right.
 411 func ordermapassign(n *Node, order *Order) {
 412         switch n.Op {
 413         default:
 414                 Fatalf("ordermapassign %v", Oconv(int(n.Op), 0))
 415
 416         case OAS:
 417                 order.out = list(order.out, n)
 418
 419                 // We call writebarrierfat only for values > 4 pointers long. See walk.go.
 420                 if (n.Left.Op == OINDEXMAP || (needwritebarrier(n.Left, n.Right) && n.Left.Type.Width > int64(4*Widthptr))) && !isaddrokay(n.Right) {
 421                         m := n.Left
 422                         n.Left = ordertemp(m.Type, order, false)
 423                         a := Nod(OAS, m, n.Left)
 424                         typecheck(&a, Etop)
 425                         order.out = list(order.out, a)
 426                 }
 427
 428         case OAS2, OAS2DOTTYPE, OAS2MAPR, OAS2FUNC:
 429                 var post *NodeList
 430                 var m *Node
 431                 var a *Node
 432                 for l := n.List; l != nil; l = l.Next {
 433                         if l.N.Op == OINDEXMAP {
 434                                 m = l.N
 435                                 if !istemp(m.Left) {
 436                                         m.Left = ordercopyexpr(m.Left, m.Left.Type, order, 0)
 437                                 }
 438                                 if !istemp(m.Right) {
 439                                         m.Right = ordercopyexpr(m.Right, m.Right.Type, order, 0)
 440                                 }
 441                                 l.N = ordertemp(m.Type, order, false)
 442                                 a = Nod(OAS, m, l.N)
 443                                 typecheck(&a, Etop)
 444                                 post = list(post, a)
 445                         } else if instrumenting && n.Op == OAS2FUNC && !isblank(l.N) {
 446                                 m = l.N
 447                                 l.N = ordertemp(m.Type, order, false)
 448                                 a = Nod(OAS, m, l.N)
 449                                 typecheck(&a, Etop)
 450                                 post = list(post, a)
 451                         }
 452                 }
 453
 454                 order.out = list(order.out, n)
 455                 order.out = concat(order.out, post)
 456         }
 457 }
 458
 459 // Orderstmt orders the statement n, appending to order->out.
 460 // Temporaries created during the statement are cleaned
 461 // up using VARKILL instructions as possible.
 462 func orderstmt(n *Node, order *Order) {
 463         if n == nil {
 464                 return
 465         }
 466
 467         lno := int(setlineno(n))
 468
 469         orderinit(n, order)
 470
 471         switch n.Op {
 472         default:
 473                 Fatalf("orderstmt %v", Oconv(int(n.Op), 0))
 474
 475         case OVARKILL, OVARLIVE:
 476                 order.out = list(order.out, n)
 477
 478         case OAS:
 479                 t := marktemp(order)
 480                 orderexpr(&n.Left, order, nil)
 481                 orderexpr(&n.Right, order, n.Left)
 482                 ordermapassign(n, order)
 483                 cleantemp(t, order)
 484
 485         case OAS2,
 486                 OCLOSE,
 487                 OCOPY,
 488                 OPRINT,
 489                 OPRINTN,
 490                 ORECOVER,
 491                 ORECV:
 492                 t := marktemp(order)
 493                 orderexpr(&n.Left, order, nil)
 494                 orderexpr(&n.Right, order, nil)
 495                 orderexprlist(n.List, order)
 496                 orderexprlist(n.Rlist, order)
 497                 switch n.Op {
 498                 case OAS2, OAS2DOTTYPE:
 499                         ordermapassign(n, order)
 500                 default:
 501                         order.out = list(order.out, n)
 502                 }
 503                 cleantemp(t, order)
 504
 505         case OASOP:
 506                 // Special: rewrite l op= r into l = l op r.
 507                 // This simplifies quite a few operations;
 508                 // most important is that it lets us separate
 509                 // out map read from map write when l is
 510                 // a map index expression.
 511                 t := marktemp(order)
 512
 513                 orderexpr(&n.Left, order, nil)
 514                 n.Left = ordersafeexpr(n.Left, order)
 515                 tmp1 := treecopy(n.Left, 0)
 516                 if tmp1.Op == OINDEXMAP {
 517                         tmp1.Etype = 0 // now an rvalue not an lvalue
 518                 }
 519                 tmp1 = ordercopyexpr(tmp1, n.Left.Type, order, 0)
 520                 // TODO(marvin): Fix Node.EType type union.
 521                 n.Right = Nod(Op(n.Etype), tmp1, n.Right)
 522                 typecheck(&n.Right, Erv)
 523                 orderexpr(&n.Right, order, nil)
 524                 n.Etype = 0
 525                 n.Op = OAS
 526                 ordermapassign(n, order)
 527                 cleantemp(t, order)
 528
 529                 // Special: make sure key is addressable,
 530         // and make sure OINDEXMAP is not copied out.
 531         case OAS2MAPR:
 532                 t := marktemp(order)
 533
 534                 orderexprlist(n.List, order)
 535                 r := n.Rlist.N
 536                 orderexpr(&r.Left, order, nil)
 537                 orderexpr(&r.Right, order, nil)
 538
 539                 // See case OINDEXMAP below.
 540                 if r.Right.Op == OARRAYBYTESTR {
 541                         r.Right.Op = OARRAYBYTESTRTMP
 542                 }
 543                 orderaddrtemp(&r.Right, order)
 544                 ordermapassign(n, order)
 545                 cleantemp(t, order)
 546
 547                 // Special: avoid copy of func call n->rlist->n.
 548         case OAS2FUNC:
 549                 t := marktemp(order)
 550
 551                 orderexprlist(n.List, order)
 552                 ordercall(n.Rlist.N, order)
 553                 ordermapassign(n, order)
 554                 cleantemp(t, order)
 555
 556                 // Special: use temporary variables to hold result,
 557         // so that assertI2Tetc can take address of temporary.
 558         // No temporary for blank assignment.
 559         case OAS2DOTTYPE:
 560                 t := marktemp(order)
 561
 562                 orderexprlist(n.List, order)
 563                 orderexpr(&n.Rlist.N.Left, order, nil) // i in i.(T)
 564                 if isblank(n.List.N) {
 565                         order.out = list(order.out, n)
 566                 } else {
 567                         typ := n.Rlist.N.Type
 568                         tmp1 := ordertemp(typ, order, haspointers(typ))
 569                         order.out = list(order.out, n)
 570                         r := Nod(OAS, n.List.N, tmp1)
 571                         typecheck(&r, Etop)
 572                         ordermapassign(r, order)
 573                         n.List = list(list1(tmp1), n.List.Next.N)
 574                 }
 575
 576                 cleantemp(t, order)
 577
 578                 // Special: use temporary variables to hold result,
 579         // so that chanrecv can take address of temporary.
 580         case OAS2RECV:
 581                 t := marktemp(order)
 582
 583                 orderexprlist(n.List, order)
 584                 orderexpr(&n.Rlist.N.Left, order, nil) // arg to recv
 585                 ch := n.Rlist.N.Left.Type
 586                 tmp1 := ordertemp(ch.Type, order, haspointers(ch.Type))
 587                 var tmp2 *Node
 588                 if !isblank(n.List.Next.N) {
 589                         tmp2 = ordertemp(n.List.Next.N.Type, order, false)
 590                 } else {
 591                         tmp2 = ordertemp(Types[TBOOL], order, false)
 592                 }
 593                 order.out = list(order.out, n)
 594                 r := Nod(OAS, n.List.N, tmp1)
 595                 typecheck(&r, Etop)
 596                 ordermapassign(r, order)
 597                 r = Nod(OAS, n.List.Next.N, tmp2)
 598                 typecheck(&r, Etop)
 599                 ordermapassign(r, order)
 600                 n.List = list(list1(tmp1), tmp2)
 601                 cleantemp(t, order)
 602
 603                 // Special: does not save n onto out.
 604         case OBLOCK, OEMPTY:
 605                 orderstmtlist(n.List, order)
 606
 607                 // Special: n->left is not an expression; save as is.
 608         case OBREAK,
 609                 OCONTINUE,
 610                 ODCL,
 611                 ODCLCONST,
 612                 ODCLTYPE,
 613                 OFALL,
 614                 OXFALL,
 615                 OGOTO,
 616                 OLABEL,
 617                 ORETJMP:
 618                 order.out = list(order.out, n)
 619
 620                 // Special: handle call arguments.
 621         case OCALLFUNC, OCALLINTER, OCALLMETH:
 622                 t := marktemp(order)
 623
 624                 ordercall(n, order)
 625                 order.out = list(order.out, n)
 626                 cleantemp(t, order)
 627
 628                 // Special: order arguments to inner call but not call itself.
 629         case ODEFER, OPROC:
 630                 t := marktemp(order)
 631
 632                 switch n.Left.Op {
 633                 // Delete will take the address of the key.
 634                 // Copy key into new temp and do not clean it
 635                 // (it persists beyond the statement).
 636                 case ODELETE:
 637                         orderexprlist(n.Left.List, order)
 638
 639                         t1 := marktemp(order)
 640                         np := &n.Left.List.Next.N // map key
 641                         *np = ordercopyexpr(*np, (*np).Type, order, 0)
 642                         poptemp(t1, order)
 643
 644                 default:
 645                         ordercall(n.Left, order)
 646                 }
 647
 648                 order.out = list(order.out, n)
 649                 cleantemp(t, order)
 650
 651         case ODELETE:
 652                 t := marktemp(order)
 653                 orderexpr(&n.List.N, order, nil)
 654                 orderexpr(&n.List.Next.N, order, nil)
 655                 orderaddrtemp(&n.List.Next.N, order) // map key
 656                 order.out = list(order.out, n)
 657                 cleantemp(t, order)
 658
 659                 // Clean temporaries from condition evaluation at
 660         // beginning of loop body and after for statement.
 661         case OFOR:
 662                 t := marktemp(order)
 663
 664                 orderexprinplace(&n.Left, order)
 665                 var l *NodeList
 666                 cleantempnopop(t, order, &l)
 667                 n.Nbody = concat(l, n.Nbody)
 668                 orderblock(&n.Nbody)
 669                 orderstmtinplace(&n.Right)
 670                 order.out = list(order.out, n)
 671                 cleantemp(t, order)
 672
 673                 // Clean temporaries from condition at
 674         // beginning of both branches.
 675         case OIF:
 676                 t := marktemp(order)
 677
 678                 orderexprinplace(&n.Left, order)
 679                 var l *NodeList
 680                 cleantempnopop(t, order, &l)
 681                 n.Nbody = concat(l, n.Nbody)
 682                 l = nil
 683                 cleantempnopop(t, order, &l)
 684                 n.Rlist = concat(l, n.Rlist)
 685                 poptemp(t, order)
 686                 orderblock(&n.Nbody)
 687                 orderblock(&n.Rlist)
 688                 order.out = list(order.out, n)
 689
 690                 // Special: argument will be converted to interface using convT2E
 691         // so make sure it is an addressable temporary.
 692         case OPANIC:
 693                 t := marktemp(order)
 694
 695                 orderexpr(&n.Left, order, nil)
 696                 if !Isinter(n.Left.Type) {
 697                         orderaddrtemp(&n.Left, order)
 698                 }
 699                 order.out = list(order.out, n)
 700                 cleantemp(t, order)
 701
 702                 // n->right is the expression being ranged over.
 703         // order it, and then make a copy if we need one.
 704         // We almost always do, to ensure that we don't
 705         // see any value changes made during the loop.
 706         // Usually the copy is cheap (e.g., array pointer, chan, slice, string are all tiny).
 707         // The exception is ranging over an array value (not a slice, not a pointer to array),
 708         // which must make a copy to avoid seeing updates made during
 709         // the range body. Ranging over an array value is uncommon though.
 710         case ORANGE:
 711                 t := marktemp(order)
 712
 713                 orderexpr(&n.Right, order, nil)
 714                 switch n.Type.Etype {
 715                 default:
 716                         Fatalf("orderstmt range %v", n.Type)
 717
 718                         // Mark []byte(str) range expression to reuse string backing storage.
 719                 // It is safe because the storage cannot be mutated.
 720                 case TARRAY:
 721                         if n.Right.Op == OSTRARRAYBYTE {
 722                                 n.Right.Op = OSTRARRAYBYTETMP
 723                         }
 724                         if count(n.List) < 2 || isblank(n.List.Next.N) {
 725                                 // for i := range x will only use x once, to compute len(x).
 726                                 // No need to copy it.
 727                                 break
 728                         }
 729                         fallthrough
 730
 731                         // chan, string, slice, array ranges use value multiple times.
 732                 // make copy.
 733                 // fall through
 734                 case TCHAN, TSTRING:
 735                         r := n.Right
 736
 737                         if r.Type.Etype == TSTRING && r.Type != Types[TSTRING] {
 738                                 r = Nod(OCONV, r, nil)
 739                                 r.Type = Types[TSTRING]
 740                                 typecheck(&r, Erv)
 741                         }
 742
 743                         n.Right = ordercopyexpr(r, r.Type, order, 0)
 744
 745                         // copy the map value in case it is a map literal.
 746                 // TODO(rsc): Make tmp = literal expressions reuse tmp.
 747                 // For maps tmp is just one word so it hardly matters.
 748                 case TMAP:
 749                         r := n.Right
 750
 751                         n.Right = ordercopyexpr(r, r.Type, order, 0)
 752
 753                         // n->alloc is the temp for the iterator.
 754                         prealloc[n] = ordertemp(Types[TUINT8], order, true)
 755                 }
 756
 757                 for l := n.List; l != nil; l = l.Next {
 758                         orderexprinplace(&l.N, order)
 759                 }
 760                 orderblock(&n.Nbody)
 761                 order.out = list(order.out, n)
 762                 cleantemp(t, order)
 763
 764         case ORETURN:
 765                 ordercallargs(&n.List, order)
 766                 order.out = list(order.out, n)
 767
 768         // Special: clean case temporaries in each block entry.
 769         // Select must enter one of its blocks, so there is no
 770         // need for a cleaning at the end.
 771         // Doubly special: evaluation order for select is stricter
 772         // than ordinary expressions. Even something like p.c
 773         // has to be hoisted into a temporary, so that it cannot be
 774         // reordered after the channel evaluation for a different
 775         // case (if p were nil, then the timing of the fault would
 776         // give this away).
 777         case OSELECT:
 778                 t := marktemp(order)
 779
 780                 var tmp1 *Node
 781                 var tmp2 *Node
 782                 var r *Node
 783                 for l := n.List; l != nil; l = l.Next {
 784                         if l.N.Op != OXCASE {
 785                                 Fatalf("order select case %v", Oconv(int(l.N.Op), 0))
 786                         }
 787                         r = l.N.Left
 788                         setlineno(l.N)
 789
 790                         // Append any new body prologue to ninit.
 791                         // The next loop will insert ninit into nbody.
 792                         if l.N.Ninit != nil {
 793                                 Fatalf("order select ninit")
 794                         }
 795                         if r != nil {
 796                                 switch r.Op {
 797                                 default:
 798                                         Yyerror("unknown op in select %v", Oconv(int(r.Op), 0))
 799                                         Dump("select case", r)
 800
 801                                         // If this is case x := <-ch or case x, y := <-ch, the case has
 802                                 // the ODCL nodes to declare x and y. We want to delay that
 803                                 // declaration (and possible allocation) until inside the case body.
 804                                 // Delete the ODCL nodes here and recreate them inside the body below.
 805                                 case OSELRECV, OSELRECV2:
 806                                         if r.Colas {
 807                                                 init := r.Ninit
 808                                                 if init != nil && init.N.Op == ODCL && init.N.Left == r.Left {
 809                                                         init = init.Next
 810                                                 }
 811                                                 if init != nil && init.N.Op == ODCL && r.List != nil && init.N.Left == r.List.N {
 812                                                         init = init.Next
 813                                                 }
 814                                                 if init == nil {
 815                                                         r.Ninit = nil
 816                                                 }
 817                                         }
 818
 819                                         if r.Ninit != nil {
 820                                                 Yyerror("ninit on select recv")
 821                                                 dumplist("ninit", r.Ninit)
 822                                         }
 823
 824                                         // case x = <-c
 825                                         // case x, ok = <-c
 826                                         // r->left is x, r->ntest is ok, r->right is ORECV, r->right->left is c.
 827                                         // r->left == N means 'case <-c'.
 828                                         // c is always evaluated; x and ok are only evaluated when assigned.
 829                                         orderexpr(&r.Right.Left, order, nil)
 830
 831                                         if r.Right.Left.Op != ONAME {
 832                                                 r.Right.Left = ordercopyexpr(r.Right.Left, r.Right.Left.Type, order, 0)
 833                                         }
 834
 835                                         // Introduce temporary for receive and move actual copy into case body.
 836                                         // avoids problems with target being addressed, as usual.
 837                                         // NOTE: If we wanted to be clever, we could arrange for just one
 838                                         // temporary per distinct type, sharing the temp among all receives
 839                                         // with that temp. Similarly one ok bool could be shared among all
 840                                         // the x,ok receives. Not worth doing until there's a clear need.
 841                                         if r.Left != nil && isblank(r.Left) {
 842                                                 r.Left = nil
 843                                         }
 844                                         if r.Left != nil {
 845                                                 // use channel element type for temporary to avoid conversions,
 846                                                 // such as in case interfacevalue = <-intchan.
 847                                                 // the conversion happens in the OAS instead.
 848                                                 tmp1 = r.Left
 849
 850                                                 if r.Colas {
 851                                                         tmp2 = Nod(ODCL, tmp1, nil)
 852                                                         typecheck(&tmp2, Etop)
 853                                                         l.N.Ninit = list(l.N.Ninit, tmp2)
 854                                                 }
 855
 856                                                 r.Left = ordertemp(r.Right.Left.Type.Type, order, haspointers(r.Right.Left.Type.Type))
 857                                                 tmp2 = Nod(OAS, tmp1, r.Left)
 858                                                 typecheck(&tmp2, Etop)
 859                                                 l.N.Ninit = list(l.N.Ninit, tmp2)
 860                                         }
 861
 862                                         if r.List != nil && isblank(r.List.N) {
 863                                                 r.List = nil
 864                                         }
 865                                         if r.List != nil {
 866                                                 tmp1 = r.List.N
 867                                                 if r.Colas {
 868                                                         tmp2 = Nod(ODCL, tmp1, nil)
 869                                                         typecheck(&tmp2, Etop)
 870                                                         l.N.Ninit = list(l.N.Ninit, tmp2)
 871                                                 }
 872
 873                                                 r.List = list1(ordertemp(tmp1.Type, order, false))
 874                                                 tmp2 = Nod(OAS, tmp1, r.List.N)
 875                                                 typecheck(&tmp2, Etop)
 876                                                 l.N.Ninit = list(l.N.Ninit, tmp2)
 877                                         }
 878
 879                                         orderblock(&l.N.Ninit)
 880
 881                                 case OSEND:
 882                                         if r.Ninit != nil {
 883                                                 Yyerror("ninit on select send")
 884                                                 dumplist("ninit", r.Ninit)
 885                                         }
 886
 887                                         // case c <- x
 888                                         // r->left is c, r->right is x, both are always evaluated.
 889                                         orderexpr(&r.Left, order, nil)
 890
 891                                         if !istemp(r.Left) {
 892                                                 r.Left = ordercopyexpr(r.Left, r.Left.Type, order, 0)
 893                                         }
 894                                         orderexpr(&r.Right, order, nil)
 895                                         if !istemp(r.Right) {
 896                                                 r.Right = ordercopyexpr(r.Right, r.Right.Type, order, 0)
 897                                         }
 898                                 }
 899                         }
 900
 901                         orderblock(&l.N.Nbody)
 902                 }
 903
 904                 // Now that we have accumulated all the temporaries, clean them.
 905                 // Also insert any ninit queued during the previous loop.
 906                 // (The temporary cleaning must follow that ninit work.)
 907                 for l := n.List; l != nil; l = l.Next {
 908                         cleantempnopop(t, order, &l.N.Ninit)
 909                         l.N.Nbody = concat(l.N.Ninit, l.N.Nbody)
 910                         l.N.Ninit = nil
 911                 }
 912
 913                 order.out = list(order.out, n)
 914                 poptemp(t, order)
 915
 916                 // Special: value being sent is passed as a pointer; make it addressable.
 917         case OSEND:
 918                 t := marktemp(order)
 919
 920                 orderexpr(&n.Left, order, nil)
 921                 orderexpr(&n.Right, order, nil)
 922                 orderaddrtemp(&n.Right, order)
 923                 order.out = list(order.out, n)
 924                 cleantemp(t, order)
 925
 926                 // TODO(rsc): Clean temporaries more aggressively.
 927         // Note that because walkswitch will rewrite some of the
 928         // switch into a binary search, this is not as easy as it looks.
 929         // (If we ran that code here we could invoke orderstmt on
 930         // the if-else chain instead.)
 931         // For now just clean all the temporaries at the end.
 932         // In practice that's fine.
 933         case OSWITCH:
 934                 t := marktemp(order)
 935
 936                 orderexpr(&n.Left, order, nil)
 937                 for l := n.List; l != nil; l = l.Next {
 938                         if l.N.Op != OXCASE {
 939                                 Fatalf("order switch case %v", Oconv(int(l.N.Op), 0))
 940                         }
 941                         orderexprlistinplace(l.N.List, order)
 942                         orderblock(&l.N.Nbody)
 943                 }
 944
 945                 order.out = list(order.out, n)
 946                 cleantemp(t, order)
 947         }
 948
 949         lineno = int32(lno)
 950 }
 951
 952 // Orderexprlist orders the expression list l into order.
 953 func orderexprlist(l *NodeList, order *Order) {
 954         for ; l != nil; l = l.Next {
 955                 orderexpr(&l.N, order, nil)
 956         }
 957 }
 958
 959 // Orderexprlist orders the expression list l but saves
 960 // the side effects on the individual expression ninit lists.
 961 func orderexprlistinplace(l *NodeList, order *Order) {
 962         for ; l != nil; l = l.Next {
 963                 orderexprinplace(&l.N, order)
 964         }
 965 }
 966
 967 // prealloc[x] records the allocation to use for x.
 968 var prealloc = map[*Node]*Node{}
 969
 970 // Orderexpr orders a single expression, appending side
 971 // effects to order->out as needed.
 972 // If this is part of an assignment lhs = *np, lhs is given.
 973 // Otherwise lhs == nil. (When lhs != nil it may be possible
 974 // to avoid copying the result of the expression to a temporary.)
 975 func orderexpr(np **Node, order *Order, lhs *Node) {
 976         n := *np
 977         if n == nil {
 978                 return
 979         }
 980
 981         lno := int(setlineno(n))
 982         orderinit(n, order)
 983
 984         switch n.Op {
 985         default:
 986                 orderexpr(&n.Left, order, nil)
 987                 orderexpr(&n.Right, order, nil)
 988                 orderexprlist(n.List, order)
 989                 orderexprlist(n.Rlist, order)
 990
 991                 // Addition of strings turns into a function call.
 992         // Allocate a temporary to hold the strings.
 993         // Fewer than 5 strings use direct runtime helpers.
 994         case OADDSTR:
 995                 orderexprlist(n.List, order)
 996
 997                 if count(n.List) > 5 {
 998                         t := typ(TARRAY)
 999                         t.Bound = int64(count(n.List))
1000                         t.Type = Types[TSTRING]
1001                         prealloc[n] = ordertemp(t, order, false)
1002                 }
1003
1004                 // Mark string(byteSlice) arguments to reuse byteSlice backing
1005                 // buffer during conversion. String concatenation does not
1006                 // memorize the strings for later use, so it is safe.
1007                 // However, we can do it only if there is at least one non-empty string literal.
1008                 // Otherwise if all other arguments are empty strings,
1009                 // concatstrings will return the reference to the temp string
1010                 // to the caller.
1011                 hasbyte := false
1012
1013                 haslit := false
1014                 for l := n.List; l != nil; l = l.Next {
1015                         hasbyte = hasbyte || l.N.Op == OARRAYBYTESTR
1016                         haslit = haslit || l.N.Op == OLITERAL && len(l.N.Val().U.(string)) != 0
1017                 }
1018
1019                 if haslit && hasbyte {
1020                         for l := n.List; l != nil; l = l.Next {
1021                                 if l.N.Op == OARRAYBYTESTR {
1022                                         l.N.Op = OARRAYBYTESTRTMP
1023                                 }
1024                         }
1025                 }
1026
1027         case OCMPSTR:
1028                 orderexpr(&n.Left, order, nil)
1029                 orderexpr(&n.Right, order, nil)
1030
1031                 // Mark string(byteSlice) arguments to reuse byteSlice backing
1032                 // buffer during conversion. String comparison does not
1033                 // memorize the strings for later use, so it is safe.
1034                 if n.Left.Op == OARRAYBYTESTR {
1035                         n.Left.Op = OARRAYBYTESTRTMP
1036                 }
1037                 if n.Right.Op == OARRAYBYTESTR {
1038                         n.Right.Op = OARRAYBYTESTRTMP
1039                 }
1040
1041                 // key must be addressable
1042         case OINDEXMAP:
1043                 orderexpr(&n.Left, order, nil)
1044
1045                 orderexpr(&n.Right, order, nil)
1046
1047                 // For x = m[string(k)] where k is []byte, the allocation of
1048                 // backing bytes for the string can be avoided by reusing
1049                 // the []byte backing array. This is a special case that it
1050                 // would be nice to handle more generally, but because
1051                 // there are no []byte-keyed maps, this specific case comes
1052                 // up in important cases in practice. See issue 3512.
1053                 // Nothing can change the []byte we are not copying before
1054                 // the map index, because the map access is going to
1055                 // be forced to happen immediately following this
1056                 // conversion (by the ordercopyexpr a few lines below).
1057                 if n.Etype == 0 && n.Right.Op == OARRAYBYTESTR {
1058                         n.Right.Op = OARRAYBYTESTRTMP
1059                 }
1060
1061                 orderaddrtemp(&n.Right, order)
1062                 if n.Etype == 0 {
1063                         // use of value (not being assigned);
1064                         // make copy in temporary.
1065                         n = ordercopyexpr(n, n.Type, order, 0)
1066                 }
1067
1068                 // concrete type (not interface) argument must be addressable
1069         // temporary to pass to runtime.
1070         case OCONVIFACE:
1071                 orderexpr(&n.Left, order, nil)
1072
1073                 if !Isinter(n.Left.Type) {
1074                         orderaddrtemp(&n.Left, order)
1075                 }
1076
1077         case OANDAND, OOROR:
1078                 mark := marktemp(order)
1079                 orderexpr(&n.Left, order, nil)
1080
1081                 // Clean temporaries from first branch at beginning of second.
1082                 // Leave them on the stack so that they can be killed in the outer
1083                 // context in case the short circuit is taken.
1084                 var l *NodeList
1085
1086                 cleantempnopop(mark, order, &l)
1087                 n.Right.Ninit = concat(l, n.Right.Ninit)
1088                 orderexprinplace(&n.Right, order)
1089
1090         case OCALLFUNC,
1091                 OCALLINTER,
1092                 OCALLMETH,
1093                 OCAP,
1094                 OCOMPLEX,
1095                 OCOPY,
1096                 OIMAG,
1097                 OLEN,
1098                 OMAKECHAN,
1099                 OMAKEMAP,
1100                 OMAKESLICE,
1101                 ONEW,
1102                 OREAL,
1103                 ORECOVER,
1104                 OSTRARRAYBYTE,
1105                 OSTRARRAYBYTETMP,
1106                 OSTRARRAYRUNE:
1107                 ordercall(n, order)
1108                 if lhs == nil || lhs.Op != ONAME || instrumenting {
1109                         n = ordercopyexpr(n, n.Type, order, 0)
1110                 }
1111
1112         case OAPPEND:
1113                 ordercallargs(&n.List, order)
1114                 if lhs == nil || lhs.Op != ONAME && !samesafeexpr(lhs, n.List.N) {
1115                         n = ordercopyexpr(n, n.Type, order, 0)
1116                 }
1117
1118         case OSLICE, OSLICEARR, OSLICESTR:
1119                 orderexpr(&n.Left, order, nil)
1120                 orderexpr(&n.Right.Left, order, nil)
1121                 n.Right.Left = ordercheapexpr(n.Right.Left, order)
1122                 orderexpr(&n.Right.Right, order, nil)
1123                 n.Right.Right = ordercheapexpr(n.Right.Right, order)
1124                 if lhs == nil || lhs.Op != ONAME && !samesafeexpr(lhs, n.Left) {
1125                         n = ordercopyexpr(n, n.Type, order, 0)
1126                 }
1127
1128         case OSLICE3, OSLICE3ARR:
1129                 orderexpr(&n.Left, order, nil)
1130                 orderexpr(&n.Right.Left, order, nil)
1131                 n.Right.Left = ordercheapexpr(n.Right.Left, order)
1132                 orderexpr(&n.Right.Right.Left, order, nil)
1133                 n.Right.Right.Left = ordercheapexpr(n.Right.Right.Left, order)
1134                 orderexpr(&n.Right.Right.Right, order, nil)
1135                 n.Right.Right.Right = ordercheapexpr(n.Right.Right.Right, order)
1136                 if lhs == nil || lhs.Op != ONAME && !samesafeexpr(lhs, n.Left) {
1137                         n = ordercopyexpr(n, n.Type, order, 0)
1138                 }
1139
1140         case OCLOSURE:
1141                 if n.Noescape && len(n.Func.Cvars.Slice()) > 0 {
1142                         prealloc[n] = ordertemp(Types[TUINT8], order, false) // walk will fill in correct type
1143                 }
1144
1145         case OARRAYLIT, OCALLPART:
1146                 orderexpr(&n.Left, order, nil)
1147                 orderexpr(&n.Right, order, nil)
1148                 orderexprlist(n.List, order)
1149                 orderexprlist(n.Rlist, order)
1150                 if n.Noescape {
1151                         prealloc[n] = ordertemp(Types[TUINT8], order, false) // walk will fill in correct type
1152                 }
1153
1154         case ODDDARG:
1155                 if n.Noescape {
1156                         // The ddd argument does not live beyond the call it is created for.
1157                         // Allocate a temporary that will be cleaned up when this statement
1158                         // completes. We could be more aggressive and try to arrange for it
1159                         // to be cleaned up when the call completes.
1160                         prealloc[n] = ordertemp(n.Type.Type, order, false)
1161                 }
1162
1163         case ODOTTYPE, ODOTTYPE2:
1164                 orderexpr(&n.Left, order, nil)
1165                 // TODO(rsc): The Isfat is for consistency with componentgen and walkexpr.
1166                 // It needs to be removed in all three places.
1167                 // That would allow inlining x.(struct{*int}) the same as x.(*int).
1168                 if !isdirectiface(n.Type) || Isfat(n.Type) || instrumenting {
1169                         n = ordercopyexpr(n, n.Type, order, 1)
1170                 }
1171
1172         case ORECV:
1173                 orderexpr(&n.Left, order, nil)
1174                 n = ordercopyexpr(n, n.Type, order, 1)
1175
1176         case OEQ, ONE:
1177                 orderexpr(&n.Left, order, nil)
1178                 orderexpr(&n.Right, order, nil)
1179                 t := n.Left.Type
1180                 if t.Etype == TSTRUCT || Isfixedarray(t) {
1181                         // for complex comparisons, we need both args to be
1182                         // addressable so we can pass them to the runtime.
1183                         orderaddrtemp(&n.Left, order)
1184                         orderaddrtemp(&n.Right, order)
1185                 }
1186         }
1187
1188         lineno = int32(lno)
1189
1190         *np = n
1191 }