• Benedikt Meurer's avatar
    [turbofan] Escape analysis support for LoadElement with variable index. · 3e43ded9
    Benedikt Meurer authored
    This adds support to the escape analysis to allow scalar replacement
    of (small) FixedArrays with element accesses where the index is not a
    compile time constant. This happens quite often when inlining functions
    that operate on variable number of arguments. For example consider this
    little piece of code:
    
    ```js
    function sum(...args) {
      let s = 0;
      for (let i = 0; i < args.length; ++i) s += args[i];
      return s;
    }
    
    function sum2(x, y) {
      return sum(x, y);
    }
    ```
    
    This example is made up, of course, but it shows the problem. Let's
    assume that TurboFan inlines the function `sum` into it's call site
    at `sum2`. Now it has to materialize the `args` array with the two
    values `x` and `y`, and iterate through these `args` to sum them up.
    The escape analysis pass figures out that `args` doesn't escape (aka
    doesn't outlive) the optimized code for `sum2` now, but TurboFan still
    needs to materialize the elements backing store for `args` since there's
    a `LoadElement(args.elements,i)` in the graph now, and `i` is not a
    compile time constant.
    
    However the escape analysis has more information than just that. In
    particular the escape analysis knows exactly how many elements a non
    escaping object has, based on the fact that the allocation must be
    local to the function and that we only track objects with known size.
    So in the case above when we get to `args[i]` in the escape analysis
    the relevant part of the graph looks something like this:
    
    ```
    elements = LoadField[elements](args)
    length = LoadField[length](args)
    index = CheckBounds(i, length)
    value = LoadElement(elements, index)
    ```
    
    In particular the contract here is that `LoadElement(elements,index)`
    is guaranteed to have an `index` that is within the valid bounds for
    the `elements` (there must be a preceeding `CheckBounds` or some other
    guard in optimized code before it). And since `elements` is allocated
    inside of the optimized code object, the escape analysis also knows
    that `elements` has exactly two elements inside (namely the values of
    `x` and `y`). So we can use that information and replace the access
    with a `Select(index===0,x,y)` operation instead, which allows us to
    scalar replace the `elements`, since there's no escaping use anymore
    in the graph.
    
    We do this for the case that the number of elements is 2, as described
    above, but also for the case where elements length is one. In case
    of 0, we know that the `LoadElement` must be in dead code, but we can't
    just mark it for deletion from the graph (to make sure it doesn't block
    scalar replacement of non-dead code), so we don't handle this for now.
    And for one element it's even easier, since the `LoadElement` has to
    yield exactly said element.
    
    We could generalize this to handle arbitrary lengths, but since there's
    a cost to arbitrary decision trees here, it's unclear when this is still
    beneficial. Another possible solution for length > 2 would be to have
    special stack allocation for these backing stores and do variable index
    accesses to these stack areas. But that's way beyond the scope of this
    isolated change.
    
    This change shows a ~2% improvement on the EarleyBoyer benchmark in
    JetStream, since it benefits a lot from not having to materialize these
    small arguments backing stores.
    
    Drive-by-fix: Fix JSCreateLowering to properly initialize "elements"
    with StoreElement instead of StoreField (which violates the invariant
    in TurboFan that fields and elements never alias).
    
    Bug: v8:5267, v8:6200
    Change-Id: Idd464a15a81e7c9653c48c814b406eb859841428
    Reviewed-on: https://chromium-review.googlesource.com/c/1267935
    Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
    Reviewed-by: 's avatarTobias Tebbi <tebbi@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#56442}
    3e43ded9
escape-analysis-array.js 865 Bytes