[dev.typeparams] cmd/compile: make HasShape() more efficient by implementing with a type flag

Implement HasShape() similar to how HasTParam() is implemented.

Fixes #47456

Change-Id: Icbd538574237faad2c4cd8c8e187725a1df47637
Reviewed-on: https://go-review.googlesource.com/c/go/+/339029
Reviewed-by: Keith Randall <khr@golang.org>
Trust: Dan Scales <danscales@google.com>

2 files changed, 54 insertions, 53 deletions

diff --git a/src/cmd/compile/internal/typecheck/subr.go b/src/cmd/compile/internal/typecheck/subr.go
index 5ee4152e1c..968d7a0d6d 100644
--- a/src/cmd/compile/internal/typecheck/subr.go
+++ b/src/cmd/compile/internal/typecheck/subr.go
@@ -1367,6 +1367,7 @@ func Shapify(t *types.Type) *types.Type {
 	s := types.NewNamed(name)
 	s.SetUnderlying(u)
 	s.SetIsShape(true)
+	s.SetHasShape(true)
 	name.SetType(s)
 	name.SetTypecheck(1)
 	// TODO: add methods to s that the bound has?
diff --git a/src/cmd/compile/internal/types/type.go b/src/cmd/compile/internal/types/type.go
index 58ac4db95a..1f01498ca1 100644
--- a/src/cmd/compile/internal/types/type.go
+++ b/src/cmd/compile/internal/types/type.go
@@ -211,6 +211,7 @@ const (
 	typeRecur
 	typeHasTParam // there is a typeparam somewhere in the type (generic function or type)
 	typeIsShape   // represents a set of closely related types, for generics
+	typeHasShape  // there is a shape somewhere in the type
 )
 
 func (t *Type) NotInHeap() bool  { return t.flags&typeNotInHeap != 0 }
@@ -220,17 +221,21 @@ func (t *Type) Deferwidth() bool { return t.flags&typeDeferwidth != 0 }
 func (t *Type) Recur() bool      { return t.flags&typeRecur != 0 }
 func (t *Type) HasTParam() bool  { return t.flags&typeHasTParam != 0 }
 func (t *Type) IsShape() bool    { return t.flags&typeIsShape != 0 }
+func (t *Type) HasShape() bool   { return t.flags&typeHasShape != 0 }
 
 func (t *Type) SetNotInHeap(b bool)  { t.flags.set(typeNotInHeap, b) }
 func (t *Type) SetBroke(b bool)      { t.flags.set(typeBroke, b) }
 func (t *Type) SetNoalg(b bool)      { t.flags.set(typeNoalg, b) }
 func (t *Type) SetDeferwidth(b bool) { t.flags.set(typeDeferwidth, b) }
 func (t *Type) SetRecur(b bool)      { t.flags.set(typeRecur, b) }
-func (t *Type) SetIsShape(b bool)    { t.flags.set(typeIsShape, b) }
 
 // Generic types should never have alg functions.
 func (t *Type) SetHasTParam(b bool) { t.flags.set(typeHasTParam, b); t.flags.set(typeNoalg, b) }
 
+// Should always do SetHasShape(true) when doing SeIsShape(true).
+func (t *Type) SetIsShape(b bool)  { t.flags.set(typeIsShape, b) }
+func (t *Type) SetHasShape(b bool) { t.flags.set(typeHasShape, b) }
+
 // Kind returns the kind of type t.
 func (t *Type) Kind() Kind { return t.kind }
 
@@ -271,9 +276,6 @@ func (t *Type) SetRParams(rparams []*Type) {
 		base.Fatalf("Setting nil or zero-length rparams")
 	}
 	t.rparams = &rparams
-	if t.HasTParam() {
-		return
-	}
 	// HasTParam should be set if any rparam is or has a type param. This is
 	// to handle the case of a generic type which doesn't reference any of its
 	// type params (e.g. most commonly, an empty struct).
@@ -282,6 +284,10 @@ func (t *Type) SetRParams(rparams []*Type) {
 			t.SetHasTParam(true)
 			break
 		}
+		if rparam.HasShape() {
+			t.SetHasShape(true)
+			break
+		}
 	}
 }
 
@@ -624,6 +630,9 @@ func NewArray(elem *Type, bound int64) *Type {
 	if elem.HasTParam() {
 		t.SetHasTParam(true)
 	}
+	if elem.HasShape() {
+		t.SetHasShape(true)
+	}
 	return t
 }
 
@@ -642,6 +651,9 @@ func NewSlice(elem *Type) *Type {
 	if elem.HasTParam() {
 		t.SetHasTParam(true)
 	}
+	if elem.HasShape() {
+		t.SetHasShape(true)
+	}
 	return t
 }
 
