1143011 - RegisterSet take & add are no longer symmetric.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Nicolas B. Pierron [:nbp]]

Currently,
  take, does not filter out all aliased registers.
  takeAny, filters out all aliased registers.
  add, asserts that all alises can be added back into the register set.

For sanity reason we should remove the aliased registers when we take a register out of a register set, but this might cause issues with the register allocator.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Registerset::{take,add} are now considering aliased registers too.

Not asking for review yet, I want to see if I can remove some of the
function which are already used.

Comment 2

[Boris Zbarsky [:bzbarsky]]

[Tracking Requested - why for this release]: The fuzzers keep finding this.....

Comment 3

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8577465 [details] [diff] [review]
Registerset::{take,add} are now considering aliased registers too.

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

::: js/src/jsapi-tests/moz.build
@@ +94,5 @@
>          'testJitGVN.cpp',
>          'testJitMoveEmitterCycles-mips.cpp',
>          'testJitMoveEmitterCycles.cpp',
>          'testJitRangeAnalysis.cpp',
> +        'testJitRegisterSet.cpp',

missing file in the patch

Comment 4

[Nicolas B. Pierron [:nbp]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #3)
> ::: js/src/jsapi-tests/moz.build
> > +        'testJitRegisterSet.cpp',
> 
> missing file in the patch

This is a test case, you can just remove this line :)

I am working on a larger patch (unfortunately) where we would no longer be able to have such issues.  Register sets are used for 2 different use cases, and the methods of the TypedRegisterSet badly reflect this fact.  I first thought of replacing all add/take by more verbose variants such as hasRegisterIndex and hasAllocatable, but I figured that we in fact want to have consistent uses of these method over time, i-e that we always use the same variant of has/add/take on one register set.

The approach that I am taking with the clean-up patch is to provide the has/add/take accessors based on how the register set is used.  Basically we have 2 use cases:

When we allocate, and when we remember what got allocated.  The first use case should consider aliases — as aliases are no longer available once they are allocated, while the second use cases should only consider register indexes — as we have allocated a register with only one type, and not its aliases.

Comment 5

[Nicolas B. Pierron [:nbp]]

Attachment: (WIP) Extract the has/add/take logic out of the register sets to distinguish between an allocator pool and a live set.

Comment 6

[Nicolas B. Pierron [:nbp]]

Attachment: (WIP) Use Allocator<...> or LiveSet<...> for all register sets uses.

Comment 7

[Jan de Mooij [:jandem]]

Comment on attachment 8579346 [details] [diff] [review]
(WIP) Extract the has/add/take logic out of the register sets to distinguish between an allocator pool and a live set.

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

I think splitting these cases makes sense. I didn't check all the template magic but some comments:

- It looks like alignedOrDominatedAliasedSet is the same as (or similar to) aliasedSet? I think aliasedSet is clearer...

- s/Allocator/AllocatedSet/ so that it sounds more similar to LiveSet.

- LiveSet<GeneralRegisterSet> and AllocatedSet<GeneralRegisterSet> are a bit long and repetitive. Maybe we could add typedefs: LiveGeneralRegisterSet, AllocatedGeneralRegisterSet?

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #7)
> I think splitting these cases makes sense. I didn't check all the template
> magic but some comments:
> 
> - It looks like alignedOrDominatedAliasedSet is the same as (or similar to)
> aliasedSet? I think aliasedSet is clearer...

Unfortunately no, the difference is subtle but it can be seen on ARM:

  s0 alias s0 | d0.
  s1 alias s1 | d0.
  d0 alias s0 | s1 | d0.

  s0 "is aligned with / dominates" s0 | d0.
  s1 "is aligned with / dominates" s1.
  d0 "is aligned with / dominates" s0 | s1 | d0.

The later is better, as it does not imply adding additional logic to masking logic when we are taking / adding a register from/to the allocator set.  Note that with the later we have the relation

  alignedOrDominate(d0) == alignedOrDominate(s0) | alignedOrDominate(s1)
  alignedOrDominate(d0) == alignedOrDominate(s0) ^ alignedOrDominate(s1)

which ensures that we can do:

  Allocator<RegisterSet> pool;
  pool.add(s0);
  pool.add(s1);
  pool.take(d0);

without adding special conditions to the take / add functions.

By the way, the aliasedSet is nice, but it is no longer used :(

> - s/Allocator/AllocatedSet/ so that it sounds more similar to LiveSet.

I prefer AllocatorSet over AllocatedSet, as the later implies that the registers which are in the set are already allocated, while this is the opposite.  Any register listed in an AllocatorSet is allocatable, and thus not allocated yet.

> - LiveSet<GeneralRegisterSet> and AllocatedSet<GeneralRegisterSet> are a bit
> long and repetitive. Maybe we could add typedefs: LiveGeneralRegisterSet,
> AllocatedGeneralRegisterSet?

Sounds good, I will do that :)

Comment 9

[Nicolas B. Pierron [:nbp]]

Attachment: (WIP) Extract the has/add/take logic out of the register sets to distinguish between an allocator pool and a live set.

