10406fa415957495f248a992e59e64d85f78b281
[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 (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         case DoubleRep: {
220             // This short-circuits circuitous conversions, like ValueRep(DoubleRep(value)) or
221             // even more complicated things. Like, it can handle a beast like
222             // ValueRep(DoubleRep(Int52Rep(value))).
223             
224             // The only speculation that we would do beyond validating that we have a type that
225             // can be represented a certain way is an Int32 check that would appear on Int52Rep
226             // nodes. For now, if we see this and the final type we want is an Int52, we use it
227             // as an excuse not to fold. The only thing we would need is a Int52RepInt32Use kind.
228             bool hadInt32Check = false;
229             if (m_node->op() == Int52Rep) {
230                 if (m_node->child1().useKind() != Int32Use)
231                     break;
232                 hadInt32Check = true;
233             }
234             for (Node* node = m_node->child1().node(); ; node = node->child1().node()) {
235                 if (canonicalResultRepresentation(node->result()) ==
236                     canonicalResultRepresentation(m_node->result())) {
237                     m_insertionSet.insertCheck(m_nodeIndex, m_node);
238                     if (hadInt32Check) {
239                         // FIXME: Consider adding Int52RepInt32Use or even DoubleRepInt32Use,
240                         // which would be super weird. The latter would only arise in some
241                         // seriously circuitous conversions.
242                         if (canonicalResultRepresentation(node->result()) != NodeResultJS)
243                             break;
244                         
245                         m_insertionSet.insertCheck(
246                             m_nodeIndex, m_node->origin, Edge(node, Int32Use));
247                     }
248                     m_node->child1() = node->defaultEdge();
249                     m_node->convertToIdentity();
250                     m_changed = true;
251                     break;
252                 }
253                 
254                 switch (node->op()) {
255                 case Int52Rep:
256                     if (node->child1().useKind() != Int32Use)
257                         break;
258                     hadInt32Check = true;
259                     continue;
260                     
261                 case DoubleRep:
262                 case ValueRep:
263                     continue;
264                     
265                 default:
266                     break;
267                 }
268                 break;
269             }
270             break;
271         }
272             
273         case Flush: {
274             ASSERT(m_graph.m_form != SSA);
275             
276             Node* setLocal = nullptr;
277             VirtualRegister local = m_node->local();
278             
279             for (unsigned i = m_nodeIndex; i--;) {
280                 Node* node = m_block->at(i);
281                 if (node->op() == SetLocal && node->local() == local) {
282                     setLocal = node;
283                     break;
284                 }
285                 if (accessesOverlap(m_graph, node, AbstractHeap(Stack, local)))
286                     break;
287             }
288             
289             if (!setLocal)
290                 break;
291             
292             // The Flush should become a PhantomLocal at this point. This means that we want the
293             // local's value during OSR, but we don't care if the value is stored to the stack. CPS
294             // rethreading can canonicalize PhantomLocals for us.
295             m_node->convertFlushToPhantomLocal();
296             m_graph.dethread();
297             m_changed = true;
298             break;
299         }
300
301         // FIXME: we should probably do this in constant folding but this currently relies on an OSR exit rule.
302         // https://bugs.webkit.org/show_bug.cgi?id=154832
303         case OverridesHasInstance: {
304             if (!m_node->child2().node()->isCellConstant())
305                 break;
306
307             if (m_node->child2().node()->asCell() != m_graph.globalObjectFor(m_node->origin.semantic)->functionProtoHasInstanceSymbolFunction()) {
308                 m_graph.convertToConstant(m_node, jsBoolean(true));
309                 m_changed = true;
310
311             } else if (!m_graph.hasExitSite(m_node->origin.semantic, BadTypeInfoFlags)) {
312                 // We optimistically assume that we will not see a function that has a custom instanceof operation as they should be rare.
313                 m_insertionSet.insertNode(m_nodeIndex, SpecNone, CheckTypeInfoFlags, m_node->origin, OpInfo(ImplementsDefaultHasInstance), Edge(m_node->child1().node(), CellUse));
314                 m_graph.convertToConstant(m_node, jsBoolean(false));
315                 m_changed = true;
316             }
317
318             break;
319         }
320
321         // FIXME: We have a lot of string constant-folding rules here. It would be great to
322         // move these to the abstract interpreter once AbstractValue can support LazyJSValue.
323         // https://bugs.webkit.org/show_bug.cgi?id=155204
324
325         case ValueAdd: {
326             if (m_node->child1()->isConstant()
327                 && m_node->child2()->isConstant()
328                 && (!!m_node->child1()->tryGetString(m_graph) || !!m_node->child2()->tryGetString(m_graph))) {
329                 auto tryGetConstantString = [&] (Node* node) -> String {
330                     String string = node->tryGetString(m_graph);
331                     if (!string.isEmpty())
332                         return string;
333                     JSValue value = node->constant()->value();
334                     if (!value)
335                         return String();
336                     if (value.isInt32())
337                         return String::number(value.asInt32());
338                     if (value.isNumber())
339                         return String::numberToStringECMAScript(value.asNumber());
340                     if (value.isBoolean())
341                         return value.asBoolean() ? ASCIILiteral("true") : ASCIILiteral("false");
342                     if (value.isNull())
343                         return ASCIILiteral("null");
344                     if (value.isUndefined())
345                         return ASCIILiteral("undefined");
346                     return String();
347                 };
348
349                 String leftString = tryGetConstantString(m_node->child1().node());
350                 if (!leftString)
351                     break;
352                 String rightString = tryGetConstantString(m_node->child2().node());
353                 if (!rightString)
354                     break;
355
356                 StringBuilder builder;
357                 builder.append(leftString);
358                 builder.append(rightString);
359                 m_node->convertToLazyJSConstant(
360                     m_graph, LazyJSValue::newString(m_graph, builder.toString()));
361                 m_changed = true;
362             }
363             break;
364         }
365
366         case MakeRope:
367         case StrCat: {
368             String leftString = m_node->child1()->tryGetString(m_graph);
369             if (!leftString)
370                 break;
371             String rightString = m_node->child2()->tryGetString(m_graph);
372             if (!rightString)
373                 break;
374             String extraString;
375             if (m_node->child3()) {
376                 extraString = m_node->child3()->tryGetString(m_graph);
377                 if (!extraString)
378                     break;
379             }
380
381             StringBuilder builder;
382             builder.append(leftString);
383             builder.append(rightString);
384             if (!!extraString)
385                 builder.append(extraString);
386
387             m_node->convertToLazyJSConstant(
388                 m_graph, LazyJSValue::newString(m_graph, builder.toString()));
389             m_changed = true;
390             break;
391         }
392
393         case GetArrayLength: {
394             if (m_node->arrayMode().type() == Array::Generic
395                 || m_node->arrayMode().type() == Array::String) {
396                 String string = m_node->child1()->tryGetString(m_graph);
397                 if (!!string) {
398                     m_graph.convertToConstant(m_node, jsNumber(string.length()));
399                     m_changed = true;
400                     break;
401                 }
402             }
403             break;
404         }
405
406         case GetGlobalObject: {
407             if (JSObject* object = m_node->child1()->dynamicCastConstant<JSObject*>()) {
408                 m_graph.convertToConstant(m_node, object->globalObject());
409                 m_changed = true;
410                 break;
411             }
412             break;
413         }
414
415         case RegExpExec:
416         case RegExpTest: {
417             JSGlobalObject* globalObject = m_node->child1()->dynamicCastConstant<JSGlobalObject*>();
418             if (!globalObject) {
419                 if (verbose)
420                     dataLog("Giving up because no global object.\n");
421                 break;
422             }
423
424             if (globalObject->isHavingABadTime()) {
425                 if (verbose)
426                     dataLog("Giving up because bad time.\n");
427                 break;
428             }
429
430             Node* regExpObjectNode = m_node->child2().node();
431             RegExp* regExp;
432             if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>())
433                 regExp = regExpObject->regExp();
434             else if (regExpObjectNode->op() == NewRegexp)
435                 regExp = regExpObjectNode->castOperand<RegExp*>();
436             else {
437                 if (verbose)
438                     dataLog("Giving up because the regexp is unknown.\n");
439                 break;
440             }
441
442             Node* stringNode = m_node->child3().node();
443             
444             // NOTE: This mostly already protects us from having the compiler execute a regexp
445             // operation on a ginormous string by preventing us from getting our hands on ginormous
446             // strings in the first place.
447             String string = m_node->child3()->tryGetString(m_graph);
448             if (!string) {
449                 if (verbose)
450                     dataLog("Giving up because the string is unknown.\n");
451                 break;
452             }
453
454             FrozenValue* regExpFrozenValue = m_graph.freeze(regExp);
455
456             // Refuse to do things with regular expressions that have a ginormous number of
457             // subpatterns.
458             unsigned ginormousNumberOfSubPatterns = 1000;
459             if (regExp->numSubpatterns() > ginormousNumberOfSubPatterns) {
460                 if (verbose)
461                     dataLog("Giving up because of pattern limit.\n");
462                 break;
463             }
464             
465             unsigned lastIndex;
466             if (regExp->globalOrSticky()) {
467                 // This will only work if we can prove what the value of lastIndex is. To do this
468                 // safely, we need to execute the insertion set so that we see any previous strength
469                 // reductions. This is needed for soundness since otherwise the effectfulness of any
470                 // previous strength reductions would be invisible to us.
471                 executeInsertionSet();
472                 lastIndex = UINT_MAX;
473                 for (unsigned otherNodeIndex = m_nodeIndex; otherNodeIndex--;) {
474                     Node* otherNode = m_block->at(otherNodeIndex);
475                     if (otherNode == regExpObjectNode) {
476                         lastIndex = 0;
477                         break;
478                     }
479                     if (otherNode->op() == SetRegExpObjectLastIndex
480                         && otherNode->child1() == regExpObjectNode
481                         && otherNode->child2()->isInt32Constant()
482                         && otherNode->child2()->asInt32() >= 0) {
483                         lastIndex = static_cast<unsigned>(otherNode->child2()->asInt32());
484                         break;
485                     }
486                     if (writesOverlap(m_graph, otherNode, RegExpObject_lastIndex))
487                         break;
488                 }
489                 if (lastIndex == UINT_MAX) {
490                     if (verbose)
491                         dataLog("Giving up because the last index is not known.\n");
492                     break;
493                 }
494             } else
495                 lastIndex = 0;
496
497             m_graph.watchpoints().addLazily(globalObject->havingABadTimeWatchpoint());
498             
499             Structure* structure = globalObject->regExpMatchesArrayStructure();
500             if (structure->indexingType() != ArrayWithContiguous) {
501                 // This is further protection against a race with haveABadTime.
502                 if (verbose)
503                     dataLog("Giving up because the structure has the wrong indexing type.\n");
504                 break;
505             }
506             m_graph.registerStructure(structure);
507
508             RegExpConstructor* constructor = globalObject->regExpConstructor();
509             FrozenValue* constructorFrozenValue = m_graph.freeze(constructor);
510
511             MatchResult result;
512             Vector<int> ovector;
513             // We have to call the kind of match function that the main thread would have called.
514             // Otherwise, we might not have the desired Yarr code compiled, and the match will fail.
515             if (m_node->op() == RegExpExec) {
516                 int position;
517                 if (!regExp->matchConcurrently(vm(), string, lastIndex, position, ovector)) {
518                     if (verbose)
519                         dataLog("Giving up because match failed.\n");
520                     break;
521                 }
522                 result.start = position;
523                 result.end = ovector[1];
524             } else {
525                 if (!regExp->matchConcurrently(vm(), string, lastIndex, result)) {
526                     if (verbose)
527                         dataLog("Giving up because match failed.\n");
528                     break;
529                 }
530             }
531
532             // We've constant-folded the regexp. Now we're committed to replacing RegExpExec/Test.
533
534             m_changed = true;
535
536             NodeOrigin origin = m_node->origin;
537
538             m_insertionSet.insertNode(
539                 m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
540
541             if (m_node->op() == RegExpExec) {
542                 if (result) {
543                     StructureSet* structureSet = m_graph.addStructureSet(structure);
544
545                     // Create an array modeling the JS array that we will try to allocate. This is
546                     // basically createRegExpMatchesArray but over C++ strings instead of JSStrings.
547                     Vector<String> resultArray;
548                     resultArray.append(string.substring(result.start, result.end - result.start));
549                     for (unsigned i = 1; i <= regExp->numSubpatterns(); ++i) {
550                         int start = ovector[2 * i];
551                         if (start >= 0)
552                             resultArray.append(string.substring(start, ovector[2 * i + 1] - start));
553                         else
554                             resultArray.append(String());
555                     }
556
557                     unsigned publicLength = resultArray.size();
558                     unsigned vectorLength =
559                         Butterfly::optimalContiguousVectorLength(structure, publicLength);
560
561                     UniquedStringImpl* indexUID = vm().propertyNames->index.impl();
562                     UniquedStringImpl* inputUID = vm().propertyNames->input.impl();
563                     unsigned indexIndex = m_graph.identifiers().ensure(indexUID);
564                     unsigned inputIndex = m_graph.identifiers().ensure(inputUID);
565
566                     unsigned firstChild = m_graph.m_varArgChildren.size();
567                     m_graph.m_varArgChildren.append(
568                         m_insertionSet.insertConstantForUse(
569                             m_nodeIndex, origin, structure, KnownCellUse));
570                     ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
571             
572                     m_graph.m_varArgChildren.append(
573                         m_insertionSet.insertConstantForUse(
574                             m_nodeIndex, origin, jsNumber(publicLength), KnownInt32Use));
575                     data->m_properties.append(PublicLengthPLoc);
576             
577                     m_graph.m_varArgChildren.append(
578                         m_insertionSet.insertConstantForUse(
579                             m_nodeIndex, origin, jsNumber(vectorLength), KnownInt32Use));
580                     data->m_properties.append(VectorLengthPLoc);
581
582                     m_graph.m_varArgChildren.append(
583                         m_insertionSet.insertConstantForUse(
584                             m_nodeIndex, origin, jsNumber(result.start), UntypedUse));
585                     data->m_properties.append(
586                         PromotedLocationDescriptor(NamedPropertyPLoc, indexIndex));
587
588                     m_graph.m_varArgChildren.append(Edge(stringNode, UntypedUse));
589                     data->m_properties.append(
590                         PromotedLocationDescriptor(NamedPropertyPLoc, inputIndex));
591
592                     auto materializeString = [&] (const String& string) -> Node* {
593                         if (string.isNull())
594                             return nullptr;
595                         if (string.isEmpty()) {
596                             return m_insertionSet.insertConstant(
597                                 m_nodeIndex, origin, vm().smallStrings.emptyString());
598                         }
599                         LazyJSValue value = LazyJSValue::newString(m_graph, string);
600                         return m_insertionSet.insertNode(
601                             m_nodeIndex, SpecNone, LazyJSConstant, origin,
602                             OpInfo(m_graph.m_lazyJSValues.add(value)));
603                     };
604
605                     for (unsigned i = 0; i < resultArray.size(); ++i) {
606                         if (Node* node = materializeString(resultArray[i])) {
607                             m_graph.m_varArgChildren.append(Edge(node, UntypedUse));
608                             data->m_properties.append(
609                                 PromotedLocationDescriptor(IndexedPropertyPLoc, i));
610                         }
611                     }
612             
613                     Node* resultNode = m_insertionSet.insertNode(
614                         m_nodeIndex, SpecArray, Node::VarArg, MaterializeNewObject, origin,
615                         OpInfo(structureSet), OpInfo(data), firstChild,
616                         m_graph.m_varArgChildren.size() - firstChild);
617                 
618                     m_node->convertToIdentityOn(resultNode);
619                 } else
620                     m_graph.convertToConstant(m_node, jsNull());
621             } else
622                 m_graph.convertToConstant(m_node, jsBoolean(!!result));
623
624             // Whether it's Exec or Test, we need to tell the constructor and RegExpObject what's up.
625             // Because SetRegExpObjectLastIndex may exit and it clobbers exit state, we do that
626             // first.
627             
628             if (regExp->globalOrSticky()) {
629                 m_insertionSet.insertNode(
630                     m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
631                     Edge(regExpObjectNode, RegExpObjectUse),
632                     m_insertionSet.insertConstantForUse(
633                         m_nodeIndex, origin, jsNumber(result ? result.end : 0), UntypedUse));
634                 
635                 origin = origin.withInvalidExit();
636             }
637
638             if (result) {
639                 unsigned firstChild = m_graph.m_varArgChildren.size();
640                 m_graph.m_varArgChildren.append(
641                     m_insertionSet.insertConstantForUse(
642                         m_nodeIndex, origin, constructorFrozenValue, KnownCellUse));
643                 m_graph.m_varArgChildren.append(
644                     m_insertionSet.insertConstantForUse(
645                         m_nodeIndex, origin, regExpFrozenValue, KnownCellUse));
646                 m_graph.m_varArgChildren.append(Edge(stringNode, KnownCellUse));
647                 m_graph.m_varArgChildren.append(
648                     m_insertionSet.insertConstantForUse(
649                         m_nodeIndex, origin, jsNumber(result.start), KnownInt32Use));
650                 m_graph.m_varArgChildren.append(
651                     m_insertionSet.insertConstantForUse(
652                         m_nodeIndex, origin, jsNumber(result.end), KnownInt32Use));
653                 m_insertionSet.insertNode(
654                     m_nodeIndex, SpecNone, Node::VarArg, RecordRegExpCachedResult, origin,
655                     OpInfo(), OpInfo(), firstChild, m_graph.m_varArgChildren.size() - firstChild);
656
657                 origin = origin.withInvalidExit();
658             }
659             
660             m_node->origin = origin;
661             break;
662         }
663
664         case StringReplace:
665         case StringReplaceRegExp: {
666             Node* stringNode = m_node->child1().node();
667             String string = stringNode->tryGetString(m_graph);
668             if (!string)
669                 break;
670             
671             Node* regExpObjectNode = m_node->child2().node();
672             RegExp* regExp;
673             if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>())
674                 regExp = regExpObject->regExp();
675             else if (regExpObjectNode->op() == NewRegexp)
676                 regExp = regExpObjectNode->castOperand<RegExp*>();
677             else {
678                 if (verbose)
679                     dataLog("Giving up because the regexp is unknown.\n");
680                 break;
681             }
682
683             String replace = m_node->child3()->tryGetString(m_graph);
684             if (!replace)
685                 break;
686
687             StringBuilder builder;
688
689             unsigned lastIndex = 0;
690             unsigned startPosition = 0;
691             bool ok = true;
692             do {
693                 MatchResult result;
694                 Vector<int> ovector;
695                 // Model which version of match() is called by the main thread.
696                 if (replace.isEmpty() && regExp->global()) {
697                     if (!regExp->matchConcurrently(vm(), string, startPosition, result)) {
698                         ok = false;
699                         break;
700                     }
701                 } else {
702                     int position;
703                     if (!regExp->matchConcurrently(vm(), string, startPosition, position, ovector)) {
704                         ok = false;
705                         break;
706                     }
707                     
708                     result.start = position;
709                     result.end = ovector[1];
710                 }
711                 
712                 if (!result)
713                     break;
714
715                 unsigned replLen = replace.length();
716                 if (lastIndex < result.start || replLen) {
717                     builder.append(string, lastIndex, result.start - lastIndex);
718                     if (replLen)
719                         builder.append(substituteBackreferences(replace, string, ovector.data(), regExp));
720                 }
721
722                 lastIndex = result.end;
723                 startPosition = lastIndex;
724
725                 // special case of empty match
726                 if (result.empty()) {
727                     startPosition++;
728                     if (startPosition > string.length())
729                         break;
730                 }
731             } while (regExp->global());
732             if (!ok)
733                 break;
734
735             // We are committed at this point.
736             m_changed = true;
737
738             NodeOrigin origin = m_node->origin;
739
740             if (regExp->global()) {
741                 m_insertionSet.insertNode(
742                     m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
743                     Edge(regExpObjectNode, RegExpObjectUse),
744                     m_insertionSet.insertConstantForUse(
745                         m_nodeIndex, origin, jsNumber(0), UntypedUse));
746                 
747                 origin = origin.withInvalidExit();
748             }
749
750             if (!lastIndex && builder.isEmpty())
751                 m_node->convertToIdentityOn(stringNode);
752             else {
753                 if (lastIndex < string.length())
754                     builder.append(string, lastIndex, string.length() - lastIndex);
755                 
756                 m_node->convertToLazyJSConstant(
757                     m_graph, LazyJSValue::newString(m_graph, builder.toString()));
758             }
759
760             m_node->origin = origin;
761             break;
762         }
763             
764         case Call:
765         case Construct:
766         case TailCallInlinedCaller:
767         case TailCall: {
768             ExecutableBase* executable = nullptr;
769             Edge callee = m_graph.varArgChild(m_node, 0);
770             if (JSFunction* function = callee->dynamicCastConstant<JSFunction*>())
771                 executable = function->executable();
772             else if (callee->isFunctionAllocation())
773                 executable = callee->castOperand<FunctionExecutable*>();
774             
775             if (!executable)
776                 break;
777             
778             if (FunctionExecutable* functionExecutable = jsDynamicCast<FunctionExecutable*>(executable)) {
779                 // We need to update m_parameterSlots before we get to the backend, but we don't
780                 // want to do too much of this.
781                 unsigned numAllocatedArgs =
782                     static_cast<unsigned>(functionExecutable->parameterCount()) + 1;
783                 
784                 if (numAllocatedArgs <= Options::maximumDirectCallStackSize()) {
785                     m_graph.m_parameterSlots = std::max(
786                         m_graph.m_parameterSlots,
787                         Graph::parameterSlotsForArgCount(numAllocatedArgs));
788                 }
789             }
790             
791             m_node->convertToDirectCall(m_graph.freeze(executable));
792             m_changed = true;
793             break;
794         }
795
796         default:
797             break;
798         }
799     }
800             
801     void convertToIdentityOverChild(unsigned childIndex)
802     {
803         m_insertionSet.insertCheck(m_nodeIndex, m_node);
804         m_node->children.removeEdge(childIndex ^ 1);
805         m_node->convertToIdentity();
806         m_changed = true;
807     }
808     
809     void convertToIdentityOverChild1()
810     {
811         convertToIdentityOverChild(0);
812     }
813     
814     void convertToIdentityOverChild2()
815     {
816         convertToIdentityOverChild(1);
817     }
818     
819     void handleCommutativity()
820     {
821         // It's definitely not sound to swap the lhs and rhs when we may be performing effectful
822         // calls on the lhs/rhs for valueOf.
823         if (m_node->child1().useKind() == UntypedUse || m_node->child2().useKind() == UntypedUse)
824             return;
825
826         // If the right side is a constant then there is nothing left to do.
827         if (m_node->child2()->hasConstant())
828             return;
829         
830         // This case ensures that optimizations that look for x + const don't also have
831         // to look for const + x.
832         if (m_node->child1()->hasConstant() && !m_node->child1()->asJSValue().isCell()) {
833             std::swap(m_node->child1(), m_node->child2());
834             m_changed = true;
835             return;
836         }
837         
838         // This case ensures that CSE is commutativity-aware.
839         if (m_node->child1().node() > m_node->child2().node()) {
840             std::swap(m_node->child1(), m_node->child2());
841             m_changed = true;
842             return;
843         }
844     }
845
846     void executeInsertionSet()
847     {
848         m_nodeIndex += m_insertionSet.execute(m_block);
849     }
850     
851     InsertionSet m_insertionSet;
852     BasicBlock* m_block;
853     unsigned m_nodeIndex;
854     Node* m_node;
855     bool m_changed;
856 };
857     
858 bool performStrengthReduction(Graph& graph)
859 {
860     return runPhase<StrengthReductionPhase>(graph);
861 }
862
863 } } // namespace JSC::DFG
864
865 #endif // ENABLE(DFG_JIT)
866