diff options
author | Josh Bleecher Snyder <josharian@gmail.com> | 2016-03-25 07:33:39 -0700 |
---|---|---|
committer | Josh Bleecher Snyder <josharian@gmail.com> | 2016-03-25 15:41:10 +0000 |
commit | 41e176fbe09de9487fad9577df8222d2073d6d21 (patch) | |
tree | bf49724427092d0b40346a3a8cc9de15eba213ed /src/cmd/compile/internal/ssa/schedule.go | |
parent | 967b9940b4695f4d21e1f8484cbc7a5b89cce076 (diff) | |
download | go-41e176fbe09de9487fad9577df8222d2073d6d21.tar.gz go-41e176fbe09de9487fad9577df8222d2073d6d21.zip |
cmd/compile/ssa: generate less garbage in schedule
Passes toolstash -cmp.
name old alloc/op new alloc/op delta
Template 58.5MB ± 0% 57.8MB ± 0% -1.15% (p=0.000 n=10+10)
Unicode 41.3MB ± 0% 41.2MB ± 0% -0.17% (p=0.000 n=10+10)
GoTypes 196MB ± 0% 193MB ± 0% -1.26% (p=0.000 n=10+10)
Compiler 863MB ± 0% 850MB ± 0% -1.49% (p=0.000 n=10+10)
name old allocs/op new allocs/op delta
Template 522k ± 0% 507k ± 0% -2.99% (p=0.000 n=10+10)
Unicode 403k ± 0% 401k ± 0% -0.42% (p=0.000 n=10+10)
GoTypes 1.58M ± 0% 1.52M ± 0% -3.61% (p=0.000 n=10+10)
Compiler 6.47M ± 0% 6.17M ± 0% -4.62% (p=0.000 n=10+10)
Change-Id: Ia7a6242e8d226b41966c344d253814dcce6424a8
Reviewed-on: https://go-review.googlesource.com/21141
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
Diffstat (limited to 'src/cmd/compile/internal/ssa/schedule.go')
-rw-r--r-- | src/cmd/compile/internal/ssa/schedule.go | 47 |
1 files changed, 25 insertions, 22 deletions
diff --git a/src/cmd/compile/internal/ssa/schedule.go b/src/cmd/compile/internal/ssa/schedule.go index 8124823040..765f0c1277 100644 --- a/src/cmd/compile/internal/ssa/schedule.go +++ b/src/cmd/compile/internal/ssa/schedule.go @@ -16,8 +16,8 @@ const ( ) type ValHeap struct { - a []*Value - less func(a, b *Value) bool + a []*Value + score []int8 } func (h ValHeap) Len() int { return len(h.a) } @@ -36,7 +36,24 @@ func (h *ValHeap) Pop() interface{} { h.a = old[0 : n-1] return x } -func (h ValHeap) Less(i, j int) bool { return h.less(h.a[i], h.a[j]) } +func (h ValHeap) Less(i, j int) bool { + x := h.a[i] + y := h.a[j] + sx := h.score[x.ID] + sy := h.score[y.ID] + if c := sx - sy; c != 0 { + return c > 0 // higher score comes later. + } + if x.Line != y.Line { // Favor in-order line stepping + return x.Line > y.Line + } + if x.Op != OpPhi { + if c := len(x.Args) - len(y.Args); c != 0 { + return c < 0 // smaller args comes later + } + } + return x.ID > y.ID +} // Schedule the Values in each Block. After this phase returns, the // order of b.Values matters and is the order in which those values @@ -48,6 +65,9 @@ func schedule(f *Func) { // by values that have not been scheduled yet. uses := make([]int32, f.NumValues()) + // reusable priority queue + priq := new(ValHeap) + // "priority" for a value score := make([]int8, f.NumValues()) @@ -156,25 +176,8 @@ func schedule(f *Func) { // To put things into a priority queue // The values that should come last are least. - priq := &ValHeap{ - a: make([]*Value, 0, 8), // TODO allocate once and reuse. - less: func(x, y *Value) bool { - sx := score[x.ID] - sy := score[y.ID] - if c := sx - sy; c != 0 { - return c > 0 // higher score comes later. - } - if x.Line != y.Line { // Favor in-order line stepping - return x.Line > y.Line - } - if x.Op != OpPhi { - if c := len(x.Args) - len(y.Args); c != 0 { - return c < 0 // smaller args comes later - } - } - return x.ID > y.ID - }, - } + priq.score = score + priq.a = priq.a[:0] // Initialize priority queue with schedulable values. for _, v := range b.Values { |