code review 12829043: cmd/gc: add temporary-merging optimization pass

cmd/gc: add temporary-merging optimization pass

The compilers assume they can generate temporary variables
as needed to preserve the right semantics or simplify code
generation and the back end will still generate good code.
This turns out not to be true. The back ends will only
track the first 128 variables per function and give up
on the remainder. That needs to be fixed too, in a later CL.

This CL merges temporary variables with equal types and
non-overlapping lifetimes using the greedy algorithm in
Poletto and Sarkar, "Linear Scan Register Allocation",
ACM TOPLAS 1999.

The result can be striking in the right functions.

Top 20 frame size changes in a 6g godoc binary by bytes saved:

5464 1984 (-3480, -63.7%) go/build.(*Context).Import
4456 1824 (-2632, -59.1%) go/printer.(*printer).expr1
2560   80 (-2480, -96.9%) time.nextStdChunk
3496 1608 (-1888, -54.0%) go/printer.(*printer).stmt
1896  272 (-1624, -85.7%) net/http.init
2688 1400 (-1288, -47.9%) fmt.(*pp).printReflectValue
2800 1512 (-1288, -46.0%) main.main
3296 2016 (-1280, -38.8%) crypto/tls.(*Conn).clientHandshake
1664  488 (-1176, -70.7%) time.loadZoneZip
1760  608 (-1152, -65.5%) time.parse
4104 3072 (-1032, -25.1%) runtime/pprof.writeHeap
1680  712 ( -968, -57.6%) go/ast.Walk
2488 1560 ( -928, -37.3%) crypto/x509.parseCertificate
1128  392 ( -736, -65.2%) math/big.nat.divLarge
1528  864 ( -664, -43.5%) go/printer.(*printer).fieldList
1360  712 ( -648, -47.6%) regexp/syntax.(*parser).factor
2104 1528 ( -576, -27.4%) encoding/asn1.parseField
1064  504 ( -560, -52.6%) encoding/xml.(*Decoder).text
 584   48 ( -536, -91.8%) html.init
1400  864 ( -536, -38.3%) go/doc.playExample

In the same godoc build, cuts the number of functions with
too many vars from 83 to 32.

[rsc, 2013-08-13 04:09:29]

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

I'd like you to review this change to
https://code.google.com/p/go/

[rsc, 2013-08-13 04:09:34]

*** Submitted as https://code.google.com/p/go/source/detail?r=df2050eeba3a ***

cmd/gc: add temporary-merging optimization pass

The compilers assume they can generate temporary variables
as needed to preserve the right semantics or simplify code
generation and the back end will still generate good code.
This turns out not to be true. The back ends will only
track the first 128 variables per function and give up
on the remainder. That needs to be fixed too, in a later CL.

This CL merges temporary variables with equal types and
non-overlapping lifetimes using the greedy algorithm in
Poletto and Sarkar, "Linear Scan Register Allocation",
ACM TOPLAS 1999.

The result can be striking in the right functions.

Top 20 frame size changes in a 6g godoc binary by bytes saved:

5464 1984 (-3480, -63.7%) go/build.(*Context).Import
4456 1824 (-2632, -59.1%) go/printer.(*printer).expr1
2560   80 (-2480, -96.9%) time.nextStdChunk
3496 1608 (-1888, -54.0%) go/printer.(*printer).stmt
1896  272 (-1624, -85.7%) net/http.init
2688 1400 (-1288, -47.9%) fmt.(*pp).printReflectValue
2800 1512 (-1288, -46.0%) main.main
3296 2016 (-1280, -38.8%) crypto/tls.(*Conn).clientHandshake
1664  488 (-1176, -70.7%) time.loadZoneZip
1760  608 (-1152, -65.5%) time.parse
4104 3072 (-1032, -25.1%) runtime/pprof.writeHeap
1680  712 ( -968, -57.6%) go/ast.Walk
2488 1560 ( -928, -37.3%) crypto/x509.parseCertificate
1128  392 ( -736, -65.2%) math/big.nat.divLarge
1528  864 ( -664, -43.5%) go/printer.(*printer).fieldList
1360  712 ( -648, -47.6%) regexp/syntax.(*parser).factor
2104 1528 ( -576, -27.4%) encoding/asn1.parseField
1064  504 ( -560, -52.6%) encoding/xml.(*Decoder).text
 584   48 ( -536, -91.8%) html.init
1400  864 ( -536, -38.3%) go/doc.playExample

In the same godoc build, cuts the number of functions with
too many vars from 83 to 32.

R=ken2
CC=golang-dev
https://codereview.appspot.com/12829043

[ken3, 2013-08-13 10:34:32]

