From cd2cb6e3f57e4820d66dbefd7577048c38ee9e04 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Daniel=20Mart=C3=AD?= Date: Mon, 5 Mar 2018 10:46:44 +0000 Subject: [PATCH] cmd/compile: cache sparse maps across ssa passes MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This is done for sparse sets already, but it was missing for sparse maps. Only affects deadstore and regalloc, as they're the only ones that use sparse maps. name old time/op new time/op delta DSEPass-4 247µs ± 0% 216µs ± 0% -12.75% (p=0.008 n=5+5) DSEPassBlock-4 3.05ms ± 1% 2.87ms ± 1% -6.02% (p=0.002 n=6+6) CSEPass-4 2.30ms ± 0% 2.32ms ± 0% +0.53% (p=0.026 n=6+6) CSEPassBlock-4 23.8ms ± 0% 23.8ms ± 0% ~ (p=0.931 n=6+5) DeadcodePass-4 51.7µs ± 1% 51.5µs ± 2% ~ (p=0.429 n=5+6) DeadcodePassBlock-4 734µs ± 1% 742µs ± 3% ~ (p=0.394 n=6+6) MultiPass-4 152µs ± 0% 149µs ± 2% ~ (p=0.082 n=5+6) MultiPassBlock-4 2.67ms ± 1% 2.41ms ± 2% -9.77% (p=0.008 n=5+5) name old alloc/op new alloc/op delta DSEPass-4 41.2kB ± 0% 0.1kB ± 0% -99.68% (p=0.002 n=6+6) DSEPassBlock-4 560kB ± 0% 4kB ± 0% -99.34% (p=0.026 n=5+6) CSEPass-4 189kB ± 0% 189kB ± 0% ~ (all equal) CSEPassBlock-4 3.10MB ± 0% 3.10MB ± 0% ~ (p=0.444 n=5+5) DeadcodePass-4 10.5kB ± 0% 10.5kB ± 0% ~ (all equal) DeadcodePassBlock-4 164kB ± 0% 164kB ± 0% ~ (all equal) MultiPass-4 240kB ± 0% 199kB ± 0% -17.06% (p=0.002 n=6+6) MultiPassBlock-4 3.60MB ± 0% 2.99MB ± 0% -17.06% (p=0.002 n=6+6) name old allocs/op new allocs/op delta DSEPass-4 8.00 ± 0% 4.00 ± 0% -50.00% (p=0.002 n=6+6) DSEPassBlock-4 240 ± 0% 120 ± 0% -50.00% (p=0.002 n=6+6) CSEPass-4 9.00 ± 0% 9.00 ± 0% ~ (all equal) CSEPassBlock-4 1.35k ± 0% 1.35k ± 0% ~ (all equal) DeadcodePass-4 3.00 ± 0% 3.00 ± 0% ~ (all equal) DeadcodePassBlock-4 9.00 ± 0% 9.00 ± 0% ~ (all equal) MultiPass-4 11.0 ± 0% 10.0 ± 0% -9.09% (p=0.002 n=6+6) MultiPassBlock-4 165 ± 0% 150 ± 0% -9.09% (p=0.002 n=6+6) Change-Id: I43860687c88f33605eb1415f36473c5cfe8fde4a Reviewed-on: https://go-review.googlesource.com/98449 Run-TryBot: Daniel Martí TryBot-Result: Gobot Gobot Reviewed-by: Josh Bleecher Snyder --- src/cmd/compile/internal/ssa/cache.go | 3 +- src/cmd/compile/internal/ssa/deadstore.go | 3 +- src/cmd/compile/internal/ssa/func.go | 37 +++++++++++++++++++---- src/cmd/compile/internal/ssa/regalloc.go | 6 ++-- src/cmd/compile/internal/ssa/sparsemap.go | 4 +++ 5 files changed, 43 insertions(+), 10 deletions(-) diff --git a/src/cmd/compile/internal/ssa/cache.go b/src/cmd/compile/internal/ssa/cache.go index e149f6a4c5..b30af6304d 100644 --- a/src/cmd/compile/internal/ssa/cache.go +++ b/src/cmd/compile/internal/ssa/cache.go @@ -22,7 +22,8 @@ type Cache struct { stackAllocState *stackAllocState domblockstore []ID // scratch space for computing dominators - scrSparse []*sparseSet // scratch sparse sets to be re-used. + scrSparseSet []*sparseSet // scratch sparse sets to be re-used. + scrSparseMap []*sparseMap // scratch sparse maps to be re-used. ValueToProgAfter []*obj.Prog debugState debugState diff --git a/src/cmd/compile/internal/ssa/deadstore.go b/src/cmd/compile/internal/ssa/deadstore.go index bbeb990f17..e1ce980e5c 100644 --- a/src/cmd/compile/internal/ssa/deadstore.go +++ b/src/cmd/compile/internal/ssa/deadstore.go @@ -19,7 +19,8 @@ func dse(f *Func) { defer f.retSparseSet(loadUse) storeUse := f.newSparseSet(f.NumValues()) defer f.retSparseSet(storeUse) - shadowed := newSparseMap(f.NumValues()) // TODO: cache + shadowed := f.newSparseMap(f.NumValues()) + defer f.retSparseMap(shadowed) for _, b := range f.Blocks { // Find all the stores in this block. Categorize their uses: // loadUse contains stores which are used by a subsequent load. diff --git a/src/cmd/compile/internal/ssa/func.go b/src/cmd/compile/internal/ssa/func.go index 3868ee37d9..bde36a5b3f 100644 --- a/src/cmd/compile/internal/ssa/func.go +++ b/src/cmd/compile/internal/ssa/func.go @@ -84,9 +84,9 @@ func (f *Func) NumValues() int { // newSparseSet returns a sparse set that can store at least up to n integers. func (f *Func) newSparseSet(n int) *sparseSet { - for i, scr := range f.Cache.scrSparse { + for i, scr := range f.Cache.scrSparseSet { if scr != nil && scr.cap() >= n { - f.Cache.scrSparse[i] = nil + f.Cache.scrSparseSet[i] = nil scr.clear() return scr } @@ -94,15 +94,40 @@ func (f *Func) newSparseSet(n int) *sparseSet { return newSparseSet(n) } -// retSparseSet returns a sparse set to the config's cache of sparse sets to be reused by f.newSparseSet. +// retSparseSet returns a sparse set to the config's cache of sparse +// sets to be reused by f.newSparseSet. func (f *Func) retSparseSet(ss *sparseSet) { - for i, scr := range f.Cache.scrSparse { + for i, scr := range f.Cache.scrSparseSet { if scr == nil { - f.Cache.scrSparse[i] = ss + f.Cache.scrSparseSet[i] = ss return } } - f.Cache.scrSparse = append(f.Cache.scrSparse, ss) + f.Cache.scrSparseSet = append(f.Cache.scrSparseSet, ss) +} + +// newSparseMap returns a sparse map that can store at least up to n integers. +func (f *Func) newSparseMap(n int) *sparseMap { + for i, scr := range f.Cache.scrSparseMap { + if scr != nil && scr.cap() >= n { + f.Cache.scrSparseMap[i] = nil + scr.clear() + return scr + } + } + return newSparseMap(n) +} + +// retSparseMap returns a sparse map to the config's cache of sparse +// sets to be reused by f.newSparseMap. +func (f *Func) retSparseMap(ss *sparseMap) { + for i, scr := range f.Cache.scrSparseMap { + if scr == nil { + f.Cache.scrSparseMap[i] = ss + return + } + } + f.Cache.scrSparseMap = append(f.Cache.scrSparseMap, ss) } // newValue allocates a new Value with the given fields and places it at the end of b.Values. diff --git a/src/cmd/compile/internal/ssa/regalloc.go b/src/cmd/compile/internal/ssa/regalloc.go index abc4e60d7c..ea88da3b9c 100644 --- a/src/cmd/compile/internal/ssa/regalloc.go +++ b/src/cmd/compile/internal/ssa/regalloc.go @@ -2183,8 +2183,10 @@ func (s *regAllocState) computeLive() { s.desired = make([]desiredState, f.NumBlocks()) var phis []*Value - live := newSparseMap(f.NumValues()) - t := newSparseMap(f.NumValues()) + live := f.newSparseMap(f.NumValues()) + defer f.retSparseMap(live) + t := f.newSparseMap(f.NumValues()) + defer f.retSparseMap(t) // Keep track of which value we want in each register. var desired desiredState diff --git a/src/cmd/compile/internal/ssa/sparsemap.go b/src/cmd/compile/internal/ssa/sparsemap.go index 973ab3d434..c42fb99c7a 100644 --- a/src/cmd/compile/internal/ssa/sparsemap.go +++ b/src/cmd/compile/internal/ssa/sparsemap.go @@ -26,6 +26,10 @@ func newSparseMap(n int) *sparseMap { return &sparseMap{dense: nil, sparse: make([]int32, n)} } +func (s *sparseMap) cap() int { + return len(s.sparse) +} + func (s *sparseMap) size() int { return len(s.dense) } -- 2.48.1