alg.go 13.5 KB
Newer Older
1 2 3 4 5 6
// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package gc

7 8 9 10
import (
	"cmd/compile/internal/types"
	"fmt"
)
11

12 13 14 15
// AlgKind describes the kind of algorithms used for comparing and
// hashing a Type.
type AlgKind int

16 17
const (
	// These values are known by runtime.
18
	ANOEQ AlgKind = iota
19 20 21 22 23 24 25 26 27 28 29 30 31
	AMEM0
	AMEM8
	AMEM16
	AMEM32
	AMEM64
	AMEM128
	ASTRING
	AINTER
	ANILINTER
	AFLOAT32
	AFLOAT64
	ACPLX64
	ACPLX128
32 33 34 35 36 37

	// Type can be compared/hashed as regular memory.
	AMEM AlgKind = 100

	// Type needs special comparison/hashing functions.
	ASPECIAL AlgKind = -1
38 39
)

40
// IsComparable reports whether t is a comparable type.
41
func IsComparable(t *types.Type) bool {
42 43 44 45 46
	a, _ := algtype1(t)
	return a != ANOEQ
}

// IsRegularMemory reports whether t can be compared/hashed as regular memory.
47
func IsRegularMemory(t *types.Type) bool {
48 49 50 51 52
	a, _ := algtype1(t)
	return a == AMEM
}

// 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 57 58 59 60 61 62 63
			return f
		}
	}
	return nil
}

// algtype is like algtype1, except it returns the fixed-width AMEMxx variants
// instead of the general AMEM kind when possible.
64
func algtype(t *types.Type) AlgKind {
65
	a, _ := algtype1(t)
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
	if a == AMEM {
		switch t.Width {
		case 0:
			return AMEM0
		case 1:
			return AMEM8
		case 2:
			return AMEM16
		case 4:
			return AMEM32
		case 8:
			return AMEM64
		case 16:
			return AMEM128
		}
	}

	return a
}

