walk.go

     1  // Copyright 2009 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  	"internal/abi"
    10  
    11  	"cmd/compile/internal/base"
    12  	"cmd/compile/internal/ir"
    13  	"cmd/compile/internal/rttype"
    14  	"cmd/compile/internal/ssagen"
    15  	"cmd/compile/internal/typecheck"
    16  	"cmd/compile/internal/types"
    17  	"cmd/internal/src"
    18  )
    19  
    20  // The constant is known to runtime.
    21  const tmpstringbufsize = 32
    22  
    23  func Walk(fn *ir.Func) {
    24  	ir.CurFunc = fn
    25  
    26  	// Set and then clear a package-level cache of static values for this fn.
    27  	// (At some point, it might be worthwhile to have a walkState structure
    28  	// that gets passed everywhere where things like this can go.)
    29  	staticValues = findStaticValues(fn)
    30  	defer func() { staticValues = nil }()
    31  
    32  	errorsBefore := base.Errors()
    33  	order(fn)
    34  	if base.Errors() > errorsBefore {
    35  		return
    36  	}
    37  
    38  	if base.Flag.W != 0 {
    39  		s := fmt.Sprintf("\nbefore walk %v", ir.CurFunc.Sym())
    40  		ir.DumpList(s, ir.CurFunc.Body)
    41  	}
    42  
    43  	walkStmtList(ir.CurFunc.Body)
    44  	if base.Flag.W != 0 {
    45  		s := fmt.Sprintf("after walk %v", ir.CurFunc.Sym())
    46  		ir.DumpList(s, ir.CurFunc.Body)
    47  	}
    48  
    49  	// Eagerly compute sizes of all variables for SSA.
    50  	for _, n := range fn.Dcl {
    51  		types.CalcSize(n.Type())
    52  	}
    53  }
    54  
    55  // walkRecv walks an ORECV node.
    56  func walkRecv(n *ir.UnaryExpr) ir.Node {
    57  	if n.Typecheck() == 0 {
    58  		base.Fatalf("missing typecheck: %+v", n)
    59  	}
    60  	init := ir.TakeInit(n)
    61  
    62  	n.X = walkExpr(n.X, &init)
    63  	call := walkExpr(mkcall1(chanfn("chanrecv1", 2, n.X.Type()), nil, &init, n.X, typecheck.NodNil()), &init)
    64  	return ir.InitExpr(init, call)
    65  }
    66  
    67  func convas(n *ir.AssignStmt, init *ir.Nodes) *ir.AssignStmt {
    68  	if n.Op() != ir.OAS {
    69  		base.Fatalf("convas: not OAS %v", n.Op())
    70  	}
    71  	n.SetTypecheck(1)
    72  
    73  	if n.X == nil || n.Y == nil {
    74  		return n
    75  	}
    76  
    77  	lt := n.X.Type()
    78  	rt := n.Y.Type()
    79  	if lt == nil || rt == nil {
    80  		return n
    81  	}
    82  
    83  	if ir.IsBlank(n.X) {
    84  		n.Y = typecheck.DefaultLit(n.Y, nil)
    85  		return n
    86  	}
    87  
    88  	if !types.Identical(lt, rt) {
    89  		n.Y = typecheck.AssignConv(n.Y, lt, "assignment")
    90  		n.Y = walkExpr(n.Y, init)
    91  	}
    92  	types.CalcSize(n.Y.Type())
    93  
    94  	return n
    95  }
    96  
    97  func vmkcall(fn ir.Node, t *types.Type, init *ir.Nodes, va []ir.Node) *ir.CallExpr {
    98  	if init == nil {
    99  		base.Fatalf("mkcall with nil init: %v", fn)
   100  	}
   101  	if fn.Type() == nil || fn.Type().Kind() != types.TFUNC {
   102  		base.Fatalf("mkcall %v %v", fn, fn.Type())
   103  	}
   104  
   105  	n := fn.Type().NumParams()
   106  	if n != len(va) {
   107  		base.Fatalf("vmkcall %v needs %v args got %v", fn, n, len(va))
   108  	}
   109  
   110  	call := typecheck.Call(base.Pos, fn, va, false).(*ir.CallExpr)
   111  	call.SetType(t)
   112  	return walkExpr(call, init).(*ir.CallExpr)
   113  }
   114  
   115  func mkcall(name string, t *types.Type, init *ir.Nodes, args ...ir.Node) *ir.CallExpr {
   116  	return vmkcall(typecheck.LookupRuntime(name), t, init, args)
   117  }
   118  
   119  func mkcallstmt(name string, args ...ir.Node) ir.Node {
   120  	return mkcallstmt1(typecheck.LookupRuntime(name), args...)
   121  }
   122  
   123  func mkcall1(fn ir.Node, t *types.Type, init *ir.Nodes, args ...ir.Node) *ir.CallExpr {
   124  	return vmkcall(fn, t, init, args)
   125  }
   126  
   127  func mkcallstmt1(fn ir.Node, args ...ir.Node) ir.Node {
   128  	var init ir.Nodes
   129  	n := vmkcall(fn, nil, &init, args)
   130  	if len(init) == 0 {
   131  		return n
   132  	}
   133  	init.Append(n)
   134  	return ir.NewBlockStmt(n.Pos(), init)
   135  }
   136  
   137  func chanfn(name string, n int, t *types.Type) ir.Node {
   138  	if !t.IsChan() {
   139  		base.Fatalf("chanfn %v", t)
   140  	}
   141  	switch n {
   142  	case 1:
   143  		return typecheck.LookupRuntime(name, t.Elem())
   144  	case 2:
   145  		return typecheck.LookupRuntime(name, t.Elem(), t.Elem())
   146  	}
   147  	base.Fatalf("chanfn %d", n)
   148  	return nil
   149  }
   150  
   151  func mapfn(name string, t *types.Type, isfat bool) ir.Node {
   152  	if !t.IsMap() {
   153  		base.Fatalf("mapfn %v", t)
   154  	}
   155  	if mapfast(t) == mapslow || isfat {
   156  		return typecheck.LookupRuntime(name, t.Key(), t.Elem(), t.Key(), t.Elem())
   157  	}
   158  	return typecheck.LookupRuntime(name, t.Key(), t.Elem(), t.Elem())
   159  }
   160  
   161  func mapfndel(name string, t *types.Type) ir.Node {
   162  	if !t.IsMap() {
   163  		base.Fatalf("mapfn %v", t)
   164  	}
   165  	if mapfast(t) == mapslow {
   166  		return typecheck.LookupRuntime(name, t.Key(), t.Elem(), t.Key())
   167  	}
   168  	return typecheck.LookupRuntime(name, t.Key(), t.Elem())
   169  }
   170  
   171  const (
   172  	mapslow = iota
   173  	mapfast32
   174  	mapfast32ptr
   175  	mapfast64
   176  	mapfast64ptr
   177  	mapfaststr
   178  	nmapfast
   179  )
   180  
   181  type mapnames [nmapfast]string
   182  
   183  func mkmapnames(base string, ptr string) mapnames {
   184  	return mapnames{base, base + "_fast32", base + "_fast32" + ptr, base + "_fast64", base + "_fast64" + ptr, base + "_faststr"}
   185  }
   186  
   187  var mapaccess = mkmapnames("mapaccess2", "")
   188  var mapassign = mkmapnames("mapassign", "ptr")
   189  var mapdelete = mkmapnames("mapdelete", "")
   190  
   191  func mapfast(t *types.Type) int {
   192  	if t.Elem().Size() > abi.MapMaxElemBytes {
   193  		return mapslow
   194  	}
   195  	switch algType(t.Key()) {
   196  	case types.AMEM32:
   197  		if !t.Key().HasPointers() {
   198  			return mapfast32
   199  		}
   200  		if types.PtrSize == 4 {
   201  			return mapfast32ptr
   202  		}
   203  		base.Fatalf("small pointer %v", t.Key())
   204  	case types.AMEM64:
   205  		if !t.Key().HasPointers() {
   206  			return mapfast64
   207  		}
   208  		if types.PtrSize == 8 {
   209  			return mapfast64ptr
   210  		}
   211  		// Two-word object, at least one of which is a pointer.
   212  		// Use the slow path.
   213  	case types.ASTRING:
   214  		return mapfaststr
   215  	}
   216  	return mapslow
   217  }
   218  
   219  // algType returns the fixed-width AMEMxx variants instead of the general
   220  // AMEM kind when possible.
   221  func algType(t *types.Type) types.AlgKind {
   222  	a := types.AlgType(t)
   223  	if a == types.AMEM {
   224  		if t.Alignment() < int64(base.Ctxt.Arch.Alignment) && t.Alignment() < t.Size() {
   225  			// For example, we can't treat [2]int16 as an int32 if int32s require
   226  			// 4-byte alignment. See issue 46283.
   227  			return a
   228  		}
   229  		switch t.Size() {
   230  		case 0:
   231  			return types.AMEM0
   232  		case 1:
   233  			return types.AMEM8
   234  		case 2:
   235  			return types.AMEM16
   236  		case 4:
   237  			return types.AMEM32
   238  		case 8:
   239  			return types.AMEM64
   240  		case 16:
   241  			return types.AMEM128
   242  		}
   243  	}
   244  
   245  	return a
   246  }
   247  
   248  func walkAppendArgs(n *ir.CallExpr, init *ir.Nodes) {
   249  	walkExprListSafe(n.Args, init)
   250  
   251  	// walkExprListSafe will leave OINDEX (s[n]) alone if both s
   252  	// and n are name or literal, but those may index the slice we're
   253  	// modifying here. Fix explicitly.
   254  	ls := n.Args
   255  	for i1, n1 := range ls {
   256  		ls[i1] = cheapExpr(n1, init)
   257  	}
   258  }
   259  
   260  // appendWalkStmt typechecks and walks stmt and then appends it to init.
   261  func appendWalkStmt(init *ir.Nodes, stmt ir.Node) {
   262  	op := stmt.Op()
   263  	n := typecheck.Stmt(stmt)
   264  	if op == ir.OAS || op == ir.OAS2 {
   265  		// If the assignment has side effects, walkExpr will append them
   266  		// directly to init for us, while walkStmt will wrap it in an OBLOCK.
   267  		// We need to append them directly.
   268  		// TODO(rsc): Clean this up.
   269  		n = walkExpr(n, init)
   270  	} else {
   271  		n = walkStmt(n)
   272  	}
   273  	init.Append(n)
   274  }
   275  
   276  // The max number of defers in a function using open-coded defers. We enforce this
   277  // limit because the deferBits bitmask is currently a single byte (to minimize code size)
   278  const maxOpenDefers = 8
   279  
   280  // backingArrayPtrLen extracts the pointer and length from a slice or string.
   281  // This constructs two nodes referring to n, so n must be a cheapExpr.
   282  func backingArrayPtrLen(n ir.Node) (ptr, length ir.Node) {
   283  	var init ir.Nodes
   284  	c := cheapExpr(n, &init)
   285  	if c != n || len(init) != 0 {
   286  		base.Fatalf("backingArrayPtrLen not cheap: %v", n)
   287  	}
   288  	ptr = ir.NewUnaryExpr(base.Pos, ir.OSPTR, n)
   289  	if n.Type().IsString() {
   290  		ptr.SetType(types.Types[types.TUINT8].PtrTo())
   291  	} else {
   292  		ptr.SetType(n.Type().Elem().PtrTo())
   293  	}
   294  	ptr.SetTypecheck(1)
   295  	length = ir.NewUnaryExpr(base.Pos, ir.OLEN, n)
   296  	length.SetType(types.Types[types.TINT])
   297  	length.SetTypecheck(1)
   298  	return ptr, length
   299  }
   300  
   301  // mayCall reports whether evaluating expression n may require
   302  // function calls, which could clobber function call arguments/results
   303  // currently on the stack.
   304  func mayCall(n ir.Node) bool {
   305  	// This is intended to avoid putting constants
   306  	// into temporaries with the race detector (or other
   307  	// instrumentation) which interferes with simple
   308  	// "this is a constant" tests in ssagen.
   309  	// Also, it will generally lead to better code.
   310  	if n.Op() == ir.OLITERAL {
   311  		return false
   312  	}
   313  
   314  	// When instrumenting, any expression might require function calls.
   315  	if base.Flag.Cfg.Instrumenting {
   316  		return true
   317  	}
   318  
   319  	isSoftFloat := func(typ *types.Type) bool {
   320  		return types.IsFloat[typ.Kind()] || types.IsComplex[typ.Kind()]
   321  	}
   322  
   323  	return ir.Any(n, func(n ir.Node) bool {
   324  		// walk should have already moved any Init blocks off of
   325  		// expressions.
   326  		if len(n.Init()) != 0 {
   327  			base.FatalfAt(n.Pos(), "mayCall %+v", n)
   328  		}
   329  
   330  		switch n.Op() {
   331  		default:
   332  			base.FatalfAt(n.Pos(), "mayCall %+v", n)
   333  
   334  		case ir.OCALLFUNC, ir.OCALLINTER,
   335  			ir.OUNSAFEADD, ir.OUNSAFESLICE:
   336  			return true
   337  
   338  		case ir.OINDEX, ir.OSLICE, ir.OSLICEARR, ir.OSLICE3, ir.OSLICE3ARR, ir.OSLICESTR,
   339  			ir.ODEREF, ir.ODOTPTR, ir.ODOTTYPE, ir.ODYNAMICDOTTYPE, ir.ODIV, ir.OMOD,
   340  			ir.OSLICE2ARR, ir.OSLICE2ARRPTR:
   341  			// These ops might panic, make sure they are done
   342  			// before we start marshaling args for a call. See issue 16760.
   343  			return true
   344  
   345  		case ir.OANDAND, ir.OOROR:
   346  			n := n.(*ir.LogicalExpr)
   347  			// The RHS expression may have init statements that
   348  			// should only execute conditionally, and so cannot be
   349  			// pulled out to the top-level init list. We could try
   350  			// to be more precise here.
   351  			return len(n.Y.Init()) != 0
   352  
   353  		// When using soft-float, these ops might be rewritten to function calls
   354  		// so we ensure they are evaluated first.
   355  		case ir.OADD, ir.OSUB, ir.OMUL, ir.ONEG:
   356  			return ssagen.Arch.SoftFloat && isSoftFloat(n.Type())
   357  		case ir.OLT, ir.OEQ, ir.ONE, ir.OLE, ir.OGE, ir.OGT:
   358  			n := n.(*ir.BinaryExpr)
   359  			return ssagen.Arch.SoftFloat && isSoftFloat(n.X.Type())
   360  		case ir.OCONV:
   361  			n := n.(*ir.ConvExpr)
   362  			return ssagen.Arch.SoftFloat && (isSoftFloat(n.Type()) || isSoftFloat(n.X.Type()))
   363  
   364  		case ir.OMIN, ir.OMAX:
   365  			// string or float requires runtime call, see (*ssagen.state).minmax method.
   366  			return n.Type().IsString() || n.Type().IsFloat()
   367  
   368  		case ir.OLITERAL, ir.ONIL, ir.ONAME, ir.OLINKSYMOFFSET, ir.OMETHEXPR,
   369  			ir.OAND, ir.OANDNOT, ir.OLSH, ir.OOR, ir.ORSH, ir.OXOR, ir.OCOMPLEX, ir.OMAKEFACE,
   370  			ir.OADDR, ir.OBITNOT, ir.ONOT, ir.OPLUS,
   371  			ir.OCAP, ir.OIMAG, ir.OLEN, ir.OREAL,
   372  			ir.OCONVNOP, ir.ODOT,
   373  			ir.OCFUNC, ir.OIDATA, ir.OITAB, ir.OSPTR,
   374  			ir.OBYTES2STRTMP, ir.OGETG, ir.OGETCALLERSP, ir.OSLICEHEADER, ir.OSTRINGHEADER:
   375  			// ok: operations that don't require function calls.
   376  			// Expand as needed.
   377  		}
   378  
   379  		return false
   380  	})
   381  }
   382  
   383  // itabType loads the _type field from a runtime.itab struct.
   384  func itabType(itab ir.Node) ir.Node {
   385  	if itabTypeField == nil {
   386  		// internal/abi.ITab's Type field
   387  		itabTypeField = runtimeField("Type", rttype.ITab.OffsetOf("Type"), types.NewPtr(types.Types[types.TUINT8]))
   388  	}
   389  	return boundedDotPtr(base.Pos, itab, itabTypeField)
   390  }
   391  
   392  var itabTypeField *types.Field
   393  
   394  // boundedDotPtr returns a selector expression representing ptr.field
   395  // and omits nil-pointer checks for ptr.
   396  func boundedDotPtr(pos src.XPos, ptr ir.Node, field *types.Field) *ir.SelectorExpr {
   397  	sel := ir.NewSelectorExpr(pos, ir.ODOTPTR, ptr, field.Sym)
   398  	sel.Selection = field
   399  	sel.SetType(field.Type)
   400  	sel.SetTypecheck(1)
   401  	sel.SetBounded(true) // guaranteed not to fault
   402  	return sel
   403  }
   404  
   405  func runtimeField(name string, offset int64, typ *types.Type) *types.Field {
   406  	f := types.NewField(src.NoXPos, ir.Pkgs.Runtime.Lookup(name), typ)
   407  	f.Offset = offset
   408  	return f
   409  }
   410  
   411  // ifaceData loads the data field from an interface.
   412  // The concrete type must be known to have type t.
   413  // It follows the pointer if !IsDirectIface(t).
   414  func ifaceData(pos src.XPos, n ir.Node, t *types.Type) ir.Node {
   415  	if t.IsInterface() {
   416  		base.Fatalf("ifaceData interface: %v", t)
   417  	}
   418  	ptr := ir.NewUnaryExpr(pos, ir.OIDATA, n)
   419  	if types.IsDirectIface(t) {
   420  		ptr.SetType(t)
   421  		ptr.SetTypecheck(1)
   422  		return ptr
   423  	}
   424  	ptr.SetType(types.NewPtr(t))
   425  	ptr.SetTypecheck(1)
   426  	ind := ir.NewStarExpr(pos, ptr)
   427  	ind.SetType(t)
   428  	ind.SetTypecheck(1)
   429  	ind.SetBounded(true)
   430  	return ind
   431  }
   432  
   433  // staticValue returns the earliest expression it can find that always
   434  // evaluates to n, with similar semantics to [ir.StaticValue].
   435  //
   436  // It only returns results for the ir.CurFunc being processed in [Walk],
   437  // including its closures, and uses a cache to reduce duplicative work.
   438  // It can return n or nil if it does not find an earlier expression.
   439  //
   440  // The current use case is reducing OCONVIFACE allocations, and hence
   441  // staticValue is currently only useful when given an *ir.ConvExpr.X as n.
   442  func staticValue(n ir.Node) ir.Node {
   443  	if staticValues == nil {
   444  		base.Fatalf("staticValues is nil. staticValue called outside of walk.Walk?")
   445  	}
   446  	return staticValues[n]
   447  }
   448  
   449  // staticValues is a cache of static values for use by staticValue.
   450  var staticValues map[ir.Node]ir.Node
   451  
   452  // findStaticValues returns a map of static values for fn.
   453  func findStaticValues(fn *ir.Func) map[ir.Node]ir.Node {
   454  	// We can't use an ir.ReassignOracle or ir.StaticValue in the
   455  	// middle of walk because they don't currently handle
   456  	// transformed assignments (e.g., will complain about 'RHS == nil').
   457  	// So we instead build this map to use in walk.
   458  	ro := &ir.ReassignOracle{}
   459  	ro.Init(fn)
   460  	m := make(map[ir.Node]ir.Node)
   461  	ir.Visit(fn, func(n ir.Node) {
   462  		if n.Op() == ir.OCONVIFACE {
   463  			x := n.(*ir.ConvExpr).X
   464  			v := ro.StaticValue(x)
   465  			if v != nil && v != x {
   466  				m[x] = v
   467  			}
   468  		}
   469  	})
   470  	return m
   471  }
   472
View as plain text