Upgrade to Pro — share decks privately, control downloads, hide ads and more …

CSS JIT: Optimizing CSS Selector Matching with ...

CSS JIT: Optimizing CSS Selector Matching with Just-in-Time Compilation

CSS Selector matching is used for Style Resolution and SelectorQuerying.
We describe CSS Selector JIT in WebKit, optimizing CSS Selector Matching with Just-in-Time compilation techniques.
NOTE: http://constellation.github.io/blog/2014/07/14/webkit-css-jit-internals/

Yusuke SUZUKI

July 14, 2014
Tweet

More Decks by Yusuke SUZUKI

Other Decks in Programming

Transcript

  1. Motivation • CSS Selector is executed frequently • Style Resolution

    / QuerySelector – For each node, check selector match/fail over node • Speed of selector matching is important for Rendering / JS (Selectors API) .rabbit.house { … } CSS StyleSheet
  2. Motivation • CSS Selector is executed frequently • Style Resolution

    / QuerySelector – For each node, check selector match/fail over node • Speed of selector matching is important for Rendering / JS (Selectors API) .rabbit.house { … } CSS StyleSheet Selector Matching
  3. QuerySelector implementation • root.querySelectorAll(/* selector */) 1. For each element

    under root 1. Do selector matching with selector and element (SelectorChecker in WebKit / Blink) 2. if matched 1. result.append(element) 2. Return result • querySelectorAll executes selector matching the number of elements times
  4. Goals • Provide faster selector matching – Make style resolution

    faster – Make JS code using QuerySelector faster
  5. Existing CSS Selector Implementation • Highly tuned C++ implementation (WebKit/Blink)

    • SelectorChecker::match • SelectorChecker::matchRecursively • SelectorChecker::checkOne • … recursively call markRecursively (backtracking is needed)
  6. CSS Selector Structure & Terminology • Composed of compound selectors

    – simple selector (e.g. div) + combinator (e.g. >) • Selector is evaluated from-right-to-left span div > div + div compound selectors (div+ div~ div div> span) div ~ descendant child following- sibling next- sibling rightmost http://dev.w3.org/csswg/selectors4/#structure
  7. Evaluation Example • body div span case span div body

    section div span p h3 section body section div div p span Matching starts with this span
  8. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  9. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  10. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  11. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  12. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  13. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  14. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  15. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  16. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  17. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  18. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  19. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  20. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div
  21. Evaluation Example: Matched • body div span case span div

    body section div span p h3 section body section div p span div Matched
  22. Evaluation Example: Failed • body div> span case span div>

    body section div span p h3 section body section div p span div
  23. Evaluation Example: Failed • body div> span case span div>

    body section div span p h3 section body section div p span div
  24. Evaluation Example: Failed • body div> span case span div>

    body section div span p h3 section body section div p span div
  25. Evaluation Example: Failed • body div> span case span div>

    body section div span p h3 section body section div p span div
  26. Evaluation Example: Failed • body div> span case span div>

    body section div span p h3 section body section div p span div
  27. Evaluation Example: Failed • body div> span case span div>

    body section div span p h3 section body section div p span div Failed
  28. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  29. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  30. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  31. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  32. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  33. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  34. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  35. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  36. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  37. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  38. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  39. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  40. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div
  41. Evaluation Example: Backtracking • body> div> div span case •

    When child(xxx>) is failed, backtracking with the closest descendant(xxx) span div> body> div div span body div div div Matched
  42. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  43. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  44. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  45. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  46. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  47. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  48. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  49. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  50. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  51. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  52. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  53. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  54. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  55. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  56. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div
  57. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div Failed Completely
  58. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div Failed Completely
  59. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div Failed Completely
  60. Evaluation Example: Backtracking • section> div div span case •

    When descendant(xxx) is failed, selector matching completely failes. span div section> div div span body div div div Failed Completely Candidates become less
  61. CSS Selector JIT • Just-in-Time compile Selector Matching predicate –

    Provide faster selector matching • Leverage selector’s static data to generate highly optimized machine code
  62. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span
  63. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL SUCCESS
  64. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL SUCCESS unmatch
  65. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL SUCCESS unmatch Parent
  66. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL SUCCESS unmatch no parent Parent
  67. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL div SUCCESS unmatch no parent Parent
  68. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL div SUCCESS unmatch no parent Parent unmatch
  69. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL div SUCCESS unmatch no parent Parent unmatch Parent
  70. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL div SUCCESS unmatch no parent no parent Parent unmatch Parent
  71. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL div SUCCESS unmatch no parent no parent Parent unmatch Parent div
  72. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL div SUCCESS unmatch no parent no parent Parent unmatch Parent div unmatch (current register is already suitable)
  73. Compiling machine code • Represent CSS Selector Matching with code

    & jumps – Avoid recursive function call (NO CALLS!) – Storing current element to register Example 1: div> div span span FAIL div SUCCESS unmatch no parent no parent Parent unmatch Parent div unmatch (current register is already suitable)
  74. Compiling machine code • Storing backtracking element to one register

    Example 2: div> div> div span span FAIL div P unmatch div P unmatch unmatch no parent
  75. Compiling machine code • Storing backtracking element to one register

    Example 2: div> div> div span span FAIL div P unmatch div P unmatch unmatch no parent save
  76. Compiling machine code • Storing backtracking element to one register

    Example 2: div> div> div span span FAIL div P unmatch div P unmatch unmatch no parent save P
  77. Compiling machine code • Storing backtracking element to one register

    Example 2: div> div> div span span FAIL div P unmatch div P unmatch unmatch no parent save P no parent
  78. Compiling machine code • Storing backtracking element to one register

    Example 2: div> div> div span span FAIL div P unmatch div P unmatch unmatch no parent save P div no parent
  79. Compiling machine code • Storing backtracking element to one register

    Example 2: div> div> div span span FAIL div P unmatch div P unmatch unmatch no parent save P div no parent unmatch backtrack with saved register
  80. Compiling machine code • Storing backtracking element to one register

    Example 2: div> div> div span span FAIL div SUCCESS P unmatch div P unmatch unmatch no parent save P div no parent unmatch backtrack with saved register
  81. Compiling machine code • Storing backtracking element to one register

    – Since only one descendant should be considered Example 3: div> div> div div> div> div span span FAIL div P div P unmatch save P div unmatch with saved
  82. Compiling machine code • Storing backtracking element to one register

    – Since only one descendant should be considered Example 3: div> div> div div> div> div span span FAIL div P div P unmatch save P div unmatch with saved div P div P save P div unmatch with saved SUCCESS
  83. div> div span Code Generated JIT code for CSS Selector

    JIT for "div > div span": Code at [0x7fd031187000, 0x7fd0311870a0): 0x7fd031187000: push %rbp 0x7fd031187001: mov 0x58(%rdi), %rax 0x7fd031187005: mov $0x7fd08c30ec50, %rcx 0x7fd03118700f: cmp %rcx, 0x18(%rax) 0x7fd031187013: jnz 0x7fd031187081 0x7fd031187019: mov 0x20(%rdi), %rdi 0x7fd03118701d: test %rdi, %rdi 0x7fd031187020: jz 0x7fd031187081 0x7fd031187026: test $0x4, 0x1c(%rdi) 0x7fd03118702a: jz 0x7fd031187081 0x7fd031187030: mov 0x58(%rdi), %rdx 0x7fd031187034: mov $0x7fd08c30f670, %rsi 0x7fd03118703e: cmp %rsi, 0x18(%rdx) 0x7fd031187042: jnz 0x7fd031187019 0x7fd031187048: mov 0x20(%rdi), %rdi 0x7fd03118704c: test %rdi, %rdi 0x7fd03118704f: jz 0x7fd031187081 0x7fd031187055: test $0x4, 0x1c(%rdi) 0x7fd031187059: jz 0x7fd031187081 0x7fd03118705f: mov 0x58(%rdi), %r8 0x7fd031187063: mov $0x7fd08c30f670, %r9 0x7fd03118706d: cmp %r9, 0x18(%r8) 0x7fd031187071: jnz 0x7fd031187019 0x7fd031187077: mov $0x1, %eax 0x7fd03118707c: jmp 0x7fd031187083 0x7fd031187081: xor %eax, %eax 0x7fd031187083: pop %rbp 0x7fd031187084: ret
  84. div> div span Code Generated JIT code for CSS Selector

    JIT for "div > div span": Code at [0x7fd031187000, 0x7fd0311870a0): 0x7fd031187000: push %rbp 0x7fd031187001: mov 0x58(%rdi), %rax 0x7fd031187005: mov $0x7fd08c30ec50, %rcx 0x7fd03118700f: cmp %rcx, 0x18(%rax) 0x7fd031187013: jnz 0x7fd031187081 0x7fd031187019: mov 0x20(%rdi), %rdi 0x7fd03118701d: test %rdi, %rdi 0x7fd031187020: jz 0x7fd031187081 0x7fd031187026: test $0x4, 0x1c(%rdi) 0x7fd03118702a: jz 0x7fd031187081 0x7fd031187030: mov 0x58(%rdi), %rdx 0x7fd031187034: mov $0x7fd08c30f670, %rsi 0x7fd03118703e: cmp %rsi, 0x18(%rdx) 0x7fd031187042: jnz 0x7fd031187019 0x7fd031187048: mov 0x20(%rdi), %rdi 0x7fd03118704c: test %rdi, %rdi 0x7fd03118704f: jz 0x7fd031187081 0x7fd031187055: test $0x4, 0x1c(%rdi) 0x7fd031187059: jz 0x7fd031187081 0x7fd03118705f: mov 0x58(%rdi), %r8 0x7fd031187063: mov $0x7fd08c30f670, %r9 0x7fd03118706d: cmp %r9, 0x18(%r8) 0x7fd031187071: jnz 0x7fd031187019 0x7fd031187077: mov $0x1, %eax 0x7fd03118707c: jmp 0x7fd031187083 0x7fd031187081: xor %eax, %eax 0x7fd031187083: pop %rbp 0x7fd031187084: ret span
  85. div> div span Code Generated JIT code for CSS Selector

    JIT for "div > div span": Code at [0x7fd031187000, 0x7fd0311870a0): 0x7fd031187000: push %rbp 0x7fd031187001: mov 0x58(%rdi), %rax 0x7fd031187005: mov $0x7fd08c30ec50, %rcx 0x7fd03118700f: cmp %rcx, 0x18(%rax) 0x7fd031187013: jnz 0x7fd031187081 0x7fd031187019: mov 0x20(%rdi), %rdi 0x7fd03118701d: test %rdi, %rdi 0x7fd031187020: jz 0x7fd031187081 0x7fd031187026: test $0x4, 0x1c(%rdi) 0x7fd03118702a: jz 0x7fd031187081 0x7fd031187030: mov 0x58(%rdi), %rdx 0x7fd031187034: mov $0x7fd08c30f670, %rsi 0x7fd03118703e: cmp %rsi, 0x18(%rdx) 0x7fd031187042: jnz 0x7fd031187019 0x7fd031187048: mov 0x20(%rdi), %rdi 0x7fd03118704c: test %rdi, %rdi 0x7fd03118704f: jz 0x7fd031187081 0x7fd031187055: test $0x4, 0x1c(%rdi) 0x7fd031187059: jz 0x7fd031187081 0x7fd03118705f: mov 0x58(%rdi), %r8 0x7fd031187063: mov $0x7fd08c30f670, %r9 0x7fd03118706d: cmp %r9, 0x18(%r8) 0x7fd031187071: jnz 0x7fd031187019 0x7fd031187077: mov $0x1, %eax 0x7fd03118707c: jmp 0x7fd031187083 0x7fd031187081: xor %eax, %eax 0x7fd031187083: pop %rbp 0x7fd031187084: ret span FAIL
  86. div> div span Code Generated JIT code for CSS Selector

    JIT for "div > div span": Code at [0x7fd031187000, 0x7fd0311870a0): 0x7fd031187000: push %rbp 0x7fd031187001: mov 0x58(%rdi), %rax 0x7fd031187005: mov $0x7fd08c30ec50, %rcx 0x7fd03118700f: cmp %rcx, 0x18(%rax) 0x7fd031187013: jnz 0x7fd031187081 0x7fd031187019: mov 0x20(%rdi), %rdi 0x7fd03118701d: test %rdi, %rdi 0x7fd031187020: jz 0x7fd031187081 0x7fd031187026: test $0x4, 0x1c(%rdi) 0x7fd03118702a: jz 0x7fd031187081 0x7fd031187030: mov 0x58(%rdi), %rdx 0x7fd031187034: mov $0x7fd08c30f670, %rsi 0x7fd03118703e: cmp %rsi, 0x18(%rdx) 0x7fd031187042: jnz 0x7fd031187019 0x7fd031187048: mov 0x20(%rdi), %rdi 0x7fd03118704c: test %rdi, %rdi 0x7fd03118704f: jz 0x7fd031187081 0x7fd031187055: test $0x4, 0x1c(%rdi) 0x7fd031187059: jz 0x7fd031187081 0x7fd03118705f: mov 0x58(%rdi), %r8 0x7fd031187063: mov $0x7fd08c30f670, %r9 0x7fd03118706d: cmp %r9, 0x18(%r8) 0x7fd031187071: jnz 0x7fd031187019 0x7fd031187077: mov $0x1, %eax 0x7fd03118707c: jmp 0x7fd031187083 0x7fd031187081: xor %eax, %eax 0x7fd031187083: pop %rbp 0x7fd031187084: ret span FAIL parent parent
  87. div> div span Code Generated JIT code for CSS Selector

    JIT for "div > div span": Code at [0x7fd031187000, 0x7fd0311870a0): 0x7fd031187000: push %rbp 0x7fd031187001: mov 0x58(%rdi), %rax 0x7fd031187005: mov $0x7fd08c30ec50, %rcx 0x7fd03118700f: cmp %rcx, 0x18(%rax) 0x7fd031187013: jnz 0x7fd031187081 0x7fd031187019: mov 0x20(%rdi), %rdi 0x7fd03118701d: test %rdi, %rdi 0x7fd031187020: jz 0x7fd031187081 0x7fd031187026: test $0x4, 0x1c(%rdi) 0x7fd03118702a: jz 0x7fd031187081 0x7fd031187030: mov 0x58(%rdi), %rdx 0x7fd031187034: mov $0x7fd08c30f670, %rsi 0x7fd03118703e: cmp %rsi, 0x18(%rdx) 0x7fd031187042: jnz 0x7fd031187019 0x7fd031187048: mov 0x20(%rdi), %rdi 0x7fd03118704c: test %rdi, %rdi 0x7fd03118704f: jz 0x7fd031187081 0x7fd031187055: test $0x4, 0x1c(%rdi) 0x7fd031187059: jz 0x7fd031187081 0x7fd03118705f: mov 0x58(%rdi), %r8 0x7fd031187063: mov $0x7fd08c30f670, %r9 0x7fd03118706d: cmp %r9, 0x18(%r8) 0x7fd031187071: jnz 0x7fd031187019 0x7fd031187077: mov $0x1, %eax 0x7fd03118707c: jmp 0x7fd031187083 0x7fd031187081: xor %eax, %eax 0x7fd031187083: pop %rbp 0x7fd031187084: ret span FAIL div parent parent
  88. div> div span Code Generated JIT code for CSS Selector

    JIT for "div > div span": Code at [0x7fd031187000, 0x7fd0311870a0): 0x7fd031187000: push %rbp 0x7fd031187001: mov 0x58(%rdi), %rax 0x7fd031187005: mov $0x7fd08c30ec50, %rcx 0x7fd03118700f: cmp %rcx, 0x18(%rax) 0x7fd031187013: jnz 0x7fd031187081 0x7fd031187019: mov 0x20(%rdi), %rdi 0x7fd03118701d: test %rdi, %rdi 0x7fd031187020: jz 0x7fd031187081 0x7fd031187026: test $0x4, 0x1c(%rdi) 0x7fd03118702a: jz 0x7fd031187081 0x7fd031187030: mov 0x58(%rdi), %rdx 0x7fd031187034: mov $0x7fd08c30f670, %rsi 0x7fd03118703e: cmp %rsi, 0x18(%rdx) 0x7fd031187042: jnz 0x7fd031187019 0x7fd031187048: mov 0x20(%rdi), %rdi 0x7fd03118704c: test %rdi, %rdi 0x7fd03118704f: jz 0x7fd031187081 0x7fd031187055: test $0x4, 0x1c(%rdi) 0x7fd031187059: jz 0x7fd031187081 0x7fd03118705f: mov 0x58(%rdi), %r8 0x7fd031187063: mov $0x7fd08c30f670, %r9 0x7fd03118706d: cmp %r9, 0x18(%r8) 0x7fd031187071: jnz 0x7fd031187019 0x7fd031187077: mov $0x1, %eax 0x7fd03118707c: jmp 0x7fd031187083 0x7fd031187081: xor %eax, %eax 0x7fd031187083: pop %rbp 0x7fd031187084: ret span FAIL div div parent parent
  89. div> div span Code Generated JIT code for CSS Selector

    JIT for "div > div span": Code at [0x7fd031187000, 0x7fd0311870a0): 0x7fd031187000: push %rbp 0x7fd031187001: mov 0x58(%rdi), %rax 0x7fd031187005: mov $0x7fd08c30ec50, %rcx 0x7fd03118700f: cmp %rcx, 0x18(%rax) 0x7fd031187013: jnz 0x7fd031187081 0x7fd031187019: mov 0x20(%rdi), %rdi 0x7fd03118701d: test %rdi, %rdi 0x7fd031187020: jz 0x7fd031187081 0x7fd031187026: test $0x4, 0x1c(%rdi) 0x7fd03118702a: jz 0x7fd031187081 0x7fd031187030: mov 0x58(%rdi), %rdx 0x7fd031187034: mov $0x7fd08c30f670, %rsi 0x7fd03118703e: cmp %rsi, 0x18(%rdx) 0x7fd031187042: jnz 0x7fd031187019 0x7fd031187048: mov 0x20(%rdi), %rdi 0x7fd03118704c: test %rdi, %rdi 0x7fd03118704f: jz 0x7fd031187081 0x7fd031187055: test $0x4, 0x1c(%rdi) 0x7fd031187059: jz 0x7fd031187081 0x7fd03118705f: mov 0x58(%rdi), %r8 0x7fd031187063: mov $0x7fd08c30f670, %r9 0x7fd03118706d: cmp %r9, 0x18(%r8) 0x7fd031187071: jnz 0x7fd031187019 0x7fd031187077: mov $0x1, %eax 0x7fd03118707c: jmp 0x7fd031187083 0x7fd031187081: xor %eax, %eax 0x7fd031187083: pop %rbp 0x7fd031187084: ret span FAIL div div parent parent SUCCESS
  90. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  91. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  92. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  93. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  94. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  95. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  96. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  97. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  98. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  99. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  100. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul
  101. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul Done
  102. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul But Ideal Backtracking is…
  103. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul But Ideal Backtracking is…
  104. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul But Ideal Backtracking is…
  105. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul But Ideal Backtracking is…
  106. More intelligent backtracking • Leveraging this static information, provide more

    intelligent backtracking – This is my largest contribution to WebKit CSS JIT Example 4: ul> li> p span span li> ul> p ol span li li p p ul But Ideal Backtracking is…
  107. Computing Backtracking height • Pre-compute appropriate backtracking height Example 4:

    ul> li> p span span li> ul> p pre-tag height 0 2 1 0 1 2 span FAIL p SUCCESS P unmatch li P unmatch unmatch no parent save P ul no parent unmatch backtrack with saved register
  108. Computing Backtracking height • Pre-compute appropriate backtracking height Example 4:

    ul> li> p span span li> ul> p pre-tag height 0 2 1 0 1 2 span FAIL p SUCCESS P unmatch li P unmatch unmatch no parent P ul no parent unmatch
  109. Status • x64 / ARMv7s / ARMv7 / ARM64 backend

    • More intelligent backtracking is now planned – Most of implementation is done – Before implementing it, I’ll instrument/profile the impact of this • Seeing the Safari release branch… – Maybe shipped with the next OSX – not in iOS8… See you next year, CSS Selector JIT! – In iOS 8 beta3! Hello CSS Selector JIT in your iPhone!
  110. Conclusion • Selector matching is crucial • CSS Selector JIT

    brings up to the next stage – Avoid function calls – Store almost all to the registers – Provide faster performance • Intelligent backtracking – Reduces register pressure – Avoid unnecessary backtraking