86 87 88
// algtype1 returns the AlgKind used for comparing and hashing Type t.
// If it returns ANOEQ, it also returns the component type of t that
// 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 98
	}

	switch t.Etype {
	case TANY, TFORW:
99
		// will be defined later.
100
		return ANOEQ, t
101

102 103 104 105 106
	case TINT8, TUINT8, TINT16, TUINT16,
		TINT32, TUINT32, TINT64, TUINT64,
		TINT, TUINT, TUINTPTR,
		TBOOL, TPTR32, TPTR64,
		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 134
	case TSLICE:
		return ANOEQ, t
135

136
	case TARRAY:
137
		a, bad := algtype1(t.Elem())
138 139
		switch a {
		case AMEM:
140
			return AMEM, nil
141
		case ANOEQ:
142
			return ANOEQ, bad
143 144
		}

145
		switch t.NumElem() {
146 147
		case 0:
			// We checked above that the element type is comparable.
148
			return AMEM, nil
149 150
		case 1:
			// Single-element array is same as its lone element.
151
			return a, nil
152 153
		}

154
		return ASPECIAL, nil
155 156

	case TSTRUCT:
157 158 159 160
		fields := t.FieldSlice()

		// One-field struct is same as that one field alone.
		if len(fields) == 1 && !isblanksym(fields[0].Sym) {
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 173
			}

			// Blank fields, padded fields, fields with non-memory
			// equality need special compare.
174
			if a != AMEM || isblanksym(f.Sym) || 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 189 190 191
	if Debug['r'] != 0 {
		fmt.Printf("genhash %v %v\n", sym, t)
	}

192
	lineno = autogeneratedPos // less confusing than end of input
193 194 195 196
	dclcontext = PEXTERN
	markdcl()

	// func sym(p *T, h uintptr) uintptr
197
	fn := nod(ODCLFUNC, nil, nil)
198 199 200

	fn.Func.Nname = newname(sym)
	fn.Func.Nname.Class = PFUNC
201
	tfn := nod(OTFUNC, nil, nil)
202 203
	fn.Func.Nname.Name.Param.Ntype = tfn

204
	n := namedfield("p", types.NewPtr(t))
205
	tfn.List.Append(n)
206
	np := n.Left
207
	n = namedfield("h", types.Types[TUINTPTR])
208
	tfn.List.Append(n)
209
	nh := n.Left
210
	n = anonfield(types.Types[TUINTPTR]) // return value
211
	tfn.Rlist.Append(n)
212 213

	funchdr(fn)
214
	fn.Func.Nname.Name.Param.Ntype = typecheck(fn.Func.Nname.Name.Param.Ntype, Etype)
215 216 217 218 219 220 221 222

	// genhash is only called for types that have equality but
	// cannot be handled by the standard algorithms,
	// so t must be either an array or a struct.
	switch t.Etype {
	default:
		Fatalf("genhash %v", t)

223
	case types.TARRAY:
224 225 226
		// An array of pure memory would be handled by the
		// standard algorithm, so the element type must not be
		// pure memory.
227
		hashel := hashfor(t.Elem())
228

229
		n := nod(ORANGE, nil, nod(OIND, np, nil))
230
		ni := newname(lookup("i"))
231
		ni.Type = types.Types[TINT]
232
		n.List.Set1(ni)
233
		n.SetColas(true)
234
		colasdefn(n.List.Slice(), n)
235
		ni = n.List.First()
236 237

		// h = hashel(&p[i], h)
238
		call := nod(OCALL, hashel, nil)
239

240
		nx := nod(OINDEX, np, ni)
241
		nx.SetBounded(true)
242
		na := nod(OADDR, nx, nil)
243
		na.Etype = 1 // no escape to heap
244 245
		call.List.Append(na)
		call.List.Append(nh)
246
		n.Nbody.Append(nod(OAS, nh, call))
247

248
		fn.Nbody.Append(n)
249

250
	case types.TSTRUCT:
251 252
		// Walk the struct using memhash for runs of AMEM
		// and calling specific hash functions for the others.
253 254 255
		for i, fields := 0, t.FieldSlice(); i < len(fields); {
			f := fields[i]

256 257
			// Skip blank fields.
			if isblanksym(f.Sym) {
258
				i++
259 260
				continue
			}
261

262
			// Hash non-memory fields with appropriate hash function.
263
			if !IsRegularMemory(f.Type) {
264
				hashel := hashfor(f.Type)
265
				call := nod(OCALL, hashel, nil)
266
				nx := nodSym(OXDOT, np, f.Sym) // TODO: fields from other packages?
267
				na := nod(OADDR, nx, nil)
268
				na.Etype = 1 // no escape to heap
269 270
				call.List.Append(na)
				call.List.Append(nh)
271
				fn.Nbody.Append(nod(OAS, nh, call))
272
				i++
273 274 275
				continue
			}

276
			// Otherwise, hash a maximal length run of raw memory.
277
			size, next := memrun(t, i)
278 279 280

			// h = hashel(&p.first, size, h)
			hashel := hashmem(f.Type)
281
			call := nod(OCALL, hashel, nil)
282
			nx := nodSym(OXDOT, np, f.Sym) // TODO: fields from other packages?
283
			na := nod(OADDR, nx, nil)
284
			na.Etype = 1 // no escape to heap
285 286
			call.List.Append(na)
			call.List.Append(nh)
287
			call.List.Append(nodintconst(size))
288
			fn.Nbody.Append(nod(OAS, nh, call))
289

290
			i = next
291 292 293
		}
	}

294
	r := nod(ORETURN, nil, nil)
295
	r.List.Append(nh)
296
	fn.Nbody.Append(r)
297 298

	if Debug['r'] != 0 {
299
		dumplist("genhash body", fn.Nbody)
300 301 302 303
	}

	funcbody(fn)
	Curfn = fn
304
	fn.Func.SetDupok(true)
305
	fn = typecheck(fn, Etop)
306
	typecheckslice(fn.Nbody.Slice(), Etop)
307
	Curfn = nil
308
	popdcl()
309 310 311
	if debug_dclstack != 0 {
		testdclstack()
	}
312 313 314 315 316 317 318

	// Disable safemode while compiling this code: the code we
	// generate internally can refer to unsafe.Pointer.
	// In this case it can happen if we need to generate an ==
	// for a struct containing a reflect.Value, which itself has
	// an unexported field of type unsafe.Pointer.
	old_safemode := safemode
319
	safemode = false
320

321
	disable_checknil++
322
	funccompile(fn)
323
	disable_checknil--
324

325 326 327
	safemode = old_safemode
}

