584275 - nanojit: preparation for adding many more access regions

Status: RESOLVED FIXED

(Core Graveyard :: Nanojit, defect)

Description

[Nicholas Nethercote [inactive]]

Attachment: NJ patch (against 48641:8cae6d5cd69c)

This patch adds some optimisations to avoid slow-downs caused by using more
access regions.

- In CseFilter, only clear a hash table if it is non-empty.  This avoids a
  good number of memset() calls.

- Add a function msbSet() which uses machine instructions to find the
  most-significant bit set in a uint32_t.  I haven't yet tested msbSet() on
  Windows but it's cribbed from jsbit.h in TM so hopefully it'll work.  I'll
  try server it shortly.

- Use msbSet() in CseFilter::insLoad() to optimise the invalidation loop, so
  there's only one iteration for each bit set in storesSinceLastLoad.  Also
  use it to speed up compressAccSet(), along with the new isSingletonSet()
  function.

Also:

- Change the way embedder-specific values are passed into ValidateWriter --
  use an array, so any number of values can be passed in.
  
- Add 'disp' to checkAccSet().

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: TM patch (against TM 48641:8cae6d5cd69c)

Update TM for the NJ patches.

Comment 2

[Edwin Smith]

cool, msbSet()'s active ingredient is the same instruction as nRegisterAllocFromSet (more or less; bsf vs bsr).  I also noticed this patch's use of msbSet() would work equally well on architectures that only have an "lsb" equivalent instruction.  See NativeARM.cpp for more crib-able code for ARM.

It occurs to me we could also use this to speed up iterating through various register sets.  A common pattern is:

for (Register r = FirstReg; r <= LastReg; r = nextreg(r))
   if (/* mask expression of rmask(r) */ && something)
      ..

it could be replaced by:
RegisterMask mask = /* equivalent mask expression */
for (Register r = msbSet(mask); mask != 0; r = msbSet())
   if (/* something */)
      ...
   mask &= ~rmask(r)

I remember a while back you were looking at speeding up those iteration loops but i dont know if you tried something based on the BSR/BSF (or equivalent) machine instruction.

Comment 3

[Edwin Smith]

Comment on attachment 462670 [details] [diff] [review]
NJ patch (against 48641:8cae6d5cd69c)

Looks correct.  It would be good to factor out the bit-scanning code from each backend, but its not something that must be done on the critical path.

Comment 4

[Nicholas Nethercote [inactive]]

(In reply to comment #2)
> 
> It occurs to me we could also use this to speed up iterating through various
> register sets.  A common pattern is:
> 
> for (Register r = FirstReg; r <= LastReg; r = nextreg(r))
>    if (/* mask expression of rmask(r) */ && something)
>       ..
> 
> it could be replaced by:
> RegisterMask mask = /* equivalent mask expression */
> for (Register r = msbSet(mask); mask != 0; r = msbSet())
>    if (/* something */)
>       ...
>    mask &= ~rmask(r)
> 
> I remember a while back you were looking at speeding up those iteration loops
> but i dont know if you tried something based on the BSR/BSF (or equivalent)
> machine instruction.

I didn't, but it's a good idea for the ones where the pattern applies.  There are still several of the form:

  for (Register r = FirstReg; r <= LastReg; r = nextreg(r))
     LIns* ins = _allocator.getActive(r)
     if (ins) {
        ...
     }

Is there a fast way to do the same thing at the level of words?  I guess we could have a bit-set alongside 'active' to enable bitscanning, though that's less ideal.

Comment 5

[Nicholas Nethercote [inactive]]

Attachment: TR patch (against TR 4968:b7fa3e7574f0)

Comment 6

[Edwin Smith]

(In reply to comment #4)
> Is there a fast way to do the same thing at the level of words?  I guess we
> could have a bit-set alongside 'active' to enable bitscanning, though that's
> less ideal.

two ideas:

1. active = ~free & managed, then use bsr/bsf.  One alu op to compute
the active bitmask (free is managed in RegAlloc, and "managed" is
constant).   the loop in unionRegisterState would look like this:

mask = (~current.free | ~saved.free) & managed
for (... bsf-iteration of mask)

2. replace active[] with a Briggs/Torczon style sparse set
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319

The sparse set maintains two arrays of [MaxReg]: sparse[] and dense[].
sparse[] is indexed by register, like _active is, but contains an index
in dense.  add, get, and delete are O(1), and iteration is O(N) where N
is the # of active entries. (vs a bitset which is O(U)).  

Using BSF/BSR on a 1-word bitmask ought to be just as fast though, since
it could skip 1..32 bits in 1 machine cycle, making iteration O(N)
instead of O(U).  the sparse set starts to beat the bitmap when U/32 >> N,
ie when the set is *so* big and sparse that we start losing the benefit
of the 1-cycle BSF instruction and 32-bit parallel ALU ops.

oh, and idea #3: use SSE instructions to slurp 2 or 4 words at a time,
or more.  this doesnt seem worth the bother.

Comment 7

[Edwin Smith]

I prototyped idea #1 in Bug 584935, its showing about a 5% speedup in pure jit speed (large input set of 1000's of methods, no jit-code execution) on x64.  Expect that % to be diluted in the real world of course.

Comment 8

[Robert Sayre]

is this fixed?

http://hg.mozilla.org/mozilla-central/rev/a99f99f9f614

Comment 9

[Nicholas Nethercote [inactive]]

It's fixed in NJ and TM, sorry I forgot the whiteboard+links:

http://hg.mozilla.org/projects/nanojit-central/rev/64ae262a0203
http://hg.mozilla.org/tracemonkey/rev/a99f99f9f614

Comment 10

[Edwin Smith]

Attachment: Force CseFilter tables to be cleared in CseFilter constructor

This snuck in because TR's implementation of Allocator::allocChunk() calls malloc(), while IIRC TM's calls calloc().

Comment 11

[Edwin Smith]

nj patches
http://hg.mozilla.org/tamarin-redux/rev/5f0eb4431a4c
http://hg.mozilla.org/tamarin-redux/rev/053e59c92312
http://hg.mozilla.org/tamarin-redux/rev/355dd7b3ec01

tr patch
http://hg.mozilla.org/tamarin-redux/rev/4530cb245a32