On 2013/08/13 04:09:34, rsc wrote:
> *** Submitted as https://code.google.com/p/go/source/detail?r=df2050eeba3a ***
> 
> cmd/gc: add temporary-merging optimization pass
> 
> The compilers assume they can generate temporary variables
> as needed to preserve the right semantics or simplify code
> generation and the back end will still generate good code.
> This turns out not to be true. The back ends will only
> track the first 128 variables per function and give up
> on the remainder. That needs to be fixed too, in a later CL.
> 
> This CL merges temporary variables with equal types and
> non-overlapping lifetimes using the greedy algorithm in
> Poletto and Sarkar, "Linear Scan Register Allocation",
> ACM TOPLAS 1999.
> 
> The result can be striking in the right functions.
> 
> Top 20 frame size changes in a 6g godoc binary by bytes saved:
> 
> 5464 1984 (-3480, -63.7%) go/build.(*Context).Import
> 4456 1824 (-2632, -59.1%) go/printer.(*printer).expr1
> 2560   80 (-2480, -96.9%) time.nextStdChunk
> 3496 1608 (-1888, -54.0%) go/printer.(*printer).stmt
> 1896  272 (-1624, -85.7%) net/http.init
> 2688 1400 (-1288, -47.9%) fmt.(*pp).printReflectValue
> 2800 1512 (-1288, -46.0%) main.main
> 3296 2016 (-1280, -38.8%) crypto/tls.(*Conn).clientHandshake
> 1664  488 (-1176, -70.7%) time.loadZoneZip
> 1760  608 (-1152, -65.5%) time.parse
> 4104 3072 (-1032, -25.1%) runtime/pprof.writeHeap
> 1680  712 ( -968, -57.6%) go/ast.Walk
> 2488 1560 ( -928, -37.3%) crypto/x509.parseCertificate
> 1128  392 ( -736, -65.2%) math/big.nat.divLarge
> 1528  864 ( -664, -43.5%) go/printer.(*printer).fieldList
> 1360  712 ( -648, -47.6%) regexp/syntax.(*parser).factor
> 2104 1528 ( -576, -27.4%) encoding/asn1.parseField
> 1064  504 ( -560, -52.6%) encoding/xml.(*Decoder).text
>  584   48 ( -536, -91.8%) html.init
> 1400  864 ( -536, -38.3%) go/doc.playExample
> 
> In the same godoc build, cuts the number of functions with
> too many vars from 83 to 32.
> 
> R=ken2
> CC=golang-dev
> https://codereview.appspot.com/12829043

lttm

[dvyukov, 2013-12-03 07:06:56]

Any idea as to why it has slowed down json by 20%?
http://goperfd.appspot.com/perfdetail?commit=df2050eeba3ae4c34b6b5c44addc3762...
http://goperfd.appspot.com/perfdetail?commit=df2050eeba3ae4c34b6b5c44addc3762...

[bradfitz, 2013-12-03 10:01:18]

Russ mentioned once before that this made the stacks smaller, and now this
benchmark hits an unlucky hot stack split.

Try cherry-picking the 8kb stack CL and it should go away.



On Mon, Dec 2, 2013 at 11:06 PM, <dvyukov@google.com> wrote:

> Any idea as to why it has slowed down json by 20%?
> http://goperfd.appspot.com/perfdetail?commit=
> df2050eeba3ae4c34b6b5c44addc3762a3e01e1c&builder=linux-
> amd64-perf&benchmark=json
> http://goperfd.appspot.com/perfdetail?commit=
> df2050eeba3ae4c34b6b5c44addc3762a3e01e1c&builder=linux-
> amd64-perf&benchmark=build
>
>
> https://codereview.appspot.com/12829043/
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-dev+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>

[dvyukov, 2013-12-03 11:06:18]

OK, makes sense

On Tue, Dec 3, 2013 at 2:01 PM, Brad Fitzpatrick <bradfitz@golang.org> wrote:
> Russ mentioned once before that this made the stacks smaller, and now this
> benchmark hits an unlucky hot stack split.
>
> Try cherry-picking the 8kb stack CL and it should go away.
>
>
>
> On Mon, Dec 2, 2013 at 11:06 PM, <dvyukov@google.com> wrote:
>>
>> Any idea as to why it has slowed down json by 20%?
>>
>>
http://goperfd.appspot.com/perfdetail?commit=df2050eeba3ae4c34b6b5c44addc3762...
>>
>>
http://goperfd.appspot.com/perfdetail?commit=df2050eeba3ae4c34b6b5c44addc3762...
>>
>>
>> https://codereview.appspot.com/12829043/
>>
>>
>> --
>>
>> ---You received this message because you are subscribed to the Google
>> Groups "golang-dev" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to golang-dev+unsubscribe@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>
>