328 329
func hashfor(t *types.Type) *Node {
	var sym *types.Sym
330

331
	switch a, _ := algtype1(t); a {
332 333 334
	case AMEM:
		Fatalf("hashfor with AMEM type")
	case AINTER:
335
		sym = Runtimepkg.Lookup("interhash")
336
	case ANILINTER:
337
		sym = Runtimepkg.Lookup("nilinterhash")
338
	case ASTRING:
339
		sym = Runtimepkg.Lookup("strhash")
340
	case AFLOAT32:
341
		sym = Runtimepkg.Lookup("f32hash")
342
	case AFLOAT64:
343
		sym = Runtimepkg.Lookup("f64hash")
344
	case ACPLX64:
345
		sym = Runtimepkg.Lookup("c64hash")
346
	case ACPLX128:
347
		sym = Runtimepkg.Lookup("c128hash")
348 349 350 351 352 353
	default:
		sym = typesymprefix(".hash", t)
	}

	n := newname(sym)
	n.Class = PFUNC
354
	tfn := nod(OTFUNC, nil, nil)
355 356 357
	tfn.List.Append(anonfield(types.NewPtr(t)))
	tfn.List.Append(anonfield(types.Types[TUINTPTR]))
	tfn.Rlist.Append(anonfield(types.Types[TUINTPTR]))
358
	tfn = typecheck(tfn, Etype)
359 360 361 362 363 364
	n.Type = tfn.Type
	return n
}

// geneq generates a helper function to
// check equality of two values of type t.
365
func geneq(sym *types.Sym, t *types.Type) {
366 367 368 369
	if Debug['r'] != 0 {
		fmt.Printf("geneq %v %v\n", sym, t)
	}

370
	lineno = autogeneratedPos // less confusing than end of input
371 372 373 374
	dclcontext = PEXTERN
	markdcl()

	// func sym(p, q *T) bool
375
	fn := nod(ODCLFUNC, nil, nil)
376 377 378

	fn.Func.Nname = newname(sym)
	fn.Func.Nname.Class = PFUNC
379
	tfn := nod(OTFUNC, nil, nil)
380 381
	fn.Func.Nname.Name.Param.Ntype = tfn

382
	n := namedfield("p", types.NewPtr(t))
383
	tfn.List.Append(n)
384
	np := n.Left
385
	n = namedfield("q", types.NewPtr(t))
386
	tfn.List.Append(n)
387
	nq := n.Left
388
	n = anonfield(types.Types[TBOOL])
389
	tfn.Rlist.Append(n)
390 391

	funchdr(fn)
392
	fn.Func.Nname.Name.Param.Ntype = typecheck(fn.Func.Nname.Name.Param.Ntype, Etype)
393 394 395 396 397 398 399 400 401 402 403

	// geneq is only called for types that have equality but
	// cannot be handled by the standard algorithms,
	// so t must be either an array or a struct.
	switch t.Etype {
	default:
		Fatalf("geneq %v", t)

	case TARRAY:
		// An array of pure memory would be handled by the
		// standard memequal, so the element type must not be
404
		// pure memory. Even if we unrolled the range loop,
405 406
		// each iteration would be a function call, so don't bother
		// unrolling.
407
		nrange := nod(ORANGE, nil, nod(OIND, np, nil))
408

409
		ni := newname(lookup("i"))
410
		ni.Type = types.Types[TINT]
411
		nrange.List.Set1(ni)
412
		nrange.SetColas(true)
413
		colasdefn(nrange.List.Slice(), nrange)
414
		ni = nrange.List.First()
415 416

		// if p[i] != q[i] { return false }
417
		nx := nod(OINDEX, np, ni)
418

419
		nx.SetBounded(true)
420
		ny := nod(OINDEX, nq, ni)
421
		ny.SetBounded(true)
422

423 424 425
		nif := nod(OIF, nil, nil)
		nif.Left = nod(ONE, nx, ny)
		r := nod(ORETURN, nil, nil)
426
		r.List.Append(nodbool(false))
427 428 429
		nif.Nbody.Append(r)
		nrange.Nbody.Append(nif)
		fn.Nbody.Append(nrange)
430 431

		// return true
432
		ret := nod(ORETURN, nil, nil)
433
		ret.List.Append(nodbool(true))
434
		fn.Nbody.Append(ret)
435 436

	case TSTRUCT:
437 438 439 440 441 442
		var cond *Node
		and := func(n *Node) {
			if cond == nil {
				cond = n
				return
			}
443
			cond = nod(OANDAND, cond, n)
444
		}
445

446 447
		// Walk the struct using memequal for runs of AMEM
		// and calling specific equality tests for the others.
448 449 450
		for i, fields := 0, t.FieldSlice(); i < len(fields); {
			f := fields[i]

451 452
			// Skip blank-named fields.
			if isblanksym(f.Sym) {
453
				i++
454 455
				continue
			}
456 457

			// Compare non-memory fields with field equality.
458
			if !IsRegularMemory(f.Type) {
459
				and(eqfield(np, nq, f.Sym))
460
				i++
461 462 463
				continue
			}

464
			// Find maximal length run of memory-only fields.
465
			size, next := memrun(t, i)
466 467 468

			// TODO(rsc): All the calls to newname are wrong for
			// cross-package unexported fields.
469 470 471
			if s := fields[i:next]; len(s) <= 2 {
				// Two or fewer fields: use plain field equality.
				for _, f := range s {
472
					and(eqfield(np, nq, f.Sym))
473
				}
474 475
			} else {
				// More than two fields: use memequal.
476
				and(eqmem(np, nq, f.Sym, size))
477
			}
478
			i = next
479 480
		}

481
		if cond == nil {
482
			cond = nodbool(true)
483 484
		}

485
		ret := nod(ORETURN, nil, nil)
486
		ret.List.Append(cond)
487
		fn.Nbody.Append(ret)
488 489 490
	}

	if Debug['r'] != 0 {
491
		dumplist("geneq body", fn.Nbody)
492 493 494 495
	}

	funcbody(fn)
	Curfn = fn
496
	fn.Func.SetDupok(true)
497
	fn = typecheck(fn, Etop)
498
	typecheckslice(fn.Nbody.Slice(), Etop)
499
	Curfn = nil
500
	popdcl()
501 502 503
	if debug_dclstack != 0 {
		testdclstack()
	}
504 505 506 507 508 509 510

	// Disable safemode while compiling this code: the code we
	// generate internally can refer to unsafe.Pointer.
	// In this case it can happen if we need to generate an ==
	// for a struct containing a reflect.Value, which itself has
	// an unexported field of type unsafe.Pointer.
	old_safemode := safemode
511
	safemode = false
512 513 514 515 516

	// Disable checknils while compiling this code.
	// We are comparing a struct or an array,
	// neither of which can be nil, and our comparisons
	// are shallow.
517
	disable_checknil++
518 519 520 521

	funccompile(fn)

	safemode = old_safemode
522
	disable_checknil--
523 524 525 526
}

