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