Changeset 218525 in webkit


Ignore:
Timestamp:
Jun 19, 2017 7:46:08 PM (7 years ago)
Author:
Yusuke Suzuki
Message:

[DFG] More ArrayIndexOf fixups for various types
​https://bugs.webkit.org/show_bug.cgi?id=173176

Reviewed by Saam Barati.

JSTests:

  • stress/array-indexof-arraystorage.js: Added.

(shouldBe):
(indexOfInt32Other):
(indexOfInt32Cell):
(indexOfInt32Boolean):
(indexOfDoubleOther):
(indexOfDoubleCell):
(indexOfDoubleBoolean):
(indexOfInt32):
(indexOfDouble):

  • stress/array-indexof-constant-folding.js: Added.

(shouldBe):
(indexOfInt32Other):
(indexOfInt32Cell):
(indexOfInt32Boolean):
(indexOfDoubleOther):
(indexOfDoubleCell):
(indexOfDoubleBoolean):

  • stress/array-indexof-hole-and-other.js: Added.

(shouldBe):
(indexOf):

  • stress/array-indexof-other.js: Added.

(shouldBe):
(indexOfInt32):
(indexOfDouble):
(indexOfString):
(indexOfObject):

  • stress/array-indexof-symbol.js: Added.

(shouldBe):
(indexOfInt32):
(indexOfDouble):
(indexOfString):
(indexOfObject):

Source/JavaScriptCore:

This patch further expands coverage of ArrayIndexOf optimization in DFG and FTL.

  1. We attempt to fold ArrayIndexOf to constant (-1) if we know that its array

never contains the given search value.

  1. We support Symbol and Other specialization additionally. Especially, Other is

useful because null/undefined can be used as a sentinel value.

One interesting thing is that Array.prototype.indexOf does not consider holes as
undefineds. Thus,

var array = [,];
array.indexOf(undefined); => -1

This can be trivially achieved in JSC because Empty and Undefined are different values.

  • dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::fixupArrayIndexOf):

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::compileArrayIndexOf):
(JSC::DFG::SpeculativeJIT::speculateOther):

  • dfg/DFGSpeculativeJIT.h:
  • ftl/FTLLowerDFGToB3.cpp:

(JSC::FTL::DFG::LowerDFGToB3::compileArrayIndexOf):