// eqfield returns the node
// 	p.field == q.field
527
func eqfield(p *Node, q *Node, field *types.Sym) *Node {
528 529
	nx := nodSym(OXDOT, p, field)
	ny := nodSym(OXDOT, q, field)
530
	ne := nod(OEQ, nx, ny)
531 532 533 534 535
	return ne
}

// eqmem returns the node
// 	memequal(&p.field, &q.field [, size])
536
func eqmem(p *Node, q *Node, field *types.Sym, size int64) *Node {
537
	nx := nod(OADDR, nodSym(OXDOT, p, field), nil)
538
	nx.Etype = 1 // does not escape
539
	ny := nod(OADDR, nodSym(OXDOT, q, field), nil)
540
	ny.Etype = 1 // does not escape
541 542
	nx = typecheck(nx, Erv)
	ny = typecheck(ny, Erv)
543

544
	fn, needsize := eqmemfunc(size, nx.Type.Elem())
545
	call := nod(OCALL, fn, nil)
546 547
	call.List.Append(nx)
	call.List.Append(ny)
548
	if needsize {
549
		call.List.Append(nodintconst(size))
550 551 552 553 554
	}

	return call
}

555
func eqmemfunc(size int64, t *types.Type) (fn *Node, needsize bool) {
556 557
	switch size {
	default:
558
		fn = syslook("memequal")
559
		needsize = true
560 561
	case 1, 2, 4, 8, 16:
		buf := fmt.Sprintf("memequal%d", int(size)*8)
562
		fn = syslook(buf)
563 564
	}

565
	fn = substArgTypes(fn, t, t)
566
	return fn, needsize
567 568 569
}

// memrun finds runs of struct fields for which memory-only algs are appropriate.
570
// t is the parent struct type, and start is the field index at which to start the run.
571
// size is the length in bytes of the memory included in the run.
572
// next is the index just after the end of the memory run.
573
func memrun(t *types.Type, start int) (size int64, next int) {
574
	next = start
575
	for {
576
		next++
577
		if next == t.NumFields() {
578 579
			break
		}
580
		// Stop run after a padded field.
581
		if ispaddedfield(t, next-1) {
582
			break
583
		}
584
		// Also, stop before a blank or non-memory field.
585
		if f := t.Field(next); isblanksym(f.Sym) || !IsRegularMemory(f.Type) {
586 587 588
			break
		}
	}
589
	return t.Field(next-1).End() - t.Field(start).Offset, next
590 591
}

592
// ispaddedfield reports whether the i'th field of struct type t is followed
593
// by padding.
594
func ispaddedfield(t *types.Type, i int) bool {
595
	if !t.IsStruct() {
596 597 598
		Fatalf("ispaddedfield called non-struct %v", t)
	}
	end := t.Width
599 600
	if i+1 < t.NumFields() {
		end = t.Field(i + 1).Offset
601
	}
602
	return t.Field(i).End() != end
603
}