531840 - Optimize deadvars()

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect, P3)

Description

[Edwin Smith]

The deadvars() pass currently has a couple of opportunities to optimize:

1. deadvars_kill() works by erasing instructions, by overwriting them with LIR_skip.  Instead, it could be turned into a LirFilter subclass, and run inline with the assembler, which a) eliminates one pass, and b) does not require erasing instructions with LIR_skip.  This, in turn, lets LirReader::read() avoid needing a loop for skipping LIR_skip instructions; the loop can be turned into an if since there won't be multiple consequitive skips.

2. the deadvars_kill pass still must analyze each instruction, since deadvars_analyze() only remembers live/dead store states at blocks starting with LIR_label.  Since it's doing the analysis, this is the *only* required pass in any method with no loops.  so:  skip deadvars_analyze() if there are no backward edges.  we can detect this condition in the first pass while LIR is created.

Comment 1

[Edwin Smith]

Attachment: working prototype, introduces DeadStoreAnalyzer and DeadStoreFilter

not ready to land yet, but comments on the direction are appreciated.

Comment 2

[Edwin Smith]

DeadStoreFilter appears to be a generalized version of nanojit::StackFilter that deals with arbitrary control flow (branches, labels, plus exception edges).

Comment 3

[Edwin Smith]

Comment on attachment 415190 [details] [diff] [review]
working prototype, introduces DeadStoreAnalyzer and DeadStoreFilter

i will rebase this and r? again soon.

Comment 4

[Edwin Smith]

marking "major" with the expectation of a nontrivial improvement in jit compiler speed.

Comment 5

[Edwin Smith]

Observation:
  - only a vanishingly small % of methods have >64 local vars  (even >32 is a small %).
  - most methods dont contain loops

So, we could write a single-pass, non-iterative version of deadvars, that uses a plain uint64_t mask for liveness tracking, and execute it in-line with code generation.   in fact, this case might already be implemented correctly in StackFilter (which uses a BitSet, but the BitSet could be templatized).

Comment 6

[Edwin Smith]

Unassigning - patch is old and I probably won't have time to work on this any time soon.  The idea is still valid, though; we could still perform the equivalent of deadvars_kill() concurrently with the assembler pass.

Comment 7

[Edwin Smith]

targeting dolores in the hopes of improving jit compiler speed for gaming - will need to update patch, and/or try the approach from comment #5, then measure the effect on jit speed.