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