579285 - TM: [meta] improve sayrer's astar benchmark

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

Attachment: benchmark

This is a meta bug for improving TM's performance on the astar benchmark.  I extracted the .js file from the above URL and uncommented the "print(go())" at the end, which is enough to get it to run.

Cachegrind tells me that of the 3,734,799,157 instructions executed, 3,462,352,279 (93%) of them are in generated code.  Most of the remaining 7% is in parsing;  the script is over 50,000 lines because it defines what is conceptually a 100x100 array of bools in a monumentally stupid way.  So clearly generated code is worth focusing on.

Running with TMFLAGS=fragprofile tells me that 96.7% of the on-trace fragment executions occur in a single fragment, for this loop on line 8:

  Array.prototype.findGraphNode = function(obj) {
      for(var i=0;i<this.length;i++) {
          if(this[i].pos == obj.pos) { return this[i]; }
      }
      return false;
  };

Furthermore, it loops 99.94% of the time, exits because the loop bound is hit 0.04% of the time, and exits because the in-loop test succeeds 0.02%.

It's a very single-minded benchmark.

The LIR for this hot fragment is at the bottom of this comment.  There's nothing terribly surprising -- a 'this' determination, an array access, a couple of shape guards for the .pos property access.  There are three "class is Function" guards that I don't understand, they seem like they might be removable.

Just for a laugh I tried running it with my totally half-baked LICM patch applied (see bug 545406) and the running time reported by the script dropped from ~840ms to ~640ms, due to 5 out of 14 guards being hoisted.


      ebx = parami 0 ebx
      esi = parami 1 esi
      edi = parami 2 edi
      state = parami 0 ecx

      label1:
      sp = ldi.o state[8]
      cx = ldi.o state[0]
      ldi1 = ldi.csro cx[0]
      immi1 = immi 0
      eqi1 = eqi ldi1, immi1/*0*/
      xf1: xf eqi1 -> pc=0x85ce781 imacpc=(nil) sp+0 rp+0 (GuardID=001)

      $stack1 = ldi.s sp[-40]
      ldi2 = ldi.o $stack1[4]
      clasp = immi 136763968
      guard(class is With) = eqi ldi2, clasp/*136763968*/
      xt1: xt guard(class is With) -> pc=0x85ce782 imacpc=(nil) sp+0 rp+0 (GuardID=002)

      wrappedGlobal = immi -154136576
      ldi3 = ldi.o $stack1[24]
      eqi2 = eqi ldi3, immi1/*0*/
      cmovi1 = cmovi eqi2 ? wrappedGlobal/*-154136576*/ : $stack1
      sti.s sp[0] = cmovi1
      ldi4 = ldi.s sp[-8]
      sti.s sp[8] = ldi4
      ldi5 = ldi.o cmovi1[4]
      clasp2 = immi 136755168
      guard(class is Array) = eqi ldi5, clasp2/*136755168*/
      xf2: xf guard(class is Array) -> pc=0x85ce786 imacpc=(nil) sp+16 rp+0 (GuardID=003)

      dslots = ldi.o cmovi1[16]
      minLenCap = ldi.o cmovi1[48]
      ltui1 = ltui ldi4, minLenCap
      xf3: xf ltui1 -> pc=0x85ce786 imacpc=(nil) sp+16 rp+0 (GuardID=004)

      immi2 = immi 3
      lshi1 = lshi ldi4, immi2/*3*/
      addi1 = addi dslots, lshi1
      ldi6 = ldi.o addi1[4]
      JSVAL_TAG_OBJECT = immi -65529
      eqi3 = eqi ldi6, JSVAL_TAG_OBJECT/*-65529*/
      xf4: xf eqi3 -> pc=0x85ce786 imacpc=(nil) sp+16 rp+0 (GuardID=005)

      ldi7 = ldi.o addi1[0]
      ldi8 = ldi.o ldi7[4]
      clasp3 = immi 136760512
      guard(class is Function) = eqi ldi8, clasp3/*136760512*/
      xt2: xt guard(class is Function) -> pc=0x85ce786 imacpc=(nil) sp+16 rp+0 (GuardID=006)

      sti.s sp[0] = ldi7
      map = ldi.o ldi7[0]
      shape = ldi.o map[4]
      immi3 = immi 287
      guard_kshape = eqi shape, immi3/*287*/
      xf5: xf guard_kshape -> pc=0x85ce787 imacpc=(nil) sp+8 rp+0 (GuardID=007)

      ldi9 = ldi.o ldi7[16]
      ldi10 = ldi.o ldi9[4]
      eqi4 = eqi ldi10, JSVAL_TAG_OBJECT/*-65529*/
      xf6: xf eqi4 -> pc=0x85ce787 imacpc=(nil) sp+8 rp+0 (GuardID=008)

      ldi11 = ldi.o ldi9[0]
      ldi12 = ldi.o ldi11[4]
      guard(class is Function) = eqi ldi12, clasp3/*136760512*/
      xt3: xt guard(class is Function) -> pc=0x85ce787 imacpc=(nil) sp+8 rp+0 (GuardID=009)

      sti.s sp[0] = ldi11
      $stack2_2 = ldi.s sp[-32]
      map2 = ldi.o $stack2_2[0]
      shape2 = ldi.o map2[4]
      guard_kshape2 = eqi shape2, immi3/*287*/
      xf7: xf guard_kshape2 -> pc=0x85ce78a imacpc=(nil) sp+8 rp+0 (GuardID=010)

      ldi13 = ldi.o $stack2_2[16]
      ldi14 = ldi.o ldi13[4]
      eqi5 = eqi ldi14, JSVAL_TAG_OBJECT/*-65529*/
      xf8: xf eqi5 -> pc=0x85ce78a imacpc=(nil) sp+8 rp+0 (GuardID=011)

      ldi15 = ldi.o ldi13[0]
      ldi16 = ldi.o ldi15[4]
      guard(class is Function)2 = eqi ldi16, clasp3/*136760512*/
      xt4: xt guard(class is Function)2 -> pc=0x85ce78a imacpc=(nil) sp+8 rp+0 (GuardID=012)

      sti.s sp[8] = ldi15
      eqi6 = eqi ldi11, ldi15
      xt5: xt eqi6 -> pc=0x85ce78f imacpc=(nil) sp+16 rp+0 (GuardID=013)

      immi4 = immi 1
      addxovi1 = addxovi ldi4, immi4/*1*/ -> pc=0x85ce799 imacpc=(nil) sp+0 rp+0 (GuardID=014)
      sti.s sp[-8] = addxovi1
      sti.s sp[0] = addxovi1
      ldi17 = ldi.o cmovi1[32]
      sti.s sp[8] = ldi17
      lti1 = lti addxovi1, ldi17
      xf9: xf lti1 -> pc=0x85ce7a2 imacpc=(nil) sp+16 rp+0 (GuardID=017)

      j -> label1
      livei state

Comment 1

[Nicholas Nethercote [inactive]]

This tracking bug only has one bug blocking it, and ai-astar is now in Kraken, so we won't forget about it any time soon.