Closed Bug 1027897 Opened 5 years ago Closed 3 years ago

Register allocation refactoring

Categories

(Core :: JavaScript Engine: JIT, enhancement, P5)

enhancement

Tracking

()

RESOLVED WONTFIX
mozilla33

People

(Reporter: sunfish, Assigned: sunfish)

References

Details

Attachments

(11 files)

Attached are a series of patches refactoring various things in and around register allocation.
Simple cleanups.
Attachment #8443105 - Flags: review?(bhackett1024)
This simplifies some uses of CodePosition values.
Attachment #8443107 - Flags: review?(bhackett1024)
This patch introduces entryOf and exitOf helper functions to simplify a common pattern.
Attachment #8443127 - Flags: review?(bhackett1024)
This patch adds a bunch more debugging output for register allocation. While here, I took the liberty of revising some of the ASCII art used to represent live ranges and other things. Here's a brief example:

Allocations by virtual register:
  v1[0] req(rdi,rax?) has(rdi) [3,5) v1:r?@4
  v2[0] req(r,rax?) has(rax) [5,8) v2:r@7
  v3[0] req(r) has(rcx) [6,8)
  v4[0] req(r) has(rdx) [7,8) / v4[1] req(rax) has(rax) [8,9) v4:rax@8 / v4[2] has(stack:8) [8,9
)

Allocations by physical register:
  rax: v2 [5,8) / v4 [8,9) / [9,10)
  rcx: v3 [6,8) / [9,10)
  rdx: v4 [7,8) / [9,10)
  rbx: [9,10)
  rbp: [9,10)
  rsi: [9,10)
  rdi: v1 [3,5) / [9,10)
...

Of course, this can be fairly subjective, and I'm open to suggestions and objections.

Also worth noting are phis:

Block 10 [successor 12] [successor 11]
[56,59 Phi] [def v18<i>] [use v16:r?] [use v13:r?]
[56,59 Phi] [def v19<i>] [use v17:r?] [use v6:r?]

Previously I had changed phis to not display the input position; now that I'm more familiar with the code, I believe it makes more sense to print the entry position of the block for each phi, and give all the phis the same output position too.
Attachment #8443162 - Flags: review?(bhackett1024)
The code I wrote calling SplitHere and NextSplitPosition was fairly confusing and not well encapsulated. This patch gathers the code and data into a class, allowing assertions to be more consistently enforced, and allowing a more readable interface.
Attachment #8443164 - Flags: review?(bhackett1024)
Simple patch which compares intervals by their start rather than their end, since they are sorted by their start.
Attachment #8443168 - Flags: review?(bhackett1024)
This patch just adds a few comments.
Attachment #8443169 - Flags: review?(bhackett1024)
This patch renames LDefinition's PRESET and DEFAULT to FIXED and REGISTER, for consistency with corresponding names in LUse. Also it renames Requirement::SAME_AS_OTHER to MUST_REUSE_INPUT for consistency with LDefinition.
Attachment #8443174 - Flags: review?(bhackett1024)
This uses FixedList to replace some hand-coded arrays.
Attachment #8443175 - Flags: review?(bhackett1024)
This renames CodePosition's pos() method to bits(), since especially after the ra-range-tidiness.patch patch above, it shouldn't be used very frequently, so it's good to make it explicit. And it eliminates awkward-looking .pos.pos() code.
Attachment #8443176 - Flags: review?(bhackett1024)
Attachment #8443105 - Flags: review?(bhackett1024) → review+
Attachment #8443107 - Flags: review?(bhackett1024) → review+
Comment on attachment 8443127 [details] [diff] [review]
ra-entryof-exitof.patch