Location:
trunk
Files:
5 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r218512 r218525  
     12017-06-13  Yusuke Suzuki  <utatane.tea@gmail.com>
     2
     3        [DFG] More ArrayIndexOf fixups for various types
     4        https://bugs.webkit.org/show_bug.cgi?id=173176
     5
     6        Reviewed by Saam Barati.
     7
     8        * stress/array-indexof-arraystorage.js: Added.
     9        (shouldBe):
     10        (indexOfInt32Other):
     11        (indexOfInt32Cell):
     12        (indexOfInt32Boolean):
     13        (indexOfDoubleOther):
     14        (indexOfDoubleCell):
     15        (indexOfDoubleBoolean):
     16        (indexOfInt32):
     17        (indexOfDouble):
     18        * stress/array-indexof-constant-folding.js: Added.
     19        (shouldBe):
     20        (indexOfInt32Other):
     21        (indexOfInt32Cell):
     22        (indexOfInt32Boolean):
     23        (indexOfDoubleOther):
     24        (indexOfDoubleCell):
     25        (indexOfDoubleBoolean):
     26        * stress/array-indexof-hole-and-other.js: Added.
     27        (shouldBe):
     28        (indexOf):
     29        * stress/array-indexof-other.js: Added.
     30        (shouldBe):
     31        (indexOfInt32):
     32        (indexOfDouble):
     33        (indexOfString):
     34        (indexOfObject):
     35        * stress/array-indexof-symbol.js: Added.
     36        (shouldBe):
     37        (indexOfInt32):
     38        (indexOfDouble):
     39        (indexOfString):
     40        (indexOfObject):
     41
    1422017-06-19  Joseph Pecoraro  <pecoraro@apple.com>
    243

  • trunk/Source/JavaScriptCore/ChangeLog

    r218519 r218525  
     12017-06-13  Yusuke Suzuki  <utatane.tea@gmail.com>
     2
     3        [DFG] More ArrayIndexOf fixups for various types
     4        https://bugs.webkit.org/show_bug.cgi?id=173176
     5
     6        Reviewed by Saam Barati.
     7
     8        This patch further expands coverage of ArrayIndexOf optimization in DFG and FTL.
     9
     10        1. We attempt to fold ArrayIndexOf to constant (-1) if we know that its array
     11        never contains the given search value.
     12
     13        2. We support Symbol and Other specialization additionally. Especially, Other is
     14        useful because null/undefined can be used as a sentinel value.
     15
     16        One interesting thing is that Array.prototype.indexOf does not consider holes as
     17        undefineds. Thus,
     18
     19            var array = [,,,,,,,];
     20            array.indexOf(undefined); // => -1
     21
     22        This can be trivially achieved in JSC because Empty and Undefined are different values.
     23
     24        * dfg/DFGFixupPhase.cpp:
     25        (JSC::DFG::FixupPhase::fixupNode):
     26        (JSC::DFG::FixupPhase::fixupArrayIndexOf):
     27        * dfg/DFGSpeculativeJIT.cpp:
     28        (JSC::DFG::SpeculativeJIT::compileArrayIndexOf):
     29        (JSC::DFG::SpeculativeJIT::speculateOther):
     30        * dfg/DFGSpeculativeJIT.h:
     31        * ftl/FTLLowerDFGToB3.cpp:
     32        (JSC::FTL::DFG::LowerDFGToB3::compileArrayIndexOf):
     33
    1342017-06-19  Caio Lima  <ticaiolima@gmail.com>
    235

  • trunk/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp

    r218084 r218525  
    10241024        }
    10251025
    1026         case ArrayIndexOf: {
    1027             Edge& array = m_graph.varArgChild(node, 0);
    1028             Edge& storage = m_graph.varArgChild(node, node->numChildren() == 3 ? 2 : 3);
    1029             blessArrayOperation(array, Edge(), storage);
    1030             ASSERT_WITH_MESSAGE(storage.node(), "blessArrayOperation for ArrayIndexOf must set Butterfly for storage edge.");
    1031 
    1032             fixEdge<KnownCellUse>(array);
    1033             if (node->numChildren() == 4)
    1034                 fixEdge<Int32Use>(m_graph.varArgChild(node, 2));
    1035 
    1036             Edge& searchElement = m_graph.varArgChild(node, 1);
    1037             // FIXME: We have a chance to constant-fold this node to -1 by
    1038             // emitting non number edge filters.
    1039             // https://bugs.webkit.org/show_bug.cgi?id=173176
    1040             switch (node->arrayMode().type()) {
    1041             case Array::Double: {
    1042                 if (searchElement->shouldSpeculateNumber())
    1043                     fixEdge<DoubleRepUse>(searchElement);
    1044                 break;
    1045             }
    1046             case Array::Int32: {
    1047                 if (searchElement->shouldSpeculateInt32())
    1048                     fixEdge<Int32Use>(searchElement);
    1049                 break;
    1050             }
    1051             case Array::Contiguous: {
    1052                 if (searchElement->shouldSpeculateString())
    1053                     fixEdge<StringUse>(searchElement);
    1054                 else if (searchElement->shouldSpeculateObject())
    1055                     fixEdge<ObjectUse>(searchElement);
    1056                 break;
    1057             }
    1058             default:
    1059                 RELEASE_ASSERT_NOT_REACHED();
    1060                 break;
    1061             }
    1062             break;
    1063         }
     1026        case ArrayIndexOf:
     1027            fixupArrayIndexOf(node);
     1028            break;
    10641029           
    10651030        case RegExpExec:
    … …  
    30523017    }
    30533018
     3019    void fixupArrayIndexOf(Node* node)
     3020    {
     3021        Edge& array = m_graph.varArgChild(node, 0);
     3022        Edge& storage = m_graph.varArgChild(node, node->numChildren() == 3 ? 2 : 3);
     3023        blessArrayOperation(array, Edge(), storage);
     3024        ASSERT_WITH_MESSAGE(storage.node(), "blessArrayOperation for ArrayIndexOf must set Butterfly for storage edge.");
     3025
     3026        Edge& searchElement = m_graph.varArgChild(node, 1);
     3027
     3028        // Constant folding.
     3029        switch (node->arrayMode().type()) {
     3030        case Array::Double:
     3031        case Array::Int32: {
     3032            if (searchElement->shouldSpeculateCell()) {
     3033                m_insertionSet.insertNode(m_indexInBlock, SpecNone, Check, node->origin, Edge(searchElement.node(), CellUse));
     3034                m_graph.convertToConstant(node, jsNumber(-1));
     3035                observeUseKindOnNode<CellUse>(searchElement.node());
     3036                return;
     3037            }
     3038
     3039            if (searchElement->shouldSpeculateOther()) {
     3040                m_insertionSet.insertNode(m_indexInBlock, SpecNone, Check, node->origin, Edge(searchElement.node(), OtherUse));
     3041                m_graph.convertToConstant(node, jsNumber(-1));
     3042                observeUseKindOnNode<OtherUse>(searchElement.node());
     3043                return;
     3044            }
     3045
     3046            if (searchElement->shouldSpeculateBoolean()) {
     3047                m_insertionSet.insertNode(m_indexInBlock, SpecNone, Check, node->origin, Edge(searchElement.node(), BooleanUse));
     3048                m_graph.convertToConstant(node, jsNumber(-1));
     3049                observeUseKindOnNode<BooleanUse>(searchElement.node());
     3050                return;
     3051            }
     3052            break;
     3053        }
     3054        default:
     3055            break;
     3056        }
     3057
     3058        fixEdge<KnownCellUse>(array);
     3059        if (node->numChildren() == 4)
     3060            fixEdge<Int32Use>(m_graph.varArgChild(node, 2));
     3061
     3062        switch (node->arrayMode().type()) {
     3063        case Array::Double: {
     3064            if (searchElement->shouldSpeculateNumber())
     3065                fixEdge<DoubleRepUse>(searchElement);
     3066            return;
     3067        }
     3068        case Array::Int32: {
     3069            if (searchElement->shouldSpeculateInt32())
     3070                fixEdge<Int32Use>(searchElement);
     3071            return;
     3072        }
     3073        case Array::Contiguous: {
     3074            if (searchElement->shouldSpeculateString())
     3075                fixEdge<StringUse>(searchElement);
     3076            else if (searchElement->shouldSpeculateSymbol())
     3077                fixEdge<SymbolUse>(searchElement);
     3078            else if (searchElement->shouldSpeculateOther())
     3079                fixEdge<OtherUse>(searchElement);
     3080            else if (searchElement->shouldSpeculateObject())
     3081                fixEdge<ObjectUse>(searchElement);
     3082            return;
     3083        }
     3084        default:
     3085            RELEASE_ASSERT_NOT_REACHED();
     3086            return;
     3087        }
     3088    }
     3089
    30543090    void fixupChecksInBlock(BasicBlock* block)
    30553091    {

  • trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp

    r218312 r218525  
    74807480    switch (searchElementEdge.useKind()) {
    74817481    case Int32Use:
    7482     case ObjectUse: {
     7482    case ObjectUse:
     7483    case SymbolUse:
     7484    case OtherUse: {
    74837485        auto emitLoop = [&] (auto emitCompare) {
    74847486#if ENABLE(DFG_REGISTER_ALLOCATION_VALIDATION)
    … …  
    75027504            int32Result(indexGPR, node);
    75037505        };
    7504 
    7505 #if USE(JSVALUE32_64)
    7506         GPRTemporary temp(this);
    7507         GPRReg tempGPR = temp.gpr();
    7508 #endif
    75097506
    75107507        if (searchElementEdge.useKind() == Int32Use) {
    … …  
    75187515            SpeculateInt32Operand searchElement(this, searchElementEdge);
    75197516            GPRReg searchElementGPR = searchElement.gpr();
     7517
     7518            GPRTemporary temp(this);
     7519            GPRReg tempGPR = temp.gpr();
    75207520#endif
    75217521            emitLoop([&] () {
    … …  
    75307530                return found;
    75317531            });
    7532         } else {
     7532            return;
     7533        }
     7534
     7535        if (searchElementEdge.useKind() == OtherUse) {
    75337536            ASSERT(node->arrayMode().type() == Array::Contiguous);
    7534             SpeculateCellOperand searchElement(this, searchElementEdge);
    7535             GPRReg searchElementGPR = searchElement.gpr();
    7536             speculateObject(searchElementEdge, searchElementGPR);
     7537            JSValueOperand searchElement(this, searchElementEdge, ManualOperandSpeculation);
     7538            GPRTemporary temp(this);
     7539
     7540            JSValueRegs searchElementRegs = searchElement.jsValueRegs();
     7541            GPRReg tempGPR = temp.gpr();
     7542            speculateOther(searchElementEdge, searchElementRegs, tempGPR);
    75377543
    75387544            emitLoop([&] () {
    75397545#if USE(JSVALUE64)
    7540                 auto found = m_jit.branch64(CCallHelpers::Equal, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight), searchElementGPR);
     7546                auto found = m_jit.branch64(CCallHelpers::Equal, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight), searchElementRegs.payloadGPR());
    75417547#else
    7542                 auto skip = m_jit.branch32(CCallHelpers::NotEqual, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, TagOffset), TrustedImm32(JSValue::CellTag));
    7543                 m_jit.load32(MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, PayloadOffset), tempGPR);
    7544                 auto found = m_jit.branch32(CCallHelpers::Equal, tempGPR, searchElementGPR);
    7545                 skip.link(&m_jit);
     7548                m_jit.load32(MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, TagOffset), tempGPR);
     7549                auto found = m_jit.branch32(CCallHelpers::Equal, tempGPR, searchElementRegs.tagGPR());
    75467550#endif
    75477551                return found;
    75487552            });
    7549         }
    7550         break;
     7553            return;
     7554        }
     7555
     7556        ASSERT(node->arrayMode().type() == Array::Contiguous);
     7557        SpeculateCellOperand searchElement(this, searchElementEdge);
     7558        GPRReg searchElementGPR = searchElement.gpr();
     7559
     7560        if (searchElementEdge.useKind() == ObjectUse)
     7561            speculateObject(searchElementEdge, searchElementGPR);
     7562        else {
     7563            ASSERT(searchElementEdge.useKind() == SymbolUse);
     7564            speculateSymbol(searchElementEdge, searchElementGPR);
     7565        }
     7566
     7567#if USE(JSVALUE32_64)
     7568        GPRTemporary temp(this);
     7569        GPRReg tempGPR = temp.gpr();
     7570#endif
     7571
     7572        emitLoop([&] () {
     7573#if USE(JSVALUE64)
     7574            auto found = m_jit.branch64(CCallHelpers::Equal, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight), searchElementGPR);
     7575#else
     7576            auto skip = m_jit.branch32(CCallHelpers::NotEqual, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, TagOffset), TrustedImm32(JSValue::CellTag));
     7577            m_jit.load32(MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, PayloadOffset), tempGPR);
     7578            auto found = m_jit.branch32(CCallHelpers::Equal, tempGPR, searchElementGPR);
     7579            skip.link(&m_jit);
     7580#endif
     7581            return found;
     7582        });
     7583        return;
    75517584    }
    75527585
    … …  
    75777610        found.link(&m_jit);
    75787611        int32Result(indexGPR, node);
    7579         break;
     7612        return;
    75807613    }
    75817614
    … …  
    75947627
    75957628        int32Result(lengthGPR, node);
    7596         break;
     7629        return;
    75977630    }
    75987631
    … …  
    76187651
    76197652        int32Result(lengthGPR, node);
    7620         break;
     7653        return;
    76217654    }
    76227655
    76237656    default:
    76247657        RELEASE_ASSERT_NOT_REACHED();
    7625         break;
     7658        return;
    76267659    }
    76277660}
    … …  
    89168949}
    89178950
    8918 void SpeculativeJIT::speculateOther(Edge edge)
     8951void SpeculativeJIT::speculateOther(Edge edge, JSValueRegs regs, GPRReg tempGPR)
     8952{
     8953    DFG_TYPE_CHECK(regs, edge, SpecOther, m_jit.branchIfNotOther(regs, tempGPR));
     8954}
     8955
     8956void SpeculativeJIT::speculateOther(Edge edge, JSValueRegs regs)
    89198957{
    89208958    if (!needsTypeCheck(edge, SpecOther))
    89218959        return;
    8922    
    8923     JSValueOperand operand(this, edge, ManualOperandSpeculation);
     8960
    89248961    GPRTemporary temp(this);
    89258962    GPRReg tempGPR = temp.gpr();
    8926     typeCheck(
    8927         operand.jsValueRegs(), edge, SpecOther,
    8928         m_jit.branchIfNotOther(operand.jsValueRegs(), tempGPR));
     8963    speculateOther(edge, regs, tempGPR);
     8964}
     8965
     8966void SpeculativeJIT::speculateOther(Edge edge)
     8967{
     8968    if (!needsTypeCheck(edge, SpecOther))
     8969        return;
     8970   
     8971    JSValueOperand operand(this, edge, ManualOperandSpeculation);
     8972    speculateOther(edge, operand.jsValueRegs());
    89298973}
    89308974

  • trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h

    r218084 r218525  
    30093009    void speculateNotCell(Edge, JSValueRegs);
    30103010    void speculateNotCell(Edge);
     3011    void speculateOther(Edge, JSValueRegs, GPRReg temp);
     3012    void speculateOther(Edge, JSValueRegs);
    30113013    void speculateOther(Edge);
    30123014    void speculateMisc(Edge, JSValueRegs);

  • trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp

    r218137 r218525  
    40734073        case Int32Use:
    40744074        case ObjectUse:
     4075        case SymbolUse:
     4076        case OtherUse:
    40754077        case DoubleRepUse: {
    40764078            LBasicBlock loopHeader = m_out.newBlock();
    … …  
    40814083
    40824084            LValue searchElement;
    4083             if (searchElementEdge.useKind() == Int32Use) {
     4085            switch (searchElementEdge.useKind()) {
     4086            case Int32Use:
    40844087                ASSERT(m_node->arrayMode().type() == Array::Int32);
    40854088                speculate(searchElementEdge);
    40864089                searchElement = lowJSValue(searchElementEdge, ManualOperandSpeculation);
    4087             } else if (searchElementEdge.useKind() == ObjectUse) {
     4090                break;
     4091            case ObjectUse:
    40884092                ASSERT(m_node->arrayMode().type() == Array::Contiguous);
    40894093                searchElement = lowObject(searchElementEdge);
    4090             } else {
     4094                break;
     4095            case SymbolUse:
     4096                ASSERT(m_node->arrayMode().type() == Array::Contiguous);
     4097                searchElement = lowSymbol(searchElementEdge);
     4098                break;
     4099            case OtherUse:
     4100                ASSERT(m_node->arrayMode().type() == Array::Contiguous);
     4101                speculate(searchElementEdge);
     4102                searchElement = lowJSValue(searchElementEdge, ManualOperandSpeculation);
     4103                break;
     4104            case DoubleRepUse:
    40914105                ASSERT(m_node->arrayMode().type() == Array::Double);
    40924106                searchElement = lowDouble(searchElementEdge);
     4107                break;
     4108            default:
     4109                RELEASE_ASSERT_NOT_REACHED();
     4110                break;
    40934111            }
    40944112
    … …  
    41054123            m_out.appendTo(loopBody, loopNext);
    41064124            ValueFromBlock foundResult = m_out.anchor(index);
    4107             if (searchElementEdge.useKind() == Int32Use) {
     4125            switch (searchElementEdge.useKind()) {
     4126            case Int32Use: {
    41084127                // Empty value is ignored because of TagTypeNumber.
    41094128                LValue value = m_out.load64(m_out.baseIndex(m_heaps.indexedInt32Properties, storage, index));
    41104129                m_out.branch(m_out.equal(value, searchElement), unsure(continuation), unsure(loopNext));
    4111             } else if (searchElementEdge.useKind() == ObjectUse) {
    4112                 // Empty value never matches against object pointers.
     4130                break;
     4131            }
     4132            case ObjectUse:
     4133            case SymbolUse:
     4134            case OtherUse: {
     4135                // Empty value never matches against non-empty JS values.
    41134136                LValue value = m_out.load64(m_out.baseIndex(m_heaps.indexedContiguousProperties, storage, index));
    41144137                m_out.branch(m_out.equal(value, searchElement), unsure(continuation), unsure(loopNext));
    4115             } else {
     4138                break;
     4139            }
     4140            case DoubleRepUse: {
    41164141                // Empty value is ignored because of NaN.
    41174142                LValue value = m_out.loadDouble(m_out.baseIndex(m_heaps.indexedDoubleProperties, storage, index));
    41184143                m_out.branch(m_out.doubleEqual(value, searchElement), unsure(continuation), unsure(loopNext));
     4144                break;
     4145            }
     4146            default:
     4147                RELEASE_ASSERT_NOT_REACHED();
     4148                break;
    41194149            }
    41204150
Note: See TracChangeset for help on using the changeset viewer.