• Keith Randall's avatar
    cmd/compile: make CSE faster · 30088ac9
    Keith Randall authored
    To refine a set of possibly equivalent values, the old CSE algorithm
    picked one value, compared it against all the others, and made two sets
    out of the results (the values that match the picked value and the
    values that didn't).  Unfortunately, this leads to O(n^2) behavior. The
    picked value ends up being equal to no other values, we make size 1 and
    size n-1 sets, and then recurse on the size n-1 set.
    
    Instead, sort the set by the equivalence classes of its arguments.  Then
    we just look for spots in the sorted list where the equivalence classes
    of the arguments change.  This lets us do a multi-way split for O(n lg
    n) time.
    
    This change makes cmpDepth unnecessary.
    
    The refinement portion used to call the type comparator.  That is
    unnecessary as the type was already part of the initial partition.
    
    Lowers time of 16361 from 8 sec to 3 sec.
    Lowers time of 15112 from 282 sec to 20 sec. That's kind of unfair, as
    CL 30257 changed it from 21 sec to 282 sec. But that CL fixed other bad
    compile times (issue #17127) by large factors, so net still a big win.
    
    Fixes #15112
    Fixes #16361
    
    Change-Id: I351ce111bae446608968c6d48710eeb6a3d8e527
    Reviewed-on: https://go-review.googlesource.com/30354Reviewed-by: 's avatarTodd Neal <todd@tneal.org>
    30088ac9
cse.go 9.37 KB