ValueRep(DoubleRep(@v)) can not simply convert to @v
[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 "MathCommon.h"
40 #include "RegExpConstructor.h"
41 #include "StringPrototype.h"
42 #include <cstdlib>
43 #include <wtf/text/StringBuilder.h>
44
45 namespace JSC { namespace DFG {
46
47 class StrengthReductionPhase : public Phase {
48     static const bool verbose = false;
49     
50 public:
51     StrengthReductionPhase(Graph& graph)
52         : Phase(graph, "strength reduction")
53         , m_insertionSet(graph)
54     {
55     }
56     
57     bool run()
58     {
59         ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
60         
61         m_changed = false;
62         
63         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
64             m_block = m_graph.block(blockIndex);
65             if (!m_block)
66                 continue;
67             for (m_nodeIndex = 0; m_nodeIndex < m_block->size(); ++m_nodeIndex) {
68                 m_node = m_block->at(m_nodeIndex);
69                 handleNode();
70             }
71             m_insertionSet.execute(m_block);
72         }
73         
74         return m_changed;
75     }
76
77 private:
78     void handleNode()
79     {
80         switch (m_node->op()) {
81         case BitOr:
82             handleCommutativity();
83
84             if (m_node->child1().useKind() != UntypedUse && m_node->child2()->isInt32Constant() && !m_node->child2()->asInt32()) {
85                 convertToIdentityOverChild1();
86                 break;
87             }
88             break;
89             
90         case BitXor:
91         case BitAnd:
92             handleCommutativity();
93             break;
94             
95         case BitLShift:
96         case BitRShift:
97         case BitURShift:
98             if (m_node->child1().useKind() != UntypedUse && m_node->child2()->isInt32Constant() && !(m_node->child2()->asInt32() & 0x1f)) {
99                 convertToIdentityOverChild1();
100                 break;
101             }
102             break;
103             
104         case UInt32ToNumber:
105             if (m_node->child1()->op() == BitURShift
106                 && m_node->child1()->child2()->isInt32Constant()
107                 && (m_node->child1()->child2()->asInt32() & 0x1f)
108                 && m_node->arithMode() != Arith::DoOverflow) {
109                 m_node->convertToIdentity();
110                 m_changed = true;
111                 break;
112             }
113             break;
114             
115         case ArithAdd:
116             handleCommutativity();
117             
118             if (m_node->child2()->isInt32Constant() && !m_node->child2()->asInt32()) {
119                 convertToIdentityOverChild1();
120                 break;
121             }
122             break;
123             
124         case ArithMul: {
125             handleCommutativity();
126             Edge& child2 = m_node->child2();
127             if (child2->isNumberConstant() && child2->asNumber() == 2) {
128                 switch (m_node->binaryUseKind()) {
129                 case DoubleRepUse:
130                     // It is always valuable to get rid of a double multiplication by 2.
131                     // We won't have half-register dependencies issues on x86 and we won't have to load the constants.
132                     m_node->setOp(ArithAdd);
133                     child2.setNode(m_node->child1().node());
134                     m_changed = true;
135                     break;
136 #if USE(JSVALUE64)
137                 case Int52RepUse:
138 #endif
139                 case Int32Use:
140                     // For integers, we can only convert compatible modes.
141                     // ArithAdd does handle do negative zero check for example.
142                     if (m_node->arithMode() == Arith::CheckOverflow || m_node->arithMode() == Arith::Unchecked) {
143                         m_node->setOp(ArithAdd);
144                         child2.setNode(m_node->child1().node());
145                         m_changed = true;
146                     }
147                     break;
148                 default:
149                     break;
150                 }
151             }
152             break;
153         }
154         case ArithSub:
155             if (m_node->child2()->isInt32Constant()
156                 && m_node->isBinaryUseKind(Int32Use)) {
157                 int32_t value = m_node->child2()->asInt32();
158                 if (-value != value) {
159                     m_node->setOp(ArithAdd);
160                     m_node->child2().setNode(
161                         m_insertionSet.insertConstant(
162                             m_nodeIndex, m_node->origin, jsNumber(-value)));
163                     m_changed = true;
164                     break;
165                 }
166             }
167             break;
168
169         case ArithPow:
170             if (m_node->child2()->isNumberConstant()) {
171                 double yOperandValue = m_node->child2()->asNumber();
172                 if (yOperandValue == 1) {
173                     convertToIdentityOverChild1();
174                     m_changed = true;
175                 } else if (yOperandValue == 2) {
176                     m_node->setOp(ArithMul);
177                     m_node->child2() = m_node->child1();
178                     m_changed = true;
179                 }
180             }
181             break;
182
183         case ArithMod:
184             // On Integers
185             // In: ArithMod(ArithMod(x, const1), const2)
186             // Out: Identity(ArithMod(x, const1))
187             //     if const1 <= const2.
188             if (m_node->binaryUseKind() == Int32Use
189                 && m_node->child2()->isInt32Constant()
190                 && m_node->child1()->op() == ArithMod
191                 && m_node->child1()->binaryUseKind() == Int32Use
192                 && m_node->child1()->child2()->isInt32Constant()
193                 && std::abs(m_node->child1()->child2()->asInt32()) <= std::abs(m_node->child2()->asInt32())) {
194                     convertToIdentityOverChild1();
195             }
196             break;
197
198         case ArithDiv:
199             // Transform
200             //    ArithDiv(x, constant)
201             // Into
202             //    ArithMul(x, 1 / constant)
203             // if the operation has the same result.
204             if (m_node->isBinaryUseKind(DoubleRepUse)
205                 && m_node->child2()->isNumberConstant()) {
206
207                 if (std::optional<double> reciprocal = safeReciprocalForDivByConst(m_node->child2()->asNumber())) {
208                     Node* reciprocalNode = m_insertionSet.insertConstant(m_nodeIndex, m_node->origin, jsDoubleNumber(*reciprocal), DoubleConstant);
209                     m_node->setOp(ArithMul);
210                     m_node->child2() = Edge(reciprocalNode, DoubleRepUse);
211                     m_changed = true;
212                     break;
213                 }
214             }
215             break;
216
217         case ValueRep:
218         case Int52Rep: {
219             // This short-circuits circuitous conversions, like ValueRep(Int52Rep(value)).
220             
221             // The only speculation that we would do beyond validating that we have a type that
222             // can be represented a certain way is an Int32 check that would appear on Int52Rep
223             // nodes. For now, if we see this and the final type we want is an Int52, we use it
224             // as an excuse not to fold. The only thing we would need is a Int52RepInt32Use kind.
225             bool hadInt32Check = false;
226             if (m_node->op() == Int52Rep) {
227                 if (m_node->child1().useKind() != Int32Use)
228                     break;
229                 hadInt32Check = true;
230             }
231             for (Node* node = m_node->child1().node(); ; node = node->child1().node()) {
232                 if (canonicalResultRepresentation(node->result()) ==
233                     canonicalResultRepresentation(m_node->result())) {
234                     m_insertionSet.insertCheck(m_nodeIndex, m_node);
235                     if (hadInt32Check) {
236                         // FIXME: Consider adding Int52RepInt32Use or even DoubleRepInt32Use,
237                         // which would be super weird. The latter would only arise in some
238                         // seriously circuitous conversions.
239                         if (canonicalResultRepresentation(node->result()) != NodeResultJS)
240                             break;
241                         
242                         m_insertionSet.insertCheck(
243                             m_nodeIndex, m_node->origin, Edge(node, Int32Use));
244                     }
245                     m_node->child1() = node->defaultEdge();
246                     m_node->convertToIdentity();
247                     m_changed = true;
248                     break;
249                 }
250                 
251                 switch (node->op()) {
252                 case Int52Rep:
253                     if (node->child1().useKind() != Int32Use)
254                         break;
255                     hadInt32Check = true;
256                     continue;
257                     
258                 case ValueRep:
259                     continue;
260                     
261                 default:
262                     break;
263                 }
264                 break;
265             }
266             break;
267         }
268             
269         case Flush: {
270             ASSERT(m_graph.m_form != SSA);
271             
272             Node* setLocal = nullptr;
273             VirtualRegister local = m_node->local();
274             
275             for (unsigned i = m_nodeIndex; i--;) {
276                 Node* node = m_block->at(i);
277                 if (node->op() == SetLocal && node->local() == local) {
278                     setLocal = node;
279                     break;
280                 }
281                 if (accessesOverlap(m_graph, node, AbstractHeap(Stack, local)))
282                     break;
283             }
284             
285             if (!setLocal)
286                 break;
287             
288             // The Flush should become a PhantomLocal at this point. This means that we want the
289             // local's value during OSR, but we don't care if the value is stored to the stack. CPS
290             // rethreading can canonicalize PhantomLocals for us.
291             m_node->convertFlushToPhantomLocal();
292             m_graph.dethread();
293             m_changed = true;
294             break;
295         }
296
297         // FIXME: we should probably do this in constant folding but this currently relies on an OSR exit rule.
298         // https://bugs.webkit.org/show_bug.cgi?id=154832
299         case OverridesHasInstance: {
300             if (!m_node->child2().node()->isCellConstant())
301                 break;
302
303             if (m_node->child2().node()->asCell() != m_graph.globalObjectFor(m_node->origin.semantic)->functionProtoHasInstanceSymbolFunction()) {
304                 m_graph.convertToConstant(m_node, jsBoolean(true));
305                 m_changed = true;
306
307             } else if (!m_graph.hasExitSite(m_node->origin.semantic, BadTypeInfoFlags)) {
308                 // We optimistically assume that we will not see a function that has a custom instanceof operation as they should be rare.
309                 m_insertionSet.insertNode(m_nodeIndex, SpecNone, CheckTypeInfoFlags, m_node->origin, OpInfo(ImplementsDefaultHasInstance), Edge(m_node->child1().node(), CellUse));
310                 m_graph.convertToConstant(m_node, jsBoolean(false));
311                 m_changed = true;
312             }
313
314             break;
315         }
316
317         // FIXME: We have a lot of string constant-folding rules here. It would be great to
318         // move these to the abstract interpreter once AbstractValue can support LazyJSValue.
319         // https://bugs.webkit.org/show_bug.cgi?id=155204
320
321         case ValueAdd: {
322             if (m_node->child1()->isConstant()
323                 && m_node->child2()->isConstant()
324                 && (!!m_node->child1()->tryGetString(m_graph) || !!m_node->child2()->tryGetString(m_graph))) {
325                 auto tryGetConstantString = [&] (Node* node) -> String {
326                     String string = node->tryGetString(m_graph);
327                     if (!string.isEmpty())
328                         return string;
329                     JSValue value = node->constant()->value();
330                     if (!value)
331                         return String();
332                     if (value.isInt32())
333                         return String::number(value.asInt32());
334                     if (value.isNumber())
335                         return String::numberToStringECMAScript(value.asNumber());
336                     if (value.isBoolean())
337                         return value.asBoolean() ? ASCIILiteral("true") : ASCIILiteral("false");
338                     if (value.isNull())
339                         return ASCIILiteral("null");
340                     if (value.isUndefined())
341                         return ASCIILiteral("undefined");
342                     return String();
343                 };
344
345                 String leftString = tryGetConstantString(m_node->child1().node());
346                 if (!leftString)
347                     break;
348                 String rightString = tryGetConstantString(m_node->child2().node());
349                 if (!rightString)
350                     break;
351
352                 StringBuilder builder;
353                 builder.append(leftString);
354                 builder.append(rightString);
355                 m_node->convertToLazyJSConstant(
356                     m_graph, LazyJSValue::newString(m_graph, builder.toString()));
357                 m_changed = true;
358             }
359             break;
360         }
361
362         case MakeRope:
363         case StrCat: {
364             String leftString = m_node->child1()->tryGetString(m_graph);
365             if (!leftString)
366                 break;
367             String rightString = m_node->child2()->tryGetString(m_graph);
368             if (!rightString)
369                 break;
370             String extraString;
371             if (m_node->child3()) {
372                 extraString = m_node->child3()->tryGetString(m_graph);
373                 if (!extraString)
374                     break;
375             }
376
377             StringBuilder builder;
378             builder.append(leftString);
379             builder.append(rightString);
380             if (!!extraString)
381                 builder.append(extraString);
382
383             m_node->convertToLazyJSConstant(
384                 m_graph, LazyJSValue::newString(m_graph, builder.toString()));
385             m_changed = true;
386             break;
387         }
388
389         case ToString:
390         case CallStringConstructor: {
391             Edge& child1 = m_node->child1();
392             switch (child1.useKind()) {
393             case Int32Use:
394             case Int52RepUse:
395             case DoubleRepUse: {
396                 if (child1->hasConstant()) {
397                     JSValue value = child1->constant()->value();
398                     if (value) {
399                         String result;
400                         if (value.isInt32())
401                             result = String::number(value.asInt32());
402                         else if (value.isNumber())
403                             result = String::numberToStringECMAScript(value.asNumber());
404
405                         if (!result.isNull()) {
406                             m_node->convertToLazyJSConstant(m_graph, LazyJSValue::newString(m_graph, result));
407                             m_changed = true;
408                         }
409                     }
410                 }
411                 break;
412             }
413
414             default:
415                 break;
416             }
417             break;
418         }
419
420         case GetArrayLength: {
421             if (m_node->arrayMode().type() == Array::Generic
422                 || m_node->arrayMode().type() == Array::String) {
423                 String string = m_node->child1()->tryGetString(m_graph);
424                 if (!!string) {
425                     m_graph.convertToConstant(m_node, jsNumber(string.length()));
426                     m_changed = true;
427                     break;
428                 }
429             }
430             break;
431         }
432
433         case GetGlobalObject: {
434             if (JSObject* object = m_node->child1()->dynamicCastConstant<JSObject*>(vm())) {
435                 m_graph.convertToConstant(m_node, object->globalObject());
436                 m_changed = true;
437                 break;
438             }
439             break;
440         }
441
442         case RegExpExec:
443         case RegExpTest: {
444             JSGlobalObject* globalObject = m_node->child1()->dynamicCastConstant<JSGlobalObject*>(vm());
445             if (!globalObject) {
446                 if (verbose)
447                     dataLog("Giving up because no global object.\n");
448                 break;
449             }
450
451             if (globalObject->isHavingABadTime()) {
452                 if (verbose)
453                     dataLog("Giving up because bad time.\n");
454                 break;
455             }
456
457             Node* regExpObjectNode = m_node->child2().node();
458             RegExp* regExp;
459             if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>(vm()))
460                 regExp = regExpObject->regExp();
461             else if (regExpObjectNode->op() == NewRegexp)
462                 regExp = regExpObjectNode->castOperand<RegExp*>();
463             else {
464                 if (verbose)
465                     dataLog("Giving up because the regexp is unknown.\n");
466                 break;
467             }
468
469             Node* stringNode = m_node->child3().node();
470             
471             // NOTE: This mostly already protects us from having the compiler execute a regexp
472             // operation on a ginormous string by preventing us from getting our hands on ginormous
473             // strings in the first place.
474             String string = m_node->child3()->tryGetString(m_graph);
475             if (!string) {
476                 if (verbose)
477                     dataLog("Giving up because the string is unknown.\n");
478                 break;
479             }
480
481             FrozenValue* regExpFrozenValue = m_graph.freeze(regExp);
482
483             // Refuse to do things with regular expressions that have a ginormous number of
484             // subpatterns.
485             unsigned ginormousNumberOfSubPatterns = 1000;
486             if (regExp->numSubpatterns() > ginormousNumberOfSubPatterns) {
487                 if (verbose)
488                     dataLog("Giving up because of pattern limit.\n");
489                 break;
490             }
491             
492             unsigned lastIndex;
493             if (regExp->globalOrSticky()) {
494                 // This will only work if we can prove what the value of lastIndex is. To do this
495                 // safely, we need to execute the insertion set so that we see any previous strength
496                 // reductions. This is needed for soundness since otherwise the effectfulness of any
497                 // previous strength reductions would be invisible to us.
498                 executeInsertionSet();
499                 lastIndex = UINT_MAX;
500                 for (unsigned otherNodeIndex = m_nodeIndex; otherNodeIndex--;) {
501                     Node* otherNode = m_block->at(otherNodeIndex);
502                     if (otherNode == regExpObjectNode) {
503                         lastIndex = 0;
504                         break;
505                     }
506                     if (otherNode->op() == SetRegExpObjectLastIndex
507                         && otherNode->child1() == regExpObjectNode
508                         && otherNode->child2()->isInt32Constant()
509                         && otherNode->child2()->asInt32() >= 0) {
510                         lastIndex = static_cast<unsigned>(otherNode->child2()->asInt32());
511                         break;
512                     }
513                     if (writesOverlap(m_graph, otherNode, RegExpObject_lastIndex))
514                         break;
515                 }
516                 if (lastIndex == UINT_MAX) {
517                     if (verbose)
518                         dataLog("Giving up because the last index is not known.\n");
519                     break;
520                 }
521             } else
522                 lastIndex = 0;
523
524             m_graph.watchpoints().addLazily(globalObject->havingABadTimeWatchpoint());
525             
526             Structure* structure = globalObject->regExpMatchesArrayStructure();
527             if (structure->indexingType() != ArrayWithContiguous) {
528                 // This is further protection against a race with haveABadTime.
529                 if (verbose)
530                     dataLog("Giving up because the structure has the wrong indexing type.\n");
531                 break;
532             }
533             m_graph.registerStructure(structure);
534
535             RegExpConstructor* constructor = globalObject->regExpConstructor();
536             FrozenValue* constructorFrozenValue = m_graph.freeze(constructor);
537
538             MatchResult result;
539             Vector<int> ovector;
540             // We have to call the kind of match function that the main thread would have called.
541             // Otherwise, we might not have the desired Yarr code compiled, and the match will fail.
542             if (m_node->op() == RegExpExec) {
543                 int position;
544                 if (!regExp->matchConcurrently(vm(), string, lastIndex, position, ovector)) {
545                     if (verbose)
546                         dataLog("Giving up because match failed.\n");
547                     break;
548                 }
549                 result.start = position;
550                 result.end = ovector[1];
551             } else {
552                 if (!regExp->matchConcurrently(vm(), string, lastIndex, result)) {
553                     if (verbose)
554                         dataLog("Giving up because match failed.\n");
555                     break;
556                 }
557             }
558
559             // We've constant-folded the regexp. Now we're committed to replacing RegExpExec/Test.
560
561             m_changed = true;
562
563             NodeOrigin origin = m_node->origin;
564
565             m_insertionSet.insertNode(
566                 m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
567
568             if (m_node->op() == RegExpExec) {
569                 if (result) {
570                     RegisteredStructureSet* structureSet = m_graph.addStructureSet(structure);
571
572                     // Create an array modeling the JS array that we will try to allocate. This is
573                     // basically createRegExpMatchesArray but over C++ strings instead of JSStrings.
574                     Vector<String> resultArray;
575                     resultArray.append(string.substring(result.start, result.end - result.start));
576                     for (unsigned i = 1; i <= regExp->numSubpatterns(); ++i) {
577                         int start = ovector[2 * i];
578                         if (start >= 0)
579                             resultArray.append(string.substring(start, ovector[2 * i + 1] - start));
580                         else
581                             resultArray.append(String());
582                     }
583
584                     unsigned publicLength = resultArray.size();
585                     unsigned vectorLength =
586                         Butterfly::optimalContiguousVectorLength(structure, publicLength);
587
588                     UniquedStringImpl* indexUID = vm().propertyNames->index.impl();
589                     UniquedStringImpl* inputUID = vm().propertyNames->input.impl();
590                     unsigned indexIndex = m_graph.identifiers().ensure(indexUID);
591                     unsigned inputIndex = m_graph.identifiers().ensure(inputUID);
592
593                     unsigned firstChild = m_graph.m_varArgChildren.size();
594                     m_graph.m_varArgChildren.append(
595                         m_insertionSet.insertConstantForUse(
596                             m_nodeIndex, origin, structure, KnownCellUse));
597                     ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
598             
599                     m_graph.m_varArgChildren.append(
600                         m_insertionSet.insertConstantForUse(
601                             m_nodeIndex, origin, jsNumber(publicLength), KnownInt32Use));
602                     data->m_properties.append(PublicLengthPLoc);
603             
604                     m_graph.m_varArgChildren.append(
605                         m_insertionSet.insertConstantForUse(
606                             m_nodeIndex, origin, jsNumber(vectorLength), KnownInt32Use));
607                     data->m_properties.append(VectorLengthPLoc);
608
609                     m_graph.m_varArgChildren.append(
610                         m_insertionSet.insertConstantForUse(
611                             m_nodeIndex, origin, jsNumber(result.start), UntypedUse));
612                     data->m_properties.append(
613                         PromotedLocationDescriptor(NamedPropertyPLoc, indexIndex));
614
615                     m_graph.m_varArgChildren.append(Edge(stringNode, UntypedUse));
616                     data->m_properties.append(
617                         PromotedLocationDescriptor(NamedPropertyPLoc, inputIndex));
618
619                     auto materializeString = [&] (const String& string) -> Node* {
620                         if (string.isNull())
621                             return nullptr;
622                         if (string.isEmpty()) {
623                             return m_insertionSet.insertConstant(
624                                 m_nodeIndex, origin, vm().smallStrings.emptyString());
625                         }
626                         LazyJSValue value = LazyJSValue::newString(m_graph, string);
627                         return m_insertionSet.insertNode(
628                             m_nodeIndex, SpecNone, LazyJSConstant, origin,
629                             OpInfo(m_graph.m_lazyJSValues.add(value)));
630                     };
631
632                     for (unsigned i = 0; i < resultArray.size(); ++i) {
633                         if (Node* node = materializeString(resultArray[i])) {
634                             m_graph.m_varArgChildren.append(Edge(node, UntypedUse));
635                             data->m_properties.append(
636                                 PromotedLocationDescriptor(IndexedPropertyPLoc, i));
637                         }
638                     }
639             
640                     Node* resultNode = m_insertionSet.insertNode(
641                         m_nodeIndex, SpecArray, Node::VarArg, MaterializeNewObject, origin,
642                         OpInfo(structureSet), OpInfo(data), firstChild,
643                         m_graph.m_varArgChildren.size() - firstChild);
644                 
645                     m_node->convertToIdentityOn(resultNode);
646                 } else
647                     m_graph.convertToConstant(m_node, jsNull());
648             } else
649                 m_graph.convertToConstant(m_node, jsBoolean(!!result));
650
651             // Whether it's Exec or Test, we need to tell the constructor and RegExpObject what's up.
652             // Because SetRegExpObjectLastIndex may exit and it clobbers exit state, we do that
653             // first.
654             
655             if (regExp->globalOrSticky()) {
656                 m_insertionSet.insertNode(
657                     m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
658                     Edge(regExpObjectNode, RegExpObjectUse),
659                     m_insertionSet.insertConstantForUse(
660                         m_nodeIndex, origin, jsNumber(result ? result.end : 0), UntypedUse));
661                 
662                 origin = origin.withInvalidExit();
663             }
664
665             if (result) {
666                 unsigned firstChild = m_graph.m_varArgChildren.size();
667                 m_graph.m_varArgChildren.append(
668                     m_insertionSet.insertConstantForUse(
669                         m_nodeIndex, origin, constructorFrozenValue, KnownCellUse));
670                 m_graph.m_varArgChildren.append(
671                     m_insertionSet.insertConstantForUse(
672                         m_nodeIndex, origin, regExpFrozenValue, KnownCellUse));
673                 m_graph.m_varArgChildren.append(Edge(stringNode, KnownCellUse));
674                 m_graph.m_varArgChildren.append(
675                     m_insertionSet.insertConstantForUse(
676                         m_nodeIndex, origin, jsNumber(result.start), KnownInt32Use));
677                 m_graph.m_varArgChildren.append(
678                     m_insertionSet.insertConstantForUse(
679                         m_nodeIndex, origin, jsNumber(result.end), KnownInt32Use));
680                 m_insertionSet.insertNode(
681                     m_nodeIndex, SpecNone, Node::VarArg, RecordRegExpCachedResult, origin,
682                     OpInfo(), OpInfo(), firstChild, m_graph.m_varArgChildren.size() - firstChild);
683
684                 origin = origin.withInvalidExit();
685             }
686             
687             m_node->origin = origin;
688             break;
689         }
690
691         case StringReplace:
692         case StringReplaceRegExp: {
693             Node* stringNode = m_node->child1().node();
694             String string = stringNode->tryGetString(m_graph);
695             if (!string)
696                 break;
697             
698             Node* regExpObjectNode = m_node->child2().node();
699             RegExp* regExp;
700             if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>(vm()))
701                 regExp = regExpObject->regExp();
702             else if (regExpObjectNode->op() == NewRegexp)
703                 regExp = regExpObjectNode->castOperand<RegExp*>();
704             else {
705                 if (verbose)
706                     dataLog("Giving up because the regexp is unknown.\n");
707                 break;
708             }
709
710             String replace = m_node->child3()->tryGetString(m_graph);
711             if (!replace)
712                 break;
713
714             StringBuilder builder;
715
716             unsigned lastIndex = 0;
717             unsigned startPosition = 0;
718             bool ok = true;
719             do {
720                 MatchResult result;
721                 Vector<int> ovector;
722                 // Model which version of match() is called by the main thread.
723                 if (replace.isEmpty() && regExp->global()) {
724                     if (!regExp->matchConcurrently(vm(), string, startPosition, result)) {
725                         ok = false;
726                         break;
727                     }
728                 } else {
729                     int position;
730                     if (!regExp->matchConcurrently(vm(), string, startPosition, position, ovector)) {
731                         ok = false;
732                         break;
733                     }
734                     
735                     result.start = position;
736                     result.end = ovector[1];
737                 }
738                 
739                 if (!result)
740                     break;
741
742                 unsigned replLen = replace.length();
743                 if (lastIndex < result.start || replLen) {
744                     builder.append(string, lastIndex, result.start - lastIndex);
745                     if (replLen)
746                         builder.append(substituteBackreferences(replace, string, ovector.data(), regExp));
747                 }
748
749                 lastIndex = result.end;
750                 startPosition = lastIndex;
751
752                 // special case of empty match
753                 if (result.empty()) {
754                     startPosition++;
755                     if (startPosition > string.length())
756                         break;
757                 }
758             } while (regExp->global());
759             if (!ok)
760                 break;
761
762             // We are committed at this point.
763             m_changed = true;
764
765             NodeOrigin origin = m_node->origin;
766
767             if (regExp->global()) {
768                 m_insertionSet.insertNode(
769                     m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
770                     Edge(regExpObjectNode, RegExpObjectUse),
771                     m_insertionSet.insertConstantForUse(
772                         m_nodeIndex, origin, jsNumber(0), UntypedUse));
773                 
774                 origin = origin.withInvalidExit();
775             }
776
777             if (!lastIndex && builder.isEmpty())
778                 m_node->convertToIdentityOn(stringNode);
779             else {
780                 if (lastIndex < string.length())
781                     builder.append(string, lastIndex, string.length() - lastIndex);
782                 
783                 m_node->convertToLazyJSConstant(
784                     m_graph, LazyJSValue::newString(m_graph, builder.toString()));
785             }
786
787             m_node->origin = origin;
788             break;
789         }
790             
791         case Call:
792         case Construct:
793         case TailCallInlinedCaller:
794         case TailCall: {
795             ExecutableBase* executable = nullptr;
796             Edge callee = m_graph.varArgChild(m_node, 0);
797             if (JSFunction* function = callee->dynamicCastConstant<JSFunction*>(vm()))
798                 executable = function->executable();
799             else if (callee->isFunctionAllocation())
800                 executable = callee->castOperand<FunctionExecutable*>();
801             
802             if (!executable)
803                 break;
804             
805             if (FunctionExecutable* functionExecutable = jsDynamicCast<FunctionExecutable*>(vm(), executable)) {
806                 // We need to update m_parameterSlots before we get to the backend, but we don't
807                 // want to do too much of this.
808                 unsigned numAllocatedArgs =
809                     static_cast<unsigned>(functionExecutable->parameterCount()) + 1;
810                 
811                 if (numAllocatedArgs <= Options::maximumDirectCallStackSize()) {
812                     m_graph.m_parameterSlots = std::max(
813                         m_graph.m_parameterSlots,
814                         Graph::parameterSlotsForArgCount(numAllocatedArgs));
815                 }
816             }
817             
818             m_node->convertToDirectCall(m_graph.freeze(executable));
819             m_changed = true;
820             break;
821         }
822
823         default:
824             break;
825         }
826     }
827             
828     void convertToIdentityOverChild(unsigned childIndex)
829     {
830         m_insertionSet.insertCheck(m_nodeIndex, m_node);
831         m_node->children.removeEdge(childIndex ^ 1);
832         m_node->convertToIdentity();
833         m_changed = true;
834     }
835     
836     void convertToIdentityOverChild1()
837     {
838         convertToIdentityOverChild(0);
839     }
840     
841     void convertToIdentityOverChild2()
842     {
843         convertToIdentityOverChild(1);
844     }
845     
846     void handleCommutativity()
847     {
848         // It's definitely not sound to swap the lhs and rhs when we may be performing effectful
849         // calls on the lhs/rhs for valueOf.
850         if (m_node->child1().useKind() == UntypedUse || m_node->child2().useKind() == UntypedUse)
851             return;
852
853         // If the right side is a constant then there is nothing left to do.
854         if (m_node->child2()->hasConstant())
855             return;
856         
857         // This case ensures that optimizations that look for x + const don't also have
858         // to look for const + x.
859         if (m_node->child1()->hasConstant() && !m_node->child1()->asJSValue().isCell()) {
860             std::swap(m_node->child1(), m_node->child2());
861             m_changed = true;
862             return;
863         }
864         
865         // This case ensures that CSE is commutativity-aware.
866         if (m_node->child1().node() > m_node->child2().node()) {
867             std::swap(m_node->child1(), m_node->child2());
868             m_changed = true;
869             return;
870         }
871     }
872
873     void executeInsertionSet()
874     {
875         m_nodeIndex += m_insertionSet.execute(m_block);
876     }
877     
878     InsertionSet m_insertionSet;
879     BasicBlock* m_block;
880     unsigned m_nodeIndex;
881     Node* m_node;
882     bool m_changed;
883 };
884     
885 bool performStrengthReduction(Graph& graph)
886 {
887     return runPhase<StrengthReductionPhase>(graph);
888 }
889
890 } } // namespace JSC::DFG
891
892 #endif // ENABLE(DFG_JIT)
893