[Webkit-unassigned] [Bug 50295] New: Regexp JIT'ed Code Contains Branches to Branches for Backtracking

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=50295

           Summary: Regexp JIT'ed Code Contains Branches to Branches for
                    Backtracking
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: Enhancement
          Priority: P2
         Component: JavaScriptCore
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: msaboff at apple.com


The regular expression JIT compiler currently generates code one term at a time.  A term may contain backtracking logic to handle trying another alternative of a parenthetical subexpression.  The generated code often contains sequences of branches to branches.  There are also branches around some logic.  If that logic was moved some of those jumps could be eliminated.

This is one of the issues covered by <rdar://problem/8511767>.

Here is a symbolic version of the code generated for /(a|A)(b|B)/ 
        push   %rbp
        mov    %rsp,%rbp
        push   %rbx
        mov    %esi,(%rcx)
        sub    $0x10,%rsp
        add    $0x2,%esi
        cmp    %edx,%esi
        ja     nextChar
loop:
        mov    %rsi,%rax
        add    $0xfffffffffffffffe,%eax
        mov    %eax,0x8(%rcx)
        cmpw   $0x61,-0x4(%rdi,%rsi,2)
        jne    tryAlt1A
        mov    $tryAlt1A,%r11
        mov    %r11,(%rsp)
        jmpq   term1Match
tryAlt1A:
        cmpw   $0x41,-0x4(%rdi,%rsi,2)
        jne    term1AFail  // Jump to a jump
        mov    $term1AFail,%r11
        mov    %r11,(%rsp)
        jmpq   term1Match  // Jump around two other jumps
term1AFail:
        jmpq   term1Fail
backTrackTerm1Select:
        jmpq   *(%rsp)
term1Match:
        mov    %rsi,%rax
        add    $0xffffffffffffffff,%eax
        mov    %eax,0xc(%rcx)
        jmpq   startTerm2  // Jump around "fail" code
backTrackTerm1:
        jmpq   backTrackTerm1Select  // Jump to an indirect jump
term1Fail:
        movl   $0xffffffff,0x8(%rcx)
        jmpq   nextChar
startTerm2:
        mov    %rsi,%rax
        add    $0xffffffffffffffff,%eax
        mov    %eax,0x10(%rcx)
        cmpw   $0x62,-0x2(%rdi,%rsi,2)
        jne    tryAlt2B
        mov    $tryAlt2B,%r11
        mov    %r11,0x8(%rsp)
        jmpq   term2Match
tryAlt2B:
        cmpw   $0x42,-0x2(%rdi,%rsi,2)
        jne    term2BFail
        mov    $term2BFail,%r11
        mov    %r11,0x8(%rsp)
        jmpq   term2Match  // Jump around jumps
term2BFail:
        jmpq   term2Fail
backTrackTerm2Select:
        jmpq   *0x8(%rsp)  // Unused code
term2Match:
        mov    %esi,0x14(%rcx)
        jmpq   matchSuccess  // Jump around "fail" logic
        jmpq   backTrackTerm2Select  // Jump to an indirect jump - also not used!!
term2Fail:
        movl   $0xffffffff,0x10(%rcx)
        jmpq   backTrackTerm1  // << Jump to a jump to an indirect jump
matchSuccess:
        add    $0x10,%rsp
        mov    (%rcx),%eax
        mov    %esi,0x4(%rcx)
        pop    %rbx
        pop    %rbp
        retq   
nextChar:
        mov    %rsi,%rax
        sub    $0x1,%eax
        mov    %eax,(%rcx)
        add    $0x1,%esi
        cmp    %edx,%esi
        jbe    loop
        add    $0x10,%rsp
        mov    $0xffffffff,%eax
        pop    %rbx
        pop    %rbp
        retq

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.