alg.go

Documentation: cmd/compile/internal/reflectdata

     1  // Copyright 2016 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 reflectdata
     6  
     7  import (
     8  	"fmt"
     9  	"math/bits"
    10  	"sort"
    11  
    12  	"cmd/compile/internal/base"
    13  	"cmd/compile/internal/ir"
    14  	"cmd/compile/internal/objw"
    15  	"cmd/compile/internal/typecheck"
    16  	"cmd/compile/internal/types"
    17  	"cmd/internal/obj"
    18  )
    19  
    20  // isRegularMemory reports whether t can be compared/hashed as regular memory.
    21  func isRegularMemory(t *types.Type) bool {
    22  	a, _ := types.AlgType(t)
    23  	return a == types.AMEM
    24  }
    25  
    26  // eqCanPanic reports whether == on type t could panic (has an interface somewhere).
    27  // t must be comparable.
    28  func eqCanPanic(t *types.Type) bool {
    29  	switch t.Kind() {
    30  	default:
    31  		return false
    32  	case types.TINTER:
    33  		return true
    34  	case types.TARRAY:
    35  		return eqCanPanic(t.Elem())
    36  	case types.TSTRUCT:
    37  		for _, f := range t.FieldSlice() {
    38  			if !f.Sym.IsBlank() && eqCanPanic(f.Type) {
    39  				return true
    40  			}
    41  		}
    42  		return false
    43  	}
    44  }
    45  
    46  // AlgType returns the fixed-width AMEMxx variants instead of the general
    47  // AMEM kind when possible.
    48  func AlgType(t *types.Type) types.AlgKind {
    49  	a, _ := types.AlgType(t)
    50  	if a == types.AMEM {
    51  		if t.Alignment() < int64(base.Ctxt.Arch.Alignment) && t.Alignment() < t.Width {
    52  			// For example, we can't treat [2]int16 as an int32 if int32s require
    53  			// 4-byte alignment. See issue 46283.
    54  			return a
    55  		}
    56  		switch t.Width {
    57  		case 0:
    58  			return types.AMEM0
    59  		case 1:
    60  			return types.AMEM8
    61  		case 2:
    62  			return types.AMEM16
    63  		case 4:
    64  			return types.AMEM32
    65  		case 8:
    66  			return types.AMEM64
    67  		case 16:
    68  			return types.AMEM128
    69  		}
    70  	}
    71  
    72  	return a
    73  }
    74  
    75  // genhash returns a symbol which is the closure used to compute
    76  // the hash of a value of type t.
    77  // Note: the generated function must match runtime.typehash exactly.
    78  func genhash(t *types.Type) *obj.LSym {
    79  	switch AlgType(t) {
    80  	default:
    81  		// genhash is only called for types that have equality
    82  		base.Fatalf("genhash %v", t)
    83  	case types.AMEM0:
    84  		return sysClosure("memhash0")
    85  	case types.AMEM8:
    86  		return sysClosure("memhash8")
    87  	case types.AMEM16:
    88  		return sysClosure("memhash16")
    89  	case types.AMEM32:
    90  		return sysClosure("memhash32")
    91  	case types.AMEM64:
    92  		return sysClosure("memhash64")
    93  	case types.AMEM128:
    94  		return sysClosure("memhash128")
    95  	case types.ASTRING:
    96  		return sysClosure("strhash")
    97  	case types.AINTER:
    98  		return sysClosure("interhash")
    99  	case types.ANILINTER:
   100  		return sysClosure("nilinterhash")
   101  	case types.AFLOAT32:
   102  		return sysClosure("f32hash")
   103  	case types.AFLOAT64:
   104  		return sysClosure("f64hash")
   105  	case types.ACPLX64:
   106  		return sysClosure("c64hash")
   107  	case types.ACPLX128:
   108  		return sysClosure("c128hash")
   109  	case types.AMEM:
   110  		// For other sizes of plain memory, we build a closure
   111  		// that calls memhash_varlen. The size of the memory is
   112  		// encoded in the first slot of the closure.
   113  		closure := TypeLinksymLookup(fmt.Sprintf(".hashfunc%d", t.Width))
   114  		if len(closure.P) > 0 { // already generated
   115  			return closure
   116  		}
   117  		if memhashvarlen == nil {
   118  			memhashvarlen = typecheck.LookupRuntimeFunc("memhash_varlen")
   119  		}
   120  		ot := 0
   121  		ot = objw.SymPtr(closure, ot, memhashvarlen, 0)
   122  		ot = objw.Uintptr(closure, ot, uint64(t.Width)) // size encoded in closure
   123  		objw.Global(closure, int32(ot), obj.DUPOK|obj.RODATA)
   124  		return closure
   125  	case types.ASPECIAL:
   126  		break
   127  	}
   128  
   129  	closure := TypeLinksymPrefix(".hashfunc", t)
   130  	if len(closure.P) > 0 { // already generated
   131  		return closure
   132  	}
   133  
   134  	// Generate hash functions for subtypes.
   135  	// There are cases where we might not use these hashes,
   136  	// but in that case they will get dead-code eliminated.
   137  	// (And the closure generated by genhash will also get
   138  	// dead-code eliminated, as we call the subtype hashers
   139  	// directly.)
   140  	switch t.Kind() {
   141  	case types.TARRAY:
   142  		genhash(t.Elem())
   143  	case types.TSTRUCT:
   144  		for _, f := range t.FieldSlice() {
   145  			genhash(f.Type)
   146  		}
   147  	}
   148  
   149  	sym := TypeSymPrefix(".hash", t)
   150  	if base.Flag.LowerR != 0 {
   151  		fmt.Printf("genhash %v %v %v\n", closure, sym, t)
   152  	}
   153  
   154  	base.Pos = base.AutogeneratedPos // less confusing than end of input
   155  	typecheck.DeclContext = ir.PEXTERN
   156  
   157  	// func sym(p *T, h uintptr) uintptr
   158  	args := []*ir.Field{
   159  		ir.NewField(base.Pos, typecheck.Lookup("p"), nil, types.NewPtr(t)),
   160  		ir.NewField(base.Pos, typecheck.Lookup("h"), nil, types.Types[types.TUINTPTR]),
   161  	}
   162  	results := []*ir.Field{ir.NewField(base.Pos, nil, nil, types.Types[types.TUINTPTR])}
   163  	tfn := ir.NewFuncType(base.Pos, nil, args, results)
   164  
   165  	fn := typecheck.DeclFunc(sym, tfn)
   166  	np := ir.AsNode(tfn.Type().Params().Field(0).Nname)
   167  	nh := ir.AsNode(tfn.Type().Params().Field(1).Nname)
   168  
   169  	switch t.Kind() {
   170  	case types.TARRAY:
   171  		// An array of pure memory would be handled by the
   172  		// standard algorithm, so the element type must not be
   173  		// pure memory.
   174  		hashel := hashfor(t.Elem())
   175  
   176  		// for i := 0; i < nelem; i++
   177  		ni := typecheck.Temp(types.Types[types.TINT])
   178  		init := ir.NewAssignStmt(base.Pos, ni, ir.NewInt(0))
   179  		cond := ir.NewBinaryExpr(base.Pos, ir.OLT, ni, ir.NewInt(t.NumElem()))
   180  		post := ir.NewAssignStmt(base.Pos, ni, ir.NewBinaryExpr(base.Pos, ir.OADD, ni, ir.NewInt(1)))
   181  		loop := ir.NewForStmt(base.Pos, nil, cond, post, nil)
   182  		loop.PtrInit().Append(init)
   183  
   184  		// h = hashel(&p[i], h)
   185  		call := ir.NewCallExpr(base.Pos, ir.OCALL, hashel, nil)
   186  
   187  		nx := ir.NewIndexExpr(base.Pos, np, ni)
   188  		nx.SetBounded(true)
   189  		na := typecheck.NodAddr(nx)
   190  		call.Args.Append(na)
   191  		call.Args.Append(nh)
   192  		loop.Body.Append(ir.NewAssignStmt(base.Pos, nh, call))
   193  
   194  		fn.Body.Append(loop)
   195  
   196  	case types.TSTRUCT:
   197  		// Walk the struct using memhash for runs of AMEM
   198  		// and calling specific hash functions for the others.
   199  		for i, fields := 0, t.FieldSlice(); i < len(fields); {
   200  			f := fields[i]
   201  
   202  			// Skip blank fields.
   203  			if f.Sym.IsBlank() {
   204  				i++
   205  				continue
   206  			}
   207  
   208  			// Hash non-memory fields with appropriate hash function.
   209  			if !isRegularMemory(f.Type) {
   210  				hashel := hashfor(f.Type)
   211  				call := ir.NewCallExpr(base.Pos, ir.OCALL, hashel, nil)
   212  				nx := ir.NewSelectorExpr(base.Pos, ir.OXDOT, np, f.Sym) // TODO: fields from other packages?
   213  				na := typecheck.NodAddr(nx)
   214  				call.Args.Append(na)
   215  				call.Args.Append(nh)
   216  				fn.Body.Append(ir.NewAssignStmt(base.Pos, nh, call))
   217  				i++
   218  				continue
   219  			}
   220  
   221  			// Otherwise, hash a maximal length run of raw memory.
   222  			size, next := memrun(t, i)
   223  
   224  			// h = hashel(&p.first, size, h)
   225  			hashel := hashmem(f.Type)
   226  			call := ir.NewCallExpr(base.Pos, ir.OCALL, hashel, nil)
   227  			nx := ir.NewSelectorExpr(base.Pos, ir.OXDOT, np, f.Sym) // TODO: fields from other packages?
   228  			na := typecheck.NodAddr(nx)
   229  			call.Args.Append(na)
   230  			call.Args.Append(nh)
   231  			call.Args.Append(ir.NewInt(size))
   232  			fn.Body.Append(ir.NewAssignStmt(base.Pos, nh, call))
   233  
   234  			i = next
   235  		}
   236  	}
   237  
   238  	r := ir.NewReturnStmt(base.Pos, nil)
   239  	r.Results.Append(nh)
   240  	fn.Body.Append(r)
   241  
   242  	if base.Flag.LowerR != 0 {
   243  		ir.DumpList("genhash body", fn.Body)
   244  	}
   245  
   246  	typecheck.FinishFuncBody()
   247  
   248  	fn.SetDupok(true)
   249  	typecheck.Func(fn)
   250  
   251  	ir.CurFunc = fn
   252  	typecheck.Stmts(fn.Body)
   253  	ir.CurFunc = nil
   254  
   255  	if base.Debug.DclStack != 0 {
   256  		types.CheckDclstack()
   257  	}
   258  
   259  	fn.SetNilCheckDisabled(true)
   260  	typecheck.Target.Decls = append(typecheck.Target.Decls, fn)
   261  
   262  	// Build closure. It doesn't close over any variables, so
   263  	// it contains just the function pointer.
   264  	objw.SymPtr(closure, 0, fn.Linksym(), 0)
   265  	objw.Global(closure, int32(types.PtrSize), obj.DUPOK|obj.RODATA)
   266  
   267  	return closure
   268  }
   269  
   270  func hashfor(t *types.Type) ir.Node {
   271  	var sym *types.Sym
   272  
   273  	switch a, _ := types.AlgType(t); a {
   274  	case types.AMEM:
   275  		base.Fatalf("hashfor with AMEM type")
   276  	case types.AINTER:
   277  		sym = ir.Pkgs.Runtime.Lookup("interhash")
   278  	case types.ANILINTER:
   279  		sym = ir.Pkgs.Runtime.Lookup("nilinterhash")
   280  	case types.ASTRING:
   281  		sym = ir.Pkgs.Runtime.Lookup("strhash")
   282  	case types.AFLOAT32:
   283  		sym = ir.Pkgs.Runtime.Lookup("f32hash")
   284  	case types.AFLOAT64:
   285  		sym = ir.Pkgs.Runtime.Lookup("f64hash")
   286  	case types.ACPLX64:
   287  		sym = ir.Pkgs.Runtime.Lookup("c64hash")
   288  	case types.ACPLX128:
   289  		sym = ir.Pkgs.Runtime.Lookup("c128hash")
   290  	default:
   291  		// Note: the caller of hashfor ensured that this symbol
   292  		// exists and has a body by calling genhash for t.
   293  		sym = TypeSymPrefix(".hash", t)
   294  	}
   295  
   296  	// TODO(austin): This creates an ir.Name with a nil Func.
   297  	n := typecheck.NewName(sym)
   298  	ir.MarkFunc(n)
   299  	n.SetType(types.NewSignature(types.NoPkg, nil, nil, []*types.Field{
   300  		types.NewField(base.Pos, nil, types.NewPtr(t)),
   301  		types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
   302  	}, []*types.Field{
   303  		types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
   304  	}))
   305  	return n
   306  }
   307  
   308  // sysClosure returns a closure which will call the
   309  // given runtime function (with no closed-over variables).
   310  func sysClosure(name string) *obj.LSym {
   311  	s := typecheck.LookupRuntimeVar(name + "·f")
   312  	if len(s.P) == 0 {
   313  		f := typecheck.LookupRuntimeFunc(name)
   314  		objw.SymPtr(s, 0, f, 0)
   315  		objw.Global(s, int32(types.PtrSize), obj.DUPOK|obj.RODATA)
   316  	}
   317  	return s
   318  }
   319  
   320  // geneq returns a symbol which is the closure used to compute
   321  // equality for two objects of type t.
   322  func geneq(t *types.Type) *obj.LSym {
   323  	switch AlgType(t) {
   324  	case types.ANOEQ:
   325  		// The runtime will panic if it tries to compare
   326  		// a type with a nil equality function.
   327  		return nil
   328  	case types.AMEM0:
   329  		return sysClosure("memequal0")
   330  	case types.AMEM8:
   331  		return sysClosure("memequal8")
   332  	case types.AMEM16:
   333  		return sysClosure("memequal16")
   334  	case types.AMEM32:
   335  		return sysClosure("memequal32")
   336  	case types.AMEM64:
   337  		return sysClosure("memequal64")
   338  	case types.AMEM128:
   339  		return sysClosure("memequal128")
   340  	case types.ASTRING:
   341  		return sysClosure("strequal")
   342  	case types.AINTER:
   343  		return sysClosure("interequal")
   344  	case types.ANILINTER:
   345  		return sysClosure("nilinterequal")
   346  	case types.AFLOAT32:
   347  		return sysClosure("f32equal")
   348  	case types.AFLOAT64:
   349  		return sysClosure("f64equal")
   350  	case types.ACPLX64:
   351  		return sysClosure("c64equal")
   352  	case types.ACPLX128:
   353  		return sysClosure("c128equal")
   354  	case types.AMEM:
   355  		// make equality closure. The size of the type
   356  		// is encoded in the closure.
   357  		closure := TypeLinksymLookup(fmt.Sprintf(".eqfunc%d", t.Width))
   358  		if len(closure.P) != 0 {
   359  			return closure
   360  		}
   361  		if memequalvarlen == nil {
   362  			memequalvarlen = typecheck.LookupRuntimeFunc("memequal_varlen")
   363  		}
   364  		ot := 0
   365  		ot = objw.SymPtr(closure, ot, memequalvarlen, 0)
   366  		ot = objw.Uintptr(closure, ot, uint64(t.Width))
   367  		objw.Global(closure, int32(ot), obj.DUPOK|obj.RODATA)
   368  		return closure
   369  	case types.ASPECIAL:
   370  		break
   371  	}
   372  
   373  	closure := TypeLinksymPrefix(".eqfunc", t)
   374  	if len(closure.P) > 0 { // already generated
   375  		return closure
   376  	}
   377  	sym := TypeSymPrefix(".eq", t)
   378  	if base.Flag.LowerR != 0 {
   379  		fmt.Printf("geneq %v\n", t)
   380  	}
   381  
   382  	// Autogenerate code for equality of structs and arrays.
   383  
   384  	base.Pos = base.AutogeneratedPos // less confusing than end of input
   385  	typecheck.DeclContext = ir.PEXTERN
   386  
   387  	// func sym(p, q *T) bool
   388  	tfn := ir.NewFuncType(base.Pos, nil,
   389  		[]*ir.Field{ir.NewField(base.Pos, typecheck.Lookup("p"), nil, types.NewPtr(t)), ir.NewField(base.Pos, typecheck.Lookup("q"), nil, types.NewPtr(t))},
   390  		[]*ir.Field{ir.NewField(base.Pos, typecheck.Lookup("r"), nil, types.Types[types.TBOOL])})
   391  
   392  	fn := typecheck.DeclFunc(sym, tfn)
   393  	np := ir.AsNode(tfn.Type().Params().Field(0).Nname)
   394  	nq := ir.AsNode(tfn.Type().Params().Field(1).Nname)
   395  	nr := ir.AsNode(tfn.Type().Results().Field(0).Nname)
   396  
   397  	// Label to jump to if an equality test fails.
   398  	neq := typecheck.AutoLabel(".neq")
   399  
   400  	// We reach here only for types that have equality but
   401  	// cannot be handled by the standard algorithms,
   402  	// so t must be either an array or a struct.
   403  	switch t.Kind() {
   404  	default:
   405  		base.Fatalf("geneq %v", t)
   406  
   407  	case types.TARRAY:
   408  		nelem := t.NumElem()
   409  
   410  		// checkAll generates code to check the equality of all array elements.
   411  		// If unroll is greater than nelem, checkAll generates:
   412  		//
   413  		// if eq(p[0], q[0]) && eq(p[1], q[1]) && ... {
   414  		// } else {
   415  		//   return
   416  		// }
   417  		//
   418  		// And so on.
   419  		//
   420  		// Otherwise it generates:
   421  		//
   422  		// for i := 0; i < nelem; i++ {
   423  		//   if eq(p[i], q[i]) {
   424  		//   } else {
   425  		//     goto neq
   426  		//   }
   427  		// }
   428  		//
   429  		// TODO(josharian): consider doing some loop unrolling
   430  		// for larger nelem as well, processing a few elements at a time in a loop.
   431  		checkAll := func(unroll int64, last bool, eq func(pi, qi ir.Node) ir.Node) {
   432  			// checkIdx generates a node to check for equality at index i.
   433  			checkIdx := func(i ir.Node) ir.Node {
   434  				// pi := p[i]
   435  				pi := ir.NewIndexExpr(base.Pos, np, i)
   436  				pi.SetBounded(true)
   437  				pi.SetType(t.Elem())
   438  				// qi := q[i]
   439  				qi := ir.NewIndexExpr(base.Pos, nq, i)
   440  				qi.SetBounded(true)
   441  				qi.SetType(t.Elem())
   442  				return eq(pi, qi)
   443  			}
   444  
   445  			if nelem <= unroll {
   446  				if last {
   447  					// Do last comparison in a different manner.
   448  					nelem--
   449  				}
   450  				// Generate a series of checks.
   451  				for i := int64(0); i < nelem; i++ {
   452  					// if check {} else { goto neq }
   453  					nif := ir.NewIfStmt(base.Pos, checkIdx(ir.NewInt(i)), nil, nil)
   454  					nif.Else.Append(ir.NewBranchStmt(base.Pos, ir.OGOTO, neq))
   455  					fn.Body.Append(nif)
   456  				}
   457  				if last {
   458  					fn.Body.Append(ir.NewAssignStmt(base.Pos, nr, checkIdx(ir.NewInt(nelem))))
   459  				}
   460  			} else {
   461  				// Generate a for loop.
   462  				// for i := 0; i < nelem; i++
   463  				i := typecheck.Temp(types.Types[types.TINT])
   464  				init := ir.NewAssignStmt(base.Pos, i, ir.NewInt(0))
   465  				cond := ir.NewBinaryExpr(base.Pos, ir.OLT, i, ir.NewInt(nelem))
   466  				post := ir.NewAssignStmt(base.Pos, i, ir.NewBinaryExpr(base.Pos, ir.OADD, i, ir.NewInt(1)))
   467  				loop := ir.NewForStmt(base.Pos, nil, cond, post, nil)
   468  				loop.PtrInit().Append(init)
   469  				// if eq(pi, qi) {} else { goto neq }
   470  				nif := ir.NewIfStmt(base.Pos, checkIdx(i), nil, nil)
   471  				nif.Else.Append(ir.NewBranchStmt(base.Pos, ir.OGOTO, neq))
   472  				loop.Body.Append(nif)
   473  				fn.Body.Append(loop)
   474  				if last {
   475  					fn.Body.Append(ir.NewAssignStmt(base.Pos, nr, ir.NewBool(true)))
   476  				}
   477  			}
   478  		}
   479  
   480  		switch t.Elem().Kind() {
   481  		case types.TSTRING:
   482  			// Do two loops. First, check that all the lengths match (cheap).
   483  			// Second, check that all the contents match (expensive).
   484  			// TODO: when the array size is small, unroll the length match checks.
   485  			checkAll(3, false, func(pi, qi ir.Node) ir.Node {
   486  				// Compare lengths.
   487  				eqlen, _ := EqString(pi, qi)
   488  				return eqlen
   489  			})
   490  			checkAll(1, true, func(pi, qi ir.Node) ir.Node {
   491  				// Compare contents.
   492  				_, eqmem := EqString(pi, qi)
   493  				return eqmem
   494  			})
   495  		case types.TFLOAT32, types.TFLOAT64:
   496  			checkAll(2, true, func(pi, qi ir.Node) ir.Node {
   497  				// p[i] == q[i]
   498  				return ir.NewBinaryExpr(base.Pos, ir.OEQ, pi, qi)
   499  			})
   500  		// TODO: pick apart structs, do them piecemeal too
   501  		default:
   502  			checkAll(1, true, func(pi, qi ir.Node) ir.Node {
   503  				// p[i] == q[i]
   504  				return ir.NewBinaryExpr(base.Pos, ir.OEQ, pi, qi)
   505  			})
   506  		}
   507  
   508  	case types.TSTRUCT:
   509  		// Build a list of conditions to satisfy.
   510  		// The conditions are a list-of-lists. Conditions are reorderable
   511  		// within each inner list. The outer lists must be evaluated in order.
   512  		var conds [][]ir.Node
   513  		conds = append(conds, []ir.Node{})
   514  		and := func(n ir.Node) {
   515  			i := len(conds) - 1
   516  			conds[i] = append(conds[i], n)
   517  		}
   518  
   519  		// Walk the struct using memequal for runs of AMEM
   520  		// and calling specific equality tests for the others.
   521  		for i, fields := 0, t.FieldSlice(); i < len(fields); {
   522  			f := fields[i]
   523  
   524  			// Skip blank-named fields.
   525  			if f.Sym.IsBlank() {
   526  				i++
   527  				continue
   528  			}
   529  
   530  			// Compare non-memory fields with field equality.
   531  			if !isRegularMemory(f.Type) {
   532  				if eqCanPanic(f.Type) {
   533  					// Enforce ordering by starting a new set of reorderable conditions.
   534  					conds = append(conds, []ir.Node{})
   535  				}
   536  				p := ir.NewSelectorExpr(base.Pos, ir.OXDOT, np, f.Sym)
   537  				q := ir.NewSelectorExpr(base.Pos, ir.OXDOT, nq, f.Sym)
   538  				switch {
   539  				case f.Type.IsString():
   540  					eqlen, eqmem := EqString(p, q)
   541  					and(eqlen)
   542  					and(eqmem)
   543  				default:
   544  					and(ir.NewBinaryExpr(base.Pos, ir.OEQ, p, q))
   545  				}
   546  				if eqCanPanic(f.Type) {
   547  					// Also enforce ordering after something that can panic.
   548  					conds = append(conds, []ir.Node{})
   549  				}
   550  				i++
   551  				continue
   552  			}
   553  
   554  			// Find maximal length run of memory-only fields.
   555  			size, next := memrun(t, i)
   556  
   557  			// TODO(rsc): All the calls to newname are wrong for
   558  			// cross-package unexported fields.
   559  			if s := fields[i:next]; len(s) <= 2 {
   560  				// Two or fewer fields: use plain field equality.
   561  				for _, f := range s {
   562  					and(eqfield(np, nq, f.Sym))
   563  				}
   564  			} else {
   565  				// More than two fields: use memequal.
   566  				and(eqmem(np, nq, f.Sym, size))
   567  			}
   568  			i = next
   569  		}
   570  
   571  		// Sort conditions to put runtime calls last.
   572  		// Preserve the rest of the ordering.
   573  		var flatConds []ir.Node
   574  		for _, c := range conds {
   575  			isCall := func(n ir.Node) bool {
   576  				return n.Op() == ir.OCALL || n.Op() == ir.OCALLFUNC
   577  			}
   578  			sort.SliceStable(c, func(i, j int) bool {
   579  				return !isCall(c[i]) && isCall(c[j])
   580  			})
   581  			flatConds = append(flatConds, c...)
   582  		}
   583  
   584  		if len(flatConds) == 0 {
   585  			fn.Body.Append(ir.NewAssignStmt(base.Pos, nr, ir.NewBool(true)))
   586  		} else {
   587  			for _, c := range flatConds[:len(flatConds)-1] {
   588  				// if cond {} else { goto neq }
   589  				n := ir.NewIfStmt(base.Pos, c, nil, nil)
   590  				n.Else.Append(ir.NewBranchStmt(base.Pos, ir.OGOTO, neq))
   591  				fn.Body.Append(n)
   592  			}
   593  			fn.Body.Append(ir.NewAssignStmt(base.Pos, nr, flatConds[len(flatConds)-1]))
   594  		}
   595  	}
   596  
   597  	// ret:
   598  	//   return
   599  	ret := typecheck.AutoLabel(".ret")
   600  	fn.Body.Append(ir.NewLabelStmt(base.Pos, ret))
   601  	fn.Body.Append(ir.NewReturnStmt(base.Pos, nil))
   602  
   603  	// neq:
   604  	//   r = false
   605  	//   return (or goto ret)
   606  	fn.Body.Append(ir.NewLabelStmt(base.Pos, neq))
   607  	fn.Body.Append(ir.NewAssignStmt(base.Pos, nr, ir.NewBool(false)))
   608  	if eqCanPanic(t) || anyCall(fn) {
   609  		// Epilogue is large, so share it with the equal case.
   610  		fn.Body.Append(ir.NewBranchStmt(base.Pos, ir.OGOTO, ret))
   611  	} else {
   612  		// Epilogue is small, so don't bother sharing.
   613  		fn.Body.Append(ir.NewReturnStmt(base.Pos, nil))
   614  	}
   615  	// TODO(khr): the epilogue size detection condition above isn't perfect.
   616  	// We should really do a generic CL that shares epilogues across
   617  	// the board. See #24936.
   618  
   619  	if base.Flag.LowerR != 0 {
   620  		ir.DumpList("geneq body", fn.Body)
   621  	}
   622  
   623  	typecheck.FinishFuncBody()
   624  
   625  	fn.SetDupok(true)
   626  	typecheck.Func(fn)
   627  
   628  	ir.CurFunc = fn
   629  	typecheck.Stmts(fn.Body)
   630  	ir.CurFunc = nil
   631  
   632  	if base.Debug.DclStack != 0 {
   633  		types.CheckDclstack()
   634  	}
   635  
   636  	// Disable checknils while compiling this code.
   637  	// We are comparing a struct or an array,
   638  	// neither of which can be nil, and our comparisons
   639  	// are shallow.
   640  	fn.SetNilCheckDisabled(true)
   641  	typecheck.Target.Decls = append(typecheck.Target.Decls, fn)
   642  
   643  	// Generate a closure which points at the function we just generated.
   644  	objw.SymPtr(closure, 0, fn.Linksym(), 0)
   645  	objw.Global(closure, int32(types.PtrSize), obj.DUPOK|obj.RODATA)
   646  	return closure
   647  }
   648  
   649  func anyCall(fn *ir.Func) bool {
   650  	return ir.Any(fn, func(n ir.Node) bool {
   651  		// TODO(rsc): No methods?
   652  		op := n.Op()
   653  		return op == ir.OCALL || op == ir.OCALLFUNC
   654  	})
   655  }
   656  
   657  // eqfield returns the node
   658  // 	p.field == q.field
   659  func eqfield(p ir.Node, q ir.Node, field *types.Sym) ir.Node {
   660  	nx := ir.NewSelectorExpr(base.Pos, ir.OXDOT, p, field)
   661  	ny := ir.NewSelectorExpr(base.Pos, ir.OXDOT, q, field)
   662  	ne := ir.NewBinaryExpr(base.Pos, ir.OEQ, nx, ny)
   663  	return ne
   664  }
   665  
   666  // EqString returns the nodes
   667  //   len(s) == len(t)
   668  // and
   669  //   memequal(s.ptr, t.ptr, len(s))
   670  // which can be used to construct string equality comparison.
   671  // eqlen must be evaluated before eqmem, and shortcircuiting is required.
   672  func EqString(s, t ir.Node) (eqlen *ir.BinaryExpr, eqmem *ir.CallExpr) {
   673  	s = typecheck.Conv(s, types.Types[types.TSTRING])
   674  	t = typecheck.Conv(t, types.Types[types.TSTRING])
   675  	sptr := ir.NewUnaryExpr(base.Pos, ir.OSPTR, s)
   676  	tptr := ir.NewUnaryExpr(base.Pos, ir.OSPTR, t)
   677  	slen := typecheck.Conv(ir.NewUnaryExpr(base.Pos, ir.OLEN, s), types.Types[types.TUINTPTR])
   678  	tlen := typecheck.Conv(ir.NewUnaryExpr(base.Pos, ir.OLEN, t), types.Types[types.TUINTPTR])
   679  
   680  	fn := typecheck.LookupRuntime("memequal")
   681  	fn = typecheck.SubstArgTypes(fn, types.Types[types.TUINT8], types.Types[types.TUINT8])
   682  	call := ir.NewCallExpr(base.Pos, ir.OCALL, fn, []ir.Node{sptr, tptr, ir.Copy(slen)})
   683  	typecheck.Call(call)
   684  
   685  	cmp := ir.NewBinaryExpr(base.Pos, ir.OEQ, slen, tlen)
   686  	cmp = typecheck.Expr(cmp).(*ir.BinaryExpr)
   687  	cmp.SetType(types.Types[types.TBOOL])
   688  	return cmp, call
   689  }
   690  
   691  // EqInterface returns the nodes
   692  //   s.tab == t.tab (or s.typ == t.typ, as appropriate)
   693  // and
   694  //   ifaceeq(s.tab, s.data, t.data) (or efaceeq(s.typ, s.data, t.data), as appropriate)
   695  // which can be used to construct interface equality comparison.
   696  // eqtab must be evaluated before eqdata, and shortcircuiting is required.
   697  func EqInterface(s, t ir.Node) (eqtab *ir.BinaryExpr, eqdata *ir.CallExpr) {
   698  	if !types.Identical(s.Type(), t.Type()) {
   699  		base.Fatalf("EqInterface %v %v", s.Type(), t.Type())
   700  	}
   701  	// func ifaceeq(tab *uintptr, x, y unsafe.Pointer) (ret bool)
   702  	// func efaceeq(typ *uintptr, x, y unsafe.Pointer) (ret bool)
   703  	var fn ir.Node
   704  	if s.Type().IsEmptyInterface() {
   705  		fn = typecheck.LookupRuntime("efaceeq")
   706  	} else {
   707  		fn = typecheck.LookupRuntime("ifaceeq")
   708  	}
   709  
   710  	stab := ir.NewUnaryExpr(base.Pos, ir.OITAB, s)
   711  	ttab := ir.NewUnaryExpr(base.Pos, ir.OITAB, t)
   712  	sdata := ir.NewUnaryExpr(base.Pos, ir.OIDATA, s)
   713  	tdata := ir.NewUnaryExpr(base.Pos, ir.OIDATA, t)
   714  	sdata.SetType(types.Types[types.TUNSAFEPTR])
   715  	tdata.SetType(types.Types[types.TUNSAFEPTR])
   716  	sdata.SetTypecheck(1)
   717  	tdata.SetTypecheck(1)
   718  
   719  	call := ir.NewCallExpr(base.Pos, ir.OCALL, fn, []ir.Node{stab, sdata, tdata})
   720  	typecheck.Call(call)
   721  
   722  	cmp := ir.NewBinaryExpr(base.Pos, ir.OEQ, stab, ttab)
   723  	cmp = typecheck.Expr(cmp).(*ir.BinaryExpr)
   724  	cmp.SetType(types.Types[types.TBOOL])
   725  	return cmp, call
   726  }
   727  
   728  // eqmem returns the node
   729  // 	memequal(&p.field, &q.field [, size])
   730  func eqmem(p ir.Node, q ir.Node, field *types.Sym, size int64) ir.Node {
   731  	nx := typecheck.Expr(typecheck.NodAddr(ir.NewSelectorExpr(base.Pos, ir.OXDOT, p, field)))
   732  	ny := typecheck.Expr(typecheck.NodAddr(ir.NewSelectorExpr(base.Pos, ir.OXDOT, q, field)))
   733  
   734  	fn, needsize := eqmemfunc(size, nx.Type().Elem())
   735  	call := ir.NewCallExpr(base.Pos, ir.OCALL, fn, nil)
   736  	call.Args.Append(nx)
   737  	call.Args.Append(ny)
   738  	if needsize {
   739  		call.Args.Append(ir.NewInt(size))
   740  	}
   741  
   742  	return call
   743  }
   744  
   745  func eqmemfunc(size int64, t *types.Type) (fn *ir.Name, needsize bool) {
   746  	switch size {
   747  	default:
   748  		fn = typecheck.LookupRuntime("memequal")
   749  		needsize = true
   750  	case 1, 2, 4, 8, 16:
   751  		buf := fmt.Sprintf("memequal%d", int(size)*8)
   752  		fn = typecheck.LookupRuntime(buf)
   753  	}
   754  
   755  	fn = typecheck.SubstArgTypes(fn, t, t)
   756  	return fn, needsize
   757  }
   758  
   759  // memrun finds runs of struct fields for which memory-only algs are appropriate.
   760  // t is the parent struct type, and start is the field index at which to start the run.
   761  // size is the length in bytes of the memory included in the run.
   762  // next is the index just after the end of the memory run.
   763  func memrun(t *types.Type, start int) (size int64, next int) {
   764  	next = start
   765  	for {
   766  		next++
   767  		if next == t.NumFields() {
   768  			break
   769  		}
   770  		// Stop run after a padded field.
   771  		if types.IsPaddedField(t, next-1) {
   772  			break
   773  		}
   774  		// Also, stop before a blank or non-memory field.
   775  		if f := t.Field(next); f.Sym.IsBlank() || !isRegularMemory(f.Type) {
   776  			break
   777  		}
   778  		// For issue 46283, don't combine fields if the resulting load would
   779  		// require a larger alignment than the component fields.
   780  		if base.Ctxt.Arch.Alignment > 1 {
   781  			align := t.Alignment()
   782  			if off := t.Field(start).Offset; off&(align-1) != 0 {
   783  				// Offset is less aligned than the containing type.
   784  				// Use offset to determine alignment.
   785  				align = 1 << uint(bits.TrailingZeros64(uint64(off)))
   786  			}
   787  			size := t.Field(next).End() - t.Field(start).Offset
   788  			if size > align {
   789  				break
   790  			}
   791  		}
   792  	}
   793  	return t.Field(next-1).End() - t.Field(start).Offset, next
   794  }
   795  
   796  func hashmem(t *types.Type) ir.Node {
   797  	sym := ir.Pkgs.Runtime.Lookup("memhash")
   798  
   799  	// TODO(austin): This creates an ir.Name with a nil Func.
   800  	n := typecheck.NewName(sym)
   801  	ir.MarkFunc(n)
   802  	n.SetType(types.NewSignature(types.NoPkg, nil, nil, []*types.Field{
   803  		types.NewField(base.Pos, nil, types.NewPtr(t)),
   804  		types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
   805  		types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
   806  	}, []*types.Field{
   807  		types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
   808  	}))
   809  	return n
   810  }
   811
View as plain text