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  	// Build pre-walk analysis caches with a single AST traversal.
    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  	analyzePreWalk(fn)
    30  	defer func() { staticValues = nil; shapeConvSources = 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 mapaccess1 = mkmapnames("mapaccess1", "")
   188  var mapaccess2 = mkmapnames("mapaccess2", "")
   189  var mapassign = mkmapnames("mapassign", "ptr")
   190  var mapdelete = mkmapnames("mapdelete", "")
   191  
   192  func mapfast(t *types.Type) int {
   193  	if t.Elem().Size() > abi.MapMaxElemBytes {
   194  		return mapslow
   195  	}
   196  	switch algType(t.Key()) {
   197  	case types.AMEM32:
   198  		if !t.Key().HasPointers() {
   199  			return mapfast32
   200  		}
   201  		if types.PtrSize == 4 {
   202  			return mapfast32ptr
   203  		}
   204  		base.Fatalf("small pointer %v", t.Key())
   205  	case types.AMEM64:
   206  		if !t.Key().HasPointers() {
   207  			return mapfast64
   208  		}
   209  		if types.PtrSize == 8 {
   210  			return mapfast64ptr
   211  		}
   212  		// Two-word object, at least one of which is a pointer.
   213  		// Use the slow path.
   214  	case types.ASTRING:
   215  		return mapfaststr
   216  	}
   217  	return mapslow
   218  }
   219  
   220  // algType returns the fixed-width AMEMxx variants instead of the general
   221  // AMEM kind when possible.
   222  func algType(t *types.Type) types.AlgKind {
   223  	a := types.AlgType(t)
   224  	if a == types.AMEM {
   225  		if t.Alignment() < int64(base.Ctxt.Arch.Alignment) && t.Alignment() < t.Size() {
   226  			// For example, we can't treat [2]int16 as an int32 if int32s require
   227  			// 4-byte alignment. See issue 46283.
   228  			return a
   229  		}
   230  		switch t.Size() {
   231  		case 0:
   232  			return types.AMEM0
   233  		case 1:
   234  			return types.AMEM8
   235  		case 2:
   236  			return types.AMEM16
   237  		case 4:
   238  			return types.AMEM32
   239  		case 8:
   240  			return types.AMEM64
   241  		case 16:
   242  			return types.AMEM128
   243  		}
   244  	}
   245  
   246  	return a
   247  }
   248  
   249  func walkAppendArgs(n *ir.CallExpr, init *ir.Nodes) {
   250  	walkExprListSafe(n.Args, init)
   251  
   252  	// walkExprListSafe will leave OINDEX (s[n]) alone if both s
   253  	// and n are name or literal, but those may index the slice we're
   254  	// modifying here. Fix explicitly.
   255  	ls := n.Args
   256  	for i1, n1 := range ls {
   257  		ls[i1] = cheapExpr(n1, init)
   258  	}
   259  }
   260  
   261  // appendWalkStmt typechecks and walks stmt and then appends it to init.
   262  func appendWalkStmt(init *ir.Nodes, stmt ir.Node) {
   263  	op := stmt.Op()
   264  	n := typecheck.Stmt(stmt)
   265  	if op == ir.OAS || op == ir.OAS2 {
   266  		// If the assignment has side effects, walkExpr will append them
   267  		// directly to init for us, while walkStmt will wrap it in an OBLOCK.
   268  		// We need to append them directly.
   269  		// TODO(rsc): Clean this up.
   270  		n = walkExpr(n, init)
   271  	} else {
   272  		n = walkStmt(n)
   273  	}
   274  	init.Append(n)
   275  }
   276  
   277  // The max number of defers in a function using open-coded defers. We enforce this
   278  // limit because the deferBits bitmask is currently a single byte (to minimize code size)
   279  const maxOpenDefers = 8
   280  
   281  // backingArrayPtrLen extracts the pointer and length from a slice or string.
   282  // This constructs two nodes referring to n, so n must be a cheapExpr.
   283  func backingArrayPtrLen(n ir.Node) (ptr, length ir.Node) {
   284  	var init ir.Nodes
   285  	c := cheapExpr(n, &init)
   286  	if c != n || len(init) != 0 {
   287  		base.Fatalf("backingArrayPtrLen not cheap: %v", n)
   288  	}
   289  	ptr = ir.NewUnaryExpr(base.Pos, ir.OSPTR, n)
   290  	if n.Type().IsString() {
   291  		ptr.SetType(types.Types[types.TUINT8].PtrTo())
   292  	} else {
   293  		ptr.SetType(n.Type().Elem().PtrTo())
   294  	}
   295  	ptr.SetTypecheck(1)
   296  	length = ir.NewUnaryExpr(base.Pos, ir.OLEN, n)
   297  	length.SetType(types.Types[types.TINT])
   298  	length.SetTypecheck(1)
   299  	return ptr, length
   300  }
   301  
   302  // mayCall reports whether evaluating expression n may require
   303  // function calls, which could clobber function call arguments/results
   304  // currently on the stack.
   305  func mayCall(n ir.Node) bool {
   306  	// This is intended to avoid putting constants
   307  	// into temporaries with the race detector (or other
   308  	// instrumentation) which interferes with simple
   309  	// "this is a constant" tests in ssagen.
   310  	// Also, it will generally lead to better code.
   311  	if n.Op() == ir.OLITERAL {
   312  		return false
   313  	}
   314  
   315  	// When instrumenting, any expression might require function calls.
   316  	if base.Flag.Cfg.Instrumenting {
   317  		return true
   318  	}
   319  
   320  	isSoftFloat := func(typ *types.Type) bool {
   321  		return types.IsFloat[typ.Kind()] || types.IsComplex[typ.Kind()]
   322  	}
   323  
   324  	return ir.Any(n, func(n ir.Node) bool {
   325  		// walk should have already moved any Init blocks off of
   326  		// expressions.
   327  		if len(n.Init()) != 0 {
   328  			base.FatalfAt(n.Pos(), "mayCall %+v", n)
   329  		}
   330  
   331  		switch n.Op() {
   332  		default:
   333  			base.FatalfAt(n.Pos(), "mayCall %+v", n)
   334  
   335  		case ir.OCALLFUNC, ir.OCALLINTER,
   336  			ir.OUNSAFEADD, ir.OUNSAFESLICE:
   337  			return true
   338  
   339  		case ir.OINDEX, ir.OSLICE, ir.OSLICEARR, ir.OSLICE3, ir.OSLICE3ARR, ir.OSLICESTR,
   340  			ir.ODEREF, ir.ODOTPTR, ir.ODOTTYPE, ir.ODYNAMICDOTTYPE, ir.ODIV, ir.OMOD,
   341  			ir.OSLICE2ARR, ir.OSLICE2ARRPTR:
   342  			// These ops might panic, make sure they are done
   343  			// before we start marshaling args for a call. See issue 16760.
   344  			return true
   345  
   346  		case ir.OANDAND, ir.OOROR:
   347  			n := n.(*ir.LogicalExpr)
   348  			// The RHS expression may have init statements that
   349  			// should only execute conditionally, and so cannot be
   350  			// pulled out to the top-level init list. We could try
   351  			// to be more precise here.
   352  			return len(n.Y.Init()) != 0
   353  
   354  		// When using soft-float, these ops might be rewritten to function calls
   355  		// so we ensure they are evaluated first.
   356  		case ir.OADD, ir.OSUB, ir.OMUL, ir.ONEG:
   357  			return ssagen.Arch.SoftFloat && isSoftFloat(n.Type())
   358  		case ir.OLT, ir.OEQ, ir.ONE, ir.OLE, ir.OGE, ir.OGT:
   359  			n := n.(*ir.BinaryExpr)
   360  			return ssagen.Arch.SoftFloat && isSoftFloat(n.X.Type())
   361  		case ir.OCONV:
   362  			n := n.(*ir.ConvExpr)
   363  			return ssagen.Arch.SoftFloat && (isSoftFloat(n.Type()) || isSoftFloat(n.X.Type()))
   364  
   365  		case ir.OMIN, ir.OMAX:
   366  			// string or float requires runtime call, see (*ssagen.state).minmax method.
   367  			return n.Type().IsString() || n.Type().IsFloat()
   368  
   369  		case ir.OLITERAL, ir.ONIL, ir.ONAME, ir.OLINKSYMOFFSET, ir.OMETHEXPR,
   370  			ir.OAND, ir.OANDNOT, ir.OLSH, ir.OOR, ir.ORSH, ir.OXOR, ir.OCOMPLEX, ir.OMAKEFACE,
   371  			ir.OADDR, ir.OBITNOT, ir.ONOT, ir.OPLUS,
   372  			ir.OCAP, ir.OIMAG, ir.OLEN, ir.OREAL,
   373  			ir.OCONVNOP, ir.ODOT,
   374  			ir.OCFUNC, ir.OIDATA, ir.OITAB, ir.OSPTR,
   375  			ir.OBYTES2STRTMP, ir.OGETG, ir.OGETCALLERSP, ir.OSLICEHEADER, ir.OSTRINGHEADER:
   376  			// ok: operations that don't require function calls.
   377  			// Expand as needed.
   378  		}
   379  
   380  		return false
   381  	})
   382  }
   383  
   384  // itabType loads the _type field from a runtime.itab struct.
   385  func itabType(itab ir.Node) ir.Node {
   386  	if itabTypeField == nil {
   387  		// internal/abi.ITab's Type field
   388  		itabTypeField = runtimeField("Type", rttype.ITab.OffsetOf("Type"), types.NewPtr(types.Types[types.TUINT8]))
   389  	}
   390  	return boundedDotPtr(base.Pos, itab, itabTypeField)
   391  }
   392  
   393  var itabTypeField *types.Field
   394  
   395  // boundedDotPtr returns a selector expression representing ptr.field
   396  // and omits nil-pointer checks for ptr.
   397  func boundedDotPtr(pos src.XPos, ptr ir.Node, field *types.Field) *ir.SelectorExpr {
   398  	sel := ir.NewSelectorExpr(pos, ir.ODOTPTR, ptr, field.Sym)
   399  	sel.Selection = field
   400  	sel.SetType(field.Type)
   401  	sel.SetTypecheck(1)
   402  	sel.SetBounded(true) // guaranteed not to fault
   403  	return sel
   404  }
   405  
   406  func runtimeField(name string, offset int64, typ *types.Type) *types.Field {
   407  	f := types.NewField(src.NoXPos, ir.Pkgs.Runtime.Lookup(name), typ)
   408  	f.Offset = offset
   409  	return f
   410  }
   411  
   412  // ifaceData loads the data field from an interface.
   413  // The concrete type must be known to have type t.
   414  // It follows the pointer if !IsDirectIface(t).
   415  func ifaceData(pos src.XPos, n ir.Node, t *types.Type) ir.Node {
   416  	if t.IsInterface() {
   417  		base.Fatalf("ifaceData interface: %v", t)
   418  	}
   419  	ptr := ir.NewUnaryExpr(pos, ir.OIDATA, n)
   420  	if types.IsDirectIface(t) {
   421  		ptr.SetType(t)
   422  		ptr.SetTypecheck(1)
   423  		return ptr
   424  	}
   425  	ptr.SetType(types.NewPtr(t))
   426  	ptr.SetTypecheck(1)
   427  	ind := ir.NewStarExpr(pos, ptr)
   428  	ind.SetType(t)
   429  	ind.SetTypecheck(1)
   430  	ind.SetBounded(true)
   431  	return ind
   432  }
   433  
   434  // staticValue returns the earliest expression it can find that always
   435  // evaluates to n, with similar semantics to [ir.StaticValue].
   436  //
   437  // It only returns results for the ir.CurFunc being processed in [Walk],
   438  // including its closures, and uses a cache to reduce duplicative work.
   439  // It can return n or nil if it does not find an earlier expression.
   440  //
   441  // The current use case is reducing OCONVIFACE allocations, and hence
   442  // staticValue is currently only useful when given an *ir.ConvExpr.X as n.
   443  func staticValue(n ir.Node) ir.Node {
   444  	if staticValues == nil {
   445  		base.Fatalf("staticValues is nil. staticValue called outside of walk.Walk?")
   446  	}
   447  	return staticValues[n]
   448  }
   449  
   450  // staticValues is a cache of static values for use by staticValue.
   451  var staticValues map[ir.Node]ir.Node
   452  
   453  // shapeConvSources maps an *ir.Name (a PAUTO interface variable) to
   454  // the shape type of the OCONVIFACE expression that is its single
   455  // static value, if any.
   456  var shapeConvSources map[*ir.Name]*types.Type
   457  
   458  // analyzePreWalk populates staticValues and shapeConvSources using a
   459  // single AST traversal. We can't use an ir.ReassignOracle or
   460  // ir.StaticValue in the middle of walk because they don't currently
   461  // handle transformed assignments (e.g., will complain about
   462  // 'RHS == nil'). So we build these maps before walk begins.
   463  func analyzePreWalk(fn *ir.Func) {
   464  	ro := &ir.ReassignOracle{}
   465  	ro.Init(fn)
   466  	sv := make(map[ir.Node]ir.Node)
   467  	scs := make(map[*ir.Name]*types.Type)
   468  	ir.Visit(fn, func(n ir.Node) {
   469  		switch n.Op() {
   470  		case ir.OCONVIFACE:
   471  			x := n.(*ir.ConvExpr).X
   472  			v := ro.StaticValue(x)
   473  			if v != nil && v != x {
   474  				sv[x] = v
   475  			}
   476  		case ir.ONAME:
   477  			name := n.(*ir.Name).Canonical()
   478  			if name.Class != ir.PAUTO || name.Type() == nil || !name.Type().IsInterface() {
   479  				return
   480  			}
   481  			val := ro.StaticValue(name)
   482  			if val == nil || val.Op() != ir.OCONVIFACE {
   483  				return
   484  			}
   485  			srcType := val.(*ir.ConvExpr).X.Type()
   486  			if srcType != nil && !srcType.IsInterface() && srcType.IsShape() {
   487  				scs[name] = srcType
   488  			}
   489  		}
   490  	})
   491  	staticValues = sv
   492  	shapeConvSources = scs
   493  }
   494
View as plain text