421982 - Tracer spends lots of time traversing LIns -- need revisions to make it more efficient

Status: VERIFIED WONTFIX

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

Description

[Steven Johnson]

We spend an awful lot of time dealing with LIns traversal in tracing:

-- LCompressedReader::previous is called a jillion times and is measurable in lots of places in Shark; could we somehow rethink our opcode layout so
that previous() could be effectively inlined?

-- LIns seems to be laid out with the assumption we only need to traverse backwards, but in the cse/loop opt code we laboriously copy (and recopy) into an InsList so we can traverse forwards. This takes a lot of time; crypto-md5 spends ~8% of its time in forms of this loop:

        for (LCompressedReader r(ins); ins != 0; ins = r.previous())
            lir.add(ins);

Rick's thoughts:
 
The forward traversal can be solved by putting a LIR_skip above gaps in the instruction stream. For example right now, we layout a 32bit imm like so,

 0
 4  imm_val
 8  LIR_imm32
   
with the skip we'd do it like,

 0 LIR_skip
 4 imm_val
 8 LIR_imm32

This chews up 4Bytes but gives us a generic means by which we can traverse forward. The next piece would be to pack things a little tighter; for example imm32 would become:

  4  LIR_imm32_lo
  8  LIR_imm32_hi

where we then bitshift and or to get the constant, but you get the idea. The idea being to normalize the stream into either a LIR_skip or +/- increment and have no other variants.

Another idea is to separate the constants from the instruction stream -- what if we had a constant area per page and we started at the bottom of the page and grew it up until it collided with the downwards growing LIR stream. That way all instructions would be +/-1 and access to the constant pool would be 4Byte index-based on a 16bit offset contained in the instruction.

Comment 1

[Rick Reitmaier]

changing component to 'nanojit' - Seeing as these issues have not come up recently I'm assuming we can retire this bug?

Comment 2

[Chris Peyer]

removing QRB request, bug verified