code review 6828056: cmd/8g: eliminate obviously useless temps before regopt.

cmd/8g: eliminate obviously useless temps before regopt.

This patch introduces a sort of pre-regopt peephole optimization.
When a temporary is introduced that just holds a value for the
duration of the next instruction and is otherwise unused, we
elide it to make the job of regopt easier.

Since x86 has very few registers, this situation happens very
often. The result is large savings in stack variables for
arithmetic-heavy functions.

crypto/aes

benchmark                 old ns/op    new ns/op    delta
BenchmarkEncrypt               1301          392  -69.87%
BenchmarkDecrypt               1309          368  -71.89%
BenchmarkExpand                2913         1036  -64.44%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkEncrypt              12.29        40.74    3.31x
BenchmarkDecrypt              12.21        43.37    3.55x

crypto/md5

benchmark                 old ns/op    new ns/op    delta
BenchmarkHash8Bytes            1761          914  -48.10%
BenchmarkHash1K               16912         5570  -67.06%
BenchmarkHash8K              123895        38286  -69.10%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkHash8Bytes            4.54         8.75    1.93x
BenchmarkHash1K               60.55       183.83    3.04x
BenchmarkHash8K               66.12       213.97    3.24x

bench/go1

benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17    8364835000   8303154000   -0.74%
BenchmarkFannkuch11      7511723000   6381729000  -15.04%
BenchmarkGobDecode         27764090     27103270   -2.38%
BenchmarkGobEncode         11240880     11184370   -0.50%
BenchmarkGzip            1470224000    856668400  -41.73%
BenchmarkGunzip           240660800    201697300  -16.19%
BenchmarkJSONEncode       155225800    185571900  +19.55%
BenchmarkJSONDecode       243347900    282123000  +15.93%
BenchmarkMandelbrot200     12240970     12201880   -0.32%
BenchmarkParse              8837445      8765210   -0.82%
BenchmarkRevcomp         2556310000   1868566000  -26.90%
BenchmarkTemplate         389298000    379792000   -2.44%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkGobDecode            27.64        28.32    1.02x
BenchmarkGobEncode            68.28        68.63    1.01x
BenchmarkGzip                 13.20        22.65    1.72x
BenchmarkGunzip               80.63        96.21    1.19x
BenchmarkJSONEncode           12.50        10.46    0.84x
BenchmarkJSONDecode            7.97         6.88    0.86x
BenchmarkParse                 6.55         6.61    1.01x
BenchmarkRevcomp              99.43       136.02    1.37x
BenchmarkTemplate              4.98         5.11    1.03x

Fixes issue 4035.

[remyoudompheng, 2012-11-11 00:17:13]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[remyoudompheng, 2012-11-11 00:20:00]

This patch gives probably better results than the solutions suggested in issue
4035:
* increasing NVAR has large effects on compiler performance (I think it's
O(NVAR²) in regopt)
* reusing temporaries may make regopt less efficient.

This proposal does not have these drawbacks and maybe even improves regopt
efficiency: some additional registerization is observed in cases where the
variable count does not reach NVAR (currently 160).

[remyoudompheng, 2012-11-11 00:20:52]

The Json benchmark is slwoed down but I suppose it's the usual flakiness of this
benchmark due to stack frame size change (Gob is usually also flaky in the same
way).

[minux1, 2012-11-11 08:26:32]

https://codereview.appspot.com/6828056/diff/1002/src/cmd/8g/reg.c
File src/cmd/8g/reg.c (right):

https://codereview.appspot.com/6828056/diff/1002/src/cmd/8g/reg.c#newcode1703
src/cmd/8g/reg.c:1703: h = 2166136261;
h = 2166136261U;

or gcc will complain when compiled on 32-bit machines.

https://codereview.appspot.com/6828056/diff/1002/src/cmd/8g/reg.c#newcode1725
src/cmd/8g/reg.c:1725: uint16 counts[1<<16]; // A hash table to count variable
occurences.
i'm a little concerned about overflowing the uint16.
although it will be very very rare, if happens at all.

