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

View as plain text