• Leszek Swirski's avatar
    [parser] Add an n-ary node for large binop chains · 52ef2a1c
    Leszek Swirski authored
    Expressions of the form
    
        a_0 + a_1 + a_2 + a_3 + ... + a_n
    
    seem to be reasonably common for cases such as building templates.
    However, parsing these expressions results in a n-deep expression tree:
    
               ...
              /
             +
            / \
           +  a_2
          / \
        a_0 a_1
    
    Traversing this tree during compilation can cause a stack overflow when n is
    large.
    
    Instead, for left-associate operations such as add, we now build up an
    n-ary node in the parse tree, of the form
    
             n-ary +
           /  |      \
          /   |  ...  \
        a_0  a_1      a_n
    
    The bytecode compiler can now iterate through the child expressions
    rather than recursing.
    
    This patch only supports arithmetic operations -- subsequent patches
    will enable the same optimization for logical tests and comma
    expressions.
    
    Bug: v8:6964
    Bug: chromium:724961
    Bug: chromium:731861
    Bug: chromium:752081
    Bug: chromium:771653
    Bug: chromium:777302
    Change-Id: Ie97e4ce42506fe62a7bc4ffbdaa90a9f698352cb
    Reviewed-on: https://chromium-review.googlesource.com/733120
    Commit-Queue: Leszek Swirski <leszeks@chromium.org>
    Reviewed-by: 's avatarMarja Hölttä <marja@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#48920}
    52ef2a1c
unoptimized-compile-job-unittest.cc 12.6 KB