• 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
Name
Last commit
Last update
.github Loading commit data...
api Loading commit data...
doc Loading commit data...
lib/time Loading commit data...
misc Loading commit data...
src Loading commit data...
test Loading commit data...
.gitattributes Loading commit data...
.gitignore Loading commit data...
AUTHORS Loading commit data...
CONTRIBUTING.md Loading commit data...
CONTRIBUTORS Loading commit data...
LICENSE Loading commit data...
PATENTS Loading commit data...
README.md Loading commit data...
favicon.ico Loading commit data...
robots.txt Loading commit data...