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         ir.SetPos(fn) // Set reasonable position for instrumenting code. See issue 53688.
  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 __sancov_cntrs
 450         counter := staticinit.StaticName(types.Types[types.TUINT8])
 451         counter.SetLibfuzzer8BitCounter(true)
 452         // As well as setting SetLibfuzzer8BitCounter, we preemptively set the
 453         // symbol type to SLIBFUZZER_8BIT_COUNTER so that the race detector
 454         // instrumentation pass (which does not have access to the flags set by
 455         // SetLibfuzzer8BitCounter) knows to ignore them. This information is
 456         // lost by the time it reaches the compile step, so SetLibfuzzer8BitCounter
 457         // is still necessary.
 458         counter.Linksym().Type = objabi.SLIBFUZZER_8BIT_COUNTER
 459
 460         // We guarantee that the counter never becomes zero again once it has been
 461         // incremented once. This implementation follows the NeverZero optimization
 462         // presented by the paper:
 463         // "AFL++: Combining Incremental Steps of Fuzzing Research"
 464         // The NeverZero policy avoids the overflow to 0 by setting the counter to one
 465         // after it reaches 255 and so, if an edge is executed at least one time, the entry is
 466         // never 0.
 467         // Another policy presented in the paper is the Saturated Counters policy which
 468         // freezes the counter when it reaches the value of 255. However, a range
 469         // of experiments showed that that decreases overall performance.
 470         o.append(ir.NewIfStmt(base.Pos,
 471                 ir.NewBinaryExpr(base.Pos, ir.OEQ, counter, ir.NewInt(0xff)),
 472                 []ir.Node{ir.NewAssignStmt(base.Pos, counter, ir.NewInt(1))},
 473                 []ir.Node{ir.NewAssignOpStmt(base.Pos, ir.OADD, counter, ir.NewInt(1))}))
 474 }
 475
 476 // orderBlock orders the block of statements in n into a new slice,
 477 // and then replaces the old slice in n with the new slice.
 478 // free is a map that can be used to obtain temporary variables by type.
 479 func orderBlock(n *ir.Nodes, free map[string][]*ir.Name) {
 480         if len(*n) != 0 {
 481                 // Set reasonable position for instrumenting code. See issue 53688.
 482                 // It would be nice if ir.Nodes had a position (the opening {, probably),
 483                 // but it doesn't. So we use the first statement's position instead.
 484                 ir.SetPos((*n)[0])
 485         }
 486         var order orderState
 487         order.free = free
 488         mark := order.markTemp()
 489         order.edge()
 490         order.stmtList(*n)
 491         order.cleanTemp(mark)
 492         *n = order.out
 493 }
 494
 495 // exprInPlace orders the side effects in *np and
 496 // leaves them as the init list of the final *np.
 497 // The result of exprInPlace MUST be assigned back to n, e.g.
 498 //
 499 //      n.Left = o.exprInPlace(n.Left)
 500 func (o *orderState) exprInPlace(n ir.Node) ir.Node {
 501         var order orderState
 502         order.free = o.free
 503         n = order.expr(n, nil)
 504         n = ir.InitExpr(order.out, n)
 505
 506         // insert new temporaries from order
 507         // at head of outer list.
 508         o.temp = append(o.temp, order.temp...)
 509         return n
 510 }
 511
 512 // orderStmtInPlace orders the side effects of the single statement *np
 513 // and replaces it with the resulting statement list.
 514 // The result of orderStmtInPlace MUST be assigned back to n, e.g.
 515 //
 516 //      n.Left = orderStmtInPlace(n.Left)
 517 //
 518 // free is a map that can be used to obtain temporary variables by type.
 519 func orderStmtInPlace(n ir.Node, free map[string][]*ir.Name) ir.Node {
 520         var order orderState
 521         order.free = free
 522         mark := order.markTemp()
 523         order.stmt(n)
 524         order.cleanTemp(mark)
 525         return ir.NewBlockStmt(src.NoXPos, order.out)
 526 }
 527
 528 // init moves n's init list to o.out.
 529 func (o *orderState) init(n ir.Node) {
 530         if ir.MayBeShared(n) {
 531                 // For concurrency safety, don't mutate potentially shared nodes.
 532                 // First, ensure that no work is required here.
 533                 if len(n.Init()) > 0 {
 534                         base.Fatalf("order.init shared node with ninit")
 535                 }
 536                 return
 537         }
 538         o.stmtList(ir.TakeInit(n))
 539 }
 540
 541 // call orders the call expression n.
 542 // n.Op is OCALLFUNC/OCALLINTER or a builtin like OCOPY.
 543 func (o *orderState) call(nn ir.Node) {
 544         if len(nn.Init()) > 0 {
 545                 // Caller should have already called o.init(nn).
 546                 base.Fatalf("%v with unexpected ninit", nn.Op())
 547         }
 548         if nn.Op() == ir.OCALLMETH {
 549                 base.FatalfAt(nn.Pos(), "OCALLMETH missed by typecheck")
 550         }
 551
 552         // Builtin functions.
 553         if nn.Op() != ir.OCALLFUNC && nn.Op() != ir.OCALLINTER {
 554                 switch n := nn.(type) {
 555                 default:
 556                         base.Fatalf("unexpected call: %+v", n)
 557                 case *ir.UnaryExpr:
 558                         n.X = o.expr(n.X, nil)
 559                 case *ir.ConvExpr:
 560                         n.X = o.expr(n.X, nil)
 561                 case *ir.BinaryExpr:
 562                         n.X = o.expr(n.X, nil)
 563                         n.Y = o.expr(n.Y, nil)
 564                 case *ir.MakeExpr:
 565                         n.Len = o.expr(n.Len, nil)
 566                         n.Cap = o.expr(n.Cap, nil)
 567                 case *ir.CallExpr:
 568                         o.exprList(n.Args)
 569                 }
 570                 return
 571         }
 572
 573         n := nn.(*ir.CallExpr)
 574         typecheck.FixVariadicCall(n)
 575
 576         if isFuncPCIntrinsic(n) && isIfaceOfFunc(n.Args[0]) {
 577                 // For internal/abi.FuncPCABIxxx(fn), if fn is a defined function,
 578                 // do not introduce temporaries here, so it is easier to rewrite it
 579                 // to symbol address reference later in walk.
 580                 return
 581         }
 582
 583         n.X = o.expr(n.X, nil)
 584         o.exprList(n.Args)
 585 }
 586
 587 // mapAssign appends n to o.out.
 588 func (o *orderState) mapAssign(n ir.Node) {
 589         switch n.Op() {
 590         default:
 591                 base.Fatalf("order.mapAssign %v", n.Op())
 592
 593         case ir.OAS:
 594                 n := n.(*ir.AssignStmt)
 595                 if n.X.Op() == ir.OINDEXMAP {
 596                         n.Y = o.safeMapRHS(n.Y)
 597                 }
 598                 o.out = append(o.out, n)
 599         case ir.OASOP:
 600                 n := n.(*ir.AssignOpStmt)
 601                 if n.X.Op() == ir.OINDEXMAP {
 602                         n.Y = o.safeMapRHS(n.Y)
 603                 }
 604                 o.out = append(o.out, n)
 605         }
 606 }
 607
 608 func (o *orderState) safeMapRHS(r ir.Node) ir.Node {
 609         // Make sure we evaluate the RHS before starting the map insert.
 610         // We need to make sure the RHS won't panic.  See issue 22881.
 611         if r.Op() == ir.OAPPEND {
 612                 r := r.(*ir.CallExpr)
 613                 s := r.Args[1:]
 614                 for i, n := range s {
 615                         s[i] = o.cheapExpr(n)
 616                 }
 617                 return r
 618         }
 619         return o.cheapExpr(r)
 620 }
 621
 622 // stmt orders the statement n, appending to o.out.
 623 // Temporaries created during the statement are cleaned
 624 // up using VARKILL instructions as possible.
 625 func (o *orderState) stmt(n ir.Node) {
 626         if n == nil {
 627                 return
 628         }
 629
 630         lno := ir.SetPos(n)
 631         o.init(n)
 632
 633         switch n.Op() {
 634         default:
 635                 base.Fatalf("order.stmt %v", n.Op())
 636
 637         case ir.OVARKILL, ir.OVARLIVE, ir.OINLMARK:
 638                 o.out = append(o.out, n)
 639
 640         case ir.OAS:
 641                 n := n.(*ir.AssignStmt)
 642                 t := o.markTemp()
 643                 n.X = o.expr(n.X, nil)
 644                 n.Y = o.expr(n.Y, n.X)
 645                 o.mapAssign(n)
 646                 o.cleanTemp(t)
 647
 648         case ir.OASOP:
 649                 n := n.(*ir.AssignOpStmt)
 650                 t := o.markTemp()
 651                 n.X = o.expr(n.X, nil)
 652                 n.Y = o.expr(n.Y, nil)
 653
 654                 if base.Flag.Cfg.Instrumenting || n.X.Op() == ir.OINDEXMAP && (n.AsOp == ir.ODIV || n.AsOp == ir.OMOD) {
 655                         // Rewrite m[k] op= r into m[k] = m[k] op r so
 656                         // that we can ensure that if op panics
 657                         // because r is zero, the panic happens before
 658                         // the map assignment.
 659                         // DeepCopy is a big hammer here, but safeExpr
 660                         // makes sure there is nothing too deep being copied.
 661                         l1 := o.safeExpr(n.X)
 662                         l2 := ir.DeepCopy(src.NoXPos, l1)
 663                         if l2.Op() == ir.OINDEXMAP {
 664                                 l2 := l2.(*ir.IndexExpr)
 665                                 l2.Assigned = false
 666                         }
 667                         l2 = o.copyExpr(l2)
 668                         r := o.expr(typecheck.Expr(ir.NewBinaryExpr(n.Pos(), n.AsOp, l2, n.Y)), nil)
 669                         as := typecheck.Stmt(ir.NewAssignStmt(n.Pos(), l1, r))
 670                         o.mapAssign(as)
 671                         o.cleanTemp(t)
 672                         return
 673                 }
 674
 675                 o.mapAssign(n)
 676                 o.cleanTemp(t)
 677
 678         case ir.OAS2:
 679                 n := n.(*ir.AssignListStmt)
 680                 t := o.markTemp()
 681                 o.exprList(n.Lhs)
 682                 o.exprList(n.Rhs)
 683                 o.out = append(o.out, n)
 684                 o.cleanTemp(t)
 685
 686         // Special: avoid copy of func call n.Right
 687         case ir.OAS2FUNC:
 688                 n := n.(*ir.AssignListStmt)
 689                 t := o.markTemp()
 690                 o.exprList(n.Lhs)
 691                 call := n.Rhs[0]
 692                 o.init(call)
 693                 if ic, ok := call.(*ir.InlinedCallExpr); ok {
 694                         o.stmtList(ic.Body)
 695
 696                         n.SetOp(ir.OAS2)
 697                         n.Rhs = ic.ReturnVars
 698
 699                         o.exprList(n.Rhs)
 700                         o.out = append(o.out, n)
 701                 } else {
 702                         o.call(call)
 703                         o.as2func(n)
 704                 }
 705                 o.cleanTemp(t)
 706
 707         // Special: use temporary variables to hold result,
 708         // so that runtime can take address of temporary.
 709         // No temporary for blank assignment.
 710         //
 711         // OAS2MAPR: make sure key is addressable if needed,
 712         //           and make sure OINDEXMAP is not copied out.
 713         case ir.OAS2DOTTYPE, ir.OAS2RECV, ir.OAS2MAPR:
 714                 n := n.(*ir.AssignListStmt)
 715                 t := o.markTemp()
 716                 o.exprList(n.Lhs)
 717
 718                 switch r := n.Rhs[0]; r.Op() {
 719                 case ir.ODOTTYPE2:
 720                         r := r.(*ir.TypeAssertExpr)
 721                         r.X = o.expr(r.X, nil)
 722                 case ir.ODYNAMICDOTTYPE2:
 723                         r := r.(*ir.DynamicTypeAssertExpr)
 724                         r.X = o.expr(r.X, nil)
 725                         r.RType = o.expr(r.RType, nil)
 726                         r.ITab = o.expr(r.ITab, nil)
 727                 case ir.ORECV:
 728                         r := r.(*ir.UnaryExpr)
 729                         r.X = o.expr(r.X, nil)
 730                 case ir.OINDEXMAP:
 731                         r := r.(*ir.IndexExpr)
 732                         r.X = o.expr(r.X, nil)
 733                         r.Index = o.expr(r.Index, nil)
 734                         // See similar conversion for OINDEXMAP below.
 735                         _ = mapKeyReplaceStrConv(r.Index)
 736                         r.Index = o.mapKeyTemp(r.X.Type(), r.Index)
 737                 default:
 738                         base.Fatalf("order.stmt: %v", r.Op())
 739                 }
 740
 741                 o.as2ok(n)
 742                 o.cleanTemp(t)
 743
 744         // Special: does not save n onto out.
 745         case ir.OBLOCK:
 746                 n := n.(*ir.BlockStmt)
 747                 o.stmtList(n.List)
 748
 749         // Special: n->left is not an expression; save as is.
 750         case ir.OBREAK,
 751                 ir.OCONTINUE,
 752                 ir.ODCL,
 753                 ir.ODCLCONST,
 754                 ir.ODCLTYPE,
 755                 ir.OFALL,
 756                 ir.OGOTO,
 757                 ir.OLABEL,
 758                 ir.OTAILCALL:
 759                 o.out = append(o.out, n)
 760
 761         // Special: handle call arguments.
 762         case ir.OCALLFUNC, ir.OCALLINTER:
 763                 n := n.(*ir.CallExpr)
 764                 t := o.markTemp()
 765                 o.call(n)
 766                 o.out = append(o.out, n)
 767                 o.cleanTemp(t)
 768
 769         case ir.OINLCALL:
 770                 n := n.(*ir.InlinedCallExpr)
 771                 o.stmtList(n.Body)
 772
 773                 // discard results; double-check for no side effects
 774                 for _, result := range n.ReturnVars {
 775                         if staticinit.AnySideEffects(result) {
 776                                 base.FatalfAt(result.Pos(), "inlined call result has side effects: %v", result)
 777                         }
 778                 }
 779
 780         case ir.OCHECKNIL, ir.OCLOSE, ir.OPANIC, ir.ORECV:
 781                 n := n.(*ir.UnaryExpr)
 782                 t := o.markTemp()
 783                 n.X = o.expr(n.X, nil)
 784                 o.out = append(o.out, n)
 785                 o.cleanTemp(t)
 786
 787         case ir.OCOPY:
 788                 n := n.(*ir.BinaryExpr)
 789                 t := o.markTemp()
 790                 n.X = o.expr(n.X, nil)
 791                 n.Y = o.expr(n.Y, nil)
 792                 o.out = append(o.out, n)
 793                 o.cleanTemp(t)
 794
 795         case ir.OPRINT, ir.OPRINTN, ir.ORECOVERFP:
 796                 n := n.(*ir.CallExpr)
 797                 t := o.markTemp()
 798                 o.call(n)
 799                 o.out = append(o.out, n)
 800                 o.cleanTemp(t)
 801
 802         // Special: order arguments to inner call but not call itself.
 803         case ir.ODEFER, ir.OGO:
 804                 n := n.(*ir.GoDeferStmt)
 805                 t := o.markTemp()
 806                 o.init(n.Call)
 807                 o.call(n.Call)
 808                 o.out = append(o.out, n)
 809                 o.cleanTemp(t)
 810
 811         case ir.ODELETE:
 812                 n := n.(*ir.CallExpr)
 813                 t := o.markTemp()
 814                 n.Args[0] = o.expr(n.Args[0], nil)
 815                 n.Args[1] = o.expr(n.Args[1], nil)
 816                 n.Args[1] = o.mapKeyTemp(n.Args[0].Type(), n.Args[1])
 817                 o.out = append(o.out, n)
 818                 o.cleanTemp(t)
 819
 820         // Clean temporaries from condition evaluation at
 821         // beginning of loop body and after for statement.
 822         case ir.OFOR:
 823                 n := n.(*ir.ForStmt)
 824                 t := o.markTemp()
 825                 n.Cond = o.exprInPlace(n.Cond)
 826                 n.Body.Prepend(o.cleanTempNoPop(t)...)
 827                 orderBlock(&n.Body, o.free)
 828                 n.Post = orderStmtInPlace(n.Post, o.free)
 829                 o.out = append(o.out, n)
 830                 o.cleanTemp(t)
 831
 832         // Clean temporaries from condition at
 833         // beginning of both branches.
 834         case ir.OIF:
 835                 n := n.(*ir.IfStmt)
 836                 t := o.markTemp()
 837                 n.Cond = o.exprInPlace(n.Cond)
 838                 n.Body.Prepend(o.cleanTempNoPop(t)...)
 839                 n.Else.Prepend(o.cleanTempNoPop(t)...)
 840                 o.popTemp(t)
 841                 orderBlock(&n.Body, o.free)
 842                 orderBlock(&n.Else, o.free)
 843                 o.out = append(o.out, n)
 844
 845         case ir.ORANGE:
 846                 // n.Right is the expression being ranged over.
 847                 // order it, and then make a copy if we need one.
 848                 // We almost always do, to ensure that we don't
 849                 // see any value changes made during the loop.
 850                 // Usually the copy is cheap (e.g., array pointer,
 851                 // chan, slice, string are all tiny).
 852                 // The exception is ranging over an array value
 853                 // (not a slice, not a pointer to array),
 854                 // which must make a copy to avoid seeing updates made during
 855                 // the range body. Ranging over an array value is uncommon though.
 856
 857                 // Mark []byte(str) range expression to reuse string backing storage.
 858                 // It is safe because the storage cannot be mutated.
 859                 n := n.(*ir.RangeStmt)
 860                 if n.X.Op() == ir.OSTR2BYTES {
 861                         n.X.(*ir.ConvExpr).SetOp(ir.OSTR2BYTESTMP)
 862                 }
 863
 864                 t := o.markTemp()
 865                 n.X = o.expr(n.X, nil)
 866
 867                 orderBody := true
 868                 xt := typecheck.RangeExprType(n.X.Type())
 869                 switch xt.Kind() {
 870                 default:
 871                         base.Fatalf("order.stmt range %v", n.Type())
 872
 873                 case types.TARRAY, types.TSLICE:
 874                         if n.Value == nil || ir.IsBlank(n.Value) {
 875                                 // for i := range x will only use x once, to compute len(x).
 876                                 // No need to copy it.
 877                                 break
 878                         }
 879                         fallthrough
 880
 881                 case types.TCHAN, types.TSTRING:
 882                         // chan, string, slice, array ranges use value multiple times.
 883                         // make copy.
 884                         r := n.X
 885
 886                         if r.Type().IsString() && r.Type() != types.Types[types.TSTRING] {
 887                                 r = ir.NewConvExpr(base.Pos, ir.OCONV, nil, r)
 888                                 r.SetType(types.Types[types.TSTRING])
 889                                 r = typecheck.Expr(r)
 890                         }
 891
 892                         n.X = o.copyExpr(r)
 893
 894                 case types.TMAP:
 895                         if isMapClear(n) {
 896                                 // Preserve the body of the map clear pattern so it can
 897                                 // be detected during walk. The loop body will not be used
 898                                 // when optimizing away the range loop to a runtime call.
 899                                 orderBody = false
 900                                 break
 901                         }
 902
 903                         // copy the map value in case it is a map literal.
 904                         // TODO(rsc): Make tmp = literal expressions reuse tmp.
 905                         // For maps tmp is just one word so it hardly matters.
 906                         r := n.X
 907                         n.X = o.copyExpr(r)
 908
 909                         // n.Prealloc is the temp for the iterator.
 910                         // MapIterType contains pointers and needs to be zeroed.
 911                         n.Prealloc = o.newTemp(reflectdata.MapIterType(xt), true)
 912                 }
 913                 n.Key = o.exprInPlace(n.Key)
 914                 n.Value = o.exprInPlace(n.Value)
 915                 if orderBody {
 916                         orderBlock(&n.Body, o.free)
 917                 }
 918                 o.out = append(o.out, n)
 919                 o.cleanTemp(t)
 920
 921         case ir.ORETURN:
 922                 n := n.(*ir.ReturnStmt)
 923                 o.exprList(n.Results)
 924                 o.out = append(o.out, n)
 925
 926         // Special: clean case temporaries in each block entry.
 927         // Select must enter one of its blocks, so there is no
 928         // need for a cleaning at the end.
 929         // Doubly special: evaluation order for select is stricter
 930         // than ordinary expressions. Even something like p.c
 931         // has to be hoisted into a temporary, so that it cannot be
 932         // reordered after the channel evaluation for a different
 933         // case (if p were nil, then the timing of the fault would
 934         // give this away).
 935         case ir.OSELECT:
 936                 n := n.(*ir.SelectStmt)
 937                 t := o.markTemp()
 938                 for _, ncas := range n.Cases {
 939                         r := ncas.Comm
 940                         ir.SetPos(ncas)
 941
 942                         // Append any new body prologue to ninit.
 943                         // The next loop will insert ninit into nbody.
 944                         if len(ncas.Init()) != 0 {
 945                                 base.Fatalf("order select ninit")
 946                         }
 947                         if r == nil {
 948                                 continue
 949                         }
 950                         switch r.Op() {
 951                         default:
 952                                 ir.Dump("select case", r)
 953                                 base.Fatalf("unknown op in select %v", r.Op())
 954
 955                         case ir.OSELRECV2:
 956                                 // case x, ok = <-c
 957                                 r := r.(*ir.AssignListStmt)
 958                                 recv := r.Rhs[0].(*ir.UnaryExpr)
 959                                 recv.X = o.expr(recv.X, nil)
 960                                 if !ir.IsAutoTmp(recv.X) {
 961                                         recv.X = o.copyExpr(recv.X)
 962                                 }
 963                                 init := ir.TakeInit(r)
 964
 965                                 colas := r.Def
 966                                 do := func(i int, t *types.Type) {
 967                                         n := r.Lhs[i]
 968                                         if ir.IsBlank(n) {
 969                                                 return
 970                                         }
 971                                         // If this is case x := <-ch or case x, y := <-ch, the case has
 972                                         // the ODCL nodes to declare x and y. We want to delay that
 973                                         // declaration (and possible allocation) until inside the case body.
 974                                         // Delete the ODCL nodes here and recreate them inside the body below.
 975                                         if colas {
 976                                                 if len(init) > 0 && init[0].Op() == ir.ODCL && init[0].(*ir.Decl).X == n {
 977                                                         init = init[1:]
 978
 979                                                         // iimport may have added a default initialization assignment,
 980                                                         // due to how it handles ODCL statements.
 981                                                         if len(init) > 0 && init[0].Op() == ir.OAS && init[0].(*ir.AssignStmt).X == n {
 982                                                                 init = init[1:]
 983                                                         }
 984                                                 }
 985                                                 dcl := typecheck.Stmt(ir.NewDecl(base.Pos, ir.ODCL, n.(*ir.Name)))
 986                                                 ncas.PtrInit().Append(dcl)
 987                                         }
 988                                         tmp := o.newTemp(t, t.HasPointers())
 989                                         as := typecheck.Stmt(ir.NewAssignStmt(base.Pos, n, typecheck.Conv(tmp, n.Type())))
 990                                         ncas.PtrInit().Append(as)
 991                                         r.Lhs[i] = tmp
 992                                 }
 993                                 do(0, recv.X.Type().Elem())
 994                                 do(1, types.Types[types.TBOOL])
 995                                 if len(init) != 0 {
 996                                         ir.DumpList("ninit", init)
 997                                         base.Fatalf("ninit on select recv")
 998                                 }
 999                                 orderBlock(ncas.PtrInit(), o.free)
1000
1001                         case ir.OSEND:
1002                                 r := r.(*ir.SendStmt)
1003                                 if len(r.Init()) != 0 {
1004                                         ir.DumpList("ninit", r.Init())
1005                                         base.Fatalf("ninit on select send")
1006                                 }
1007
1008                                 // case c <- x
1009                                 // r->left is c, r->right is x, both are always evaluated.
1010                                 r.Chan = o.expr(r.Chan, nil)
1011
1012                                 if !ir.IsAutoTmp(r.Chan) {
1013                                         r.Chan = o.copyExpr(r.Chan)
1014                                 }
1015                                 r.Value = o.expr(r.Value, nil)
1016                                 if !ir.IsAutoTmp(r.Value) {
1017                                         r.Value = o.copyExpr(r.Value)
1018                                 }
1019                         }
1020                 }
1021                 // Now that we have accumulated all the temporaries, clean them.
1022                 // Also insert any ninit queued during the previous loop.
1023                 // (The temporary cleaning must follow that ninit work.)
1024                 for _, cas := range n.Cases {
1025                         orderBlock(&cas.Body, o.free)
1026                         cas.Body.Prepend(o.cleanTempNoPop(t)...)
1027
1028                         // TODO(mdempsky): Is this actually necessary?
1029                         // walkSelect appears to walk Ninit.
1030                         cas.Body.Prepend(ir.TakeInit(cas)...)
1031                 }
1032
1033                 o.out = append(o.out, n)
1034                 o.popTemp(t)
1035
1036         // Special: value being sent is passed as a pointer; make it addressable.
1037         case ir.OSEND:
1038                 n := n.(*ir.SendStmt)
1039                 t := o.markTemp()
1040                 n.Chan = o.expr(n.Chan, nil)
1041                 n.Value = o.expr(n.Value, nil)
1042                 if base.Flag.Cfg.Instrumenting {
1043                         // Force copying to the stack so that (chan T)(nil) <- x
1044                         // is still instrumented as a read of x.
1045                         n.Value = o.copyExpr(n.Value)
1046                 } else {
1047                         n.Value = o.addrTemp(n.Value)
1048                 }
1049                 o.out = append(o.out, n)
1050                 o.cleanTemp(t)
1051
1052         // TODO(rsc): Clean temporaries more aggressively.
1053         // Note that because walkSwitch will rewrite some of the
1054         // switch into a binary search, this is not as easy as it looks.
1055         // (If we ran that code here we could invoke order.stmt on
1056         // the if-else chain instead.)
1057         // For now just clean all the temporaries at the end.
1058         // In practice that's fine.
1059         case ir.OSWITCH:
1060                 n := n.(*ir.SwitchStmt)
1061                 if base.Debug.Libfuzzer != 0 && !hasDefaultCase(n) {
1062                         // Add empty "default:" case for instrumentation.
1063                         n.Cases = append(n.Cases, ir.NewCaseStmt(base.Pos, nil, nil))
1064                 }
1065
1066                 t := o.markTemp()
1067                 n.Tag = o.expr(n.Tag, nil)
1068                 for _, ncas := range n.Cases {
1069                         o.exprListInPlace(ncas.List)
1070                         orderBlock(&ncas.Body, o.free)
1071                 }
1072
1073                 o.out = append(o.out, n)
1074                 o.cleanTemp(t)
1075         }
1076
1077         base.Pos = lno
1078 }
1079
1080 func hasDefaultCase(n *ir.SwitchStmt) bool {
1081         for _, ncas := range n.Cases {
1082                 if len(ncas.List) == 0 {
1083                         return true
1084                 }
1085         }
1086         return false
1087 }
1088
1089 // exprList orders the expression list l into o.
1090 func (o *orderState) exprList(l ir.Nodes) {
1091         s := l
1092         for i := range s {
1093                 s[i] = o.expr(s[i], nil)
1094         }
1095 }
1096
1097 // exprListInPlace orders the expression list l but saves
1098 // the side effects on the individual expression ninit lists.
1099 func (o *orderState) exprListInPlace(l ir.Nodes) {
1100         s := l
1101         for i := range s {
1102                 s[i] = o.exprInPlace(s[i])
1103         }
1104 }
1105
1106 func (o *orderState) exprNoLHS(n ir.Node) ir.Node {
1107         return o.expr(n, nil)
1108 }
1109
1110 // expr orders a single expression, appending side
1111 // effects to o.out as needed.
1112 // If this is part of an assignment lhs = *np, lhs is given.
1113 // Otherwise lhs == nil. (When lhs != nil it may be possible
1114 // to avoid copying the result of the expression to a temporary.)
1115 // The result of expr MUST be assigned back to n, e.g.
1116 //
1117 //      n.Left = o.expr(n.Left, lhs)
1118 func (o *orderState) expr(n, lhs ir.Node) ir.Node {
1119         if n == nil {
1120                 return n
1121         }
1122         lno := ir.SetPos(n)
1123         n = o.expr1(n, lhs)
1124         base.Pos = lno
1125         return n
1126 }
1127
1128 func (o *orderState) expr1(n, lhs ir.Node) ir.Node {
1129         o.init(n)
1130
1131         switch n.Op() {
1132         default:
1133                 if o.edit == nil {
1134                         o.edit = o.exprNoLHS // create closure once
1135                 }
1136                 ir.EditChildren(n, o.edit)
1137                 return n
1138
1139         // Addition of strings turns into a function call.
1140         // Allocate a temporary to hold the strings.
1141         // Fewer than 5 strings use direct runtime helpers.
1142         case ir.OADDSTR:
1143                 n := n.(*ir.AddStringExpr)
1144                 o.exprList(n.List)
1145
1146                 if len(n.List) > 5 {
1147                         t := types.NewArray(types.Types[types.TSTRING], int64(len(n.List)))
1148                         n.Prealloc = o.newTemp(t, false)
1149                 }
1150
1151                 // Mark string(byteSlice) arguments to reuse byteSlice backing
1152                 // buffer during conversion. String concatenation does not
1153                 // memorize the strings for later use, so it is safe.
1154                 // However, we can do it only if there is at least one non-empty string literal.
1155                 // Otherwise if all other arguments are empty strings,
1156                 // concatstrings will return the reference to the temp string
1157                 // to the caller.
1158                 hasbyte := false
1159
1160                 haslit := false
1161                 for _, n1 := range n.List {
1162                         hasbyte = hasbyte || n1.Op() == ir.OBYTES2STR
1163                         haslit = haslit || n1.Op() == ir.OLITERAL && len(ir.StringVal(n1)) != 0
1164                 }
1165
1166                 if haslit && hasbyte {
1167                         for _, n2 := range n.List {
1168                                 if n2.Op() == ir.OBYTES2STR {
1169                                         n2 := n2.(*ir.ConvExpr)
1170                                         n2.SetOp(ir.OBYTES2STRTMP)
1171                                 }
1172                         }
1173                 }
1174                 return n
1175
1176         case ir.OINDEXMAP:
1177                 n := n.(*ir.IndexExpr)
1178                 n.X = o.expr(n.X, nil)
1179                 n.Index = o.expr(n.Index, nil)
1180                 needCopy := false
1181
1182                 if !n.Assigned {
1183                         // Enforce that any []byte slices we are not copying
1184                         // can not be changed before the map index by forcing
1185                         // the map index to happen immediately following the
1186                         // conversions. See copyExpr a few lines below.
1187                         needCopy = mapKeyReplaceStrConv(n.Index)
1188
1189                         if base.Flag.Cfg.Instrumenting {
1190                                 // Race detector needs the copy.
1191                                 needCopy = true
1192                         }
1193                 }
1194
1195                 // key must be addressable
1196                 n.Index = o.mapKeyTemp(n.X.Type(), n.Index)
1197                 if needCopy {
1198                         return o.copyExpr(n)
1199                 }
1200                 return n
1201
1202         // concrete type (not interface) argument might need an addressable
1203         // temporary to pass to the runtime conversion routine.
1204         case ir.OCONVIFACE, ir.OCONVIDATA:
1205                 n := n.(*ir.ConvExpr)
1206                 n.X = o.expr(n.X, nil)
1207                 if n.X.Type().IsInterface() {
1208                         return n
1209                 }
1210                 if _, _, needsaddr := dataWordFuncName(n.X.Type()); needsaddr || isStaticCompositeLiteral(n.X) {
1211                         // Need a temp if we need to pass the address to the conversion function.
1212                         // We also process static composite literal node here, making a named static global
1213                         // whose address we can put directly in an interface (see OCONVIFACE/OCONVIDATA case in walk).
1214                         n.X = o.addrTemp(n.X)
1215                 }
1216                 return n
1217
1218         case ir.OCONVNOP:
1219                 n := n.(*ir.ConvExpr)
1220                 if n.X.Op() == ir.OCALLMETH {
1221                         base.FatalfAt(n.X.Pos(), "OCALLMETH missed by typecheck")
1222                 }
1223                 if n.Type().IsKind(types.TUNSAFEPTR) && n.X.Type().IsKind(types.TUINTPTR) && (n.X.Op() == ir.OCALLFUNC || n.X.Op() == ir.OCALLINTER) {
1224                         call := n.X.(*ir.CallExpr)
1225                         // When reordering unsafe.Pointer(f()) into a separate
1226                         // statement, the conversion and function call must stay
1227                         // together. See golang.org/issue/15329.
1228                         o.init(call)
1229                         o.call(call)
1230                         if lhs == nil || lhs.Op() != ir.ONAME || base.Flag.Cfg.Instrumenting {
1231                                 return o.copyExpr(n)
1232                         }
1233                 } else {
1234                         n.X = o.expr(n.X, nil)
1235                 }
1236                 return n
1237
1238         case ir.OANDAND, ir.OOROR:
1239                 // ... = LHS && RHS
1240                 //
1241                 // var r bool
1242                 // r = LHS
1243                 // if r {       // or !r, for OROR
1244                 //     r = RHS
1245                 // }
1246                 // ... = r
1247
1248                 n := n.(*ir.LogicalExpr)
1249                 r := o.newTemp(n.Type(), false)
1250
1251                 // Evaluate left-hand side.
1252                 lhs := o.expr(n.X, nil)
1253                 o.out = append(o.out, typecheck.Stmt(ir.NewAssignStmt(base.Pos, r, lhs)))
1254
1255                 // Evaluate right-hand side, save generated code.
1256                 saveout := o.out
1257                 o.out = nil
1258                 t := o.markTemp()
1259                 o.edge()
1260                 rhs := o.expr(n.Y, nil)
1261                 o.out = append(o.out, typecheck.Stmt(ir.NewAssignStmt(base.Pos, r, rhs)))
1262                 o.cleanTemp(t)
1263                 gen := o.out
1264                 o.out = saveout
1265
1266                 // If left-hand side doesn't cause a short-circuit, issue right-hand side.
1267                 nif := ir.NewIfStmt(base.Pos, r, nil, nil)
1268                 if n.Op() == ir.OANDAND {
1269                         nif.Body = gen
1270                 } else {
1271                         nif.Else = gen
1272                 }
1273                 o.out = append(o.out, nif)
1274                 return r
1275
1276         case ir.OCALLMETH:
1277                 base.FatalfAt(n.Pos(), "OCALLMETH missed by typecheck")
1278                 panic("unreachable")
1279
1280         case ir.OCALLFUNC,
1281                 ir.OCALLINTER,
1282                 ir.OCAP,
1283                 ir.OCOMPLEX,
1284                 ir.OCOPY,
1285                 ir.OIMAG,
1286                 ir.OLEN,
1287                 ir.OMAKECHAN,
1288                 ir.OMAKEMAP,
1289                 ir.OMAKESLICE,
1290                 ir.OMAKESLICECOPY,
1291                 ir.ONEW,
1292                 ir.OREAL,
1293                 ir.ORECOVERFP,
1294                 ir.OSTR2BYTES,
1295                 ir.OSTR2BYTESTMP,
1296                 ir.OSTR2RUNES:
1297
1298                 if isRuneCount(n) {
1299                         // len([]rune(s)) is rewritten to runtime.countrunes(s) later.
1300                         conv := n.(*ir.UnaryExpr).X.(*ir.ConvExpr)
1301                         conv.X = o.expr(conv.X, nil)
1302                 } else {
1303                         o.call(n)
1304                 }
1305
1306                 if lhs == nil || lhs.Op() != ir.ONAME || base.Flag.Cfg.Instrumenting {
1307                         return o.copyExpr(n)
1308                 }
1309                 return n
1310
1311         case ir.OINLCALL:
1312                 n := n.(*ir.InlinedCallExpr)
1313                 o.stmtList(n.Body)
1314                 return n.SingleResult()
1315
1316         case ir.OAPPEND:
1317                 // Check for append(x, make([]T, y)...) .
1318                 n := n.(*ir.CallExpr)
1319                 if isAppendOfMake(n) {
1320                         n.Args[0] = o.expr(n.Args[0], nil) // order x
1321                         mk := n.Args[1].(*ir.MakeExpr)
1322                         mk.Len = o.expr(mk.Len, nil) // order y
1323                 } else {
1324                         o.exprList(n.Args)
1325                 }
1326
1327                 if lhs == nil || lhs.Op() != ir.ONAME && !ir.SameSafeExpr(lhs, n.Args[0]) {
1328                         return o.copyExpr(n)
1329                 }
1330                 return n
1331
1332         case ir.OSLICE, ir.OSLICEARR, ir.OSLICESTR, ir.OSLICE3, ir.OSLICE3ARR:
1333                 n := n.(*ir.SliceExpr)
1334                 n.X = o.expr(n.X, nil)
1335                 n.Low = o.cheapExpr(o.expr(n.Low, nil))
1336                 n.High = o.cheapExpr(o.expr(n.High, nil))
1337                 n.Max = o.cheapExpr(o.expr(n.Max, nil))
1338                 if lhs == nil || lhs.Op() != ir.ONAME && !ir.SameSafeExpr(lhs, n.X) {
1339                         return o.copyExpr(n)
1340                 }
1341                 return n
1342
1343         case ir.OCLOSURE:
1344                 n := n.(*ir.ClosureExpr)
1345                 if n.Transient() && len(n.Func.ClosureVars) > 0 {
1346                         n.Prealloc = o.newTemp(typecheck.ClosureType(n), false)
1347                 }
1348                 return n
1349
1350         case ir.OMETHVALUE:
1351                 n := n.(*ir.SelectorExpr)
1352                 n.X = o.expr(n.X, nil)
1353                 if n.Transient() {
1354                         t := typecheck.MethodValueType(n)
1355                         n.Prealloc = o.newTemp(t, false)
1356                 }
1357                 return n
1358
1359         case ir.OSLICELIT:
1360                 n := n.(*ir.CompLitExpr)
1361                 o.exprList(n.List)
1362                 if n.Transient() {
1363                         t := types.NewArray(n.Type().Elem(), n.Len)
1364                         n.Prealloc = o.newTemp(t, false)
1365                 }
1366                 return n
1367
1368         case ir.ODOTTYPE, ir.ODOTTYPE2:
1369                 n := n.(*ir.TypeAssertExpr)
1370                 n.X = o.expr(n.X, nil)
1371                 if !types.IsDirectIface(n.Type()) || base.Flag.Cfg.Instrumenting {
1372                         return o.copyExprClear(n)
1373                 }
1374                 return n
1375
1376         case ir.ORECV:
1377                 n := n.(*ir.UnaryExpr)
1378                 n.X = o.expr(n.X, nil)
1379                 return o.copyExprClear(n)
1380
1381         case ir.OEQ, ir.ONE, ir.OLT, ir.OLE, ir.OGT, ir.OGE:
1382                 n := n.(*ir.BinaryExpr)
1383                 n.X = o.expr(n.X, nil)
1384                 n.Y = o.expr(n.Y, nil)
1385
1386                 t := n.X.Type()
1387                 switch {
1388                 case t.IsString():
1389                         // Mark string(byteSlice) arguments to reuse byteSlice backing
1390                         // buffer during conversion. String comparison does not
1391                         // memorize the strings for later use, so it is safe.
1392                         if n.X.Op() == ir.OBYTES2STR {
1393                                 n.X.(*ir.ConvExpr).SetOp(ir.OBYTES2STRTMP)
1394                         }
1395                         if n.Y.Op() == ir.OBYTES2STR {
1396                                 n.Y.(*ir.ConvExpr).SetOp(ir.OBYTES2STRTMP)
1397                         }
1398
1399                 case t.IsStruct() || t.IsArray():
1400                         // for complex comparisons, we need both args to be
1401                         // addressable so we can pass them to the runtime.
1402                         n.X = o.addrTemp(n.X)
1403                         n.Y = o.addrTemp(n.Y)
1404                 }
1405                 return n
1406
1407         case ir.OMAPLIT:
1408                 // Order map by converting:
1409                 //   map[int]int{
1410                 //     a(): b(),
1411                 //     c(): d(),
1412                 //     e(): f(),
1413                 //   }
1414                 // to
1415                 //   m := map[int]int{}
1416                 //   m[a()] = b()
1417                 //   m[c()] = d()
1418                 //   m[e()] = f()
1419                 // Then order the result.
1420                 // Without this special case, order would otherwise compute all
1421                 // the keys and values before storing any of them to the map.
1422                 // See issue 26552.
1423                 n := n.(*ir.CompLitExpr)
1424                 entries := n.List
1425                 statics := entries[:0]
1426                 var dynamics []*ir.KeyExpr
1427                 for _, r := range entries {
1428                         r := r.(*ir.KeyExpr)
1429
1430                         if !isStaticCompositeLiteral(r.Key) || !isStaticCompositeLiteral(r.Value) {
1431                                 dynamics = append(dynamics, r)
1432                                 continue
1433                         }
1434
1435                         // Recursively ordering some static entries can change them to dynamic;
1436                         // e.g., OCONVIFACE nodes. See #31777.
1437                         r = o.expr(r, nil).(*ir.KeyExpr)
1438                         if !isStaticCompositeLiteral(r.Key) || !isStaticCompositeLiteral(r.Value) {
1439                                 dynamics = append(dynamics, r)
1440                                 continue
1441                         }
1442
1443                         statics = append(statics, r)
1444                 }
1445                 n.List = statics
1446
1447                 if len(dynamics) == 0 {
1448                         return n
1449                 }
1450
1451                 // Emit the creation of the map (with all its static entries).
1452                 m := o.newTemp(n.Type(), false)
1453                 as := ir.NewAssignStmt(base.Pos, m, n)
1454                 typecheck.Stmt(as)
1455                 o.stmt(as)
1456
1457                 // Emit eval+insert of dynamic entries, one at a time.
1458                 for _, r := range dynamics {
1459                         lhs := typecheck.AssignExpr(ir.NewIndexExpr(base.Pos, m, r.Key)).(*ir.IndexExpr)
1460                         base.AssertfAt(lhs.Op() == ir.OINDEXMAP, lhs.Pos(), "want OINDEXMAP, have %+v", lhs)
1461                         lhs.RType = n.RType
1462
1463                         as := ir.NewAssignStmt(base.Pos, lhs, r.Value)
1464                         typecheck.Stmt(as)
1465                         o.stmt(as)
1466                 }
1467
1468                 // Remember that we issued these assignments so we can include that count
1469                 // in the map alloc hint.
1470                 // We're assuming here that all the keys in the map literal are distinct.
1471                 // If any are equal, this will be an overcount. Probably not worth accounting
1472                 // for that, as equal keys in map literals are rare, and at worst we waste
1473                 // a bit of space.
1474                 n.Len += int64(len(dynamics))
1475
1476                 return m
1477         }
1478
1479         // No return - type-assertions above. Each case must return for itself.
1480 }
1481
1482 // as2func orders OAS2FUNC nodes. It creates temporaries to ensure left-to-right assignment.
1483 // The caller should order the right-hand side of the assignment before calling order.as2func.
1484 // It rewrites,
1485 //
1486 //      a, b, a = ...
1487 //
1488 // as
1489 //
1490 //      tmp1, tmp2, tmp3 = ...
1491 //      a, b, a = tmp1, tmp2, tmp3
1492 //
1493 // This is necessary to ensure left to right assignment order.
1494 func (o *orderState) as2func(n *ir.AssignListStmt) {
1495         results := n.Rhs[0].Type()
1496         as := ir.NewAssignListStmt(n.Pos(), ir.OAS2, nil, nil)
1497         for i, nl := range n.Lhs {
1498                 if !ir.IsBlank(nl) {
1499                         typ := results.Field(i).Type
1500                         tmp := o.newTemp(typ, typ.HasPointers())
1501                         n.Lhs[i] = tmp
1502                         as.Lhs = append(as.Lhs, nl)
1503                         as.Rhs = append(as.Rhs, tmp)
1504                 }
1505         }
1506
1507         o.out = append(o.out, n)
1508         o.stmt(typecheck.Stmt(as))
1509 }
1510
1511 // as2ok orders OAS2XXX with ok.
1512 // Just like as2func, this also adds temporaries to ensure left-to-right assignment.
1513 func (o *orderState) as2ok(n *ir.AssignListStmt) {
1514         as := ir.NewAssignListStmt(n.Pos(), ir.OAS2, nil, nil)
1515
1516         do := func(i int, typ *types.Type) {
1517                 if nl := n.Lhs[i]; !ir.IsBlank(nl) {
1518                         var tmp ir.Node = o.newTemp(typ, typ.HasPointers())
1519                         n.Lhs[i] = tmp
1520                         as.Lhs = append(as.Lhs, nl)
1521                         if i == 1 {
1522                                 // The "ok" result is an untyped boolean according to the Go
1523                                 // spec. We need to explicitly convert it to the LHS type in
1524                                 // case the latter is a defined boolean type (#8475).
1525                                 tmp = typecheck.Conv(tmp, nl.Type())
1526                         }
1527                         as.Rhs = append(as.Rhs, tmp)
1528                 }
1529         }
1530
1531         do(0, n.Rhs[0].Type())
1532         do(1, types.Types[types.TBOOL])
1533
1534         o.out = append(o.out, n)
1535         o.stmt(typecheck.Stmt(as))
1536 }
1537
1538 // isFuncPCIntrinsic returns whether n is a direct call of internal/abi.FuncPCABIxxx functions.
1539 func isFuncPCIntrinsic(n *ir.CallExpr) bool {
1540         if n.Op() != ir.OCALLFUNC || n.X.Op() != ir.ONAME {
1541                 return false
1542         }
1543         fn := n.X.(*ir.Name).Sym()
1544         return (fn.Name == "FuncPCABI0" || fn.Name == "FuncPCABIInternal") &&
1545                 (fn.Pkg.Path == "internal/abi" || fn.Pkg == types.LocalPkg && base.Ctxt.Pkgpath == "internal/abi")
1546 }
1547
1548 // isIfaceOfFunc returns whether n is an interface conversion from a direct reference of a func.
1549 func isIfaceOfFunc(n ir.Node) bool {
1550         return n.Op() == ir.OCONVIFACE && n.(*ir.ConvExpr).X.Op() == ir.ONAME && n.(*ir.ConvExpr).X.(*ir.Name).Class == ir.PFUNC
1551 }