code review 6733055: cmd/5g, cmd/6g: fix out of registers with array indexing.

cmd/5g, cmd/6g: fix out of registers with array indexing.

Compiling expressions like:
    s[s[s[s[s[s[s[s[s[s[s[s[i]]]]]]]]]]]]
make 5g and 6g run out of registers. Such expressions can arise
if a slice is used to represent a permutation and the user wants
to iterate it.

This is due to the usual problem of allocating registers before
going down the expression tree, instead of allocating them in a
postfix way.

The functions cgenr and agenr (that generate a value to a newly
allocated register instead of an existing location), are either
introduced or modified when they already existed to allocate
the new register as late as possible, and sudoaddable is disabled
for OINDEX nodes so that igen/agenr is used instead.

Update issue 4207.

[remyoudompheng, 2012-10-20 19:24:27]

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

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

[dfc, 2012-10-21 10:15:31]

./all.bash does not pass nilptr.go

# ../test
run        nilptr.go           : incorrect output
0
panic: memory reference did not panic

goroutine 1 [running]:
main.func·001(0x1c0e8, 0x10d84)
        /home/dfc/go/test/nilptr.go:46 +0x78
main.shouldPanic(0x10d84, 0x2)
        /home/dfc/go/test/nilptr.go:49 +0x50
main.main()
        /home/dfc/go/test/nilptr.go:31 +0x7c

goroutine 2 [syscall]:
created by runtime.main
        /home/dfc/go/src/pkg/runtime/proc.c:224
exit status 2

run        recover3.go         : incorrect output
unexpected fault address 0x4e20
throw: fault
[signal 0xb code=0x1 addr=0x4e20 pc=0x11550]

goroutine 1 [running]:
main.func·006(0xb6f49fb4, 0x10e74)
        /home/dfc/go/test/recover3.go:63 +0x2c
main.check(0x2cc44, 0xd, 0x10519900, 0x2d1c0, 0x17, ...)
        /home/dfc/go/test/recover3.go:48 +0x60
main.main()
        /home/dfc/go/test/recover3.go:63 +0x204

goroutine 2 [syscall]:
created by runtime.main
        /home/dfc/go/src/pkg/runtime/proc.c:224
exit status 2

[remyoudompheng, 2012-10-29 07:50:16]

On 2012/10/21 10:15:31, dfc wrote:
> ./all.bash does not pass nilptr.go

The old code in agen never checked for explicit nils for large arrays. I have
added the check.

Rémy.

[dfc, 2012-10-29 07:51:33]

Thank you.

On Mon, Oct 29, 2012 at 6:50 PM,  <remyoudompheng@gmail.com> wrote:
> On 2012/10/21 10:15:31, dfc wrote:
>>
>> ./all.bash does not pass nilptr.go
>
>
> The old code in agen never checked for explicit nils for large arrays. I
> have added the check.
>
> Rémy.
>
> http://codereview.appspot.com/6733055/

[remyoudompheng, 2012-10-29 07:55:35]

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

Please take another look.

[dfc, 2012-10-29 08:04:15]

http://codereview.appspot.com/6733055/diff/14001/src/cmd/5g/gsubr.c
File src/cmd/5g/gsubr.c (right):

http://codereview.appspot.com/6733055/diff/14001/src/cmd/5g/gsubr.c#newcode1809
src/cmd/5g/gsubr.c:1809: // disabled.
could you please leave a small comment explaining why this is disabled.

http://codereview.appspot.com/6733055/diff/14001/src/cmd/6g/gsubr.c
File src/cmd/6g/gsubr.c (right):

http://codereview.appspot.com/6733055/diff/14001/src/cmd/6g/gsubr.c#newcode1953
src/cmd/6g/gsubr.c:1953: if(n->left->type->etype == TSTRING)
is this dead code ?

[dfc, 2012-10-29 08:37:57]

linux/arm, omap4:

benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17   46192261000  45795379000   -0.86%
BenchmarkFannkuch11     34446014000  34150849000   -0.86%
BenchmarkGobDecode        115428150    113720700   -1.48%
BenchmarkGobEncode         57655040     56268920   -2.40%
BenchmarkGzip            5620087000   5498596000   -2.16%
BenchmarkGunzip          1077423000   1008453000   -6.40%
BenchmarkJSONEncode       678076200    677569600   -0.07%
BenchmarkJSONDecode      1585084000   1570160000   -0.94%
BenchmarkMandelbrot200     45711060     45711680   +0.00%
BenchmarkParse             60339960     56372060   -6.58%
BenchmarkRevcomp          126818850    128361500   +1.22%
BenchmarkTemplate        1731140000   1724090000   -0.41%

benchmark                  old MB/s     new MB/s  speedup
BenchmarkGobDecode             6.65         6.75    1.02x
BenchmarkGobEncode            13.31        13.64    1.02x
BenchmarkGzip                  3.45         3.53    1.02x
BenchmarkGunzip               18.01        19.24    1.07x
BenchmarkJSONEncode            2.86         2.86    1.00x
BenchmarkJSONDecode            1.22         1.24    1.02x
BenchmarkParse                 0.96         1.03    1.07x
BenchmarkRevcomp              20.04        19.80    0.99x
BenchmarkTemplate              1.12         1.13    1.01x

[dfc, 2012-10-29 16:51:51]

http://codereview.appspot.com/6733055/diff/14001/src/cmd/5g/cgen.c
File src/cmd/5g/cgen.c (right):

http://codereview.appspot.com/6733055/diff/14001/src/cmd/5g/cgen.c#newcode599
src/cmd/5g/cgen.c:599: USED(nr);
If nr is not used, can it be removed?

