• Jakob Gruber's avatar
    Revert "[regalloc] Use an adaptive data structure for live sets" · fb5c7c87
    Jakob Gruber authored
    This reverts commit b3d748a2.
    
    Reason for revert: Regressions, see https://crbug.com/1023423.
    
    Original change's description:
    > [regalloc] Use an adaptive data structure for live sets
    > 
    > Live sets represent sets of live virtual registers at block entry and
    > exit points. They are usually sparsely populated; for example, a sample
    > taken from Octane2 shows 80% of sampled live sets with a fill ratio of
    > 10% or less.
    > 
    > Prior to this CL, live sets were implemented as a statically-sized bit
    > vector. This is fine for low-ish virtual register counts, but becomes
    > wasteful at higher numbers.
    > 
    > This CL attempts to address this issue through an adaptive
    > implementation. Small live sets remain bit vectors, while larger sets
    > switch to a PersistentMap-based implementation. PersistentMap has very
    > memory-efficient add/remove/copy operations.
    > 
    > Of course, with adaptive data structures we enter the territory of
    > parameter fiddling. In this case, two parameters are used:
    > kMaxSmallSetSize controls when to switch implementations, and
    > kMaxDeletionsBeforePrune controls when pruning (= managing the # of
    > deleted entries in the map) sets in.
    > 
    > On the (degenerate) test case from the linked bug, the register
    > allocation zone shrinks from 1008MB to 475MB. For more realistic cases
    > I expect savings on the order of 10s of KB.
    > 
    > Bug: v8:9574
    > Change-Id: Id903bbe23f030b418e8d887ef4839c8d65126c52
    > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1891693
    > Reviewed-by: Tobias Tebbi <tebbi@chromium.org>
    > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
    > Commit-Queue: Jakob Gruber <jgruber@chromium.org>
    > Cr-Commit-Position: refs/heads/master@{#64872}
    
    TBR=jgruber@chromium.org,tebbi@chromium.org,thibaudm@chromium.org
    
    # Not skipping CQ checks because original CL landed > 1 day ago.
    
    Bug: v8:9574
    Change-Id: I5d684198f9c4575a0c892076459cc2c20dce9aec
    Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1910944Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
    Commit-Queue: Jakob Gruber <jgruber@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#64912}
    fb5c7c87
persistent-map.h 16.9 KB