Source/JavaScriptCore:
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGStrengthReductionPhase.cpp
1 /*
2  * Copyright (C) 2013-2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "DFGStrengthReductionPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractHeap.h"
32 #include "DFGClobberize.h"
33 #include "DFGGraph.h"
34 #include "DFGInsertionSet.h"
35 #include "DFGPhase.h"
36 #include "DFGPredictionPropagationPhase.h"
37 #include "DFGVariableAccessDataDump.h"
38 #include "JSCInlines.h"
39 #include "RegExpConstructor.h"
40 #include "StringPrototype.h"
41 #include <cstdlib>
42
43 namespace JSC { namespace DFG {
44
45 class StrengthReductionPhase : public Phase {
46     static const bool verbose = false;
47     
48 public:
49     StrengthReductionPhase(Graph& graph)
50         : Phase(graph, "strength reduction")
51         , m_insertionSet(graph)
52     {
53     }
54     
55     bool run()
56     {
57         ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
58         
59         m_changed = false;
60         
61         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
62             m_block = m_graph.block(blockIndex);
63             if (!m_block)
64                 continue;
65             for (m_nodeIndex = 0; m_nodeIndex < m_block->size(); ++m_nodeIndex) {
66                 m_node = m_block->at(m_nodeIndex);
67                 handleNode();
68             }
69             m_insertionSet.execute(m_block);
70         }
71         
72         return m_changed;
73     }
74
75 private:
76     void handleNode()
77     {
78         switch (m_node->op()) {
79         case BitOr:
80             handleCommutativity();
81
82             if (m_node->child1().useKind() != UntypedUse && m_node->child2()->isInt32Constant() && !m_node->child2()->asInt32()) {
83                 convertToIdentityOverChild1();
84                 break;
85             }
86             break;
87             
88         case BitXor:
89         case BitAnd:
90             handleCommutativity();
91             break;
92             
93         case BitLShift:
94         case BitRShift:
95         case BitURShift:
96             if (m_node->child1().useKind() != UntypedUse && m_node->child2()->isInt32Constant() && !(m_node->child2()->asInt32() & 0x1f)) {
97                 convertToIdentityOverChild1();
98                 break;
99             }
100             break;
101             
102         case UInt32ToNumber:
103             if (m_node->child1()->op() == BitURShift
104                 && m_node->child1()->child2()->isInt32Constant()
105                 && (m_node->child1()->child2()->asInt32() & 0x1f)
106                 && m_node->arithMode() != Arith::DoOverflow) {
107                 m_node->convertToIdentity();
108                 m_changed = true;
109                 break;
110             }
111             break;
112             
113         case ArithAdd:
114             handleCommutativity();
115             
116             if (m_node->child2()->isInt32Constant() && !m_node->child2()->asInt32()) {
117                 convertToIdentityOverChild1();
118                 break;
119             }
120             break;
121             
122         case ArithMul: {
123             handleCommutativity();
124             Edge& child2 = m_node->child2();
125             if (child2->isNumberConstant() && child2->asNumber() == 2) {
126                 switch (m_node->binaryUseKind()) {
127                 case DoubleRepUse:
128                     // It is always valuable to get rid of a double multiplication by 2.
129                     // We won't have half-register dependencies issues on x86 and we won't have to load the constants.
130                     m_node->setOp(ArithAdd);
131                     child2.setNode(m_node->child1().node());
132                     m_changed = true;
133                     break;
134 #if USE(JSVALUE64)
135                 case Int52RepUse:
136 #endif
137                 case Int32Use:
138                     // For integers, we can only convert compatible modes.
139                     // ArithAdd does handle do negative zero check for example.
140                     if (m_node->arithMode() == Arith::CheckOverflow || m_node->arithMode() == Arith::Unchecked) {
141                         m_node->setOp(ArithAdd);
142                         child2.setNode(m_node->child1().node());
143                         m_changed = true;
144                     }
145                     break;
146                 default:
147                     break;
148                 }
149             }
150             break;
151         }
152         case ArithSub:
153             if (m_node->child2()->isInt32Constant()
154                 && m_node->isBinaryUseKind(Int32Use)) {
155                 int32_t value = m_node->child2()->asInt32();
156                 if (-value != value) {
157                     m_node->setOp(ArithAdd);
158                     m_node->child2().setNode(
159                         m_insertionSet.insertConstant(
160                             m_nodeIndex, m_node->origin, jsNumber(-value)));
161                     m_changed = true;
162                     break;
163                 }
164             }
165             break;
166
167         case ArithPow:
168             if (m_node->child2()->isNumberConstant()) {
169                 double yOperandValue = m_node->child2()->asNumber();
170                 if (yOperandValue == 1) {
171                     convertToIdentityOverChild1();
172                 } else if (yOperandValue == 0.5) {
173                     m_insertionSet.insertCheck(m_nodeIndex, m_node);
174                     m_node->convertToArithSqrt();
175                     m_changed = true;
176                 }
177             }
178             break;
179
180         case ArithMod:
181             // On Integers
182             // In: ArithMod(ArithMod(x, const1), const2)
183             // Out: Identity(ArithMod(x, const1))
184             //     if const1 <= const2.
185             if (m_node->binaryUseKind() == Int32Use
186                 && m_node->child2()->isInt32Constant()
187                 && m_node->child1()->op() == ArithMod
188                 && m_node->child1()->binaryUseKind() == Int32Use
189                 && m_node->child1()->child2()->isInt32Constant()
190                 && std::abs(m_node->child1()->child2()->asInt32()) <= std::abs(m_node->child2()->asInt32())) {
191                     convertToIdentityOverChild1();
192             }
193             break;
194
195         case ValueRep:
196         case Int52Rep:
197         case DoubleRep: {
198             // This short-circuits circuitous conversions, like ValueRep(DoubleRep(value)) or
199             // even more complicated things. Like, it can handle a beast like
200             // ValueRep(DoubleRep(Int52Rep(value))).
201             
202             // The only speculation that we would do beyond validating that we have a type that
203             // can be represented a certain way is an Int32 check that would appear on Int52Rep
204             // nodes. For now, if we see this and the final type we want is an Int52, we use it
205             // as an excuse not to fold. The only thing we would need is a Int52RepInt32Use kind.
206             bool hadInt32Check = false;
207             if (m_node->op() == Int52Rep) {
208                 if (m_node->child1().useKind() != Int32Use)
209                     break;
210                 hadInt32Check = true;
211             }
212             for (Node* node = m_node->child1().node(); ; node = node->child1().node()) {
213                 if (canonicalResultRepresentation(node->result()) ==
214                     canonicalResultRepresentation(m_node->result())) {
215                     m_insertionSet.insertCheck(m_nodeIndex, m_node);
216                     if (hadInt32Check) {
217                         // FIXME: Consider adding Int52RepInt32Use or even DoubleRepInt32Use,
218                         // which would be super weird. The latter would only arise in some
219                         // seriously circuitous conversions.
220                         if (canonicalResultRepresentation(node->result()) != NodeResultJS)
221                             break;
222                         
223                         m_insertionSet.insertCheck(
224                             m_nodeIndex, m_node->origin, Edge(node, Int32Use));
225                     }
226                     m_node->child1() = node->defaultEdge();
227                     m_node->convertToIdentity();
228                     m_changed = true;
229                     break;
230                 }
231                 
232                 switch (node->op()) {
233                 case Int52Rep:
234                     if (node->child1().useKind() != Int32Use)
235                         break;
236                     hadInt32Check = true;
237                     continue;
238                     
239                 case DoubleRep:
240                 case ValueRep:
241                     continue;
242                     
243                 default:
244                     break;
245                 }
246                 break;
247             }
248             break;
249         }
250             
251         case Flush: {
252             ASSERT(m_graph.m_form != SSA);
253             
254             Node* setLocal = nullptr;
255             VirtualRegister local = m_node->local();
256             
257             for (unsigned i = m_nodeIndex; i--;) {
258                 Node* node = m_block->at(i);
259                 if (node->op() == SetLocal && node->local() == local) {
260                     setLocal = node;
261                     break;
262                 }
263                 if (accessesOverlap(m_graph, node, AbstractHeap(Stack, local)))
264                     break;
265             }
266             
267             if (!setLocal)
268                 break;
269             
270             // The Flush should become a PhantomLocal at this point. This means that we want the
271             // local's value during OSR, but we don't care if the value is stored to the stack. CPS
272             // rethreading can canonicalize PhantomLocals for us.
273             m_node->convertFlushToPhantomLocal();
274             m_graph.dethread();
275             m_changed = true;
276             break;
277         }
278
279         // FIXME: we should probably do this in constant folding but this currently relies on an OSR exit rule.
280         // https://bugs.webkit.org/show_bug.cgi?id=154832
281         case OverridesHasInstance: {
282             if (!m_node->child2().node()->isCellConstant())
283                 break;
284
285             if (m_node->child2().node()->asCell() != m_graph.globalObjectFor(m_node->origin.semantic)->functionProtoHasInstanceSymbolFunction()) {
286                 m_graph.convertToConstant(m_node, jsBoolean(true));
287                 m_changed = true;
288
289             } else if (!m_graph.hasExitSite(m_node->origin.semantic, BadTypeInfoFlags)) {
290                 // We optimistically assume that we will not see a function that has a custom instanceof operation as they should be rare.
291                 m_insertionSet.insertNode(m_nodeIndex, SpecNone, CheckTypeInfoFlags, m_node->origin, OpInfo(ImplementsDefaultHasInstance), Edge(m_node->child1().node(), CellUse));
292                 m_graph.convertToConstant(m_node, jsBoolean(false));
293                 m_changed = true;
294             }
295
296             break;
297         }
298
299         // FIXME: We have a lot of string constant-folding rules here. It would be great to
300         // move these to the abstract interpreter once AbstractValue can support LazyJSValue.
301         // https://bugs.webkit.org/show_bug.cgi?id=155204
302
303         case MakeRope:
304         case ValueAdd:
305         case StrCat: {
306             String leftString = m_node->child1()->tryGetString(m_graph);
307             if (!leftString)
308                 break;
309             String rightString = m_node->child2()->tryGetString(m_graph);
310             if (!rightString)
311                 break;
312             String extraString;
313             if (m_node->child3()) {
314                 extraString = m_node->child3()->tryGetString(m_graph);
315                 if (!extraString)
316                     break;
317             }
318
319             StringBuilder builder;
320             builder.append(leftString);
321             builder.append(rightString);
322             if (!!extraString)
323                 builder.append(extraString);
324
325             m_node->convertToLazyJSConstant(
326                 m_graph, LazyJSValue::newString(m_graph, builder.toString()));
327             m_changed = true;
328             break;
329         }
330
331         case GetArrayLength: {
332             if (m_node->arrayMode().type() == Array::Generic
333                 || m_node->arrayMode().type() == Array::String) {
334                 String string = m_node->child1()->tryGetString(m_graph);
335                 if (!!string) {
336                     m_graph.convertToConstant(m_node, jsNumber(string.length()));
337                     m_changed = true;
338                     break;
339                 }
340             }
341             break;
342         }
343
344         case GetGlobalObject: {
345             if (JSObject* object = m_node->child1()->dynamicCastConstant<JSObject*>()) {
346                 m_graph.convertToConstant(m_node, object->globalObject());
347                 m_changed = true;
348                 break;
349             }
350             break;
351         }
352
353         case RegExpExec:
354         case RegExpTest: {
355             JSGlobalObject* globalObject = m_node->child1()->dynamicCastConstant<JSGlobalObject*>();
356             if (!globalObject) {
357                 if (verbose)
358                     dataLog("Giving up because no global object.\n");
359                 break;
360             }
361
362             if (globalObject->isHavingABadTime()) {
363                 if (verbose)
364                     dataLog("Giving up because bad time.\n");
365                 break;
366             }
367
368             Node* regExpObjectNode = m_node->child2().node();
369             RegExp* regExp;
370             if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>())
371                 regExp = regExpObject->regExp();
372             else if (regExpObjectNode->op() == NewRegexp)
373                 regExp = codeBlock()->regexp(regExpObjectNode->regexpIndex());
374             else {
375                 if (verbose)
376                     dataLog("Giving up because the regexp is unknown.\n");
377                 break;
378             }
379
380             Node* stringNode = m_node->child3().node();
381             
382             // NOTE: This mostly already protects us from having the compiler execute a regexp
383             // operation on a ginormous string by preventing us from getting our hands on ginormous
384             // strings in the first place.
385             String string = m_node->child3()->tryGetString(m_graph);
386             if (!string) {
387                 if (verbose)
388                     dataLog("Giving up because the string is unknown.\n");
389                 break;
390             }
391
392             FrozenValue* regExpFrozenValue = m_graph.freeze(regExp);
393
394             // Refuse to do things with regular expressions that have a ginormous number of
395             // subpatterns.
396             unsigned ginormousNumberOfSubPatterns = 1000;
397             if (regExp->numSubpatterns() > ginormousNumberOfSubPatterns) {
398                 if (verbose)
399                     dataLog("Giving up because of pattern limit.\n");
400                 break;
401             }
402
403             unsigned lastIndex;
404             if (regExp->globalOrSticky()) {
405                 // This will only work if we can prove what the value of lastIndex is. To do this
406                 // safely, we need to execute the insertion set so that we see any previous strength
407                 // reductions. This is needed for soundness since otherwise the effectfulness of any
408                 // previous strength reductions would be invisible to us.
409                 executeInsertionSet();
410                 lastIndex = UINT_MAX;
411                 for (unsigned otherNodeIndex = m_nodeIndex; otherNodeIndex--;) {
412                     Node* otherNode = m_block->at(otherNodeIndex);
413                     if (otherNode == regExpObjectNode) {
414                         lastIndex = 0;
415                         break;
416                     }
417                     if (otherNode->op() == SetRegExpObjectLastIndex
418                         && otherNode->child1() == regExpObjectNode
419                         && otherNode->child2()->isInt32Constant()
420                         && otherNode->child2()->asInt32() >= 0) {
421                         lastIndex = static_cast<unsigned>(otherNode->child2()->asInt32());
422                         break;
423                     }
424                     if (writesOverlap(m_graph, otherNode, RegExpObject_lastIndex))
425                         break;
426                 }
427                 if (lastIndex == UINT_MAX) {
428                     if (verbose)
429                         dataLog("Giving up because the last index is not known.\n");
430                     break;
431                 }
432             } else
433                 lastIndex = 0;
434
435             m_graph.watchpoints().addLazily(globalObject->havingABadTimeWatchpoint());
436             
437             Structure* structure = globalObject->regExpMatchesArrayStructure();
438             if (structure->indexingType() != ArrayWithContiguous) {
439                 // This is further protection against a race with haveABadTime.
440                 if (verbose)
441                     dataLog("Giving up because the structure has the wrong indexing type.\n");
442                 break;
443             }
444             m_graph.registerStructure(structure);
445
446             RegExpConstructor* constructor = globalObject->regExpConstructor();
447             FrozenValue* constructorFrozenValue = m_graph.freeze(constructor);
448
449             MatchResult result;
450             Vector<int, 32> ovector;
451             // We have to call the kind of match function that the main thread would have called.
452             // Otherwise, we might not have the desired Yarr code compiled, and the match will fail.
453             if (m_node->op() == RegExpExec) {
454                 int position;
455                 if (!regExp->matchConcurrently(vm(), string, lastIndex, position, ovector)) {
456                     if (verbose)
457                         dataLog("Giving up because match failed.\n");
458                     break;
459                 }
460                 result.start = position;
461                 result.end = ovector[1];
462             } else {
463                 if (!regExp->matchConcurrently(vm(), string, lastIndex, result)) {
464                     if (verbose)
465                         dataLog("Giving up because match failed.\n");
466                     break;
467                 }
468             }
469
470             // We've constant-folded the regexp. Now we're committed to replacing RegExpExec/Test.
471
472             m_changed = true;
473
474             NodeOrigin origin = m_node->origin;
475
476             m_insertionSet.insertNode(
477                 m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
478
479             if (m_node->op() == RegExpExec) {
480                 if (result) {
481                     StructureSet* structureSet = m_graph.addStructureSet(structure);
482
483                     // Create an array modeling the JS array that we will try to allocate. This is
484                     // basically createRegExpMatchesArray but over C++ strings instead of JSStrings.
485                     Vector<String> resultArray;
486                     resultArray.append(string.substring(result.start, result.end - result.start));
487                     for (unsigned i = 1; i <= regExp->numSubpatterns(); ++i) {
488                         int start = ovector[2 * i];
489                         if (start >= 0)
490                             resultArray.append(string.substring(start, ovector[2 * i + 1] - start));
491                         else
492                             resultArray.append(String());
493                     }
494
495                     unsigned publicLength = resultArray.size();
496                     unsigned vectorLength = std::max(BASE_VECTOR_LEN, publicLength);
497
498                     UniquedStringImpl* indexUID = vm().propertyNames->index.impl();
499                     UniquedStringImpl* inputUID = vm().propertyNames->input.impl();
500                     unsigned indexIndex = m_graph.identifiers().ensure(indexUID);
501                     unsigned inputIndex = m_graph.identifiers().ensure(inputUID);
502
503                     unsigned firstChild = m_graph.m_varArgChildren.size();
504                     m_graph.m_varArgChildren.append(
505                         m_insertionSet.insertConstantForUse(
506                             m_nodeIndex, origin, structure, KnownCellUse));
507                     ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
508             
509                     m_graph.m_varArgChildren.append(
510                         m_insertionSet.insertConstantForUse(
511                             m_nodeIndex, origin, jsNumber(publicLength), KnownInt32Use));
512                     data->m_properties.append(PublicLengthPLoc);
513             
514                     m_graph.m_varArgChildren.append(
515                         m_insertionSet.insertConstantForUse(
516                             m_nodeIndex, origin, jsNumber(vectorLength), KnownInt32Use));
517                     data->m_properties.append(VectorLengthPLoc);
518
519                     m_graph.m_varArgChildren.append(
520                         m_insertionSet.insertConstantForUse(
521                             m_nodeIndex, origin, jsNumber(result.start), UntypedUse));
522                     data->m_properties.append(
523                         PromotedLocationDescriptor(NamedPropertyPLoc, indexIndex));
524
525                     m_graph.m_varArgChildren.append(Edge(stringNode, UntypedUse));
526                     data->m_properties.append(
527                         PromotedLocationDescriptor(NamedPropertyPLoc, inputIndex));
528
529                     auto materializeString = [&] (const String& string) -> Node* {
530                         if (string.isNull())
531                             return nullptr;
532                         if (string.isEmpty()) {
533                             return m_insertionSet.insertConstant(
534                                 m_nodeIndex, origin, vm().smallStrings.emptyString());
535                         }
536                         LazyJSValue value = LazyJSValue::newString(m_graph, string);
537                         return m_insertionSet.insertNode(
538                             m_nodeIndex, SpecNone, LazyJSConstant, origin,
539                             OpInfo(m_graph.m_lazyJSValues.add(value)));
540                     };
541
542                     for (unsigned i = 0; i < resultArray.size(); ++i) {
543                         if (Node* node = materializeString(resultArray[i])) {
544                             m_graph.m_varArgChildren.append(Edge(node, UntypedUse));
545                             data->m_properties.append(
546                                 PromotedLocationDescriptor(IndexedPropertyPLoc, i));
547                         }
548                     }
549             
550                     Node* resultNode = m_insertionSet.insertNode(
551                         m_nodeIndex, SpecArray, Node::VarArg, MaterializeNewObject, origin,
552                         OpInfo(structureSet), OpInfo(data), firstChild,
553                         m_graph.m_varArgChildren.size() - firstChild);
554                 
555                     m_node->convertToIdentityOn(resultNode);
556                 } else
557                     m_graph.convertToConstant(m_node, jsNull());
558             } else
559                 m_graph.convertToConstant(m_node, jsBoolean(!!result));
560
561             // Whether it's Exec or Test, we need to tell the constructor and RegExpObject what's up.
562             // Because SetRegExpObjectLastIndex may exit and it clobbers exit state, we do that
563             // first.
564             
565             if (regExp->globalOrSticky()) {
566                 m_insertionSet.insertNode(
567                     m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
568                     Edge(regExpObjectNode, RegExpObjectUse),
569                     m_insertionSet.insertConstantForUse(
570                         m_nodeIndex, origin, jsNumber(result ? result.end : 0), UntypedUse));
571                 
572                 origin = origin.withInvalidExit();
573             }
574
575             if (result) {
576                 unsigned firstChild = m_graph.m_varArgChildren.size();
577                 m_graph.m_varArgChildren.append(
578                     m_insertionSet.insertConstantForUse(
579                         m_nodeIndex, origin, constructorFrozenValue, KnownCellUse));
580                 m_graph.m_varArgChildren.append(
581                     m_insertionSet.insertConstantForUse(
582                         m_nodeIndex, origin, regExpFrozenValue, KnownCellUse));
583                 m_graph.m_varArgChildren.append(Edge(stringNode, KnownCellUse));
584                 m_graph.m_varArgChildren.append(
585                     m_insertionSet.insertConstantForUse(
586                         m_nodeIndex, origin, jsNumber(result.start), KnownInt32Use));
587                 m_graph.m_varArgChildren.append(
588                     m_insertionSet.insertConstantForUse(
589                         m_nodeIndex, origin, jsNumber(result.end), KnownInt32Use));
590                 m_insertionSet.insertNode(
591                     m_nodeIndex, SpecNone, Node::VarArg, RecordRegExpCachedResult, origin,
592                     OpInfo(), OpInfo(), firstChild, m_graph.m_varArgChildren.size() - firstChild);
593
594                 origin = origin.withInvalidExit();
595             }
596             
597             m_node->origin = origin;
598             break;
599         }
600
601         case StringReplace: {
602             Node* stringNode = m_node->child1().node();
603             String string = stringNode->tryGetString(m_graph);
604             if (!string)
605                 break;
606             
607             Node* regExpObjectNode = m_node->child2().node();
608             RegExp* regExp;
609             if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>())
610                 regExp = regExpObject->regExp();
611             else if (regExpObjectNode->op() == NewRegexp)
612                 regExp = codeBlock()->regexp(regExpObjectNode->regexpIndex());
613             else {
614                 if (verbose)
615                     dataLog("Giving up because the regexp is unknown.\n");
616                 break;
617             }
618
619             String replace = m_node->child3()->tryGetString(m_graph);
620             if (!string)
621                 break;
622
623             StringBuilder builder;
624
625             unsigned lastIndex = 0;
626             unsigned startPosition = 0;
627             bool ok = true;
628             do {
629                 MatchResult result;
630                 Vector<int, 32> ovector;
631                 // Model which version of match() is called by the main thread.
632                 if (replace.isEmpty() && regExp->global()) {
633                     if (!regExp->matchConcurrently(vm(), string, startPosition, result)) {
634                         ok = false;
635                         break;
636                     }
637                 } else {
638                     int position;
639                     if (!regExp->matchConcurrently(vm(), string, startPosition, position, ovector)) {
640                         ok = false;
641                         break;
642                     }
643                     
644                     result.start = position;
645                     result.end = ovector[1];
646                 }
647                 
648                 if (!result)
649                     break;
650
651                 unsigned replLen = replace.length();
652                 if (lastIndex < result.start || replLen) {
653                     builder.append(string, lastIndex, result.start - lastIndex);
654                     if (replLen)
655                         builder.append(substituteBackreferences(replace, string, ovector.data(), regExp));
656                 }
657
658                 lastIndex = result.end;
659                 startPosition = lastIndex;
660
661                 // special case of empty match
662                 if (result.empty()) {
663                     startPosition++;
664                     if (startPosition > string.length())
665                         break;
666                 }
667             } while (regExp->global());
668             if (!ok)
669                 break;
670
671             // We are committed at this point.
672             m_changed = true;
673
674             NodeOrigin origin = m_node->origin;
675
676             if (regExp->global()) {
677                 m_insertionSet.insertNode(
678                     m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
679                     Edge(regExpObjectNode, RegExpObjectUse),
680                     m_insertionSet.insertConstantForUse(
681                         m_nodeIndex, origin, jsNumber(0), UntypedUse));
682                 
683                 origin = origin.withInvalidExit();
684             }
685
686             if (!lastIndex && builder.isEmpty())
687                 m_node->convertToIdentityOn(stringNode);
688             else {
689                 if (lastIndex < string.length())
690                     builder.append(string, lastIndex, string.length() - lastIndex);
691                 
692                 m_node->convertToLazyJSConstant(
693                     m_graph, LazyJSValue::newString(m_graph, builder.toString()));
694             }
695
696             m_node->origin = origin;
697             break;
698         }
699
700         default:
701             break;
702         }
703     }
704             
705     void convertToIdentityOverChild(unsigned childIndex)
706     {
707         m_insertionSet.insertCheck(m_nodeIndex, m_node);
708         m_node->children.removeEdge(childIndex ^ 1);
709         m_node->convertToIdentity();
710         m_changed = true;
711     }
712     
713     void convertToIdentityOverChild1()
714     {
715         convertToIdentityOverChild(0);
716     }
717     
718     void convertToIdentityOverChild2()
719     {
720         convertToIdentityOverChild(1);
721     }
722     
723     void handleCommutativity()
724     {
725         // If the right side is a constant then there is nothing left to do.
726         if (m_node->child2()->hasConstant())
727             return;
728         
729         // This case ensures that optimizations that look for x + const don't also have
730         // to look for const + x.
731         if (m_node->child1()->hasConstant()) {
732             std::swap(m_node->child1(), m_node->child2());
733             m_changed = true;
734             return;
735         }
736         
737         // This case ensures that CSE is commutativity-aware.
738         if (m_node->child1().node() > m_node->child2().node()) {
739             std::swap(m_node->child1(), m_node->child2());
740             m_changed = true;
741             return;
742         }
743     }
744
745     void executeInsertionSet()
746     {
747         m_nodeIndex += m_insertionSet.execute(m_block);
748     }
749     
750     InsertionSet m_insertionSet;
751     BasicBlock* m_block;
752     unsigned m_nodeIndex;
753     Node* m_node;
754     bool m_changed;
755 };
756     
757 bool performStrengthReduction(Graph& graph)
758 {
759     return runPhase<StrengthReductionPhase>(graph);
760 }
761
762 } } // namespace JSC::DFG
763
764 #endif // ENABLE(DFG_JIT)
765