[remyoudompheng, 2012-10-30 07:14:02]

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

Please take another look.

[remyoudompheng, 2012-10-30 07:32:58]

On 2012/10/29 08:37:57, dfc wrote:
> linux/arm, omap4:
> 
> benchmark                 old ns/op    new ns/op    delta
> BenchmarkBinaryTree17   46192261000  45795379000   -0.86%
> BenchmarkFannkuch11     34446014000  34150849000   -0.86%
> BenchmarkGobDecode        115428150    113720700   -1.48%
> BenchmarkGobEncode         57655040     56268920   -2.40%
> BenchmarkGzip            5620087000   5498596000   -2.16%
> BenchmarkGunzip          1077423000   1008453000   -6.40%
> BenchmarkJSONEncode       678076200    677569600   -0.07%
> BenchmarkJSONDecode      1585084000   1570160000   -0.94%
> BenchmarkMandelbrot200     45711060     45711680   +0.00%
> BenchmarkParse             60339960     56372060   -6.58%
> BenchmarkRevcomp          126818850    128361500   +1.22%
> BenchmarkTemplate        1731140000   1724090000   -0.41%

I'm surprised to see a noticeable performance improvement.

sudoaddable is essentially unused after this patch. Its role is essentially to
implement something similar to igen for OINDEX nodes (the ODOT and ODOTPTR cases
are redundant with igen), and allow 6g to generate instructions like "MOVQ
(R8)(8*R9), R10".

[dfc, 2012-10-30 09:45:26]

> I'm surprised to see a noticeable performance improvement.

Could this be an improvement in stack usage ? If this is truly unexpected, I can
investigate further, but I am happy that there is no performance regression.
 
> sudoaddable is essentially unused after this patch. Its role is essentially to
> implement something similar to igen for OINDEX nodes (the ODOT and ODOTPTR
cases
> are redundant with igen), and allow 6g to generate instructions like "MOVQ
> (R8)(8*R9), R10".

I am very happy to see sudoaddable on its way out the door.

[DMorsing, 2012-10-30 10:41:05]

On 2012/10/30 09:45:26, dfc wrote:
> Could this be an improvement in stack usage ?

My immediate guess would be that postfix allocation of registers causes some of
the registers to be reused when they otherwise wouldn't. Makes the job of regopt
significantly easier.

[dfc, 2012-10-30 14:40:14]

Here is an analysis of the difference in stack usage between
3312fddeb739 without and with this CL applied. From my reading, the
differences are all increases in stack usage.

There is no difference in escape analysis for the same sample, non was
expected.

On Tue, Oct 30, 2012 at 9:41 PM,  <daniel.morsing@gmail.com> wrote:
> On 2012/10/30 09:45:26, dfc wrote:
>>
>> Could this be an improvement in stack usage ?
>
>
> My immediate guess would be that postfix allocation of registers causes
> some of the registers to be reused when they otherwise wouldn't. Makes
> the job of regopt significantly easier.
>
> https://codereview.appspot.com/6733055/

[dfc, 2012-10-30 14:41:39]

For clarity, this analysis was on linux/amd64 (not arm)

[remyoudompheng, 2012-10-31 05:28:51]

On arm the difference is very small. I think the difference on amd64 is just a
manifestation of a deeper problem. See http://codereview.appspot.com/6821052

[rsc, 2012-11-01 17:54:26]

LGTM

https://codereview.appspot.com/6733055/diff/15002/src/cmd/5g/cgen.c
File src/cmd/5g/cgen.c (right):

https://codereview.appspot.com/6733055/diff/15002/src/cmd/5g/cgen.c#newcode834
src/cmd/5g/cgen.c:834: *  newreg = &n
In agenr the parameter that has the register that needs freeing is the second
and is called 'a'.

It would be nice if cgenr used the same convention

void cgenr(Node *n, Node *a, Node *dst)

and also mention the need to call regfree in the comment, like in the agenr
comment.

[remyoudompheng, 2012-11-02 06:51:09]

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

cmd/5g, cmd/6g: fix out of registers with array indexing.

Compiling expressions like:
    s[s[s[s[s[s[s[s[s[s[s[s[i]]]]]]]]]]]]
make 5g and 6g run out of registers. Such expressions can arise
if a slice is used to represent a permutation and the user wants
to iterate it.

This is due to the usual problem of allocating registers before
going down the expression tree, instead of allocating them in a
postfix way.

The functions cgenr and agenr (that generate a value to a newly
allocated register instead of an existing location), are either
introduced or modified when they already existed to allocate
the new register as late as possible, and sudoaddable is disabled
for OINDEX nodes so that igen/agenr is used instead.

Update issue 4207.

R=dave, daniel.morsing, rsc
CC=golang-dev
http://codereview.appspot.com/6733055

[Nick name, 2019-08-04 15:40:20]

Not hard and I'm still doing all this with just 2g

[Nick name, 2019-08-04 15:44:25]

On 2012/10/30 09:45:26, dfc wrote:
> > I'm surprised to see a noticeable performance improvement.
> 
> Could this be an improvement in stack usage ? If this is truly unexpected, I
can
> investigate further, but I am happy that there is no performance regression.
>  
> > sudoaddable is essentially unused after this patch. Its role is essentially
to
> > implement something similar to igen for OINDEX nodes (the ODOT and ODOTPTR
> cases
> > are redundant with igen), and allow 6g to generate instructions like "MOVQ
> > (R8)(8*R9), R10".
> 
> I am very happy to see sudoaddable on its way out the door.

No I did have the 5-6 running on it so yeah if it's not out of your way go ahead