Unreviewed, rolling out r184415.
[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->convertToPhantomCreateActivation();
590                     }
591                     break;
592                 }
593
594                 case MaterializeCreateActivation: {
595                     if (m_sinkCandidates.contains(node)) {
596                         m_insertionSet.insert(
597                             nodeIndex + 1,
598                             PromotedHeapLocation(ActivationScopePLoc, node).createHint(
599                                 m_graph, node->origin, m_graph.varArgChild(node, 0).node()));
600                         ObjectMaterializationData& data = node->objectMaterializationData();
601                         for (unsigned i = 0; i < data.m_properties.size(); ++i) {
602                             unsigned identifierNumber = data.m_properties[i].m_identifierNumber;
603                             m_insertionSet.insert(
604                                 nodeIndex + 1,
605                                 PromotedHeapLocation(
606                                     ClosureVarPLoc, node, identifierNumber).createHint(
607                                     m_graph, node->origin,
608                                     m_graph.varArgChild(node, i + 1).node()));
609                         }
610                         node->convertToPhantomCreateActivation();
611                     }
612                     break;
613                 }
614
615                 case StoreBarrier: {
616                     Node* target = node->child1().node();
617                     if (m_sinkCandidates.contains(target)) {
618                         ASSERT(target->isPhantomAllocation());
619                         node->remove();
620                     }
621                     break;
622                 }
623                     
624                 default:
625                     break;
626                 }
627                 
628                 m_graph.doToChildren(
629                     node,
630                     [&] (Edge& edge) {
631                         if (m_sinkCandidates.contains(edge.node()))
632                             edge.setUseKind(KnownCellUse);
633                     });
634             }
635             m_insertionSet.execute(block);
636         }
637     }
638     
639     void promoteSunkenFields()
640     {
641         // Collect the set of heap locations that we will be operating over.
642         HashSet<PromotedHeapLocation> locations;
643         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
644             for (Node* node : *block) {
645                 promoteHeapAccess(
646                     node,
647                     [&] (PromotedHeapLocation location, Edge) {
648                         if (m_sinkCandidates.contains(location.base()))
649                             locations.add(location);
650                     },
651                     [&] (PromotedHeapLocation location) {
652                         if (m_sinkCandidates.contains(location.base()))
653                             locations.add(location);
654                     });
655             }
656         }
657         
658         // Figure out which locations belong to which allocations.
659         m_locationsForAllocation.clear();
660         for (PromotedHeapLocation location : locations) {
661             auto result = m_locationsForAllocation.add(location.base(), Vector<PromotedHeapLocation>());
662             ASSERT(!result.iterator->value.contains(location));
663             result.iterator->value.append(location);
664         }
665         
666         // For each sunken thingy, make sure we create Bottom values for all of its fields.
667         // Note that this has the hilarious slight inefficiency of creating redundant hints for
668         // things that were previously materializations. This should only impact compile times and
669         // not code quality, and it's necessary for soundness without some data structure hackage.
670         // For example, a MaterializeNewObject that we choose to sink may have new fields added to
671         // it conditionally. That would necessitate Bottoms.
672         Node* bottom = nullptr;
673         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
674             if (block == m_graph.block(0))
675                 bottom = m_insertionSet.insertConstant(0, NodeOrigin(), jsUndefined());
676             
677             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
678                 Node* node = block->at(nodeIndex);
679                 for (PromotedHeapLocation location : m_locationsForAllocation.get(node)) {
680                     m_insertionSet.insert(
681                         nodeIndex + 1, location.createHint(m_graph, node->origin, bottom));
682                 }
683             }
684             m_insertionSet.execute(block);
685         }
686
687         m_ssaCalculator.reset();
688
689         // Collect the set of "variables" that we will be sinking.
690         m_locationToVariable.clear();
691         m_indexToLocation.clear();
692         for (PromotedHeapLocation location : locations) {
693             SSACalculator::Variable* variable = m_ssaCalculator.newVariable();
694             m_locationToVariable.add(location, variable);
695             ASSERT(m_indexToLocation.size() == variable->index());
696             m_indexToLocation.append(location);
697         }
698         
699         // Create Defs from the existing hints.
700         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
701             for (Node* node : *block) {
702                 promoteHeapAccess(
703                     node,
704                     [&] (PromotedHeapLocation location, Edge value) {
705                         if (!m_sinkCandidates.contains(location.base()))
706                             return;
707                         SSACalculator::Variable* variable = m_locationToVariable.get(location);
708                         m_ssaCalculator.newDef(variable, block, value.node());
709                     },
710                     [&] (PromotedHeapLocation) { });
711             }
712         }
713         
714         // OMG run the SSA calculator to create Phis!
715         m_ssaCalculator.computePhis(
716             [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
717                 PromotedHeapLocation location = m_indexToLocation[variable->index()];
718                 if (!m_combinedLiveness.liveAtHead[block].contains(location.base()))
719                     return nullptr;
720                 
721                 Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
722                 phiNode->mergeFlags(NodeResultJS);
723                 return phiNode;
724             });
725         
726         // Place Phis in the right places, replace all uses of any load with the appropriate
727         // value, and create the appropriate Upsilon nodes.
728         m_graph.clearReplacements();
729         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
730             // This mapping table is intended to be lazy. If something is omitted from the table,
731             // it means that there haven't been any local stores to that promoted heap location.
732             m_localMapping.clear();
733             
734             // Insert the Phi functions that we had previously created.
735             for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) {
736                 PromotedHeapLocation location = m_indexToLocation[phiDef->variable()->index()];
737                 
738                 m_insertionSet.insert(
739                     0, phiDef->value());
740                 m_insertionSet.insert(
741                     0, location.createHint(m_graph, NodeOrigin(), phiDef->value()));
742                 m_localMapping.add(location, phiDef->value());
743             }
744             
745             if (verbose)
746                 dataLog("Local mapping at ", pointerDump(block), ": ", mapDump(m_localMapping), "\n");
747             
748             // Process the block and replace all uses of loads with the promoted value.
749             for (Node* node : *block) {
750                 m_graph.performSubstitution(node);
751                 
752                 if (Node* escapee = m_materializationToEscapee.get(node))
753                     populateMaterialize(block, node, escapee);
754                 
755                 promoteHeapAccess(
756                     node,
757                     [&] (PromotedHeapLocation location, Edge value) {
758                         if (m_sinkCandidates.contains(location.base()))
759                             m_localMapping.set(location, value.node());
760                     },
761                     [&] (PromotedHeapLocation location) {
762                         if (m_sinkCandidates.contains(location.base())) {
763                             switch (node->op()) {
764                             case CheckStructure:
765                                 node->convertToCheckStructureImmediate(resolve(block, location));
766                                 break;
767
768                             default:
769                                 node->replaceWith(resolve(block, location));
770                                 break;
771                             }
772                         }
773                     });
774             }
775             
776             // Gotta drop some Upsilons.
777             NodeAndIndex terminal = block->findTerminal();
778             size_t upsilonInsertionPoint = terminal.index;
779             NodeOrigin upsilonOrigin = terminal.node->origin;
780             for (BasicBlock* successorBlock : block->successors()) {
781                 for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
782                     Node* phiNode = phiDef->value();
783                     SSACalculator::Variable* variable = phiDef->variable();
784                     PromotedHeapLocation location = m_indexToLocation[variable->index()];
785                     Node* incoming = resolve(block, location);
786                     
787                     m_insertionSet.insertNode(
788                         upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
789                         OpInfo(phiNode), incoming->defaultEdge());
790                 }
791             }
792             
793             m_insertionSet.execute(block);
794         }
795     }
796     
797     Node* resolve(BasicBlock* block, PromotedHeapLocation location)
798     {
799         if (Node* result = m_localMapping.get(location))
800             return result;
801         
802         // This implies that there is no local mapping. Find a non-local mapping.
803         SSACalculator::Def* def = m_ssaCalculator.nonLocalReachingDef(
804             block, m_locationToVariable.get(location));
805         ASSERT(def);
806         ASSERT(def->value());
807         m_localMapping.add(location, def->value());
808         return def->value();
809     }
810
811     template<typename SinkCandidateFunctor, typename EscapeFunctor>
812     void handleNode(
813         Node* node,
814         const SinkCandidateFunctor& sinkCandidate,
815         const EscapeFunctor& escape)
816     {
817         switch (node->op()) {
818         case NewObject:
819         case MaterializeNewObject:
820         case MaterializeCreateActivation:
821             sinkCandidate();
822             m_graph.doToChildren(
823                 node,
824                 [&] (Edge edge) {
825                     escape(edge.node());
826                 });
827             break;
828
829         case NewFunction:
830             if (!node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid())
831                 sinkCandidate();
832             escape(node->child1().node());
833             break;
834
835         case CreateActivation:
836             if (!m_graph.symbolTableFor(node->origin.semantic)->singletonScope()->isStillValid())
837                 sinkCandidate();
838             escape(node->child1().node());
839             break;
840
841         case Check:
842             m_graph.doToChildren(
843                 node,
844                 [&] (Edge edge) {
845                     if (edge.willNotHaveCheck())
846                         return;
847                     
848                     if (alreadyChecked(edge.useKind(), SpecObject))
849                         return;
850                     
851                     escape(edge.node());
852                 });
853             break;
854
855         case MovHint:
856         case PutHint:
857         case StoreBarrier:
858             break;
859
860         case PutStructure:
861         case CheckStructure:
862         case GetByOffset:
863         case MultiGetByOffset:
864         case GetGetterSetterByOffset: {
865             Node* target = node->child1().node();
866             if (!target->isObjectAllocation())
867                 escape(target);
868             break;
869         }
870             
871         case PutByOffset: {
872             Node* target = node->child2().node();
873             if (!target->isObjectAllocation()) {
874                 escape(target);
875                 escape(node->child1().node());
876             }
877             escape(node->child3().node());
878             break;
879         }
880
881         case PutClosureVar: {
882             Node* target = node->child1().node();
883             if (!target->isActivationAllocation())
884                 escape(target);
885             escape(node->child2().node());
886             break;
887         }
888             
889         case MultiPutByOffset:
890             // FIXME: In the future we should be able to handle this. It's just a matter of
891             // building the appropriate *Hint variant of this instruction, along with a
892             // PhantomStructureSelect node - since this transforms the Structure in a conditional
893             // way.
894             // https://bugs.webkit.org/show_bug.cgi?id=136924
895             escape(node->child1().node());
896             escape(node->child2().node());
897             break;
898
899         default:
900             m_graph.doToChildren(
901                 node,
902                 [&] (Edge edge) {
903                     escape(edge.node());
904                 });
905             break;
906         }
907     }
908     
909     Node* createMaterialize(Node* escapee, Node* where)
910     {
911         Node* result = nullptr;
912         
913         switch (escapee->op()) {
914         case NewObject:
915         case MaterializeNewObject: {
916             ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
917             
918             result = m_graph.addNode(
919                 escapee->prediction(), Node::VarArg, MaterializeNewObject,
920                 NodeOrigin(
921                     escapee->origin.semantic,
922                     where->origin.forExit),
923                 OpInfo(data), OpInfo(), 0, 0);
924             break;
925         }
926
927         case NewFunction:
928             result = m_graph.addNode(
929                 escapee->prediction(), NewFunction,
930                 NodeOrigin(
931                     escapee->origin.semantic,
932                     where->origin.forExit),
933                 OpInfo(escapee->cellOperand()),
934                 escapee->child1());
935             break;
936
937         case CreateActivation:
938         case MaterializeCreateActivation: {
939             ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
940
941             result = m_graph.addNode(
942                 escapee->prediction(), Node::VarArg, MaterializeCreateActivation,
943                 NodeOrigin(
944                     escapee->origin.semantic,
945                     where->origin.forExit),
946                 OpInfo(data), OpInfo(), 0, 0);
947             break;
948         }
949
950         default:
951             DFG_CRASH(m_graph, escapee, "Bad escapee op");
952             break;
953         }
954         
955         if (verbose)
956             dataLog("Creating materialization point at ", where, " for ", escapee, ": ", result, "\n");
957         
958         m_materializationToEscapee.add(result, escapee);
959         m_materializationSiteToMaterializations.add(
960             where, Vector<Node*>()).iterator->value.append(result);
961         
962         return result;
963     }
964     
965     void populateMaterialize(BasicBlock* block, Node* node, Node* escapee)
966     {
967         switch (node->op()) {
968         case MaterializeNewObject: {
969             ObjectMaterializationData& data = node->objectMaterializationData();
970             unsigned firstChild = m_graph.m_varArgChildren.size();
971             
972             Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
973             
974             PromotedHeapLocation structure(StructurePLoc, escapee);
975             ASSERT(locations.contains(structure));
976             
977             m_graph.m_varArgChildren.append(Edge(resolve(block, structure), KnownCellUse));
978             
979             for (unsigned i = 0; i < locations.size(); ++i) {
980                 switch (locations[i].kind()) {
981                 case StructurePLoc: {
982                     ASSERT(locations[i] == structure);
983                     break;
984                 }
985                     
986                 case NamedPropertyPLoc: {
987                     Node* value = resolve(block, locations[i]);
988                     if (value->op() == BottomValue) {
989                         // We can skip Bottoms entirely.
990                         break;
991                     }
992                     
993                     data.m_properties.append(PhantomPropertyValue(locations[i].info()));
994                     m_graph.m_varArgChildren.append(value);
995                     break;
996                 }
997                     
998                 default:
999                     DFG_CRASH(m_graph, node, "Bad location kind");
1000                 }
1001             }
1002             
1003             node->children = AdjacencyList(
1004                 AdjacencyList::Variable,
1005                 firstChild, m_graph.m_varArgChildren.size() - firstChild);
1006             break;
1007         }
1008
1009         case MaterializeCreateActivation: {
1010             ObjectMaterializationData& data = node->objectMaterializationData();
1011
1012             unsigned firstChild = m_graph.m_varArgChildren.size();
1013
1014             Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
1015
1016             PromotedHeapLocation scope(ActivationScopePLoc, escapee);
1017             ASSERT(locations.contains(scope));
1018
1019             m_graph.m_varArgChildren.append(Edge(resolve(block, scope), KnownCellUse));
1020
1021             for (unsigned i = 0; i < locations.size(); ++i) {
1022                 switch (locations[i].kind()) {
1023                 case ActivationScopePLoc: {
1024                     ASSERT(locations[i] == scope);
1025                     break;
1026                 }
1027
1028                 case ClosureVarPLoc: {
1029                     Node* value = resolve(block, locations[i]);
1030                     if (value->op() == BottomValue)
1031                         break;
1032
1033                     data.m_properties.append(PhantomPropertyValue(locations[i].info()));
1034                     m_graph.m_varArgChildren.append(value);
1035                     break;
1036                 }
1037
1038                 default:
1039                     DFG_CRASH(m_graph, node, "Bad location kind");
1040                 }
1041             }
1042
1043             node->children = AdjacencyList(
1044                 AdjacencyList::Variable,
1045                 firstChild, m_graph.m_varArgChildren.size() - firstChild);
1046             break;
1047         }
1048
1049         case NewFunction: {
1050             if (!ASSERT_DISABLED) {
1051                 Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee);
1052
1053                 ASSERT(locations.size() == 2);
1054
1055                 PromotedHeapLocation executable(FunctionExecutablePLoc, escapee);
1056                 ASSERT(locations.contains(executable));
1057
1058                 PromotedHeapLocation activation(FunctionActivationPLoc, escapee);
1059                 ASSERT(locations.contains(activation));
1060
1061                 for (unsigned i = 0; i < locations.size(); ++i) {
1062                     switch (locations[i].kind()) {
1063                     case FunctionExecutablePLoc: {
1064                         ASSERT(locations[i] == executable);
1065                         break;
1066                     }
1067
1068                     case FunctionActivationPLoc: {
1069                         ASSERT(locations[i] == activation);
1070                         break;
1071                     }
1072
1073                     default:
1074                         DFG_CRASH(m_graph, node, "Bad location kind");
1075                     }
1076                 }
1077             }
1078
1079             break;
1080         }
1081
1082         default:
1083             DFG_CRASH(m_graph, node, "Bad materialize op");
1084             break;
1085         }
1086     }
1087     
1088     CombinedLiveness m_combinedLiveness;
1089     SSACalculator m_ssaCalculator;
1090     HashSet<Node*> m_sinkCandidates;
1091     HashMap<Node*, Node*> m_materializationToEscapee;
1092     HashMap<Node*, Vector<Node*>> m_materializationSiteToMaterializations;
1093     HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation;
1094     HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
1095     Vector<PromotedHeapLocation> m_indexToLocation;
1096     HashMap<PromotedHeapLocation, Node*> m_localMapping;
1097     InsertionSet m_insertionSet;
1098 };
1099     
1100 bool performObjectAllocationSinking(Graph& graph)
1101 {
1102     SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase");
1103     return runPhase<ObjectAllocationSinkingPhase>(graph);
1104 }
1105
1106 } } // namespace JSC::DFG
1107
1108 #endif // ENABLE(DFG_JIT)
1109