cmd/compile: Tinkering with schedule for debug and regalloc
cmd/compile: Tinkering with schedule for debug and regalloc

This adds a heap-based proper priority queue to the
scheduler which made a relatively easy to test quite a few
heuristics that "ought to work well".  For go tools
themselves (which may not be representative) the heuristic
that works best is (1) in line-number-order, then (2) from
more to fewer args, then (3) in variable ID order.  Trying
to improve this with information about use at end of
blocks turned out to be fruitless -- all of my naive
attempts at using that information turned out worse than
ignoring it.  I can confirm that the stores-early heuristic
tends to help; removing it makes the results slightly worse.

My metric is code size reduction, which I take to mean fewer
spills from register allocation.  It's not uniform.
Here's the endpoints for "vet" from one set of pretty-good
heuristics (this is representative at least).

-2208 time.parse 13472 15680 -14.081633%
-1514 runtime.pclntab 1002058 1003572 -0.150861%
-352 time.Time.AppendFormat 9952 10304 -3.416149%
-112 runtime.runGCProg 1984 2096 -5.343511%
-64 regexp/syntax.(*parser).factor 7264 7328 -0.873362%
-44 go.string.alldata 238630 238674 -0.018435%

48 math/big.(*Float).round 1376 1328 3.614458%
48 text/tabwriter.(*Writer).writeLines 1232 1184 4.054054%
48 math/big.shr 832 784 6.122449%
88 go.func.* 75174 75086 0.117199%
96 time.Date 1968 1872 5.128205%

Overall there appears to be an 0.1% decrease in text size.
No timings yet, and given the distribution of size reductions
it might make sense to wait on those.

addr2line  text (code) = -4392 bytes (-0.156273%)
api  text (code) = -5502 bytes (-0.147644%)
asm  text (code) = -5254 bytes (-0.187810%)
cgo  text (code) = -4886 bytes (-0.148846%)
compile  text (code) = -1577 bytes (-0.019346%) * changed
cover  text (code) = -5236 bytes (-0.137992%)
dist  text (code) = -5015 bytes (-0.167829%)
doc  text (code) = -5180 bytes (-0.182121%)
fix  text (code) = -5000 bytes (-0.215148%)
link  text (code) = -5092 bytes (-0.152712%)
newlink  text (code) = -5204 bytes (-0.196986%)
nm  text (code) = -4398 bytes (-0.156018%)
objdump  text (code) = -4582 bytes (-0.155046%)
pack  text (code) = -4503 bytes (-0.294287%)
pprof  text (code) = -6314 bytes (-0.085177%)
trace  text (code) = -5856 bytes (-0.097818%)
vet  text (code) = -5696 bytes (-0.117334%)
yacc  text (code) = -4971 bytes (-0.213817%)

This leaves me sorely tempted to look into a "real" scheduler
to try to do a better job, but I think it might make more
sense to look into getting loop information into the
register allocator instead.

Fixes #14577.

Change-Id: I5238b83284ce76dea1eb94084a8cd47277db6827
Reviewed-on: https://go-review.googlesource.com/20240
Run-TryBot: David Chase <ae171625adc8645b8b79b7e405a6da5aba5341e0@google.com>
TryBot-Result: Gobot Gobot <66cb808b70d30c07676d5e946fee83fd561249e5@golang.org>
Reviewed-by: Keith Randall <8c99c3a9284e493be632950b84cd789d08ed3e9d@golang.org>

derekmarcotte/go,miolini/go,golang/go,goodlang/good,codestation/go,vsekhar/elastic-go,cloudflare/go,nawawi/go,cloudflare/go,linux-on-ibm-z/go,akutz/go,linux-on-ibm-z/go,polyverse-security/go,golang/go,golang/go,cloudflare/go,theif519/go,polyverse-security/go,miolini/go,CAFxX/go,vanloswang/go,nawawi/go,derekmarcotte/go,momchil-velikov/go,cloudflare/go,ganboing/go-esx,4ad/go,nawawi/go,vanloswang/go,josharian/go,derekmarcotte/go,vsekhar/elastic-go,akutz/go,ganboing/go-esx,christopher-henderson/Go,linux-on-ibm-z/go,derekmarcotte/go,suncycheng/go,CAFxX/go,momchil-velikov/go,Cofyc/go,ImJasonH/go,4ad/go,Samurais/go,Cofyc/go,josharian/go,CAFxX/go,Cofyc/go,vanloswang/go,Samurais/go,4ad/go,goodlang/good,polyverse-security/go,ImJasonH/go,Cofyc/go,ImJasonH/go,miolini/go,suncycheng/go,4ad/go,suncycheng/go,4ad/go,derekmarcotte/go,vanloswang/go,ImJasonH/go,goodlang/good,josharian/go,codestation/go,derekmarcotte/go,vsekhar/elastic-go,CAFxX/go,josharian/go,nawawi/go,codestation/go,Samurais/go,vanloswang/go,nawawi/go,theif519/go,Samurais/go,ImJasonH/go,suncycheng/go,goodlang/good,ImJasonH/go,miolini/go,Samurais/go,akutz/go,miolini/go,codestation/go,theif519/go,CAFxX/go,linux-on-ibm-z/go,miolini/go,polyverse-security/go,akutz/go,ImJasonH/go,Cofyc/go,ganboing/go-esx,linux-on-ibm-z/go,vanloswang/go,vanloswang/go,goodlang/good,akutz/go,vsekhar/elastic-go,polyverse-security/go,miolini/go,golang/go,momchil-velikov/go,akutz/go,cloudflare/go,4ad/go,momchil-velikov/go,derekmarcotte/go,codestation/go,momchil-velikov/go,ganboing/go-esx,theif519/go,suncycheng/go,theif519/go,CAFxX/go,4ad/go,suncycheng/go,CAFxX/go,ganboing/go-esx,golang/go,4ad/go,cloudflare/go,polyverse-security/go,suncycheng/go,derekmarcotte/go,Cofyc/go,josharian/go,goodlang/good,nawawi/go,theif519/go,golang/go,Cofyc/go,ganboing/go-esx,akutz/go,theif519/go,linux-on-ibm-z/go,ImJasonH/go,momchil-velikov/go,nawawi/go,cloudflare/go,akutz/go,goodlang/good,codestation/go,ganboing/go-esx,Samurais/go,Samurais/go,vsekhar/elastic-go,codestation/go,vsekhar/elastic-go,polyverse-security/go,cloudflare/go,golang/go,miolini/go,vsekhar/elastic-go,ganboing/go-esx,linux-on-ibm-z/go,CAFxX/go,polyverse-security/go,linux-on-ibm-z/go,codestation/go,golang/go,momchil-velikov/go,nawawi/go,Samurais/go,Cofyc/go,suncycheng/go,josharian/go,momchil-velikov/go,theif519/go,goodlang/good,vanloswang/go,vsekhar/elastic-go,josharian/go,josharian/go