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 != INT32_MIN) {
 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_graph, 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             if (m_graph.willCatchExceptionInMachineFrame(m_node->origin.semantic)) {
 273                 // FIXME: We should be able to relax this:
 274                 // https://bugs.webkit.org/show_bug.cgi?id=150824
 275                 break;
 276             }
 277
 278             Node* setLocal = nullptr;
 279             VirtualRegister local = m_node->local();
 280
 281             for (unsigned i = m_nodeIndex; i--;) {
 282                 Node* node = m_block->at(i);
 283
 284                 if (node->op() == SetLocal && node->local() == local) {
 285                     setLocal = node;
 286                     break;
 287                 }
 288
 289                 if (accessesOverlap(m_graph, node, AbstractHeap(Stack, local)))
 290                     break;
 291
 292             }
 293
 294             if (!setLocal)
 295                 break;
 296
 297             // The Flush should become a PhantomLocal at this point. This means that we want the
 298             // local's value during OSR, but we don't care if the value is stored to the stack. CPS
 299             // rethreading can canonicalize PhantomLocals for us.
 300             m_node->convertFlushToPhantomLocal();
 301             m_graph.dethread();
 302             m_changed = true;
 303             break;
 304         }
 305
 306         // FIXME: we should probably do this in constant folding but this currently relies on an OSR exit rule.
 307         // https://bugs.webkit.org/show_bug.cgi?id=154832
 308         case OverridesHasInstance: {
 309             if (!m_node->child2().node()->isCellConstant())
 310                 break;
 311
 312             if (m_node->child2().node()->asCell() != m_graph.globalObjectFor(m_node->origin.semantic)->functionProtoHasInstanceSymbolFunction()) {
 313                 m_graph.convertToConstant(m_node, jsBoolean(true));
 314                 m_changed = true;
 315
 316             } else if (!m_graph.hasExitSite(m_node->origin.semantic, BadTypeInfoFlags)) {
 317                 // We optimistically assume that we will not see a function that has a custom instanceof operation as they should be rare.
 318                 m_insertionSet.insertNode(m_nodeIndex, SpecNone, CheckTypeInfoFlags, m_node->origin, OpInfo(ImplementsDefaultHasInstance), Edge(m_node->child1().node(), CellUse));
 319                 m_graph.convertToConstant(m_node, jsBoolean(false));
 320                 m_changed = true;
 321             }
 322
 323             break;
 324         }
 325
 326         // FIXME: We have a lot of string constant-folding rules here. It would be great to
 327         // move these to the abstract interpreter once AbstractValue can support LazyJSValue.
 328         // https://bugs.webkit.org/show_bug.cgi?id=155204
 329
 330         case ValueAdd: {
 331             if (m_node->child1()->isConstant()
 332                 && m_node->child2()->isConstant()
 333                 && (!!m_node->child1()->tryGetString(m_graph) || !!m_node->child2()->tryGetString(m_graph))) {
 334                 auto tryGetConstantString = [&] (Node* node) -> String {
 335                     String string = node->tryGetString(m_graph);
 336                     if (!string.isEmpty())
 337                         return string;
 338                     JSValue value = node->constant()->value();
 339                     if (!value)
 340                         return String();
 341                     if (value.isInt32())
 342                         return String::number(value.asInt32());
 343                     if (value.isNumber())
 344                         return String::numberToStringECMAScript(value.asNumber());
 345                     if (value.isBoolean())
 346                         return value.asBoolean() ? ASCIILiteral("true") : ASCIILiteral("false");
 347                     if (value.isNull())
 348                         return ASCIILiteral("null");
 349                     if (value.isUndefined())
 350                         return ASCIILiteral("undefined");
 351                     return String();
 352                 };
 353
 354                 String leftString = tryGetConstantString(m_node->child1().node());
 355                 if (!leftString)
 356                     break;
 357                 String rightString = tryGetConstantString(m_node->child2().node());
 358                 if (!rightString)
 359                     break;
 360
 361                 StringBuilder builder;
 362                 builder.append(leftString);
 363                 builder.append(rightString);
 364                 convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, builder.toString()));
 365                 m_changed = true;
 366             }
 367             break;
 368         }
 369
 370         case MakeRope:
 371         case StrCat: {
 372             String leftString = m_node->child1()->tryGetString(m_graph);
 373             if (!leftString)
 374                 break;
 375             String rightString = m_node->child2()->tryGetString(m_graph);
 376             if (!rightString)
 377                 break;
 378             String extraString;
 379             if (m_node->child3()) {
 380                 extraString = m_node->child3()->tryGetString(m_graph);
 381                 if (!extraString)
 382                     break;
 383             }
 384
 385             StringBuilder builder;
 386             builder.append(leftString);
 387             builder.append(rightString);
 388             if (!!extraString)
 389                 builder.append(extraString);
 390
 391             convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, builder.toString()));
 392             m_changed = true;
 393             break;
 394         }
 395
 396         case ToString:
 397         case CallStringConstructor: {
 398             Edge& child1 = m_node->child1();
 399             switch (child1.useKind()) {
 400             case Int32Use:
 401             case Int52RepUse:
 402             case DoubleRepUse: {
 403                 if (child1->hasConstant()) {
 404                     JSValue value = child1->constant()->value();
 405                     if (value) {
 406                         String result;
 407                         if (value.isInt32())
 408                             result = String::number(value.asInt32());
 409                         else if (value.isNumber())
 410                             result = String::numberToStringECMAScript(value.asNumber());
 411
 412                         if (!result.isNull()) {
 413                             convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, result));
 414                             m_changed = true;
 415                         }
 416                     }
 417                 }
 418                 break;
 419             }
 420
 421             default:
 422                 break;
 423             }
 424             break;
 425         }
 426
 427         case NumberToStringWithValidRadixConstant: {
 428             Edge& child1 = m_node->child1();
 429             if (child1->hasConstant()) {
 430                 JSValue value = child1->constant()->value();
 431                 if (value && value.isNumber()) {
 432                     String result = toStringWithRadix(value.asNumber(), m_node->validRadixConstant());
 433                     convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, result));
 434                     m_changed = true;
 435                 }
 436             }
 437             break;
 438         }
 439
 440         case GetArrayLength: {
 441             if (m_node->arrayMode().type() == Array::Generic
 442                 || m_node->arrayMode().type() == Array::String) {
 443                 String string = m_node->child1()->tryGetString(m_graph);
 444                 if (!!string) {
 445                     m_graph.convertToConstant(m_node, jsNumber(string.length()));
 446                     m_changed = true;
 447                     break;
 448                 }
 449             }
 450             break;
 451         }
 452
 453         case GetGlobalObject: {
 454             if (JSObject* object = m_node->child1()->dynamicCastConstant<JSObject*>(vm())) {
 455                 m_graph.convertToConstant(m_node, object->globalObject());
 456                 m_changed = true;
 457                 break;
 458             }
 459             break;
 460         }
 461
 462         case RegExpExec:
 463         case RegExpTest:
 464         case RegExpMatchFast:
 465         case RegExpExecNonGlobalOrSticky: {
 466             JSGlobalObject* globalObject = m_node->child1()->dynamicCastConstant<JSGlobalObject*>(vm());
 467             if (!globalObject) {
 468                 if (verbose)
 469                     dataLog("Giving up because no global object.\n");
 470                 break;
 471             }
 472
 473             if (globalObject->isHavingABadTime()) {
 474                 if (verbose)
 475                     dataLog("Giving up because bad time.\n");
 476                 break;
 477             }
 478
 479             Node* regExpObjectNode = nullptr;
 480             RegExp* regExp = nullptr;
 481             if (m_node->op() == RegExpExec || m_node->op() == RegExpTest || m_node->op() == RegExpMatchFast) {
 482                 regExpObjectNode = m_node->child2().node();
 483                 if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>(vm()))
 484                     regExp = regExpObject->regExp();
 485                 else if (regExpObjectNode->op() == NewRegexp)
 486                     regExp = regExpObjectNode->castOperand<RegExp*>();
 487                 else {
 488                     if (verbose)
 489                         dataLog("Giving up because the regexp is unknown.\n");
 490                     break;
 491                 }
 492             } else
 493                 regExp = m_node->castOperand<RegExp*>();
 494
 495             if (m_node->op() == RegExpMatchFast) {
 496                 if (regExp->global()) {
 497                     if (regExp->sticky())
 498                         break;
 499                     if (m_node->child3().useKind() != StringUse)
 500                         break;
 501                     NodeOrigin origin = m_node->origin;
 502                     m_insertionSet.insertNode(
 503                         m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
 504                     m_insertionSet.insertNode(
 505                         m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
 506                         OpInfo(false),
 507                         Edge(regExpObjectNode, RegExpObjectUse),
 508                         m_insertionSet.insertConstantForUse(
 509                             m_nodeIndex, origin, jsNumber(0), UntypedUse));
 510                     origin = origin.withInvalidExit();
 511                     m_node->convertToRegExpMatchFastGlobal(m_graph.freeze(regExp));
 512                     m_node->origin = origin;
 513                     m_changed = true;
 514                     break;
 515                 }
 516
 517                 m_node->setOp(RegExpExec);
 518                 m_changed = true;
 519                 // Continue performing strength reduction onto RegExpExec node.
 520             }
 521
 522             ASSERT(m_node->op() != RegExpMatchFast);
 523
 524             auto foldToConstant = [&] {
 525                 Node* stringNode = nullptr;
 526                 if (m_node->op() == RegExpExecNonGlobalOrSticky)
 527                     stringNode = m_node->child2().node();
 528                 else
 529                     stringNode = m_node->child3().node();
 530
 531                 // NOTE: This mostly already protects us from having the compiler execute a regexp
 532                 // operation on a ginormous string by preventing us from getting our hands on ginormous
 533                 // strings in the first place.
 534                 String string = stringNode->tryGetString(m_graph);
 535                 if (!string) {
 536                     if (verbose)
 537                         dataLog("Giving up because the string is unknown.\n");
 538                     return false;
 539                 }
 540
 541                 FrozenValue* regExpFrozenValue = m_graph.freeze(regExp);
 542
 543                 // Refuse to do things with regular expressions that have a ginormous number of
 544                 // subpatterns.
 545                 unsigned ginormousNumberOfSubPatterns = 1000;
 546                 if (regExp->numSubpatterns() > ginormousNumberOfSubPatterns) {
 547                     if (verbose)
 548                         dataLog("Giving up because of pattern limit.\n");
 549                     return false;
 550                 }
 551
 552                 if ((m_node->op() == RegExpExec || m_node->op() == RegExpExecNonGlobalOrSticky) && regExp->hasNamedCaptures()) {
 553                     // FIXME: https://bugs.webkit.org/show_bug.cgi?id=176464
 554                     // Implement strength reduction optimization for named capture groups.
 555                     if (verbose)
 556                         dataLog("Giving up because of named capture groups.\n");
 557                     return false;
 558                 }
 559
 560                 unsigned lastIndex;
 561                 if (regExp->globalOrSticky()) {
 562                     // This will only work if we can prove what the value of lastIndex is. To do this
 563                     // safely, we need to execute the insertion set so that we see any previous strength
 564                     // reductions. This is needed for soundness since otherwise the effectfulness of any
 565                     // previous strength reductions would be invisible to us.
 566                     ASSERT(regExpObjectNode);
 567                     executeInsertionSet();
 568                     lastIndex = UINT_MAX;
 569                     for (unsigned otherNodeIndex = m_nodeIndex; otherNodeIndex--;) {
 570                         Node* otherNode = m_block->at(otherNodeIndex);
 571                         if (otherNode == regExpObjectNode) {
 572                             lastIndex = 0;
 573                             break;
 574                         }
 575                         if (otherNode->op() == SetRegExpObjectLastIndex
 576                             && otherNode->child1() == regExpObjectNode
 577                             && otherNode->child2()->isInt32Constant()
 578                             && otherNode->child2()->asInt32() >= 0) {
 579                             lastIndex = static_cast<unsigned>(otherNode->child2()->asInt32());
 580                             break;
 581                         }
 582                         if (writesOverlap(m_graph, otherNode, RegExpObject_lastIndex))
 583                             break;
 584                     }
 585                     if (lastIndex == UINT_MAX) {
 586                         if (verbose)
 587                             dataLog("Giving up because the last index is not known.\n");
 588                         return false;
 589                     }
 590                 } else
 591                     lastIndex = 0;
 592
 593                 m_graph.watchpoints().addLazily(globalObject->havingABadTimeWatchpoint());
 594
 595                 Structure* structure;
 596                 if ((m_node->op() == RegExpExec || m_node->op() == RegExpExecNonGlobalOrSticky) && regExp->hasNamedCaptures())
 597                     structure = globalObject->regExpMatchesArrayWithGroupsStructure();
 598                 else
 599                     structure = globalObject->regExpMatchesArrayStructure();
 600
 601                 if (structure->indexingType() != ArrayWithContiguous) {
 602                     // This is further protection against a race with haveABadTime.
 603                     if (verbose)
 604                         dataLog("Giving up because the structure has the wrong indexing type.\n");
 605                     return false;
 606                 }
 607                 m_graph.registerStructure(structure);
 608
 609                 RegExpConstructor* constructor = globalObject->regExpConstructor();
 610                 FrozenValue* constructorFrozenValue = m_graph.freeze(constructor);
 611
 612                 MatchResult result;
 613                 Vector<int> ovector;
 614                 // We have to call the kind of match function that the main thread would have called.
 615                 // Otherwise, we might not have the desired Yarr code compiled, and the match will fail.
 616                 if (m_node->op() == RegExpExec || m_node->op() == RegExpExecNonGlobalOrSticky) {
 617                     int position;
 618                     if (!regExp->matchConcurrently(vm(), string, lastIndex, position, ovector)) {
 619                         if (verbose)
 620                             dataLog("Giving up because match failed.\n");
 621                         return false;
 622                     }
 623                     result.start = position;
 624                     result.end = ovector[1];
 625                 } else {
 626                     if (!regExp->matchConcurrently(vm(), string, lastIndex, result)) {
 627                         if (verbose)
 628                             dataLog("Giving up because match failed.\n");
 629                         return false;
 630                     }
 631                 }
 632
 633                 // We've constant-folded the regexp. Now we're committed to replacing RegExpExec/Test.
 634
 635                 m_changed = true;
 636
 637                 NodeOrigin origin = m_node->origin;
 638
 639                 m_insertionSet.insertNode(
 640                     m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
 641
 642                 if (m_node->op() == RegExpExec || m_node->op() == RegExpExecNonGlobalOrSticky) {
 643                     if (result) {
 644                         RegisteredStructureSet* structureSet = m_graph.addStructureSet(structure);
 645
 646                         // Create an array modeling the JS array that we will try to allocate. This is
 647                         // basically createRegExpMatchesArray but over C++ strings instead of JSStrings.
 648                         Vector<String> resultArray;
 649                         resultArray.append(string.substring(result.start, result.end - result.start));
 650                         for (unsigned i = 1; i <= regExp->numSubpatterns(); ++i) {
 651                             int start = ovector[2 * i];
 652                             if (start >= 0)
 653                                 resultArray.append(string.substring(start, ovector[2 * i + 1] - start));
 654                             else
 655                                 resultArray.append(String());
 656                         }
 657
 658                         unsigned publicLength = resultArray.size();
 659                         unsigned vectorLength =
 660                             Butterfly::optimalContiguousVectorLength(structure, publicLength);
 661
 662                         UniquedStringImpl* indexUID = vm().propertyNames->index.impl();
 663                         UniquedStringImpl* inputUID = vm().propertyNames->input.impl();
 664                         unsigned indexIndex = m_graph.identifiers().ensure(indexUID);
 665                         unsigned inputIndex = m_graph.identifiers().ensure(inputUID);
 666
 667                         unsigned firstChild = m_graph.m_varArgChildren.size();
 668                         m_graph.m_varArgChildren.append(
 669                             m_insertionSet.insertConstantForUse(
 670                                 m_nodeIndex, origin, structure, KnownCellUse));
 671                         ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
 672
 673                         m_graph.m_varArgChildren.append(
 674                             m_insertionSet.insertConstantForUse(
 675                                 m_nodeIndex, origin, jsNumber(publicLength), KnownInt32Use));
 676                         data->m_properties.append(PublicLengthPLoc);
 677
 678                         m_graph.m_varArgChildren.append(
 679                             m_insertionSet.insertConstantForUse(
 680                                 m_nodeIndex, origin, jsNumber(vectorLength), KnownInt32Use));
 681                         data->m_properties.append(VectorLengthPLoc);
 682
 683                         m_graph.m_varArgChildren.append(
 684                             m_insertionSet.insertConstantForUse(
 685                                 m_nodeIndex, origin, jsNumber(result.start), UntypedUse));
 686                         data->m_properties.append(
 687                             PromotedLocationDescriptor(NamedPropertyPLoc, indexIndex));
 688
 689                         m_graph.m_varArgChildren.append(Edge(stringNode, UntypedUse));
 690                         data->m_properties.append(
 691                             PromotedLocationDescriptor(NamedPropertyPLoc, inputIndex));
 692
 693                         auto materializeString = [&] (const String& string) -> Node* {
 694                             if (string.isNull())
 695                                 return nullptr;
 696                             if (string.isEmpty()) {
 697                                 return m_insertionSet.insertConstant(
 698                                     m_nodeIndex, origin, vm().smallStrings.emptyString());
 699                             }
 700                             LazyJSValue value = LazyJSValue::newString(m_graph, string);
 701                             return m_insertionSet.insertNode(
 702                                 m_nodeIndex, SpecNone, LazyJSConstant, origin,
 703                                 OpInfo(m_graph.m_lazyJSValues.add(value)));
 704                         };
 705
 706                         for (unsigned i = 0; i < resultArray.size(); ++i) {
 707                             if (Node* node = materializeString(resultArray[i])) {
 708                                 m_graph.m_varArgChildren.append(Edge(node, UntypedUse));
 709                                 data->m_properties.append(
 710                                     PromotedLocationDescriptor(IndexedPropertyPLoc, i));
 711                             }
 712                         }
 713
 714                         Node* resultNode = m_insertionSet.insertNode(
 715                             m_nodeIndex, SpecArray, Node::VarArg, MaterializeNewObject, origin,
 716                             OpInfo(structureSet), OpInfo(data), firstChild,
 717                             m_graph.m_varArgChildren.size() - firstChild);
 718
 719                         m_node->convertToIdentityOn(resultNode);
 720                     } else
 721                         m_graph.convertToConstant(m_node, jsNull());
 722                 } else
 723                     m_graph.convertToConstant(m_node, jsBoolean(!!result));
 724
 725                 // Whether it's Exec or Test, we need to tell the constructor and RegExpObject what's up.
 726                 // Because SetRegExpObjectLastIndex may exit and it clobbers exit state, we do that
 727                 // first.
 728
 729                 if (regExp->globalOrSticky()) {
 730                     ASSERT(regExpObjectNode);
 731                     m_insertionSet.insertNode(
 732                         m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
 733                         OpInfo(false),
 734                         Edge(regExpObjectNode, RegExpObjectUse),
 735                         m_insertionSet.insertConstantForUse(
 736                             m_nodeIndex, origin, jsNumber(result ? result.end : 0), UntypedUse));
 737
 738                     origin = origin.withInvalidExit();
 739                 }
 740
 741                 if (result) {
 742                     unsigned firstChild = m_graph.m_varArgChildren.size();
 743                     m_graph.m_varArgChildren.append(
 744                         m_insertionSet.insertConstantForUse(
 745                             m_nodeIndex, origin, constructorFrozenValue, KnownCellUse));
 746                     m_graph.m_varArgChildren.append(
 747                         m_insertionSet.insertConstantForUse(
 748                             m_nodeIndex, origin, regExpFrozenValue, KnownCellUse));
 749                     m_graph.m_varArgChildren.append(Edge(stringNode, KnownCellUse));
 750                     m_graph.m_varArgChildren.append(
 751                         m_insertionSet.insertConstantForUse(
 752                             m_nodeIndex, origin, jsNumber(result.start), KnownInt32Use));
 753                     m_graph.m_varArgChildren.append(
 754                         m_insertionSet.insertConstantForUse(
 755                             m_nodeIndex, origin, jsNumber(result.end), KnownInt32Use));
 756                     m_insertionSet.insertNode(
 757                         m_nodeIndex, SpecNone, Node::VarArg, RecordRegExpCachedResult, origin,
 758                         OpInfo(), OpInfo(), firstChild, m_graph.m_varArgChildren.size() - firstChild);
 759
 760                     origin = origin.withInvalidExit();
 761                 }
 762
 763                 m_node->origin = origin;
 764                 return true;
 765             };
 766
 767             auto convertToStatic = [&] {
 768                 if (m_node->op() != RegExpExec)
 769                     return false;
 770                 if (regExp->globalOrSticky())
 771                     return false;
 772                 if (m_node->child3().useKind() != StringUse)
 773                     return false;
 774                 NodeOrigin origin = m_node->origin;
 775                 m_insertionSet.insertNode(
 776                     m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
 777                 m_node->convertToRegExpExecNonGlobalOrSticky(m_graph.freeze(regExp));
 778                 m_changed = true;
 779                 return true;
 780             };
 781
 782             if (foldToConstant())
 783                 break;
 784
 785             if (convertToStatic())
 786                 break;
 787
 788             break;
 789         }
 790
 791         case StringReplace:
 792         case StringReplaceRegExp: {
 793             Node* stringNode = m_node->child1().node();
 794             String string = stringNode->tryGetString(m_graph);
 795             if (!string)
 796                 break;
 797
 798             Node* regExpObjectNode = m_node->child2().node();
 799             RegExp* regExp;
 800             if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>(vm()))
 801                 regExp = regExpObject->regExp();
 802             else if (regExpObjectNode->op() == NewRegexp)
 803                 regExp = regExpObjectNode->castOperand<RegExp*>();
 804             else {
 805                 if (verbose)
 806                     dataLog("Giving up because the regexp is unknown.\n");
 807                 break;
 808             }
 809
 810             String replace = m_node->child3()->tryGetString(m_graph);
 811             if (!replace)
 812                 break;
 813
 814             StringBuilder builder;
 815
 816             unsigned lastIndex = 0;
 817             unsigned startPosition = 0;
 818             bool ok = true;
 819             do {
 820                 MatchResult result;
 821                 Vector<int> ovector;
 822                 // Model which version of match() is called by the main thread.
 823                 if (replace.isEmpty() && regExp->global()) {
 824                     if (!regExp->matchConcurrently(vm(), string, startPosition, result)) {
 825                         ok = false;
 826                         break;
 827                     }
 828                 } else {
 829                     int position;
 830                     if (!regExp->matchConcurrently(vm(), string, startPosition, position, ovector)) {
 831                         ok = false;
 832                         break;
 833                     }
 834
 835                     result.start = position;
 836                     result.end = ovector[1];
 837                 }
 838
 839                 if (!result)
 840                     break;
 841
 842                 unsigned replLen = replace.length();
 843                 if (lastIndex < result.start || replLen) {
 844                     builder.append(string, lastIndex, result.start - lastIndex);
 845                     if (replLen)
 846                         builder.append(substituteBackreferences(replace, string, ovector.data(), regExp));
 847                 }
 848
 849                 lastIndex = result.end;
 850                 startPosition = lastIndex;
 851
 852                 // special case of empty match
 853                 if (result.empty()) {
 854                     startPosition++;
 855                     if (startPosition > string.length())
 856                         break;
 857                 }
 858             } while (regExp->global());
 859             if (!ok)
 860                 break;
 861
 862             // We are committed at this point.
 863             m_changed = true;
 864
 865             NodeOrigin origin = m_node->origin;
 866
 867             // Preserve any checks we have.
 868             m_insertionSet.insertNode(
 869                 m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
 870
 871             if (regExp->global()) {
 872                 m_insertionSet.insertNode(
 873                     m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
 874                     OpInfo(false),
 875                     Edge(regExpObjectNode, RegExpObjectUse),
 876                     m_insertionSet.insertConstantForUse(
 877                         m_nodeIndex, origin, jsNumber(0), UntypedUse));
 878
 879                 origin = origin.withInvalidExit();
 880             }
 881
 882             if (!lastIndex && builder.isEmpty())
 883                 m_node->convertToIdentityOn(stringNode);
 884             else {
 885                 if (lastIndex < string.length())
 886                     builder.append(string, lastIndex, string.length() - lastIndex);
 887
 888                 m_node->convertToLazyJSConstant(m_graph, LazyJSValue::newString(m_graph, builder.toString()));
 889             }
 890
 891             m_node->origin = origin;
 892             break;
 893         }
 894
 895         case Call:
 896         case Construct:
 897         case TailCallInlinedCaller:
 898         case TailCall: {
 899             ExecutableBase* executable = nullptr;
 900             Edge callee = m_graph.varArgChild(m_node, 0);
 901             if (JSFunction* function = callee->dynamicCastConstant<JSFunction*>(vm()))
 902                 executable = function->executable();
 903             else if (callee->isFunctionAllocation())
 904                 executable = callee->castOperand<FunctionExecutable*>();
 905
 906             if (!executable)
 907                 break;
 908
 909             if (FunctionExecutable* functionExecutable = jsDynamicCast<FunctionExecutable*>(vm(), executable)) {
 910                 // We need to update m_parameterSlots before we get to the backend, but we don't
 911                 // want to do too much of this.
 912                 unsigned numAllocatedArgs =
 913                     static_cast<unsigned>(functionExecutable->parameterCount()) + 1;
 914
 915                 if (numAllocatedArgs <= Options::maximumDirectCallStackSize()) {
 916                     m_graph.m_parameterSlots = std::max(
 917                         m_graph.m_parameterSlots,
 918                         Graph::parameterSlotsForArgCount(numAllocatedArgs));
 919                 }
 920             }
 921
 922             m_node->convertToDirectCall(m_graph.freeze(executable));
 923             m_changed = true;
 924             break;
 925         }
 926
 927         default:
 928             break;
 929         }
 930     }
 931
 932     void convertToIdentityOverChild(unsigned childIndex)
 933     {
 934         ASSERT(!(m_node->flags() & NodeHasVarArgs));
 935         m_insertionSet.insertCheck(m_graph, m_nodeIndex, m_node);
 936         m_node->children.removeEdge(childIndex ^ 1);
 937         m_node->convertToIdentity();
 938         m_changed = true;
 939     }
 940
 941     void convertToIdentityOverChild1()
 942     {
 943         convertToIdentityOverChild(0);
 944     }
 945
 946     void convertToIdentityOverChild2()
 947     {
 948         convertToIdentityOverChild(1);
 949     }
 950
 951     void convertToLazyJSValue(Node* node, LazyJSValue value)
 952     {
 953         m_insertionSet.insertCheck(m_graph, m_nodeIndex, node);
 954         node->convertToLazyJSConstant(m_graph, value);
 955     }
 956
 957     void handleCommutativity()
 958     {
 959         // It's definitely not sound to swap the lhs and rhs when we may be performing effectful
 960         // calls on the lhs/rhs for valueOf.
 961         if (m_node->child1().useKind() == UntypedUse || m_node->child2().useKind() == UntypedUse)
 962             return;
 963
 964         // If the right side is a constant then there is nothing left to do.
 965         if (m_node->child2()->hasConstant())
 966             return;
 967
 968         // This case ensures that optimizations that look for x + const don't also have
 969         // to look for const + x.
 970         if (m_node->child1()->hasConstant() && !m_node->child1()->asJSValue().isCell()) {
 971             std::swap(m_node->child1(), m_node->child2());
 972             m_changed = true;
 973             return;
 974         }
 975
 976         // This case ensures that CSE is commutativity-aware.
 977         if (m_node->child1().node() > m_node->child2().node()) {
 978             std::swap(m_node->child1(), m_node->child2());
 979             m_changed = true;
 980             return;
 981         }
 982     }
 983
 984     void executeInsertionSet()
 985     {
 986         m_nodeIndex += m_insertionSet.execute(m_block);
 987     }
 988
 989     InsertionSet m_insertionSet;
 990     BasicBlock* m_block;
 991     unsigned m_nodeIndex;
 992     Node* m_node;
 993     bool m_changed;
 994 };
 995
 996 bool performStrengthReduction(Graph& graph)
 997 {
 998     return runPhase<StrengthReductionPhase>(graph);
 999 }
1000
1001 } } // namespace JSC::DFG
1002
1003 #endif // ENABLE(DFG_JIT)
1004