• Russ Cox's avatar
    cmd/gc: add temporary-merging optimization pass · fa72679f
    Russ Cox authored
    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://golang.org/cl/12829043
    fa72679f
reg.c 21.3 KB