WebKit Bugzilla
New
Browse
Log In
×
Sign in with GitHub
or
Remember my login
Create Account
·
Forgot Password
Forgotten password account recovery
RESOLVED CONFIGURATION CHANGED
236269
running testZDefOfSpillSlotWithOffsetNeedingToBeMaterializedInARegister on O2 Air shouldn't take minutes
https://bugs.webkit.org/show_bug.cgi?id=236269
Summary
running testZDefOfSpillSlotWithOffsetNeedingToBeMaterializedInARegister on O2...
Saam Barati
Reported
2022-02-07 15:58:37 PST
Spending all our time in stack graph coloring.
Attachments
Add attachment
proposed patch, testcase, etc.
Radar WebKit Bug Importer
Comment 1
2022-02-14 15:59:16 PST
<
rdar://problem/88933599
>
Robin Morisset
Comment 2
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.
Robin Morisset
Comment 3
2022-02-21 15:37:16 PST
First patch:
https://bugs.webkit.org/show_bug.cgi?id=236997
Brent Fulgham
Comment 4
2022-06-23 15:10:04 PDT
*** This bug has been marked as a duplicate of
bug 236610
***
Brent Fulgham
Comment 5
2022-06-23 15:11:30 PDT
Ignore the dupe -- this was completed as two checkins (see related bugs).
Note
You need to
log in
before you can comment on or make changes to this bug.
Top of Page
Format For Printing
XML
Clone This Bug