From 6505fcbd0aaba2ab39915dcf437f01f1af83cd25 Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Wed, 11 Jun 2025 17:14:59 -0700 Subject: [PATCH] cmd/compile: use generics for sparse map So it is easier to reuse this code with different key/value types. Change-Id: I5a9e669769cf359b32f2fe784594868acdee4d02 Reviewed-on: https://go-review.googlesource.com/c/go/+/681175 Reviewed-by: Keith Randall Reviewed-by: David Chase Auto-Submit: Keith Randall LUCI-TryBot-Result: Go LUCI Reviewed-by: Cherry Mui --- .../compile/internal/ssa/biasedsparsemap.go | 6 +- src/cmd/compile/internal/ssa/deadstore.go | 4 +- src/cmd/compile/internal/ssa/sparsemap.go | 68 +++++++++---------- 3 files changed, 39 insertions(+), 39 deletions(-) diff --git a/src/cmd/compile/internal/ssa/biasedsparsemap.go b/src/cmd/compile/internal/ssa/biasedsparsemap.go index 948aef9a9b..c08efbf162 100644 --- a/src/cmd/compile/internal/ssa/biasedsparsemap.go +++ b/src/cmd/compile/internal/ssa/biasedsparsemap.go @@ -68,7 +68,11 @@ func (s *biasedSparseMap) get(x uint) int32 { if int(x) >= s.cap() { return -1 } - return s.s.get(ID(int(x) - s.first)) + k := ID(int(x) - s.first) + if !s.s.contains(k) { + return -1 // TODO: push presence check to callers? + } + return s.s.get(k) } // getEntry returns the i'th key and value stored in s, diff --git a/src/cmd/compile/internal/ssa/deadstore.go b/src/cmd/compile/internal/ssa/deadstore.go index f8c69dc698..40905bedcf 100644 --- a/src/cmd/compile/internal/ssa/deadstore.go +++ b/src/cmd/compile/internal/ssa/deadstore.go @@ -156,9 +156,7 @@ func dse(f *Func) { // A shadowRange encodes a set of byte offsets [lo():hi()] from // a given pointer that will be written to later in the block. -// A zero shadowRange encodes an empty shadowed range (and so -// does a -1 shadowRange, which is what sparsemap.get returns -// on a failed lookup). +// A zero shadowRange encodes an empty shadowed range. type shadowRange int32 func (sr shadowRange) lo() int64 { diff --git a/src/cmd/compile/internal/ssa/sparsemap.go b/src/cmd/compile/internal/ssa/sparsemap.go index 9443c8b4b4..b7363b36eb 100644 --- a/src/cmd/compile/internal/ssa/sparsemap.go +++ b/src/cmd/compile/internal/ssa/sparsemap.go @@ -7,70 +7,60 @@ package ssa // from https://research.swtch.com/sparse // in turn, from Briggs and Torczon -type sparseEntry struct { - key ID - val int32 +// sparseKey needs to be something we can index a slice with. +type sparseKey interface{ ~int | ~int32 } + +type sparseEntry[K sparseKey, V any] struct { + key K + val V } -type sparseMap struct { - dense []sparseEntry +type genericSparseMap[K sparseKey, V any] struct { + dense []sparseEntry[K, V] sparse []int32 } -// newSparseMap returns a sparseMap that can map -// integers between 0 and n-1 to int32s. -func newSparseMap(n int) *sparseMap { - return &sparseMap{dense: nil, sparse: make([]int32, n)} +// newGenericSparseMap returns a sparseMap that can map +// integers between 0 and n-1 to a value type. +func newGenericSparseMap[K sparseKey, V any](n int) *genericSparseMap[K, V] { + return &genericSparseMap[K, V]{dense: nil, sparse: make([]int32, n)} } -func (s *sparseMap) cap() int { +func (s *genericSparseMap[K, V]) cap() int { return len(s.sparse) } -func (s *sparseMap) size() int { +func (s *genericSparseMap[K, V]) size() int { return len(s.dense) } -func (s *sparseMap) contains(k ID) bool { +func (s *genericSparseMap[K, V]) contains(k K) bool { i := s.sparse[k] return i < int32(len(s.dense)) && s.dense[i].key == k } -// get returns the value for key k, or -1 if k does -// not appear in the map. -func (s *sparseMap) get(k ID) int32 { +// get returns the value for key k, or the zero V +// if k does not appear in the map. +func (s *genericSparseMap[K, V]) get(k K) V { i := s.sparse[k] if i < int32(len(s.dense)) && s.dense[i].key == k { return s.dense[i].val } - return -1 + var v V + return v } -func (s *sparseMap) set(k ID, v int32) { +func (s *genericSparseMap[K, V]) set(k K, v V) { i := s.sparse[k] if i < int32(len(s.dense)) && s.dense[i].key == k { s.dense[i].val = v return } - s.dense = append(s.dense, sparseEntry{k, v}) - s.sparse[k] = int32(len(s.dense)) - 1 -} - -// setBit sets the v'th bit of k's value, where 0 <= v < 32 -func (s *sparseMap) setBit(k ID, v uint) { - if v >= 32 { - panic("bit index too large.") - } - i := s.sparse[k] - if i < int32(len(s.dense)) && s.dense[i].key == k { - s.dense[i].val |= 1 << v - return - } - s.dense = append(s.dense, sparseEntry{k, 1 << v}) + s.dense = append(s.dense, sparseEntry[K, V]{k, v}) s.sparse[k] = int32(len(s.dense)) - 1 } -func (s *sparseMap) remove(k ID) { +func (s *genericSparseMap[K, V]) remove(k K) { i := s.sparse[k] if i < int32(len(s.dense)) && s.dense[i].key == k { y := s.dense[len(s.dense)-1] @@ -80,10 +70,18 @@ func (s *sparseMap) remove(k ID) { } } -func (s *sparseMap) clear() { +func (s *genericSparseMap[K, V]) clear() { s.dense = s.dense[:0] } -func (s *sparseMap) contents() []sparseEntry { +func (s *genericSparseMap[K, V]) contents() []sparseEntry[K, V] { return s.dense } + +type sparseMap = genericSparseMap[ID, int32] + +// newSparseMap returns a sparseMap that can map +// integers between 0 and n-1 to int32s. +func newSparseMap(n int) *sparseMap { + return newGenericSparseMap[ID, int32](n) +} -- 2.51.0