518267 - nanojit: some instructions not printed with TMFLAGS=assembly

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

With TMFLAGS=assembly, the basic idea is that an instruction is only printed if its reservation is marked as used.  But there are a couple of cases where an instruction should be printed even if its reservation is not marked as used, and that's because we generate code for as part of generating code for another instruction.  Guard/cmov conditions is one case, div+mod is another case.  These are handled with ad hoc special cases at the end of Assembler::gen().

But I just realised that at least one other case isn't handled -- if ld(add(X,Y)), the ld and add are codegen'd together, at least on i386.  We can't add that as another special case in Assembler::gen() because it's backend-specific.

A more general solution would be to add a bit to LIns with a name something like "codeAlreadyGenerated", probably by stealing a bit from the "reg" field (which would leave it with 6 bits, enough for 64 registers, which is still twice what we currently need).  It could be set in the cases where an instruction has code generated when dealing with another instruction, and then the gen() special case would just look at that bit and print the instruction if it's set.

Comment 1

[Edwin Smith]

ppc uses something approaching 64 registers, but i'm sure there's still a bit somewhere that can be used.

another idea:

this is all for debug output, right?  the nanojit::live() analyzer in LIR.cpp figures out what instructions are live, period, regardless of the register allocator.  At least on tamarin in verbose mode, we always print the live instructions before staring the assembler.

we could have that pass just keep its list of live instructions so the assembler can decide whether or not to print a certian instruction interleaved with asm.  its not as cheap as a single bit, but this is verbose mode.  and its a totally independent algorithm for finding liveness, so if we did have a register allocator bug where a live instruction got dropped, verbose output generated this way might be slightly less hard to debug.

Comment 2

[Nicholas Nethercote [inactive]]

I agree using the liveness analyzer is a good way to do this -- otherwise, every time a backend generates code for more than one LIns at a time, it has to remember to set a bit.

I've started working on this.  I've got it basically working, though there's lots of clean-up to be done.  The liveness pass as needed for the liveness printing is a little different than that needed for assembly printing:

- liveness ignores LIR_paramp, assembly wants to print them.  Easy to fix:  assembly can just look for them and always print them.

- liveness "retires" instructions once they're def-point is reached, assembly doesn't want that.  That'll be controlled by a flag passed to the liveness pass.

- liveness pass prints stuff out, which isn't wanted for assembly.  Again, a flag.

- liveness ignores immediates.  Currently assembly mostly does too, when printing -- because they're mostly generated as part of another instructions -- but I think it should print them.  So that'll be another flag-controlled difference.

It'll end up being a bit clunky, ie. several behavioural differences in the liveness pass depending on an external flag, but I can live with that.

Comment 3

[Nicholas Nethercote [inactive]]

Attachment: NJ patch

This patch changes assembly printing to use info computed by the liveness
pass to determine which LIR instructions to print.

- I pulled live() into LiveTable, which made a lot of sense and allowed
  various things (eg. RetiredEntry) to be made private within LiveTable.
  LiveTable ended up in Assembler.{cpp,h} instead of LIR.cpp, because it was
  a more sensible place for it.

- The liveness pass can now be run twice.  Using TM terminology, once for
  TMFLAGS=liveness and once for TMFLAGS=assembly.  It's run twice even if
  TMFLAGS=liveness,assembly is specified, because the info collected on the
  two runs is different (as controlled by the 'show' parameter to
  LiveTable::LiveTable()).  This requires setting up a reader pipeline
  twice.  This is ugly but I couldn't see a better way to do it.

- I separated the liveness computation (livePass()) from the liveness
  printing (liveShow()), as the latter is only used by TMFLAGS=liveness.

- I renamed various things, partly to avoid repeating names (which I find
  confusing) and partly to make those names more descriptive.  Eg.
  LiveTable::live -> LiveTable::defUseMap, live() -> livePass(), 'i' ->
  'ins'.

- LiveTable is now passed to Assembler::assemble() and Assembler::gen(), but
  only on verbose builds.  This is ugly but I couldn't see a better way to
  do it.