Comment 10

[Nicolas B. Pierron [:nbp]]

Attachment: (WIP) Use Allocator<...> or LiveSet<...> for all register sets uses.

Comment 11

[Nicolas B. Pierron [:nbp]]

The latest patches are only rebased on top of the lastets version of mozilla-central, they do not address any of the comment of the previous feedback.

Comment 12

[Nicolas B. Pierron [:nbp]]

So far I am unsuccesfull at getting these patches to work with gcc 4.7.2 & gcc 4.7.3 (internal compiler error) that we are using for the Linux slaves on treeherder.

I will dig in to see if I can work-around this problem.

Comment 13

[Nicolas B. Pierron [:nbp]]

Attachment: Extract the has/add/take logic out of the register sets to distinguish between an allocator pool and a live set.

Delta:
 - Apply feedback (rename classes)
 - Simplify the template magic to avoid template of templates.
 - Add special case to support gcc 4.7.3 which is used by taskcluster. (even
   if it appears under the 4.7.2 directory)
   Note: I am currently compiling gcc 4.7.4 to check if it is affected by
   this issue on constrexpr of LiveRegisterSet.
 - Accessor clases are not providing unchecked versions first, and the
   checks are added after to avoid extra complexity in the
   AllocatorSetAccessor and LiveSetAccessor classes.

Comment 14

[Nicolas B. Pierron [:nbp]]

Attachment: Use AllocatorSet or LiveSet for all register sets uses.

Comment 15

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8580140 [details] [diff] [review]
Extract the has/add/take logic out of the register sets to distinguish between an allocator pool and a live set.

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

::: mfbt/Attributes.h
@@ +95,5 @@
>  #      define MOZ_HAVE_CXX11_FINAL       final
>  #    endif
> +#    define MOZ_HAVE_CXX11_CONSTEXPR
> +#    if MOZ_GCC_VERSION_AT_LEAST(4, 7, 4)
> +#      define MOZ_HAVE_CXX11_CONSTEXPR_IN_TEMPLATES

I just checked with 4.7.4, and I can still reproduce the issue, I will bump this value to 4.8.0 and report a bug.

Comment 16

[Jan de Mooij [:jandem]]

Comment on attachment 8580140 [details] [diff] [review]
Extract the has/add/take logic out of the register sets to distinguish between an allocator pool and a live set.

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

Some heavy template magic here. The approach makes sense though, I agree this distinction is safer and the way to go. Also nice comments.

