• Keith Randall's avatar
    cmd/compile: Use Sreedhar+Gao phi building algorithm · 5a6e511c
    Keith Randall authored
    Should be more asymptotically happy.
    
    We process each variable in turn to find all the
    locations where it needs a phi (the dominance frontier
    of all of its definitions).  Then we add all those phis.
    This takes O(n * #variables), although hopefully much less.
    
    Then we do a single tree walk to match all the
    FwdRefs with the nearest definition or phi.
    This takes O(n) time.
    
    The one remaining inefficiency is that we might end up
    introducing a bunch of dead phis in the first step.
    A TODO is to introduce phis only where they might be
    used by a read.
    
    The old algorithm is still faster on small functions,
    so there's a cutover size (currently 500 blocks).
    
    This algorithm supercedes the David's sparse phi
    placement algorithm for large functions.
    
    Lowers compile time of example from #14934 from
    ~10 sec to ~4 sec.
    Lowers compile time of example from #16361 from
    ~4.5 sec to ~3 sec.
    Lowers #16407 from ~20 min to ~30 sec.
    
    Update #14934
    Update #16361
    Fixes #16407
    
    Change-Id: I1cff6364e1623c143190b6a924d7599e309db58f
    Reviewed-on: https://go-review.googlesource.com/30163Reviewed-by: 's avatarDavid Chase <drchase@google.com>
    5a6e511c
ssa.go 146 KB