• Jakob Gruber's avatar
    Reland "[regalloc] Use an adaptive data structure for live sets" · a9ea67d4
    Jakob Gruber authored
    This is a reland of b3d748a2
    
    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}
    
    Bug: v8:9574
    Change-Id: I5a95d56c33a98cc5c6c58ff9308314e2eefa462c
    Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1910953Reviewed-by: 's avatarTobias Tebbi <tebbi@chromium.org>
    Reviewed-by: 's avatarThibaud Michaud <thibaudm@chromium.org>
    Commit-Queue: Jakob Gruber <jgruber@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#64950}
    a9ea67d4
persistent-map.h 16.9 KB