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  	"go/constant"
    10  	"strconv"
    11  	"strings"
    12  
    13  	"cmd/compile/internal/base"
    14  	"cmd/compile/internal/ir"
    15  	"cmd/compile/internal/objw"
    16  	"cmd/compile/internal/typecheck"
    17  	"cmd/compile/internal/types"
    18  	"cmd/internal/obj"
    19  )
    20  
    21  // genhash returns a symbol which is the closure used to compute
    22  // the hash of a value of type t.
    23  func genhash(t *types.Type) *obj.LSym {
    24  	return genhashSig(eqSignature(t))
    25  }
    26  
    27  func genhashSig(sig string) *obj.LSym {
    28  	if len(sig) > 0 && sig[0] == sigAlign {
    29  		_, sig = parseNum(sig[1:])
    30  	}
    31  	switch sig {
    32  	case "":
    33  		return sysClosure("memhash0")
    34  	case string(sigMemory) + "1":
    35  		return sysClosure("memhash8")
    36  	case string(sigMemory) + "2":
    37  		return sysClosure("memhash16")
    38  	case string(sigMemory) + "4":
    39  		return sysClosure("memhash32")
    40  	case string(sigMemory) + "8":
    41  		return sysClosure("memhash64")
    42  	case string(sigMemory) + "16":
    43  		return sysClosure("memhash128")
    44  	case string(sigString):
    45  		return sysClosure("strhash")
    46  	case string(sigIface):
    47  		return sysClosure("interhash")
    48  	case string(sigEface):
    49  		return sysClosure("nilinterhash")
    50  	case string(sigFloat32):
    51  		return sysClosure("f32hash")
    52  	case string(sigFloat64):
    53  		return sysClosure("f64hash")
    54  	case string(sigFloat32) + string(sigFloat32):
    55  		return sysClosure("c64hash")
    56  	case string(sigFloat64) + string(sigFloat64):
    57  		return sysClosure("c128hash")
    58  	}
    59  
    60  	closure := TypeLinksymLookup(".hashfunc." + sig)
    61  	if len(closure.P) > 0 { // already generated
    62  		return closure
    63  	}
    64  
    65  	if sig[0] == sigMemory {
    66  		n, rest := parseNum(sig[1:])
    67  		if rest == "" {
    68  			// Just M%d. We can make a memhash_varlen closure.
    69  			// The size of the memory region to hash is encoded in the closure.
    70  			if memhashvarlen == nil {
    71  				memhashvarlen = typecheck.LookupRuntimeFunc("memhash_varlen")
    72  			}
    73  			ot := 0
    74  			ot = objw.SymPtr(closure, ot, memhashvarlen, 0)
    75  			ot = objw.Uintptr(closure, ot, uint64(n)) // size encoded in closue
    76  			objw.Global(closure, int32(ot), obj.DUPOK|obj.RODATA)
    77  			return closure
    78  		}
    79  	}
    80  
    81  	if base.Flag.LowerR != 0 {
    82  		fmt.Printf("genhash %s\n", sig)
    83  	}
    84  
    85  	fn := hashFunc(sig)
    86  
    87  	// Build closure. It doesn't close over any variables, so
    88  	// it contains just the function pointer.
    89  	objw.SymPtr(closure, 0, fn.Linksym(), 0)
    90  	objw.Global(closure, int32(types.PtrSize), obj.DUPOK|obj.RODATA)
    91  	return closure
    92  }
    93  
    94  func hashFunc(sig string) *ir.Func {
    95  	sym := types.TypeSymLookup(".hash." + sig)
    96  	if sym.Def != nil {
    97  		return sym.Def.(*ir.Name).Func
    98  	}
    99  
   100  	pos := base.AutogeneratedPos // less confusing than end of input
   101  	base.Pos = pos
   102  
   103  	// func sym(p unsafe.Pointer, h uintptr) uintptr
   104  	fn := ir.NewFunc(pos, pos, sym, types.NewSignature(nil,
   105  		[]*types.Field{
   106  			types.NewField(pos, typecheck.Lookup("p"), types.Types[types.TUNSAFEPTR]),
   107  			types.NewField(pos, typecheck.Lookup("h"), types.Types[types.TUINTPTR]),
   108  		},
   109  		[]*types.Field{
   110  			types.NewField(pos, nil, types.Types[types.TUINTPTR]),
   111  		},
   112  	))
   113  	sym.Def = fn.Nname
   114  	fn.Pragma |= ir.Noinline // TODO(mdempsky): We need to emit this during the unified frontend instead, to allow inlining.
   115  	typecheck.DeclFunc(fn)
   116  	np := fn.Dcl[0]
   117  	nh := fn.Dcl[1]
   118  
   119  	// Skip alignment, hash functions can handle unaligned data.
   120  	if len(sig) > 0 && sig[0] == sigAlign {
   121  		_, sig = parseNum(sig[1:])
   122  	}
   123  
   124  	// offset from np that we're currently working on
   125  	var off int64
   126  
   127  	// Return np+off (as an unsafe.Pointer).
   128  	ptr := func() ir.Node {
   129  		c := ir.NewBasicLit(pos, types.Types[types.TUINTPTR], constant.MakeInt64(off))
   130  		return ir.NewBinaryExpr(pos, ir.OUNSAFEADD, np, c)
   131  	}
   132  	// hash data using function name at np+off.
   133  	// Increment off by size.
   134  	hash := func(name string, size int64) {
   135  		p := ptr()
   136  		hashFn := typecheck.LookupRuntime(name)
   137  		call := ir.NewCallExpr(pos, ir.OCALL, hashFn, []ir.Node{p, nh})
   138  		fn.Body.Append(ir.NewAssignStmt(pos, nh, call))
   139  		off += size
   140  	}
   141  
   142  	for len(sig) > 0 {
   143  		kind := sig[0]
   144  		sig = sig[1:]
   145  		switch kind {
   146  		case sigMemory:
   147  			var n int64
   148  			n, sig = parseNum(sig)
   149  			switch {
   150  			case n == 4:
   151  				p := ptr()
   152  				memhash := typecheck.LookupRuntime("memhash32")
   153  				call := ir.NewCallExpr(pos, ir.OCALL, memhash, []ir.Node{p, nh})
   154  				fn.Body.Append(ir.NewAssignStmt(pos, nh, call))
   155  			case n == 8:
   156  				p := ptr()
   157  				memhash := typecheck.LookupRuntime("memhash64")
   158  				call := ir.NewCallExpr(pos, ir.OCALL, memhash, []ir.Node{p, nh})
   159  				fn.Body.Append(ir.NewAssignStmt(pos, nh, call))
   160  			default:
   161  				p := ptr()
   162  				memhash := typecheck.LookupRuntime("memhash")
   163  				size := ir.NewBasicLit(pos, types.Types[types.TUINTPTR], constant.MakeInt64(n))
   164  				call := ir.NewCallExpr(pos, ir.OCALL, memhash, []ir.Node{p, nh, size})
   165  				fn.Body.Append(ir.NewAssignStmt(pos, nh, call))
   166  			}
   167  			off += n
   168  		case sigFloat32:
   169  			hash("f32hash", 4)
   170  		case sigFloat64:
   171  			hash("f64hash", 8)
   172  		case sigString:
   173  			hash("strhash", 2*int64(types.PtrSize))
   174  		case sigEface:
   175  			hash("nilinterhash", 2*int64(types.PtrSize))
   176  		case sigIface:
   177  			hash("interhash", 2*int64(types.PtrSize))
   178  		case sigSkip:
   179  			var n int64
   180  			n, sig = parseNum(sig)
   181  			off += n
   182  		case sigArrayStart:
   183  			var n int64
   184  			var elemSig string
   185  			n, elemSig, sig = parseArray(sig)
   186  			elemSize := sigSize(elemSig)
   187  
   188  			// Loop N times, calling hash function for the element.
   189  			//     for i := off; i < off + N*elemSize; i += elemSize {
   190  			//         h = elemfn(p+i, h)
   191  			//     }
   192  			elemFn := hashFunc(elemSig).Nname
   193  			idx := typecheck.TempAt(pos, ir.CurFunc, types.Types[types.TUINTPTR])
   194  			init := ir.NewAssignStmt(pos, idx, ir.NewInt(pos, off))
   195  			cond := ir.NewBinaryExpr(pos, ir.OLT, idx, ir.NewInt(pos, off+n*elemSize))
   196  			post := ir.NewAssignStmt(pos, idx, ir.NewBinaryExpr(pos, ir.OADD, idx, ir.NewInt(pos, elemSize)))
   197  
   198  			p := ir.NewBinaryExpr(pos, ir.OUNSAFEADD, np, idx)
   199  			call := typecheck.Call(pos, elemFn, []ir.Node{p, nh}, false)
   200  			as := ir.NewAssignStmt(pos, nh, call)
   201  			loop := ir.NewForStmt(pos, init, cond, post, []ir.Node{as}, false)
   202  			fn.Body.Append(loop)
   203  			off += n * elemSize
   204  		}
   205  	}
   206  
   207  	fn.Body.Append(ir.NewReturnStmt(pos, []ir.Node{nh}))
   208  
   209  	if base.Flag.LowerR != 0 {
   210  		ir.DumpList("genhash body", fn.Body)
   211  	}
   212  
   213  	typecheck.FinishFuncBody()
   214  
   215  	fn.SetDupok(true)
   216  
   217  	ir.WithFunc(fn, func() {
   218  		typecheck.Stmts(fn.Body)
   219  	})
   220  
   221  	fn.SetNilCheckDisabled(true)
   222  	return fn
   223  }
   224  
   225  // sysClosure returns a closure which will call the
   226  // given runtime function (with no closed-over variables).
   227  func sysClosure(name string) *obj.LSym {
   228  	s := typecheck.LookupRuntimeVar(name + "·f")
   229  	if len(s.P) == 0 {
   230  		f := typecheck.LookupRuntimeFunc(name)
   231  		objw.SymPtr(s, 0, f, 0)
   232  		objw.Global(s, int32(types.PtrSize), obj.DUPOK|obj.RODATA)
   233  	}
   234  	return s
   235  }
   236  
   237  // geneq returns a symbol which is the closure used to compute
   238  // equality for two objects of type t.
   239  func geneq(t *types.Type) *obj.LSym {
   240  	switch types.AlgType(t) {
   241  	case types.ANOEQ, types.ANOALG:
   242  		// The runtime will panic if it tries to compare
   243  		// a type with a nil equality function.
   244  		return nil
   245  	}
   246  	return geneqSig(eqSignature(t))
   247  }
   248  
   249  // geneqSig returns a symbol which is the closure used to compute
   250  // equality for two objects with equality signature sig.
   251  func geneqSig(sig string) *obj.LSym {
   252  	align := int64(types.PtrSize)
   253  	if len(sig) > 0 && sig[0] == sigAlign {
   254  		align, sig = parseNum(sig[1:])
   255  	}
   256  	if base.Ctxt.Arch.CanMergeLoads {
   257  		align = 8
   258  	}
   259  	switch sig {
   260  	case "":
   261  		return sysClosure("memequal0")
   262  	case string(sigMemory) + "1":
   263  		return sysClosure("memequal8")
   264  	case string(sigMemory) + "2":
   265  		if align >= 2 {
   266  			return sysClosure("memequal16")
   267  		}
   268  	case string(sigMemory) + "4":
   269  		if align >= 4 {
   270  			return sysClosure("memequal32")
   271  		}
   272  	case string(sigMemory) + "8":
   273  		if align >= 8 {
   274  			return sysClosure("memequal64")
   275  		}
   276  	case string(sigMemory) + "16":
   277  		if align >= 8 {
   278  			return sysClosure("memequal128")
   279  		}
   280  	case string(sigString):
   281  		return sysClosure("strequal")
   282  	case string(sigIface):
   283  		return sysClosure("interequal")
   284  	case string(sigEface):
   285  		return sysClosure("nilinterequal")
   286  	case string(sigFloat32):
   287  		return sysClosure("f32equal")
   288  	case string(sigFloat64):
   289  		return sysClosure("f64equal")
   290  	case string(sigFloat32) + string(sigFloat32):
   291  		return sysClosure("c64equal")
   292  	case string(sigFloat64) + string(sigFloat64):
   293  		return sysClosure("c128equal")
   294  	}
   295  
   296  	closure := TypeLinksymLookup(".eqfunc." + sig)
   297  	if len(closure.P) > 0 { // already generated
   298  		return closure
   299  	}
   300  
   301  	if sig[0] == sigMemory {
   302  		n, rest := parseNum(sig[1:])
   303  		if rest == "" {
   304  			// Just M%d. We can make a memequal_varlen closure.
   305  			// The size of the memory region to compare is encoded in the closure.
   306  			if memequalvarlen == nil {
   307  				memequalvarlen = typecheck.LookupRuntimeFunc("memequal_varlen")
   308  			}
   309  			ot := 0
   310  			ot = objw.SymPtr(closure, ot, memequalvarlen, 0)
   311  			ot = objw.Uintptr(closure, ot, uint64(n))
   312  			objw.Global(closure, int32(ot), obj.DUPOK|obj.RODATA)
   313  			return closure
   314  		}
   315  	}
   316  
   317  	if base.Flag.LowerR != 0 {
   318  		fmt.Printf("geneqSig %s\n", sig)
   319  	}
   320  
   321  	fn := eqFunc(sig)
   322  
   323  	// Generate a closure which points at the function we just generated.
   324  	objw.SymPtr(closure, 0, fn.Linksym(), 0)
   325  	objw.Global(closure, int32(types.PtrSize), obj.DUPOK|obj.RODATA)
   326  	return closure
   327  }
   328  
   329  func eqFunc(sig string) *ir.Func {
   330  	sym := types.TypeSymLookup(".eq." + sig)
   331  	if sym.Def != nil {
   332  		return sym.Def.(*ir.Name).Func
   333  	}
   334  
   335  	pos := base.AutogeneratedPos // less confusing than end of input
   336  	base.Pos = pos
   337  
   338  	// func sym(p, q unsafe.Pointer) bool
   339  	fn := ir.NewFunc(pos, pos, sym, types.NewSignature(nil,
   340  		[]*types.Field{
   341  			types.NewField(pos, typecheck.Lookup("p"), types.Types[types.TUNSAFEPTR]),
   342  			types.NewField(pos, typecheck.Lookup("q"), types.Types[types.TUNSAFEPTR]),
   343  		},
   344  		[]*types.Field{
   345  			types.NewField(pos, typecheck.Lookup("r"), types.Types[types.TBOOL]),
   346  		},
   347  	))
   348  	sym.Def = fn.Nname
   349  	fn.Pragma |= ir.Noinline // TODO(mdempsky): We need to emit this during the unified frontend instead, to allow inlining.
   350  	typecheck.DeclFunc(fn)
   351  	np := fn.Dcl[0]
   352  	nq := fn.Dcl[1]
   353  	nr := fn.Dcl[2]
   354  
   355  	// Label to jump to if an equality test fails.
   356  	neq := typecheck.AutoLabel(".neq")
   357  
   358  	// Grab known alignment of argument pointers. (ptrSize is the default.)
   359  	align := int64(types.PtrSize)
   360  	if len(sig) > 0 && sig[0] == sigAlign {
   361  		sig = sig[1:]
   362  		align, sig = parseNum(sig)
   363  	}
   364  	unalignedOk := base.Ctxt.Arch.CanMergeLoads
   365  
   366  	// offset from np/nq that we're currently working on
   367  	var off int64
   368  	var hasCall bool
   369  
   370  	// test takes a boolean. If it evaluates to false, short circuit
   371  	// and return false immediately. Otherwise, keep checking.
   372  	var lastTest ir.Node
   373  	test := func(eq ir.Node) {
   374  		// Buffer one test in lastTest so we can use the
   375  		// last one as the return value.
   376  		if lastTest != nil {
   377  			nif := ir.NewIfStmt(pos, lastTest, nil, []ir.Node{ir.NewBranchStmt(pos, ir.OGOTO, neq)})
   378  			fn.Body.Append(nif)
   379  		}
   380  		lastTest = eq
   381  	}
   382  	// load loads data of type t from np+off and nq+off.
   383  	// Increments off by the size of t.
   384  	load := func(t *types.Type) (ir.Node, ir.Node) {
   385  		c := ir.NewBasicLit(pos, types.Types[types.TUINTPTR], constant.MakeInt64(off))
   386  		p := ir.NewBinaryExpr(pos, ir.OUNSAFEADD, np, c)
   387  		q := ir.NewBinaryExpr(pos, ir.OUNSAFEADD, nq, c)
   388  		x := ir.NewStarExpr(pos, ir.NewConvExpr(pos, ir.OCONVNOP, t.PtrTo(), p))
   389  		y := ir.NewStarExpr(pos, ir.NewConvExpr(pos, ir.OCONVNOP, t.PtrTo(), q))
   390  		off += t.Size()
   391  		return x, y
   392  	}
   393  	// compare compares x and y and jumps to neq if they are not equal.
   394  	compare := func(x, y ir.Node) {
   395  		test(ir.NewBinaryExpr(pos, ir.OEQ, x, y))
   396  	}
   397  
   398  	// We keep track of string contents that we don't compare immediately.
   399  	// We delay comparing string contents because they might be large and
   400  	// we'd rather compare scalars farther along in the signature first.
   401  	var pendingStrings []int64
   402  	flushStrings := func() {
   403  		defer func(saveOff int64) {
   404  			off = saveOff
   405  		}(off)
   406  		for _, x := range pendingStrings {
   407  			off = x
   408  			ptrA, ptrB := load(types.Types[types.TUNSAFEPTR])
   409  			len, _ := load(types.Types[types.TUINTPTR])
   410  			// Note: we already checked that the lengths are equal.
   411  			memeq := typecheck.LookupRuntime("memequal")
   412  			test(typecheck.Call(pos, memeq, []ir.Node{ptrA, ptrB, len}, false))
   413  			hasCall = true
   414  		}
   415  		pendingStrings = pendingStrings[:0]
   416  	}
   417  
   418  	for len(sig) > 0 {
   419  		kind := sig[0]
   420  		sig = sig[1:]
   421  		switch kind {
   422  		case sigMemory:
   423  			var n int64
   424  			n, sig = parseNum(sig)
   425  			if n > 64 { // TODO: why 64?
   426  				// For big regions, call memequal.
   427  				c := ir.NewBasicLit(pos, types.Types[types.TUINTPTR], constant.MakeInt64(off))
   428  				p := ir.NewBinaryExpr(pos, ir.OUNSAFEADD, np, c)
   429  				q := ir.NewBinaryExpr(pos, ir.OUNSAFEADD, nq, c)
   430  				len := ir.NewBasicLit(pos, types.Types[types.TUINTPTR], constant.MakeInt64(n))
   431  				memeq := typecheck.LookupRuntime("memequal")
   432  				test(typecheck.Call(pos, memeq, []ir.Node{p, q, len}, false))
   433  				hasCall = true
   434  				off += n
   435  				n = 0
   436  			}
   437  			n0 := n
   438  			for n != 0 {
   439  				switch {
   440  				case n >= 8 && (unalignedOk || align >= 8 && off%8 == 0):
   441  					compare(load(types.Types[types.TUINT64]))
   442  					n -= 8
   443  				case (n == 5 || n == 6 || n == 7) && unalignedOk && n0 >= 8:
   444  					off -= 8 - n
   445  					compare(load(types.Types[types.TUINT64]))
   446  					n = 0
   447  				case n >= 4 && (unalignedOk || align >= 4 && off%4 == 0):
   448  					compare(load(types.Types[types.TUINT32]))
   449  					n -= 4
   450  				case n == 3 && unalignedOk && n0 >= 4:
   451  					off--
   452  					compare(load(types.Types[types.TUINT32]))
   453  					n = 0
   454  				case n >= 2 && (unalignedOk || align >= 2 && off%2 == 0):
   455  					compare(load(types.Types[types.TUINT16]))
   456  					n -= 2
   457  				default:
   458  					compare(load(types.Types[types.TUINT8]))
   459  					n--
   460  				}
   461  			}
   462  		case sigFloat32:
   463  			compare(load(types.Types[types.TFLOAT32]))
   464  		case sigFloat64:
   465  			compare(load(types.Types[types.TFLOAT64]))
   466  		case sigString:
   467  			// Compare just the lengths right now.
   468  			// Save the contents for later.
   469  			pendingStrings = append(pendingStrings, off)
   470  			off += int64(types.PtrSize)
   471  			compare(load(types.Types[types.TUINTPTR]))
   472  		case sigEface, sigIface:
   473  			// flushStrings here to ensure that we only get a panic from
   474  			// this interface test if all previous equality checks pass.
   475  			flushStrings()
   476  			typeX, typeY := load(types.Types[types.TUINTPTR].PtrTo())
   477  			compare(typeX, typeY)
   478  			dataX, dataY := load(types.Types[types.TUNSAFEPTR])
   479  			var eqFn *ir.Name
   480  			if kind == sigEface {
   481  				eqFn = typecheck.LookupRuntime("efaceeq")
   482  			} else {
   483  				eqFn = typecheck.LookupRuntime("ifaceeq")
   484  			}
   485  			test(typecheck.Call(pos, eqFn, []ir.Node{typeX, dataX, dataY}, false))
   486  			hasCall = true
   487  		case sigSkip:
   488  			var n int64
   489  			n, sig = parseNum(sig)
   490  			off += n
   491  		case sigArrayStart:
   492  			// Flush any pending test.
   493  			flushStrings()
   494  			// TODO: if the element comparison can't panic (no E or I), then
   495  			// maybe we don't need to do this flushStrings?
   496  			// On the other hand, maybe the unflushed string is not equal, but
   497  			// a big following array is all equal.
   498  			if lastTest != nil {
   499  				nif := ir.NewIfStmt(pos, lastTest, nil, []ir.Node{ir.NewBranchStmt(pos, ir.OGOTO, neq)})
   500  				fn.Body.Append(nif)
   501  				lastTest = nil
   502  			}
   503  
   504  			var n int64
   505  			var elemSig string
   506  			n, elemSig, sig = parseArray(sig)
   507  			elemSize := sigSize(elemSig)
   508  
   509  			// Loop N times, calling comparison function for the element.
   510  			//     for i := off; i < off + N*elemSize; i += elemSize {
   511  			//         if !eqfn(p+i, q+i) { goto neq }
   512  			//     }
   513  			elemFn := eqFunc(sigTrimSkip(elemSig)).Nname
   514  			idx := typecheck.TempAt(pos, ir.CurFunc, types.Types[types.TUINTPTR])
   515  			init := ir.NewAssignStmt(pos, idx, ir.NewInt(pos, off))
   516  			cond := ir.NewBinaryExpr(pos, ir.OLT, idx, ir.NewInt(pos, off+n*elemSize))
   517  			post := ir.NewAssignStmt(pos, idx, ir.NewBinaryExpr(pos, ir.OADD, idx, ir.NewInt(pos, elemSize)))
   518  
   519  			p := ir.NewBinaryExpr(pos, ir.OUNSAFEADD, np, idx)
   520  			q := ir.NewBinaryExpr(pos, ir.OUNSAFEADD, nq, idx)
   521  			call := typecheck.Call(pos, elemFn, []ir.Node{p, q}, false)
   522  			nif := ir.NewIfStmt(pos, call, nil, []ir.Node{ir.NewBranchStmt(pos, ir.OGOTO, neq)})
   523  			loop := ir.NewForStmt(pos, init, cond, post, []ir.Node{nif}, false)
   524  			fn.Body.Append(loop)
   525  			off += n * elemSize
   526  
   527  			// TODO: if the element comparison can't panic, but has strings
   528  			// in it, maybe we do a loop first without string contents and a
   529  			// second loop with string contents. There is no way to accomplish
   530  			// this now they way this code works (to call the equality
   531  			// function of the sub-signature).
   532  		}
   533  	}
   534  	// Flush any pending tests.
   535  	// The last test is used directly as a result (instead of branching using it).
   536  	flushStrings()
   537  	if lastTest == nil {
   538  		lastTest = ir.NewBool(pos, true)
   539  	}
   540  	as := ir.NewAssignStmt(pos, nr, lastTest)
   541  	fn.Body.Append(as)
   542  
   543  	// ret:
   544  	//   return
   545  	ret := typecheck.AutoLabel(".ret")
   546  	fn.Body.Append(ir.NewLabelStmt(pos, ret))
   547  	fn.Body.Append(ir.NewReturnStmt(pos, nil))
   548  
   549  	// neq:
   550  	//   r = false
   551  	//   return (or goto ret)
   552  	fn.Body.Append(ir.NewLabelStmt(pos, neq))
   553  	fn.Body.Append(ir.NewAssignStmt(pos, nr, ir.NewBool(pos, false)))
   554  	if hasCall {
   555  		// Epilogue is large, so share it with the equal case.
   556  		fn.Body.Append(ir.NewBranchStmt(pos, ir.OGOTO, ret))
   557  	} else {
   558  		// Epilogue is small, so don't bother sharing.
   559  		fn.Body.Append(ir.NewReturnStmt(pos, nil))
   560  	}
   561  	// TODO(khr): the epilogue size detection condition above isn't perfect.
   562  	// We should really do a generic CL that shares epilogues across
   563  	// the board. See #24936.
   564  
   565  	if base.Flag.LowerR != 0 {
   566  		ir.DumpList("geneq body", fn.Body)
   567  	}
   568  
   569  	typecheck.FinishFuncBody()
   570  
   571  	fn.SetDupok(true)
   572  
   573  	ir.WithFunc(fn, func() {
   574  		typecheck.Stmts(fn.Body)
   575  	})
   576  
   577  	// Disable checknils while compiling this code.
   578  	// We are comparing a struct or an array,
   579  	// neither of which can be nil, and our comparisons
   580  	// are shallow.
   581  	fn.SetNilCheckDisabled(true)
   582  	return fn
   583  }
   584  
   585  // EqFor returns ONAME node represents type t's equal function, and a boolean
   586  // to indicates whether a length needs to be passed when calling the function.
   587  func EqFor(t *types.Type) (ir.Node, bool) {
   588  	switch types.AlgType(t) {
   589  	case types.AMEM:
   590  		return typecheck.LookupRuntime("memequal"), true
   591  	case types.ASPECIAL:
   592  		fn := eqFunc(eqSignature(t))
   593  		return fn.Nname, false
   594  	}
   595  	base.Fatalf("EqFor %v", t)
   596  	return nil, false
   597  }
   598  
   599  // eqSignature returns a signature of the equality function for type t.
   600  // If two types have the same signature, they can use the same equality function.
   601  // The signature lists the comparisons that the equality function needs
   602  // to make, in order. So for instance, a type like:
   603  //
   604  //	type S struct {
   605  //	    i int32
   606  //	    j uint32
   607  //	    s string
   608  //	    e error
   609  //	}
   610  //
   611  // Will have the signature "M8SI".
   612  //
   613  //	M8 = 8 bytes of regular memory
   614  //	S = string
   615  //	I = nonempty interface
   616  //
   617  // The content of the signature is not intended for users. It is an
   618  // internal condensation of the comparison operations that need to be
   619  // performed.
   620  // (Although, note that these names might be seen in tracebacks where
   621  // the equality test panics due to incomparable interfaces.)
   622  //
   623  // Full signature spec:
   624  //
   625  //	M%d    = %d bytes of memory that should be compared directly
   626  //	K%d    = %d bytes of memory that should not be compared (sKip)
   627  //	F      = float32
   628  //	G      = float64
   629  //	S      = string
   630  //	I      = non-empty interface
   631  //	E      = empty interface
   632  //	[%d%s] = array: repeat signature %s %d times.
   633  //	A%d    = known alignment of type pointers (defaults to ptrSize)
   634  //
   635  // An alignment directive is only needed on platforms that can't do
   636  // unaligned loads.
   637  // If an alignment directive is present, it must be first.
   638  // Signatures can end early; a K%d is not required at the end.
   639  func eqSignature(t *types.Type) string {
   640  	var e eqSigBuilder
   641  	if !base.Ctxt.Arch.CanMergeLoads { // alignment only matters if we can't use unaligned loads
   642  		if a := t.Alignment(); a != int64(types.PtrSize) {
   643  			e.r.WriteString(fmt.Sprintf("%c%d", sigAlign, a))
   644  		}
   645  	}
   646  	e.build(t)
   647  	e.flush(true)
   648  	return e.r.String()
   649  }
   650  
   651  const (
   652  	sigMemory     = 'M' // followed by an integer number of bytes
   653  	sigSkip       = 'K' // followed by an integer number of bytes
   654  	sigFloat32    = 'F'
   655  	sigFloat64    = 'G'
   656  	sigString     = 'S'
   657  	sigIface      = 'I' // non-empty interface
   658  	sigEface      = 'E' // empty interface
   659  	sigArrayStart = '[' // followed by an iteration count, element signature, and sigArrayEnd
   660  	sigArrayEnd   = ']'
   661  	sigAlign      = 'A' // followed by an integer byte alignment
   662  )
   663  
   664  type eqSigBuilder struct {
   665  	r       strings.Builder
   666  	regMem  int64 // queued up region of regular memory
   667  	skipMem int64 // queued up region of memory to skip
   668  }
   669  
   670  func (e *eqSigBuilder) flush(atEnd bool) {
   671  	if e.regMem > 0 {
   672  		e.r.WriteString(fmt.Sprintf("%c%d", sigMemory, e.regMem))
   673  		e.regMem = 0
   674  	}
   675  	if e.skipMem > 0 {
   676  		if !atEnd {
   677  			e.r.WriteString(fmt.Sprintf("%c%d", sigSkip, e.skipMem))
   678  		}
   679  		e.skipMem = 0
   680  	}
   681  }
   682  func (e *eqSigBuilder) regular(n int64) {
   683  	if e.regMem == 0 {
   684  		e.flush(false)
   685  	}
   686  	e.regMem += n
   687  }
   688  func (e *eqSigBuilder) skip(n int64) {
   689  	if e.skipMem == 0 {
   690  		e.flush(false)
   691  	}
   692  	e.skipMem += n
   693  }
   694  func (e *eqSigBuilder) float32() {
   695  	e.flush(false)
   696  	e.r.WriteByte(sigFloat32)
   697  }
   698  func (e *eqSigBuilder) float64() {
   699  	e.flush(false)
   700  	e.r.WriteByte(sigFloat64)
   701  }
   702  func (e *eqSigBuilder) string() {
   703  	e.flush(false)
   704  	e.r.WriteByte(sigString)
   705  }
   706  func (e *eqSigBuilder) eface() {
   707  	e.flush(false)
   708  	e.r.WriteByte(sigEface)
   709  }
   710  func (e *eqSigBuilder) iface() {
   711  	e.flush(false)
   712  	e.r.WriteByte(sigIface)
   713  }
   714  
   715  func (e *eqSigBuilder) build(t *types.Type) {
   716  	switch t.Kind() {
   717  	case types.TINT8, types.TUINT8, types.TBOOL:
   718  		e.regular(1)
   719  	case types.TINT16, types.TUINT16:
   720  		e.regular(2)
   721  	case types.TINT32, types.TUINT32:
   722  		e.regular(4)
   723  	case types.TINT64, types.TUINT64:
   724  		e.regular(8)
   725  	case types.TINT, types.TUINT, types.TUINTPTR, types.TPTR, types.TUNSAFEPTR, types.TCHAN:
   726  		e.regular(int64(types.PtrSize))
   727  	case types.TFLOAT32:
   728  		e.float32()
   729  	case types.TFLOAT64:
   730  		e.float64()
   731  	case types.TCOMPLEX64:
   732  		e.float32()
   733  		e.float32()
   734  	case types.TCOMPLEX128:
   735  		e.float64()
   736  		e.float64()
   737  	case types.TSTRING:
   738  		e.string()
   739  	case types.TINTER:
   740  		if t.IsEmptyInterface() {
   741  			e.eface()
   742  		} else {
   743  			e.iface()
   744  		}
   745  	case types.TSTRUCT:
   746  		var off int64
   747  		for _, f := range t.Fields() {
   748  			if f.Sym.IsBlank() {
   749  				continue
   750  			}
   751  			if off < f.Offset {
   752  				e.skip(f.Offset - off)
   753  			}
   754  			e.build(f.Type)
   755  			off = f.Offset + f.Type.Size()
   756  		}
   757  		if off < t.Size() {
   758  			e.skip(t.Size() - off)
   759  		}
   760  	case types.TARRAY:
   761  		if types.AlgType(t) == types.AMEM {
   762  			// TODO: some "regular equality" types don't hit here,
   763  			// like [8]sync/atomic.Pointer. Figure out how to
   764  			// handle the subtle difference between "AMEM" and
   765  			// "can be compared byte-by-byte for equality".
   766  			e.regular(t.Size())
   767  			break
   768  		}
   769  		et := t.Elem()
   770  		n := t.NumElem()
   771  		switch n {
   772  		case 0:
   773  		case 1:
   774  			e.build(et)
   775  		default:
   776  			// To keep signatures small, we can't just repeat
   777  			// the element signature N times. Instead, we issue
   778  			// an array into the signature. Note that this can
   779  			// lead to a situation where two types which could
   780  			// share an equality function do not, like
   781  			//   struct { a, b, c, d string }   sig: SSSS
   782  			//   [4]string                      sig: [4S]
   783  			// That's ok, just a tad inefficient.
   784  			//
   785  			// The generated loops are kind of inefficient as well,
   786  			// so unroll the loop a bit.
   787  			const unrollSize = 32 // make loop body compare around this many bytes
   788  			if et.Size() == 0 {
   789  				break // zero-size elements need no comparison
   790  			}
   791  			unroll := max(1, unrollSize/et.Size())
   792  			// Do partial loops directly.
   793  			for n%unroll != 0 {
   794  				e.build(et)
   795  				n--
   796  			}
   797  			if n == 0 {
   798  				break
   799  			}
   800  			// If we only have one loop left, do it directly.
   801  			if n == unroll {
   802  				for range n {
   803  					e.build(et)
   804  				}
   805  				break
   806  			}
   807  			e.flush(false)
   808  			e.r.WriteString(fmt.Sprintf("%c%d", sigArrayStart, n/unroll))
   809  			for range unroll {
   810  				e.build(et)
   811  			}
   812  			e.flush(false)
   813  			e.r.WriteByte(sigArrayEnd)
   814  		}
   815  	default:
   816  		base.Fatalf("eqSigBuilder %v", t)
   817  	}
   818  }
   819  
   820  // Parse and remove the number at the start of s.
   821  func parseNum(s string) (int64, string) {
   822  	n := 0
   823  	for n < len(s) && s[n] >= '0' && s[n] <= '9' {
   824  		n++
   825  	}
   826  	x, err := strconv.ParseInt(s[:n], 10, 64)
   827  	if err != nil {
   828  		base.Fatalf("bad integer: %s", s[:n])
   829  	}
   830  	return x, s[n:]
   831  }
   832  
   833  // parseArray parses "%d%s]" from the front of a signature.
   834  // Returns the repeat count (the %d), the element signature
   835  // (the %s), and any remaining signature after the closing ']'.
   836  func parseArray(sig string) (int64, string, string) {
   837  	var n int64
   838  	n, sig = parseNum(sig)
   839  	// Find matching closing brace.
   840  	i := 0
   841  	depth := 1
   842  	for {
   843  		if i == len(sig) {
   844  			base.Fatalf("mismatched brackets in %s", sig)
   845  		}
   846  		switch sig[i] {
   847  		case sigArrayStart:
   848  			depth++
   849  		case sigArrayEnd:
   850  			depth--
   851  			if depth == 0 {
   852  				return n, sig[:i], sig[i+1:]
   853  			}
   854  		}
   855  		i++
   856  	}
   857  }
   858  
   859  // sigSize returns the size of the type described by the signature.
   860  func sigSize(sig string) int64 {
   861  	var size int64
   862  	for len(sig) > 0 {
   863  		kind := sig[0]
   864  		sig = sig[1:]
   865  		switch kind {
   866  		case sigMemory, sigSkip:
   867  			var n int64
   868  			n, sig = parseNum(sig)
   869  			size += n
   870  		case sigFloat32:
   871  			size += 4
   872  		case sigFloat64:
   873  			size += 8
   874  		case sigString, sigIface, sigEface:
   875  			size += 2 * int64(types.PtrSize)
   876  		case sigArrayStart:
   877  			var n int64
   878  			var elemSig string
   879  			n, elemSig, sig = parseArray(sig)
   880  			size += n * sigSize(elemSig)
   881  		}
   882  	}
   883  	return size
   884  }
   885  
   886  func sigTrimSkip(s string) string {
   887  	i := strings.LastIndexByte(s, sigSkip)
   888  	if i < 0 {
   889  		return s
   890  	}
   891  	for j := i + 1; j < len(s); j++ {
   892  		if s[j] < '0' || s[j] > '9' {
   893  			return s
   894  		}
   895  	}
   896  	return s[:i]
   897  }
   898
View as plain text