Allow object allocation sinking through GetScope, GetExecutable and SkipScope nodes
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGObjectAllocationSinkingPhase.cpp
1 /*
2  * Copyright (C) 2014, 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 "DFGObjectAllocationSinkingPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractHeap.h"
32 #include "DFGBlockMapInlines.h"
33 #include "DFGClobberize.h"
34 #include "DFGCombinedLiveness.h"
35 #include "DFGGraph.h"
36 #include "DFGInsertOSRHintsForUpdate.h"
37 #include "DFGInsertionSet.h"
38 #include "DFGLivenessAnalysisPhase.h"
39 #include "DFGOSRAvailabilityAnalysisPhase.h"
40 #include "DFGPhase.h"
41 #include "DFGPromoteHeapAccess.h"
42 #include "DFGSSACalculator.h"
43 #include "DFGValidate.h"
44 #include "JSCInlines.h"
45
46 namespace JSC { namespace DFG {
47
48 static bool verbose = false;
49
50 class ObjectAllocationSinkingPhase : public Phase {
51 public:
52     ObjectAllocationSinkingPhase(Graph& graph)
53         : Phase(graph, "object allocation sinking")
54         , m_ssaCalculator(graph)
55         , m_insertionSet(graph)
56     {
57     }
58     
59     bool run()
60     {
61         ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
62         
63         m_graph.m_dominators.computeIfNecessary(m_graph);
64         
65         // Logically we wish to consider every NewObject and sink it. However it's probably not
66         // profitable to sink a NewObject that will always escape. So, first we do a very simple
67         // forward flow analysis that determines the set of NewObject nodes that have any chance
68         // of benefiting from object allocation sinking. Then we fixpoint the following rules:
69         //
70         // - For each NewObject, we turn the original NewObject into a PhantomNewObject and then
71         //   we insert MaterializeNewObject just before those escaping sites that come before any
72         //   other escaping sites - that is, there is no path between the allocation and those sites
73         //   that would see any other escape. Note that Upsilons constitute escaping sites. Then we
74         //   insert additional MaterializeNewObject nodes on Upsilons that feed into Phis that mix
75         //   materializations and the original PhantomNewObject. We then turn each PutByOffset over a
76         //   PhantomNewObject into a PutHint.
77         //
78         // - We perform the same optimization for MaterializeNewObject. This allows us to cover
79         //   cases where we had MaterializeNewObject flowing into a PutHint.
80         //
81         // We could also add this rule:
82         //
83         // - If all of the Upsilons of a Phi have a MaterializeNewObject that isn't used by anyone
84         //   else, then replace the Phi with the MaterializeNewObject.
85         //
86         //   FIXME: Implement this. Note that this totally doable but it requires some gnarly
87         //   code, and to be effective the pruner needs to be aware of it. Currently any Upsilon
88         //   is considered to be an escape even by the pruner, so it's unlikely that we'll see
89         //   many cases of Phi over Materializations.
90         //   https://bugs.webkit.org/show_bug.cgi?id=136927
91         
92         if (!performSinking())
93             return false;
94         
95         while (performSinking()) { }
96         
97         if (verbose) {
98             dataLog("Graph after sinking:\n");
99             m_graph.dump();
100         }
101         
102         return true;
103     }
104
105 private:
106     bool performSinking()
107     {
108         m_graph.computeRefCounts();
109         performLivenessAnalysis(m_graph);
110         performOSRAvailabilityAnalysis(m_graph);
111         m_combinedLiveness = CombinedLiveness(m_graph);
112         
113         CString graphBeforeSinking;
114         if (Options::verboseValidationFailure() && Options::validateGraphAtEachPhase()) {
115             StringPrintStream out;
116             m_graph.dump(out);
117             graphBeforeSinking = out.toCString();
118         }
119         
120         if (verbose) {
121             dataLog("Graph before sinking:\n");
122             m_graph.dump();
123         }
124         
125         determineMaterializationPoints();
126         if (m_sinkCandidates.isEmpty())
127             return false;
128         
129         // At this point we are committed to sinking the sinking candidates.
130         placeMaterializationPoints();
131         lowerNonReadingOperationsOnPhantomAllocations();
132         promoteSunkenFields();
133         
134         if (Options::validateGraphAtEachPhase())
135             validate(m_graph, DumpGraph, graphBeforeSinking);
136         
137         if (verbose)
138             dataLog("Sinking iteration changed the graph.\n");
139         return true;
140     }
141     
142     void determineMaterializationPoints()
143     {
144         // The premise of this pass is that if there exists a point in the program where some
145         // path from a phantom allocation site to that point causes materialization, then *all*
146         // paths cause materialization. This should mean that there are never any redundant
147         // materializations.
148         
149         m_sinkCandidates.clear();
150         m_materializationToEscapee.clear();
151         m_materializationSiteToMaterializations.clear();
152         
153         BlockMap<HashMap<Node*, bool>> materializedAtHead(m_graph);
154         BlockMap<HashMap<Node*, bool>> materializedAtTail(m_graph);
155         
156         bool changed;
157         do {
158             if (verbose)
159                 dataLog("Doing iteration of materialization point placement.\n");
160             changed = false;
161             for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
162                 HashMap<Node*, bool> materialized = materializedAtHead[block];
163                 if (verbose)
164                     dataLog("    Looking at block ", pointerDump(block), "\n");
165                 for (Node* node : *block) {
166                     handleNode(
167                         node,
168                         [&] () {
169                             materialized.add(node, false);
170                         },
171                         [&] (Node* escapee) {
172                             auto iter = materialized.find(escapee);
173                             if (iter != materialized.end()) {
174                                 if (verbose)
175                                     dataLog("    ", escapee, " escapes at ", node, "\n");
176                                 iter->value = true;
177                             }
178                         });
179                 }
180                 
181                 if (verbose)
182                     dataLog("    Materialized at tail of ", pointerDump(block), ": ", mapDump(materialized), "\n");
183                 
184                 if (materialized == materializedAtTail[block])
185                     continue;
186                 
187                 materializedAtTail[block] = materialized;
188                 changed = true;
189                 
190                 // Only propagate things to our successors if they are alive in all successors.
191                 // So, we prune materialized-at-tail to only include things that are live.
192                 Vector<Node*> toRemove;
193                 for (auto pair : materialized) {
194                     if (!m_combinedLiveness.liveAtTail[block].contains(pair.key))
195                         toRemove.append(pair.key);
196                 }
197                 for (Node* key : toRemove)
198                     materialized.remove(key);
199                 
200                 for (BasicBlock* successorBlock : block->successors()) {
201                     for (auto pair : materialized) {
202                         materializedAtHead[successorBlock].add(
203                             pair.key, false).iterator->value |= pair.value;
204                     }
205                 }
206             }
207         } while (changed);
208         
209         // Determine the sink candidates. Broadly, a sink candidate is a node that handleNode()
210         // believes is sinkable, and one of the following is true:
211         //
212         // 1) There exists a basic block with only backward outgoing edges (or no outgoing edges)
213         //    in which the node wasn't materialized. This is meant to catch effectively-infinite
214         //    loops in which we don't need to have allocated the object.
215         //
216         // 2) There exists a basic block at the tail of which the node is not materialized and the
217         //    node is dead.
218         //
219         // 3) The sum of execution counts of the materializations is less than the sum of
220         //    execution counts of the original node.
221         //
222         // We currently implement only rule #2.
223         // FIXME: Implement the two other rules.
224         // https://bugs.webkit.org/show_bug.cgi?id=137073 (rule #1)
225         // https://bugs.webkit.org/show_bug.cgi?id=137074 (rule #3)
226         
227         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
228             for (auto pair : materializedAtTail[block]) {
229                 if (pair.value)
230                     continue; // It was materialized.
231                 
232                 if (m_combinedLiveness.liveAtTail[block].contains(pair.key))
233                     continue; // It might still get materialized in all of the successors.
234                 
235                 // We know that it died in this block and it wasn't materialized. That means that
236                 // if we sink this allocation, then *this* will be a path along which we never
237                 // have to allocate. Profit!
238                 m_sinkCandidates.add(pair.key);
239             }
240         }
241         
242         if (m_sinkCandidates.isEmpty())
243             return;
244         
245         // A materialization edge exists at any point where a node escapes but hasn't been
246         // materialized yet. We do this in two parts. First we find all of the nodes that cause
247         // escaping to happen, where the escapee had not yet been materialized. This catches
248         // everything but loops. We then catch loops - as well as weirder control flow constructs -
249         // in a subsequent pass that looks at places in the CFG where an edge exists from a block
250         // that hasn't materialized to a block that has. We insert the materialization along such an
251         // edge, and we rely on the fact that critical edges were already broken so that we actually
252         // either insert the materialization at the head of the successor or the tail of the
253         // predecessor.
254         //
255         // FIXME: This can create duplicate allocations when we really only needed to perform one.
256         // For example:
257         //
258         //     var o = new Object();
259         //     if (rare) {
260         //         if (stuff)
261         //             call(o); // o escapes here.
262         //         return;
263         //     }
264         //     // o doesn't escape down here.
265         //
266         // In this example, we would place a materialization point at call(o) and then we would find
267         // ourselves having to insert another one at the implicit else case of that if statement
268         // ('cause we've broken critical edges). We would instead really like to just have one
269         // materialization point right at the top of the then case of "if (rare)". To do this, we can
270         // find the LCA of the various materializations in the dom tree.
271         // https://bugs.webkit.org/show_bug.cgi?id=137124
272         
273         // First pass: find intra-block materialization points.
274         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
275             HashSet<Node*> materialized;
276             for (auto pair : materializedAtHead[block]) {
277                 if (pair.value && m_sinkCandidates.contains(pair.key))
278                     materialized.add(pair.key);
279             }
280             
281             if (verbose)
282                 dataLog("Placing materialization points in ", pointerDump(block), " with materialization set ", listDump(materialized), "\n");
283             
284             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
285                 Node* node = block->at(nodeIndex);
286                 
287                 handleNode(
288                     node,
289                     [&] () { },
290                     [&] (Node* escapee) {
291                         if (verbose)
292                             dataLog("Seeing ", escapee, " escape at ", node, "\n");
293                         
294                         if (!m_sinkCandidates.contains(escapee)) {
295                             if (verbose)
296                                 dataLog("    It's not a sink candidate.\n");
297                             return;
298                         }
299                         
300                         if (!materialized.add(escapee).isNewEntry) {
301                             if (verbose)
302                                 dataLog("   It's already materialized.\n");
303                             return;
304                         }
305                         
306                         createMaterialize(escapee, node);
307                     });
308             }
309         }
310         
311         // Second pass: find CFG edge materialization points.
312         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
313             for (BasicBlock* successorBlock : block->successors()) {
314                 for (auto pair : materializedAtHead[successorBlock]) {
315                     Node* allocation = pair.key;
316                     
317                     // We only care if it is materialized in the successor.
318                     if (!pair.value)
319                         continue;
320                     
321                     // We only care about sinking candidates.
322                     if (!m_sinkCandidates.contains(allocation))
323                         continue;
324                     
325                     // We only care if it isn't materialized in the predecessor.
326                     if (materializedAtTail[block].get(allocation))
327                         continue;
328                     
329                     // We need to decide if we put the materialization at the head of the successor,
330                     // or the tail of the predecessor. It needs to be placed so that the allocation
331                     // is never materialized before, and always materialized after.
332                     
333                     // Is it never materialized in any of successor's predecessors? I like to think
334                     // of "successors' predecessors" and "predecessor's successors" as the "shadow",
335                     // because of what it looks like when you draw it.
336                     bool neverMaterializedInShadow = true;
337                     for (BasicBlock* shadowBlock : successorBlock->predecessors) {
338                         if (materializedAtTail[shadowBlock].get(allocation)) {
339                             neverMaterializedInShadow = false;
340                             break;
341                         }
342                     }
343                     
344                     if (neverMaterializedInShadow) {
345                         createMaterialize(allocation, successorBlock->firstOriginNode());
346                         continue;
347                     }
348                     
349                     // Because we had broken critical edges, it must be the case that the
350                     // predecessor's successors all materialize the object. This is because the
351                     // previous case is guaranteed to catch the case where the successor only has
352                     // one predecessor. When critical edges are broken, this is also the only case
353                     // where the predecessor could have had multiple successors. Therefore we have
354                     // already handled the case where the predecessor has multiple successors.
355                     DFG_ASSERT(m_graph, block, block->numSuccessors() == 1);
356                     
357                     createMaterialize(allocation, block->terminal());
358                 }
359             }
360         }
361     }
362     
363     void placeMaterializationPoints()
364     {
365         m_ssaCalculator.reset();
366         
367         // The "variables" are the object allocations that we are sinking. So, nodeToVariable maps
368         // sink candidates (aka escapees) to the SSACalculator's notion of Variable, and indexToNode
369         // maps in the opposite direction using the SSACalculator::Variable::index() as the key.
370         HashMap<Node*, SSACalculator::Variable*> nodeToVariable;
371         Vector<Node*> indexToNode;
372         
373         for (Node* node : m_sinkCandidates) {
374             SSACalculator::Variable* variable = m_ssaCalculator.newVariable();
375             nodeToVariable.add(node, variable);
376             ASSERT(indexToNode.size() == variable->index());
377             indexToNode.append(node);
378         }
379         
380         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
381             for (Node* node : *block) {
382                 if (SSACalculator::Variable* variable = nodeToVariable.get(node))
383                     m_ssaCalculator.newDef(variable, block, node);
384                 
385                 for (Node* materialize : m_materializationSiteToMaterializations.get(node)) {
386                     m_ssaCalculator.newDef(
387                         nodeToVariable.get(m_materializationToEscapee.get(materialize)),
388                         block, materialize);
389                 }
390             }
391         }
392         
393         m_ssaCalculator.computePhis(
394             [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
395                 Node* allocation = indexToNode[variable->index()];
396                 if (!m_combinedLiveness.liveAtHead[block].contains(allocation))
397                     return nullptr;
398                 
399                 Node* phiNode = m_graph.addNode(allocation->prediction(), Phi, NodeOrigin());
400                 phiNode->mergeFlags(NodeResultJS);
401                 return phiNode;
402             });
403         
404         // Place Phis in the right places. Replace all uses of any allocation with the appropriate
405         // materialization. Create the appropriate Upsilon nodes.
406         LocalOSRAvailabilityCalculator availabilityCalculator;
407         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
408             HashMap<Node*, Node*> mapping;
409             
410             for (Node* candidate : m_combinedLiveness.liveAtHead[block]) {
411                 SSACalculator::Variable* variable = nodeToVariable.get(candidate);
412                 if (!variable)
413                     continue;
414                 
415                 SSACalculator::Def* def = m_ssaCalculator.reachingDefAtHead(block, variable);
416                 if (!def)
417                     continue;
418                 
419                 mapping.set(indexToNode[variable->index()], def->value());
420             }
421             
422             availabilityCalculator.beginBlock(block);
423             for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) {
424                 m_insertionSet.insert(0, phiDef->value());
425                 
426                 Node* originalNode = indexToNode[phiDef->variable()->index()];
427                 insertOSRHintsForUpdate(
428                     m_insertionSet, 0, NodeOrigin(), availabilityCalculator.m_availability,
429                     originalNode, phiDef->value());
430
431                 mapping.set(originalNode, phiDef->value());
432             }
433             
434             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
435                 Node* node = block->at(nodeIndex);
436
437                 for (Node* materialize : m_materializationSiteToMaterializations.get(node)) {
438                     Node* escapee = m_materializationToEscapee.get(materialize);
439                     m_insertionSet.insert(nodeIndex, materialize);
440                     insertOSRHintsForUpdate(
441                         m_insertionSet, nodeIndex, node->origin,
442                         availabilityCalculator.m_availability, escapee, materialize);
443                     mapping.set(escapee, materialize);
444                 }
445                     
446                 availabilityCalculator.executeNode(node);
447                 
448                 m_graph.doToChildren(
449                     node,
450                     [&] (Edge& edge) {
451                         if (Node* materialize = mapping.get(edge.node()))
452                             edge.setNode(materialize);
453                     });
454                 
455                 // If you cause an escape, you shouldn't see the original escapee.
456                 if (validationEnabled()) {
457                     handleNode(
458                         node,
459                         [&] () { },
460                         [&] (Node* escapee) {
461                             DFG_ASSERT(m_graph, node, !m_sinkCandidates.contains(escapee));
462                         });
463                 }
464             }
465             
466             NodeAndIndex terminal = block->findTerminal();
467             size_t upsilonInsertionPoint = terminal.index;
468             Node* upsilonWhere = terminal.node;
469             NodeOrigin upsilonOrigin = upsilonWhere->origin;
470             for (BasicBlock* successorBlock : block->successors()) {
471                 for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
472                     Node* phiNode = phiDef->value();
473                     SSACalculator::Variable* variable = phiDef->variable();
474                     Node* allocation = indexToNode[variable->index()];
475                     
476                     Node* incoming = mapping.get(allocation);
477                     DFG_ASSERT(m_graph, incoming, incoming != allocation);
478                     
479                     m_insertionSet.insertNode(
480                         upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
481                         OpInfo(phiNode), incoming->defaultEdge());
482                 }
483             }
484             
485             m_insertionSet.execute(block);
486         }
487         
488         // At this point we have dummy materialization nodes along with edges to them. This means
489         // that the part of the control flow graph that prefers to see actual object allocations
490         // is completely fixed up, except for the materializations themselves.
491     }
492     
493     void lowerNonReadingOperationsOnPhantomAllocations()
494     {
495         // Lower everything but reading operations on phantom allocations. We absolutely have to
496         // lower all writes so as to reveal them to the SSA calculator. We cannot lower reads
497         // because the whole point is that those go away completely.
498         
499         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
500             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
501                 Node* node = block->at(nodeIndex);
502                 switch (node->op()) {
503                 case PutByOffset: {
504                     Node* target = node->child2().node();
505                     if (m_sinkCandidates.contains(target)) {
506                         ASSERT(target->isPhantomObjectAllocation());
507                         node->convertToPutByOffsetHint();
508                     }
509                     break;
510                 }
511
512                 case PutClosureVar: {
513                     Node* target = node->child1().node();
514                     if (m_sinkCandidates.contains(target)) {
515                         ASSERT(target->isPhantomActivationAllocation());
516                         node->convertToPutClosureVarHint();
517                     }
518                     break;
519                 }
520                     
521                 case PutStructure: {
522                     Node* target = node->child1().node();
523                     if (m_sinkCandidates.contains(target)) {
524                         ASSERT(target->isPhantomObjectAllocation());
525                         Node* structure = m_insertionSet.insertConstant(
526                             nodeIndex, node->origin, JSValue(node->transition()->next));
527                         node->convertToPutStructureHint(structure);
528                     }
529                     break;
530                 }
531                     
532                 case NewObject: {
533                     if (m_sinkCandidates.contains(node)) {
534                         Node* structure = m_insertionSet.insertConstant(
535                             nodeIndex + 1, node->origin, JSValue(node->structure()));
536                         m_insertionSet.insert(
537                             nodeIndex + 1,
538                             PromotedHeapLocation(StructurePLoc, node).createHint(
539                                 m_graph, node->origin, structure));
540                         node->convertToPhantomNewObject();
541                     }
542                     break;
543                 }
544                     
545                 case MaterializeNewObject: {
546                     if (m_sinkCandidates.contains(node)) {
547                         m_insertionSet.insert(
548                             nodeIndex + 1,
549                             PromotedHeapLocation(StructurePLoc, node).createHint(
550                                 m_graph, node->origin, m_graph.varArgChild(node, 0).node()));
551                         for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {
552                             unsigned identifierNumber =
553                                 node->objectMaterializationData().m_properties[i].m_identifierNumber;
554                             m_insertionSet.insert(
555                                 nodeIndex + 1,
556                                 PromotedHeapLocation(
557                                     NamedPropertyPLoc, node, identifierNumber).createHint(
558                                     m_graph, node->origin,
559                                     m_graph.varArgChild(node, i + 1).node()));
560                         }
561                         node->convertToPhantomNewObject();
562                     }
563                     break;
564                 }
565
566                 case NewFunction: {
567                     if (m_sinkCandidates.contains(node)) {
568                         Node* executable = m_insertionSet.insertConstant(
569                             nodeIndex + 1, node->origin, node->cellOperand());
570                         m_insertionSet.insert(
571                             nodeIndex + 1,
572                             PromotedHeapLocation(FunctionExecutablePLoc, node).createHint(
573                                 m_graph, node->origin, executable));
574                         m_insertionSet.insert(
575                             nodeIndex + 1,
576                             PromotedHeapLocation(FunctionActivationPLoc, node).createHint(
577                                 m_graph, node->origin, node->child1().node()));
578                         node->convertToPhantomNewFunction();
579                     }
580                     break;
581                 }
582
583                 case CreateActivation: {
584                     if (m_sinkCandidates.contains(node)) {
585                         m_insertionSet.insert(
586                             nodeIndex + 1,
587                             PromotedHeapLocation(ActivationScopePLoc, node).createHint(
588                                 m_graph, node->origin, node->child1().node()));
589                         Node* symbolTableNode = m_insertionSet.insertConstant(
590                             nodeIndex + 1, node->origin, node->cellOperand());
591                         m_insertionSet.insert(
592                             nodeIndex + 1,
593                             PromotedHeapLocation(ActivationSymbolTablePLoc, node).createHint(
594                                 m_graph, node->origin, symbolTableNode));
595
596                         {
597                             SymbolTable* symbolTable = node->castOperand<SymbolTable*>();
598                             Node* undefined = m_insertionSet.insertConstant(
599                                 nodeIndex + 1, node->origin, jsUndefined());
600                             ConcurrentJITLocker locker(symbolTable->m_lock);
601                             for (auto iter = symbolTable->begin(locker), end = symbolTable->end(locker); iter != end; ++iter) {
602                                 m_insertionSet.insert(
603                                     nodeIndex + 1,
604                                     PromotedHeapLocation(
605                                         ClosureVarPLoc, node, iter->value.scopeOffset().offset()).createHint(
606                                         m_graph, node->origin, undefined));
607                             }
608                         }
609
610                         node->convertToPhantomCreateActivation();
611                     }
612                     break;
613                 }
614
615                 case MaterializeCreateActivation: {
616                     if (m_sinkCandidates.contains(node)) {
617                         m_insertionSet.insert(
618                             nodeIndex + 1,
619                             PromotedHeapLocation(ActivationScopePLoc, node).createHint(
620                                 m_graph, node->origin, m_graph.varArgChild(node, 0).node()));
621                         Node* symbolTableNode = m_insertionSet.insertConstant(
622                             nodeIndex + 1, node->origin, node->cellOperand());
623                         m_insertionSet.insert(
624                             nodeIndex + 1,
625                             PromotedHeapLocation(ActivationSymbolTablePLoc, node).createHint(
626                                 m_graph, node->origin, symbolTableNode));
627                         ObjectMaterializationData& data = node->objectMaterializationData();
628                         for (unsigned i = 0; i < data.m_properties.size(); ++i) {
629                             unsigned identifierNumber = data.m_properties[i].m_identifierNumber;
630                             m_insertionSet.insert(
631                                 nodeIndex + 1,
632                                 PromotedHeapLocation(
633                                     ClosureVarPLoc, node, identifierNumber).createHint(
634                                     m_graph, node->origin,
635                                     m_graph.varArgChild(node, i + 1).node()));
636                         }
637                         node->convertToPhantomCreateActivation();
638                     }
639                     break;
640                 }
641
642                 case StoreBarrier: {
643                     DFG_CRASH(m_graph, node, "Unexpected store barrier during sinking.");
644                     break;
645                 }
646                     
647                 default:
648                     break;
649                 }
650                 
651                 m_graph.doToChildren(
652                     node,
653                     [&] (Edge& edge) {
654                         if (m_sinkCandidates.contains(edge.node()))
655                             edge.setUseKind(KnownCellUse);
656                     });
657             }
658             m_insertionSet.execute(block);
659         }
660     }
661     
662     void promoteSunkenFields()
663     {
664         // Collect the set of heap locations that we will be operating over.
665         HashSet<PromotedHeapLocation> locations;
666         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
667             for (Node* node : *block) {
668                 promoteHeapAccess(
669                     node,
670                     [&] (PromotedHeapLocation location, Edge) {
671                         if (m_sinkCandidates.contains(location.base()))
672                             locations.add(location);
673                     },
674                     [&] (PromotedHeapLocation location) {
675                         if (m_sinkCandidates.contains(location.base()))
676                             locations.add(location);
677                     });
678             }
679         }
680         
681         // Figure out which locations belong to which allocations.
682         m_locationsForAllocation.clear();
683         for (PromotedHeapLocation location : locations) {
684             auto result = m_locationsForAllocation.add(location.base(), Vector<PromotedHeapLocation>());
685             ASSERT(!result.iterator->value.contains(location));
686             result.iterator->value.append(location);
687         }
688         
689         // For each sunken thingy, make sure we create Bottom values for all of its fields.
690         // Note that this has the hilarious slight inefficiency of creating redundant hints for
691         // things that were previously materializations. This should only impact compile times and
692         // not code quality, and it's necessary for soundness without some data structure hackage.
693         // For example, a MaterializeNewObject that we choose to sink may have new fields added to
694         // it conditionally. That would necessitate Bottoms.
695         Node* bottom = nullptr;
696         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
697             if (block == m_graph.block(0))
698                 bottom = m_insertionSet.insertConstant(0, NodeOrigin(), jsUndefined());
699             
700             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
701                 Node* node = block->at(nodeIndex);
702                 for (PromotedHeapLocation location : m_locationsForAllocation.get(node)) {
703                     m_insertionSet.insert(
704                         nodeIndex + 1, location.createHint(m_graph, node->origin, bottom));
705                 }
706             }
707             m_insertionSet.execute(block);
708         }
709
710         m_ssaCalculator.reset();
711
712         // Collect the set of "variables" that we will be sinking.
713         m_locationToVariable.clear();
714         m_indexToLocation.clear();
715         for (PromotedHeapLocation location : locations) {
716             SSACalculator::Variable* variable = m_ssaCalculator.newVariable();
717             m_locationToVariable.add(location, variable);
718             ASSERT(m_indexToLocation.size() == variable->index());
719             m_indexToLocation.append(location);
720         }
721         
722         // Create Defs from the existing hints.
723         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
724             for (Node* node : *block) {
725                 promoteHeapAccess(
726                     node,
727                     [&] (PromotedHeapLocation location, Edge value) {
728                         if (!m_sinkCandidates.contains(location.base()))
729                             return;
730                         SSACalculator::Variable* variable = m_locationToVariable.get(location);
731                         m_ssaCalculator.newDef(variable, block, value.node());
732                     },
733                     [&] (PromotedHeapLocation) { });
734             }
735         }
736         
737         // OMG run the SSA calculator to create Phis!
738         m_ssaCalculator.computePhis(
739             [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
740                 PromotedHeapLocation location = m_indexToLocation[variable->index()];
741                 if (!m_combinedLiveness.liveAtHead[block].contains(location.base()))
742                     return nullptr;
743                 
744                 Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
745                 phiNode->mergeFlags(NodeResultJS);
746                 return phiNode;
747             });
748         
749         // Place Phis in the right places, replace all uses of any load with the appropriate
750         // value, and create the appropriate Upsilon nodes.
751         m_graph.clearReplacements();
752         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
753             // This mapping table is intended to be lazy. If something is omitted from the table,
754             // it means that there haven't been any local stores to that promoted heap location.
755             m_localMapping.clear();
756             
757             // Insert the Phi functions that we had previously created.
758             for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) {
759                 PromotedHeapLocation location = m_indexToLocation[phiDef->variable()->index()];
760                 
761                 m_insertionSet.insert(
762                     0, phiDef->value());
763                 m_insertionSet.insert(
764                     0, location.createHint(m_graph, NodeOrigin(), phiDef->value()));
765                 m_localMapping.add(location, phiDef->value());
766             }
767             
768             if (verbose)
769                 dataLog("Local mapping at ", pointerDump(block), ": ", mapDump(m_localMapping), "\n");
770             
771             // Process the block and replace all uses of loads with the promoted value.
772             for (Node* node : *block) {
773                 m_graph.performSubstitution(node);
774                 
775                 if (Node* escapee = m_materializationToEscapee.get(node))
776                     populateMaterialize(block, node, escapee);
777                 
778                 promoteHeapAccess(
779                     node,
780                     [&] (PromotedHeapLocation location, Edge value) {
781                         if (m_sinkCandidates.contains(location.base()))
782                             m_localMapping.set(location, value.node());
783                     },
784                     [&] (PromotedHeapLocation location) {
785                         if (m_sinkCandidates.contains(location.base())) {
786                             switch (node->op()) {
787                             case CheckStructure:
788                                 node->convertToCheckStructureImmediate(resolve(block, location));
789                                 break;
790
791                             default:
792                                 node->replaceWith(resolve(block, location));
793                                 break;
794                             }
795                         }
796                     });
797             }
798             
799             // Gotta drop some Upsilons.
800             NodeAndIndex terminal = block->findTerminal();
801             size_t upsilonInsertionPoint = terminal.index;
802             NodeOrigin upsilonOrigin = terminal.node->origin;
803             for (BasicBlock* successorBlock : block->successors()) {
804                 for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
805                     Node* phiNode = phiDef->value();
806                     SSACalculator::Variable* variable = phiDef->variable();
807                     PromotedHeapLocation location = m_indexToLocation[variable->index()];
808                     Node* incoming = resolve(block, location);
809                     
810                     m_insertionSet.insertNode(
811                         upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
812                         OpInfo(phiNode), incoming->defaultEdge());
813                 }
814             }
815             
816             m_insertionSet.execute(block);
817         }
818     }
819     
820     Node* resolve(BasicBlock* block, PromotedHeapLocation location)
821     {
822         if (Node* result = m_localMapping.get(location))
823             return result;
824         
825         // This implies that there is no local mapping. Find a non-local mapping.
826         SSACalculator::Def* def = m_ssaCalculator.nonLocalReachingDef(
827             block, m_locationToVariable.get(location));
828         ASSERT(def);
829         ASSERT(def->value());
830         m_localMapping.add(location, def->value());
831         return def->value();
832     }
833
834     template<typename SinkCandidateFunctor, typename EscapeFunctor>
835     void handleNode(
836         Node* node,
837         const SinkCandidateFunctor& sinkCandidate,
838         const EscapeFunctor& escape)
839     {
840         switch (node->op()) {
841         case NewObject:
842         case MaterializeNewObject:
843         case MaterializeCreateActivation:
844             sinkCandidate();
845             m_graph.doToChildren(
846                 node,
847                 [&] (Edge edge) {
848                     escape(edge.node());
849                 });
850             break;
851
852         case NewFunction:
853             if (!node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid())
854                 sinkCandidate();
855             escape(node->child1().node());
856             break;
857
858         case CreateActivation:
859             if (!node->castOperand<SymbolTable*>()->singletonScope()->isStillValid())
860                 sinkCandidate();
861             escape(node->child1().node());
862             break;
863
864         case Check:
865             m_graph.doToChildren(
866                 node,
867                 [&] (Edge edge) {
868                     if (edge.willNotHaveCheck())
869                         return;
870                     
871                     if (alreadyChecked(edge.useKind(), SpecObject))
872                         return;
873                     
874                     escape(edge.node());
875                 });
876             break;
877
878         case MovHint:
879         case PutHint:
880             break;
881
882         case PutStructure:
883         case CheckStructure:
884         case GetByOffset:
885         case MultiGetByOffset:
886         case GetGetterSetterByOffset: {
887             Node* target = node->child1().node();
888             if (!target->isObjectAllocation())
889                 escape(target);
890             break;
891         }
892             
893         case PutByOffset: {
894             Node* target = node->child2().node();
895             if (!target->isObjectAllocation()) {
896                 escape(target);
897                 escape(node->child1().node());
898             }
899             escape(node->child3().node());
900             break;
901         }
902
903         case GetClosureVar: {
904             Node* target = node->child1().node();
905             if (!target->isActivationAllocation())
906                 escape(target);
907             break;
908         }
909
910         case PutClosureVar: {
911             Node* target = node->child1().node();
912             if (!target->isActivationAllocation())
913                 escape(target);
914             escape(node->child2().node());
915             break;
916         }
917
918         case GetScope: {
919             Node* target = node->child1().node();
920             if (!target->isFunctionAllocation())
921                 escape(target);
922             break;
923         }
924
925         case GetExecutable: {
926             Node* target = node->child1().node();
927             if (!target->isFunctionAllocation())
928                 escape(target);
929             break;
930         }
931
932         case SkipScope: {
933             Node* target = node->child1().node();
934             if (!target->isActivationAllocation())
935                 escape(target);
936             break;
937         }
938             
939         case MultiPutByOffset:
940             // FIXME: In the future we should be able to handle this. It's just a matter of
941             // building the appropriate *Hint variant of this instruction, along with a
942             // PhantomStructureSelect node - since this transforms the Structure in a conditional
943             // way.
944             // https://bugs.webkit.org/show_bug.cgi?id=136924
945             escape(node->child1().node());
946             escape(node->child2().node());
947             break;
948
949         default:
950             m_graph.doToChildren(
951                 node,
952                 [&] (Edge edge) {
953                     escape(edge.node());
954                 });
955             break;
956         }
957     }
958     
959     Node* createMaterialize(Node* escapee, Node* where)
960     {
961         Node* result = nullptr;
962         
963         switch (escapee->op()) {
964         case NewObject:
965         case MaterializeNewObject: {
966             ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
967             
968             result = m_graph.addNode(
969                 escapee->prediction(), Node::VarArg, MaterializeNewObject,
970                 NodeOrigin(
971                     escapee->origin.semantic,
972                     where->origin.forExit),
973                 OpInfo(data), OpInfo(), 0, 0);
974             break;
975         }
976
977         case NewFunction:
978             result = m_graph.addNode(
979                 escapee->prediction(), NewFunction,
980                 NodeOrigin(
981                     escapee->origin.semantic,
982                     where->origin.forExit),
983                 OpInfo(escapee->cellOperand()),
984                 escapee->child1());
985             break;
986
987         case CreateActivation:
988         case MaterializeCreateActivation: {
989             ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
990             FrozenValue* symbolTable = escapee->cellOperand();
991             result = m_graph.addNode(
992                 escapee->prediction(), Node::VarArg, MaterializeCreateActivation,
993                 NodeOrigin(
994                     escapee->origin.semantic,
995                     where->origin.forExit),
996                 OpInfo(data), OpInfo(symbolTable), 0, 0);
997             break;
998         }
999
1000         default:
1001             DFG_CRASH(m_graph, escapee, "Bad escapee op");
1002             break;
1003         }
1004         
1005         if (verbose)
1006             dataLog("Creating materialization point at ", where, " for ", escapee, ": ", result, "\n");
1007         
1008         m_materializationToEscapee.add(result, escapee);
1009         m_materializationSiteToMaterializations.add(
1010             where, Vector<Node*>()).iterator->value.append(result);
1011         
1012         return result;
1013     }
1014     
1015     void populateMaterialize(BasicBlock* block, Node* node, Node* escapee)
1016     {
1017         switch (node->op()) {
1018         case MaterializeNewObject: {
1019             ObjectMaterializationData& data = node->objectMaterializationData();
1020             unsigned firstChild = m_graph.m_varArgChildren.size();
1021             
1022             Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
1023             
1024             PromotedHeapLocation structure(StructurePLoc, escapee);
1025             ASSERT(locations.contains(structure));
1026             
1027             m_graph.m_varArgChildren.append(Edge(resolve(block, structure), KnownCellUse));
1028             
1029             for (unsigned i = 0; i < locations.size(); ++i) {
1030                 switch (locations[i].kind()) {
1031                 case StructurePLoc: {
1032                     ASSERT(locations[i] == structure);
1033                     break;
1034                 }
1035                     
1036                 case NamedPropertyPLoc: {
1037                     Node* value = resolve(block, locations[i]);
1038                     if (value->op() == BottomValue) {
1039                         // We can skip Bottoms entirely.
1040                         break;
1041                     }
1042                     
1043                     data.m_properties.append(PhantomPropertyValue(locations[i].info()));
1044                     m_graph.m_varArgChildren.append(value);
1045                     break;
1046                 }
1047                     
1048                 default:
1049                     DFG_CRASH(m_graph, node, "Bad location kind");
1050                 }
1051             }
1052             
1053             node->children = AdjacencyList(
1054                 AdjacencyList::Variable,
1055                 firstChild, m_graph.m_varArgChildren.size() - firstChild);
1056             break;
1057         }
1058
1059         case MaterializeCreateActivation: {
1060             ObjectMaterializationData& data = node->objectMaterializationData();
1061
1062             unsigned firstChild = m_graph.m_varArgChildren.size();
1063
1064             Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
1065
1066             PromotedHeapLocation scope(ActivationScopePLoc, escapee);
1067             PromotedHeapLocation symbolTable(ActivationSymbolTablePLoc, escapee);
1068             ASSERT(locations.contains(scope));
1069
1070             m_graph.m_varArgChildren.append(Edge(resolve(block, scope), KnownCellUse));
1071
1072             for (unsigned i = 0; i < locations.size(); ++i) {
1073                 switch (locations[i].kind()) {
1074                 case ActivationScopePLoc: {
1075                     ASSERT(locations[i] == scope);
1076                     break;
1077                 }
1078
1079                 case ActivationSymbolTablePLoc: {
1080                     ASSERT(locations[i] == symbolTable);
1081                     break;
1082                 }
1083
1084                 case ClosureVarPLoc: {
1085                     Node* value = resolve(block, locations[i]);
1086                     if (value->op() == BottomValue)
1087                         break;
1088
1089                     data.m_properties.append(PhantomPropertyValue(locations[i].info()));
1090                     m_graph.m_varArgChildren.append(value);
1091                     break;
1092                 }
1093
1094                 default:
1095                     DFG_CRASH(m_graph, node, "Bad location kind");
1096                 }
1097             }
1098
1099             node->children = AdjacencyList(
1100                 AdjacencyList::Variable,
1101                 firstChild, m_graph.m_varArgChildren.size() - firstChild);
1102             break;
1103         }
1104
1105         case NewFunction: {
1106             if (!ASSERT_DISABLED) {
1107                 Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
1108
1109                 ASSERT(locations.size() == 2);
1110
1111                 PromotedHeapLocation executable(FunctionExecutablePLoc, escapee);
1112                 ASSERT(locations.contains(executable));
1113
1114                 PromotedHeapLocation activation(FunctionActivationPLoc, escapee);
1115                 ASSERT(locations.contains(activation));
1116
1117                 for (unsigned i = 0; i < locations.size(); ++i) {
1118                     switch (locations[i].kind()) {
1119                     case FunctionExecutablePLoc: {
1120                         ASSERT(locations[i] == executable);
1121                         break;
1122                     }
1123
1124                     case FunctionActivationPLoc: {
1125                         ASSERT(locations[i] == activation);
1126                         break;
1127                     }
1128
1129                     default:
1130                         DFG_CRASH(m_graph, node, "Bad location kind");
1131                     }
1132                 }
1133             }
1134
1135             break;
1136         }
1137
1138         default:
1139             DFG_CRASH(m_graph, node, "Bad materialize op");
1140             break;
1141         }
1142     }
1143     
1144     CombinedLiveness m_combinedLiveness;
1145     SSACalculator m_ssaCalculator;
1146     HashSet<Node*> m_sinkCandidates;
1147     HashMap<Node*, Node*> m_materializationToEscapee;
1148     HashMap<Node*, Vector<Node*>> m_materializationSiteToMaterializations;
1149     HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation;
1150     HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
1151     Vector<PromotedHeapLocation> m_indexToLocation;
1152     HashMap<PromotedHeapLocation, Node*> m_localMapping;
1153     InsertionSet m_insertionSet;
1154 };
1155     
1156 bool performObjectAllocationSinking(Graph& graph)
1157 {
1158     SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase");
1159     return runPhase<ObjectAllocationSinkingPhase>(graph);
1160 }
1161
1162 } } // namespace JSC::DFG
1163
1164 #endif // ENABLE(DFG_JIT)
1165