cmd/compile: improve PopCount's limits modeling and add bruteforce tests

This make PopCount perfect within the limitations limits can represent.

Change-Id: Ia52e5d79064ad8109117f009c5390a6eba8ccd98
Reviewed-on: https://go-review.googlesource.com/c/go/+/727782
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Carlos Amedee <carlos@golang.org>
Auto-Submit: Jorropo <jorropo.pgm@gmail.com>
Reviewed-by: Keith Randall <khr@google.com>

2 files changed, 30 insertions, 6 deletions

diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go
index 233d0b30d1..3de964f061 100644
--- a/src/cmd/compile/internal/ssa/prove.go
+++ b/src/cmd/compile/internal/ssa/prove.go
@@ -436,6 +436,29 @@ func (l limit) bitlen(b uint) limit {
 	)
 }
 
+// Similar to add, but computes the PopCount of the limit for bitsize b.
+func (l limit) popcount(b uint) limit {
+	fixed, fixedCount := l.unsignedFixedLeadingBits()
+	varying := 64 - fixedCount
+	fixedContribution := uint64(bits.OnesCount64(fixed))
+
+	min := fixedContribution
+	max := fixedContribution + uint64(varying)
+
+	varyingMask := uint64(1)<<varying - 1
+
+	if varyingPartOfUmax := l.umax & varyingMask; uint(bits.OnesCount64(varyingPartOfUmax)) != varying {
+		// there is at least one zero bit in the varying part
+		max--
+	}
+	if varyingPartOfUmin := l.umin & varyingMask; varyingPartOfUmin != 0 {
+		// there is at least one non-zero bit in the varying part
+		min++
+	}
+
+	return noLimit.unsignedMinMax(min, max)
+}
+
 var noLimit = limit{math.MinInt64, math.MaxInt64, 0, math.MaxUint64}
 
 // a limitFact is a limit known for a particular value.
@@ -1942,12 +1965,9 @@ func (ft *factsTable) flowLimit(v *Value) {
 		ft.newLimit(v, al.ctz(uint(a.Type.Size())*8))
 
 	case OpPopCount64, OpPopCount32, OpPopCount16, OpPopCount8:
-		a := ft.limits[v.Args[0].ID]
-		changingBitsCount := uint64(bits.Len64(a.umax ^ a.umin))
-		sharedLeadingMask := ^(uint64(1)<<changingBitsCount - 1)
-		fixedBits := a.umax & sharedLeadingMask
-		min := uint64(bits.OnesCount64(fixedBits))
-		ft.unsignedMinMax(v, min, min+changingBitsCount)
+		a := v.Args[0]
+		al := ft.limits[a.ID]
+		ft.newLimit(v, al.popcount(uint(a.Type.Size())*8))
 
 	case OpBitLen64, OpBitLen32, OpBitLen16, OpBitLen8:
 		a := v.Args[0]
diff --git a/src/cmd/compile/internal/ssa/prove_test.go b/src/cmd/compile/internal/ssa/prove_test.go
index 969e68fee4..42a60dcb40 100644
--- a/src/cmd/compile/internal/ssa/prove_test.go
+++ b/src/cmd/compile/internal/ssa/prove_test.go
@@ -81,3 +81,7 @@ func TestLimitCtzUnsigned(t *testing.T) {
 func TestLimitBitlenUnsigned(t *testing.T) {
 	testLimitUnaryOpUnsigned8(t, "bitlen", limit{-128, 127, 0, 8}, limit.bitlen, func(x uint8) uint8 { return uint8(bits.Len8(x)) })
 }
+
+func TestLimitPopcountUnsigned(t *testing.T) {
+	testLimitUnaryOpUnsigned8(t, "popcount", limit{-128, 127, 0, 8}, limit.popcount, func(x uint8) uint8 { return uint8(bits.OnesCount8(x)) })
+}