- The LIns printing in Assembler::gen() now occurs after 'end_of_loop', ie.
  it's attempted for all LIR instructions, not just the 'required' ones.

Here are some examples of the change to the output.  In this example, the
immediate is printed:
-      eql15 = eql ldl24, 0       # codegen'd with the xf
+      0 = imml 0
+      eql15 = eql ldl24, 0
       xf16: xf eql15 -> pc=...... imacpc=(nil) sp+0 rp+0 (GuardID=001)
   ......   test ebx,ebx
   ......   jne   ......

That's not a big difference, because of the special treatment of immediates.  
For the following one the improvement is more obvious:

+      JSVAL_DOUBLE = imml 2
+      lshl1 = lshl ldl1, JSVAL_DOUBLE
+      addl4 = addl ldl20, lshl1
       ldl19 = ldl.o addl4[0]
   ......   mov   ecx,0(ecx+ebx*4)

Because ldl/add/lshl were all codegen'd together, the lshl and addl weren't
printed previously.

Comment 4

[Nicholas Nethercote [inactive]]

Attachment: TR patch

This compiles but I haven't tested it, because I don't know how the TR verbose modes work.  I'm not all that confident with the patch, it should be tested.

Comment 5

[Nicholas Nethercote [inactive]]

Hmm, now I'm backing away from reusing the liveness pass, and thinking again about adding a bit to LIns to indicate liveness.  It's not that hard to set the bit during codegen in Assembler::gen(), and having accurate liveness info at codegen time will be necessary if the generalized conditionally-live guards go ahead as described in bug 560994 comment 10.

Comment 6

[Nicholas Nethercote [inactive]]

Attachment: patch v2

This patch uses an 'isLive' bit to achieve the same goal.

- LIns has an 'isLive' bit added.  arIndex is shrunk from 15 to 14 bits,
  which is still one more than needed given that the maximum arIndex value
  is 8192.

- The 'isLive' bit is computed for every LIns during the codegen pass.  This
  is similar to what live() does, but much simpler because we're dealing
  with a binary property here, whereas live() has to deal with live ranges.

- There are new isLive()/setLiveExpr() functions.  I reworked the existing
  isLive() function -- which succeeded if the opcode was livei/liveq/lived
  -- as isLiveOpcode(), similar to isCseOpcode().

- For every expression case in the gen() switch we now have to do an
  isUsed() check before generating the code.

- I cleaned up the gen() switch a bit -- reordered some of the cases,
  removed unnecessary bracing, added some blank lines, added some missing
  countlir_XYZ calls.

- I changed isStmt();  LIR_paramp is always considered a statement now, as
  it should be.  Actually, I thought that if the LIR_paramp was for an arg
  it's an expression (ie.  it can be removed if dead), but if it's for a
  savedReg it's a statement (ie. it cannot ever be removed).  But I got some
  test failures when I tried that.  Any clarification on this point would be
  welcome.

- Similarly, I'd appreciate careful checking of the LIR_allocp case in
  gen().  I think it's safe to treat LIR_allocp as an expression, ie. if the
  result is never used it can be removed, but I'm not 100% certain.

It's slightly more instructions executed -- for TM on SunSpider it's 0.2%
for the worst of the benchmarks.  Timings are unaffected, though.

The output is identical to that from the previous patch.

Overall I think it's simpler than plumbing in the LiveTable (no need for a TR patch, for one), and more importantly, the 'isLive' bit will have other
applications (eg. bug 560994).

Comment 7

[Edwin Smith]

Comment on attachment 440949 [details] [diff] [review]
patch v2

