From 89c2f282dc84a9b3842dca375a4635305c86ad9b Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Mon, 6 Jan 2025 15:28:22 -0800 Subject: [PATCH] cmd/compile: move []byte->string map key optimization to ssa If we call slicebytetostring immediately (with no intervening writes) before calling map access or delete functions with the resulting string as the key, then we can just use the ptr/len of the slicebytetostring argument as the key. This avoids an allocation. Fixes #44898 Update #71132 There's old code in cmd/compile/internal/walk/order.go that handles some of these cases. 1. m[string(b)] 2. s := string(b); m[s] 3. m[[2]string{string(b1),string(b2)}] The old code handled cases 1&3. The new code handles cases 1&2. We'll leave the old code around to keep 3 working, although it seems not terribly common. Case 2 happens particularly after inlining, so it is pretty common. Change-Id: I8913226ca79d2c65f4e2bd69a38ac8c976a57e43 Reviewed-on: https://go-review.googlesource.com/c/go/+/640656 Reviewed-by: Keith Randall Reviewed-by: Michael Pratt LUCI-TryBot-Result: Go LUCI --- .../compile/internal/ssa/_gen/generic.rules | 19 ++++++++++ src/cmd/compile/internal/ssa/rewrite.go | 8 +++++ .../compile/internal/ssa/rewritegeneric.go | 36 +++++++++++++++++++ src/cmd/compile/internal/walk/order.go | 8 +++++ test/codegen/maps.go | 22 ++++++++++++ 5 files changed, 93 insertions(+) diff --git a/src/cmd/compile/internal/ssa/_gen/generic.rules b/src/cmd/compile/internal/ssa/_gen/generic.rules index 9188eff2ec..0339370517 100644 --- a/src/cmd/compile/internal/ssa/_gen/generic.rules +++ b/src/cmd/compile/internal/ssa/_gen/generic.rules @@ -2795,3 +2795,22 @@ && isDirectIface(itab) && clobber(v) => (MakeResult (EqPtr x y) mem) + +// If we use the result of slicebytetostring in a map lookup operation, +// then we don't need to actually do the []byte->string conversion. +// We can just use the ptr/len of the byte slice directly as a (temporary) string. +// +// Note that this does not handle some obscure cases like +// m[[2]string{string(b1), string(b2)}]. There is code in ../walk/order.go +// which handles some of those cases. +(StaticLECall {f} [argsize] typ_ map_ key:(SelectN [0] sbts:(StaticLECall {g} _ ptr len mem)) m:(SelectN [1] sbts)) + && (isSameCall(f, "runtime.mapaccess1_faststr") + || isSameCall(f, "runtime.mapaccess2_faststr") + || isSameCall(f, "runtime.mapdelete_faststr")) + && isSameCall(g, "runtime.slicebytetostring") + && key.Uses == 1 + && sbts.Uses == 2 + && resetCopy(m, mem) + && clobber(sbts) + && clobber(key) +=> (StaticLECall {f} [argsize] typ_ map_ (StringMake ptr len) mem) diff --git a/src/cmd/compile/internal/ssa/rewrite.go b/src/cmd/compile/internal/ssa/rewrite.go index 383cb23dae..71f8e9045c 100644 --- a/src/cmd/compile/internal/ssa/rewrite.go +++ b/src/cmd/compile/internal/ssa/rewrite.go @@ -964,6 +964,14 @@ func clobber(vv ...*Value) bool { return true } +// resetCopy resets v to be a copy of arg. +// Always returns true. +func resetCopy(v *Value, arg *Value) bool { + v.reset(OpCopy) + v.AddArg(arg) + return true +} + // clobberIfDead resets v when use count is 1. Returns true. // clobberIfDead is used by rewrite rules to decrement // use counts of v's args when v is dead and never used. diff --git a/src/cmd/compile/internal/ssa/rewritegeneric.go b/src/cmd/compile/internal/ssa/rewritegeneric.go index b3161ad50d..d0b6e0b100 100644 --- a/src/cmd/compile/internal/ssa/rewritegeneric.go +++ b/src/cmd/compile/internal/ssa/rewritegeneric.go @@ -30350,6 +30350,42 @@ func rewriteValuegeneric_OpStaticLECall(v *Value) bool { v.AddArg2(v0, mem) return true } + // match: (StaticLECall {f} [argsize] typ_ map_ key:(SelectN [0] sbts:(StaticLECall {g} _ ptr len mem)) m:(SelectN [1] sbts)) + // cond: (isSameCall(f, "runtime.mapaccess1_faststr") || isSameCall(f, "runtime.mapaccess2_faststr") || isSameCall(f, "runtime.mapdelete_faststr")) && isSameCall(g, "runtime.slicebytetostring") && key.Uses == 1 && sbts.Uses == 2 && resetCopy(m, mem) && clobber(sbts) && clobber(key) + // result: (StaticLECall {f} [argsize] typ_ map_ (StringMake ptr len) mem) + for { + if len(v.Args) != 4 { + break + } + argsize := auxIntToInt32(v.AuxInt) + f := auxToCall(v.Aux) + _ = v.Args[3] + typ_ := v.Args[0] + map_ := v.Args[1] + key := v.Args[2] + if key.Op != OpSelectN || auxIntToInt64(key.AuxInt) != 0 { + break + } + sbts := key.Args[0] + if sbts.Op != OpStaticLECall || len(sbts.Args) != 4 { + break + } + g := auxToCall(sbts.Aux) + mem := sbts.Args[3] + ptr := sbts.Args[1] + len := sbts.Args[2] + m := v.Args[3] + if m.Op != OpSelectN || auxIntToInt64(m.AuxInt) != 1 || sbts != m.Args[0] || !((isSameCall(f, "runtime.mapaccess1_faststr") || isSameCall(f, "runtime.mapaccess2_faststr") || isSameCall(f, "runtime.mapdelete_faststr")) && isSameCall(g, "runtime.slicebytetostring") && key.Uses == 1 && sbts.Uses == 2 && resetCopy(m, mem) && clobber(sbts) && clobber(key)) { + break + } + v.reset(OpStaticLECall) + v.AuxInt = int32ToAuxInt(argsize) + v.Aux = callToAux(f) + v0 := b.NewValue0(v.Pos, OpStringMake, typ.String) + v0.AddArg2(ptr, len) + v.AddArg4(typ_, map_, v0, mem) + return true + } return false } func rewriteValuegeneric_OpStore(v *Value) bool { diff --git a/src/cmd/compile/internal/walk/order.go b/src/cmd/compile/internal/walk/order.go index 858fc706ab..8967b7dbba 100644 --- a/src/cmd/compile/internal/walk/order.go +++ b/src/cmd/compile/internal/walk/order.go @@ -334,6 +334,14 @@ func (o *orderState) mapKeyTemp(outerPos src.XPos, t *types.Type, n ir.Node) ir. // It would be nice to handle these generally, but because // []byte keys are not allowed in maps, the use of string(k) // comes up in important cases in practice. See issue 3512. +// +// Note that this code does not handle the case: +// +// s := string(k) +// x = m[s] +// +// Cases like this are handled during SSA, search for slicebytetostring +// in ../ssa/_gen/generic.rules. func mapKeyReplaceStrConv(n ir.Node) bool { var replaced bool switch n.Op() { diff --git a/test/codegen/maps.go b/test/codegen/maps.go index c4aed33545..860b2c2cbd 100644 --- a/test/codegen/maps.go +++ b/test/codegen/maps.go @@ -66,6 +66,28 @@ func LookupStringConversionKeyedArrayLit(m map[[2]string]int, bytes []byte) int return m[[2]string{0: string(bytes)}] } +func LookupStringConversion1(m map[string]int, bytes []byte) int { + // amd64:-`.*runtime\.slicebytetostring\(` + s := string(bytes) + return m[s] +} +func LookupStringConversion2(m *map[string]int, bytes []byte) int { + // amd64:-`.*runtime\.slicebytetostring\(` + s := string(bytes) + return (*m)[s] +} +func LookupStringConversion3(m map[string]int, bytes []byte) (int, bool) { + // amd64:-`.*runtime\.slicebytetostring\(` + s := string(bytes) + r, ok := m[s] + return r, ok +} +func DeleteStringConversion(m map[string]int, bytes []byte) { + // amd64:-`.*runtime\.slicebytetostring\(` + s := string(bytes) + delete(m, s) +} + // ------------------- // // Map Clear // // ------------------- // -- 2.51.0