Source/JavaScriptCore/dfg/DFGCSEPhase.cpp

   1 /*
   2  * Copyright (C) 2011, 2012 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 "DFGCSEPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGGraph.h"
  32 #include "DFGPhase.h"
  33
  34 namespace JSC { namespace DFG {
  35
  36 class CSEPhase : public Phase {
  37 public:
  38     CSEPhase(Graph& graph, OptimizationFixpointState fixpointState)
  39         : Phase(graph, "common subexpression elimination")
  40         , m_fixpointState(fixpointState)
  41     {
  42         // Replacements are used to implement local common subexpression elimination.
  43         m_replacements.resize(m_graph.size());
  44
  45         for (unsigned i = 0; i < m_graph.size(); ++i)
  46             m_replacements[i] = NoNode;
  47     }
  48
  49     bool run()
  50     {
  51         m_changed = false;
  52         for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
  53             performBlockCSE(m_graph.m_blocks[block].get());
  54         return m_changed;
  55     }
  56
  57 private:
  58
  59     NodeIndex canonicalize(NodeIndex nodeIndex)
  60     {
  61         if (nodeIndex == NoNode)
  62             return NoNode;
  63
  64         if (m_graph[nodeIndex].op() == ValueToInt32)
  65             nodeIndex = m_graph[nodeIndex].child1().index();
  66
  67         return nodeIndex;
  68     }
  69     NodeIndex canonicalize(Edge nodeUse)
  70     {
  71         return canonicalize(nodeUse.indexUnchecked());
  72     }
  73
  74     unsigned endIndexForPureCSE()
  75     {
  76         unsigned result = m_lastSeen[m_graph[m_compileIndex].op()];
  77         if (result == UINT_MAX)
  78             result = 0;
  79         else
  80             result++;
  81         ASSERT(result <= m_indexInBlock);
  82 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
  83         dataLog("  limit %u: ", result);
  84 #endif
  85         return result;
  86     }
  87
  88     NodeIndex pureCSE(Node& node)
  89     {
  90         NodeIndex child1 = canonicalize(node.child1());
  91         NodeIndex child2 = canonicalize(node.child2());
  92         NodeIndex child3 = canonicalize(node.child3());
  93
  94         for (unsigned i = endIndexForPureCSE(); i--;) {
  95             NodeIndex index = m_currentBlock->at(i);
  96             if (index == child1 || index == child2 || index == child3)
  97                 break;
  98
  99             Node& otherNode = m_graph[index];
 100             if (node.op() != otherNode.op())
 101                 continue;
 102
 103             if (node.arithNodeFlags() != otherNode.arithNodeFlags())
 104                 continue;
 105
 106             NodeIndex otherChild = canonicalize(otherNode.child1());
 107             if (otherChild == NoNode)
 108                 return index;
 109             if (otherChild != child1)
 110                 continue;
 111
 112             otherChild = canonicalize(otherNode.child2());
 113             if (otherChild == NoNode)
 114                 return index;
 115             if (otherChild != child2)
 116                 continue;
 117
 118             otherChild = canonicalize(otherNode.child3());
 119             if (otherChild == NoNode)
 120                 return index;
 121             if (otherChild != child3)
 122                 continue;
 123
 124             return index;
 125         }
 126         return NoNode;
 127     }
 128
 129     NodeIndex constantCSE(Node& node)
 130     {
 131         for (unsigned i = endIndexForPureCSE(); i--;) {
 132             NodeIndex index = m_currentBlock->at(i);
 133             Node& otherNode = m_graph[index];
 134             if (otherNode.op() != JSConstant)
 135                 continue;
 136
 137             if (otherNode.constantNumber() != node.constantNumber())
 138                 continue;
 139
 140             return index;
 141         }
 142         return NoNode;
 143     }
 144
 145     NodeIndex weakConstantCSE(Node& node)
 146     {
 147         for (unsigned i = endIndexForPureCSE(); i--;) {
 148             NodeIndex index = m_currentBlock->at(i);
 149             Node& otherNode = m_graph[index];
 150             if (otherNode.op() != WeakJSConstant)
 151                 continue;
 152
 153             if (otherNode.weakConstant() != node.weakConstant())
 154                 continue;
 155
 156             return index;
 157         }
 158         return NoNode;
 159     }
 160
 161     NodeIndex impureCSE(Node& node)
 162     {
 163         NodeIndex child1 = canonicalize(node.child1());
 164         NodeIndex child2 = canonicalize(node.child2());
 165         NodeIndex child3 = canonicalize(node.child3());
 166
 167         for (unsigned i = m_indexInBlock; i--;) {
 168             NodeIndex index = m_currentBlock->at(i);
 169             if (index == child1 || index == child2 || index == child3)
 170                 break;
 171
 172             Node& otherNode = m_graph[index];
 173             if (node.op() == otherNode.op()
 174                 && node.arithNodeFlags() == otherNode.arithNodeFlags()) {
 175                 NodeIndex otherChild = canonicalize(otherNode.child1());
 176                 if (otherChild == NoNode)
 177                     return index;
 178                 if (otherChild == child1) {
 179                     otherChild = canonicalize(otherNode.child2());
 180                     if (otherChild == NoNode)
 181                         return index;
 182                     if (otherChild == child2) {
 183                         otherChild = canonicalize(otherNode.child3());
 184                         if (otherChild == NoNode)
 185                             return index;
 186                         if (otherChild == child3)
 187                             return index;
 188                     }
 189                 }
 190             }
 191             if (m_graph.clobbersWorld(index))
 192                 break;
 193         }
 194         return NoNode;
 195     }
 196
 197     NodeIndex globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
 198     {
 199         for (unsigned i = m_indexInBlock; i--;) {
 200             NodeIndex index = m_currentBlock->at(i);
 201             Node& node = m_graph[index];
 202             switch (node.op()) {
 203             case GetGlobalVar:
 204                 if (node.registerPointer() == registerPointer)
 205                     return index;
 206                 break;
 207             case PutGlobalVar:
 208                 if (node.registerPointer() == registerPointer)
 209                     return node.child1().index();
 210                 break;
 211             default:
 212                 break;
 213             }
 214             if (m_graph.clobbersWorld(index))
 215                 break;
 216         }
 217         return NoNode;
 218     }
 219
 220     NodeIndex globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
 221     {
 222         for (unsigned i = m_indexInBlock; i--;) {
 223             NodeIndex index = m_currentBlock->at(i);
 224             Node& node = m_graph[index];
 225             if (!node.shouldGenerate())
 226                 continue;
 227             switch (node.op()) {
 228             case PutGlobalVar:
 229                 if (node.registerPointer() == registerPointer)
 230                     return index;
 231                 break;
 232
 233             case GetGlobalVar:
 234                 if (node.registerPointer() == registerPointer)
 235                     return NoNode;
 236                 break;
 237
 238             default:
 239                 break;
 240             }
 241             if (m_graph.clobbersWorld(index) || node.canExit())
 242                 return NoNode;
 243         }
 244         return NoNode;
 245     }
 246
 247     NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
 248     {
 249         for (unsigned i = m_indexInBlock; i--;) {
 250             NodeIndex index = m_currentBlock->at(i);
 251             if (index == child1 || index == canonicalize(child2))
 252                 break;
 253
 254             Node& node = m_graph[index];
 255             switch (node.op()) {
 256             case GetByVal:
 257                 if (!m_graph.byValIsPure(node))
 258                     return NoNode;
 259                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
 260                     return index;
 261                 break;
 262             case PutByVal:
 263             case PutByValAlias:
 264                 if (!m_graph.byValIsPure(node))
 265                     return NoNode;
 266                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
 267                     return node.child3().index();
 268                 // We must assume that the PutByVal will clobber the location we're getting from.
 269                 // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
 270                 // different type than the GetByVal, then we know that they won't clobber each other.
 271                 return NoNode;
 272             case PutStructure:
 273             case PutByOffset:
 274                 // GetByVal currently always speculates that it's accessing an
 275                 // array with an integer index, which means that it's impossible
 276                 // for a structure change or a put to property storage to affect
 277                 // the GetByVal.
 278                 break;
 279             case ArrayPush:
 280                 // A push cannot affect previously existing elements in the array.
 281                 break;
 282             default:
 283                 if (m_graph.clobbersWorld(index))
 284                     return NoNode;
 285                 break;
 286             }
 287         }
 288         return NoNode;
 289     }
 290
 291     bool checkFunctionElimination(JSFunction* function, NodeIndex child1)
 292     {
 293         for (unsigned i = endIndexForPureCSE(); i--;) {
 294             NodeIndex index = m_currentBlock->at(i);
 295             if (index == child1)
 296                 break;
 297
 298             Node& node = m_graph[index];
 299             if (node.op() == CheckFunction && node.child1() == child1 && node.function() == function)
 300                 return true;
 301         }
 302         return false;
 303     }
 304
 305     bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1)
 306     {
 307         for (unsigned i = m_indexInBlock; i--;) {
 308             NodeIndex index = m_currentBlock->at(i);
 309             if (index == child1)
 310                 break;
 311
 312             Node& node = m_graph[index];
 313             switch (node.op()) {
 314             case CheckStructure:
 315                 if (node.child1() == child1
 316                     && structureSet.isSupersetOf(node.structureSet()))
 317                     return true;
 318                 break;
 319
 320             case PutStructure:
 321                 if (node.child1() == child1
 322                     && structureSet.contains(node.structureTransitionData().newStructure))
 323                     return true;
 324                 if (structureSet.contains(node.structureTransitionData().previousStructure))
 325                     return false;
 326                 break;
 327
 328             case PutByOffset:
 329                 // Setting a property cannot change the structure.
 330                 break;
 331
 332             case PutByVal:
 333             case PutByValAlias:
 334                 if (m_graph.byValIsPure(node)) {
 335                     // If PutByVal speculates that it's accessing an array with an
 336                     // integer index, then it's impossible for it to cause a structure
 337                     // change.
 338                     break;
 339                 }
 340                 return false;
 341
 342             default:
 343                 if (m_graph.clobbersWorld(index))
 344                     return false;
 345                 break;
 346             }
 347         }
 348         return false;
 349     }
 350
 351     NodeIndex putStructureStoreElimination(NodeIndex child1)
 352     {
 353         for (unsigned i = m_indexInBlock; i--;) {
 354             NodeIndex index = m_currentBlock->at(i);
 355             if (index == child1)
 356                 break;
 357             Node& node = m_graph[index];
 358             if (!node.shouldGenerate())
 359                 break;
 360             switch (node.op()) {
 361             case CheckStructure:
 362                 return NoNode;
 363
 364             case PhantomPutStructure:
 365                 if (node.child1() == child1) // No need to retrace our steps.
 366                     return NoNode;
 367                 break;
 368
 369             case PutStructure:
 370                 if (node.child1() == child1)
 371                     return index;
 372                 break;
 373
 374             // PutStructure needs to execute if we GC. Hence this needs to
 375             // be careful with respect to nodes that GC.
 376             case CreateArguments:
 377             case TearOffArguments:
 378             case NewFunctionNoCheck:
 379             case NewFunction:
 380             case NewFunctionExpression:
 381             case CreateActivation:
 382             case TearOffActivation:
 383             case StrCat:
 384             case ToPrimitive:
 385             case NewRegexp:
 386             case NewArrayBuffer:
 387             case NewArray:
 388             case NewObject:
 389             case CreateThis:
 390                 return NoNode;
 391
 392             default:
 393                 break;
 394             }
 395             if (m_graph.clobbersWorld(index) || node.canExit())
 396                 return NoNode;
 397         }
 398         return NoNode;
 399     }
 400
 401     NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
 402     {
 403         for (unsigned i = m_indexInBlock; i--;) {
 404             NodeIndex index = m_currentBlock->at(i);
 405             if (index == child1)
 406                 break;
 407
 408             Node& node = m_graph[index];
 409             switch (node.op()) {
 410             case GetByOffset:
 411                 if (node.child1() == child1
 412                     && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
 413                     return index;
 414                 break;
 415
 416             case PutByOffset:
 417                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
 418                     if (node.child1() == child1) // Must be same property storage.
 419                         return node.child3().index();
 420                     return NoNode;
 421                 }
 422                 break;
 423
 424             case PutStructure:
 425                 // Changing the structure cannot change the outcome of a property get.
 426                 break;
 427
 428             case PutByVal:
 429             case PutByValAlias:
 430                 if (m_graph.byValIsPure(node)) {
 431                     // If PutByVal speculates that it's accessing an array with an
 432                     // integer index, then it's impossible for it to cause a structure
 433                     // change.
 434                     break;
 435                 }
 436                 return NoNode;
 437
 438             default:
 439                 if (m_graph.clobbersWorld(index))
 440                     return NoNode;
 441                 break;
 442             }
 443         }
 444         return NoNode;
 445     }
 446
 447     NodeIndex putByOffsetStoreElimination(unsigned identifierNumber, NodeIndex child1)
 448     {
 449         for (unsigned i = m_indexInBlock; i--;) {
 450             NodeIndex index = m_currentBlock->at(i);
 451             if (index == child1)
 452                 break;
 453
 454             Node& node = m_graph[index];
 455             if (!node.shouldGenerate())
 456                 continue;
 457             switch (node.op()) {
 458             case GetByOffset:
 459                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
 460                     return NoNode;
 461                 break;
 462
 463             case PutByOffset:
 464                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
 465                     if (node.child1() == child1) // Must be same property storage.
 466                         return index;
 467                     return NoNode;
 468                 }
 469                 break;
 470
 471             case PutByVal:
 472             case PutByValAlias:
 473             case GetByVal:
 474                 if (m_graph.byValIsPure(node)) {
 475                     // If PutByVal speculates that it's accessing an array with an
 476                     // integer index, then it's impossible for it to cause a structure
 477                     // change.
 478                     break;
 479                 }
 480                 return NoNode;
 481
 482             default:
 483                 if (m_graph.clobbersWorld(index))
 484                     return NoNode;
 485                 break;
 486             }
 487             if (node.canExit())
 488                 return NoNode;
 489         }
 490         return NoNode;
 491     }
 492
 493     NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
 494     {
 495         for (unsigned i = m_indexInBlock; i--;) {
 496             NodeIndex index = m_currentBlock->at(i);
 497             if (index == child1)
 498                 break;
 499
 500             Node& node = m_graph[index];
 501             switch (node.op()) {
 502             case GetPropertyStorage:
 503                 if (node.child1() == child1)
 504                     return index;
 505                 break;
 506
 507             case PutByOffset:
 508             case PutStructure:
 509                 // Changing the structure or putting to the storage cannot
 510                 // change the property storage pointer.
 511                 break;
 512
 513             case PutByVal:
 514             case PutByValAlias:
 515                 if (m_graph.byValIsPure(node)) {
 516                     // If PutByVal speculates that it's accessing an array with an
 517                     // integer index, then it's impossible for it to cause a structure
 518                     // change.
 519                     break;
 520                 }
 521                 return NoNode;
 522
 523             default:
 524                 if (m_graph.clobbersWorld(index))
 525                     return NoNode;
 526                 break;
 527             }
 528         }
 529         return NoNode;
 530     }
 531
 532     NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, bool hasIntegerIndexPrediction)
 533     {
 534         for (unsigned i = m_indexInBlock; i--;) {
 535             NodeIndex index = m_currentBlock->at(i);
 536             if (index == child1)
 537                 break;
 538
 539             Node& node = m_graph[index];
 540             switch (node.op()) {
 541             case GetIndexedPropertyStorage: {
 542                 SpeculatedType basePrediction = m_graph[node.child2()].prediction();
 543                 bool nodeHasIntegerIndexPrediction = !(!(basePrediction & SpecInt32) && basePrediction);
 544                 if (node.child1() == child1 && hasIntegerIndexPrediction == nodeHasIntegerIndexPrediction)
 545                     return index;
 546                 break;
 547             }
 548
 549             case PutByOffset:
 550             case PutStructure:
 551                 // Changing the structure or putting to the storage cannot
 552                 // change the property storage pointer.
 553                 break;
 554
 555             case PutByValAlias:
 556                 // PutByValAlias can't change the indexed storage pointer
 557                 break;
 558
 559             case PutByVal:
 560                 if (isFixedIndexedStorageObjectSpeculation(m_graph[node.child1()].prediction()) && m_graph.byValIsPure(node))
 561                     break;
 562                 return NoNode;
 563
 564             default:
 565                 if (m_graph.clobbersWorld(index))
 566                     return NoNode;
 567                 break;
 568             }
 569         }
 570         return NoNode;
 571     }
 572
 573     NodeIndex getScopeChainLoadElimination(unsigned depth)
 574     {
 575         for (unsigned i = endIndexForPureCSE(); i--;) {
 576             NodeIndex index = m_currentBlock->at(i);
 577             Node& node = m_graph[index];
 578             if (node.op() == GetScopeChain
 579                 && node.scopeChainDepth() == depth)
 580                 return index;
 581         }
 582         return NoNode;
 583     }
 584
 585     NodeIndex getLocalLoadElimination(VirtualRegister local, NodeIndex& relevantLocalOp)
 586     {
 587         relevantLocalOp = NoNode;
 588
 589         for (unsigned i = m_indexInBlock; i--;) {
 590             NodeIndex index = m_currentBlock->at(i);
 591             Node& node = m_graph[index];
 592             switch (node.op()) {
 593             case GetLocal:
 594                 if (node.local() == local) {
 595                     relevantLocalOp = index;
 596                     return index;
 597                 }
 598                 break;
 599
 600             case GetLocalUnlinked:
 601                 if (node.unlinkedLocal() == local) {
 602                     relevantLocalOp = index;
 603                     return index;
 604                 }
 605                 break;
 606
 607             case SetLocal:
 608                 if (node.local() == local) {
 609                     relevantLocalOp = index;
 610                     return node.child1().index();
 611                 }
 612                 break;
 613
 614             default:
 615                 if (m_graph.clobbersWorld(index))
 616                     return NoNode;
 617                 break;
 618             }
 619         }
 620         return NoNode;
 621     }
 622
 623     struct SetLocalStoreEliminationResult {
 624         SetLocalStoreEliminationResult()
 625             : mayBeAccessed(false)
 626             , mayExit(false)
 627             , mayClobberWorld(false)
 628         {
 629         }
 630
 631         bool mayBeAccessed;
 632         bool mayExit;
 633         bool mayClobberWorld;
 634     };
 635     SetLocalStoreEliminationResult setLocalStoreElimination(
 636         VirtualRegister local, NodeIndex expectedNodeIndex)
 637     {
 638         SetLocalStoreEliminationResult result;
 639         for (unsigned i = m_indexInBlock; i--;) {
 640             NodeIndex index = m_currentBlock->at(i);
 641             Node& node = m_graph[index];
 642             if (!node.shouldGenerate())
 643                 continue;
 644             switch (node.op()) {
 645             case GetLocal:
 646             case Flush:
 647                 if (node.local() == local)
 648                     result.mayBeAccessed = true;
 649                 break;
 650
 651             case GetLocalUnlinked:
 652                 if (node.unlinkedLocal() == local)
 653                     result.mayBeAccessed = true;
 654                 break;
 655
 656             case SetLocal: {
 657                 if (node.local() != local)
 658                     break;
 659                 if (index != expectedNodeIndex)
 660                     result.mayBeAccessed = true;
 661                 if (m_graph[index].refCount() > 1)
 662                     result.mayBeAccessed = true;
 663                 return result;
 664             }
 665
 666             case GetScopeChain:
 667                 if (m_graph.uncheckedActivationRegisterFor(node.codeOrigin) == local)
 668                     result.mayBeAccessed = true;
 669                 break;
 670
 671             case CheckArgumentsNotCreated:
 672             case GetMyArgumentsLength:
 673             case GetMyArgumentsLengthSafe:
 674                 if (m_graph.uncheckedArgumentsRegisterFor(node.codeOrigin) == local)
 675                     result.mayBeAccessed = true;
 676                 break;
 677
 678             case GetMyArgumentByVal:
 679             case GetMyArgumentByValSafe:
 680                 result.mayBeAccessed = true;
 681                 break;
 682
 683             case GetByVal:
 684                 // If this is accessing arguments then it's potentially accessing locals.
 685                 if (m_graph[node.child1()].shouldSpeculateArguments())
 686                     result.mayBeAccessed = true;
 687                 break;
 688
 689             case CreateArguments:
 690             case TearOffActivation:
 691             case TearOffArguments:
 692                 // If an activation is being torn off then it means that captured variables
 693                 // are live. We could be clever here and check if the local qualifies as an
 694                 // argument register. But that seems like it would buy us very little since
 695                 // any kind of tear offs are rare to begin with.
 696                 result.mayBeAccessed = true;
 697                 break;
 698
 699             default:
 700                 break;
 701             }
 702             result.mayExit |= node.canExit();
 703             result.mayClobberWorld |= m_graph.clobbersWorld(index);
 704         }
 705         ASSERT_NOT_REACHED();
 706         // Be safe in release mode.
 707         result.mayBeAccessed = true;
 708         return result;
 709     }
 710
 711     void performSubstitution(Edge& child, bool addRef = true)
 712     {
 713         // Check if this operand is actually unused.
 714         if (!child)
 715             return;
 716
 717         // Check if there is any replacement.
 718         NodeIndex replacement = m_replacements[child.index()];
 719         if (replacement == NoNode)
 720             return;
 721
 722         child.setIndex(replacement);
 723
 724         // There is definitely a replacement. Assert that the replacement does not
 725         // have a replacement.
 726         ASSERT(m_replacements[child.index()] == NoNode);
 727
 728         if (addRef)
 729             m_graph[child].ref();
 730     }
 731
 732     enum PredictionHandlingMode { RequireSamePrediction, AllowPredictionMismatch };
 733     bool setReplacement(NodeIndex replacement, PredictionHandlingMode predictionHandlingMode = RequireSamePrediction)
 734     {
 735         if (replacement == NoNode)
 736             return false;
 737
 738         // Be safe. Don't try to perform replacements if the predictions don't
 739         // agree.
 740         if (predictionHandlingMode == RequireSamePrediction
 741             && m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
 742             return false;
 743
 744 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 745         dataLog("   Replacing @%u -> @%u", m_compileIndex, replacement);
 746 #endif
 747
 748         Node& node = m_graph[m_compileIndex];
 749         node.setOpAndDefaultFlags(Phantom);
 750         node.setRefCount(1);
 751
 752         // At this point we will eliminate all references to this node.
 753         m_replacements[m_compileIndex] = replacement;
 754
 755         return true;
 756     }
 757
 758     void eliminate()
 759     {
 760 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 761         dataLog("   Eliminating @%u", m_compileIndex);
 762 #endif
 763
 764         Node& node = m_graph[m_compileIndex];
 765         ASSERT(node.refCount() == 1);
 766         ASSERT(node.mustGenerate());
 767         node.setOpAndDefaultFlags(Phantom);
 768     }
 769
 770     void eliminate(NodeIndex nodeIndex, NodeType phantomType = Phantom)
 771     {
 772         if (nodeIndex == NoNode)
 773             return;
 774         Node& node = m_graph[nodeIndex];
 775         if (node.refCount() != 1)
 776             return;
 777         ASSERT(node.mustGenerate());
 778         node.setOpAndDefaultFlags(phantomType);
 779     }
 780
 781     void performNodeCSE(Node& node)
 782     {
 783         bool shouldGenerate = node.shouldGenerate();
 784
 785         if (node.flags() & NodeHasVarArgs) {
 786             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
 787                 performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
 788         } else {
 789             performSubstitution(node.children.child1(), shouldGenerate);
 790             performSubstitution(node.children.child2(), shouldGenerate);
 791             performSubstitution(node.children.child3(), shouldGenerate);
 792         }
 793
 794         if (!shouldGenerate)
 795             return;
 796
 797 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 798         dataLog("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex);
 799 #endif
 800
 801         // NOTE: there are some nodes that we deliberately don't CSE even though we
 802         // probably could, like StrCat and ToPrimitive. That's because there is no
 803         // evidence that doing CSE on these nodes would result in a performance
 804         // progression. Hence considering these nodes in CSE would just mean that this
 805         // code does more work with no win. Of course, we may want to reconsider this,
 806         // since StrCat is trivially CSE-able. It's not trivially doable for
 807         // ToPrimitive, but we could change that with some speculations if we really
 808         // needed to.
 809
 810         switch (node.op()) {
 811
 812         // Handle the pure nodes. These nodes never have any side-effects.
 813         case BitAnd:
 814         case BitOr:
 815         case BitXor:
 816         case BitRShift:
 817         case BitLShift:
 818         case BitURShift:
 819         case ArithAdd:
 820         case ArithSub:
 821         case ArithNegate:
 822         case ArithMul:
 823         case ArithMod:
 824         case ArithDiv:
 825         case ArithAbs:
 826         case ArithMin:
 827         case ArithMax:
 828         case ArithSqrt:
 829         case GetInt8ArrayLength:
 830         case GetInt16ArrayLength:
 831         case GetInt32ArrayLength:
 832         case GetUint8ArrayLength:
 833         case GetUint8ClampedArrayLength:
 834         case GetUint16ArrayLength:
 835         case GetUint32ArrayLength:
 836         case GetFloat32ArrayLength:
 837         case GetFloat64ArrayLength:
 838         case GetCallee:
 839         case GetStringLength:
 840         case StringCharAt:
 841         case StringCharCodeAt:
 842         case Int32ToDouble:
 843         case IsUndefined:
 844         case IsBoolean:
 845         case IsNumber:
 846         case IsString:
 847         case IsObject:
 848         case IsFunction:
 849         case DoubleAsInt32:
 850         case LogicalNot:
 851             setReplacement(pureCSE(node));
 852             break;
 853
 854         case GetLocal: {
 855             VariableAccessData* variableAccessData = node.variableAccessData();
 856             if (!variableAccessData->isCaptured())
 857                 break;
 858             NodeIndex relevantLocalOp;
 859             NodeIndex possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp);
 860             ASSERT(relevantLocalOp == NoNode
 861                    || m_graph[relevantLocalOp].op() == GetLocalUnlinked
 862                    || m_graph[relevantLocalOp].variableAccessData() == variableAccessData);
 863             NodeIndex phiIndex = node.child1().index();
 864             if (!setReplacement(possibleReplacement))
 865                 break;
 866             // If the GetLocal we replaced used to refer to a SetLocal, then it now
 867             // should refer to the child of the SetLocal instead.
 868             if (m_graph[phiIndex].op() == SetLocal) {
 869                 ASSERT(node.child1().index() == phiIndex);
 870                 m_graph.changeEdge(node.children.child1(), m_graph[phiIndex].child1());
 871             }
 872             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(
 873                 variableAccessData->local());
 874             if (oldTailIndex == m_compileIndex) {
 875                 m_currentBlock->variablesAtTail.operand(variableAccessData->local()) =
 876                     relevantLocalOp;
 877
 878                 // Maintain graph integrity: since we're replacing a GetLocal with a GetLocalUnlinked,
 879                 // make sure that the GetLocalUnlinked is now linked.
 880                 if (m_graph[relevantLocalOp].op() == GetLocalUnlinked) {
 881                     m_graph[relevantLocalOp].setOp(GetLocal);
 882                     m_graph[relevantLocalOp].children.child1() = Edge(phiIndex);
 883                     m_graph.ref(phiIndex);
 884                 }
 885             }
 886             m_changed = true;
 887             break;
 888         }
 889
 890         case GetLocalUnlinked: {
 891             NodeIndex relevantLocalOpIgnored;
 892             m_changed |= setReplacement(getLocalLoadElimination(node.unlinkedLocal(), relevantLocalOpIgnored));
 893             break;
 894         }
 895
 896         case Flush: {
 897             VariableAccessData* variableAccessData = node.variableAccessData();
 898             VirtualRegister local = variableAccessData->local();
 899             NodeIndex replacementIndex = node.child1().index();
 900             Node& replacement = m_graph[replacementIndex];
 901             if (replacement.op() != SetLocal)
 902                 break;
 903             ASSERT(replacement.variableAccessData() == variableAccessData);
 904             // FIXME: We should be able to remove SetLocals that can exit; we just need
 905             // to replace them with appropriate type checks.
 906             if (m_fixpointState == FixpointNotConverged) {
 907                 // Need to be conservative at this time; if the SetLocal has any chance of performing
 908                 // any speculations then we cannot do anything.
 909                 if (variableAccessData->isCaptured()) {
 910                     // Captured SetLocals never speculate and hence never exit.
 911                 } else {
 912                     if (variableAccessData->shouldUseDoubleFormat())
 913                         break;
 914                     SpeculatedType prediction = variableAccessData->argumentAwarePrediction();
 915                     if (isInt32Speculation(prediction))
 916                         break;
 917                     if (isArraySpeculation(prediction))
 918                         break;
 919                     if (isBooleanSpeculation(prediction))
 920                         break;
 921                 }
 922             } else {
 923                 if (replacement.canExit())
 924                     break;
 925             }
 926             SetLocalStoreEliminationResult result =
 927                 setLocalStoreElimination(local, replacementIndex);
 928             if (result.mayBeAccessed || result.mayClobberWorld)
 929                 break;
 930             ASSERT(replacement.op() == SetLocal);
 931             ASSERT(replacement.refCount() == 1);
 932             ASSERT(replacement.shouldGenerate());
 933             // FIXME: Investigate using mayExit as a further optimization.
 934             node.setOpAndDefaultFlags(Phantom);
 935             NodeIndex dataNodeIndex = replacement.child1().index();
 936             ASSERT(m_graph[dataNodeIndex].hasResult());
 937             m_graph.clearAndDerefChild1(node);
 938             node.children.child1() = Edge(dataNodeIndex);
 939             m_graph.ref(dataNodeIndex);
 940             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(local);
 941             if (oldTailIndex == m_compileIndex)
 942                 m_currentBlock->variablesAtTail.operand(local) = replacementIndex;
 943             m_changed = true;
 944             break;
 945         }
 946
 947         case JSConstant:
 948             // This is strange, but necessary. Some phases will convert nodes to constants,
 949             // which may result in duplicated constants. We use CSE to clean this up.
 950             setReplacement(constantCSE(node), AllowPredictionMismatch);
 951             break;
 952
 953         case WeakJSConstant:
 954             // FIXME: have CSE for weak constants against strong constants and vice-versa.
 955             setReplacement(weakConstantCSE(node));
 956             break;
 957
 958         case GetArrayLength:
 959             setReplacement(impureCSE(node));
 960             break;
 961
 962         case GetScopeChain:
 963             setReplacement(getScopeChainLoadElimination(node.scopeChainDepth()));
 964             break;
 965
 966         // Handle nodes that are conditionally pure: these are pure, and can
 967         // be CSE'd, so long as the prediction is the one we want.
 968         case ValueAdd:
 969         case CompareLess:
 970         case CompareLessEq:
 971         case CompareGreater:
 972         case CompareGreaterEq:
 973         case CompareEq: {
 974             if (m_graph.isPredictedNumerical(node)) {
 975                 NodeIndex replacementIndex = pureCSE(node);
 976                 if (replacementIndex != NoNode && m_graph.isPredictedNumerical(m_graph[replacementIndex]))
 977                     setReplacement(replacementIndex);
 978             }
 979             break;
 980         }
 981
 982         // Finally handle heap accesses. These are not quite pure, but we can still
 983         // optimize them provided that some subtle conditions are met.
 984         case GetGlobalVar:
 985             setReplacement(globalVarLoadElimination(node.registerPointer()));
 986             break;
 987
 988         case PutGlobalVar:
 989             if (m_fixpointState == FixpointNotConverged)
 990                 break;
 991             eliminate(globalVarStoreElimination(node.registerPointer()));
 992             break;
 993
 994         case GetByVal:
 995             if (m_graph.byValIsPure(node))
 996                 setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index()));
 997             break;
 998
 999         case PutByVal:
1000             if (m_graph.byValIsPure(node)
1001                 && !m_graph[node.child1()].shouldSpeculateArguments()
1002                 && getByValLoadElimination(node.child1().index(), node.child2().index()) != NoNode)
1003                 node.setOp(PutByValAlias);
1004             break;
1005
1006         case CheckStructure:
1007             if (checkStructureLoadElimination(node.structureSet(), node.child1().index()))
1008                 eliminate();
1009             break;
1010
1011         case PutStructure:
1012             if (m_fixpointState == FixpointNotConverged)
1013                 break;
1014             eliminate(putStructureStoreElimination(node.child1().index()), PhantomPutStructure);
1015             break;
1016
1017         case CheckFunction:
1018             if (checkFunctionElimination(node.function(), node.child1().index()))
1019                 eliminate();
1020             break;
1021
1022         case GetIndexedPropertyStorage: {
1023             SpeculatedType basePrediction = m_graph[node.child2()].prediction();
1024             bool nodeHasIntegerIndexPrediction = !(!(basePrediction & SpecInt32) && basePrediction);
1025             setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), nodeHasIntegerIndexPrediction));
1026             break;
1027         }
1028
1029         case GetPropertyStorage:
1030             setReplacement(getPropertyStorageLoadElimination(node.child1().index()));
1031             break;
1032
1033         case GetByOffset:
1034             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1035             break;
1036
1037         case PutByOffset:
1038             if (m_fixpointState == FixpointNotConverged)
1039                 break;
1040             eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1041             break;
1042
1043         default:
1044             // do nothing.
1045             break;
1046         }
1047
1048         m_lastSeen[node.op()] = m_indexInBlock;
1049 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1050         dataLog("\n");
1051 #endif
1052     }
1053
1054     void performBlockCSE(BasicBlock* block)
1055     {
1056         if (!block)
1057             return;
1058         if (!block->isReachable)
1059             return;
1060
1061         m_currentBlock = block;
1062         for (unsigned i = 0; i < LastNodeType; ++i)
1063             m_lastSeen[i] = UINT_MAX;
1064
1065         for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
1066             m_compileIndex = block->at(m_indexInBlock);
1067             performNodeCSE(m_graph[m_compileIndex]);
1068         }
1069     }
1070
1071     BasicBlock* m_currentBlock;
1072     NodeIndex m_compileIndex;
1073     unsigned m_indexInBlock;
1074     Vector<NodeIndex, 16> m_replacements;
1075     FixedArray<unsigned, LastNodeType> m_lastSeen;
1076     OptimizationFixpointState m_fixpointState;
1077     bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
1078 };
1079
1080 bool performCSE(Graph& graph, OptimizationFixpointState fixpointState)
1081 {
1082     return runPhase<CSEPhase>(graph, fixpointState);
1083 }
1084
1085 } } // namespace JSC::DFG
1086
1087 #endif // ENABLE(DFG_JIT)
1088
1089