dfg/DFGCSEPhase.cpp

   1 /*
   2  * Copyright (C) 2011, 2012, 2013 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 #include "JSCellInlines.h"
  34 #include <wtf/FastBitVector.h>
  35
  36 namespace JSC { namespace DFG {
  37
  38 enum CSEMode { NormalCSE, StoreElimination };
  39
  40 template<CSEMode cseMode>
  41 class CSEPhase : public Phase {
  42 public:
  43     CSEPhase(Graph& graph)
  44         : Phase(graph, cseMode == NormalCSE ? "common subexpression elimination" : "store elimination")
  45     {
  46     }
  47
  48     bool run()
  49     {
  50         ASSERT((cseMode == NormalCSE) == (m_graph.m_fixpointState == FixpointNotConverged));
  51         ASSERT(m_graph.m_fixpointState != BeforeFixpoint);
  52
  53         m_changed = false;
  54
  55         for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
  56             performBlockCSE(m_graph.m_blocks[block].get());
  57
  58         return m_changed;
  59     }
  60
  61 private:
  62
  63     Node* canonicalize(Node* node)
  64     {
  65         if (!node)
  66             return 0;
  67
  68         if (node->op() == ValueToInt32)
  69             node = node->child1().node();
  70
  71         return node;
  72     }
  73     Node* canonicalize(Edge edge)
  74     {
  75         return canonicalize(edge.node());
  76     }
  77
  78     unsigned endIndexForPureCSE()
  79     {
  80         unsigned result = m_lastSeen[m_currentNode->op()];
  81         if (result == UINT_MAX)
  82             result = 0;
  83         else
  84             result++;
  85         ASSERT(result <= m_indexInBlock);
  86 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
  87         dataLogF("  limit %u: ", result);
  88 #endif
  89         return result;
  90     }
  91
  92     Node* pureCSE(Node* node)
  93     {
  94         Node* child1 = canonicalize(node->child1());
  95         Node* child2 = canonicalize(node->child2());
  96         Node* child3 = canonicalize(node->child3());
  97
  98         for (unsigned i = endIndexForPureCSE(); i--;) {
  99             Node* otherNode = m_currentBlock->at(i);
 100             if (otherNode == child1 || otherNode == child2 || otherNode == child3)
 101                 break;
 102
 103             if (node->op() != otherNode->op())
 104                 continue;
 105
 106             if (node->arithNodeFlags() != otherNode->arithNodeFlags())
 107                 continue;
 108
 109             Node* otherChild = canonicalize(otherNode->child1());
 110             if (!otherChild)
 111                 return otherNode;
 112             if (otherChild != child1)
 113                 continue;
 114
 115             otherChild = canonicalize(otherNode->child2());
 116             if (!otherChild)
 117                 return otherNode;
 118             if (otherChild != child2)
 119                 continue;
 120
 121             otherChild = canonicalize(otherNode->child3());
 122             if (!otherChild)
 123                 return otherNode;
 124             if (otherChild != child3)
 125                 continue;
 126
 127             return otherNode;
 128         }
 129         return 0;
 130     }
 131
 132     Node* int32ToDoubleCSE(Node* node)
 133     {
 134         for (unsigned i = m_indexInBlock; i--;) {
 135             Node* otherNode = m_currentBlock->at(i);
 136             if (otherNode == node->child1())
 137                 return 0;
 138             switch (otherNode->op()) {
 139             case Int32ToDouble:
 140             case ForwardInt32ToDouble:
 141                 if (otherNode->child1() == node->child1())
 142                     return otherNode;
 143                 break;
 144             default:
 145                 break;
 146             }
 147         }
 148         return 0;
 149     }
 150
 151     Node* constantCSE(Node* node)
 152     {
 153         for (unsigned i = endIndexForPureCSE(); i--;) {
 154             Node* otherNode = m_currentBlock->at(i);
 155             if (otherNode->op() != JSConstant)
 156                 continue;
 157
 158             if (otherNode->constantNumber() != node->constantNumber())
 159                 continue;
 160
 161             return otherNode;
 162         }
 163         return 0;
 164     }
 165
 166     Node* weakConstantCSE(Node* node)
 167     {
 168         for (unsigned i = endIndexForPureCSE(); i--;) {
 169             Node* otherNode = m_currentBlock->at(i);
 170             if (otherNode->op() != WeakJSConstant)
 171                 continue;
 172
 173             if (otherNode->weakConstant() != node->weakConstant())
 174                 continue;
 175
 176             return otherNode;
 177         }
 178         return 0;
 179     }
 180
 181     Node* getCalleeLoadElimination(InlineCallFrame* inlineCallFrame)
 182     {
 183         for (unsigned i = m_indexInBlock; i--;) {
 184             Node* node = m_currentBlock->at(i);
 185             if (node->codeOrigin.inlineCallFrame != inlineCallFrame)
 186                 continue;
 187             switch (node->op()) {
 188             case GetCallee:
 189                 return node;
 190             case SetCallee:
 191                 return node->child1().node();
 192             default:
 193                 break;
 194             }
 195         }
 196         return 0;
 197     }
 198
 199     Node* getArrayLengthElimination(Node* array)
 200     {
 201         for (unsigned i = m_indexInBlock; i--;) {
 202             Node* node = m_currentBlock->at(i);
 203             switch (node->op()) {
 204             case GetArrayLength:
 205                 if (node->child1() == array)
 206                     return node;
 207                 break;
 208
 209             case PutByVal:
 210                 if (!m_graph.byValIsPure(node))
 211                     return 0;
 212                 if (node->arrayMode().mayStoreToHole())
 213                     return 0;
 214                 break;
 215
 216             default:
 217                 if (m_graph.clobbersWorld(node))
 218                     return 0;
 219             }
 220         }
 221         return 0;
 222     }
 223
 224     Node* globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
 225     {
 226         for (unsigned i = m_indexInBlock; i--;) {
 227             Node* node = m_currentBlock->at(i);
 228             switch (node->op()) {
 229             case GetGlobalVar:
 230                 if (node->registerPointer() == registerPointer)
 231                     return node;
 232                 break;
 233             case PutGlobalVar:
 234                 if (node->registerPointer() == registerPointer)
 235                     return node->child1().node();
 236                 break;
 237             default:
 238                 break;
 239             }
 240             if (m_graph.clobbersWorld(node))
 241                 break;
 242         }
 243         return 0;
 244     }
 245
 246     Node* scopedVarLoadElimination(Node* registers, unsigned varNumber)
 247     {
 248         for (unsigned i = m_indexInBlock; i--;) {
 249             Node* node = m_currentBlock->at(i);
 250             switch (node->op()) {
 251             case GetScopedVar: {
 252                 if (node->child1() == registers && node->varNumber() == varNumber)
 253                     return node;
 254                 break;
 255             }
 256             case PutScopedVar: {
 257                 if (node->child2() == registers && node->varNumber() == varNumber)
 258                     return node->child3().node();
 259                 break;
 260             }
 261             case SetLocal: {
 262                 VariableAccessData* variableAccessData = node->variableAccessData();
 263                 if (variableAccessData->isCaptured()
 264                     && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
 265                     return 0;
 266                 break;
 267             }
 268             default:
 269                 break;
 270             }
 271             if (m_graph.clobbersWorld(node))
 272                 break;
 273         }
 274         return 0;
 275     }
 276
 277     bool globalVarWatchpointElimination(WriteBarrier<Unknown>* registerPointer)
 278     {
 279         for (unsigned i = m_indexInBlock; i--;) {
 280             Node* node = m_currentBlock->at(i);
 281             switch (node->op()) {
 282             case GlobalVarWatchpoint:
 283                 if (node->registerPointer() == registerPointer)
 284                     return true;
 285                 break;
 286             case PutGlobalVar:
 287                 if (node->registerPointer() == registerPointer)
 288                     return false;
 289                 break;
 290             default:
 291                 break;
 292             }
 293             if (m_graph.clobbersWorld(node))
 294                 break;
 295         }
 296         return false;
 297     }
 298
 299     Node* globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
 300     {
 301         for (unsigned i = m_indexInBlock; i--;) {
 302             Node* node = m_currentBlock->at(i);
 303             switch (node->op()) {
 304             case PutGlobalVar:
 305             case PutGlobalVarCheck:
 306                 if (node->registerPointer() == registerPointer)
 307                     return node;
 308                 break;
 309
 310             case GetGlobalVar:
 311                 if (node->registerPointer() == registerPointer)
 312                     return 0;
 313                 break;
 314
 315             default:
 316                 break;
 317             }
 318             if (m_graph.clobbersWorld(node) || node->canExit())
 319                 return 0;
 320         }
 321         return 0;
 322     }
 323
 324     Node* scopedVarStoreElimination(Node* scope, Node* registers, unsigned varNumber)
 325     {
 326         for (unsigned i = m_indexInBlock; i--;) {
 327             Node* node = m_currentBlock->at(i);
 328             switch (node->op()) {
 329             case PutScopedVar: {
 330                 if (node->child1() == scope && node->child2() == registers && node->varNumber() == varNumber)
 331                     return node;
 332                 break;
 333             }
 334
 335             case GetScopedVar: {
 336                 // Let's be conservative.
 337                 if (node->varNumber() == varNumber)
 338                     return 0;
 339                 break;
 340             }
 341
 342             case GetLocal: {
 343                 VariableAccessData* variableAccessData = node->variableAccessData();
 344                 if (variableAccessData->isCaptured()
 345                     && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
 346                     return 0;
 347                 break;
 348             }
 349
 350             default:
 351                 break;
 352             }
 353             if (m_graph.clobbersWorld(node) || node->canExit())
 354                 return 0;
 355         }
 356         return 0;
 357     }
 358
 359     Node* getByValLoadElimination(Node* child1, Node* child2)
 360     {
 361         for (unsigned i = m_indexInBlock; i--;) {
 362             Node* node = m_currentBlock->at(i);
 363             if (node == child1 || node == canonicalize(child2))
 364                 break;
 365
 366             switch (node->op()) {
 367             case GetByVal:
 368                 if (!m_graph.byValIsPure(node))
 369                     return 0;
 370                 if (node->child1() == child1 && canonicalize(node->child2()) == canonicalize(child2))
 371                     return node;
 372                 break;
 373             case PutByVal:
 374             case PutByValAlias: {
 375                 if (!m_graph.byValIsPure(node))
 376                     return 0;
 377                 if (m_graph.varArgChild(node, 0) == child1 && canonicalize(m_graph.varArgChild(node, 1)) == canonicalize(child2))
 378                     return m_graph.varArgChild(node, 2).node();
 379                 // We must assume that the PutByVal will clobber the location we're getting from.
 380                 // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
 381                 // different type than the GetByVal, then we know that they won't clobber each other.
 382                 // ... except of course for typed arrays, where all typed arrays clobber all other
 383                 // typed arrays!  An Int32Array can alias a Float64Array for example, and so on.
 384                 return 0;
 385             }
 386             case PutStructure:
 387             case PutByOffset:
 388                 // GetByVal currently always speculates that it's accessing an
 389                 // array with an integer index, which means that it's impossible
 390                 // for a structure change or a put to property storage to affect
 391                 // the GetByVal.
 392                 break;
 393             default:
 394                 if (m_graph.clobbersWorld(node))
 395                     return 0;
 396                 break;
 397             }
 398         }
 399         return 0;
 400     }
 401
 402     bool checkFunctionElimination(JSCell* function, Node* child1)
 403     {
 404         for (unsigned i = endIndexForPureCSE(); i--;) {
 405             Node* node = m_currentBlock->at(i);
 406             if (node == child1)
 407                 break;
 408
 409             if (node->op() == CheckFunction && node->child1() == child1 && node->function() == function)
 410                 return true;
 411         }
 412         return false;
 413     }
 414
 415     bool checkExecutableElimination(ExecutableBase* executable, Node* child1)
 416     {
 417         for (unsigned i = endIndexForPureCSE(); i--;) {
 418             Node* node = m_currentBlock->at(i);
 419             if (node == child1)
 420                 break;
 421
 422             if (node->op() == CheckExecutable && node->child1() == child1 && node->executable() == executable)
 423                 return true;
 424         }
 425         return false;
 426     }
 427
 428     bool checkStructureElimination(const StructureSet& structureSet, Node* child1)
 429     {
 430         for (unsigned i = m_indexInBlock; i--;) {
 431             Node* node = m_currentBlock->at(i);
 432             if (node == child1)
 433                 break;
 434
 435             switch (node->op()) {
 436             case CheckStructure:
 437             case ForwardCheckStructure:
 438                 if (node->child1() == child1
 439                     && structureSet.isSupersetOf(node->structureSet()))
 440                     return true;
 441                 break;
 442
 443             case StructureTransitionWatchpoint:
 444             case ForwardStructureTransitionWatchpoint:
 445                 if (node->child1() == child1
 446                     && structureSet.contains(node->structure()))
 447                     return true;
 448                 break;
 449
 450             case PutStructure:
 451                 if (node->child1() == child1
 452                     && structureSet.contains(node->structureTransitionData().newStructure))
 453                     return true;
 454                 if (structureSet.contains(node->structureTransitionData().previousStructure))
 455                     return false;
 456                 break;
 457
 458             case PutByOffset:
 459                 // Setting a property cannot change the structure.
 460                 break;
 461
 462             case PutByVal:
 463             case PutByValAlias:
 464                 if (m_graph.byValIsPure(node)) {
 465                     // If PutByVal speculates that it's accessing an array with an
 466                     // integer index, then it's impossible for it to cause a structure
 467                     // change.
 468                     break;
 469                 }
 470                 return false;
 471
 472             case Arrayify:
 473             case ArrayifyToStructure:
 474                 // We could check if the arrayification could affect our structures.
 475                 // But that seems like it would take Effort.
 476                 return false;
 477
 478             default:
 479                 if (m_graph.clobbersWorld(node))
 480                     return false;
 481                 break;
 482             }
 483         }
 484         return false;
 485     }
 486
 487     bool structureTransitionWatchpointElimination(Structure* structure, Node* child1)
 488     {
 489         for (unsigned i = m_indexInBlock; i--;) {
 490             Node* node = m_currentBlock->at(i);
 491             if (node == child1)
 492                 break;
 493
 494             switch (node->op()) {
 495             case CheckStructure:
 496             case ForwardCheckStructure:
 497                 if (node->child1() == child1
 498                     && node->structureSet().containsOnly(structure))
 499                     return true;
 500                 break;
 501
 502             case PutStructure:
 503                 ASSERT(node->structureTransitionData().previousStructure != structure);
 504                 break;
 505
 506             case PutByOffset:
 507                 // Setting a property cannot change the structure.
 508                 break;
 509
 510             case PutByVal:
 511             case PutByValAlias:
 512                 if (m_graph.byValIsPure(node)) {
 513                     // If PutByVal speculates that it's accessing an array with an
 514                     // integer index, then it's impossible for it to cause a structure
 515                     // change.
 516                     break;
 517                 }
 518                 return false;
 519
 520             case StructureTransitionWatchpoint:
 521             case ForwardStructureTransitionWatchpoint:
 522                 if (node->structure() == structure && node->child1() == child1)
 523                     return true;
 524                 break;
 525
 526             case Arrayify:
 527             case ArrayifyToStructure:
 528                 // We could check if the arrayification could affect our structures.
 529                 // But that seems like it would take Effort.
 530                 return false;
 531
 532             default:
 533                 if (m_graph.clobbersWorld(node))
 534                     return false;
 535                 break;
 536             }
 537         }
 538         return false;
 539     }
 540
 541     Node* putStructureStoreElimination(Node* child1)
 542     {
 543         for (unsigned i = m_indexInBlock; i--;) {
 544             Node* node = m_currentBlock->at(i);
 545             if (node == child1)
 546                 break;
 547             switch (node->op()) {
 548             case CheckStructure:
 549             case ForwardCheckStructure:
 550                 return 0;
 551
 552             case PhantomPutStructure:
 553                 if (node->child1() == child1) // No need to retrace our steps.
 554                     return 0;
 555                 break;
 556
 557             case PutStructure:
 558                 if (node->child1() == child1)
 559                     return node;
 560                 break;
 561
 562             // PutStructure needs to execute if we GC. Hence this needs to
 563             // be careful with respect to nodes that GC.
 564             case CreateArguments:
 565             case TearOffArguments:
 566             case NewFunctionNoCheck:
 567             case NewFunction:
 568             case NewFunctionExpression:
 569             case CreateActivation:
 570             case TearOffActivation:
 571             case ToPrimitive:
 572             case NewRegexp:
 573             case NewArrayBuffer:
 574             case NewArray:
 575             case NewObject:
 576             case CreateThis:
 577             case AllocatePropertyStorage:
 578             case ReallocatePropertyStorage:
 579             case TypeOf:
 580             case ToString:
 581             case NewStringObject:
 582             case MakeRope:
 583                 return 0;
 584
 585             case GetIndexedPropertyStorage:
 586                 if (node->arrayMode().getIndexedPropertyStorageMayTriggerGC())
 587                     return 0;
 588                 break;
 589
 590             default:
 591                 break;
 592             }
 593             if (m_graph.clobbersWorld(node) || node->canExit())
 594                 return 0;
 595         }
 596         return 0;
 597     }
 598
 599     Node* getByOffsetLoadElimination(unsigned identifierNumber, Node* child1)
 600     {
 601         for (unsigned i = m_indexInBlock; i--;) {
 602             Node* node = m_currentBlock->at(i);
 603             if (node == child1)
 604                 break;
 605
 606             switch (node->op()) {
 607             case GetByOffset:
 608                 if (node->child1() == child1
 609                     && m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
 610                     return node;
 611                 break;
 612
 613             case PutByOffset:
 614                 if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
 615                     if (node->child1() == child1) // Must be same property storage.
 616                         return node->child3().node();
 617                     return 0;
 618                 }
 619                 break;
 620
 621             case PutStructure:
 622                 // Changing the structure cannot change the outcome of a property get.
 623                 break;
 624
 625             case PutByVal:
 626             case PutByValAlias:
 627                 if (m_graph.byValIsPure(node)) {
 628                     // If PutByVal speculates that it's accessing an array with an
 629                     // integer index, then it's impossible for it to cause a structure
 630                     // change.
 631                     break;
 632                 }
 633                 return 0;
 634
 635             default:
 636                 if (m_graph.clobbersWorld(node))
 637                     return 0;
 638                 break;
 639             }
 640         }
 641         return 0;
 642     }
 643
 644     Node* putByOffsetStoreElimination(unsigned identifierNumber, Node* child1)
 645     {
 646         for (unsigned i = m_indexInBlock; i--;) {
 647             Node* node = m_currentBlock->at(i);
 648             if (node == child1)
 649                 break;
 650
 651             switch (node->op()) {
 652             case GetByOffset:
 653                 if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
 654                     return 0;
 655                 break;
 656
 657             case PutByOffset:
 658                 if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
 659                     if (node->child1() == child1) // Must be same property storage.
 660                         return node;
 661                     return 0;
 662                 }
 663                 break;
 664
 665             case PutByVal:
 666             case PutByValAlias:
 667             case GetByVal:
 668                 if (m_graph.byValIsPure(node)) {
 669                     // If PutByVal speculates that it's accessing an array with an
 670                     // integer index, then it's impossible for it to cause a structure
 671                     // change.
 672                     break;
 673                 }
 674                 return 0;
 675
 676             default:
 677                 if (m_graph.clobbersWorld(node))
 678                     return 0;
 679                 break;
 680             }
 681             if (node->canExit())
 682                 return 0;
 683         }
 684         return 0;
 685     }
 686
 687     Node* getPropertyStorageLoadElimination(Node* child1)
 688     {
 689         for (unsigned i = m_indexInBlock; i--;) {
 690             Node* node = m_currentBlock->at(i);
 691             if (node == child1)
 692                 break;
 693
 694             switch (node->op()) {
 695             case GetButterfly:
 696                 if (node->child1() == child1)
 697                     return node;
 698                 break;
 699
 700             case AllocatePropertyStorage:
 701             case ReallocatePropertyStorage:
 702                 // If we can cheaply prove this is a change to our object's storage, we
 703                 // can optimize and use its result.
 704                 if (node->child1() == child1)
 705                     return node;
 706                 // Otherwise, we currently can't prove that this doesn't change our object's
 707                 // storage, so we conservatively assume that it may change the storage
 708                 // pointer of any object, including ours.
 709                 return 0;
 710
 711             case PutByOffset:
 712             case PutStructure:
 713                 // Changing the structure or putting to the storage cannot
 714                 // change the property storage pointer.
 715                 break;
 716
 717             case PutByVal:
 718             case PutByValAlias:
 719                 if (m_graph.byValIsPure(node)) {
 720                     // If PutByVal speculates that it's accessing an array with an
 721                     // integer index, then it's impossible for it to cause a structure
 722                     // change.
 723                     break;
 724                 }
 725                 return 0;
 726
 727             case Arrayify:
 728             case ArrayifyToStructure:
 729                 // We could check if the arrayification could affect our butterfly.
 730                 // But that seems like it would take Effort.
 731                 return 0;
 732
 733             default:
 734                 if (m_graph.clobbersWorld(node))
 735                     return 0;
 736                 break;
 737             }
 738         }
 739         return 0;
 740     }
 741
 742     bool checkArrayElimination(Node* child1, ArrayMode arrayMode)
 743     {
 744         for (unsigned i = m_indexInBlock; i--;) {
 745             Node* node = m_currentBlock->at(i);
 746             if (node == child1)
 747                 break;
 748
 749             switch (node->op()) {
 750             case PutByOffset:
 751             case PutStructure:
 752                 // Changing the structure or putting to the storage cannot
 753                 // change the property storage pointer.
 754                 break;
 755
 756             case CheckArray:
 757                 if (node->child1() == child1 && node->arrayMode() == arrayMode)
 758                     return true;
 759                 break;
 760
 761             case Arrayify:
 762             case ArrayifyToStructure:
 763                 // We could check if the arrayification could affect our array.
 764                 // But that seems like it would take Effort.
 765                 return false;
 766
 767             default:
 768                 if (m_graph.clobbersWorld(node))
 769                     return false;
 770                 break;
 771             }
 772         }
 773         return false;
 774     }
 775
 776     Node* getIndexedPropertyStorageLoadElimination(Node* child1, ArrayMode arrayMode)
 777     {
 778         for (unsigned i = m_indexInBlock; i--;) {
 779             Node* node = m_currentBlock->at(i);
 780             if (node == child1)
 781                 break;
 782
 783             switch (node->op()) {
 784             case GetIndexedPropertyStorage: {
 785                 if (node->child1() == child1 && node->arrayMode() == arrayMode)
 786                     return node;
 787                 break;
 788             }
 789
 790             case PutByOffset:
 791             case PutStructure:
 792                 // Changing the structure or putting to the storage cannot
 793                 // change the property storage pointer.
 794                 break;
 795
 796             default:
 797                 if (m_graph.clobbersWorld(node))
 798                     return 0;
 799                 break;
 800             }
 801         }
 802         return 0;
 803     }
 804
 805     Node* getMyScopeLoadElimination(InlineCallFrame* inlineCallFrame)
 806     {
 807         for (unsigned i = m_indexInBlock; i--;) {
 808             Node* node = m_currentBlock->at(i);
 809             if (node->codeOrigin.inlineCallFrame != inlineCallFrame)
 810                 continue;
 811             switch (node->op()) {
 812             case CreateActivation:
 813                 // This may cause us to return a different scope.
 814                 return 0;
 815             case GetMyScope:
 816                 return node;
 817             case SetMyScope:
 818                 return node->child1().node();
 819             default:
 820                 break;
 821             }
 822         }
 823         return 0;
 824     }
 825
 826     Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)
 827     {
 828         relevantLocalOp = 0;
 829
 830         for (unsigned i = m_indexInBlock; i--;) {
 831             Node* node = m_currentBlock->at(i);
 832             switch (node->op()) {
 833             case GetLocal:
 834                 if (node->local() == local) {
 835                     relevantLocalOp = node;
 836                     return node;
 837                 }
 838                 break;
 839
 840             case GetLocalUnlinked:
 841                 if (node->unlinkedLocal() == local) {
 842                     relevantLocalOp = node;
 843                     return node;
 844                 }
 845                 break;
 846
 847             case SetLocal:
 848                 if (node->local() == local) {
 849                     relevantLocalOp = node;
 850                     return node->child1().node();
 851                 }
 852                 break;
 853
 854             case PutScopedVar:
 855                 if (static_cast<VirtualRegister>(node->varNumber()) == local)
 856                     return 0;
 857                 break;
 858
 859             default:
 860                 if (careAboutClobbering && m_graph.clobbersWorld(node))
 861                     return 0;
 862                 break;
 863             }
 864         }
 865         return 0;
 866     }
 867
 868     struct SetLocalStoreEliminationResult {
 869         SetLocalStoreEliminationResult()
 870             : mayBeAccessed(false)
 871             , mayExit(false)
 872             , mayClobberWorld(false)
 873         {
 874         }
 875
 876         bool mayBeAccessed;
 877         bool mayExit;
 878         bool mayClobberWorld;
 879     };
 880     SetLocalStoreEliminationResult setLocalStoreElimination(
 881         VirtualRegister local, Node* expectedNode)
 882     {
 883         SetLocalStoreEliminationResult result;
 884         for (unsigned i = m_indexInBlock; i--;) {
 885             Node* node = m_currentBlock->at(i);
 886             switch (node->op()) {
 887             case GetLocal:
 888             case Flush:
 889                 if (node->local() == local)
 890                     result.mayBeAccessed = true;
 891                 break;
 892
 893             case GetLocalUnlinked:
 894                 if (node->unlinkedLocal() == local)
 895                     result.mayBeAccessed = true;
 896                 break;
 897
 898             case SetLocal: {
 899                 if (node->local() != local)
 900                     break;
 901                 if (node != expectedNode)
 902                     result.mayBeAccessed = true;
 903                 return result;
 904             }
 905
 906             case GetScopedVar:
 907                 if (static_cast<VirtualRegister>(node->varNumber()) == local)
 908                     result.mayBeAccessed = true;
 909                 break;
 910
 911             case GetMyScope:
 912             case SkipTopScope:
 913                 if (m_graph.uncheckedActivationRegisterFor(node->codeOrigin) == local)
 914                     result.mayBeAccessed = true;
 915                 break;
 916
 917             case CheckArgumentsNotCreated:
 918             case GetMyArgumentsLength:
 919             case GetMyArgumentsLengthSafe:
 920                 if (m_graph.uncheckedArgumentsRegisterFor(node->codeOrigin) == local)
 921                     result.mayBeAccessed = true;
 922                 break;
 923
 924             case GetMyArgumentByVal:
 925             case GetMyArgumentByValSafe:
 926                 result.mayBeAccessed = true;
 927                 break;
 928
 929             case GetByVal:
 930                 // If this is accessing arguments then it's potentially accessing locals.
 931                 if (node->arrayMode().type() == Array::Arguments)
 932                     result.mayBeAccessed = true;
 933                 break;
 934
 935             case CreateArguments:
 936             case TearOffActivation:
 937             case TearOffArguments:
 938                 // If an activation is being torn off then it means that captured variables
 939                 // are live. We could be clever here and check if the local qualifies as an
 940                 // argument register. But that seems like it would buy us very little since
 941                 // any kind of tear offs are rare to begin with.
 942                 result.mayBeAccessed = true;
 943                 break;
 944
 945             default:
 946                 break;
 947             }
 948             result.mayExit |= node->canExit();
 949             result.mayClobberWorld |= m_graph.clobbersWorld(node);
 950         }
 951         RELEASE_ASSERT_NOT_REACHED();
 952         // Be safe in release mode.
 953         result.mayBeAccessed = true;
 954         return result;
 955     }
 956
 957     void eliminateIrrelevantPhantomChildren(Node* node)
 958     {
 959         ASSERT(node->op() == Phantom);
 960         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
 961             Edge edge = node->children.child(i);
 962             if (!edge)
 963                 continue;
 964             if (edge.useKind() != UntypedUse)
 965                 continue; // Keep the type check.
 966             if (edge->flags() & NodeRelevantToOSR)
 967                 continue;
 968
 969 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 970             dataLog("   Eliminating edge @", m_currentNode->index(), " -> @", edge->index());
 971 #endif
 972             node->children.removeEdge(i--);
 973             m_changed = true;
 974         }
 975     }
 976
 977     bool setReplacement(Node* replacement)
 978     {
 979         if (!replacement)
 980             return false;
 981
 982 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 983         dataLogF("   Replacing @%u -> @%u", m_currentNode->index(), replacement->index());
 984 #endif
 985
 986         m_currentNode->convertToPhantom();
 987         eliminateIrrelevantPhantomChildren(m_currentNode);
 988
 989         // At this point we will eliminate all references to this node.
 990         m_currentNode->replacement = replacement;
 991
 992         m_changed = true;
 993
 994         return true;
 995     }
 996
 997     void eliminate()
 998     {
 999 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1000         dataLogF("   Eliminating @%u", m_currentNode->index());
1001 #endif
1002
1003         ASSERT(m_currentNode->mustGenerate());
1004         m_currentNode->convertToPhantom();
1005         eliminateIrrelevantPhantomChildren(m_currentNode);
1006
1007         m_changed = true;
1008     }
1009
1010     void eliminate(Node* node, NodeType phantomType = Phantom)
1011     {
1012         if (!node)
1013             return;
1014         ASSERT(node->mustGenerate());
1015         node->setOpAndDefaultNonExitFlags(phantomType);
1016         if (phantomType == Phantom)
1017             eliminateIrrelevantPhantomChildren(node);
1018
1019         m_changed = true;
1020     }
1021
1022     void performNodeCSE(Node* node)
1023     {
1024         if (cseMode == NormalCSE)
1025             m_graph.performSubstitution(node);
1026
1027         if (node->op() == SetLocal)
1028             node->child1()->mergeFlags(NodeRelevantToOSR);
1029
1030 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1031         dataLogF("   %s @%u: ", Graph::opName(node->op()), node->index());
1032 #endif
1033
1034         // NOTE: there are some nodes that we deliberately don't CSE even though we
1035         // probably could, like MakeRope and ToPrimitive. That's because there is no
1036         // evidence that doing CSE on these nodes would result in a performance
1037         // progression. Hence considering these nodes in CSE would just mean that this
1038         // code does more work with no win. Of course, we may want to reconsider this,
1039         // since MakeRope is trivially CSE-able. It's not trivially doable for
1040         // ToPrimitive, but we could change that with some speculations if we really
1041         // needed to.
1042
1043         switch (node->op()) {
1044
1045         case Identity:
1046             if (cseMode == StoreElimination)
1047                 break;
1048             setReplacement(node->child1().node());
1049             break;
1050
1051         // Handle the pure nodes. These nodes never have any side-effects.
1052         case BitAnd:
1053         case BitOr:
1054         case BitXor:
1055         case BitRShift:
1056         case BitLShift:
1057         case BitURShift:
1058         case ArithAdd:
1059         case ArithSub:
1060         case ArithNegate:
1061         case ArithMul:
1062         case ArithIMul:
1063         case ArithMod:
1064         case ArithDiv:
1065         case ArithAbs:
1066         case ArithMin:
1067         case ArithMax:
1068         case ArithSqrt:
1069         case StringCharAt:
1070         case StringCharCodeAt:
1071         case IsUndefined:
1072         case IsBoolean:
1073         case IsNumber:
1074         case IsString:
1075         case IsObject:
1076         case IsFunction:
1077         case DoubleAsInt32:
1078         case LogicalNot:
1079         case SkipTopScope:
1080         case SkipScope:
1081         case GetScopeRegisters:
1082         case GetScope:
1083         case TypeOf:
1084         case CompareEqConstant:
1085         case ValueToInt32:
1086             if (cseMode == StoreElimination)
1087                 break;
1088             setReplacement(pureCSE(node));
1089             break;
1090
1091         case Int32ToDouble:
1092         case ForwardInt32ToDouble:
1093             if (cseMode == StoreElimination)
1094                 break;
1095             setReplacement(int32ToDoubleCSE(node));
1096             break;
1097
1098         case GetCallee:
1099             if (cseMode == StoreElimination)
1100                 break;
1101             setReplacement(getCalleeLoadElimination(node->codeOrigin.inlineCallFrame));
1102             break;
1103
1104         case GetLocal: {
1105             if (cseMode == StoreElimination)
1106                 break;
1107             VariableAccessData* variableAccessData = node->variableAccessData();
1108             if (!variableAccessData->isCaptured())
1109                 break;
1110             Node* relevantLocalOp;
1111             Node* possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
1112             if (!relevantLocalOp)
1113                 break;
1114             if (relevantLocalOp->op() != GetLocalUnlinked
1115                 && relevantLocalOp->variableAccessData() != variableAccessData)
1116                 break;
1117             Node* phi = node->child1().node();
1118             if (!setReplacement(possibleReplacement))
1119                 break;
1120
1121             m_graph.dethread();
1122
1123             // If we replace a GetLocal with a GetLocalUnlinked, then turn the GetLocalUnlinked
1124             // into a GetLocal.
1125             if (relevantLocalOp->op() == GetLocalUnlinked)
1126                 relevantLocalOp->convertToGetLocal(variableAccessData, phi);
1127
1128             m_changed = true;
1129             break;
1130         }
1131
1132         case GetLocalUnlinked: {
1133             if (cseMode == StoreElimination)
1134                 break;
1135             Node* relevantLocalOpIgnored;
1136             setReplacement(getLocalLoadElimination(node->unlinkedLocal(), relevantLocalOpIgnored, true));
1137             break;
1138         }
1139
1140         case Flush: {
1141             VariableAccessData* variableAccessData = node->variableAccessData();
1142             VirtualRegister local = variableAccessData->local();
1143             Node* replacement = node->child1().node();
1144             if (replacement->op() != SetLocal)
1145                 break;
1146             ASSERT(replacement->variableAccessData() == variableAccessData);
1147             // FIXME: We should be able to remove SetLocals that can exit; we just need
1148             // to replace them with appropriate type checks.
1149             if (cseMode == NormalCSE) {
1150                 // Need to be conservative at this time; if the SetLocal has any chance of performing
1151                 // any speculations then we cannot do anything.
1152                 if (variableAccessData->isCaptured()) {
1153                     // Captured SetLocals never speculate and hence never exit.
1154                 } else {
1155                     if (variableAccessData->shouldUseDoubleFormat())
1156                         break;
1157                     SpeculatedType prediction = variableAccessData->argumentAwarePrediction();
1158                     if (isInt32Speculation(prediction))
1159                         break;
1160                     if (isArraySpeculation(prediction))
1161                         break;
1162                     if (isBooleanSpeculation(prediction))
1163                         break;
1164                 }
1165             } else {
1166                 if (replacement->canExit())
1167                     break;
1168             }
1169             SetLocalStoreEliminationResult result =
1170                 setLocalStoreElimination(local, replacement);
1171             if (result.mayBeAccessed || result.mayClobberWorld)
1172                 break;
1173             ASSERT(replacement->op() == SetLocal);
1174             // FIXME: Investigate using mayExit as a further optimization.
1175             node->convertToPhantom();
1176             Node* dataNode = replacement->child1().node();
1177             ASSERT(dataNode->hasResult());
1178             m_graph.clearAndDerefChild1(node);
1179             node->children.child1() = Edge(dataNode);
1180             m_graph.dethread();
1181             m_changed = true;
1182             break;
1183         }
1184
1185         case JSConstant:
1186             if (cseMode == StoreElimination)
1187                 break;
1188             // This is strange, but necessary. Some phases will convert nodes to constants,
1189             // which may result in duplicated constants. We use CSE to clean this up.
1190             setReplacement(constantCSE(node));
1191             break;
1192
1193         case WeakJSConstant:
1194             if (cseMode == StoreElimination)
1195                 break;
1196             // FIXME: have CSE for weak constants against strong constants and vice-versa.
1197             setReplacement(weakConstantCSE(node));
1198             break;
1199
1200         case GetArrayLength:
1201             if (cseMode == StoreElimination)
1202                 break;
1203             setReplacement(getArrayLengthElimination(node->child1().node()));
1204             break;
1205
1206         case GetMyScope:
1207             if (cseMode == StoreElimination)
1208                 break;
1209             setReplacement(getMyScopeLoadElimination(node->codeOrigin.inlineCallFrame));
1210             break;
1211
1212         // Handle nodes that are conditionally pure: these are pure, and can
1213         // be CSE'd, so long as the prediction is the one we want.
1214         case ValueAdd:
1215         case CompareLess:
1216         case CompareLessEq:
1217         case CompareGreater:
1218         case CompareGreaterEq:
1219         case CompareEq: {
1220             if (cseMode == StoreElimination)
1221                 break;
1222             if (m_graph.isPredictedNumerical(node)) {
1223                 Node* replacement = pureCSE(node);
1224                 if (replacement && m_graph.isPredictedNumerical(replacement))
1225                     setReplacement(replacement);
1226             }
1227             break;
1228         }
1229
1230         // Finally handle heap accesses. These are not quite pure, but we can still
1231         // optimize them provided that some subtle conditions are met.
1232         case GetGlobalVar:
1233             if (cseMode == StoreElimination)
1234                 break;
1235             setReplacement(globalVarLoadElimination(node->registerPointer()));
1236             break;
1237
1238         case GetScopedVar: {
1239             if (cseMode == StoreElimination)
1240                 break;
1241             setReplacement(scopedVarLoadElimination(node->child1().node(), node->varNumber()));
1242             break;
1243         }
1244
1245         case GlobalVarWatchpoint:
1246             if (cseMode == StoreElimination)
1247                 break;
1248             if (globalVarWatchpointElimination(node->registerPointer()))
1249                 eliminate();
1250             break;
1251
1252         case PutGlobalVar:
1253         case PutGlobalVarCheck:
1254             if (cseMode == NormalCSE)
1255                 break;
1256             eliminate(globalVarStoreElimination(node->registerPointer()));
1257             break;
1258
1259         case PutScopedVar: {
1260             if (cseMode == NormalCSE)
1261                 break;
1262             eliminate(scopedVarStoreElimination(node->child1().node(), node->child2().node(), node->varNumber()));
1263             break;
1264         }
1265
1266         case GetByVal:
1267             if (cseMode == StoreElimination)
1268                 break;
1269             if (m_graph.byValIsPure(node))
1270                 setReplacement(getByValLoadElimination(node->child1().node(), node->child2().node()));
1271             break;
1272
1273         case PutByVal: {
1274             if (cseMode == StoreElimination)
1275                 break;
1276             Edge child1 = m_graph.varArgChild(node, 0);
1277             Edge child2 = m_graph.varArgChild(node, 1);
1278             if (node->arrayMode().canCSEStorage()) {
1279                 Node* replacement = getByValLoadElimination(child1.node(), child2.node());
1280                 if (!replacement)
1281                     break;
1282                 node->setOp(PutByValAlias);
1283             }
1284             break;
1285         }
1286
1287         case CheckStructure:
1288         case ForwardCheckStructure:
1289             if (cseMode == StoreElimination)
1290                 break;
1291             if (checkStructureElimination(node->structureSet(), node->child1().node()))
1292                 eliminate();
1293             break;
1294
1295         case StructureTransitionWatchpoint:
1296         case ForwardStructureTransitionWatchpoint:
1297             if (cseMode == StoreElimination)
1298                 break;
1299             if (structureTransitionWatchpointElimination(node->structure(), node->child1().node()))
1300                 eliminate();
1301             break;
1302
1303         case PutStructure:
1304             if (cseMode == NormalCSE)
1305                 break;
1306             eliminate(putStructureStoreElimination(node->child1().node()), PhantomPutStructure);
1307             break;
1308
1309         case CheckFunction:
1310             if (cseMode == StoreElimination)
1311                 break;
1312             if (checkFunctionElimination(node->function(), node->child1().node()))
1313                 eliminate();
1314             break;
1315
1316         case CheckExecutable:
1317             if (cseMode == StoreElimination)
1318                 break;
1319             if (checkExecutableElimination(node->executable(), node->child1().node()))
1320                 eliminate();
1321             break;
1322
1323         case CheckArray:
1324             if (cseMode == StoreElimination)
1325                 break;
1326             if (checkArrayElimination(node->child1().node(), node->arrayMode()))
1327                 eliminate();
1328             break;
1329
1330         case GetIndexedPropertyStorage: {
1331             if (cseMode == StoreElimination)
1332                 break;
1333             setReplacement(getIndexedPropertyStorageLoadElimination(node->child1().node(), node->arrayMode()));
1334             break;
1335         }
1336
1337         case GetButterfly:
1338             if (cseMode == StoreElimination)
1339                 break;
1340             setReplacement(getPropertyStorageLoadElimination(node->child1().node()));
1341             break;
1342
1343         case GetByOffset:
1344             if (cseMode == StoreElimination)
1345                 break;
1346             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child1().node()));
1347             break;
1348
1349         case PutByOffset:
1350             if (cseMode == NormalCSE)
1351                 break;
1352             eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child1().node()));
1353             break;
1354
1355         case Phantom:
1356             // FIXME: we ought to remove Phantom's that have no children.
1357
1358             eliminateIrrelevantPhantomChildren(node);
1359             break;
1360
1361         default:
1362             // do nothing.
1363             break;
1364         }
1365
1366         m_lastSeen[node->op()] = m_indexInBlock;
1367 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1368         dataLogF("\n");
1369 #endif
1370     }
1371
1372     void performBlockCSE(BasicBlock* block)
1373     {
1374         if (!block)
1375             return;
1376         if (!block->isReachable)
1377             return;
1378
1379         m_currentBlock = block;
1380         for (unsigned i = 0; i < LastNodeType; ++i)
1381             m_lastSeen[i] = UINT_MAX;
1382
1383         // All Phis need to already be marked as relevant to OSR, and have their
1384         // replacements cleared, so we don't get confused while doing substitutions on
1385         // GetLocal's.
1386         for (unsigned i = 0; i < block->phis.size(); ++i) {
1387             ASSERT(block->phis[i]->flags() & NodeRelevantToOSR);
1388             block->phis[i]->replacement = 0;
1389         }
1390
1391         // Make all of my SetLocal and GetLocal nodes relevant to OSR, and do some other
1392         // necessary bookkeeping.
1393         for (unsigned i = 0; i < block->size(); ++i) {
1394             Node* node = block->at(i);
1395
1396             node->replacement = 0;
1397
1398             switch (node->op()) {
1399             case SetLocal:
1400             case GetLocal: // FIXME: The GetLocal case is only necessary until we do https://bugs.webkit.org/show_bug.cgi?id=106707.
1401                 node->mergeFlags(NodeRelevantToOSR);
1402                 break;
1403             default:
1404                 node->clearFlags(NodeRelevantToOSR);
1405                 break;
1406             }
1407         }
1408
1409         for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
1410             m_currentNode = block->at(m_indexInBlock);
1411             performNodeCSE(m_currentNode);
1412         }
1413
1414         if (!ASSERT_DISABLED && cseMode == StoreElimination) {
1415             // Nobody should have replacements set.
1416             for (unsigned i = 0; i < block->size(); ++i)
1417                 ASSERT(!block->at(i)->replacement);
1418         }
1419     }
1420
1421     BasicBlock* m_currentBlock;
1422     Node* m_currentNode;
1423     unsigned m_indexInBlock;
1424     FixedArray<unsigned, LastNodeType> m_lastSeen;
1425     bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
1426 };
1427
1428 bool performCSE(Graph& graph)
1429 {
1430     SamplingRegion samplingRegion("DFG CSE Phase");
1431     return runPhase<CSEPhase<NormalCSE> >(graph);
1432 }
1433
1434 bool performStoreElimination(Graph& graph)
1435 {
1436     SamplingRegion samplingRegion("DFG Store Elimination Phase");
1437     return runPhase<CSEPhase<StoreElimination> >(graph);
1438 }
1439
1440 } } // namespace JSC::DFG
1441
1442 #endif // ENABLE(DFG_JIT)
1443
1444