Bug 236269 - running testZDefOfSpillSlotWithOffsetNeedingToBeMaterializedInARegister on O2 Air shouldn't take minutes
Summary: running testZDefOfSpillSlotWithOffsetNeedingToBeMaterializedInARegister on O2...
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Robin Morisset
Keywords: InRadar
Depends on: 236037 236997
  Show dependency treegraph
Reported: 2022-02-07 15:58 PST by Saam Barati
Modified: 2022-06-23 15:11 PDT (History)
5 users (show)

See Also:


Note You need to log in before you can comment on or make changes to this bug.
Description Saam Barati 2022-02-07 15:58:37 PST
Spending all our time in stack graph coloring.
Comment 1 Radar WebKit Bug Importer 2022-02-14 15:59:16 PST
Comment 2 Robin Morisset 2022-02-21 10:29:00 PST
I found two bottlenecks:
- The creation of the interference graph has cubic complexity with a large constant factor: there are n**2 edges, and adding a new edge can require shifting right the BitVector form of LikelyDenseUnsignedIntegerSet. It just so happens that this example not only has n**2 edges, but also requires this shift for almost every single one!
- The actual call to assign() (in AirStackAllocation.cpp) is also responsible for a cubic blow-up, as for each stack slot (n of them) we try up to one possible offset per other stack slot (n of them), and test each possible offset against all other stack slots (n of them).

The second bottleneck can be lessened to O(n**2 * log(n)) by sorting the stack slots by offset doing the tests smartly. The first bottleneck I can improve the constant factor by a lot by always rounding the offset of the bit vector to the next lowest multiple of 64. This means 64x fewer shifts, and the shifts can be much cheaper since they become mere memcpy.

I intend to land these two changes in separate patches.
Comment 3 Robin Morisset 2022-02-21 15:37:16 PST
First patch: https://bugs.webkit.org/show_bug.cgi?id=236997
Comment 4 Brent Fulgham 2022-06-23 15:10:04 PDT

*** This bug has been marked as a duplicate of bug 236610 ***
Comment 5 Brent Fulgham 2022-06-23 15:11:30 PDT
Ignore the dupe -- this was completed as two checkins (see related bugs).