@@ -654,6 +666,9 @@ func NewChan(elem *Type, dir ChanDir) *Type {
 	if elem.HasTParam() {
 		t.SetHasTParam(true)
 	}
+	if elem.HasShape() {
+		t.SetHasShape(true)
+	}
 	return t
 }
 
@@ -664,6 +679,9 @@ func NewTuple(t1, t2 *Type) *Type {
 	if t1.HasTParam() || t2.HasTParam() {
 		t.SetHasTParam(true)
 	}
+	if t1.HasShape() || t2.HasShape() {
+		t.SetHasShape(true)
+	}
 	return t
 }
 
@@ -695,6 +713,9 @@ func NewMap(k, v *Type) *Type {
 	if k.HasTParam() || v.HasTParam() {
 		t.SetHasTParam(true)
 	}
+	if k.HasShape() || v.HasShape() {
+		t.SetHasShape(true)
+	}
 	return t
 }
 
@@ -719,6 +740,9 @@ func NewPtr(elem *Type) *Type {
 			// when this entry was cached.
 			t.SetHasTParam(true)
 		}
+		if elem.HasShape() {
+			t.SetHasShape(true)
+		}
 		return t
 	}
 
@@ -732,6 +756,9 @@ func NewPtr(elem *Type) *Type {
 	if elem.HasTParam() {
 		t.SetHasTParam(true)
 	}
+	if elem.HasShape() {
+		t.SetHasShape(true)
+	}
 	return t
 }
 
@@ -1768,6 +1795,9 @@ func (t *Type) SetUnderlying(underlying *Type) {
 	if underlying.HasTParam() {
 		t.SetHasTParam(true)
 	}
+	if underlying.HasShape() {
+		t.SetHasShape(true)
+	}
 
 	// spec: "The declared type does not inherit any methods bound
 	// to the existing type, but the method set of an interface
@@ -1799,6 +1829,15 @@ func fieldsHasTParam(fields []*Field) bool {
 	return false
 }
 
+func fieldsHasShape(fields []*Field) bool {
+	for _, f := range fields {
+		if f.Type != nil && f.Type.HasShape() {
+			return true
+		}
+	}
+	return false
+}
+
 // NewBasic returns a new basic type of the given kind.
 func NewBasic(kind Kind, obj Object) *Type {
 	t := New(kind)
@@ -1818,6 +1857,10 @@ func NewInterface(pkg *Pkg, methods []*Field) *Type {
 			t.SetHasTParam(true)
 			break
 		}
+		if f.Type != nil && f.Type.HasShape() {
+			t.SetHasShape(true)
+			break
+		}
 	}
 	if anyBroke(methods) {
 		t.SetBroke(true)
@@ -1923,6 +1966,9 @@ func NewSignature(pkg *Pkg, recv *Field, tparams, params, results []*Field) *Typ
 		fieldsHasTParam(results) {
 		t.SetHasTParam(true)
 	}
+	if fieldsHasShape(recvs) || fieldsHasShape(params) || fieldsHasShape(results) {
+		t.SetHasShape(true)
+	}
 
 	return t
 }
@@ -1938,6 +1984,9 @@ func NewStruct(pkg *Pkg, fields []*Field) *Type {
 	if fieldsHasTParam(fields) {
 		t.SetHasTParam(true)
 	}
+	if fieldsHasShape(fields) {
+		t.SetHasShape(true)
+	}
 	return t
 }
 
@@ -2150,52 +2199,3 @@ var (
 )
 
 var SimType [NTYPE]Kind
-
-// Reports whether t has a shape type anywere.
-func (t *Type) HasShape() bool {
-	return t.HasShape1(map[*Type]bool{})
-}
-func (t *Type) HasShape1(visited map[*Type]bool) bool {
-	if t.IsShape() {
-		return true
-	}
-	if visited[t] {
-		return false
-	}
-	visited[t] = true
-	if t.Sym() != nil {
-		for _, u := range t.RParams() {
-			if u.HasShape1(visited) {
-				return true
-			}
-		}
-	}
-	switch t.Kind() {
-	case TPTR, TARRAY, TSLICE, TCHAN:
-		return t.Elem().HasShape1(visited)
-	case TMAP:
-		return t.Elem().HasShape1(visited) || t.Key().HasShape1(visited)
-	case TSTRUCT:
-		for _, f := range t.FieldSlice() {
-			if f.Type.HasShape1(visited) {
-				return true
-			}
-		}
-	case TFUNC:
-		for _, a := range RecvsParamsResults {
-			for _, f := range a(t).FieldSlice() {
-				if f.Type.HasShape1(visited) {
-					return true
-				}
-			}
-		}
-	case TINTER:
-		for _, f := range t.Methods().Slice() {
-			if f.Type.HasShape1(visited) {
-				return true
-			}
-		}
-		return false
-	}
-	return false
-}