Source file src/cmd/compile/internal/staticinit/sched.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 staticinit
     6  
     7  import (
     8  	"fmt"
     9  	"go/constant"
    10  
    11  	"cmd/compile/internal/base"
    12  	"cmd/compile/internal/ir"
    13  	"cmd/compile/internal/reflectdata"
    14  	"cmd/compile/internal/staticdata"
    15  	"cmd/compile/internal/typecheck"
    16  	"cmd/compile/internal/types"
    17  	"cmd/internal/obj"
    18  	"cmd/internal/src"
    19  )
    20  
    21  type Entry struct {
    22  	Xoffset int64   // struct, array only
    23  	Expr    ir.Node // bytes of run-time computed expressions
    24  }
    25  
    26  type Plan struct {
    27  	E []Entry
    28  }
    29  
    30  // An Schedule is used to decompose assignment statements into
    31  // static and dynamic initialization parts. Static initializations are
    32  // handled by populating variables' linker symbol data, while dynamic
    33  // initializations are accumulated to be executed in order.
    34  type Schedule struct {
    35  	// Out is the ordered list of dynamic initialization
    36  	// statements.
    37  	Out []ir.Node
    38  
    39  	Plans map[ir.Node]*Plan
    40  	Temps map[ir.Node]*ir.Name
    41  }
    42  
    43  func (s *Schedule) append(n ir.Node) {
    44  	s.Out = append(s.Out, n)
    45  }
    46  
    47  // StaticInit adds an initialization statement n to the schedule.
    48  func (s *Schedule) StaticInit(n ir.Node) {
    49  	if !s.tryStaticInit(n) {
    50  		if base.Flag.Percent != 0 {
    51  			ir.Dump("nonstatic", n)
    52  		}
    53  		s.append(n)
    54  	}
    55  }
    56  
    57  // tryStaticInit attempts to statically execute an initialization
    58  // statement and reports whether it succeeded.
    59  func (s *Schedule) tryStaticInit(nn ir.Node) bool {
    60  	// Only worry about simple "l = r" assignments. Multiple
    61  	// variable/expression OAS2 assignments have already been
    62  	// replaced by multiple simple OAS assignments, and the other
    63  	// OAS2* assignments mostly necessitate dynamic execution
    64  	// anyway.
    65  	if nn.Op() != ir.OAS {
    66  		return false
    67  	}
    68  	n := nn.(*ir.AssignStmt)
    69  	if ir.IsBlank(n.X) && !AnySideEffects(n.Y) {
    70  		// Discard.
    71  		return true
    72  	}
    73  	lno := ir.SetPos(n)
    74  	defer func() { base.Pos = lno }()
    75  	nam := n.X.(*ir.Name)
    76  	return s.StaticAssign(nam, 0, n.Y, nam.Type())
    77  }
    78  
    79  // like staticassign but we are copying an already
    80  // initialized value r.
    81  func (s *Schedule) staticcopy(l *ir.Name, loff int64, rn *ir.Name, typ *types.Type) bool {
    82  	if rn.Class == ir.PFUNC {
    83  		// TODO if roff != 0 { panic }
    84  		staticdata.InitAddr(l, loff, staticdata.FuncLinksym(rn))
    85  		return true
    86  	}
    87  	if rn.Class != ir.PEXTERN || rn.Sym().Pkg != types.LocalPkg {
    88  		return false
    89  	}
    90  	if rn.Defn.Op() != ir.OAS {
    91  		return false
    92  	}
    93  	if rn.Type().IsString() { // perhaps overwritten by cmd/link -X (#34675)
    94  		return false
    95  	}
    96  	if rn.Embed != nil {
    97  		return false
    98  	}
    99  	orig := rn
   100  	r := rn.Defn.(*ir.AssignStmt).Y
   101  	if r == nil {
   102  		// No explicit initialization value. Probably zeroed but perhaps
   103  		// supplied externally and of unknown value.
   104  		return false
   105  	}
   106  
   107  	for r.Op() == ir.OCONVNOP && !types.Identical(r.Type(), typ) {
   108  		r = r.(*ir.ConvExpr).X
   109  	}
   110  
   111  	switch r.Op() {
   112  	case ir.OMETHEXPR:
   113  		r = r.(*ir.SelectorExpr).FuncName()
   114  		fallthrough
   115  	case ir.ONAME:
   116  		r := r.(*ir.Name)
   117  		if s.staticcopy(l, loff, r, typ) {
   118  			return true
   119  		}
   120  		// We may have skipped past one or more OCONVNOPs, so
   121  		// use conv to ensure r is assignable to l (#13263).
   122  		dst := ir.Node(l)
   123  		if loff != 0 || !types.Identical(typ, l.Type()) {
   124  			dst = ir.NewNameOffsetExpr(base.Pos, l, loff, typ)
   125  		}
   126  		s.append(ir.NewAssignStmt(base.Pos, dst, typecheck.Conv(r, typ)))
   127  		return true
   128  
   129  	case ir.ONIL:
   130  		return true
   131  
   132  	case ir.OLITERAL:
   133  		if ir.IsZero(r) {
   134  			return true
   135  		}
   136  		staticdata.InitConst(l, loff, r, int(typ.Size()))
   137  		return true
   138  
   139  	case ir.OADDR:
   140  		r := r.(*ir.AddrExpr)
   141  		if a, ok := r.X.(*ir.Name); ok && a.Op() == ir.ONAME {
   142  			staticdata.InitAddr(l, loff, staticdata.GlobalLinksym(a))
   143  			return true
   144  		}
   145  
   146  	case ir.OPTRLIT:
   147  		r := r.(*ir.AddrExpr)
   148  		switch r.X.Op() {
   149  		case ir.OARRAYLIT, ir.OSLICELIT, ir.OSTRUCTLIT, ir.OMAPLIT:
   150  			// copy pointer
   151  			staticdata.InitAddr(l, loff, staticdata.GlobalLinksym(s.Temps[r]))
   152  			return true
   153  		}
   154  
   155  	case ir.OSLICELIT:
   156  		r := r.(*ir.CompLitExpr)
   157  		// copy slice
   158  		staticdata.InitSlice(l, loff, staticdata.GlobalLinksym(s.Temps[r]), r.Len)
   159  		return true
   160  
   161  	case ir.OARRAYLIT, ir.OSTRUCTLIT:
   162  		r := r.(*ir.CompLitExpr)
   163  		p := s.Plans[r]
   164  		for i := range p.E {
   165  			e := &p.E[i]
   166  			typ := e.Expr.Type()
   167  			if e.Expr.Op() == ir.OLITERAL || e.Expr.Op() == ir.ONIL {
   168  				staticdata.InitConst(l, loff+e.Xoffset, e.Expr, int(typ.Size()))
   169  				continue
   170  			}
   171  			x := e.Expr
   172  			if x.Op() == ir.OMETHEXPR {
   173  				x = x.(*ir.SelectorExpr).FuncName()
   174  			}
   175  			if x.Op() == ir.ONAME && s.staticcopy(l, loff+e.Xoffset, x.(*ir.Name), typ) {
   176  				continue
   177  			}
   178  			// Requires computation, but we're
   179  			// copying someone else's computation.
   180  			ll := ir.NewNameOffsetExpr(base.Pos, l, loff+e.Xoffset, typ)
   181  			rr := ir.NewNameOffsetExpr(base.Pos, orig, e.Xoffset, typ)
   182  			ir.SetPos(rr)
   183  			s.append(ir.NewAssignStmt(base.Pos, ll, rr))
   184  		}
   185  
   186  		return true
   187  	}
   188  
   189  	return false
   190  }
   191  
   192  func (s *Schedule) StaticAssign(l *ir.Name, loff int64, r ir.Node, typ *types.Type) bool {
   193  	if r == nil {
   194  		// No explicit initialization value. Either zero or supplied
   195  		// externally.
   196  		return true
   197  	}
   198  	for r.Op() == ir.OCONVNOP {
   199  		r = r.(*ir.ConvExpr).X
   200  	}
   201  
   202  	assign := func(pos src.XPos, a *ir.Name, aoff int64, v ir.Node) {
   203  		if s.StaticAssign(a, aoff, v, v.Type()) {
   204  			return
   205  		}
   206  		var lhs ir.Node
   207  		if ir.IsBlank(a) {
   208  			// Don't use NameOffsetExpr with blank (#43677).
   209  			lhs = ir.BlankNode
   210  		} else {
   211  			lhs = ir.NewNameOffsetExpr(pos, a, aoff, v.Type())
   212  		}
   213  		s.append(ir.NewAssignStmt(pos, lhs, v))
   214  	}
   215  
   216  	switch r.Op() {
   217  	case ir.ONAME:
   218  		r := r.(*ir.Name)
   219  		return s.staticcopy(l, loff, r, typ)
   220  
   221  	case ir.OMETHEXPR:
   222  		r := r.(*ir.SelectorExpr)
   223  		return s.staticcopy(l, loff, r.FuncName(), typ)
   224  
   225  	case ir.ONIL:
   226  		return true
   227  
   228  	case ir.OLITERAL:
   229  		if ir.IsZero(r) {
   230  			return true
   231  		}
   232  		staticdata.InitConst(l, loff, r, int(typ.Size()))
   233  		return true
   234  
   235  	case ir.OADDR:
   236  		r := r.(*ir.AddrExpr)
   237  		if name, offset, ok := StaticLoc(r.X); ok && name.Class == ir.PEXTERN {
   238  			staticdata.InitAddrOffset(l, loff, name.Linksym(), offset)
   239  			return true
   240  		}
   241  		fallthrough
   242  
   243  	case ir.OPTRLIT:
   244  		r := r.(*ir.AddrExpr)
   245  		switch r.X.Op() {
   246  		case ir.OARRAYLIT, ir.OSLICELIT, ir.OMAPLIT, ir.OSTRUCTLIT:
   247  			// Init pointer.
   248  			a := StaticName(r.X.Type())
   249  
   250  			s.Temps[r] = a
   251  			staticdata.InitAddr(l, loff, a.Linksym())
   252  
   253  			// Init underlying literal.
   254  			assign(base.Pos, a, 0, r.X)
   255  			return true
   256  		}
   257  		//dump("not static ptrlit", r);
   258  
   259  	case ir.OSTR2BYTES:
   260  		r := r.(*ir.ConvExpr)
   261  		if l.Class == ir.PEXTERN && r.X.Op() == ir.OLITERAL {
   262  			sval := ir.StringVal(r.X)
   263  			staticdata.InitSliceBytes(l, loff, sval)
   264  			return true
   265  		}
   266  
   267  	case ir.OSLICELIT:
   268  		r := r.(*ir.CompLitExpr)
   269  		s.initplan(r)
   270  		// Init slice.
   271  		ta := types.NewArray(r.Type().Elem(), r.Len)
   272  		ta.SetNoalg(true)
   273  		a := StaticName(ta)
   274  		s.Temps[r] = a
   275  		staticdata.InitSlice(l, loff, a.Linksym(), r.Len)
   276  		// Fall through to init underlying array.
   277  		l = a
   278  		loff = 0
   279  		fallthrough
   280  
   281  	case ir.OARRAYLIT, ir.OSTRUCTLIT:
   282  		r := r.(*ir.CompLitExpr)
   283  		s.initplan(r)
   284  
   285  		p := s.Plans[r]
   286  		for i := range p.E {
   287  			e := &p.E[i]
   288  			if e.Expr.Op() == ir.OLITERAL || e.Expr.Op() == ir.ONIL {
   289  				staticdata.InitConst(l, loff+e.Xoffset, e.Expr, int(e.Expr.Type().Size()))
   290  				continue
   291  			}
   292  			ir.SetPos(e.Expr)
   293  			assign(base.Pos, l, loff+e.Xoffset, e.Expr)
   294  		}
   295  
   296  		return true
   297  
   298  	case ir.OMAPLIT:
   299  		break
   300  
   301  	case ir.OCLOSURE:
   302  		r := r.(*ir.ClosureExpr)
   303  		if ir.IsTrivialClosure(r) {
   304  			if base.Debug.Closure > 0 {
   305  				base.WarnfAt(r.Pos(), "closure converted to global")
   306  			}
   307  			// Closures with no captured variables are globals,
   308  			// so the assignment can be done at link time.
   309  			// TODO if roff != 0 { panic }
   310  			staticdata.InitAddr(l, loff, staticdata.FuncLinksym(r.Func.Nname))
   311  			return true
   312  		}
   313  		ir.ClosureDebugRuntimeCheck(r)
   314  
   315  	case ir.OCONVIFACE:
   316  		// This logic is mirrored in isStaticCompositeLiteral.
   317  		// If you change something here, change it there, and vice versa.
   318  
   319  		// Determine the underlying concrete type and value we are converting from.
   320  		r := r.(*ir.ConvExpr)
   321  		val := ir.Node(r)
   322  		for val.Op() == ir.OCONVIFACE {
   323  			val = val.(*ir.ConvExpr).X
   324  		}
   325  
   326  		if val.Type().IsInterface() {
   327  			// val is an interface type.
   328  			// If val is nil, we can statically initialize l;
   329  			// both words are zero and so there no work to do, so report success.
   330  			// If val is non-nil, we have no concrete type to record,
   331  			// and we won't be able to statically initialize its value, so report failure.
   332  			return val.Op() == ir.ONIL
   333  		}
   334  
   335  		reflectdata.MarkTypeUsedInInterface(val.Type(), l.Linksym())
   336  
   337  		var itab *ir.AddrExpr
   338  		if typ.IsEmptyInterface() {
   339  			itab = reflectdata.TypePtr(val.Type())
   340  		} else {
   341  			itab = reflectdata.ITabAddr(val.Type(), typ)
   342  		}
   343  
   344  		// Create a copy of l to modify while we emit data.
   345  
   346  		// Emit itab, advance offset.
   347  		staticdata.InitAddr(l, loff, itab.X.(*ir.LinksymOffsetExpr).Linksym)
   348  
   349  		// Emit data.
   350  		if types.IsDirectIface(val.Type()) {
   351  			if val.Op() == ir.ONIL {
   352  				// Nil is zero, nothing to do.
   353  				return true
   354  			}
   355  			// Copy val directly into n.
   356  			ir.SetPos(val)
   357  			assign(base.Pos, l, loff+int64(types.PtrSize), val)
   358  		} else {
   359  			// Construct temp to hold val, write pointer to temp into n.
   360  			a := StaticName(val.Type())
   361  			s.Temps[val] = a
   362  			assign(base.Pos, a, 0, val)
   363  			staticdata.InitAddr(l, loff+int64(types.PtrSize), a.Linksym())
   364  		}
   365  
   366  		return true
   367  	}
   368  
   369  	//dump("not static", r);
   370  	return false
   371  }
   372  
   373  func (s *Schedule) initplan(n ir.Node) {
   374  	if s.Plans[n] != nil {
   375  		return
   376  	}
   377  	p := new(Plan)
   378  	s.Plans[n] = p
   379  	switch n.Op() {
   380  	default:
   381  		base.Fatalf("initplan")
   382  
   383  	case ir.OARRAYLIT, ir.OSLICELIT:
   384  		n := n.(*ir.CompLitExpr)
   385  		var k int64
   386  		for _, a := range n.List {
   387  			if a.Op() == ir.OKEY {
   388  				kv := a.(*ir.KeyExpr)
   389  				k = typecheck.IndexConst(kv.Key)
   390  				if k < 0 {
   391  					base.Fatalf("initplan arraylit: invalid index %v", kv.Key)
   392  				}
   393  				a = kv.Value
   394  			}
   395  			s.addvalue(p, k*n.Type().Elem().Size(), a)
   396  			k++
   397  		}
   398  
   399  	case ir.OSTRUCTLIT:
   400  		n := n.(*ir.CompLitExpr)
   401  		for _, a := range n.List {
   402  			if a.Op() != ir.OSTRUCTKEY {
   403  				base.Fatalf("initplan structlit")
   404  			}
   405  			a := a.(*ir.StructKeyExpr)
   406  			if a.Sym().IsBlank() {
   407  				continue
   408  			}
   409  			s.addvalue(p, a.Field.Offset, a.Value)
   410  		}
   411  
   412  	case ir.OMAPLIT:
   413  		n := n.(*ir.CompLitExpr)
   414  		for _, a := range n.List {
   415  			if a.Op() != ir.OKEY {
   416  				base.Fatalf("initplan maplit")
   417  			}
   418  			a := a.(*ir.KeyExpr)
   419  			s.addvalue(p, -1, a.Value)
   420  		}
   421  	}
   422  }
   423  
   424  func (s *Schedule) addvalue(p *Plan, xoffset int64, n ir.Node) {
   425  	// special case: zero can be dropped entirely
   426  	if ir.IsZero(n) {
   427  		return
   428  	}
   429  
   430  	// special case: inline struct and array (not slice) literals
   431  	if isvaluelit(n) {
   432  		s.initplan(n)
   433  		q := s.Plans[n]
   434  		for _, qe := range q.E {
   435  			// qe is a copy; we are not modifying entries in q.E
   436  			qe.Xoffset += xoffset
   437  			p.E = append(p.E, qe)
   438  		}
   439  		return
   440  	}
   441  
   442  	// add to plan
   443  	p.E = append(p.E, Entry{Xoffset: xoffset, Expr: n})
   444  }
   445  
   446  // from here down is the walk analysis
   447  // of composite literals.
   448  // most of the work is to generate
   449  // data statements for the constant
   450  // part of the composite literal.
   451  
   452  var statuniqgen int // name generator for static temps
   453  
   454  // StaticName returns a name backed by a (writable) static data symbol.
   455  // Use readonlystaticname for read-only node.
   456  func StaticName(t *types.Type) *ir.Name {
   457  	// Don't use LookupNum; it interns the resulting string, but these are all unique.
   458  	n := typecheck.NewName(typecheck.Lookup(fmt.Sprintf("%s%d", obj.StaticNamePref, statuniqgen)))
   459  	statuniqgen++
   460  	typecheck.Declare(n, ir.PEXTERN)
   461  	n.SetType(t)
   462  	return n
   463  }
   464  
   465  // StaticLoc returns the static address of n, if n has one, or else nil.
   466  func StaticLoc(n ir.Node) (name *ir.Name, offset int64, ok bool) {
   467  	if n == nil {
   468  		return nil, 0, false
   469  	}
   470  
   471  	switch n.Op() {
   472  	case ir.ONAME:
   473  		n := n.(*ir.Name)
   474  		return n, 0, true
   475  
   476  	case ir.OMETHEXPR:
   477  		n := n.(*ir.SelectorExpr)
   478  		return StaticLoc(n.FuncName())
   479  
   480  	case ir.ODOT:
   481  		n := n.(*ir.SelectorExpr)
   482  		if name, offset, ok = StaticLoc(n.X); !ok {
   483  			break
   484  		}
   485  		offset += n.Offset()
   486  		return name, offset, true
   487  
   488  	case ir.OINDEX:
   489  		n := n.(*ir.IndexExpr)
   490  		if n.X.Type().IsSlice() {
   491  			break
   492  		}
   493  		if name, offset, ok = StaticLoc(n.X); !ok {
   494  			break
   495  		}
   496  		l := getlit(n.Index)
   497  		if l < 0 {
   498  			break
   499  		}
   500  
   501  		// Check for overflow.
   502  		if n.Type().Size() != 0 && types.MaxWidth/n.Type().Size() <= int64(l) {
   503  			break
   504  		}
   505  		offset += int64(l) * n.Type().Size()
   506  		return name, offset, true
   507  	}
   508  
   509  	return nil, 0, false
   510  }
   511  
   512  // AnySideEffects reports whether n contains any operations that could have observable side effects.
   513  func AnySideEffects(n ir.Node) bool {
   514  	return ir.Any(n, func(n ir.Node) bool {
   515  		switch n.Op() {
   516  		// Assume side effects unless we know otherwise.
   517  		default:
   518  			return true
   519  
   520  		// No side effects here (arguments are checked separately).
   521  		case ir.ONAME,
   522  			ir.ONONAME,
   523  			ir.OTYPE,
   524  			ir.OPACK,
   525  			ir.OLITERAL,
   526  			ir.ONIL,
   527  			ir.OADD,
   528  			ir.OSUB,
   529  			ir.OOR,
   530  			ir.OXOR,
   531  			ir.OADDSTR,
   532  			ir.OADDR,
   533  			ir.OANDAND,
   534  			ir.OBYTES2STR,
   535  			ir.ORUNES2STR,
   536  			ir.OSTR2BYTES,
   537  			ir.OSTR2RUNES,
   538  			ir.OCAP,
   539  			ir.OCOMPLIT,
   540  			ir.OMAPLIT,
   541  			ir.OSTRUCTLIT,
   542  			ir.OARRAYLIT,
   543  			ir.OSLICELIT,
   544  			ir.OPTRLIT,
   545  			ir.OCONV,
   546  			ir.OCONVIFACE,
   547  			ir.OCONVNOP,
   548  			ir.ODOT,
   549  			ir.OEQ,
   550  			ir.ONE,
   551  			ir.OLT,
   552  			ir.OLE,
   553  			ir.OGT,
   554  			ir.OGE,
   555  			ir.OKEY,
   556  			ir.OSTRUCTKEY,
   557  			ir.OLEN,
   558  			ir.OMUL,
   559  			ir.OLSH,
   560  			ir.ORSH,
   561  			ir.OAND,
   562  			ir.OANDNOT,
   563  			ir.ONEW,
   564  			ir.ONOT,
   565  			ir.OBITNOT,
   566  			ir.OPLUS,
   567  			ir.ONEG,
   568  			ir.OOROR,
   569  			ir.OPAREN,
   570  			ir.ORUNESTR,
   571  			ir.OREAL,
   572  			ir.OIMAG,
   573  			ir.OCOMPLEX:
   574  			return false
   575  
   576  		// Only possible side effect is division by zero.
   577  		case ir.ODIV, ir.OMOD:
   578  			n := n.(*ir.BinaryExpr)
   579  			if n.Y.Op() != ir.OLITERAL || constant.Sign(n.Y.Val()) == 0 {
   580  				return true
   581  			}
   582  
   583  		// Only possible side effect is panic on invalid size,
   584  		// but many makechan and makemap use size zero, which is definitely OK.
   585  		case ir.OMAKECHAN, ir.OMAKEMAP:
   586  			n := n.(*ir.MakeExpr)
   587  			if !ir.IsConst(n.Len, constant.Int) || constant.Sign(n.Len.Val()) != 0 {
   588  				return true
   589  			}
   590  
   591  		// Only possible side effect is panic on invalid size.
   592  		// TODO(rsc): Merge with previous case (probably breaks toolstash -cmp).
   593  		case ir.OMAKESLICE, ir.OMAKESLICECOPY:
   594  			return true
   595  		}
   596  		return false
   597  	})
   598  }
   599  
   600  func getlit(lit ir.Node) int {
   601  	if ir.IsSmallIntConst(lit) {
   602  		return int(ir.Int64Val(lit))
   603  	}
   604  	return -1
   605  }
   606  
   607  func isvaluelit(n ir.Node) bool {
   608  	return n.Op() == ir.OARRAYLIT || n.Op() == ir.OSTRUCTLIT
   609  }
   610  

View as plain text