Arity fixup during inlining should do a 2 phase commit so it properly recovers the...
[WebKit-https.git] / 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)