Review of attachment 8443127 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RegisterAllocator.h
@@ +353,5 @@
>          JS_ASSERT(!ins->isPhi());
> +        return inputOf(ins->id());
> +    }
> +    static CodePosition entryOf(const LBlock *block) {
> +        return CodePosition(block->firstId(), CodePosition::INPUT);

Maybe call inputOf() here.

@@ +356,5 @@
> +    static CodePosition entryOf(const LBlock *block) {
> +        return CodePosition(block->firstId(), CodePosition::INPUT);
> +    }
> +    static CodePosition exitOf(const LBlock *block) {
> +        return CodePosition(block->lastId(), CodePosition::OUTPUT);

Maybe call outputOf here.
Attachment #8443127 - Flags: review?(bhackett1024) → review+
Comment on attachment 8443162 [details] [diff] [review]
ra-debugging.patch

Review of attachment 8443162 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RegisterAllocator.h
@@ +342,5 @@
> +    CodePosition outputOf(uint32_t pos) const {
> +        if (insData[pos].ins()->isPhi()) {
> +            while (insData[pos + 1].ins()->isPhi())
> +                ++pos;
> +        }

Could you put a comment here and in inputOf(uint32_t)?  This behavior is kind of unexpected and it would be good to know why this is ok to always do.
Attachment #8443162 - Flags: review?(bhackett1024) → review+
Comment on attachment 8443164 [details] [diff] [review]
ra-splitpositions.patch

Review of attachment 8443164 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/BacktrackingAllocator.cpp
@@ +32,5 @@
> +{
> +    JS_ASSERT(!splitPositions_.empty());
> +}
> +
> +// Procede to the next split after |pos|.

typo
Attachment #8443164 - Flags: review?(bhackett1024) → review+
Comment on attachment 8443168 [details] [diff] [review]
ra-intervalfor-start.patch

Review of attachment 8443168 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/LiveRangeAllocator.cpp
@@ +347,5 @@
>  
>  LiveInterval *
>  VirtualRegister::intervalFor(CodePosition pos)
>  {
> +    // Intervals are sorted by their start position.

sorted in reverse order?
Attachment #8443168 - Flags: review?(bhackett1024) → review+
Comment on attachment 8443169 [details] [diff] [review]
ra-comments.patch

Review of attachment 8443169 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/LiveRangeAllocator.h
@@ +208,2 @@
>          CodePosition from;
> +        CodePosition to;    // The end of this range, exclusive.

Hmm, I think same-line-as-the-field comments look a little cluttered, but don't have a strong preference.
Attachment #8443169 - Flags: review?(bhackett1024) → review+
Attachment #8443174 - Flags: review?(bhackett1024) → review+
Attachment #8443175 - Flags: review?(bhackett1024) → review+
Attachment #8443176 - Flags: review?(bhackett1024) → review+
(In reply to Brian Hackett (:bhackett) from comment #11)
> Comment on attachment 8443127 [details] [diff] [review]
> ra-entryof-exitof.patch
> 
> Review of attachment 8443127 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RegisterAllocator.h
> @@ +353,5 @@
> >          JS_ASSERT(!ins->isPhi());
> > +        return inputOf(ins->id());
> > +    }
> > +    static CodePosition entryOf(const LBlock *block) {
> > +        return CodePosition(block->firstId(), CodePosition::INPUT);
> 
> Maybe call inputOf() here.

Ok.

> @@ +356,5 @@
> > +    static CodePosition entryOf(const LBlock *block) {
> > +        return CodePosition(block->firstId(), CodePosition::INPUT);
> > +    }
> > +    static CodePosition exitOf(const LBlock *block) {
> > +        return CodePosition(block->lastId(), CodePosition::OUTPUT);
> 
> Maybe call outputOf here.

Ok.

(In reply to Brian Hackett (:bhackett) from comment #12)
> Comment on attachment 8443162 [details] [diff] [review]
> ra-debugging.patch
> 
> Review of attachment 8443162 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RegisterAllocator.h
> @@ +342,5 @@
> > +    CodePosition outputOf(uint32_t pos) const {
> > +        if (insData[pos].ins()->isPhi()) {
> > +            while (insData[pos + 1].ins()->isPhi())
> > +                ++pos;
> > +        }
> 
> Could you put a comment here and in inputOf(uint32_t)?  This behavior is
> kind of unexpected and it would be good to know why this is ok to always do.

Commented.

(In reply to Brian Hackett (:bhackett) from comment #13)
> Comment on attachment 8443164 [details] [diff] [review]
> ra-splitpositions.patch
> 
> Review of attachment 8443164 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/BacktrackingAllocator.cpp
> @@ +32,5 @@
> > +{
> > +    JS_ASSERT(!splitPositions_.empty());
> > +}
> > +
> > +// Procede to the next split after |pos|.
> 
> typo

Fixed.

(In reply to Brian Hackett (:bhackett) from comment #14)
> Comment on attachment 8443168 [details] [diff] [review]
> ra-intervalfor-start.patch
> 
> Review of attachment 8443168 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/LiveRangeAllocator.cpp
> @@ +347,5 @@
> >  
> >  LiveInterval *
> >  VirtualRegister::intervalFor(CodePosition pos)
> >  {
> > +    // Intervals are sorted by their start position.
> 
> sorted in reverse order?

It's sorted in ascending order. I added this to the comment.

(In reply to Brian Hackett (:bhackett) from comment #15)
> Comment on attachment 8443169 [details] [diff] [review]
> ra-comments.patch
> 
> Review of attachment 8443169 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/LiveRangeAllocator.h
> @@ +208,2 @@
> >          CodePosition from;
> > +        CodePosition to;    // The end of this range, exclusive.
> 
> Hmm, I think same-line-as-the-field comments look a little cluttered, but
> don't have a strong preference.

Ok, I moved it to its own line.

https://hg.mozilla.org/integration/mozilla-inbound/rev/3f65f6f5b322
https://hg.mozilla.org/integration/mozilla-inbound/rev/47e90dfb0c31
https://hg.mozilla.org/integration/mozilla-inbound/rev/cfaf432d6877
https://hg.mozilla.org/integration/mozilla-inbound/rev/8051e8fec75f
https://hg.mozilla.org/integration/mozilla-inbound/rev/bcd538f7e019
https://hg.mozilla.org/integration/mozilla-inbound/rev/a965be2731d4
https://hg.mozilla.org/integration/mozilla-inbound/rev/c96c8e88e5cf
https://hg.mozilla.org/integration/mozilla-inbound/rev/359ba79e9b18
https://hg.mozilla.org/integration/mozilla-inbound/rev/ca1cfe712eab
https://hg.mozilla.org/integration/mozilla-inbound/rev/bb707791db4d
And a minor follow-up since at least one compiler didn't instantiate dumpVregs():

https://hg.mozilla.org/integration/mozilla-inbound/rev/302a9d14a3aa
I got the following warning when building with clang:

/Users/jon/work/dev2/js/src/jit/BacktrackingAllocator.cpp:1306:58: warning: binding reference member 'first_' to stack allocated parameter 'first' [-Wdangling-field]

Here's a patch.
Attachment #8445746 - Flags: review?(sunfish)
Comment on attachment 8445746 [details] [diff] [review]
fix-allocator-warning

Review of attachment 8445746 [details] [diff] [review]:
-----------------------------------------------------------------

Good catch.
Attachment #8445746 - Flags: review?(sunfish) → review+
Depends on: 1035286
Re-opening; I'd like to figure out why this patch caused that bug.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Depends on: 1080770
@sunfish: Still want to keep this bug open?
Flags: needinfo?(sunfish)
Priority: -- → P5
No; I'm not currently working on this.
Status: REOPENED → RESOLVED
Closed: 5 years ago3 years ago
Flags: needinfo?(sunfish)
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.