i think you only need to record three states, used once,
used twice and more than twice. perhaps two bits suffice
for each entry.

[remyoudompheng, 2012-11-11 11:08:01]

https://codereview.appspot.com/6828056/diff/1002/src/cmd/8g/reg.c
File src/cmd/8g/reg.c (right):

https://codereview.appspot.com/6828056/diff/1002/src/cmd/8g/reg.c#newcode1703
src/cmd/8g/reg.c:1703: h = 2166136261;
On 2012/11/11 08:26:32, minux wrote:
> h = 2166136261U;
> 
> or gcc will complain when compiled on 32-bit machines.

Done.

https://codereview.appspot.com/6828056/diff/1002/src/cmd/8g/reg.c#newcode1725
src/cmd/8g/reg.c:1725: uint16 counts[1<<16]; // A hash table to count variable
occurences.
On 2012/11/11 08:26:32, minux wrote:
> i'm a little concerned about overflowing the uint16.
> although it will be very very rare, if happens at all.
> 
> i think you only need to record three states, used once,
> used twice and more than twice. perhaps two bits suffice
> for each entry.
> 

Done. I did not bother shrinking the array. Stack space is rather cheap.

[remyoudompheng, 2012-11-11 11:08:01]

Hello golang-dev@googlegroups.com, minux.ma@gmail.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[rsc, 2012-11-12 20:49:58]

LGTM

https://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c
File src/cmd/8g/reg.c (right):

