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