513863 - nanojit: refactor registerAlloc()

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

Attachment: patch

registerAlloc() doesn't preserve the free/active/Reservation invariants.  This
patch changes it so it does.  How this happened:

- 'registerAlloc(r)' was always followed with either 'addActive(r, ins)' or
  'addFree(r)'.  So I made a copy of registerAlloc(), called
  registerAllocTmp().  I added addActive(r, ins) to the end of the original, and
  added addFree(r) to the end of the copy.  All the call sites were updated
  accordingly.

- Then I changed registerAllocTmp() to just call registerAlloc(), then
  deactivate the r that registerAlloc() added, and also free it.  This avoids
  the code duplication.  It means registerAllocTmp() is slightly inefficient,
  as it activates then deactivates a register, but it is called only
  occasionally, whereas registerAlloc() is called very frequently.

- Then I changed registerAlloc() to update the relevant Reservation itself;
  previously that was done immediately after every registerAlloc() call.

- Then I added some comments, and made a couple of other small code tweaks.

- Then I (unrelatedly) added a 'break' to the last case in the big switch in
  gen(), just because it's a good idea and will avoid future heartache if the
  case order is changed.

registerAlloc() both now maintain the invariants. 

As for registerAllocTmp(), it's less clear... its comment documents its problems.  It's not clear to me how registerAllocTmp() can be used safely at all,
but the handful of uses don't seem to cause problems.  I can't work out if
they represent a bug that hasn't manifested yet, or if there's something
devious about the uses that means they work.  Either way, registerAllocTmp()
should be removed in the future because it's horrible, and suggestions on
how to do so are welcome.

Comment 1

[Rick Reitmaier]

registerAllocTmp() in some form or another will be needed.  

I'm guessing that if we simply ensured that the register obtained through this call can NEVER be spilled from subsequent calls to the *allocator* and we tighten the invariants, possibly add a registerFreeTmp() which returns the tmp register, then we should be fine.

Comment 2

[Edwin Smith]

registerAllocTmp is a fudge for a few places in a few backends where we need a scratch register while generating assembly code, and the register isn't live beyond the code snippet emitted for that one LIR instruction.

there are other ways of getting scratch registers:
  - dont manage the register.  (ARM's IP register isn't managed for this reason)
  - don't ever use scratch registers.  (better for x86 where we cant afford to reserve any additional registers)

the latter approach is doable even on arm, if care is taken in how LIR is emitted.  for example, ARM's displacement field can't handle 32bit displacements, so if we limit displacements in LIR_ld (etc), and reference a larger constant as a separate instruction (LIR_int), then that larger constant can be shared, and can have a register assigned by the register allocator, instead of stealing a scratch register in the code for LIR_ld (etc).

another example of stealing a scratch register is the fneg sequence on SSE2 cpu's.  once again if we expand a sequence like this in LIR we can avoid needing the scratch reg in the assembler.  (maybe do the expansion in a lowering phase to avoid hindering other optimizations).

... long story, but i think if desired we might eliminate use of registerAllocTmp.  one might argue the cure is worse than the disease, but its a good discussion to have.

Comment 3

[Edwin Smith]

Comment on attachment 397813 [details] [diff] [review]
patch

i like the change and can't find anything wrong with it, but i've also been bitten before trying to clean this up in a similar way, so adding one more review.

if it passes both our test suites then it should be fine.

Comment 4

[Nicholas Nethercote [inactive]]

Let me know once you've tested it on your test suites.  It passed ours but I can retest before landing.

As for RegisterAllocTmp(), getting rid of it would be good but at least this patch separates it and marks it as dangerous, which is a good start.

Comment 5

[Rick Reitmaier]

Comment on attachment 397813 [details] [diff] [review]
patch

I haven't yet tested it (will do so tomorrow) but it looks good to me.

Comment 6

[Nicholas Nethercote [inactive]]

Attachment: patch, v2

I rebased the patch against the TM tip, which should make it easier to test.

I also realised that registerAllocTmp() is safe.  Whereas registerAlloc() finds a free register (evicting if necessary) for a specific instruction, registerAllocTmp() finds a free register but doesn't assign it to a particular instruction.  The regstate updates are appropriate.  I've updated the comment for registerAllocTmp() accordingly.

Comment 7

[Nicholas Nethercote [inactive]]

Attachment: patch, v2 (correct one this time)

Comment 8

[Rick Reitmaier]

Comment on attachment 401777 [details] [diff] [review]
patch, v2 (correct one this time)

nice cleanup, but I still am having problems applying to the redux tip.

Comment 9

[Nicholas Nethercote [inactive]]

Let's wait until the NJ merge is finished, then I can rebase and you can test more easily.

Comment 10

[Nicholas Nethercote [inactive]]

I figured this was ok to land because I am now able to test patches on Tamarin and it passed.

http://hg.mozilla.org/projects/nanojit-central/rev/6b7cffb8984f

Comment 11

[Nicholas Nethercote [inactive]]

ARM bustage fix:

http://hg.mozilla.org/projects/nanojit-central/rev/ee701ef7d0e4

Comment 12

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/dc0730e0b3a9
http://hg.mozilla.org/tracemonkey/rev/47772904e410

Comment 13

[Nicholas Nethercote [inactive]]

And another follow-up (sigh):
http://hg.mozilla.org/tracemonkey/rev/5438e5cb05ef

Comment 14

[Edwin Smith]

http://hg.mozilla.org/tamarin-redux/rev/8a07748b9782

followups are in tamarin too, do we really need to list them all?

Comment 15

[Nicholas Nethercote [inactive]]

(In reply to comment #14)
> 
> followups are in tamarin too, do we really need to list them all?

I guess it's up to you!

Comment 16

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/mozilla-central/rev/dc0730e0b3a9
http://hg.mozilla.org/mozilla-central/rev/47772904e410
http://hg.mozilla.org/mozilla-central/rev/5438e5cb05ef