alg.go

     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.Size() {
    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.Size() {
    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.Size()))
   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.Size())) // 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.Size()))
   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.Size()))
   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 := typecheck.Call(base.Pos, fn, []ir.Node{sptr, tptr, ir.Copy(slen)}, false).(*ir.CallExpr)
   683  
   684  	cmp := ir.NewBinaryExpr(base.Pos, ir.OEQ, slen, tlen)
   685  	cmp = typecheck.Expr(cmp).(*ir.BinaryExpr)
   686  	cmp.SetType(types.Types[types.TBOOL])
   687  	return cmp, call
   688  }
   689  
   690  // EqInterface returns the nodes
   691  //   s.tab == t.tab (or s.typ == t.typ, as appropriate)
   692  // and
   693  //   ifaceeq(s.tab, s.data, t.data) (or efaceeq(s.typ, s.data, t.data), as appropriate)
   694  // which can be used to construct interface equality comparison.
   695  // eqtab must be evaluated before eqdata, and shortcircuiting is required.
   696  func EqInterface(s, t ir.Node) (eqtab *ir.BinaryExpr, eqdata *ir.CallExpr) {
   697  	if !types.Identical(s.Type(), t.Type()) {
   698  		base.Fatalf("EqInterface %v %v", s.Type(), t.Type())
   699  	}
   700  	// func ifaceeq(tab *uintptr, x, y unsafe.Pointer) (ret bool)
   701  	// func efaceeq(typ *uintptr, x, y unsafe.Pointer) (ret bool)
   702  	var fn ir.Node
   703  	if s.Type().IsEmptyInterface() {
   704  		fn = typecheck.LookupRuntime("efaceeq")
   705  	} else {
   706  		fn = typecheck.LookupRuntime("ifaceeq")
   707  	}
   708  
   709  	stab := ir.NewUnaryExpr(base.Pos, ir.OITAB, s)
   710  	ttab := ir.NewUnaryExpr(base.Pos, ir.OITAB, t)
   711  	sdata := ir.NewUnaryExpr(base.Pos, ir.OIDATA, s)
   712  	tdata := ir.NewUnaryExpr(base.Pos, ir.OIDATA, t)
   713  	sdata.SetType(types.Types[types.TUNSAFEPTR])
   714  	tdata.SetType(types.Types[types.TUNSAFEPTR])
   715  	sdata.SetTypecheck(1)
   716  	tdata.SetTypecheck(1)
   717  
   718  	call := typecheck.Call(base.Pos, fn, []ir.Node{stab, sdata, tdata}, false).(*ir.CallExpr)
   719  
   720  	cmp := ir.NewBinaryExpr(base.Pos, ir.OEQ, stab, ttab)
   721  	cmp = typecheck.Expr(cmp).(*ir.BinaryExpr)
   722  	cmp.SetType(types.Types[types.TBOOL])
   723  	return cmp, call
   724  }
   725  
   726  // eqmem returns the node
   727  // 	memequal(&p.field, &q.field [, size])
   728  func eqmem(p ir.Node, q ir.Node, field *types.Sym, size int64) ir.Node {
   729  	nx := typecheck.Expr(typecheck.NodAddr(ir.NewSelectorExpr(base.Pos, ir.OXDOT, p, field)))
   730  	ny := typecheck.Expr(typecheck.NodAddr(ir.NewSelectorExpr(base.Pos, ir.OXDOT, q, field)))
   731  
   732  	fn, needsize := eqmemfunc(size, nx.Type().Elem())
   733  	call := ir.NewCallExpr(base.Pos, ir.OCALL, fn, nil)
   734  	call.Args.Append(nx)
   735  	call.Args.Append(ny)
   736  	if needsize {
   737  		call.Args.Append(ir.NewInt(size))
   738  	}
   739  
   740  	return call
   741  }
   742  
   743  func eqmemfunc(size int64, t *types.Type) (fn *ir.Name, needsize bool) {
   744  	switch size {
   745  	default:
   746  		fn = typecheck.LookupRuntime("memequal")
   747  		needsize = true
   748  	case 1, 2, 4, 8, 16:
   749  		buf := fmt.Sprintf("memequal%d", int(size)*8)
   750  		fn = typecheck.LookupRuntime(buf)
   751  	}
   752  
   753  	fn = typecheck.SubstArgTypes(fn, t, t)
   754  	return fn, needsize
   755  }
   756  
   757  // memrun finds runs of struct fields for which memory-only algs are appropriate.
   758  // t is the parent struct type, and start is the field index at which to start the run.
   759  // size is the length in bytes of the memory included in the run.
   760  // next is the index just after the end of the memory run.
   761  func memrun(t *types.Type, start int) (size int64, next int) {
   762  	next = start
   763  	for {
   764  		next++
   765  		if next == t.NumFields() {
   766  			break
   767  		}
   768  		// Stop run after a padded field.
   769  		if types.IsPaddedField(t, next-1) {
   770  			break
   771  		}
   772  		// Also, stop before a blank or non-memory field.
   773  		if f := t.Field(next); f.Sym.IsBlank() || !isRegularMemory(f.Type) {
   774  			break
   775  		}
   776  		// For issue 46283, don't combine fields if the resulting load would
   777  		// require a larger alignment than the component fields.
   778  		if base.Ctxt.Arch.Alignment > 1 {
   779  			align := t.Alignment()
   780  			if off := t.Field(start).Offset; off&(align-1) != 0 {
   781  				// Offset is less aligned than the containing type.
   782  				// Use offset to determine alignment.
   783  				align = 1 << uint(bits.TrailingZeros64(uint64(off)))
   784  			}
   785  			size := t.Field(next).End() - t.Field(start).Offset
   786  			if size > align {
   787  				break
   788  			}
   789  		}
   790  	}
   791  	return t.Field(next-1).End() - t.Field(start).Offset, next
   792  }
   793  
   794  func hashmem(t *types.Type) ir.Node {
   795  	sym := ir.Pkgs.Runtime.Lookup("memhash")
   796  
   797  	// TODO(austin): This creates an ir.Name with a nil Func.
   798  	n := typecheck.NewName(sym)
   799  	ir.MarkFunc(n)
   800  	n.SetType(types.NewSignature(types.NoPkg, nil, nil, []*types.Field{
   801  		types.NewField(base.Pos, nil, types.NewPtr(t)),
   802  		types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
   803  		types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
   804  	}, []*types.Field{
   805  		types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
   806  	}))
   807  	return n
   808  }
   809
View as plain text