From c87a62f32bc5080c6656d3f80e2da8d5c63ed55b Mon Sep 17 00:00:00 2001 From: David Chase Date: Sat, 30 Jan 2016 17:37:38 -0500 Subject: [PATCH] [dev.ssa] cmd/compile: reducing alloc footprint of dominator calc Converted working slices of pointer into slices of pointer index. Half the size (on 64-bit machine) and no pointers to trace if GC occurs while they're live. TODO - could expose slice mapping ID->*Block; some dom clients also construct these. Minor optimization in regalloc that cuts allocation count. Minor optimization in compile.go that cuts calls to Sprintf. Change-Id: I28f0bfed422b7344af333dc52ea272441e28e463 Reviewed-on: https://go-review.googlesource.com/19104 Run-TryBot: Todd Neal TryBot-Result: Gobot Gobot Reviewed-by: Todd Neal --- src/cmd/compile/internal/ssa/compile.go | 31 ++++--- src/cmd/compile/internal/ssa/dom.go | 103 ++++++++++++----------- src/cmd/compile/internal/ssa/regalloc.go | 3 + 3 files changed, 74 insertions(+), 63 deletions(-) diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go index 99e3c2b01e..e602d8f5b3 100644 --- a/src/cmd/compile/internal/ssa/compile.go +++ b/src/cmd/compile/internal/ssa/compile.go @@ -57,25 +57,24 @@ func Compile(f *Func) { tStart := time.Now() p.fn(f) - tEnd := time.Now() - time := tEnd.Sub(tStart).Nanoseconds() - var stats string - if logMemStats { - var mEnd runtime.MemStats - runtime.ReadMemStats(&mEnd) - nBytes := mEnd.TotalAlloc - mStart.TotalAlloc - nAllocs := mEnd.Mallocs - mStart.Mallocs - stats = fmt.Sprintf("[%d ns %d allocs %d bytes]", time, nAllocs, nBytes) - } else { - stats = fmt.Sprintf("[%d ns]", time) - } + if f.Log() || f.Config.HTML != nil { + tEnd := time.Now() + + time := tEnd.Sub(tStart).Nanoseconds() + var stats string + if logMemStats { + var mEnd runtime.MemStats + runtime.ReadMemStats(&mEnd) + nBytes := mEnd.TotalAlloc - mStart.TotalAlloc + nAllocs := mEnd.Mallocs - mStart.Mallocs + stats = fmt.Sprintf("[%d ns %d allocs %d bytes]", time, nAllocs, nBytes) + } else { + stats = fmt.Sprintf("[%d ns]", time) + } - if f.Log() { f.Logf(" pass %s end %s\n", p.name, stats) - } - printFunc(f) - if f.Config.HTML != nil { + printFunc(f) f.Config.HTML.WriteFunc(fmt.Sprintf("after %s %s", phaseName, stats), f) } checkFunc(f) diff --git a/src/cmd/compile/internal/ssa/dom.go b/src/cmd/compile/internal/ssa/dom.go index 0d342d184e..50ff472ca3 100644 --- a/src/cmd/compile/internal/ssa/dom.go +++ b/src/cmd/compile/internal/ssa/dom.go @@ -59,21 +59,30 @@ type linkedBlocks func(*Block) []*Block // from block id to an int indicating the order the block was reached or // notFound if the block was not reached. order contains a mapping from dfnum // to block. -func dfs(entries []*Block, succFn linkedBlocks) (dfnum []int, order []*Block, parent []*Block) { +func dfs(entries []*Block, succFn linkedBlocks) (fromID []*Block, dfnum []int32, order []ID, parent []ID) { maxBlockID := entries[0].Func.NumBlocks() - dfnum = make([]int, maxBlockID) - order = make([]*Block, maxBlockID) - parent = make([]*Block, maxBlockID) + dfnum = make([]int32, maxBlockID) + order = make([]ID, maxBlockID) + parent = make([]ID, maxBlockID) + fromID = make([]*Block, maxBlockID) - n := 0 + for _, entry := range entries[0].Func.Blocks { + eid := entry.ID + if fromID[eid] != nil { + panic("Colliding entry IDs") + } + fromID[eid] = entry + } + + n := int32(0) s := make([]*Block, 0, 256) for _, entry := range entries { if dfnum[entry.ID] != notFound { continue // already found from a previous entry } s = append(s, entry) - parent[entry.ID] = entry + parent[entry.ID] = entry.ID for len(s) > 0 { node := s[len(s)-1] s = s[:len(s)-1] @@ -83,12 +92,12 @@ func dfs(entries []*Block, succFn linkedBlocks) (dfnum []int, order []*Block, pa // if it has a dfnum, we've already visited it if dfnum[w.ID] == notFound { s = append(s, w) - parent[w.ID] = node + parent[w.ID] = node.ID dfnum[w.ID] = notExplored } } dfnum[node.ID] = n - order[n] = node + order[n] = node.ID } } @@ -143,77 +152,77 @@ func dominatorsLT(entries []*Block, predFn linkedBlocks, succFn linkedBlocks) [] // Step 1. Carry out a depth first search of the problem graph. Number // the vertices from 1 to n as they are reached during the search. - dfnum, vertex, parent := dfs(entries, succFn) + fromID, dfnum, vertex, parent := dfs(entries, succFn) maxBlockID := entries[0].Func.NumBlocks() - semi := make([]*Block, maxBlockID) - samedom := make([]*Block, maxBlockID) + semi := make([]ID, maxBlockID) + samedom := make([]ID, maxBlockID) + ancestor := make([]ID, maxBlockID) + best := make([]ID, maxBlockID) + bucket := make([]ID, maxBlockID) idom := make([]*Block, maxBlockID) - ancestor := make([]*Block, maxBlockID) - best := make([]*Block, maxBlockID) - bucket := make([]*Block, maxBlockID) // Step 2. Compute the semidominators of all vertices by applying // Theorem 4. Carry out the computation vertex by vertex in decreasing // order by number. for i := maxBlockID - 1; i > 0; i-- { w := vertex[i] - if w == nil { + if w == 0 { continue } - if dfnum[w.ID] == notFound { + if dfnum[w] == notFound { // skip unreachable node continue } // Step 3. Implicitly define the immediate dominator of each // vertex by applying Corollary 1. (reordered) - for v := bucket[w.ID]; v != nil; v = bucket[v.ID] { + for v := bucket[w]; v != 0; v = bucket[v] { u := eval(v, ancestor, semi, dfnum, best) - if semi[u.ID] == semi[v.ID] { - idom[v.ID] = w // true dominator + if semi[u] == semi[v] { + idom[v] = fromID[w] // true dominator } else { - samedom[v.ID] = u // v has same dominator as u + samedom[v] = u // v has same dominator as u } } - p := parent[w.ID] + p := parent[w] s := p // semidominator - var sp *Block + var sp ID // calculate the semidominator of w - for _, v := range w.Preds { + for _, v := range predFn(fromID[w]) { if dfnum[v.ID] == notFound { // skip unreachable predecessor continue } - if dfnum[v.ID] <= dfnum[w.ID] { - sp = v + if dfnum[v.ID] <= dfnum[w] { + sp = v.ID } else { - sp = semi[eval(v, ancestor, semi, dfnum, best).ID] + sp = semi[eval(v.ID, ancestor, semi, dfnum, best)] } - if dfnum[sp.ID] < dfnum[s.ID] { + if dfnum[sp] < dfnum[s] { s = sp } } // link - ancestor[w.ID] = p - best[w.ID] = w + ancestor[w] = p + best[w] = w - semi[w.ID] = s - if semi[s.ID] != parent[s.ID] { - bucket[w.ID] = bucket[s.ID] - bucket[s.ID] = w + semi[w] = s + if semi[s] != parent[s] { + bucket[w] = bucket[s] + bucket[s] = w } } // Final pass of step 3 - for v := bucket[0]; v != nil; v = bucket[v.ID] { - idom[v.ID] = bucket[0] + for v := bucket[0]; v != 0; v = bucket[v] { + idom[v] = fromID[bucket[0]] } // Step 4. Explictly define the immediate dominator of each vertex, @@ -221,28 +230,28 @@ func dominatorsLT(entries []*Block, predFn linkedBlocks, succFn linkedBlocks) [] // number. for i := 1; i < maxBlockID-1; i++ { w := vertex[i] - if w == nil { + if w == 0 { continue } - // w has the same dominator as samedom[w.ID] - if samedom[w.ID] != nil { - idom[w.ID] = idom[samedom[w.ID].ID] + // w has the same dominator as samedom[w] + if samedom[w] != 0 { + idom[w] = idom[samedom[w]] } } return idom } // eval function from LT paper with path compression -func eval(v *Block, ancestor []*Block, semi []*Block, dfnum []int, best []*Block) *Block { - a := ancestor[v.ID] - if ancestor[a.ID] != nil { - b := eval(a, ancestor, semi, dfnum, best) - ancestor[v.ID] = ancestor[a.ID] - if dfnum[semi[b.ID].ID] < dfnum[semi[best[v.ID].ID].ID] { - best[v.ID] = b +func eval(v ID, ancestor []ID, semi []ID, dfnum []int32, best []ID) ID { + a := ancestor[v] + if ancestor[a] != 0 { + bid := eval(a, ancestor, semi, dfnum, best) + ancestor[v] = ancestor[a] + if dfnum[semi[bid]] < dfnum[semi[best[v]]] { + best[v] = bid } } - return best[v.ID] + return best[v] } // dominators computes the dominator tree for f. It returns a slice diff --git a/src/cmd/compile/internal/ssa/regalloc.go b/src/cmd/compile/internal/ssa/regalloc.go index 2d88850999..e1f8dd1935 100644 --- a/src/cmd/compile/internal/ssa/regalloc.go +++ b/src/cmd/compile/internal/ssa/regalloc.go @@ -1624,6 +1624,9 @@ func (s *regAllocState) computeLive() { } // The live set has changed, update it. l := s.live[p.ID][:0] + if cap(l) == 0 { + l = make([]liveInfo, 0, len(t.contents())) + } for _, e := range t.contents() { l = append(l, liveInfo{e.key, e.val}) } -- 2.48.1