https://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1699
src/cmd/8g/reg.c:1699: fnv1(Sym *sym) {
{ on next line
same for next few functions
sorry

https://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1721
src/cmd/8g/reg.c:1721: *   OP reg1, reg2
add
 * this reduces the number of variables that the register optimizer
 * sees, which lets it do a better job and makes it less likely to turn
 * itself off.

https://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1725
src/cmd/8g/reg.c:1725: uint16 counts[1<<16]; // A hash table to count variable
occurences.
might as well be byte. also please make it static byte to avoid the stack
overhead.

https://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1735
src/cmd/8g/reg.c:1735: for(i=0; i<(1<<16); i++)
i<nelem(counts)

https://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1752
src/cmd/8g/reg.c:1752: // Eliminate single-use stack variables.
single-write, single-read stack variables.

[remyoudompheng, 2012-11-13 06:39:45]

*** Submitted as http://code.google.com/p/go/source/detail?r=27bce3a1244d ***

cmd/8g: eliminate obviously useless temps before regopt.

This patch introduces a sort of pre-regopt peephole optimization.
When a temporary is introduced that just holds a value for the
duration of the next instruction and is otherwise unused, we
elide it to make the job of regopt easier.

Since x86 has very few registers, this situation happens very
often. The result is large savings in stack variables for
arithmetic-heavy functions.

crypto/aes

benchmark                 old ns/op    new ns/op    delta
BenchmarkEncrypt               1301          392  -69.87%
BenchmarkDecrypt               1309          368  -71.89%
BenchmarkExpand                2913         1036  -64.44%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkEncrypt              12.29        40.74    3.31x
BenchmarkDecrypt              12.21        43.37    3.55x

crypto/md5

benchmark                 old ns/op    new ns/op    delta
BenchmarkHash8Bytes            1761          914  -48.10%
BenchmarkHash1K               16912         5570  -67.06%
BenchmarkHash8K              123895        38286  -69.10%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkHash8Bytes            4.54         8.75    1.93x
BenchmarkHash1K               60.55       183.83    3.04x
BenchmarkHash8K               66.12       213.97    3.24x

bench/go1

benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17    8364835000   8303154000   -0.74%
BenchmarkFannkuch11      7511723000   6381729000  -15.04%
BenchmarkGobDecode         27764090     27103270   -2.38%
BenchmarkGobEncode         11240880     11184370   -0.50%
BenchmarkGzip            1470224000    856668400  -41.73%
BenchmarkGunzip           240660800    201697300  -16.19%
BenchmarkJSONEncode       155225800    185571900  +19.55%
BenchmarkJSONDecode       243347900    282123000  +15.93%
BenchmarkMandelbrot200     12240970     12201880   -0.32%
BenchmarkParse              8837445      8765210   -0.82%
BenchmarkRevcomp         2556310000   1868566000  -26.90%
BenchmarkTemplate         389298000    379792000   -2.44%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkGobDecode            27.64        28.32    1.02x
BenchmarkGobEncode            68.28        68.63    1.01x
BenchmarkGzip                 13.20        22.65    1.72x
BenchmarkGunzip               80.63        96.21    1.19x
BenchmarkJSONEncode           12.50        10.46    0.84x
BenchmarkJSONDecode            7.97         6.88    0.86x
BenchmarkParse                 6.55         6.61    1.01x
BenchmarkRevcomp              99.43       136.02    1.37x
BenchmarkTemplate              4.98         5.11    1.03x

Fixes issue 4035.

R=golang-dev, minux.ma, rsc
CC=golang-dev
http://codereview.appspot.com/6828056

http://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c
File src/cmd/8g/reg.c (right):

http://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1699
src/cmd/8g/reg.c:1699: fnv1(Sym *sym) {
On 2012/11/12 20:49:59, rsc wrote:
> { on next line
> same for next few functions
> sorry

Done.

http://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1721
src/cmd/8g/reg.c:1721: *   OP reg1, reg2
On 2012/11/12 20:49:59, rsc wrote:
> add
>  * this reduces the number of variables that the register optimizer
>  * sees, which lets it do a better job and makes it less likely to turn
>  * itself off.

Done.

http://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1725
src/cmd/8g/reg.c:1725: uint16 counts[1<<16]; // A hash table to count variable
occurences.
On 2012/11/12 20:49:59, rsc wrote:
> might as well be byte. also please make it static byte to avoid the stack
> overhead.

Done.

http://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1735
src/cmd/8g/reg.c:1735: for(i=0; i<(1<<16); i++)
On 2012/11/12 20:49:59, rsc wrote:
> i<nelem(counts)

Done.

http://codereview.appspot.com/6828056/diff/7002/src/cmd/8g/reg.c#newcode1752
src/cmd/8g/reg.c:1752: // Eliminate single-use stack variables.
On 2012/11/12 20:49:59, rsc wrote:
> single-write, single-read stack variables.

Done.

[dave_cheney.net, 2012-11-13 07:09:58]

Really impressive speedup on a quad core (??) atom host

220887(~/go/test/bench/go1) % ~/go/misc/benchcmp {old,new}.txt
benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17    2147483647   2147483647   +0.04%
BenchmarkFannkuch11      2147483647   2147483647   -9.29%
BenchmarkGobDecode        108677050    108685200   +0.01%
BenchmarkGobEncode         45295540     46541140   +2.75%
BenchmarkGzip            2147483647   2147483647  -24.44%
BenchmarkGunzip           927877800    600955000  -35.23%
BenchmarkJSONEncode       616352600    765123600  +24.14%
BenchmarkJSONDecode      1086684000   1255016000  +15.49%
BenchmarkMandelbrot200     54324420     54281840   -0.08%
BenchmarkParse             37891240     37803220   -0.23%
BenchmarkRevcomp         2147483647   2147483647  -46.41%
BenchmarkTemplate        1609638000   1601209000   -0.52%

benchmark                  old MB/s     new MB/s  speedup
BenchmarkGobDecode             7.06         7.06    1.00x
BenchmarkGobEncode            16.95        16.49    0.97x
BenchmarkGzip                  4.39         5.81    1.32x
BenchmarkGunzip               20.91        32.29    1.54x
BenchmarkJSONEncode            3.15         2.54    0.81x
BenchmarkJSONDecode            1.79         1.55    0.87x
BenchmarkParse                 1.53         1.53    1.00x
BenchmarkRevcomp              26.98        50.35    1.87x
BenchmarkTemplate              1.21         1.21    1.00x