Source/JavaScriptCore/dfg/DFGCSEPhase.cpp

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