src/cmd/compile/internal/walk/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 walk
   6
   7 import (
   8         "fmt"
   9         "go/constant"
  10
  11         "cmd/compile/internal/base"
  12         "cmd/compile/internal/ir"
  13         "cmd/compile/internal/reflectdata"
  14         "cmd/compile/internal/staticinit"
  15         "cmd/compile/internal/typecheck"
  16         "cmd/compile/internal/types"
  17         "cmd/internal/objabi"
  18         "cmd/internal/src"
  19 )
  20
  21 // Rewrite tree to use separate statements to enforce
  22 // order of evaluation. Makes walk easier, because it
  23 // can (after this runs) reorder at will within an expression.
  24 //
  25 // Rewrite m[k] op= r into m[k] = m[k] op r if op is / or %.
  26 //
  27 // Introduce temporaries as needed by runtime routines.
  28 // For example, the map runtime routines take the map key
  29 // by reference, so make sure all map keys are addressable
  30 // by copying them to temporaries as needed.
  31 // The same is true for channel operations.
  32 //
  33 // Arrange that map index expressions only appear in direct
  34 // assignments x = m[k] or m[k] = x, never in larger expressions.
  35 //
  36 // Arrange that receive expressions only appear in direct assignments
  37 // x = <-c or as standalone statements <-c, never in larger expressions.
  38
  39 // TODO(rsc): The temporary introduction during multiple assignments
  40 // should be moved into this file, so that the temporaries can be cleaned
  41 // and so that conversions implicit in the OAS2FUNC and OAS2RECV
  42 // nodes can be made explicit and then have their temporaries cleaned.
  43
  44 // TODO(rsc): Goto and multilevel break/continue can jump over
  45 // inserted VARKILL annotations. Work out a way to handle these.
  46 // The current implementation is safe, in that it will execute correctly.
  47 // But it won't reuse temporaries as aggressively as it might, and
  48 // it can result in unnecessary zeroing of those variables in the function
  49 // prologue.
  50
  51 // orderState holds state during the ordering process.
  52 type orderState struct {
  53         out  []ir.Node             // list of generated statements
  54         temp []*ir.Name            // stack of temporary variables
  55         free map[string][]*ir.Name // free list of unused temporaries, by type.LinkString().
  56         edit func(ir.Node) ir.Node // cached closure of o.exprNoLHS
  57 }
  58
  59 // Order rewrites fn.Nbody to apply the ordering constraints
  60 // described in the comment at the top of the file.
  61 func order(fn *ir.Func) {
  62         if base.Flag.W > 1 {
  63                 s := fmt.Sprintf("\nbefore order %v", fn.Sym())
  64                 ir.DumpList(s, fn.Body)
  65         }
  66
  67         orderBlock(&fn.Body, map[string][]*ir.Name{})
  68 }
  69
  70 // append typechecks stmt and appends it to out.
  71 func (o *orderState) append(stmt ir.Node) {
  72         o.out = append(o.out, typecheck.Stmt(stmt))
  73 }
  74
  75 // newTemp allocates a new temporary with the given type,
  76 // pushes it onto the temp stack, and returns it.
  77 // If clear is true, newTemp emits code to zero the temporary.
  78 func (o *orderState) newTemp(t *types.Type, clear bool) *ir.Name {
  79         var v *ir.Name
  80         key := t.LinkString()
  81         if a := o.free[key]; len(a) > 0 {
  82                 v = a[len(a)-1]
  83                 if !types.Identical(t, v.Type()) {
  84                         base.Fatalf("expected %L to have type %v", v, t)
  85                 }
  86                 o.free[key] = a[:len(a)-1]
  87         } else {
  88                 v = typecheck.Temp(t)
  89         }
  90         if clear {
  91                 o.append(ir.NewAssignStmt(base.Pos, v, nil))
  92         }
  93
  94         o.temp = append(o.temp, v)
  95         return v
  96 }
  97
  98 // copyExpr behaves like newTemp but also emits
  99 // code to initialize the temporary to the value n.
 100 func (o *orderState) copyExpr(n ir.Node) *ir.Name {
 101         return o.copyExpr1(n, false)
 102 }
 103
 104 // copyExprClear is like copyExpr but clears the temp before assignment.
 105 // It is provided for use when the evaluation of tmp = n turns into
 106 // a function call that is passed a pointer to the temporary as the output space.
 107 // If the call blocks before tmp has been written,
 108 // the garbage collector will still treat the temporary as live,
 109 // so we must zero it before entering that call.
 110 // Today, this only happens for channel receive operations.
 111 // (The other candidate would be map access, but map access
 112 // returns a pointer to the result data instead of taking a pointer
 113 // to be filled in.)
 114 func (o *orderState) copyExprClear(n ir.Node) *ir.Name {
 115         return o.copyExpr1(n, true)
 116 }
 117
 118 func (o *orderState) copyExpr1(n ir.Node, clear bool) *ir.Name {
 119         t := n.Type()
 120         v := o.newTemp(t, clear)
 121         o.append(ir.NewAssignStmt(base.Pos, v, n))
 122         return v
 123 }
 124
 125 // cheapExpr returns a cheap version of n.
 126 // The definition of cheap is that n is a variable or constant.
 127 // If not, cheapExpr allocates a new tmp, emits tmp = n,
 128 // and then returns tmp.
 129 func (o *orderState) cheapExpr(n ir.Node) ir.Node {
 130         if n == nil {
 131                 return nil
 132         }
 133
 134         switch n.Op() {
 135         case ir.ONAME, ir.OLITERAL, ir.ONIL:
 136                 return n
 137         case ir.OLEN, ir.OCAP:
 138                 n := n.(*ir.UnaryExpr)
 139                 l := o.cheapExpr(n.X)
 140                 if l == n.X {
 141                         return n
 142                 }
 143                 a := ir.SepCopy(n).(*ir.UnaryExpr)
 144                 a.X = l
 145                 return typecheck.Expr(a)
 146         }
 147
 148         return o.copyExpr(n)
 149 }
 150
 151 // safeExpr returns a safe version of n.
 152 // The definition of safe is that n can appear multiple times
 153 // without violating the semantics of the original program,
 154 // and that assigning to the safe version has the same effect
 155 // as assigning to the original n.
 156 //
 157 // The intended use is to apply to x when rewriting x += y into x = x + y.
 158 func (o *orderState) safeExpr(n ir.Node) ir.Node {
 159         switch n.Op() {
 160         case ir.ONAME, ir.OLITERAL, ir.ONIL:
 161                 return n
 162
 163         case ir.OLEN, ir.OCAP:
 164                 n := n.(*ir.UnaryExpr)
 165                 l := o.safeExpr(n.X)
 166                 if l == n.X {
 167                         return n
 168                 }
 169                 a := ir.SepCopy(n).(*ir.UnaryExpr)
 170                 a.X = l
 171                 return typecheck.Expr(a)
 172
 173         case ir.ODOT:
 174                 n := n.(*ir.SelectorExpr)
 175                 l := o.safeExpr(n.X)
 176                 if l == n.X {
 177                         return n
 178                 }
 179                 a := ir.SepCopy(n).(*ir.SelectorExpr)
 180                 a.X = l
 181                 return typecheck.Expr(a)
 182
 183         case ir.ODOTPTR:
 184                 n := n.(*ir.SelectorExpr)
 185                 l := o.cheapExpr(n.X)
 186                 if l == n.X {
 187                         return n
 188                 }
 189                 a := ir.SepCopy(n).(*ir.SelectorExpr)
 190                 a.X = l
 191                 return typecheck.Expr(a)
 192
 193         case ir.ODEREF:
 194                 n := n.(*ir.StarExpr)
 195                 l := o.cheapExpr(n.X)
 196                 if l == n.X {
 197                         return n
 198                 }
 199                 a := ir.SepCopy(n).(*ir.StarExpr)
 200                 a.X = l
 201                 return typecheck.Expr(a)
 202
 203         case ir.OINDEX, ir.OINDEXMAP:
 204                 n := n.(*ir.IndexExpr)
 205                 var l ir.Node
 206                 if n.X.Type().IsArray() {
 207                         l = o.safeExpr(n.X)
 208                 } else {
 209                         l = o.cheapExpr(n.X)
 210                 }
 211                 r := o.cheapExpr(n.Index)
 212                 if l == n.X && r == n.Index {
 213                         return n
 214                 }
 215                 a := ir.SepCopy(n).(*ir.IndexExpr)
 216                 a.X = l
 217                 a.Index = r
 218                 return typecheck.Expr(a)
 219
 220         default:
 221                 base.Fatalf("order.safeExpr %v", n.Op())
 222                 return nil // not reached
 223         }
 224 }
 225
 226 // isaddrokay reports whether it is okay to pass n's address to runtime routines.
 227 // Taking the address of a variable makes the liveness and optimization analyses
 228 // lose track of where the variable's lifetime ends. To avoid hurting the analyses
 229 // of ordinary stack variables, those are not 'isaddrokay'. Temporaries are okay,
 230 // because we emit explicit VARKILL instructions marking the end of those
 231 // temporaries' lifetimes.
 232 func isaddrokay(n ir.Node) bool {
 233         return ir.IsAddressable(n) && (n.Op() != ir.ONAME || n.(*ir.Name).Class == ir.PEXTERN || ir.IsAutoTmp(n))
 234 }
 235
 236 // addrTemp ensures that n is okay to pass by address to runtime routines.
 237 // If the original argument n is not okay, addrTemp creates a tmp, emits
 238 // tmp = n, and then returns tmp.
 239 // The result of addrTemp MUST be assigned back to n, e.g.
 240 //
 241 //      n.Left = o.addrTemp(n.Left)
 242 func (o *orderState) addrTemp(n ir.Node) ir.Node {
 243         if n.Op() == ir.OLITERAL || n.Op() == ir.ONIL {
 244                 // TODO: expand this to all static composite literal nodes?
 245                 n = typecheck.DefaultLit(n, nil)
 246                 types.CalcSize(n.Type())
 247                 vstat := readonlystaticname(n.Type())
 248                 var s staticinit.Schedule
 249                 s.StaticAssign(vstat, 0, n, n.Type())
 250                 if s.Out != nil {
 251                         base.Fatalf("staticassign of const generated code: %+v", n)
 252                 }
 253                 vstat = typecheck.Expr(vstat).(*ir.Name)
 254                 return vstat
 255         }
 256         if isaddrokay(n) {
 257                 return n
 258         }
 259         return o.copyExpr(n)
 260 }
 261
 262 // mapKeyTemp prepares n to be a key in a map runtime call and returns n.
 263 // It should only be used for map runtime calls which have *_fast* versions.
 264 func (o *orderState) mapKeyTemp(t *types.Type, n ir.Node) ir.Node {
 265         // Most map calls need to take the address of the key.
 266         // Exception: map*_fast* calls. See golang.org/issue/19015.
 267         alg := mapfast(t)
 268         if alg == mapslow {
 269                 return o.addrTemp(n)
 270         }
 271         var kt *types.Type
 272         switch alg {
 273         case mapfast32:
 274                 kt = types.Types[types.TUINT32]
 275         case mapfast64:
 276                 kt = types.Types[types.TUINT64]
 277         case mapfast32ptr, mapfast64ptr:
 278                 kt = types.Types[types.TUNSAFEPTR]
 279         case mapfaststr:
 280                 kt = types.Types[types.TSTRING]
 281         }
 282         nt := n.Type()
 283         switch {
 284         case nt == kt:
 285                 return n
 286         case nt.Kind() == kt.Kind(), nt.IsPtrShaped() && kt.IsPtrShaped():
 287                 // can directly convert (e.g. named type to underlying type, or one pointer to another)
 288                 return typecheck.Expr(ir.NewConvExpr(n.Pos(), ir.OCONVNOP, kt, n))
 289         case nt.IsInteger() && kt.IsInteger():
 290                 // can directly convert (e.g. int32 to uint32)
 291                 if n.Op() == ir.OLITERAL && nt.IsSigned() {
 292                         // avoid constant overflow error
 293                         n = ir.NewConstExpr(constant.MakeUint64(uint64(ir.Int64Val(n))), n)
 294                         n.SetType(kt)
 295                         return n
 296                 }
 297                 return typecheck.Expr(ir.NewConvExpr(n.Pos(), ir.OCONV, kt, n))
 298         default:
 299                 // Unsafe cast through memory.
 300                 // We'll need to do a load with type kt. Create a temporary of type kt to
 301                 // ensure sufficient alignment. nt may be under-aligned.
 302                 if uint8(kt.Alignment()) < uint8(nt.Alignment()) {
 303                         base.Fatalf("mapKeyTemp: key type is not sufficiently aligned, kt=%v nt=%v", kt, nt)
 304                 }
 305                 tmp := o.newTemp(kt, true)
 306                 // *(*nt)(&tmp) = n
 307                 var e ir.Node = typecheck.NodAddr(tmp)
 308                 e = ir.NewConvExpr(n.Pos(), ir.OCONVNOP, nt.PtrTo(), e)
 309                 e = ir.NewStarExpr(n.Pos(), e)
 310                 o.append(ir.NewAssignStmt(base.Pos, e, n))
 311                 return tmp
 312         }
 313 }
 314
 315 // mapKeyReplaceStrConv replaces OBYTES2STR by OBYTES2STRTMP
 316 // in n to avoid string allocations for keys in map lookups.
 317 // Returns a bool that signals if a modification was made.
 318 //
 319 // For:
 320 //
 321 //      x = m[string(k)]
 322 //      x = m[T1{... Tn{..., string(k), ...}]
 323 //
 324 // where k is []byte, T1 to Tn is a nesting of struct and array literals,
 325 // the allocation of backing bytes for the string can be avoided
 326 // by reusing the []byte backing array. These are special cases
 327 // for avoiding allocations when converting byte slices to strings.
 328 // It would be nice to handle these generally, but because
 329 // []byte keys are not allowed in maps, the use of string(k)
 330 // comes up in important cases in practice. See issue 3512.
 331 func mapKeyReplaceStrConv(n ir.Node) bool {
 332         var replaced bool
 333         switch n.Op() {
 334         case ir.OBYTES2STR:
 335                 n := n.(*ir.ConvExpr)
 336                 n.SetOp(ir.OBYTES2STRTMP)
 337                 replaced = true
 338         case ir.OSTRUCTLIT:
 339                 n := n.(*ir.CompLitExpr)
 340                 for _, elem := range n.List {
 341                         elem := elem.(*ir.StructKeyExpr)
 342                         if mapKeyReplaceStrConv(elem.Value) {
 343                                 replaced = true
 344                         }
 345                 }
 346         case ir.OARRAYLIT:
 347                 n := n.(*ir.CompLitExpr)
 348                 for _, elem := range n.List {
 349                         if elem.Op() == ir.OKEY {
 350                                 elem = elem.(*ir.KeyExpr).Value
 351                         }
 352                         if mapKeyReplaceStrConv(elem) {
 353                                 replaced = true
 354                         }
 355                 }
 356         }
 357         return replaced
 358 }
 359
 360 type ordermarker int
 361
 362 // markTemp returns the top of the temporary variable stack.
 363 func (o *orderState) markTemp() ordermarker {
 364         return ordermarker(len(o.temp))
 365 }
 366
 367 // popTemp pops temporaries off the stack until reaching the mark,
 368 // which must have been returned by markTemp.
 369 func (o *orderState) popTemp(mark ordermarker) {
 370         for _, n := range o.temp[mark:] {
 371                 key := n.Type().LinkString()
 372                 o.free[key] = append(o.free[key], n)
 373         }
 374         o.temp = o.temp[:mark]
 375 }
 376
 377 // cleanTempNoPop emits VARKILL instructions to *out
 378 // for each temporary above the mark on the temporary stack.
 379 // It does not pop the temporaries from the stack.
 380 func (o *orderState) cleanTempNoPop(mark ordermarker) []ir.Node {
 381         var out []ir.Node
 382         for i := len(o.temp) - 1; i >= int(mark); i-- {
 383                 n := o.temp[i]
 384                 out = append(out, typecheck.Stmt(ir.NewUnaryExpr(base.Pos, ir.OVARKILL, n)))
 385         }
 386         return out
 387 }
 388
 389 // cleanTemp emits VARKILL instructions for each temporary above the
 390 // mark on the temporary stack and removes them from the stack.
 391 func (o *orderState) cleanTemp(top ordermarker) {
 392         o.out = append(o.out, o.cleanTempNoPop(top)...)
 393         o.popTemp(top)
 394 }
 395
 396 // stmtList orders each of the statements in the list.
 397 func (o *orderState) stmtList(l ir.Nodes) {
 398         s := l
 399         for i := range s {
 400                 orderMakeSliceCopy(s[i:])
 401                 o.stmt(s[i])
 402         }
 403 }
 404
 405 // orderMakeSliceCopy matches the pattern:
 406 //
 407 //      m = OMAKESLICE([]T, x); OCOPY(m, s)
 408 //
 409 // and rewrites it to:
 410 //
 411 //      m = OMAKESLICECOPY([]T, x, s); nil
 412 func orderMakeSliceCopy(s []ir.Node) {
 413         if base.Flag.N != 0 || base.Flag.Cfg.Instrumenting {
 414                 return
 415         }
 416         if len(s) < 2 || s[0] == nil || s[0].Op() != ir.OAS || s[1] == nil || s[1].Op() != ir.OCOPY {
 417                 return
 418         }
 419
 420         as := s[0].(*ir.AssignStmt)
 421         cp := s[1].(*ir.BinaryExpr)
 422         if as.Y == nil || as.Y.Op() != ir.OMAKESLICE || ir.IsBlank(as.X) ||
 423                 as.X.Op() != ir.ONAME || cp.X.Op() != ir.ONAME || cp.Y.Op() != ir.ONAME ||
 424                 as.X.Name() != cp.X.Name() || cp.X.Name() == cp.Y.Name() {
 425                 // The line above this one is correct with the differing equality operators:
 426                 // we want as.X and cp.X to be the same name,
 427                 // but we want the initial data to be coming from a different name.
 428                 return
 429         }
 430
 431         mk := as.Y.(*ir.MakeExpr)
 432         if mk.Esc() == ir.EscNone || mk.Len == nil || mk.Cap != nil {
 433                 return
 434         }
 435         mk.SetOp(ir.OMAKESLICECOPY)
 436         mk.Cap = cp.Y
 437         // Set bounded when m = OMAKESLICE([]T, len(s)); OCOPY(m, s)
 438         mk.SetBounded(mk.Len.Op() == ir.OLEN && ir.SameSafeExpr(mk.Len.(*ir.UnaryExpr).X, cp.Y))
 439         as.Y = typecheck.Expr(mk)
 440         s[1] = nil // remove separate copy call
 441 }
 442
 443 // edge inserts coverage instrumentation for libfuzzer.
 444 func (o *orderState) edge() {
 445         if base.Debug.Libfuzzer == 0 {
 446                 return
 447         }
 448
 449         // Create a new uint8 counter to be allocated in section
 450         // __libfuzzer_extra_counters.
 451         counter := staticinit.StaticName(types.Types[types.TUINT8])
 452         counter.SetLibfuzzerExtraCounter(true)
 453         // As well as setting SetLibfuzzerExtraCounter, we preemptively set the
 454         // symbol type to SLIBFUZZER_EXTRA_COUNTER so that the race detector
 455         // instrumentation pass (which does not have access to the flags set by
 456         // SetLibfuzzerExtraCounter) knows to ignore them. This information is
 457         // lost by the time it reaches the compile step, so SetLibfuzzerExtraCounter
 458         // is still necessary.
 459         counter.Linksym().Type = objabi.SLIBFUZZER_EXTRA_COUNTER
 460
 461         // counter += 1
 462         incr := ir.NewAssignOpStmt(base.Pos, ir.OADD, counter, ir.NewInt(1))
 463         o.append(incr)
 464 }
 465
 466 // orderBlock orders the block of statements in n into a new slice,
 467 // and then replaces the old slice in n with the new slice.
 468 // free is a map that can be used to obtain temporary variables by type.
 469 func orderBlock(n *ir.Nodes, free map[string][]*ir.Name) {
 470         var order orderState
 471         order.free = free
 472         mark := order.markTemp()
 473         order.edge()
 474         order.stmtList(*n)
 475         order.cleanTemp(mark)
 476         *n = order.out
 477 }
 478
 479 // exprInPlace orders the side effects in *np and
 480 // leaves them as the init list of the final *np.
 481 // The result of exprInPlace MUST be assigned back to n, e.g.
 482 //
 483 //      n.Left = o.exprInPlace(n.Left)
 484 func (o *orderState) exprInPlace(n ir.Node) ir.Node {
 485         var order orderState
 486         order.free = o.free
 487         n = order.expr(n, nil)
 488         n = ir.InitExpr(order.out, n)
 489
 490         // insert new temporaries from order
 491         // at head of outer list.
 492         o.temp = append(o.temp, order.temp...)
 493         return n
 494 }
 495
 496 // orderStmtInPlace orders the side effects of the single statement *np
 497 // and replaces it with the resulting statement list.
 498 // The result of orderStmtInPlace MUST be assigned back to n, e.g.
 499 //
 500 //      n.Left = orderStmtInPlace(n.Left)
 501 //
 502 // free is a map that can be used to obtain temporary variables by type.
 503 func orderStmtInPlace(n ir.Node, free map[string][]*ir.Name) ir.Node {
 504         var order orderState
 505         order.free = free
 506         mark := order.markTemp()
 507         order.stmt(n)
 508         order.cleanTemp(mark)
 509         return ir.NewBlockStmt(src.NoXPos, order.out)
 510 }
 511
 512 // init moves n's init list to o.out.
 513 func (o *orderState) init(n ir.Node) {
 514         if ir.MayBeShared(n) {
 515                 // For concurrency safety, don't mutate potentially shared nodes.
 516                 // First, ensure that no work is required here.
 517                 if len(n.Init()) > 0 {
 518                         base.Fatalf("order.init shared node with ninit")
 519                 }
 520                 return
 521         }
 522         o.stmtList(ir.TakeInit(n))
 523 }
 524
 525 // call orders the call expression n.
 526 // n.Op is OCALLFUNC/OCALLINTER or a builtin like OCOPY.
 527 func (o *orderState) call(nn ir.Node) {
 528         if len(nn.Init()) > 0 {
 529                 // Caller should have already called o.init(nn).
 530                 base.Fatalf("%v with unexpected ninit", nn.Op())
 531         }
 532         if nn.Op() == ir.OCALLMETH {
 533                 base.FatalfAt(nn.Pos(), "OCALLMETH missed by typecheck")
 534         }
 535
 536         // Builtin functions.
 537         if nn.Op() != ir.OCALLFUNC && nn.Op() != ir.OCALLINTER {
 538                 switch n := nn.(type) {
 539                 default:
 540                         base.Fatalf("unexpected call: %+v", n)
 541                 case *ir.UnaryExpr:
 542                         n.X = o.expr(n.X, nil)
 543                 case *ir.ConvExpr:
 544                         n.X = o.expr(n.X, nil)
 545                 case *ir.BinaryExpr:
 546                         n.X = o.expr(n.X, nil)
 547                         n.Y = o.expr(n.Y, nil)
 548                 case *ir.MakeExpr:
 549                         n.Len = o.expr(n.Len, nil)
 550                         n.Cap = o.expr(n.Cap, nil)
 551                 case *ir.CallExpr:
 552                         o.exprList(n.Args)
 553                 }
 554                 return
 555         }
 556
 557         n := nn.(*ir.CallExpr)
 558         typecheck.FixVariadicCall(n)
 559
 560         if isFuncPCIntrinsic(n) && isIfaceOfFunc(n.Args[0]) {
 561                 // For internal/abi.FuncPCABIxxx(fn), if fn is a defined function,
 562                 // do not introduce temporaries here, so it is easier to rewrite it
 563                 // to symbol address reference later in walk.
 564                 return
 565         }
 566
 567         n.X = o.expr(n.X, nil)
 568         o.exprList(n.Args)
 569 }
 570
 571 // mapAssign appends n to o.out.
 572 func (o *orderState) mapAssign(n ir.Node) {
 573         switch n.Op() {
 574         default:
 575                 base.Fatalf("order.mapAssign %v", n.Op())
 576
 577         case ir.OAS:
 578                 n := n.(*ir.AssignStmt)
 579                 if n.X.Op() == ir.OINDEXMAP {
 580                         n.Y = o.safeMapRHS(n.Y)
 581                 }
 582                 o.out = append(o.out, n)
 583         case ir.OASOP:
 584                 n := n.(*ir.AssignOpStmt)
 585                 if n.X.Op() == ir.OINDEXMAP {
 586                         n.Y = o.safeMapRHS(n.Y)
 587                 }
 588                 o.out = append(o.out, n)
 589         }
 590 }
 591
 592 func (o *orderState) safeMapRHS(r ir.Node) ir.Node {
 593         // Make sure we evaluate the RHS before starting the map insert.
 594         // We need to make sure the RHS won't panic.  See issue 22881.
 595         if r.Op() == ir.OAPPEND {
 596                 r := r.(*ir.CallExpr)
 597                 s := r.Args[1:]
 598                 for i, n := range s {
 599                         s[i] = o.cheapExpr(n)
 600                 }
 601                 return r
 602         }
 603         return o.cheapExpr(r)
 604 }
 605
 606 // stmt orders the statement n, appending to o.out.
 607 // Temporaries created during the statement are cleaned
 608 // up using VARKILL instructions as possible.
 609 func (o *orderState) stmt(n ir.Node) {
 610         if n == nil {
 611                 return
 612         }
 613
 614         lno := ir.SetPos(n)
 615         o.init(n)
 616
 617         switch n.Op() {
 618         default:
 619                 base.Fatalf("order.stmt %v", n.Op())
 620
 621         case ir.OVARKILL, ir.OVARLIVE, ir.OINLMARK:
 622                 o.out = append(o.out, n)
 623
 624         case ir.OAS:
 625                 n := n.(*ir.AssignStmt)
 626                 t := o.markTemp()
 627                 n.X = o.expr(n.X, nil)
 628                 n.Y = o.expr(n.Y, n.X)
 629                 o.mapAssign(n)
 630                 o.cleanTemp(t)
 631
 632         case ir.OASOP:
 633                 n := n.(*ir.AssignOpStmt)
 634                 t := o.markTemp()
 635                 n.X = o.expr(n.X, nil)
 636                 n.Y = o.expr(n.Y, nil)
 637
 638                 if base.Flag.Cfg.Instrumenting || n.X.Op() == ir.OINDEXMAP && (n.AsOp == ir.ODIV || n.AsOp == ir.OMOD) {
 639                         // Rewrite m[k] op= r into m[k] = m[k] op r so
 640                         // that we can ensure that if op panics
 641                         // because r is zero, the panic happens before
 642                         // the map assignment.
 643                         // DeepCopy is a big hammer here, but safeExpr
 644                         // makes sure there is nothing too deep being copied.
 645                         l1 := o.safeExpr(n.X)
 646                         l2 := ir.DeepCopy(src.NoXPos, l1)
 647                         if l2.Op() == ir.OINDEXMAP {
 648                                 l2 := l2.(*ir.IndexExpr)
 649                                 l2.Assigned = false
 650                         }
 651                         l2 = o.copyExpr(l2)
 652                         r := o.expr(typecheck.Expr(ir.NewBinaryExpr(n.Pos(), n.AsOp, l2, n.Y)), nil)
 653                         as := typecheck.Stmt(ir.NewAssignStmt(n.Pos(), l1, r))
 654                         o.mapAssign(as)
 655                         o.cleanTemp(t)
 656                         return
 657                 }
 658
 659                 o.mapAssign(n)
 660                 o.cleanTemp(t)
 661
 662         case ir.OAS2:
 663                 n := n.(*ir.AssignListStmt)
 664                 t := o.markTemp()
 665                 o.exprList(n.Lhs)
 666                 o.exprList(n.Rhs)
 667                 o.out = append(o.out, n)
 668                 o.cleanTemp(t)
 669
 670         // Special: avoid copy of func call n.Right
 671         case ir.OAS2FUNC:
 672                 n := n.(*ir.AssignListStmt)
 673                 t := o.markTemp()
 674                 o.exprList(n.Lhs)
 675                 call := n.Rhs[0]
 676                 o.init(call)
 677                 if ic, ok := call.(*ir.InlinedCallExpr); ok {
 678                         o.stmtList(ic.Body)
 679
 680                         n.SetOp(ir.OAS2)
 681                         n.Rhs = ic.ReturnVars
 682
 683                         o.exprList(n.Rhs)
 684                         o.out = append(o.out, n)
 685                 } else {
 686                         o.call(call)
 687                         o.as2func(n)
 688                 }
 689                 o.cleanTemp(t)
 690
 691         // Special: use temporary variables to hold result,
 692         // so that runtime can take address of temporary.
 693         // No temporary for blank assignment.
 694         //
 695         // OAS2MAPR: make sure key is addressable if needed,
 696         //           and make sure OINDEXMAP is not copied out.
 697         case ir.OAS2DOTTYPE, ir.OAS2RECV, ir.OAS2MAPR:
 698                 n := n.(*ir.AssignListStmt)
 699                 t := o.markTemp()
 700                 o.exprList(n.Lhs)
 701
 702                 switch r := n.Rhs[0]; r.Op() {
 703                 case ir.ODOTTYPE2:
 704                         r := r.(*ir.TypeAssertExpr)
 705                         r.X = o.expr(r.X, nil)
 706                 case ir.ODYNAMICDOTTYPE2:
 707                         r := r.(*ir.DynamicTypeAssertExpr)
 708                         r.X = o.expr(r.X, nil)
 709                         r.RType = o.expr(r.RType, nil)
 710                         r.ITab = o.expr(r.ITab, nil)
 711                 case ir.ORECV:
 712                         r := r.(*ir.UnaryExpr)
 713                         r.X = o.expr(r.X, nil)
 714                 case ir.OINDEXMAP:
 715                         r := r.(*ir.IndexExpr)
 716                         r.X = o.expr(r.X, nil)
 717                         r.Index = o.expr(r.Index, nil)
 718                         // See similar conversion for OINDEXMAP below.
 719                         _ = mapKeyReplaceStrConv(r.Index)
 720                         r.Index = o.mapKeyTemp(r.X.Type(), r.Index)
 721                 default:
 722                         base.Fatalf("order.stmt: %v", r.Op())
 723                 }
 724
 725                 o.as2ok(n)
 726                 o.cleanTemp(t)
 727
 728         // Special: does not save n onto out.
 729         case ir.OBLOCK:
 730                 n := n.(*ir.BlockStmt)
 731                 o.stmtList(n.List)
 732
 733         // Special: n->left is not an expression; save as is.
 734         case ir.OBREAK,
 735                 ir.OCONTINUE,
 736                 ir.ODCL,
 737                 ir.ODCLCONST,
 738                 ir.ODCLTYPE,
 739                 ir.OFALL,
 740                 ir.OGOTO,
 741                 ir.OLABEL,
 742                 ir.OTAILCALL:
 743                 o.out = append(o.out, n)
 744
 745         // Special: handle call arguments.
 746         case ir.OCALLFUNC, ir.OCALLINTER:
 747                 n := n.(*ir.CallExpr)
 748                 t := o.markTemp()
 749                 o.call(n)
 750                 o.out = append(o.out, n)
 751                 o.cleanTemp(t)
 752
 753         case ir.OINLCALL:
 754                 n := n.(*ir.InlinedCallExpr)
 755                 o.stmtList(n.Body)
 756
 757                 // discard results; double-check for no side effects
 758                 for _, result := range n.ReturnVars {
 759                         if staticinit.AnySideEffects(result) {
 760                                 base.FatalfAt(result.Pos(), "inlined call result has side effects: %v", result)
 761                         }
 762                 }
 763
 764         case ir.OCHECKNIL, ir.OCLOSE, ir.OPANIC, ir.ORECV:
 765                 n := n.(*ir.UnaryExpr)
 766                 t := o.markTemp()
 767                 n.X = o.expr(n.X, nil)
 768                 o.out = append(o.out, n)
 769                 o.cleanTemp(t)
 770
 771         case ir.OCOPY:
 772                 n := n.(*ir.BinaryExpr)
 773                 t := o.markTemp()
 774                 n.X = o.expr(n.X, nil)
 775                 n.Y = o.expr(n.Y, nil)
 776                 o.out = append(o.out, n)
 777                 o.cleanTemp(t)
 778
 779         case ir.OPRINT, ir.OPRINTN, ir.ORECOVERFP:
 780                 n := n.(*ir.CallExpr)
 781                 t := o.markTemp()
 782                 o.call(n)
 783                 o.out = append(o.out, n)
 784                 o.cleanTemp(t)
 785
 786         // Special: order arguments to inner call but not call itself.
 787         case ir.ODEFER, ir.OGO:
 788                 n := n.(*ir.GoDeferStmt)
 789                 t := o.markTemp()
 790                 o.init(n.Call)
 791                 o.call(n.Call)
 792                 o.out = append(o.out, n)
 793                 o.cleanTemp(t)
 794
 795         case ir.ODELETE:
 796                 n := n.(*ir.CallExpr)
 797                 t := o.markTemp()
 798                 n.Args[0] = o.expr(n.Args[0], nil)
 799                 n.Args[1] = o.expr(n.Args[1], nil)
 800                 n.Args[1] = o.mapKeyTemp(n.Args[0].Type(), n.Args[1])
 801                 o.out = append(o.out, n)
 802                 o.cleanTemp(t)
 803
 804         // Clean temporaries from condition evaluation at
 805         // beginning of loop body and after for statement.
 806         case ir.OFOR:
 807                 n := n.(*ir.ForStmt)
 808                 t := o.markTemp()
 809                 n.Cond = o.exprInPlace(n.Cond)
 810                 n.Body.Prepend(o.cleanTempNoPop(t)...)
 811                 orderBlock(&n.Body, o.free)
 812                 n.Post = orderStmtInPlace(n.Post, o.free)
 813                 o.out = append(o.out, n)
 814                 o.cleanTemp(t)
 815
 816         // Clean temporaries from condition at
 817         // beginning of both branches.
 818         case ir.OIF:
 819                 n := n.(*ir.IfStmt)
 820                 t := o.markTemp()
 821                 n.Cond = o.exprInPlace(n.Cond)
 822                 n.Body.Prepend(o.cleanTempNoPop(t)...)
 823                 n.Else.Prepend(o.cleanTempNoPop(t)...)
 824                 o.popTemp(t)
 825                 orderBlock(&n.Body, o.free)
 826                 orderBlock(&n.Else, o.free)
 827                 o.out = append(o.out, n)
 828
 829         case ir.ORANGE:
 830                 // n.Right is the expression being ranged over.
 831                 // order it, and then make a copy if we need one.
 832                 // We almost always do, to ensure that we don't
 833                 // see any value changes made during the loop.
 834                 // Usually the copy is cheap (e.g., array pointer,
 835                 // chan, slice, string are all tiny).
 836                 // The exception is ranging over an array value
 837                 // (not a slice, not a pointer to array),
 838                 // which must make a copy to avoid seeing updates made during
 839                 // the range body. Ranging over an array value is uncommon though.
 840
 841                 // Mark []byte(str) range expression to reuse string backing storage.
 842                 // It is safe because the storage cannot be mutated.
 843                 n := n.(*ir.RangeStmt)
 844                 if n.X.Op() == ir.OSTR2BYTES {
 845                         n.X.(*ir.ConvExpr).SetOp(ir.OSTR2BYTESTMP)
 846                 }
 847
 848                 t := o.markTemp()
 849                 n.X = o.expr(n.X, nil)
 850
 851                 orderBody := true
 852                 xt := typecheck.RangeExprType(n.X.Type())
 853                 switch xt.Kind() {
 854                 default:
 855                         base.Fatalf("order.stmt range %v", n.Type())
 856
 857                 case types.TARRAY, types.TSLICE:
 858                         if n.Value == nil || ir.IsBlank(n.Value) {
 859                                 // for i := range x will only use x once, to compute len(x).
 860                                 // No need to copy it.
 861                                 break
 862                         }
 863                         fallthrough
 864
 865                 case types.TCHAN, types.TSTRING:
 866                         // chan, string, slice, array ranges use value multiple times.
 867                         // make copy.
 868                         r := n.X
 869
 870                         if r.Type().IsString() && r.Type() != types.Types[types.TSTRING] {
 871                                 r = ir.NewConvExpr(base.Pos, ir.OCONV, nil, r)
 872                                 r.SetType(types.Types[types.TSTRING])
 873                                 r = typecheck.Expr(r)
 874                         }
 875
 876                         n.X = o.copyExpr(r)
 877
 878                 case types.TMAP:
 879                         if isMapClear(n) {
 880                                 // Preserve the body of the map clear pattern so it can
 881                                 // be detected during walk. The loop body will not be used
 882                                 // when optimizing away the range loop to a runtime call.
 883                                 orderBody = false
 884                                 break
 885                         }
 886
 887                         // copy the map value in case it is a map literal.
 888                         // TODO(rsc): Make tmp = literal expressions reuse tmp.
 889                         // For maps tmp is just one word so it hardly matters.
 890                         r := n.X
 891                         n.X = o.copyExpr(r)
 892
 893                         // n.Prealloc is the temp for the iterator.
 894                         // MapIterType contains pointers and needs to be zeroed.
 895                         n.Prealloc = o.newTemp(reflectdata.MapIterType(xt), true)
 896                 }
 897                 n.Key = o.exprInPlace(n.Key)
 898                 n.Value = o.exprInPlace(n.Value)
 899                 if orderBody {
 900                         orderBlock(&n.Body, o.free)
 901                 }
 902                 o.out = append(o.out, n)
 903                 o.cleanTemp(t)
 904
 905         case ir.ORETURN:
 906                 n := n.(*ir.ReturnStmt)
 907                 o.exprList(n.Results)
 908                 o.out = append(o.out, n)
 909
 910         // Special: clean case temporaries in each block entry.
 911         // Select must enter one of its blocks, so there is no
 912         // need for a cleaning at the end.
 913         // Doubly special: evaluation order for select is stricter
 914         // than ordinary expressions. Even something like p.c
 915         // has to be hoisted into a temporary, so that it cannot be
 916         // reordered after the channel evaluation for a different
 917         // case (if p were nil, then the timing of the fault would
 918         // give this away).
 919         case ir.OSELECT:
 920                 n := n.(*ir.SelectStmt)
 921                 t := o.markTemp()
 922                 for _, ncas := range n.Cases {
 923                         r := ncas.Comm
 924                         ir.SetPos(ncas)
 925
 926                         // Append any new body prologue to ninit.
 927                         // The next loop will insert ninit into nbody.
 928                         if len(ncas.Init()) != 0 {
 929                                 base.Fatalf("order select ninit")
 930                         }
 931                         if r == nil {
 932                                 continue
 933                         }
 934                         switch r.Op() {
 935                         default:
 936                                 ir.Dump("select case", r)
 937                                 base.Fatalf("unknown op in select %v", r.Op())
 938
 939                         case ir.OSELRECV2:
 940                                 // case x, ok = <-c
 941                                 r := r.(*ir.AssignListStmt)
 942                                 recv := r.Rhs[0].(*ir.UnaryExpr)
 943                                 recv.X = o.expr(recv.X, nil)
 944                                 if !ir.IsAutoTmp(recv.X) {
 945                                         recv.X = o.copyExpr(recv.X)
 946                                 }
 947                                 init := ir.TakeInit(r)
 948
 949                                 colas := r.Def
 950                                 do := func(i int, t *types.Type) {
 951                                         n := r.Lhs[i]
 952                                         if ir.IsBlank(n) {
 953                                                 return
 954                                         }
 955                                         // If this is case x := <-ch or case x, y := <-ch, the case has
 956                                         // the ODCL nodes to declare x and y. We want to delay that
 957                                         // declaration (and possible allocation) until inside the case body.
 958                                         // Delete the ODCL nodes here and recreate them inside the body below.
 959                                         if colas {
 960                                                 if len(init) > 0 && init[0].Op() == ir.ODCL && init[0].(*ir.Decl).X == n {
 961                                                         init = init[1:]
 962
 963                                                         // iimport may have added a default initialization assignment,
 964                                                         // due to how it handles ODCL statements.
 965                                                         if len(init) > 0 && init[0].Op() == ir.OAS && init[0].(*ir.AssignStmt).X == n {
 966                                                                 init = init[1:]
 967                                                         }
 968                                                 }
 969                                                 dcl := typecheck.Stmt(ir.NewDecl(base.Pos, ir.ODCL, n.(*ir.Name)))
 970                                                 ncas.PtrInit().Append(dcl)
 971                                         }
 972                                         tmp := o.newTemp(t, t.HasPointers())
 973                                         as := typecheck.Stmt(ir.NewAssignStmt(base.Pos, n, typecheck.Conv(tmp, n.Type())))
 974                                         ncas.PtrInit().Append(as)
 975                                         r.Lhs[i] = tmp
 976                                 }
 977                                 do(0, recv.X.Type().Elem())
 978                                 do(1, types.Types[types.TBOOL])
 979                                 if len(init) != 0 {
 980                                         ir.DumpList("ninit", r.Init())
 981                                         base.Fatalf("ninit on select recv")
 982                                 }
 983                                 orderBlock(ncas.PtrInit(), o.free)
 984
 985                         case ir.OSEND:
 986                                 r := r.(*ir.SendStmt)
 987                                 if len(r.Init()) != 0 {
 988                                         ir.DumpList("ninit", r.Init())
 989                                         base.Fatalf("ninit on select send")
 990                                 }
 991
 992                                 // case c <- x
 993                                 // r->left is c, r->right is x, both are always evaluated.
 994                                 r.Chan = o.expr(r.Chan, nil)
 995
 996                                 if !ir.IsAutoTmp(r.Chan) {
 997                                         r.Chan = o.copyExpr(r.Chan)
 998                                 }
 999                                 r.Value = o.expr(r.Value, nil)
1000                                 if !ir.IsAutoTmp(r.Value) {
1001                                         r.Value = o.copyExpr(r.Value)
1002                                 }
1003                         }
1004                 }
1005                 // Now that we have accumulated all the temporaries, clean them.
1006                 // Also insert any ninit queued during the previous loop.
1007                 // (The temporary cleaning must follow that ninit work.)
1008                 for _, cas := range n.Cases {
1009                         orderBlock(&cas.Body, o.free)
1010                         cas.Body.Prepend(o.cleanTempNoPop(t)...)
1011
1012                         // TODO(mdempsky): Is this actually necessary?
1013                         // walkSelect appears to walk Ninit.
1014                         cas.Body.Prepend(ir.TakeInit(cas)...)
1015                 }
1016
1017                 o.out = append(o.out, n)
1018                 o.popTemp(t)
1019
1020         // Special: value being sent is passed as a pointer; make it addressable.
1021         case ir.OSEND:
1022                 n := n.(*ir.SendStmt)
1023                 t := o.markTemp()
1024                 n.Chan = o.expr(n.Chan, nil)
1025                 n.Value = o.expr(n.Value, nil)
1026                 if base.Flag.Cfg.Instrumenting {
1027                         // Force copying to the stack so that (chan T)(nil) <- x
1028                         // is still instrumented as a read of x.
1029                         n.Value = o.copyExpr(n.Value)
1030                 } else {
1031                         n.Value = o.addrTemp(n.Value)
1032                 }
1033                 o.out = append(o.out, n)
1034                 o.cleanTemp(t)
1035
1036         // TODO(rsc): Clean temporaries more aggressively.
1037         // Note that because walkSwitch will rewrite some of the
1038         // switch into a binary search, this is not as easy as it looks.
1039         // (If we ran that code here we could invoke order.stmt on
1040         // the if-else chain instead.)
1041         // For now just clean all the temporaries at the end.
1042         // In practice that's fine.
1043         case ir.OSWITCH:
1044                 n := n.(*ir.SwitchStmt)
1045                 if base.Debug.Libfuzzer != 0 && !hasDefaultCase(n) {
1046                         // Add empty "default:" case for instrumentation.
1047                         n.Cases = append(n.Cases, ir.NewCaseStmt(base.Pos, nil, nil))
1048                 }
1049
1050                 t := o.markTemp()
1051                 n.Tag = o.expr(n.Tag, nil)
1052                 for _, ncas := range n.Cases {
1053                         o.exprListInPlace(ncas.List)
1054                         orderBlock(&ncas.Body, o.free)
1055                 }
1056
1057                 o.out = append(o.out, n)
1058                 o.cleanTemp(t)
1059         }
1060
1061         base.Pos = lno
1062 }
1063
1064 func hasDefaultCase(n *ir.SwitchStmt) bool {
1065         for _, ncas := range n.Cases {
1066                 if len(ncas.List) == 0 {
1067                         return true
1068                 }
1069         }
1070         return false
1071 }
1072
1073 // exprList orders the expression list l into o.
1074 func (o *orderState) exprList(l ir.Nodes) {
1075         s := l
1076         for i := range s {
1077                 s[i] = o.expr(s[i], nil)
1078         }
1079 }
1080
1081 // exprListInPlace orders the expression list l but saves
1082 // the side effects on the individual expression ninit lists.
1083 func (o *orderState) exprListInPlace(l ir.Nodes) {
1084         s := l
1085         for i := range s {
1086                 s[i] = o.exprInPlace(s[i])
1087         }
1088 }
1089
1090 func (o *orderState) exprNoLHS(n ir.Node) ir.Node {
1091         return o.expr(n, nil)
1092 }
1093
1094 // expr orders a single expression, appending side
1095 // effects to o.out as needed.
1096 // If this is part of an assignment lhs = *np, lhs is given.
1097 // Otherwise lhs == nil. (When lhs != nil it may be possible
1098 // to avoid copying the result of the expression to a temporary.)
1099 // The result of expr MUST be assigned back to n, e.g.
1100 //
1101 //      n.Left = o.expr(n.Left, lhs)
1102 func (o *orderState) expr(n, lhs ir.Node) ir.Node {
1103         if n == nil {
1104                 return n
1105         }
1106         lno := ir.SetPos(n)
1107         n = o.expr1(n, lhs)
1108         base.Pos = lno
1109         return n
1110 }
1111
1112 func (o *orderState) expr1(n, lhs ir.Node) ir.Node {
1113         o.init(n)
1114
1115         switch n.Op() {
1116         default:
1117                 if o.edit == nil {
1118                         o.edit = o.exprNoLHS // create closure once
1119                 }
1120                 ir.EditChildren(n, o.edit)
1121                 return n
1122
1123         // Addition of strings turns into a function call.
1124         // Allocate a temporary to hold the strings.
1125         // Fewer than 5 strings use direct runtime helpers.
1126         case ir.OADDSTR:
1127                 n := n.(*ir.AddStringExpr)
1128                 o.exprList(n.List)
1129
1130                 if len(n.List) > 5 {
1131                         t := types.NewArray(types.Types[types.TSTRING], int64(len(n.List)))
1132                         n.Prealloc = o.newTemp(t, false)
1133                 }
1134
1135                 // Mark string(byteSlice) arguments to reuse byteSlice backing
1136                 // buffer during conversion. String concatenation does not
1137                 // memorize the strings for later use, so it is safe.
1138                 // However, we can do it only if there is at least one non-empty string literal.
1139                 // Otherwise if all other arguments are empty strings,
1140                 // concatstrings will return the reference to the temp string
1141                 // to the caller.
1142                 hasbyte := false
1143
1144                 haslit := false
1145                 for _, n1 := range n.List {
1146                         hasbyte = hasbyte || n1.Op() == ir.OBYTES2STR
1147                         haslit = haslit || n1.Op() == ir.OLITERAL && len(ir.StringVal(n1)) != 0
1148                 }
1149
1150                 if haslit && hasbyte {
1151                         for _, n2 := range n.List {
1152                                 if n2.Op() == ir.OBYTES2STR {
1153                                         n2 := n2.(*ir.ConvExpr)
1154                                         n2.SetOp(ir.OBYTES2STRTMP)
1155                                 }
1156                         }
1157                 }
1158                 return n
1159
1160         case ir.OINDEXMAP:
1161                 n := n.(*ir.IndexExpr)
1162                 n.X = o.expr(n.X, nil)
1163                 n.Index = o.expr(n.Index, nil)
1164                 needCopy := false
1165
1166                 if !n.Assigned {
1167                         // Enforce that any []byte slices we are not copying
1168                         // can not be changed before the map index by forcing
1169                         // the map index to happen immediately following the
1170                         // conversions. See copyExpr a few lines below.
1171                         needCopy = mapKeyReplaceStrConv(n.Index)
1172
1173                         if base.Flag.Cfg.Instrumenting {
1174                                 // Race detector needs the copy.
1175                                 needCopy = true
1176                         }
1177                 }
1178
1179                 // key must be addressable
1180                 n.Index = o.mapKeyTemp(n.X.Type(), n.Index)
1181                 if needCopy {
1182                         return o.copyExpr(n)
1183                 }
1184                 return n
1185
1186         // concrete type (not interface) argument might need an addressable
1187         // temporary to pass to the runtime conversion routine.
1188         case ir.OCONVIFACE, ir.OCONVIDATA:
1189                 n := n.(*ir.ConvExpr)
1190                 n.X = o.expr(n.X, nil)
1191                 if n.X.Type().IsInterface() {
1192                         return n
1193                 }
1194                 if _, _, needsaddr := dataWordFuncName(n.X.Type()); needsaddr || isStaticCompositeLiteral(n.X) {
1195                         // Need a temp if we need to pass the address to the conversion function.
1196                         // We also process static composite literal node here, making a named static global
1197                         // whose address we can put directly in an interface (see OCONVIFACE/OCONVIDATA case in walk).
1198                         n.X = o.addrTemp(n.X)
1199                 }
1200                 return n
1201
1202         case ir.OCONVNOP:
1203                 n := n.(*ir.ConvExpr)
1204                 if n.X.Op() == ir.OCALLMETH {
1205                         base.FatalfAt(n.X.Pos(), "OCALLMETH missed by typecheck")
1206                 }
1207                 if n.Type().IsKind(types.TUNSAFEPTR) && n.X.Type().IsKind(types.TUINTPTR) && (n.X.Op() == ir.OCALLFUNC || n.X.Op() == ir.OCALLINTER) {
1208                         call := n.X.(*ir.CallExpr)
1209                         // When reordering unsafe.Pointer(f()) into a separate
1210                         // statement, the conversion and function call must stay
1211                         // together. See golang.org/issue/15329.
1212                         o.init(call)
1213                         o.call(call)
1214                         if lhs == nil || lhs.Op() != ir.ONAME || base.Flag.Cfg.Instrumenting {
1215                                 return o.copyExpr(n)
1216                         }
1217                 } else {
1218                         n.X = o.expr(n.X, nil)
1219                 }
1220                 return n
1221
1222         case ir.OANDAND, ir.OOROR:
1223                 // ... = LHS && RHS
1224                 //
1225                 // var r bool
1226                 // r = LHS
1227                 // if r {       // or !r, for OROR
1228                 //     r = RHS
1229                 // }
1230                 // ... = r
1231
1232                 n := n.(*ir.LogicalExpr)
1233                 r := o.newTemp(n.Type(), false)
1234
1235                 // Evaluate left-hand side.
1236                 lhs := o.expr(n.X, nil)
1237                 o.out = append(o.out, typecheck.Stmt(ir.NewAssignStmt(base.Pos, r, lhs)))
1238
1239                 // Evaluate right-hand side, save generated code.
1240                 saveout := o.out
1241                 o.out = nil
1242                 t := o.markTemp()
1243                 o.edge()
1244                 rhs := o.expr(n.Y, nil)
1245                 o.out = append(o.out, typecheck.Stmt(ir.NewAssignStmt(base.Pos, r, rhs)))
1246                 o.cleanTemp(t)
1247                 gen := o.out
1248                 o.out = saveout
1249
1250                 // If left-hand side doesn't cause a short-circuit, issue right-hand side.
1251                 nif := ir.NewIfStmt(base.Pos, r, nil, nil)
1252                 if n.Op() == ir.OANDAND {
1253                         nif.Body = gen
1254                 } else {
1255                         nif.Else = gen
1256                 }
1257                 o.out = append(o.out, nif)
1258                 return r
1259
1260         case ir.OCALLMETH:
1261                 base.FatalfAt(n.Pos(), "OCALLMETH missed by typecheck")
1262                 panic("unreachable")
1263
1264         case ir.OCALLFUNC,
1265                 ir.OCALLINTER,
1266                 ir.OCAP,
1267                 ir.OCOMPLEX,
1268                 ir.OCOPY,
1269                 ir.OIMAG,
1270                 ir.OLEN,
1271                 ir.OMAKECHAN,
1272                 ir.OMAKEMAP,
1273                 ir.OMAKESLICE,
1274                 ir.OMAKESLICECOPY,
1275                 ir.ONEW,
1276                 ir.OREAL,
1277                 ir.ORECOVERFP,
1278                 ir.OSTR2BYTES,
1279                 ir.OSTR2BYTESTMP,
1280                 ir.OSTR2RUNES:
1281
1282                 if isRuneCount(n) {
1283                         // len([]rune(s)) is rewritten to runtime.countrunes(s) later.
1284                         conv := n.(*ir.UnaryExpr).X.(*ir.ConvExpr)
1285                         conv.X = o.expr(conv.X, nil)
1286                 } else {
1287                         o.call(n)
1288                 }
1289
1290                 if lhs == nil || lhs.Op() != ir.ONAME || base.Flag.Cfg.Instrumenting {
1291                         return o.copyExpr(n)
1292                 }
1293                 return n
1294
1295         case ir.OINLCALL:
1296                 n := n.(*ir.InlinedCallExpr)
1297                 o.stmtList(n.Body)
1298                 return n.SingleResult()
1299
1300         case ir.OAPPEND:
1301                 // Check for append(x, make([]T, y)...) .
1302                 n := n.(*ir.CallExpr)
1303                 if isAppendOfMake(n) {
1304                         n.Args[0] = o.expr(n.Args[0], nil) // order x
1305                         mk := n.Args[1].(*ir.MakeExpr)
1306                         mk.Len = o.expr(mk.Len, nil) // order y
1307                 } else {
1308                         o.exprList(n.Args)
1309                 }
1310
1311                 if lhs == nil || lhs.Op() != ir.ONAME && !ir.SameSafeExpr(lhs, n.Args[0]) {
1312                         return o.copyExpr(n)
1313                 }
1314                 return n
1315
1316         case ir.OSLICE, ir.OSLICEARR, ir.OSLICESTR, ir.OSLICE3, ir.OSLICE3ARR:
1317                 n := n.(*ir.SliceExpr)
1318                 n.X = o.expr(n.X, nil)
1319                 n.Low = o.cheapExpr(o.expr(n.Low, nil))
1320                 n.High = o.cheapExpr(o.expr(n.High, nil))
1321                 n.Max = o.cheapExpr(o.expr(n.Max, nil))
1322                 if lhs == nil || lhs.Op() != ir.ONAME && !ir.SameSafeExpr(lhs, n.X) {
1323                         return o.copyExpr(n)
1324                 }
1325                 return n
1326
1327         case ir.OCLOSURE:
1328                 n := n.(*ir.ClosureExpr)
1329                 if n.Transient() && len(n.Func.ClosureVars) > 0 {
1330                         n.Prealloc = o.newTemp(typecheck.ClosureType(n), false)
1331                 }
1332                 return n
1333
1334         case ir.OMETHVALUE:
1335                 n := n.(*ir.SelectorExpr)
1336                 n.X = o.expr(n.X, nil)
1337                 if n.Transient() {
1338                         t := typecheck.MethodValueType(n)
1339                         n.Prealloc = o.newTemp(t, false)
1340                 }
1341                 return n
1342
1343         case ir.OSLICELIT:
1344                 n := n.(*ir.CompLitExpr)
1345                 o.exprList(n.List)
1346                 if n.Transient() {
1347                         t := types.NewArray(n.Type().Elem(), n.Len)
1348                         n.Prealloc = o.newTemp(t, false)
1349                 }
1350                 return n
1351
1352         case ir.ODOTTYPE, ir.ODOTTYPE2:
1353                 n := n.(*ir.TypeAssertExpr)
1354                 n.X = o.expr(n.X, nil)
1355                 if !types.IsDirectIface(n.Type()) || base.Flag.Cfg.Instrumenting {
1356                         return o.copyExprClear(n)
1357                 }
1358                 return n
1359
1360         case ir.ORECV:
1361                 n := n.(*ir.UnaryExpr)
1362                 n.X = o.expr(n.X, nil)
1363                 return o.copyExprClear(n)
1364
1365         case ir.OEQ, ir.ONE, ir.OLT, ir.OLE, ir.OGT, ir.OGE:
1366                 n := n.(*ir.BinaryExpr)
1367                 n.X = o.expr(n.X, nil)
1368                 n.Y = o.expr(n.Y, nil)
1369
1370                 t := n.X.Type()
1371                 switch {
1372                 case t.IsString():
1373                         // Mark string(byteSlice) arguments to reuse byteSlice backing
1374                         // buffer during conversion. String comparison does not
1375                         // memorize the strings for later use, so it is safe.
1376                         if n.X.Op() == ir.OBYTES2STR {
1377                                 n.X.(*ir.ConvExpr).SetOp(ir.OBYTES2STRTMP)
1378                         }
1379                         if n.Y.Op() == ir.OBYTES2STR {
1380                                 n.Y.(*ir.ConvExpr).SetOp(ir.OBYTES2STRTMP)
1381                         }
1382
1383                 case t.IsStruct() || t.IsArray():
1384                         // for complex comparisons, we need both args to be
1385                         // addressable so we can pass them to the runtime.
1386                         n.X = o.addrTemp(n.X)
1387                         n.Y = o.addrTemp(n.Y)
1388                 }
1389                 return n
1390
1391         case ir.OMAPLIT:
1392                 // Order map by converting:
1393                 //   map[int]int{
1394                 //     a(): b(),
1395                 //     c(): d(),
1396                 //     e(): f(),
1397                 //   }
1398                 // to
1399                 //   m := map[int]int{}
1400                 //   m[a()] = b()
1401                 //   m[c()] = d()
1402                 //   m[e()] = f()
1403                 // Then order the result.
1404                 // Without this special case, order would otherwise compute all
1405                 // the keys and values before storing any of them to the map.
1406                 // See issue 26552.
1407                 n := n.(*ir.CompLitExpr)
1408                 entries := n.List
1409                 statics := entries[:0]
1410                 var dynamics []*ir.KeyExpr
1411                 for _, r := range entries {
1412                         r := r.(*ir.KeyExpr)
1413
1414                         if !isStaticCompositeLiteral(r.Key) || !isStaticCompositeLiteral(r.Value) {
1415                                 dynamics = append(dynamics, r)
1416                                 continue
1417                         }
1418
1419                         // Recursively ordering some static entries can change them to dynamic;
1420                         // e.g., OCONVIFACE nodes. See #31777.
1421                         r = o.expr(r, nil).(*ir.KeyExpr)
1422                         if !isStaticCompositeLiteral(r.Key) || !isStaticCompositeLiteral(r.Value) {
1423                                 dynamics = append(dynamics, r)
1424                                 continue
1425                         }
1426
1427                         statics = append(statics, r)
1428                 }
1429                 n.List = statics
1430
1431                 if len(dynamics) == 0 {
1432                         return n
1433                 }
1434
1435                 // Emit the creation of the map (with all its static entries).
1436                 m := o.newTemp(n.Type(), false)
1437                 as := ir.NewAssignStmt(base.Pos, m, n)
1438                 typecheck.Stmt(as)
1439                 o.stmt(as)
1440
1441                 // Emit eval+insert of dynamic entries, one at a time.
1442                 for _, r := range dynamics {
1443                         as := ir.NewAssignStmt(base.Pos, ir.NewIndexExpr(base.Pos, m, r.Key), r.Value)
1444                         typecheck.Stmt(as) // Note: this converts the OINDEX to an OINDEXMAP
1445                         o.stmt(as)
1446                 }
1447
1448                 // Remember that we issued these assignments so we can include that count
1449                 // in the map alloc hint.
1450                 // We're assuming here that all the keys in the map literal are distinct.
1451                 // If any are equal, this will be an overcount. Probably not worth accounting
1452                 // for that, as equal keys in map literals are rare, and at worst we waste
1453                 // a bit of space.
1454                 n.Len += int64(len(dynamics))
1455
1456                 return m
1457         }
1458
1459         // No return - type-assertions above. Each case must return for itself.
1460 }
1461
1462 // as2func orders OAS2FUNC nodes. It creates temporaries to ensure left-to-right assignment.
1463 // The caller should order the right-hand side of the assignment before calling order.as2func.
1464 // It rewrites,
1465 //
1466 //      a, b, a = ...
1467 //
1468 // as
1469 //
1470 //      tmp1, tmp2, tmp3 = ...
1471 //      a, b, a = tmp1, tmp2, tmp3
1472 //
1473 // This is necessary to ensure left to right assignment order.
1474 func (o *orderState) as2func(n *ir.AssignListStmt) {
1475         results := n.Rhs[0].Type()
1476         as := ir.NewAssignListStmt(n.Pos(), ir.OAS2, nil, nil)
1477         for i, nl := range n.Lhs {
1478                 if !ir.IsBlank(nl) {
1479                         typ := results.Field(i).Type
1480                         tmp := o.newTemp(typ, typ.HasPointers())
1481                         n.Lhs[i] = tmp
1482                         as.Lhs = append(as.Lhs, nl)
1483                         as.Rhs = append(as.Rhs, tmp)
1484                 }
1485         }
1486
1487         o.out = append(o.out, n)
1488         o.stmt(typecheck.Stmt(as))
1489 }
1490
1491 // as2ok orders OAS2XXX with ok.
1492 // Just like as2func, this also adds temporaries to ensure left-to-right assignment.
1493 func (o *orderState) as2ok(n *ir.AssignListStmt) {
1494         as := ir.NewAssignListStmt(n.Pos(), ir.OAS2, nil, nil)
1495
1496         do := func(i int, typ *types.Type) {
1497                 if nl := n.Lhs[i]; !ir.IsBlank(nl) {
1498                         var tmp ir.Node = o.newTemp(typ, typ.HasPointers())
1499                         n.Lhs[i] = tmp
1500                         as.Lhs = append(as.Lhs, nl)
1501                         if i == 1 {
1502                                 // The "ok" result is an untyped boolean according to the Go
1503                                 // spec. We need to explicitly convert it to the LHS type in
1504                                 // case the latter is a defined boolean type (#8475).
1505                                 tmp = typecheck.Conv(tmp, nl.Type())
1506                         }
1507                         as.Rhs = append(as.Rhs, tmp)
1508                 }
1509         }
1510
1511         do(0, n.Rhs[0].Type())
1512         do(1, types.Types[types.TBOOL])
1513
1514         o.out = append(o.out, n)
1515         o.stmt(typecheck.Stmt(as))
1516 }
1517
1518 // isFuncPCIntrinsic returns whether n is a direct call of internal/abi.FuncPCABIxxx functions.
1519 func isFuncPCIntrinsic(n *ir.CallExpr) bool {
1520         if n.Op() != ir.OCALLFUNC || n.X.Op() != ir.ONAME {
1521                 return false
1522         }
1523         fn := n.X.(*ir.Name).Sym()
1524         return (fn.Name == "FuncPCABI0" || fn.Name == "FuncPCABIInternal") &&
1525                 (fn.Pkg.Path == "internal/abi" || fn.Pkg == types.LocalPkg && base.Ctxt.Pkgpath == "internal/abi")
1526 }
1527
1528 // isIfaceOfFunc returns whether n is an interface conversion from a direct reference of a func.
1529 func isIfaceOfFunc(n ir.Node) bool {
1530         return n.Op() == ir.OCONVIFACE && n.(*ir.ConvExpr).X.Op() == ir.ONAME && n.(*ir.ConvExpr).X.(*ir.Name).Class == ir.PFUNC
1531 }