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