Bug 168454 – Add the Briggs optimistic allocator to run on ARM64

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Saam Barati]

This should make IRC run faster. Let's see its perf impact.

[Saam Barati]

And by make IRC run faster, I meant it should run faster than IRC.

[Saam Barati]

Briggs allocator is about 10% faster right now. I haven't detected any test regressions. I want to see if I can make this even faster.

If I go full BitVector for the adjacency matrix in the interference graph, I can make things even faster. I get a 25% speed improvement (obviously this would help IRC too). There may be some alternative data structures we can use that would also be fast but not use as much memory as the BitVector. Phil suggested checking out the points to set data structure talked about in this paper:
http://hirzels.com/martin/papers/toplas07-pointers.pdf

[Saam Barati]

Created attachment 302010 [details]
WIP

Here is a patch for the Briggs optimistic allocator.
I'm still running some numbers on it. I just spoke with Ben, and he suggest checking it alongside IRC. I think I agree. But this patch is just if I replaced IRC, because I think it's easier to read this way.

It also includes a BitVector for the adjacency list, this is obviously a memory regression, so I need to consider if I want to keep it.

[Filip Pizlo]

(In reply to comment #3)
> Created attachment 302010 [details]
> WIP
> 
> Here is a patch for the Briggs optimistic allocator.
> I'm still running some numbers on it. I just spoke with Ben, and he suggest
> checking it alongside IRC. I think I agree.

I agree, too.  We should have the ability to run both for a while, and test both.

Haven't looked at the patch too closely, but it seems like it should be possible to create some abstractions that allow most of the code to be shared.

> But this patch is just if I
> replaced IRC, because I think it's easier to read this way.
> 
> It also includes a BitVector for the adjacency list, this is obviously a
> memory regression, so I need to consider if I want to keep it.

[Benjamin Poulain]

Comment on attachment 302010 [details]
WIP

View in context: https://bugs.webkit.org/attachment.cgi?id=302010&action=review

> Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:84
> +            const_cast<AbstractColoringAllocator<IndexType>*>(this)->m_coalescedTmps[tmpIndex] = nextAlias;

Shouldn't this go after the while loop()?

> Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:97
> +    unsigned k() const { return m_regsInPriorityOrder.size(); }

I think it is a good idea to avoid names from papers when they are cryptic.
Readers should not have to read the paper to understand the algorithm.

[Saam Barati]

Created attachment 302041 [details]
WIP

Here are both allocators.
I still need to add a runtime option for which allocator to run, rename the file, and add back some logging code.

So far, I haven't been able to detect any real slowdowns. Nor have I been able to detect any speedups.

[Saam Barati]

(In reply to comment #5)
> Comment on attachment 302010 [details]
> WIP
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=302010&action=review
> 
> > Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:84
> > +            const_cast<AbstractColoringAllocator<IndexType>*>(this)->m_coalescedTmps[tmpIndex] = nextAlias;
> 
> Shouldn't this go after the while loop()?
Yeah. I originally changed this to the full recursive disjoint union algorithm using
an if statement and recursion. I forgot to move it outwards after that.

> 
> > Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:97
> > +    unsigned k() const { return m_regsInPriorityOrder.size(); }
> 
> I think it is a good idea to avoid names from papers when they are cryptic.
> Readers should not have to read the paper to understand the algorithm.

Fair enough. I'll name it something more descriptive.

[Saam Barati]

Comment on attachment 302041 [details]
WIP

View in context: https://bugs.webkit.org/attachment.cgi?id=302041&action=review

> Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:459
> +    BitVector m_interferenceEdges;

I think ima go back to the HashSet here.

[Saam Barati]

(In reply to comment #6)
> Created attachment 302041 [details]
> WIP
> 
> Here are both allocators.
> I still need to add a runtime option for which allocator to run, rename the
> file, and add back some logging code.
> 
> So far, I haven't been able to detect any real slowdowns. Nor have I been
> able to detect any speedups.

I take that back. I see a 1% slowdown on Octane on x86. But not on ARM. We could try adding biased coloring to the Briggs allocator to see if that fixes the Octane regression.

Also, another observation I had, I don't think we prioritize moves in any particular way. However, it'd be beneficial to consider more "expensive" moves first. Perhaps our list of moves could be a priority queue sorted on loop depth so we always consider moves inside loops before moves elsewhere.

Given the data, it's probably not worth landing the Briggs allocator on. We could try landing turning it on for just ARM64 to see if the perf bots detect any speedup. I'll see if I can optimize it more for Octane on x86. I'll probably try out biased coloring. If we leave it off for all platforms, I'll make sure there is at least some jsc test form that runs Briggs allocator just to make sure it stays working.

[Filip Pizlo]

(In reply to comment #9)
> (In reply to comment #6)
> > Created attachment 302041 [details]
> > WIP
> > 
> > Here are both allocators.
> > I still need to add a runtime option for which allocator to run, rename the
> > file, and add back some logging code.
> > 
> > So far, I haven't been able to detect any real slowdowns. Nor have I been
> > able to detect any speedups.
> 
> I take that back. I see a 1% slowdown on Octane on x86. But not on ARM. We
> could try adding biased coloring to the Briggs allocator to see if that
> fixes the Octane regression.
> 
> Also, another observation I had, I don't think we prioritize moves in any
> particular way. However, it'd be beneficial to consider more "expensive"
> moves first. Perhaps our list of moves could be a priority queue sorted on
> loop depth so we always consider moves inside loops before moves elsewhere.
> 
> Given the data, it's probably not worth landing the Briggs allocator on. We
> could try landing turning it on for just ARM64 to see if the perf bots
> detect any speedup. I'll see if I can optimize it more for Octane on x86.
> I'll probably try out biased coloring. If we leave it off for all platforms,
> I'll make sure there is at least some jsc test form that runs Briggs
> allocator just to make sure it stays working.

I think it's sensible to have IRC for x86_64 and Briggs for ARM64 because:

- ARM64 has more registers, so it isn't so sensitive to register allocation.
- x86_64 is two-operand form so it is more sensitive to coalescing.

So, I would expect that ARM64 would use a weaker register allocator than x86_64.

[WebKit Commit Bot]

Attachment 302041 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:437:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:443:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:458:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:571:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:904:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:1676:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:1679:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:1689:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:1699:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:1700:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:1701:  Should have a space between // and comment  [whitespace/comments] [4]
Total errors found: 11 in 2 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Saam Barati]

I've also added what Briggs called "biased coloring" to our Briggs implementation, and it makes Briggs 10% and 3% faster than IRC on a couple Octane tests on x86. I still need to try it out on ARM64.

I also added biased coloring to IRC, but it's leading to crashes in a few scenarios that are really surprising to me. I need to learn why it's crashing IRC to add biases after any node is added to the select stack. I'm probably missing something as to why it's invalid.

[Saam Barati]

(In reply to comment #12)
> I've also added what Briggs called "biased coloring" to our Briggs
> implementation, and it makes Briggs 10% and 3% faster than IRC on a couple
> Octane tests on x86. I still need to try it out on ARM64.
> 
> I also added biased coloring to IRC, but it's leading to crashes in a few
> scenarios that are really surprising to me. I need to learn why it's
> crashing IRC to add biases after any node is added to the select stack. I'm
> probably missing something as to why it's invalid.

I know why my biasing algorithm works on Briggs but not on IRC (but does work on IRC but only before anything is spilled).

The reason it works for IRC before anything is spilled is the same reason it works for Briggs. As we coalesce, our interference graph keeps all the relationships we're interested in inside the interference graph. However, if we've already spilled, and then we do more coalescing, the interference graph will no longer represent the constraints that would exist for an already spilled node. This broke my implementation of biased coloring that didn't color this use case. Perhaps it's not even worth doing this. The algorithm would have to consider everything that coalesced into a node and to see if any of those interfere with a biased color. It's probably easier to just reason about the algorithm before anything makes it to the spill stack. (Again, for Briggs, this is the only way to reason about it, since we run coalescing until we're done, and then we simplify.)

[Saam Barati]

(In reply to comment #13)
> (In reply to comment #12)
> > I've also added what Briggs called "biased coloring" to our Briggs
> > implementation, and it makes Briggs 10% and 3% faster than IRC on a couple
> > Octane tests on x86. I still need to try it out on ARM64.
> > 
> > I also added biased coloring to IRC, but it's leading to crashes in a few
> > scenarios that are really surprising to me. I need to learn why it's
> > crashing IRC to add biases after any node is added to the select stack. I'm
> > probably missing something as to why it's invalid.
> 
> I know why my biasing algorithm works on Briggs but not on IRC (but does
> work on IRC but only before anything is spilled).
> 
> The reason it works for IRC before anything is spilled is the same reason it
> works for Briggs. As we coalesce, our interference graph keeps all the
> relationships we're interested in inside the interference graph. However, if
> we've already spilled, and then we do more coalescing, the interference
> graph will no longer represent the constraints that would exist for an
> already spilled node. This broke my implementation of biased coloring that
> didn't color this use case. Perhaps it's not even worth doing this. The
> algorithm would have to consider everything that coalesced into a node and
> to see if any of those interfere with a biased color. It's probably easier
> to just reason about the algorithm before anything makes it to the spill
> stack. (Again, for Briggs, this is the only way to reason about it, since we
> run coalescing until we're done, and then we simplify.)

Actually, this doesn't fit easily into IRC. I'd have to do the more complicated thing to determine if it's safe to perform a biased coloring. In Briggs, this is just natural.

[Saam Barati]

(In reply to comment #14)
> (In reply to comment #13)
> > (In reply to comment #12)
> > > I've also added what Briggs called "biased coloring" to our Briggs
> > > implementation, and it makes Briggs 10% and 3% faster than IRC on a couple
> > > Octane tests on x86. I still need to try it out on ARM64.
> > > 
> > > I also added biased coloring to IRC, but it's leading to crashes in a few
> > > scenarios that are really surprising to me. I need to learn why it's
> > > crashing IRC to add biases after any node is added to the select stack. I'm
> > > probably missing something as to why it's invalid.
> > 
> > I know why my biasing algorithm works on Briggs but not on IRC (but does
> > work on IRC but only before anything is spilled).
> > 
> > The reason it works for IRC before anything is spilled is the same reason it
> > works for Briggs. As we coalesce, our interference graph keeps all the
> > relationships we're interested in inside the interference graph. However, if
> > we've already spilled, and then we do more coalescing, the interference
> > graph will no longer represent the constraints that would exist for an
> > already spilled node. This broke my implementation of biased coloring that
> > didn't color this use case. Perhaps it's not even worth doing this. The
> > algorithm would have to consider everything that coalesced into a node and
> > to see if any of those interfere with a biased color. It's probably easier
> > to just reason about the algorithm before anything makes it to the spill
> > stack. (Again, for Briggs, this is the only way to reason about it, since we
> > run coalescing until we're done, and then we simplify.)
> 
> Actually, this doesn't fit easily into IRC. I'd have to do the more
> complicated thing to determine if it's safe to perform a biased coloring. In
> Briggs, this is just natural.

Hmmm, actually, after thinking about various interference graphs, I don't what I said is quite correct. I don't think it could happen, given how we consider a node's adjacency list. So, given that, I'm not quite sure why biased coloring is breaking IRC.

[Saam Barati]

(In reply to comment #15)
> (In reply to comment #14)
> > (In reply to comment #13)
> > > (In reply to comment #12)
> > > > I've also added what Briggs called "biased coloring" to our Briggs
> > > > implementation, and it makes Briggs 10% and 3% faster than IRC on a couple
> > > > Octane tests on x86. I still need to try it out on ARM64.
> > > > 
> > > > I also added biased coloring to IRC, but it's leading to crashes in a few
> > > > scenarios that are really surprising to me. I need to learn why it's
> > > > crashing IRC to add biases after any node is added to the select stack. I'm
> > > > probably missing something as to why it's invalid.
> > > 
> > > I know why my biasing algorithm works on Briggs but not on IRC (but does
> > > work on IRC but only before anything is spilled).
> > > 
> > > The reason it works for IRC before anything is spilled is the same reason it
> > > works for Briggs. As we coalesce, our interference graph keeps all the
> > > relationships we're interested in inside the interference graph. However, if
> > > we've already spilled, and then we do more coalescing, the interference
> > > graph will no longer represent the constraints that would exist for an
> > > already spilled node. This broke my implementation of biased coloring that
> > > didn't color this use case. Perhaps it's not even worth doing this. The
> > > algorithm would have to consider everything that coalesced into a node and
> > > to see if any of those interfere with a biased color. It's probably easier
> > > to just reason about the algorithm before anything makes it to the spill
> > > stack. (Again, for Briggs, this is the only way to reason about it, since we
> > > run coalescing until we're done, and then we simplify.)
> > 
> > Actually, this doesn't fit easily into IRC. I'd have to do the more
> > complicated thing to determine if it's safe to perform a biased coloring. In
> > Briggs, this is just natural.
> 
> Hmmm, actually, after thinking about various interference graphs, I don't
> what I said is quite correct. I don't think it could happen, given how we
> consider a node's adjacency list. So, given that, I'm not quite sure why
> biased coloring is breaking IRC.
Ok. Nevermind again. I've just come up with some simple examples that breaks my code for how I do biased coloring in IRC and it's because the statement I said above. I need to think more about how biased coloring can work in IRC.

[Saam Barati]

I was doing biased coloring slightly wrong. I was doing it after all the colors were selected. The right way to do it is while selecting the colors.

[Saam Barati]

I'll land biased coloring in a follow up patch just to make it more easily comparable perf wise.

[Saam Barati]

Created attachment 302167 [details]
patch

[WebKit Commit Bot]

Attachment 302167 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:39:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Saam Barati]

Created attachment 302168 [details]
patch

Fix style.

[Saam Barati]

Not sure why gcc in the gtk build is mad. Perhaps it's my lambda with an auto parameter.

[Filip Pizlo]

Comment on attachment 302168 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=302168&action=review

Looks reasonable to me.

> Source/JavaScriptCore/b3/air/AirRegisterAllocator.h:43
> +void allocateRegisters(Code&);

I like when compiler phases have the most precise and concise name.  For example, we say eliminateCommonSubexpressions rather than eliminateRedundantCode, because CSE refers to a more specific algorithm.

So, it would be better to call this "GraphColoring".  But in the tradition of B3 and Air compiler phases being verb phrases, I'd be fine with a verb phrase, too.  Some ideas:

allocateRegistersByGraphColoring
colorInterferenceGraph
lowerTmpsByColoringGraph

"allocateRegistersByGraphColoring" seems the most WebKitey name, and I like those kinds of names for phases.

I'm not picky, so long as it calls out that this a graph coloring algorithm.  I'm fine with it just being AirGraphColoring.

[Saam Barati]

(In reply to comment #23)
> Comment on attachment 302168 [details]
> patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=302168&action=review
> 
> Looks reasonable to me.
> 
> > Source/JavaScriptCore/b3/air/AirRegisterAllocator.h:43
> > +void allocateRegisters(Code&);
> 
> I like when compiler phases have the most precise and concise name.  For
> example, we say eliminateCommonSubexpressions rather than
> eliminateRedundantCode, because CSE refers to a more specific algorithm.
> 
> So, it would be better to call this "GraphColoring".  But in the tradition
> of B3 and Air compiler phases being verb phrases, I'd be fine with a verb
> phrase, too.  Some ideas:
> 
> allocateRegistersByGraphColoring
> colorInterferenceGraph
> lowerTmpsByColoringGraph
> 
> "allocateRegistersByGraphColoring" seems the most WebKitey name, and I like
> those kinds of names for phases.
> 
> I'm not picky, so long as it calls out that this a graph coloring algorithm.
> I'm fine with it just being AirGraphColoring.

I'll go with "allocateRegistersByGraphColoring" and name the files "AirGraphColoring.*"

[Saam Barati]

Created attachment 302357 [details]
patch for landing testing gtk to see if it builds

[Saam Barati]

Created attachment 302358 [details]
patch for landing testing gtk to see if it builds v2

[WebKit Commit Bot]

Attachment 302358 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/air/AirGenerate.cpp:39:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 7 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Saam Barati]

Created attachment 302359 [details]
patch for landing testing gtk to see if it builds v3

[Saam Barati]

Ok, gtk EWS looks to be making forward progress. Ima land it.

[Saam Barati]

landed in:
https://trac.webkit.org/changeset/212799

[Filip Pizlo]

(In reply to comment #24)
> (In reply to comment #23)
> > Comment on attachment 302168 [details]
> > patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=302168&action=review
> > 
> > Looks reasonable to me.
> > 
> > > Source/JavaScriptCore/b3/air/AirRegisterAllocator.h:43
> > > +void allocateRegisters(Code&);
> > 
> > I like when compiler phases have the most precise and concise name.  For
> > example, we say eliminateCommonSubexpressions rather than
> > eliminateRedundantCode, because CSE refers to a more specific algorithm.
> > 
> > So, it would be better to call this "GraphColoring".  But in the tradition
> > of B3 and Air compiler phases being verb phrases, I'd be fine with a verb
> > phrase, too.  Some ideas:
> > 
> > allocateRegistersByGraphColoring
> > colorInterferenceGraph
> > lowerTmpsByColoringGraph
> > 
> > "allocateRegistersByGraphColoring" seems the most WebKitey name, and I like
> > those kinds of names for phases.
> > 
> > I'm not picky, so long as it calls out that this a graph coloring algorithm.
> > I'm fine with it just being AirGraphColoring.
> 
> I'll go with "allocateRegistersByGraphColoring" and name the files
> "AirGraphColoring.*"

All other phases match the phase function name to the file name, so that if you see a function call to one of those phases, you immediately know what file to look into.

I think we should do the same thing here, and call these files AirAllocateRegistersByGraphColoring.*.  Can you lang a follow-up renaming?

[Saam Barati]

(In reply to comment #31)
> (In reply to comment #24)
> > (In reply to comment #23)
> > > Comment on attachment 302168 [details]
> > > patch
> > > 
> > > View in context:
> > > https://bugs.webkit.org/attachment.cgi?id=302168&action=review
> > > 
> > > Looks reasonable to me.
> > > 
> > > > Source/JavaScriptCore/b3/air/AirRegisterAllocator.h:43
> > > > +void allocateRegisters(Code&);
> > > 
> > > I like when compiler phases have the most precise and concise name.  For
> > > example, we say eliminateCommonSubexpressions rather than
> > > eliminateRedundantCode, because CSE refers to a more specific algorithm.
> > > 
> > > So, it would be better to call this "GraphColoring".  But in the tradition
> > > of B3 and Air compiler phases being verb phrases, I'd be fine with a verb
> > > phrase, too.  Some ideas:
> > > 
> > > allocateRegistersByGraphColoring
> > > colorInterferenceGraph
> > > lowerTmpsByColoringGraph
> > > 
> > > "allocateRegistersByGraphColoring" seems the most WebKitey name, and I like
> > > those kinds of names for phases.
> > > 
> > > I'm not picky, so long as it calls out that this a graph coloring algorithm.
> > > I'm fine with it just being AirGraphColoring.
> > 
> > I'll go with "allocateRegistersByGraphColoring" and name the files
> > "AirGraphColoring.*"
> 
> All other phases match the phase function name to the file name, so that if
> you see a function call to one of those phases, you immediately know what
> file to look into.
> 
> I think we should do the same thing here, and call these files
> AirAllocateRegistersByGraphColoring.*.  Can you lang a follow-up renaming?

Will do.

[Saam Barati]

Fixed file name in:
https://trac.webkit.org/changeset/212813