Requesting review from Waldo for the mfbt/* changes, I don't feel comfortable stamping those.

::: js/src/jit/RegisterSets.h
@@ +472,5 @@
>      static inline RegisterSet Volatile() {
>          return RegisterSet(GeneralRegisterSet::Volatile(), FloatRegisterSet::Volatile());
>      }
> +
> +

Nit: remove one of these empty lines.

@@ +501,5 @@
> +
> +};
> +
> +//
> +// Register sets are used for 2 usage:

Nit: "usages", but with "used" it sounds a bit unusual, maybe rephrase as:

There are 2 use cases for register sets:

@@ +503,5 @@
> +
> +//
> +// Register sets are used for 2 usage:
> +//
> +//   1. To serve as a pool of allocatable register. This is useful for working

What would you think of calling it AllocatableRegisterSet instead of AllocatorRegisterSet?

Allocator is a little confusing, because people may think it means "the result of the register allocator", but *that* is a LiveRegisterSet...

@@ +517,5 @@
> +// RegisterSet (for both). These classes are used to store the bit sets to
> +// represent each register.
> +//
> +// Each use case defines an Accessor class, such as AllocatorSetAccessor or
> +// LiveSetAccessor, which is parametrized with the type of the register

Nit: parameterized

@@ +524,5 @@
> +//
> +// The RegSetCommonInterface class is used to wrap the accessors with convenient
> +// shortcuts which are based on the accessors.
> +//
> +// Then, to avoid to many level of complexity while using these interfaces,

Nit: levels

@@ +542,5 @@
> +class LiveSet;
> +
> +//
> +// Base accessors classes have the minimal set of raw methods to manipulate the register set
> +// given as parameter in a consistent manner.  These methods are: , |addUnchecked|, and

Nit: add "has" between ":" and ","?

Or just "These methods are:", because we list them below too.

@@ +547,5 @@
> +// |takeUnchecked|.
> +//
> +//    - has: Returns if all the bits needed to take a register are present.
> +//
> +//    - takeUnchecked: Substracts the bits used to represent the register in the

Nit: Subtracts

@@ +558,5 @@
> +//
> +// The AllocatorSet accessors are used to make a pool of unused registers. Taking
> +// or adding registers should consider the aliasing rules of the architecture.
> +// For example, on ARM, we would have the following pieces of code should work
> +// fine, knowing that the double register |d0| is composed of float registers

Nit: "on ARM, the following piece of code should work fine,"

Nice explanations btw.

@@ +568,5 @@
> +//     // d0 is now available.
> +//     regs.take(d0);
> +//
> +// These accessors are useful for allocating registers within the function used
> +// to generate stubs, such as Trampoline, Inline caches (BaselineIC, IonCache).

Nit: functions, trampolines

@@ +641,5 @@
> +
> +
> +//
> +// The LiveSet accessors are used to collect a list of allocated
> +// registers. Taking or adding a register should *not* consider the alises, as

Nit: aliases

@@ +732,5 @@
> +    explicit MOZ_CONSTEXPR REGSET(SetType set) : Parent(set) {}  \
> +    explicit MOZ_CONSTEXPR REGSET(RegSet set) : Parent(set) {}
> +
> +//
> +// This class add checked accessors on top of the unchecked variants defined by

Nit: adds

Also I'd remove the "//" lines before and after each comment, I don't think we do that anywhere else.

@@ +928,5 @@
> +};
> +
> +
> +//
> +// Interface which is common to all register sets implementations. It overloads

Nit: register set implementations

@@ +1009,5 @@
>  
> +
> +//
> +// These classes do not provide any additional member, they only use they
> +// constructor to forward to the common interface for all register sets.  The

Nit: members, their constructor

Comment 17

[Jan de Mooij [:jandem]]

Comment on attachment 8580141 [details] [diff] [review]
Use AllocatorSet or LiveSet for all register sets uses.

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

::: js/src/jit/LinearScan.cpp
@@ +994,5 @@
>  
>      // Compute free-until positions for all registers
>      CodePosition freeUntilPos[AnyRegister::Total];
>      bool needFloat = vregs[current->vreg()].isFloatReg();
> +    if (needFloat) {

Can you make sure all jit-tests still pass with --ion-regalloc=lsra and the ARM simulator?

::: js/src/jit/MacroAssembler.h
@@ +1268,5 @@
>  
>      void alignFrameForICArguments(AfterICSaveLive &aic);
>      void restoreFrameAlignmentForICArguments(AfterICSaveLive &aic);
>  
> +    AfterICSaveLive icSaveLive(LiveRegisterSet &liveRegs) {

Pre-existing, but do icSaveLive and icRestoreLive really need a reference instead of a copy?

Comment 18

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #17)
> Comment on attachment 8580141 [details] [diff] [review]
> Use AllocatorSet or LiveSet for all register sets uses.
> 
> Review of attachment 8580141 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/LinearScan.cpp
> @@ +994,5 @@
> >  
> >      // Compute free-until positions for all registers
> >      CodePosition freeUntilPos[AnyRegister::Total];
> >      bool needFloat = vregs[current->vreg()].isFloatReg();
> > +    if (needFloat) {
> 
> Can you make sure all jit-tests still pass with --ion-regalloc=lsra and the
> ARM simulator?

I already verified with the ARM simulator both on try and locally.
I will check with LSRA.

> ::: js/src/jit/MacroAssembler.h
> @@ +1268,5 @@
> >  
> >      void alignFrameForICArguments(AfterICSaveLive &aic);
> >      void restoreFrameAlignmentForICArguments(AfterICSaveLive &aic);
> >  
> > +    AfterICSaveLive icSaveLive(LiveRegisterSet &liveRegs) {
> 
> Pre-existing, but do icSaveLive and icRestoreLive really need a reference
> instead of a copy?

RegisterSet are quite large, so using a reference instead of 2 words make sense.  I think this would even make more sense on x86 architecture, but I guess I can make a follow-up bug for adding "const" to most of these functions.

Comment 19

[Nicolas B. Pierron [:nbp]]

(In reply to Nicolas B. Pierron [:nbp] from comment #18)
> (In reply to Jan de Mooij [:jandem] from comment #17)
> > Can you make sure all jit-tests still pass with --ion-regalloc=lsra and the
> > ARM simulator?
> 
> I already verified with the ARM simulator both on try and locally.
> I will check with LSRA.

Ok, this took a while to check locally, but I tried (most of) the join product of:
 - x64 / x86 / arm simulator.
 - compiled with gcc 4.7.2, gcc 4.8.2, clang.
 - debug and optimized builds.

And I also verified that LSRA was working fine with x64-clang / arm-sim-gcc4.8 with debug builds.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=52cbe055fe7a (rebase on top of mozilla-central)
https://treeherder.mozilla.org/#/jobs?repo=try&revision=4d55564bcb78 (Apply nits & rename Allocator to Allocatable)

Comment 20

[Nicolas B. Pierron [:nbp]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/b2904e8f07e7
https://hg.mozilla.org/integration/mozilla-inbound/rev/509282768033

Comment 21

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/b2904e8f07e7
https://hg.mozilla.org/mozilla-central/rev/509282768033

Comment 23

[Ryan VanderMeulen [:RyanVM]]

This was backed out from Aurora39 due to bug 1149377.
https://hg.mozilla.org/releases/mozilla-aurora/rev/759eb70deb31

Comment 24

[Liz Henry (:lizzard) (relman/hg->git project)]

Nicolas, it sounds like once the fix for bug 1149377 lands, you should request uplift for this to aurora.

Comment 25

[Ryan VanderMeulen [:RyanVM]]

Re-landed on Aurora.