Source/JavaScriptCore/dfg/DFGCSEPhase.cpp

   1 /*
   2  * Copyright (C) 2011-2015 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 "DFGBlockMapInlines.h"
  33 #include "DFGClobberSet.h"
  34 #include "DFGClobberize.h"
  35 #include "DFGDominators.h"
  36 #include "DFGEdgeUsesStructure.h"
  37 #include "DFGGraph.h"
  38 #include "DFGPhase.h"
  39 #include "JSCInlines.h"
  40 #include <array>
  41
  42 namespace JSC { namespace DFG {
  43
  44 // This file contains two CSE implementations: local and global. LocalCSE typically runs when we're
  45 // in DFG mode, i.e. we want to compile quickly. LocalCSE contains a lot of optimizations for
  46 // compile time. GlobalCSE, on the other hand, is fairly straight-forward. It will find more
  47 // optimization opportunities by virtue of being global.
  48
  49 namespace {
  50
  51 namespace DFGCSEPhaseInternal {
  52 static const bool verbose = false;
  53 }
  54
  55 class ImpureDataSlot {
  56     WTF_MAKE_NONCOPYABLE(ImpureDataSlot);
  57     WTF_MAKE_FAST_ALLOCATED;
  58 public:
  59     ImpureDataSlot(HeapLocation key, LazyNode value, unsigned hash)
  60         : key(key), value(value), hash(hash)
  61     { }
  62
  63     HeapLocation key;
  64     LazyNode value;
  65     unsigned hash;
  66 };
  67
  68 struct ImpureDataSlotHash : public DefaultHash<std::unique_ptr<ImpureDataSlot>>::Hash {
  69     static unsigned hash(const std::unique_ptr<ImpureDataSlot>& key)
  70     {
  71         return key->hash;
  72     }
  73
  74     static bool equal(const std::unique_ptr<ImpureDataSlot>& a, const std::unique_ptr<ImpureDataSlot>& b)
  75     {
  76         // The ImpureDataSlot are unique per table per HeapLocation. This lets us compare the key
  77         // by just comparing the pointers of the unique ImpureDataSlots.
  78         ASSERT(a != b || a->key == b->key);
  79         return a == b;
  80     }
  81 };
  82
  83 struct ImpureDataTranslator {
  84     static unsigned hash(const HeapLocation& key)
  85     {
  86         return key.hash();
  87     }
  88
  89     static bool equal(const std::unique_ptr<ImpureDataSlot>& slot, const HeapLocation& key)
  90     {
  91         if (!slot)
  92             return false;
  93         if (HashTraits<std::unique_ptr<ImpureDataSlot>>::isDeletedValue(slot))
  94             return false;
  95         return slot->key == key;
  96     }
  97
  98     static void translate(std::unique_ptr<ImpureDataSlot>& slot, const HeapLocation& key, unsigned hashCode)
  99     {
 100         new (NotNull, std::addressof(slot)) std::unique_ptr<ImpureDataSlot>(new ImpureDataSlot {key, LazyNode(), hashCode});
 101     }
 102 };
 103
 104 class ImpureMap {
 105     WTF_MAKE_FAST_ALLOCATED;
 106     WTF_MAKE_NONCOPYABLE(ImpureMap);
 107 public:
 108     ImpureMap() = default;
 109
 110     ImpureMap(ImpureMap&& other)
 111     {
 112         m_abstractHeapStackMap.swap(other.m_abstractHeapStackMap);
 113         m_fallbackStackMap.swap(other.m_fallbackStackMap);
 114         m_heapMap.swap(other.m_heapMap);
 115 #if !defined(NDEBUG)
 116         m_debugImpureData.swap(other.m_debugImpureData);
 117 #endif
 118     }
 119
 120     const ImpureDataSlot* add(const HeapLocation& location, const LazyNode& node)
 121     {
 122         const ImpureDataSlot* result = addImpl(location, node);
 123
 124 #if !defined(NDEBUG)
 125         auto addResult = m_debugImpureData.add(location, node);
 126         ASSERT(!!result == !addResult.isNewEntry);
 127 #endif
 128         return result;
 129     }
 130
 131     LazyNode get(const HeapLocation& location) const
 132     {
 133         LazyNode result = getImpl(location);
 134 #if !defined(NDEBUG)
 135         ASSERT(result == m_debugImpureData.get(location));
 136 #endif
 137         return result;
 138     }
 139
 140     void clobber(AbstractHeap heap)
 141     {
 142         switch (heap.kind()) {
 143         case World: {
 144             clear();
 145             break;
 146         }
 147         case SideState:
 148             break;
 149         case Stack: {
 150             ASSERT(!heap.payload().isTop());
 151             ASSERT(heap.payload().value() == heap.payload().value32());
 152             m_abstractHeapStackMap.remove(heap.payload().value32());
 153             clobber(m_fallbackStackMap, heap);
 154             break;
 155         }
 156         default:
 157             clobber(m_heapMap, heap);
 158             break;
 159         }
 160 #if !defined(NDEBUG)
 161         m_debugImpureData.removeIf([heap](const HashMap<HeapLocation, LazyNode>::KeyValuePairType& pair) -> bool {
 162             return heap.overlaps(pair.key.heap());
 163         });
 164         ASSERT(m_debugImpureData.size()
 165             == (m_heapMap.size()
 166                 + m_abstractHeapStackMap.size()
 167                 + m_fallbackStackMap.size()));
 168
 169         const bool verifyClobber = false;
 170         if (verifyClobber) {
 171             for (auto& pair : m_debugImpureData)
 172                 ASSERT(!!get(pair.key));
 173         }
 174 #endif
 175     }
 176
 177     void clear()
 178     {
 179         m_abstractHeapStackMap.clear();
 180         m_fallbackStackMap.clear();
 181         m_heapMap.clear();
 182 #if !defined(NDEBUG)
 183         m_debugImpureData.clear();
 184 #endif
 185     }
 186
 187 private:
 188     typedef HashSet<std::unique_ptr<ImpureDataSlot>, ImpureDataSlotHash> Map;
 189
 190     const ImpureDataSlot* addImpl(const HeapLocation& location, const LazyNode& node)
 191     {
 192         switch (location.heap().kind()) {
 193         case World:
 194         case SideState:
 195             RELEASE_ASSERT_NOT_REACHED();
 196         case Stack: {
 197             AbstractHeap abstractHeap = location.heap();
 198             if (abstractHeap.payload().isTop())
 199                 return add(m_fallbackStackMap, location, node);
 200             ASSERT(abstractHeap.payload().value() == abstractHeap.payload().value32());
 201             auto addResult = m_abstractHeapStackMap.add(abstractHeap.payload().value32(), nullptr);
 202             if (addResult.isNewEntry) {
 203                 addResult.iterator->value.reset(new ImpureDataSlot {location, node, 0});
 204                 return nullptr;
 205             }
 206             if (addResult.iterator->value->key == location)
 207                 return addResult.iterator->value.get();
 208             return add(m_fallbackStackMap, location, node);
 209         }
 210         default:
 211             return add(m_heapMap, location, node);
 212         }
 213         return nullptr;
 214     }
 215
 216     LazyNode getImpl(const HeapLocation& location) const
 217     {
 218         switch (location.heap().kind()) {
 219         case World:
 220         case SideState:
 221             RELEASE_ASSERT_NOT_REACHED();
 222         case Stack: {
 223             ASSERT(location.heap().payload().value() == location.heap().payload().value32());
 224             auto iterator = m_abstractHeapStackMap.find(location.heap().payload().value32());
 225             if (iterator != m_abstractHeapStackMap.end()
 226                 && iterator->value->key == location)
 227                 return iterator->value->value;
 228             return get(m_fallbackStackMap, location);
 229         }
 230         default:
 231             return get(m_heapMap, location);
 232         }
 233         return LazyNode();
 234     }
 235
 236     static const ImpureDataSlot* add(Map& map, const HeapLocation& location, const LazyNode& node)
 237     {
 238         auto result = map.add<ImpureDataTranslator>(location);
 239         if (result.isNewEntry) {
 240             (*result.iterator)->value = node;
 241             return nullptr;
 242         }
 243         return result.iterator->get();
 244     }
 245
 246     static LazyNode get(const Map& map, const HeapLocation& location)
 247     {
 248         auto iterator = map.find<ImpureDataTranslator>(location);
 249         if (iterator != map.end())
 250             return (*iterator)->value;
 251         return LazyNode();
 252     }
 253
 254     static void clobber(Map& map, AbstractHeap heap)
 255     {
 256         map.removeIf([heap](const std::unique_ptr<ImpureDataSlot>& slot) -> bool {
 257             return heap.overlaps(slot->key.heap());
 258         });
 259     }
 260
 261     // The majority of Impure Stack Slotsare unique per value.
 262     // This is very useful for fast clobber(), we can just remove the slot addressed by AbstractHeap
 263     // in O(1).
 264     //
 265     // When there are conflict, any additional HeapLocation is added in the fallback map.
 266     // This works well because fallbackStackMap remains tiny.
 267     //
 268     // One cannot assume a unique ImpureData is in m_abstractHeapStackMap. It may have been
 269     // a duplicate in the past and now only live in m_fallbackStackMap.
 270     //
 271     // Obviously, TOP always goes into m_fallbackStackMap since it does not have a unique value.
 272     HashMap<int32_t, std::unique_ptr<ImpureDataSlot>, DefaultHash<int32_t>::Hash, WTF::SignedWithZeroKeyHashTraits<int32_t>> m_abstractHeapStackMap;
 273     Map m_fallbackStackMap;
 274
 275     Map m_heapMap;
 276
 277 #if !defined(NDEBUG)
 278     HashMap<HeapLocation, LazyNode> m_debugImpureData;
 279 #endif
 280 };
 281
 282 class LocalCSEPhase : public Phase {
 283 public:
 284     LocalCSEPhase(Graph& graph)
 285         : Phase(graph, "local common subexpression elimination")
 286         , m_smallBlock(graph)
 287         , m_largeBlock(graph)
 288     {
 289     }
 290
 291     bool run()
 292     {
 293         ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
 294         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == LoadStore);
 295
 296         bool changed = false;
 297
 298         m_graph.clearReplacements();
 299
 300         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 301             BasicBlock* block = m_graph.block(blockIndex);
 302             if (!block)
 303                 continue;
 304
 305             if (block->size() <= SmallMaps::capacity)
 306                 changed |= m_smallBlock.run(block);
 307             else
 308                 changed |= m_largeBlock.run(block);
 309         }
 310
 311         return changed;
 312     }
 313
 314 private:
 315     class SmallMaps {
 316     public:
 317         // This permits SmallMaps to be used for blocks that have up to 100 nodes. In practice,
 318         // fewer than half of the nodes in a block have pure defs, and even fewer have impure defs.
 319         // Thus, a capacity limit of 100 probably means that somewhere around ~40 things may end up
 320         // in one of these "small" list-based maps. That number still seems largeish, except that
 321         // the overhead of HashMaps can be quite high currently: clearing them, or even removing
 322         // enough things from them, deletes (or resizes) their backing store eagerly. Hence
 323         // HashMaps induce a lot of malloc traffic.
 324         static const unsigned capacity = 100;
 325
 326         SmallMaps()
 327             : m_pureLength(0)
 328             , m_impureLength(0)
 329         {
 330         }
 331
 332         void clear()
 333         {
 334             m_pureLength = 0;
 335             m_impureLength = 0;
 336         }
 337
 338         void write(AbstractHeap heap)
 339         {
 340             if (heap.kind() == SideState)
 341                 return;
 342
 343             for (unsigned i = 0; i < m_impureLength; ++i) {
 344                 if (heap.overlaps(m_impureMap[i].key.heap()))
 345                     m_impureMap[i--] = m_impureMap[--m_impureLength];
 346             }
 347         }
 348
 349         Node* addPure(PureValue value, Node* node)
 350         {
 351             for (unsigned i = m_pureLength; i--;) {
 352                 if (m_pureMap[i].key == value)
 353                     return m_pureMap[i].value;
 354             }
 355
 356             ASSERT(m_pureLength < capacity);
 357             m_pureMap[m_pureLength++] = WTF::KeyValuePair<PureValue, Node*>(value, node);
 358             return nullptr;
 359         }
 360
 361         LazyNode findReplacement(HeapLocation location)
 362         {
 363             for (unsigned i = m_impureLength; i--;) {
 364                 if (m_impureMap[i].key == location)
 365                     return m_impureMap[i].value;
 366             }
 367             return nullptr;
 368         }
 369
 370         LazyNode addImpure(HeapLocation location, LazyNode node)
 371         {
 372             // FIXME: If we are using small maps, we must not def() derived values.
 373             // For now the only derived values we def() are constant-based.
 374             if (location.index() && !location.index().isNode())
 375                 return nullptr;
 376             if (LazyNode result = findReplacement(location))
 377                 return result;
 378             ASSERT(m_impureLength < capacity);
 379             m_impureMap[m_impureLength++] = WTF::KeyValuePair<HeapLocation, LazyNode>(location, node);
 380             return nullptr;
 381         }
 382
 383     private:
 384         WTF::KeyValuePair<PureValue, Node*> m_pureMap[capacity];
 385         WTF::KeyValuePair<HeapLocation, LazyNode> m_impureMap[capacity];
 386         unsigned m_pureLength;
 387         unsigned m_impureLength;
 388     };
 389
 390     class LargeMaps {
 391     public:
 392         LargeMaps()
 393         {
 394         }
 395
 396         void clear()
 397         {
 398             m_pureMap.clear();
 399             m_impureMap.clear();
 400         }
 401
 402         void write(AbstractHeap heap)
 403         {
 404             m_impureMap.clobber(heap);
 405         }
 406
 407         Node* addPure(PureValue value, Node* node)
 408         {
 409             auto result = m_pureMap.add(value, node);
 410             if (result.isNewEntry)
 411                 return nullptr;
 412             return result.iterator->value;
 413         }
 414
 415         LazyNode findReplacement(HeapLocation location)
 416         {
 417             return m_impureMap.get(location);
 418         }
 419
 420         LazyNode addImpure(const HeapLocation& location, const LazyNode& node)
 421         {
 422             if (const ImpureDataSlot* slot = m_impureMap.add(location, node))
 423                 return slot->value;
 424             return LazyNode();
 425         }
 426
 427     private:
 428         HashMap<PureValue, Node*> m_pureMap;
 429         ImpureMap m_impureMap;
 430     };
 431
 432     template<typename Maps>
 433     class BlockCSE {
 434     public:
 435         BlockCSE(Graph& graph)
 436             : m_graph(graph)
 437             , m_insertionSet(graph)
 438         {
 439         }
 440
 441         bool run(BasicBlock* block)
 442         {
 443             m_maps.clear();
 444             m_changed = false;
 445             m_block = block;
 446
 447             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
 448                 m_node = block->at(nodeIndex);
 449                 m_graph.performSubstitution(m_node);
 450
 451                 if (m_node->op() == Identity || m_node->op() == IdentityWithProfile) {
 452                     m_node->replaceWith(m_node->child1().node());
 453                     m_changed = true;
 454                 } else {
 455                     // This rule only makes sense for local CSE, since in SSA form we have already
 456                     // factored the bounds check out of the PutByVal. It's kind of gross, but we
 457                     // still have reason to believe that PutByValAlias is a good optimization and
 458                     // that it's better to do it with a single node rather than separating out the
 459                     // CheckInBounds.
 460                     if (m_node->op() == PutByVal || m_node->op() == PutByValDirect) {
 461                         HeapLocation heap;
 462
 463                         Node* base = m_graph.varArgChild(m_node, 0).node();
 464                         Node* index = m_graph.varArgChild(m_node, 1).node();
 465                         LocationKind indexedPropertyLoc = indexedPropertyLocForResultType(m_node->result());
 466
 467                         ArrayMode mode = m_node->arrayMode();
 468                         switch (mode.type()) {
 469                         case Array::Int32:
 470                             if (!mode.isInBounds())
 471                                 break;
 472                             heap = HeapLocation(
 473                                 indexedPropertyLoc, IndexedInt32Properties, base, index);
 474                             break;
 475
 476                         case Array::Double:
 477                             if (!mode.isInBounds())
 478                                 break;
 479                             heap = HeapLocation(
 480                                 indexedPropertyLoc, IndexedDoubleProperties, base, index);
 481                             break;
 482
 483                         case Array::Contiguous:
 484                             if (!mode.isInBounds())
 485                                 break;
 486                             heap = HeapLocation(
 487                                 indexedPropertyLoc, IndexedContiguousProperties, base, index);
 488                             break;
 489
 490                         case Array::Int8Array:
 491                         case Array::Int16Array:
 492                         case Array::Int32Array:
 493                         case Array::Uint8Array:
 494                         case Array::Uint8ClampedArray:
 495                         case Array::Uint16Array:
 496                         case Array::Uint32Array:
 497                         case Array::Float32Array:
 498                         case Array::Float64Array:
 499                             if (!mode.isInBounds())
 500                                 break;
 501                             heap = HeapLocation(
 502                                 indexedPropertyLoc, TypedArrayProperties, base, index);
 503                             break;
 504
 505                         default:
 506                             break;
 507                         }
 508
 509                         if (!!heap && m_maps.findReplacement(heap))
 510                             m_node->setOp(PutByValAlias);
 511                     }
 512
 513                     clobberize(m_graph, m_node, *this);
 514                 }
 515             }
 516
 517             m_insertionSet.execute(block);
 518
 519             return m_changed;
 520         }
 521
 522         void read(AbstractHeap) { }
 523
 524         void write(AbstractHeap heap)
 525         {
 526             m_maps.write(heap);
 527         }
 528
 529         void def(PureValue value)
 530         {
 531             Node* match = m_maps.addPure(value, m_node);
 532             if (!match)
 533                 return;
 534
 535             m_node->replaceWith(match);
 536             m_changed = true;
 537         }
 538
 539         void def(const HeapLocation& location, const LazyNode& value)
 540         {
 541             LazyNode match = m_maps.addImpure(location, value);
 542             if (!match)
 543                 return;
 544
 545             if (m_node->op() == GetLocal) {
 546                 // Usually the CPS rethreading phase does this. But it's OK for us to mess with
 547                 // locals so long as:
 548                 //
 549                 // - We dethread the graph. Any changes we make may invalidate the assumptions of
 550                 //   our CPS form, particularly if this GetLocal is linked to the variablesAtTail.
 551                 //
 552                 // - We don't introduce a Phantom for the child of the GetLocal. This wouldn't be
 553                 //   totally wrong but it would pessimize the code. Just because there is a
 554                 //   GetLocal doesn't mean that the child was live. Simply rerouting the all uses
 555                 //   of this GetLocal will preserve the live-at-exit information just fine.
 556                 //
 557                 // We accomplish the latter by just clearing the child; then the Phantom that we
 558                 // introduce won't have children and so it will eventually just be deleted.
 559
 560                 m_node->child1() = Edge();
 561                 m_graph.dethread();
 562             }
 563
 564             if (value.isNode() && value.asNode() == m_node) {
 565                 match.ensureIsNode(m_insertionSet, m_block, 0)->owner = m_block;
 566                 ASSERT(match.isNode());
 567                 m_node->replaceWith(match.asNode());
 568                 m_changed = true;
 569             }
 570         }
 571
 572     private:
 573         Graph& m_graph;
 574
 575         bool m_changed;
 576         Node* m_node;
 577         BasicBlock* m_block;
 578
 579         Maps m_maps;
 580
 581         InsertionSet m_insertionSet;
 582     };
 583
 584     BlockCSE<SmallMaps> m_smallBlock;
 585     BlockCSE<LargeMaps> m_largeBlock;
 586 };
 587
 588 class GlobalCSEPhase : public Phase {
 589 public:
 590     GlobalCSEPhase(Graph& graph)
 591         : Phase(graph, "global common subexpression elimination")
 592         , m_impureDataMap(graph)
 593         , m_insertionSet(graph)
 594     {
 595     }
 596
 597     bool run()
 598     {
 599         ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
 600         ASSERT(m_graph.m_form == SSA);
 601
 602         m_graph.initializeNodeOwners();
 603         m_graph.ensureSSADominators();
 604
 605         m_preOrder = m_graph.blocksInPreOrder();
 606
 607         // First figure out what gets clobbered by blocks. Node that this uses the preOrder list
 608         // for convenience only.
 609         for (unsigned i = m_preOrder.size(); i--;) {
 610             m_block = m_preOrder[i];
 611             m_impureData = &m_impureDataMap[m_block];
 612             for (unsigned nodeIndex = m_block->size(); nodeIndex--;)
 613                 addWrites(m_graph, m_block->at(nodeIndex), m_impureData->writes);
 614         }
 615
 616         // Based on my experience doing this before, what follows might have to be made iterative.
 617         // Right now it doesn't have to be iterative because everything is dominator-bsed. But when
 618         // validation is enabled, we check if iterating would find new CSE opportunities.
 619
 620         bool changed = iterate();
 621
 622         // FIXME: It should be possible to assert that CSE will not find any new opportunities if you
 623         // run it a second time. Unfortunately, we cannot assert this right now. Note that if we did
 624         // this, we'd have to first reset all of our state.
 625         // https://bugs.webkit.org/show_bug.cgi?id=145853
 626
 627         return changed;
 628     }
 629
 630     bool iterate()
 631     {
 632         if (DFGCSEPhaseInternal::verbose)
 633             dataLog("Performing iteration.\n");
 634
 635         m_changed = false;
 636         m_graph.clearReplacements();
 637
 638         for (unsigned i = 0; i < m_preOrder.size(); ++i) {
 639             m_block = m_preOrder[i];
 640             m_impureData = &m_impureDataMap[m_block];
 641             m_writesSoFar.clear();
 642
 643             if (DFGCSEPhaseInternal::verbose)
 644                 dataLog("Processing block ", *m_block, ":\n");
 645
 646             for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
 647                 m_nodeIndex = nodeIndex;
 648                 m_node = m_block->at(nodeIndex);
 649                 if (DFGCSEPhaseInternal::verbose)
 650                     dataLog("  Looking at node ", m_node, ":\n");
 651
 652                 m_graph.performSubstitution(m_node);
 653
 654                 if (m_node->op() == Identity || m_node->op() == IdentityWithProfile) {
 655                     m_node->replaceWith(m_node->child1().node());
 656                     m_changed = true;
 657                 } else
 658                     clobberize(m_graph, m_node, *this);
 659             }
 660
 661             m_insertionSet.execute(m_block);
 662
 663             m_impureData->didVisit = true;
 664         }
 665
 666         return m_changed;
 667     }
 668
 669     void read(AbstractHeap) { }
 670
 671     void write(AbstractHeap heap)
 672     {
 673         m_impureData->availableAtTail.clobber(heap);
 674         m_writesSoFar.add(heap);
 675     }
 676
 677     void def(PureValue value)
 678     {
 679         // With pure values we do not have to worry about the possibility of some control flow path
 680         // clobbering the value. So, we just search for all of the like values that have been
 681         // computed. We pick one that is in a block that dominates ours. Note that this means that
 682         // a PureValue will map to a list of nodes, since there may be many places in the control
 683         // flow graph that compute a value but only one of them that dominates us. We may build up
 684         // a large list of nodes that compute some value in the case of gnarly control flow. This
 685         // is probably OK.
 686
 687         auto result = m_pureValues.add(value, Vector<Node*>());
 688         if (result.isNewEntry) {
 689             result.iterator->value.append(m_node);
 690             return;
 691         }
 692
 693         for (unsigned i = result.iterator->value.size(); i--;) {
 694             Node* candidate = result.iterator->value[i];
 695             if (m_graph.m_ssaDominators->dominates(candidate->owner, m_block)) {
 696                 m_node->replaceWith(candidate);
 697                 m_changed = true;
 698                 return;
 699             }
 700         }
 701
 702         result.iterator->value.append(m_node);
 703     }
 704
 705     LazyNode findReplacement(HeapLocation location)
 706     {
 707         // At this instant, our "availableAtTail" reflects the set of things that are available in
 708         // this block so far. We check this map to find block-local CSE opportunities before doing
 709         // a global search.
 710         LazyNode match = m_impureData->availableAtTail.get(location);
 711         if (!!match) {
 712             if (DFGCSEPhaseInternal::verbose)
 713                 dataLog("      Found local match: ", match, "\n");
 714             return match;
 715         }
 716
 717         // If it's not available at this point in the block, and at some prior point in the block
 718         // we have clobbered this heap location, then there is no point in doing a global search.
 719         if (m_writesSoFar.overlaps(location.heap())) {
 720             if (DFGCSEPhaseInternal::verbose)
 721                 dataLog("      Not looking globally because of local clobber: ", m_writesSoFar, "\n");
 722             return nullptr;
 723         }
 724
 725         // This perfoms a backward search over the control flow graph to find some possible
 726         // non-local def() that matches our heap location. Such a match is only valid if there does
 727         // not exist any path from that def() to our block that contains a write() that overlaps
 728         // our heap. This algorithm looks for both of these things (the matching def and the
 729         // overlapping writes) in one backwards DFS pass.
 730         //
 731         // This starts by looking at the starting block's predecessors, and then it continues along
 732         // their predecessors. As soon as this finds a possible def() - one that defines the heap
 733         // location we want while dominating our starting block - it assumes that this one must be
 734         // the match. It then lets the DFS over predecessors complete, but it doesn't add the
 735         // def()'s predecessors; this ensures that any blocks we visit thereafter are on some path
 736         // from the def() to us. As soon as the DFG finds a write() that overlaps the location's
 737         // heap, it stops, assuming that there is no possible match. Note that the write() case may
 738         // trigger before we find a def(), or after. Either way, the write() case causes this
 739         // function to immediately return nullptr.
 740         //
 741         // If the write() is found before we find the def(), then we know that any def() we would
 742         // find would have a path to us that trips over the write() and hence becomes invalid. This
 743         // is just a direct outcome of us looking for a def() that dominates us. Given a block A
 744         // that dominates block B - so that A is the one that would have the def() and B is our
 745         // starting block - we know that any other block must either be on the path from A to B, or
 746         // it must be on a path from the root to A, but not both. So, if we haven't found A yet but
 747         // we already have found a block C that has a write(), then C must be on some path from A
 748         // to B, which means that A's def() is invalid for our purposes. Hence, before we find the
 749         // def(), stopping on write() is the right thing to do.
 750         //
 751         // Stopping on write() is also the right thing to do after we find the def(). After we find
 752         // the def(), we don't add that block's predecessors to the search worklist. That means
 753         // that henceforth the only blocks we will see in the search are blocks on the path from
 754         // the def() to us. If any such block has a write() that clobbers our heap then we should
 755         // give up.
 756         //
 757         // Hence this graph search algorithm ends up being deceptively simple: any overlapping
 758         // write() causes us to immediately return nullptr, and a matching def() means that we just
 759         // record it and neglect to visit its precessors.
 760
 761         Vector<BasicBlock*, 8> worklist;
 762         Vector<BasicBlock*, 8> seenList;
 763         BitVector seen;
 764
 765         for (unsigned i = m_block->predecessors.size(); i--;) {
 766             BasicBlock* predecessor = m_block->predecessors[i];
 767             if (!seen.get(predecessor->index)) {
 768                 worklist.append(predecessor);
 769                 seen.set(predecessor->index);
 770             }
 771         }
 772
 773         while (!worklist.isEmpty()) {
 774             BasicBlock* block = worklist.takeLast();
 775             seenList.append(block);
 776
 777             if (DFGCSEPhaseInternal::verbose)
 778                 dataLog("      Searching in block ", *block, "\n");
 779             ImpureBlockData& data = m_impureDataMap[block];
 780
 781             // We require strict domination because this would only see things in our own block if
 782             // they came *after* our position in the block. Clearly, while our block dominates
 783             // itself, the things in the block after us don't dominate us.
 784             if (m_graph.m_ssaDominators->strictlyDominates(block, m_block)) {
 785                 if (DFGCSEPhaseInternal::verbose)
 786                     dataLog("        It strictly dominates.\n");
 787                 DFG_ASSERT(m_graph, m_node, data.didVisit);
 788                 DFG_ASSERT(m_graph, m_node, !match);
 789                 match = data.availableAtTail.get(location);
 790                 if (DFGCSEPhaseInternal::verbose)
 791                     dataLog("        Availability: ", match, "\n");
 792                 if (!!match) {
 793                     // Don't examine the predecessors of a match. At this point we just want to
 794                     // establish that other blocks on the path from here to there don't clobber
 795                     // the location we're interested in.
 796                     continue;
 797                 }
 798             }
 799
 800             if (DFGCSEPhaseInternal::verbose)
 801                 dataLog("        Dealing with write set ", data.writes, "\n");
 802             if (data.writes.overlaps(location.heap())) {
 803                 if (DFGCSEPhaseInternal::verbose)
 804                     dataLog("        Clobbered.\n");
 805                 return nullptr;
 806             }
 807
 808             for (unsigned i = block->predecessors.size(); i--;) {
 809                 BasicBlock* predecessor = block->predecessors[i];
 810                 if (!seen.get(predecessor->index)) {
 811                     worklist.append(predecessor);
 812                     seen.set(predecessor->index);
 813                 }
 814             }
 815         }
 816
 817         if (!match)
 818             return nullptr;
 819
 820         // Cache the results for next time. We cache them both for this block and for all of our
 821         // predecessors, since even though we've already visited our predecessors, our predecessors
 822         // probably have successors other than us.
 823         // FIXME: Consider caching failed searches as well, when match is null. It's not clear that
 824         // the reduction in compile time would warrant the increase in complexity, though.
 825         // https://bugs.webkit.org/show_bug.cgi?id=134876
 826         for (BasicBlock* block : seenList)
 827             m_impureDataMap[block].availableAtTail.add(location, match);
 828         m_impureData->availableAtTail.add(location, match);
 829
 830         return match;
 831     }
 832
 833     void def(HeapLocation location, LazyNode value)
 834     {
 835         if (DFGCSEPhaseInternal::verbose)
 836             dataLog("    Got heap location def: ", location, " -> ", value, "\n");
 837
 838         LazyNode match = findReplacement(location);
 839
 840         if (DFGCSEPhaseInternal::verbose)
 841             dataLog("      Got match: ", match, "\n");
 842
 843         if (!match) {
 844             if (DFGCSEPhaseInternal::verbose)
 845                 dataLog("      Adding at-tail mapping: ", location, " -> ", value, "\n");
 846             auto result = m_impureData->availableAtTail.add(location, value);
 847             ASSERT_UNUSED(result, !result);
 848             return;
 849         }
 850
 851         if (value.isNode() && value.asNode() == m_node) {
 852             if (!match.isNode()) {
 853                 // We need to properly record the constant in order to use an existing one if applicable.
 854                 // This ensures that re-running GCSE will not find new optimizations.
 855                 match.ensureIsNode(m_insertionSet, m_block, m_nodeIndex)->owner = m_block;
 856                 auto result = m_pureValues.add(PureValue(match.asNode(), match->constant()), Vector<Node*>());
 857                 bool replaced = false;
 858                 if (!result.isNewEntry) {
 859                     for (unsigned i = result.iterator->value.size(); i--;) {
 860                         Node* candidate = result.iterator->value[i];
 861                         if (m_graph.m_ssaDominators->dominates(candidate->owner, m_block)) {
 862                             ASSERT(candidate);
 863                             match->replaceWith(candidate);
 864                             match.setNode(candidate);
 865                             replaced = true;
 866                             break;
 867                         }
 868                     }
 869                 }
 870                 if (!replaced)
 871                     result.iterator->value.append(match.asNode());
 872             }
 873             ASSERT(match.asNode());
 874             m_node->replaceWith(match.asNode());
 875             m_changed = true;
 876         }
 877     }
 878
 879     struct ImpureBlockData {
 880         ImpureBlockData()
 881             : didVisit(false)
 882         {
 883         }
 884
 885         ClobberSet writes;
 886         ImpureMap availableAtTail;
 887         bool didVisit;
 888     };
 889
 890     Vector<BasicBlock*> m_preOrder;
 891
 892     PureMultiMap m_pureValues;
 893     BlockMap<ImpureBlockData> m_impureDataMap;
 894
 895     BasicBlock* m_block;
 896     Node* m_node;
 897     unsigned m_nodeIndex;
 898     ImpureBlockData* m_impureData;
 899     ClobberSet m_writesSoFar;
 900     InsertionSet m_insertionSet;
 901
 902     bool m_changed;
 903 };
 904
 905 } // anonymous namespace
 906
 907 bool performLocalCSE(Graph& graph)
 908 {
 909     return runPhase<LocalCSEPhase>(graph);
 910 }
 911
 912 bool performGlobalCSE(Graph& graph)
 913 {
 914     return runPhase<GlobalCSEPhase>(graph);
 915 }
 916
 917 } } // namespace JSC::DFG
 918
 919 #endif // ENABLE(DFG_JIT)