-
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: 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}
a9ea67d4