• Todd Neal's avatar
    [dev.ssa] cmd/compile/internal : Implement Lengauer-Tarjan for dominators · 078ba138
    Todd Neal authored
    Implements the simple Lengauer-Tarjan algorithm for dominator
    and post-dominator calculation.
    
    benchmark                           old ns/op     new ns/op     delta
    BenchmarkDominatorsLinear-8         1403862       1292741       -7.92%
    BenchmarkDominatorsFwdBack-8        1270633       1428285       +12.41%
    BenchmarkDominatorsManyPred-8       225932354     1530886       -99.32%
    BenchmarkDominatorsMaxPred-8        445994225     1393612       -99.69%
    BenchmarkDominatorsMaxPredVal-8     447235248     1246899       -99.72%
    BenchmarkNilCheckDeep1-8            829           1259          +51.87%
    BenchmarkNilCheckDeep10-8           2199          2397          +9.00%
    BenchmarkNilCheckDeep100-8          57325         29405         -48.70%
    BenchmarkNilCheckDeep1000-8         6625837       2933151       -55.73%
    BenchmarkNilCheckDeep10000-8        763559787     319105541     -58.21%
    
    benchmark                           old MB/s     new MB/s     speedup
    BenchmarkDominatorsLinear-8         7.12         7.74         1.09x
    BenchmarkDominatorsFwdBack-8        7.87         7.00         0.89x
    BenchmarkDominatorsManyPred-8       0.04         6.53         163.25x
    BenchmarkDominatorsMaxPred-8        0.02         7.18         359.00x
    BenchmarkDominatorsMaxPredVal-8     0.02         8.02         401.00x
    BenchmarkNilCheckDeep1-8            1.21         0.79         0.65x
    BenchmarkNilCheckDeep10-8           4.55         4.17         0.92x
    BenchmarkNilCheckDeep100-8          1.74         3.40         1.95x
    BenchmarkNilCheckDeep1000-8         0.15         0.34         2.27x
    BenchmarkNilCheckDeep10000-8        0.01         0.03         3.00x
    
    Change-Id: Icec3d774422a9bc64914779804c8c0ab73aa72bf
    Reviewed-on: https://go-review.googlesource.com/11971Reviewed-by: 's avatarKeith Randall <khr@golang.org>
    078ba138
dom.go 7.79 KB