Source file src/pkg/cmd/compile/internal/gc/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 gc
     6	
     7	import (
     8		"cmd/compile/internal/types"
     9		"fmt"
    10	)
    11	
    12	// AlgKind describes the kind of algorithms used for comparing and
    13	// hashing a Type.
    14	type AlgKind int
    15	
    16	const (
    17		// These values are known by runtime.
    18		ANOEQ AlgKind = iota
    19		AMEM0
    20		AMEM8
    21		AMEM16
    22		AMEM32
    23		AMEM64
    24		AMEM128
    25		ASTRING
    26		AINTER
    27		ANILINTER
    28		AFLOAT32
    29		AFLOAT64
    30		ACPLX64
    31		ACPLX128
    32	
    33		// Type can be compared/hashed as regular memory.
    34		AMEM AlgKind = 100
    35	
    36		// Type needs special comparison/hashing functions.
    37		ASPECIAL AlgKind = -1
    38	)
    39	
    40	// IsComparable reports whether t is a comparable type.
    41	func IsComparable(t *types.Type) bool {
    42		a, _ := algtype1(t)
    43		return a != ANOEQ
    44	}
    45	
    46	// IsRegularMemory reports whether t can be compared/hashed as regular memory.
    47	func IsRegularMemory(t *types.Type) bool {
    48		a, _ := algtype1(t)
    49		return a == AMEM
    50	}
    51	
    52	// IncomparableField returns an incomparable Field of struct Type t, if any.
    53	func IncomparableField(t *types.Type) *types.Field {
    54		for _, f := range t.FieldSlice() {
    55			if !IsComparable(f.Type) {
    56				return f
    57			}
    58		}
    59		return nil
    60	}
    61	
    62	// algtype is like algtype1, except it returns the fixed-width AMEMxx variants
    63	// instead of the general AMEM kind when possible.
    64	func algtype(t *types.Type) AlgKind {
    65		a, _ := algtype1(t)
    66		if a == AMEM {
    67			switch t.Width {
    68			case 0:
    69				return AMEM0
    70			case 1:
    71				return AMEM8
    72			case 2:
    73				return AMEM16
    74			case 4:
    75				return AMEM32
    76			case 8:
    77				return AMEM64
    78			case 16:
    79				return AMEM128
    80			}
    81		}
    82	
    83		return a
    84	}
    85	
    86	// algtype1 returns the AlgKind used for comparing and hashing Type t.
    87	// If it returns ANOEQ, it also returns the component type of t that
    88	// makes it incomparable.
    89	func algtype1(t *types.Type) (AlgKind, *types.Type) {
    90		if t.Broke() {
    91			return AMEM, nil
    92		}
    93		if t.Noalg() {
    94			return ANOEQ, t
    95		}
    96	
    97		switch t.Etype {
    98		case TANY, TFORW:
    99			// will be defined later.
   100			return ANOEQ, t
   101	
   102		case TINT8, TUINT8, TINT16, TUINT16,
   103			TINT32, TUINT32, TINT64, TUINT64,
   104			TINT, TUINT, TUINTPTR,
   105			TBOOL, TPTR,
   106			TCHAN, TUNSAFEPTR:
   107			return AMEM, nil
   108	
   109		case TFUNC, TMAP:
   110			return ANOEQ, t
   111	
   112		case TFLOAT32:
   113			return AFLOAT32, nil
   114	
   115		case TFLOAT64:
   116			return AFLOAT64, nil
   117	
   118		case TCOMPLEX64:
   119			return ACPLX64, nil
   120	
   121		case TCOMPLEX128:
   122			return ACPLX128, nil
   123	
   124		case TSTRING:
   125			return ASTRING, nil
   126	
   127		case TINTER:
   128			if t.IsEmptyInterface() {
   129				return ANILINTER, nil
   130			}
   131			return AINTER, nil
   132	
   133		case TSLICE:
   134			return ANOEQ, t
   135	
   136		case TARRAY:
   137			a, bad := algtype1(t.Elem())
   138			switch a {
   139			case AMEM:
   140				return AMEM, nil
   141			case ANOEQ:
   142				return ANOEQ, bad
   143			}
   144	
   145			switch t.NumElem() {
   146			case 0:
   147				// We checked above that the element type is comparable.
   148				return AMEM, nil
   149			case 1:
   150				// Single-element array is same as its lone element.
   151				return a, nil
   152			}
   153	
   154			return ASPECIAL, nil
   155	
   156		case TSTRUCT:
   157			fields := t.FieldSlice()
   158	
   159			// One-field struct is same as that one field alone.
   160			if len(fields) == 1 && !fields[0].Sym.IsBlank() {
   161				return algtype1(fields[0].Type)
   162			}
   163	
   164			ret := AMEM
   165			for i, f := range fields {
   166				// All fields must be comparable.
   167				a, bad := algtype1(f.Type)
   168				if a == ANOEQ {
   169					return ANOEQ, bad
   170				}
   171	
   172				// Blank fields, padded fields, fields with non-memory
   173				// equality need special compare.
   174				if a != AMEM || f.Sym.IsBlank() || ispaddedfield(t, i) {
   175					ret = ASPECIAL
   176				}
   177			}
   178	
   179			return ret, nil
   180		}
   181	
   182		Fatalf("algtype1: unexpected type %v", t)
   183		return 0, nil
   184	}
   185	
   186	// Generate a helper function to compute the hash of a value of type t.
   187	func genhash(sym *types.Sym, t *types.Type) {
   188		if Debug['r'] != 0 {
   189			fmt.Printf("genhash %v %v\n", sym, t)
   190		}
   191	
   192		lineno = autogeneratedPos // less confusing than end of input
   193		dclcontext = PEXTERN
   194	
   195		// func sym(p *T, h uintptr) uintptr
   196		tfn := nod(OTFUNC, nil, nil)
   197		tfn.List.Set2(
   198			namedfield("p", types.NewPtr(t)),
   199			namedfield("h", types.Types[TUINTPTR]),
   200		)
   201		tfn.Rlist.Set1(anonfield(types.Types[TUINTPTR]))
   202	
   203		fn := dclfunc(sym, tfn)
   204		np := asNode(tfn.Type.Params().Field(0).Nname)
   205		nh := asNode(tfn.Type.Params().Field(1).Nname)
   206	
   207		// genhash is only called for types that have equality but
   208		// cannot be handled by the standard algorithms,
   209		// so t must be either an array or a struct.
   210		switch t.Etype {
   211		default:
   212			Fatalf("genhash %v", t)
   213	
   214		case types.TARRAY:
   215			// An array of pure memory would be handled by the
   216			// standard algorithm, so the element type must not be
   217			// pure memory.
   218			hashel := hashfor(t.Elem())
   219	
   220			n := nod(ORANGE, nil, nod(ODEREF, np, nil))
   221			ni := newname(lookup("i"))
   222			ni.Type = types.Types[TINT]
   223			n.List.Set1(ni)
   224			n.SetColas(true)
   225			colasdefn(n.List.Slice(), n)
   226			ni = n.List.First()
   227	
   228			// h = hashel(&p[i], h)
   229			call := nod(OCALL, hashel, nil)
   230	
   231			nx := nod(OINDEX, np, ni)
   232			nx.SetBounded(true)
   233			na := nod(OADDR, nx, nil)
   234			call.List.Append(na)
   235			call.List.Append(nh)
   236			n.Nbody.Append(nod(OAS, nh, call))
   237	
   238			fn.Nbody.Append(n)
   239	
   240		case types.TSTRUCT:
   241			// Walk the struct using memhash for runs of AMEM
   242			// and calling specific hash functions for the others.
   243			for i, fields := 0, t.FieldSlice(); i < len(fields); {
   244				f := fields[i]
   245	
   246				// Skip blank fields.
   247				if f.Sym.IsBlank() {
   248					i++
   249					continue
   250				}
   251	
   252				// Hash non-memory fields with appropriate hash function.
   253				if !IsRegularMemory(f.Type) {
   254					hashel := hashfor(f.Type)
   255					call := nod(OCALL, hashel, nil)
   256					nx := nodSym(OXDOT, np, f.Sym) // TODO: fields from other packages?
   257					na := nod(OADDR, nx, nil)
   258					call.List.Append(na)
   259					call.List.Append(nh)
   260					fn.Nbody.Append(nod(OAS, nh, call))
   261					i++
   262					continue
   263				}
   264	
   265				// Otherwise, hash a maximal length run of raw memory.
   266				size, next := memrun(t, i)
   267	
   268				// h = hashel(&p.first, size, h)
   269				hashel := hashmem(f.Type)
   270				call := nod(OCALL, hashel, nil)
   271				nx := nodSym(OXDOT, np, f.Sym) // TODO: fields from other packages?
   272				na := nod(OADDR, nx, nil)
   273				call.List.Append(na)
   274				call.List.Append(nh)
   275				call.List.Append(nodintconst(size))
   276				fn.Nbody.Append(nod(OAS, nh, call))
   277	
   278				i = next
   279			}
   280		}
   281	
   282		r := nod(ORETURN, nil, nil)
   283		r.List.Append(nh)
   284		fn.Nbody.Append(r)
   285	
   286		if Debug['r'] != 0 {
   287			dumplist("genhash body", fn.Nbody)
   288		}
   289	
   290		funcbody()
   291	
   292		fn.Func.SetDupok(true)
   293		fn = typecheck(fn, ctxStmt)
   294	
   295		Curfn = fn
   296		typecheckslice(fn.Nbody.Slice(), ctxStmt)
   297		Curfn = nil
   298	
   299		if debug_dclstack != 0 {
   300			testdclstack()
   301		}
   302	
   303		fn.Func.SetNilCheckDisabled(true)
   304		funccompile(fn)
   305	}
   306	
   307	func hashfor(t *types.Type) *Node {
   308		var sym *types.Sym
   309	
   310		switch a, _ := algtype1(t); a {
   311		case AMEM:
   312			Fatalf("hashfor with AMEM type")
   313		case AINTER:
   314			sym = Runtimepkg.Lookup("interhash")
   315		case ANILINTER:
   316			sym = Runtimepkg.Lookup("nilinterhash")
   317		case ASTRING:
   318			sym = Runtimepkg.Lookup("strhash")
   319		case AFLOAT32:
   320			sym = Runtimepkg.Lookup("f32hash")
   321		case AFLOAT64:
   322			sym = Runtimepkg.Lookup("f64hash")
   323		case ACPLX64:
   324			sym = Runtimepkg.Lookup("c64hash")
   325		case ACPLX128:
   326			sym = Runtimepkg.Lookup("c128hash")
   327		default:
   328			sym = typesymprefix(".hash", t)
   329		}
   330	
   331		n := newname(sym)
   332		n.SetClass(PFUNC)
   333		n.Sym.SetFunc(true)
   334		n.Type = functype(nil, []*Node{
   335			anonfield(types.NewPtr(t)),
   336			anonfield(types.Types[TUINTPTR]),
   337		}, []*Node{
   338			anonfield(types.Types[TUINTPTR]),
   339		})
   340		return n
   341	}
   342	
   343	// geneq generates a helper function to
   344	// check equality of two values of type t.
   345	func geneq(sym *types.Sym, t *types.Type) {
   346		if Debug['r'] != 0 {
   347			fmt.Printf("geneq %v %v\n", sym, t)
   348		}
   349	
   350		lineno = autogeneratedPos // less confusing than end of input
   351		dclcontext = PEXTERN
   352	
   353		// func sym(p, q *T) bool
   354		tfn := nod(OTFUNC, nil, nil)
   355		tfn.List.Set2(
   356			namedfield("p", types.NewPtr(t)),
   357			namedfield("q", types.NewPtr(t)),
   358		)
   359		tfn.Rlist.Set1(anonfield(types.Types[TBOOL]))
   360	
   361		fn := dclfunc(sym, tfn)
   362		np := asNode(tfn.Type.Params().Field(0).Nname)
   363		nq := asNode(tfn.Type.Params().Field(1).Nname)
   364	
   365		// geneq is only called for types that have equality but
   366		// cannot be handled by the standard algorithms,
   367		// so t must be either an array or a struct.
   368		switch t.Etype {
   369		default:
   370			Fatalf("geneq %v", t)
   371	
   372		case TARRAY:
   373			// An array of pure memory would be handled by the
   374			// standard memequal, so the element type must not be
   375			// pure memory. Even if we unrolled the range loop,
   376			// each iteration would be a function call, so don't bother
   377			// unrolling.
   378			nrange := nod(ORANGE, nil, nod(ODEREF, np, nil))
   379	
   380			ni := newname(lookup("i"))
   381			ni.Type = types.Types[TINT]
   382			nrange.List.Set1(ni)
   383			nrange.SetColas(true)
   384			colasdefn(nrange.List.Slice(), nrange)
   385			ni = nrange.List.First()
   386	
   387			// if p[i] != q[i] { return false }
   388			nx := nod(OINDEX, np, ni)
   389	
   390			nx.SetBounded(true)
   391			ny := nod(OINDEX, nq, ni)
   392			ny.SetBounded(true)
   393	
   394			nif := nod(OIF, nil, nil)
   395			nif.Left = nod(ONE, nx, ny)
   396			r := nod(ORETURN, nil, nil)
   397			r.List.Append(nodbool(false))
   398			nif.Nbody.Append(r)
   399			nrange.Nbody.Append(nif)
   400			fn.Nbody.Append(nrange)
   401	
   402			// return true
   403			ret := nod(ORETURN, nil, nil)
   404			ret.List.Append(nodbool(true))
   405			fn.Nbody.Append(ret)
   406	
   407		case TSTRUCT:
   408			var cond *Node
   409			and := func(n *Node) {
   410				if cond == nil {
   411					cond = n
   412					return
   413				}
   414				cond = nod(OANDAND, cond, n)
   415			}
   416	
   417			// Walk the struct using memequal for runs of AMEM
   418			// and calling specific equality tests for the others.
   419			for i, fields := 0, t.FieldSlice(); i < len(fields); {
   420				f := fields[i]
   421	
   422				// Skip blank-named fields.
   423				if f.Sym.IsBlank() {
   424					i++
   425					continue
   426				}
   427	
   428				// Compare non-memory fields with field equality.
   429				if !IsRegularMemory(f.Type) {
   430					and(eqfield(np, nq, f.Sym))
   431					i++
   432					continue
   433				}
   434	
   435				// Find maximal length run of memory-only fields.
   436				size, next := memrun(t, i)
   437	
   438				// TODO(rsc): All the calls to newname are wrong for
   439				// cross-package unexported fields.
   440				if s := fields[i:next]; len(s) <= 2 {
   441					// Two or fewer fields: use plain field equality.
   442					for _, f := range s {
   443						and(eqfield(np, nq, f.Sym))
   444					}
   445				} else {
   446					// More than two fields: use memequal.
   447					and(eqmem(np, nq, f.Sym, size))
   448				}
   449				i = next
   450			}
   451	
   452			if cond == nil {
   453				cond = nodbool(true)
   454			}
   455	
   456			ret := nod(ORETURN, nil, nil)
   457			ret.List.Append(cond)
   458			fn.Nbody.Append(ret)
   459		}
   460	
   461		if Debug['r'] != 0 {
   462			dumplist("geneq body", fn.Nbody)
   463		}
   464	
   465		funcbody()
   466	
   467		fn.Func.SetDupok(true)
   468		fn = typecheck(fn, ctxStmt)
   469	
   470		Curfn = fn
   471		typecheckslice(fn.Nbody.Slice(), ctxStmt)
   472		Curfn = nil
   473	
   474		if debug_dclstack != 0 {
   475			testdclstack()
   476		}
   477	
   478		// Disable checknils while compiling this code.
   479		// We are comparing a struct or an array,
   480		// neither of which can be nil, and our comparisons
   481		// are shallow.
   482		fn.Func.SetNilCheckDisabled(true)
   483		funccompile(fn)
   484	}
   485	
   486	// eqfield returns the node
   487	// 	p.field == q.field
   488	func eqfield(p *Node, q *Node, field *types.Sym) *Node {
   489		nx := nodSym(OXDOT, p, field)
   490		ny := nodSym(OXDOT, q, field)
   491		ne := nod(OEQ, nx, ny)
   492		return ne
   493	}
   494	
   495	// eqmem returns the node
   496	// 	memequal(&p.field, &q.field [, size])
   497	func eqmem(p *Node, q *Node, field *types.Sym, size int64) *Node {
   498		nx := nod(OADDR, nodSym(OXDOT, p, field), nil)
   499		ny := nod(OADDR, nodSym(OXDOT, q, field), nil)
   500		nx = typecheck(nx, ctxExpr)
   501		ny = typecheck(ny, ctxExpr)
   502	
   503		fn, needsize := eqmemfunc(size, nx.Type.Elem())
   504		call := nod(OCALL, fn, nil)
   505		call.List.Append(nx)
   506		call.List.Append(ny)
   507		if needsize {
   508			call.List.Append(nodintconst(size))
   509		}
   510	
   511		return call
   512	}
   513	
   514	func eqmemfunc(size int64, t *types.Type) (fn *Node, needsize bool) {
   515		switch size {
   516		default:
   517			fn = syslook("memequal")
   518			needsize = true
   519		case 1, 2, 4, 8, 16:
   520			buf := fmt.Sprintf("memequal%d", int(size)*8)
   521			fn = syslook(buf)
   522		}
   523	
   524		fn = substArgTypes(fn, t, t)
   525		return fn, needsize
   526	}
   527	
   528	// memrun finds runs of struct fields for which memory-only algs are appropriate.
   529	// t is the parent struct type, and start is the field index at which to start the run.
   530	// size is the length in bytes of the memory included in the run.
   531	// next is the index just after the end of the memory run.
   532	func memrun(t *types.Type, start int) (size int64, next int) {
   533		next = start
   534		for {
   535			next++
   536			if next == t.NumFields() {
   537				break
   538			}
   539			// Stop run after a padded field.
   540			if ispaddedfield(t, next-1) {
   541				break
   542			}
   543			// Also, stop before a blank or non-memory field.
   544			if f := t.Field(next); f.Sym.IsBlank() || !IsRegularMemory(f.Type) {
   545				break
   546			}
   547		}
   548		return t.Field(next-1).End() - t.Field(start).Offset, next
   549	}
   550	
   551	// ispaddedfield reports whether the i'th field of struct type t is followed
   552	// by padding.
   553	func ispaddedfield(t *types.Type, i int) bool {
   554		if !t.IsStruct() {
   555			Fatalf("ispaddedfield called non-struct %v", t)
   556		}
   557		end := t.Width
   558		if i+1 < t.NumFields() {
   559			end = t.Field(i + 1).Offset
   560		}
   561		return t.Field(i).End() != end
   562	}
   563	

View as plain text