• Jakob Gruber's avatar
    Revert "Reland "[regalloc] Use an adaptive data structure for live sets"" · f9c5bbef
    Jakob Gruber authored
    This reverts commit a9ea67d4.
    
    Reason for revert: Regressions https://crbug.com/1025160.
    
    Original change's description:
    > Reland "[regalloc] Use an adaptive data structure for live sets"
    >
    > 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/+/1910953
    > 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@{#64950}
    
    TBR=jgruber@chromium.org,tebbi@chromium.org,thibaudm@chromium.org
    
    # Not skipping CQ checks because original CL landed > 1 day ago.
    
    Bug: v8:9574,chromium:1025160
    Change-Id: I177d64eed588cd09c999e15b04d37630c2c6538b
    Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1918255
    Commit-Queue: Jakob Gruber <jgruber@chromium.org>
    Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#64998}
    f9c5bbef
persistent-map.h 16.9 KB