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  	"errors"
     9  	"fmt"
    10  
    11  	"cmd/compile/internal/base"
    12  	"cmd/compile/internal/ir"
    13  	"cmd/compile/internal/reflectdata"
    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  const zeroValSize = 1024 // must match value of runtime/map.go:maxZero
    23  
    24  func Walk(fn *ir.Func) {
    25  	ir.CurFunc = fn
    26  	errorsBefore := base.Errors()
    27  	order(fn)
    28  	if base.Errors() > errorsBefore {
    29  		return
    30  	}
    31  
    32  	if base.Flag.W != 0 {
    33  		s := fmt.Sprintf("\nbefore walk %v", ir.CurFunc.Sym())
    34  		ir.DumpList(s, ir.CurFunc.Body)
    35  	}
    36  
    37  	lno := base.Pos
    38  
    39  	base.Pos = lno
    40  	if base.Errors() > errorsBefore {
    41  		return
    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  	if base.Flag.Cfg.Instrumenting {
    50  		instrument(fn)
    51  	}
    52  
    53  	// Eagerly compute sizes of all variables for SSA.
    54  	for _, n := range fn.Dcl {
    55  		types.CalcSize(n.Type())
    56  	}
    57  }
    58  
    59  // walkRecv walks an ORECV node.
    60  func walkRecv(n *ir.UnaryExpr) ir.Node {
    61  	if n.Typecheck() == 0 {
    62  		base.Fatalf("missing typecheck: %+v", n)
    63  	}
    64  	init := ir.TakeInit(n)
    65  
    66  	n.X = walkExpr(n.X, &init)
    67  	call := walkExpr(mkcall1(chanfn("chanrecv1", 2, n.X.Type()), nil, &init, n.X, typecheck.NodNil()), &init)
    68  	return ir.InitExpr(init, call)
    69  }
    70  
    71  func convas(n *ir.AssignStmt, init *ir.Nodes) *ir.AssignStmt {
    72  	if n.Op() != ir.OAS {
    73  		base.Fatalf("convas: not OAS %v", n.Op())
    74  	}
    75  	n.SetTypecheck(1)
    76  
    77  	if n.X == nil || n.Y == nil {
    78  		return n
    79  	}
    80  
    81  	lt := n.X.Type()
    82  	rt := n.Y.Type()
    83  	if lt == nil || rt == nil {
    84  		return n
    85  	}
    86  
    87  	if ir.IsBlank(n.X) {
    88  		n.Y = typecheck.DefaultLit(n.Y, nil)
    89  		return n
    90  	}
    91  
    92  	if !types.Identical(lt, rt) {
    93  		n.Y = typecheck.AssignConv(n.Y, lt, "assignment")
    94  		n.Y = walkExpr(n.Y, init)
    95  	}
    96  	types.CalcSize(n.Y.Type())
    97  
    98  	return n
    99  }
   100  
   101  var stop = errors.New("stop")
   102  
   103  func vmkcall(fn ir.Node, t *types.Type, init *ir.Nodes, va []ir.Node) *ir.CallExpr {
   104  	if init == nil {
   105  		base.Fatalf("mkcall with nil init: %v", fn)
   106  	}
   107  	if fn.Type() == nil || fn.Type().Kind() != types.TFUNC {
   108  		base.Fatalf("mkcall %v %v", fn, fn.Type())
   109  	}
   110  
   111  	n := fn.Type().NumParams()
   112  	if n != len(va) {
   113  		base.Fatalf("vmkcall %v needs %v args got %v", fn, n, len(va))
   114  	}
   115  
   116  	call := typecheck.Call(base.Pos, fn, va, false).(*ir.CallExpr)
   117  	call.SetType(t)
   118  	return walkExpr(call, init).(*ir.CallExpr)
   119  }
   120  
   121  func mkcall(name string, t *types.Type, init *ir.Nodes, args ...ir.Node) *ir.CallExpr {
   122  	return vmkcall(typecheck.LookupRuntime(name), t, init, args)
   123  }
   124  
   125  func mkcallstmt(name string, args ...ir.Node) ir.Node {
   126  	return mkcallstmt1(typecheck.LookupRuntime(name), args...)
   127  }
   128  
   129  func mkcall1(fn ir.Node, t *types.Type, init *ir.Nodes, args ...ir.Node) *ir.CallExpr {
   130  	return vmkcall(fn, t, init, args)
   131  }
   132  
   133  func mkcallstmt1(fn ir.Node, args ...ir.Node) ir.Node {
   134  	var init ir.Nodes
   135  	n := vmkcall(fn, nil, &init, args)
   136  	if len(init) == 0 {
   137  		return n
   138  	}
   139  	init.Append(n)
   140  	return ir.NewBlockStmt(n.Pos(), init)
   141  }
   142  
   143  func chanfn(name string, n int, t *types.Type) ir.Node {
   144  	if !t.IsChan() {
   145  		base.Fatalf("chanfn %v", t)
   146  	}
   147  	fn := typecheck.LookupRuntime(name)
   148  	switch n {
   149  	default:
   150  		base.Fatalf("chanfn %d", n)
   151  	case 1:
   152  		fn = typecheck.SubstArgTypes(fn, t.Elem())
   153  	case 2:
   154  		fn = typecheck.SubstArgTypes(fn, t.Elem(), t.Elem())
   155  	}
   156  	return fn
   157  }
   158  
   159  func mapfn(name string, t *types.Type, isfat bool) ir.Node {
   160  	if !t.IsMap() {
   161  		base.Fatalf("mapfn %v", t)
   162  	}
   163  	fn := typecheck.LookupRuntime(name)
   164  	if mapfast(t) == mapslow || isfat {
   165  		fn = typecheck.SubstArgTypes(fn, t.Key(), t.Elem(), t.Key(), t.Elem())
   166  	} else {
   167  		fn = typecheck.SubstArgTypes(fn, t.Key(), t.Elem(), t.Elem())
   168  	}
   169  	return fn
   170  }
   171  
   172  func mapfndel(name string, t *types.Type) ir.Node {
   173  	if !t.IsMap() {
   174  		base.Fatalf("mapfn %v", t)
   175  	}
   176  	fn := typecheck.LookupRuntime(name)
   177  	if mapfast(t) == mapslow {
   178  		fn = typecheck.SubstArgTypes(fn, t.Key(), t.Elem(), t.Key())
   179  	} else {
   180  		fn = typecheck.SubstArgTypes(fn, t.Key(), t.Elem())
   181  	}
   182  	return fn
   183  }
   184  
   185  const (
   186  	mapslow = iota
   187  	mapfast32
   188  	mapfast32ptr
   189  	mapfast64
   190  	mapfast64ptr
   191  	mapfaststr
   192  	nmapfast
   193  )
   194  
   195  type mapnames [nmapfast]string
   196  
   197  func mkmapnames(base string, ptr string) mapnames {
   198  	return mapnames{base, base + "_fast32", base + "_fast32" + ptr, base + "_fast64", base + "_fast64" + ptr, base + "_faststr"}
   199  }
   200  
   201  var mapaccess1 = mkmapnames("mapaccess1", "")
   202  var mapaccess2 = mkmapnames("mapaccess2", "")
   203  var mapassign = mkmapnames("mapassign", "ptr")
   204  var mapdelete = mkmapnames("mapdelete", "")
   205  
   206  func mapfast(t *types.Type) int {
   207  	// Check runtime/map.go:maxElemSize before changing.
   208  	if t.Elem().Size() > 128 {
   209  		return mapslow
   210  	}
   211  	switch reflectdata.AlgType(t.Key()) {
   212  	case types.AMEM32:
   213  		if !t.Key().HasPointers() {
   214  			return mapfast32
   215  		}
   216  		if types.PtrSize == 4 {
   217  			return mapfast32ptr
   218  		}
   219  		base.Fatalf("small pointer %v", t.Key())
   220  	case types.AMEM64:
   221  		if !t.Key().HasPointers() {
   222  			return mapfast64
   223  		}
   224  		if types.PtrSize == 8 {
   225  			return mapfast64ptr
   226  		}
   227  		// Two-word object, at least one of which is a pointer.
   228  		// Use the slow path.
   229  	case types.ASTRING:
   230  		return mapfaststr
   231  	}
   232  	return mapslow
   233  }
   234  
   235  func walkAppendArgs(n *ir.CallExpr, init *ir.Nodes) {
   236  	walkExprListSafe(n.Args, init)
   237  
   238  	// walkExprListSafe will leave OINDEX (s[n]) alone if both s
   239  	// and n are name or literal, but those may index the slice we're
   240  	// modifying here. Fix explicitly.
   241  	ls := n.Args
   242  	for i1, n1 := range ls {
   243  		ls[i1] = cheapExpr(n1, init)
   244  	}
   245  }
   246  
   247  // appendWalkStmt typechecks and walks stmt and then appends it to init.
   248  func appendWalkStmt(init *ir.Nodes, stmt ir.Node) {
   249  	op := stmt.Op()
   250  	n := typecheck.Stmt(stmt)
   251  	if op == ir.OAS || op == ir.OAS2 {
   252  		// If the assignment has side effects, walkExpr will append them
   253  		// directly to init for us, while walkStmt will wrap it in an OBLOCK.
   254  		// We need to append them directly.
   255  		// TODO(rsc): Clean this up.
   256  		n = walkExpr(n, init)
   257  	} else {
   258  		n = walkStmt(n)
   259  	}
   260  	init.Append(n)
   261  }
   262  
   263  // The max number of defers in a function using open-coded defers. We enforce this
   264  // limit because the deferBits bitmask is currently a single byte (to minimize code size)
   265  const maxOpenDefers = 8
   266  
   267  // backingArrayPtrLen extracts the pointer and length from a slice or string.
   268  // This constructs two nodes referring to n, so n must be a cheapExpr.
   269  func backingArrayPtrLen(n ir.Node) (ptr, length ir.Node) {
   270  	var init ir.Nodes
   271  	c := cheapExpr(n, &init)
   272  	if c != n || len(init) != 0 {
   273  		base.Fatalf("backingArrayPtrLen not cheap: %v", n)
   274  	}
   275  	ptr = ir.NewUnaryExpr(base.Pos, ir.OSPTR, n)
   276  	if n.Type().IsString() {
   277  		ptr.SetType(types.Types[types.TUINT8].PtrTo())
   278  	} else {
   279  		ptr.SetType(n.Type().Elem().PtrTo())
   280  	}
   281  	length = ir.NewUnaryExpr(base.Pos, ir.OLEN, n)
   282  	length.SetType(types.Types[types.TINT])
   283  	return ptr, length
   284  }
   285  
   286  // mayCall reports whether evaluating expression n may require
   287  // function calls, which could clobber function call arguments/results
   288  // currently on the stack.
   289  func mayCall(n ir.Node) bool {
   290  	// When instrumenting, any expression might require function calls.
   291  	if base.Flag.Cfg.Instrumenting {
   292  		return true
   293  	}
   294  
   295  	isSoftFloat := func(typ *types.Type) bool {
   296  		return types.IsFloat[typ.Kind()] || types.IsComplex[typ.Kind()]
   297  	}
   298  
   299  	return ir.Any(n, func(n ir.Node) bool {
   300  		// walk should have already moved any Init blocks off of
   301  		// expressions.
   302  		if len(n.Init()) != 0 {
   303  			base.FatalfAt(n.Pos(), "mayCall %+v", n)
   304  		}
   305  
   306  		switch n.Op() {
   307  		default:
   308  			base.FatalfAt(n.Pos(), "mayCall %+v", n)
   309  
   310  		case ir.OCALLFUNC, ir.OCALLINTER,
   311  			ir.OUNSAFEADD, ir.OUNSAFESLICE:
   312  			return true
   313  
   314  		case ir.OINDEX, ir.OSLICE, ir.OSLICEARR, ir.OSLICE3, ir.OSLICE3ARR, ir.OSLICESTR,
   315  			ir.ODEREF, ir.ODOTPTR, ir.ODOTTYPE, ir.ODYNAMICDOTTYPE, ir.ODIV, ir.OMOD, ir.OSLICE2ARRPTR:
   316  			// These ops might panic, make sure they are done
   317  			// before we start marshaling args for a call. See issue 16760.
   318  			return true
   319  
   320  		case ir.OANDAND, ir.OOROR:
   321  			n := n.(*ir.LogicalExpr)
   322  			// The RHS expression may have init statements that
   323  			// should only execute conditionally, and so cannot be
   324  			// pulled out to the top-level init list. We could try
   325  			// to be more precise here.
   326  			return len(n.Y.Init()) != 0
   327  
   328  		// When using soft-float, these ops might be rewritten to function calls
   329  		// so we ensure they are evaluated first.
   330  		case ir.OADD, ir.OSUB, ir.OMUL, ir.ONEG:
   331  			return ssagen.Arch.SoftFloat && isSoftFloat(n.Type())
   332  		case ir.OLT, ir.OEQ, ir.ONE, ir.OLE, ir.OGE, ir.OGT:
   333  			n := n.(*ir.BinaryExpr)
   334  			return ssagen.Arch.SoftFloat && isSoftFloat(n.X.Type())
   335  		case ir.OCONV:
   336  			n := n.(*ir.ConvExpr)
   337  			return ssagen.Arch.SoftFloat && (isSoftFloat(n.Type()) || isSoftFloat(n.X.Type()))
   338  
   339  		case ir.OLITERAL, ir.ONIL, ir.ONAME, ir.OLINKSYMOFFSET, ir.OMETHEXPR,
   340  			ir.OAND, ir.OANDNOT, ir.OLSH, ir.OOR, ir.ORSH, ir.OXOR, ir.OCOMPLEX, ir.OEFACE,
   341  			ir.OADDR, ir.OBITNOT, ir.ONOT, ir.OPLUS,
   342  			ir.OCAP, ir.OIMAG, ir.OLEN, ir.OREAL,
   343  			ir.OCONVNOP, ir.ODOT,
   344  			ir.OCFUNC, ir.OIDATA, ir.OITAB, ir.OSPTR,
   345  			ir.OBYTES2STRTMP, ir.OGETG, ir.OGETCALLERPC, ir.OGETCALLERSP, ir.OSLICEHEADER:
   346  			// ok: operations that don't require function calls.
   347  			// Expand as needed.
   348  		}
   349  
   350  		return false
   351  	})
   352  }
   353  
   354  // itabType loads the _type field from a runtime.itab struct.
   355  func itabType(itab ir.Node) ir.Node {
   356  	if itabTypeField == nil {
   357  		// runtime.itab's _type field
   358  		itabTypeField = runtimeField("_type", int64(types.PtrSize), types.NewPtr(types.Types[types.TUINT8]))
   359  	}
   360  	return boundedDotPtr(base.Pos, itab, itabTypeField)
   361  }
   362  
   363  var itabTypeField *types.Field
   364  
   365  // boundedDotPtr returns a selector expression representing ptr.field
   366  // and omits nil-pointer checks for ptr.
   367  func boundedDotPtr(pos src.XPos, ptr ir.Node, field *types.Field) *ir.SelectorExpr {
   368  	sel := ir.NewSelectorExpr(pos, ir.ODOTPTR, ptr, field.Sym)
   369  	sel.Selection = field
   370  	sel.SetType(field.Type)
   371  	sel.SetTypecheck(1)
   372  	sel.SetBounded(true) // guaranteed not to fault
   373  	return sel
   374  }
   375  
   376  func runtimeField(name string, offset int64, typ *types.Type) *types.Field {
   377  	f := types.NewField(src.NoXPos, ir.Pkgs.Runtime.Lookup(name), typ)
   378  	f.Offset = offset
   379  	return f
   380  }
   381  
   382  // ifaceData loads the data field from an interface.
   383  // The concrete type must be known to have type t.
   384  // It follows the pointer if !IsDirectIface(t).
   385  func ifaceData(pos src.XPos, n ir.Node, t *types.Type) ir.Node {
   386  	if t.IsInterface() {
   387  		base.Fatalf("ifaceData interface: %v", t)
   388  	}
   389  	ptr := ir.NewUnaryExpr(pos, ir.OIDATA, n)
   390  	if types.IsDirectIface(t) {
   391  		ptr.SetType(t)
   392  		ptr.SetTypecheck(1)
   393  		return ptr
   394  	}
   395  	ptr.SetType(types.NewPtr(t))
   396  	ptr.SetTypecheck(1)
   397  	ind := ir.NewStarExpr(pos, ptr)
   398  	ind.SetType(t)
   399  	ind.SetTypecheck(1)
   400  	ind.SetBounded(true)
   401  	return ind
   402  }
   403
View as plain text