The bit is cool and consice.  (occurs to me we might have an extra bit in the reg field, too; the most registers any platform has is 64.

nit: should "wholeWord" be called "sharedWord"?  just a thought.

If the only client of the new live bit is the verbose printer, then it could be more efficient and easier to maintain if we encapsulate the setting and checking of the live bit in a dedicated LirFilter, instead of weaving that code into gen().  Presumably the assembler, when running standalone, still can get what it needs with the inAr and inReg bits?

> ... having accurate liveness info at
> codegen time will be necessary if the generalized conditionally-live guards go
> ahead as described in bug 560994 comment 10.

ah, this is why we need the live bit even without verbose printing?

No matter what happens in Assembler, a side benefit of adding this bit is live() could be significantly simpler by using the live bit when a reference is seen, and clearing it when the instruction is seen.  it would completely eliminate "HashMap<LIns*, LIns*> live;" in class LiveTable.(In reply to comment #5)

(In reply to comment #6)
> - I changed isStmt();  LIR_paramp is always considered a statement now, as
>   it should be.  Actually, I thought that if the LIR_paramp was for an arg
>   it's an expression (ie.  it can be removed if dead), but if it's for a
>   savedReg it's a statement (ie. it cannot ever be removed).  But I got some
>   test failures when I tried that.  Any clarification on this point would be
>   welcome.

since LIR_paramp doesn't have any side effects, why should it be considered
a statement?  thing is, if its a savedReg, it *must* be live, or else something
is broken and that register is not being restored on exit.  Given that it must be
live, it shouldn't matter whether its a statement or expr.

For a plain argument (non savedReg), paramp should not have any effect if
the parameter is not referenced.  even if you make it a statement so gen()
is forced to process it, no code would be generated, right?

> - Similarly, I'd appreciate careful checking of the LIR_allocp case in
>   gen().  I think it's safe to treat LIR_allocp as an expression, ie. if the
>   result is never used it can be removed, but I'm not 100% certain.

That sounds right, TR does count on an un-referenced allocp being removed.
However, it's not cse-able, like immediates are.  Two allocp(4) instructions
for example are unique.

+            if (!ins->isLive())
+                goto ins_is_dead;

We should add an assert;  a !isLive() instruction should also be !isUsed(). 
this table might be useful documentation in LIR.h or gen()

isLive  isUsed  situation
------  ------  ---------
false   false   really dead, gen() skips before switch.
false   true    bug! need an assert
true    false   folded instruction or void statement
true    true    really live

Comment 8

[Nicholas Nethercote [inactive]]

(In reply to comment #7)
> (From update of attachment 440949 [details] [diff] [review])
> 
> If the only client of the new live bit is the verbose printer, then it could be
> more efficient and easier to maintain if we encapsulate the setting and
> checking of the live bit in a dedicated LirFilter, instead of weaving that code
> into gen().  Presumably the assembler, when running standalone, still can get
> what it needs with the inAr and inReg bits?
> 
> > ... having accurate liveness info at
> > codegen time will be necessary if the generalized conditionally-live guards go
> > ahead as described in bug 560994 comment 10.
> 
> ah, this is why we need the live bit even without verbose printing?

Yeah.  So I'd prefer to not put it in a separate LirFilter because that'll be slower.


> No matter what happens in Assembler, a side benefit of adding this bit is
> live() could be significantly simpler by using the live bit when a reference is
> seen, and clearing it when the instruction is seen.  it would completely
> eliminate "HashMap<LIns*, LIns*> live;" in class LiveTable.

True!  I'll try to do that.


> since LIR_paramp doesn't have any side effects, why should it be considered
> a statement?  thing is, if its a savedReg, it *must* be live, or else something
> is broken and that register is not being restored on exit.  Given that it must
> be
> live, it shouldn't matter whether its a statement or expr.

LIR_paramp is a weird case.  It has a result, but that result is never used.  The problem is that saved registers are handled partly explicitly in LIR, and partly implicitly.  This is why it'll be removed as dead if it's not marked as a statement.

One way to fix it would be to make them fully explicit -- have another instruction, call it LIR_unparamp for argument's sake, which is put at the end of blocks to restore the instruction.  Then the def/use pair is clear and the LIR_paramp wouldn't be removed.

A better way, which I think you've mentioned before, is to get rid of LIR_paramp for savedRegs altogether, ie. make them fully implicit.  It would also result in fewer instructions through the pipelines which would save a small amount of time.


> For a plain argument (non savedReg), paramp should not have any effect if
> the parameter is not referenced.  even if you make it a statement so gen()
> is forced to process it, no code would be generated, right?

Code is generated -- see asm_param().

 
> > - Similarly, I'd appreciate careful checking of the LIR_allocp case in
> >   gen().  I think it's safe to treat LIR_allocp as an expression, ie. if the
> >   result is never used it can be removed, but I'm not 100% certain.
> 
> That sounds right, TR does count on an un-referenced allocp being removed.
> However, it's not cse-able, like immediates are.  Two allocp(4) instructions
> for example are unique.

Right, that's what I thought.  We talk about statements and expressions but it's not really a simple binary split.  There are intermediate things like allocp that modify state but can also be removed by dead code elimination.  For this reason I wonder if changing isStmt() into something else -- eg. isCSEable and isDCEable() -- might be an improvement.


> We should add an assert;  a !isLive() instruction should also be !isUsed(). 
> this table might be useful documentation in LIR.h or gen()
> 
> isLive  isUsed  situation
> ------  ------  ---------
> false   false   really dead, gen() skips before switch.
> false   true    bug! need an assert
> true    false   folded instruction or void statement
> true    true    really live

Yes, I'll something like that.  isUsed() is actually not a good name... what it means is that the value has been explicitly computed and is currently sitting in a register or memory.  I like isExtant() better but that's an obscure word which might put people off.  Any other suggestions?

Comment 9

[Nicholas Nethercote [inactive]]

Attachment: patch v3

Reworked patch:

- I've removed most of the references to statements and expressions.  A
  binary split like that isn't helpful, the reality is more complicated, due
  to cases like LIR_paramp and LIR_allocp.  This included removing isStmt().

- I renamed isUsed() as isExtant().

- I renamed .isLiveExpr as .isResultLive;  this avoids the question of
  deciding if something is an expression or statement, which is unclear in
  some cases, replacing it with the notion of whether there is a return
  value, which is always clear.

- I fixed a bug in LiveTable::retire() -- it was including labels and jumps
  in the lists of live values, but excluding {add,sub,mul}xovi.  The new
  code is simpler.

- I changed all the inserts to LiveTable::live to use 0 as the second arg
  (the value) which makes it clear that it's never used -- only the key is
  ever used.

- I didn't change live() to use the .isResultLive bit;  turns out the 'live'
  table is still needed in LiveTable::retire().  Oh well.

Comment 10

[Nicholas Nethercote [inactive]]

Attachment: interdiff between v2 and v3

Why does the Bugzilla interdiff fail when the one on my Linux box succeeds?

Comment 11

[Edwin Smith]

Comment on attachment 441704 [details] [diff] [review]
patch v3

> Yes, I'll something like that.  isUsed() is actually not a good name... what it
> means is that the value has been explicitly computed and is currently sitting
> in a register or memory.  I like isExtant() better but that's an obscure word
> which might put people off.  Any other suggestions?

I'm finding isExtant() hard to read, but I can live with it (since it is well documented) if you don't want to do another patch gyration.  Other ideas:  isResultUsed, isResultNeeded, hasResult, hasResultValue, isResultAllocated.  Or, the not pretty but literal:  isInRegOrAr()

R+ whichever way the names come out :-)

Comment 12

[Nicholas Nethercote [inactive]]

(In reply to comment #11)
> 
Other ideas: 
> isResultUsed, isResultNeeded, hasResult, hasResultValue,

None of those communicate the idea that the value is available temporarily, and will disappear once we pass (moving backwards) its def-point.

> isResultAllocated. 
> Or, the not pretty but literal:  isInRegOrAr()

Mmm... I'll stick with isExtant, it has exactly the right meaning and will be educational for NJ readers :)

Comment 13

[Nicholas Nethercote [inactive]]

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

Comment 14

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/39515af6b064

Comment 15

[Edwin Smith]

TR: http://hg.mozilla.org/tamarin-redux/rev/a7d85e8dfbee

Comment 16

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/39515af6b064