Add WTF::move()
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGGraph.cpp
1 /*
2  * Copyright (C) 2011, 2013, 2014 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 "DFGGraph.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "BytecodeLivenessAnalysisInlines.h"
32 #include "CodeBlock.h"
33 #include "CodeBlockWithJITType.h"
34 #include "DFGClobberSet.h"
35 #include "DFGJITCode.h"
36 #include "DFGVariableAccessDataDump.h"
37 #include "FullBytecodeLiveness.h"
38 #include "FunctionExecutableDump.h"
39 #include "JIT.h"
40 #include "JSActivation.h"
41 #include "MaxFrameExtentForSlowPathCall.h"
42 #include "OperandsInlines.h"
43 #include "JSCInlines.h"
44 #include "StackAlignment.h"
45 #include <wtf/CommaPrinter.h>
46 #include <wtf/ListDump.h>
47
48 namespace JSC { namespace DFG {
49
50 // Creates an array of stringized names.
51 static const char* dfgOpNames[] = {
52 #define STRINGIZE_DFG_OP_ENUM(opcode, flags) #opcode ,
53     FOR_EACH_DFG_OP(STRINGIZE_DFG_OP_ENUM)
54 #undef STRINGIZE_DFG_OP_ENUM
55 };
56
57 Graph::Graph(VM& vm, Plan& plan, LongLivedState& longLivedState)
58     : m_vm(vm)
59     , m_plan(plan)
60     , m_codeBlock(m_plan.codeBlock.get())
61     , m_profiledBlock(m_codeBlock->alternative())
62     , m_allocator(longLivedState.m_allocator)
63     , m_mustHandleAbstractValues(OperandsLike, plan.mustHandleValues)
64     , m_hasArguments(false)
65     , m_nextMachineLocal(0)
66     , m_machineCaptureStart(std::numeric_limits<int>::max())
67     , m_fixpointState(BeforeFixpoint)
68     , m_form(LoadStore)
69     , m_unificationState(LocallyUnified)
70     , m_refCountState(EverythingIsLive)
71 {
72     ASSERT(m_profiledBlock);
73     
74     for (unsigned i = m_mustHandleAbstractValues.size(); i--;)
75         m_mustHandleAbstractValues[i].setMostSpecific(*this, plan.mustHandleValues[i]);
76 }
77
78 Graph::~Graph()
79 {
80     m_allocator.freeAll();
81 }
82
83 const char *Graph::opName(NodeType op)
84 {
85     return dfgOpNames[op];
86 }
87
88 static void printWhiteSpace(PrintStream& out, unsigned amount)
89 {
90     while (amount-- > 0)
91         out.print(" ");
92 }
93
94 bool Graph::dumpCodeOrigin(PrintStream& out, const char* prefix, Node* previousNode, Node* currentNode, DumpContext* context)
95 {
96     if (!previousNode)
97         return false;
98     
99     if (previousNode->origin.semantic.inlineCallFrame == currentNode->origin.semantic.inlineCallFrame)
100         return false;
101     
102     Vector<CodeOrigin> previousInlineStack = previousNode->origin.semantic.inlineStack();
103     Vector<CodeOrigin> currentInlineStack = currentNode->origin.semantic.inlineStack();
104     unsigned commonSize = std::min(previousInlineStack.size(), currentInlineStack.size());
105     unsigned indexOfDivergence = commonSize;
106     for (unsigned i = 0; i < commonSize; ++i) {
107         if (previousInlineStack[i].inlineCallFrame != currentInlineStack[i].inlineCallFrame) {
108             indexOfDivergence = i;
109             break;
110         }
111     }
112     
113     bool hasPrinted = false;
114     
115     // Print the pops.
116     for (unsigned i = previousInlineStack.size(); i-- > indexOfDivergence;) {
117         out.print(prefix);
118         printWhiteSpace(out, i * 2);
119         out.print("<-- ", inContext(*previousInlineStack[i].inlineCallFrame, context), "\n");
120         hasPrinted = true;
121     }
122     
123     // Print the pushes.
124     for (unsigned i = indexOfDivergence; i < currentInlineStack.size(); ++i) {
125         out.print(prefix);
126         printWhiteSpace(out, i * 2);
127         out.print("--> ", inContext(*currentInlineStack[i].inlineCallFrame, context), "\n");
128         hasPrinted = true;
129     }
130     
131     return hasPrinted;
132 }
133
134 int Graph::amountOfNodeWhiteSpace(Node* node)
135 {
136     return (node->origin.semantic.inlineDepth() - 1) * 2;
137 }
138
139 void Graph::printNodeWhiteSpace(PrintStream& out, Node* node)
140 {
141     printWhiteSpace(out, amountOfNodeWhiteSpace(node));
142 }
143
144 void Graph::dump(PrintStream& out, const char* prefix, Node* node, DumpContext* context)
145 {
146     NodeType op = node->op();
147
148     unsigned refCount = node->refCount();
149     bool skipped = !refCount;
150     bool mustGenerate = node->mustGenerate();
151     if (mustGenerate)
152         --refCount;
153
154     out.print(prefix);
155     printNodeWhiteSpace(out, node);
156
157     // Example/explanation of dataflow dump output
158     //
159     //   14:   <!2:7>  GetByVal(@3, @13)
160     //   ^1     ^2 ^3     ^4       ^5
161     //
162     // (1) The nodeIndex of this operation.
163     // (2) The reference count. The number printed is the 'real' count,
164     //     not including the 'mustGenerate' ref. If the node is
165     //     'mustGenerate' then the count it prefixed with '!'.
166     // (3) The virtual register slot assigned to this node.
167     // (4) The name of the operation.
168     // (5) The arguments to the operation. The may be of the form:
169     //         @#   - a NodeIndex referencing a prior node in the graph.
170     //         arg# - an argument number.
171     //         $#   - the index in the CodeBlock of a constant { for numeric constants the value is displayed | for integers, in both decimal and hex }.
172     //         id#  - the index in the CodeBlock of an identifier { if codeBlock is passed to dump(), the string representation is displayed }.
173     //         var# - the index of a var on the global object, used by GetGlobalVar/PutGlobalVar operations.
174     out.printf("% 4d:%s<%c%u:", (int)node->index(), skipped ? "  skipped  " : "           ", mustGenerate ? '!' : ' ', refCount);
175     if (node->hasResult() && !skipped && node->hasVirtualRegister())
176         out.print(node->virtualRegister());
177     else
178         out.print("-");
179     out.print(">\t", opName(op), "(");
180     CommaPrinter comma;
181     if (node->flags() & NodeHasVarArgs) {
182         for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
183             if (!m_varArgChildren[childIdx])
184                 continue;
185             out.print(comma, m_varArgChildren[childIdx]);
186         }
187     } else {
188         if (!!node->child1() || !!node->child2() || !!node->child3())
189             out.print(comma, node->child1());
190         if (!!node->child2() || !!node->child3())
191             out.print(comma, node->child2());
192         if (!!node->child3())
193             out.print(comma, node->child3());
194     }
195
196     if (toCString(NodeFlagsDump(node->flags())) != "<empty>")
197         out.print(comma, NodeFlagsDump(node->flags()));
198     if (node->prediction())
199         out.print(comma, SpeculationDump(node->prediction()));
200     if (node->hasArrayMode())
201         out.print(comma, node->arrayMode());
202     if (node->hasArithMode())
203         out.print(comma, node->arithMode());
204     if (node->hasVarNumber())
205         out.print(comma, node->varNumber());
206     if (node->hasRegisterPointer())
207         out.print(comma, "global", globalObjectFor(node->origin.semantic)->findRegisterIndex(node->registerPointer()), "(", RawPointer(node->registerPointer()), ")");
208     if (node->hasIdentifier())
209         out.print(comma, "id", node->identifierNumber(), "{", identifiers()[node->identifierNumber()], "}");
210     if (node->hasStructureSet())
211         out.print(comma, inContext(node->structureSet(), context));
212     if (node->hasStructure())
213         out.print(comma, inContext(*node->structure(), context));
214     if (node->hasStructureTransitionData())
215         out.print(comma, inContext(*node->structureTransitionData().previousStructure, context), " -> ", inContext(*node->structureTransitionData().newStructure, context));
216     if (node->hasFunction()) {
217         out.print(comma, "function(", RawPointer(node->function()), ", ");
218         if (node->function()->inherits(JSFunction::info())) {
219             JSFunction* function = jsCast<JSFunction*>(node->function());
220             if (function->isHostFunction())
221                 out.print("<host function>");
222             else
223                 out.print(FunctionExecutableDump(function->jsExecutable()));
224         } else
225             out.print("<not JSFunction>");
226         out.print(")");
227     }
228     if (node->hasExecutable()) {
229         if (node->executable()->inherits(FunctionExecutable::info()))
230             out.print(comma, "executable(", FunctionExecutableDump(jsCast<FunctionExecutable*>(node->executable())), ")");
231         else
232             out.print(comma, "executable(not function: ", RawPointer(node->executable()), ")");
233     }
234     if (node->hasFunctionDeclIndex()) {
235         FunctionExecutable* executable = m_codeBlock->functionDecl(node->functionDeclIndex());
236         out.print(comma, FunctionExecutableDump(executable));
237     }
238     if (node->hasFunctionExprIndex()) {
239         FunctionExecutable* executable = m_codeBlock->functionExpr(node->functionExprIndex());
240         out.print(comma, FunctionExecutableDump(executable));
241     }
242     if (node->hasStorageAccessData()) {
243         StorageAccessData& storageAccessData = m_storageAccessData[node->storageAccessDataIndex()];
244         out.print(comma, "id", storageAccessData.identifierNumber, "{", identifiers()[storageAccessData.identifierNumber], "}");
245         out.print(", ", static_cast<ptrdiff_t>(storageAccessData.offset));
246     }
247     if (node->hasMultiGetByOffsetData()) {
248         MultiGetByOffsetData& data = node->multiGetByOffsetData();
249         out.print(comma, "id", data.identifierNumber, "{", identifiers()[data.identifierNumber], "}");
250         for (unsigned i = 0; i < data.variants.size(); ++i)
251             out.print(comma, inContext(data.variants[i], context));
252     }
253     if (node->hasMultiPutByOffsetData()) {
254         MultiPutByOffsetData& data = node->multiPutByOffsetData();
255         out.print(comma, "id", data.identifierNumber, "{", identifiers()[data.identifierNumber], "}");
256         for (unsigned i = 0; i < data.variants.size(); ++i)
257             out.print(comma, inContext(data.variants[i], context));
258     }
259     ASSERT(node->hasVariableAccessData(*this) == node->hasLocal(*this));
260     if (node->hasVariableAccessData(*this)) {
261         VariableAccessData* variableAccessData = node->tryGetVariableAccessData();
262         if (variableAccessData) {
263             VirtualRegister operand = variableAccessData->local();
264             if (operand.isArgument())
265                 out.print(comma, "arg", operand.toArgument(), "(", VariableAccessDataDump(*this, variableAccessData), ")");
266             else
267                 out.print(comma, "loc", operand.toLocal(), "(", VariableAccessDataDump(*this, variableAccessData), ")");
268             
269             operand = variableAccessData->machineLocal();
270             if (operand.isValid()) {
271                 if (operand.isArgument())
272                     out.print(comma, "machine:arg", operand.toArgument());
273                 else
274                     out.print(comma, "machine:loc", operand.toLocal());
275             }
276         }
277     }
278     if (node->hasUnlinkedLocal()) {
279         VirtualRegister operand = node->unlinkedLocal();
280         if (operand.isArgument())
281             out.print(comma, "arg", operand.toArgument());
282         else
283             out.print(comma, "loc", operand.toLocal());
284     }
285     if (node->hasUnlinkedMachineLocal()) {
286         VirtualRegister operand = node->unlinkedMachineLocal();
287         if (operand.isValid()) {
288             if (operand.isArgument())
289                 out.print(comma, "machine:arg", operand.toArgument());
290             else
291                 out.print(comma, "machine:loc", operand.toLocal());
292         }
293     }
294     if (node->hasConstantBuffer()) {
295         out.print(comma);
296         out.print(node->startConstant(), ":[");
297         CommaPrinter anotherComma;
298         for (unsigned i = 0; i < node->numConstants(); ++i)
299             out.print(anotherComma, inContext(m_codeBlock->constantBuffer(node->startConstant())[i], context));
300         out.print("]");
301     }
302     if (node->hasIndexingType())
303         out.print(comma, IndexingTypeDump(node->indexingType()));
304     if (node->hasTypedArrayType())
305         out.print(comma, node->typedArrayType());
306     if (node->hasPhi())
307         out.print(comma, "^", node->phi()->index());
308     if (node->hasExecutionCounter())
309         out.print(comma, RawPointer(node->executionCounter()));
310     if (node->hasVariableWatchpointSet())
311         out.print(comma, RawPointer(node->variableWatchpointSet()));
312     if (node->hasTypedArray())
313         out.print(comma, inContext(JSValue(node->typedArray()), context));
314     if (node->hasStoragePointer())
315         out.print(comma, RawPointer(node->storagePointer()));
316     if (node->isConstant()) {
317         out.print(comma, "$", node->constantNumber());
318         JSValue value = valueOfJSConstant(node);
319         out.print(" = ", inContext(value, context));
320     }
321     if (op == WeakJSConstant)
322         out.print(comma, RawPointer(node->weakConstant()), " (", inContext(*node->weakConstant()->structure(), context), ")");
323     if (node->isJump())
324         out.print(comma, "T:", *node->targetBlock());
325     if (node->isBranch())
326         out.print(comma, "T:", node->branchData()->taken, ", F:", node->branchData()->notTaken);
327     if (node->isSwitch()) {
328         SwitchData* data = node->switchData();
329         out.print(comma, data->kind);
330         for (unsigned i = 0; i < data->cases.size(); ++i)
331             out.print(comma, inContext(data->cases[i].value, context), ":", data->cases[i].target);
332         out.print(comma, "default:", data->fallThrough);
333     }
334     ClobberSet reads;
335     ClobberSet writes;
336     addReadsAndWrites(*this, node, reads, writes);
337     if (!reads.isEmpty())
338         out.print(comma, "R:", sortedListDump(reads.direct(), ","));
339     if (!writes.isEmpty())
340         out.print(comma, "W:", sortedListDump(writes.direct(), ","));
341     out.print(comma, "bc#", node->origin.semantic.bytecodeIndex);
342     if (node->origin.semantic != node->origin.forExit)
343         out.print(comma, "exit: ", node->origin.forExit);
344     
345     out.print(")");
346
347     if (!skipped) {
348         if (node->hasVariableAccessData(*this) && node->tryGetVariableAccessData())
349             out.print("  predicting ", SpeculationDump(node->tryGetVariableAccessData()->prediction()));
350         else if (node->hasHeapPrediction())
351             out.print("  predicting ", SpeculationDump(node->getHeapPrediction()));
352     }
353     
354     out.print("\n");
355 }
356
357 void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* block, PhiNodeDumpMode phiNodeDumpMode, DumpContext* context)
358 {
359     out.print(prefix, "Block ", *block, " (", inContext(block->at(0)->origin.semantic, context), "): ", block->isReachable ? "" : "(skipped)", block->isOSRTarget ? " (OSR target)" : "", "\n");
360     if (block->executionCount == block->executionCount)
361         out.print(prefix, "  Execution count: ", block->executionCount, "\n");
362     out.print(prefix, "  Predecessors:");
363     for (size_t i = 0; i < block->predecessors.size(); ++i)
364         out.print(" ", *block->predecessors[i]);
365     out.print("\n");
366     if (m_dominators.isValid()) {
367         out.print(prefix, "  Dominated by:");
368         for (size_t i = 0; i < m_blocks.size(); ++i) {
369             if (!m_dominators.dominates(i, block->index))
370                 continue;
371             out.print(" #", i);
372         }
373         out.print("\n");
374         out.print(prefix, "  Dominates:");
375         for (size_t i = 0; i < m_blocks.size(); ++i) {
376             if (!m_dominators.dominates(block->index, i))
377                 continue;
378             out.print(" #", i);
379         }
380         out.print("\n");
381     }
382     if (m_naturalLoops.isValid()) {
383         if (const NaturalLoop* loop = m_naturalLoops.headerOf(block)) {
384             out.print(prefix, "  Loop header, contains:");
385             Vector<BlockIndex> sortedBlockList;
386             for (unsigned i = 0; i < loop->size(); ++i)
387                 sortedBlockList.append(loop->at(i)->index);
388             std::sort(sortedBlockList.begin(), sortedBlockList.end());
389             for (unsigned i = 0; i < sortedBlockList.size(); ++i)
390                 out.print(" #", sortedBlockList[i]);
391             out.print("\n");
392         }
393         
394         Vector<const NaturalLoop*> containingLoops =
395             m_naturalLoops.loopsOf(block);
396         if (!containingLoops.isEmpty()) {
397             out.print(prefix, "  Containing loop headers:");
398             for (unsigned i = 0; i < containingLoops.size(); ++i)
399                 out.print(" ", *containingLoops[i]->header());
400             out.print("\n");
401         }
402     }
403     if (!block->phis.isEmpty()) {
404         out.print(prefix, "  Phi Nodes:");
405         for (size_t i = 0; i < block->phis.size(); ++i) {
406             Node* phiNode = block->phis[i];
407             if (!phiNode->shouldGenerate() && phiNodeDumpMode == DumpLivePhisOnly)
408                 continue;
409             out.print(" @", phiNode->index(), "<", phiNode->refCount(), ">->(");
410             if (phiNode->child1()) {
411                 out.print("@", phiNode->child1()->index());
412                 if (phiNode->child2()) {
413                     out.print(", @", phiNode->child2()->index());
414                     if (phiNode->child3())
415                         out.print(", @", phiNode->child3()->index());
416                 }
417             }
418             out.print(")", i + 1 < block->phis.size() ? "," : "");
419         }
420         out.print("\n");
421     }
422 }
423
424 void Graph::dump(PrintStream& out, DumpContext* context)
425 {
426     DumpContext myContext;
427     myContext.graph = this;
428     if (!context)
429         context = &myContext;
430     
431     dataLog("\n");
432     dataLog("DFG for ", CodeBlockWithJITType(m_codeBlock, JITCode::DFGJIT), ":\n");
433     dataLog("  Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "; Ref count state: ", m_refCountState, "\n");
434     dataLog("\n");
435     
436     Node* lastNode = 0;
437     for (size_t b = 0; b < m_blocks.size(); ++b) {
438         BasicBlock* block = m_blocks[b].get();
439         if (!block)
440             continue;
441         dumpBlockHeader(out, "", block, DumpAllPhis, context);
442         switch (m_form) {
443         case LoadStore:
444         case ThreadedCPS: {
445             out.print("  vars before: ");
446             if (block->cfaHasVisited)
447                 out.print(inContext(block->valuesAtHead, context));
448             else
449                 out.print("<empty>");
450             out.print("\n");
451             out.print("  var links: ", block->variablesAtHead, "\n");
452             break;
453         }
454             
455         case SSA: {
456             RELEASE_ASSERT(block->ssa);
457             out.print("  Availability: ", block->ssa->availabilityAtHead, "\n");
458             out.print("  Live: ", nodeListDump(block->ssa->liveAtHead), "\n");
459             out.print("  Values: ", nodeMapDump(block->ssa->valuesAtHead, context), "\n");
460             break;
461         } }
462         for (size_t i = 0; i < block->size(); ++i) {
463             dumpCodeOrigin(out, "", lastNode, block->at(i), context);
464             dump(out, "", block->at(i), context);
465             lastNode = block->at(i);
466         }
467         switch (m_form) {
468         case LoadStore:
469         case ThreadedCPS: {
470             out.print("  vars after: ");
471             if (block->cfaHasVisited)
472                 out.print(inContext(block->valuesAtTail, context));
473             else
474                 out.print("<empty>");
475             out.print("\n");
476             out.print("  var links: ", block->variablesAtTail, "\n");
477             break;
478         }
479             
480         case SSA: {
481             RELEASE_ASSERT(block->ssa);
482             out.print("  Availability: ", block->ssa->availabilityAtTail, "\n");
483             out.print("  Live: ", nodeListDump(block->ssa->liveAtTail), "\n");
484             out.print("  Values: ", nodeMapDump(block->ssa->valuesAtTail, context), "\n");
485             break;
486         } }
487         dataLog("\n");
488     }
489     
490     if (!myContext.isEmpty()) {
491         myContext.dump(WTF::dataFile());
492         dataLog("\n");
493     }
494 }
495
496 void Graph::dethread()
497 {
498     if (m_form == LoadStore || m_form == SSA)
499         return;
500     
501     if (logCompilationChanges())
502         dataLog("Dethreading DFG graph.\n");
503     
504     SamplingRegion samplingRegion("DFG Dethreading");
505     
506     for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) {
507         BasicBlock* block = m_blocks[blockIndex].get();
508         if (!block)
509             continue;
510         for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
511             Node* phi = block->phis[phiIndex];
512             phi->children.reset();
513         }
514     }
515     
516     m_form = LoadStore;
517 }
518
519 void Graph::handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock* block, BasicBlock* successor)
520 {
521     if (!successor->isReachable) {
522         successor->isReachable = true;
523         worklist.append(successor);
524     }
525     
526     successor->predecessors.append(block);
527 }
528
529 void Graph::determineReachability()
530 {
531     Vector<BasicBlock*, 16> worklist;
532     worklist.append(block(0));
533     block(0)->isReachable = true;
534     while (!worklist.isEmpty()) {
535         BasicBlock* block = worklist.takeLast();
536         for (unsigned i = block->numSuccessors(); i--;)
537             handleSuccessor(worklist, block, block->successor(i));
538     }
539 }
540
541 void Graph::resetReachability()
542 {
543     for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) {
544         BasicBlock* block = m_blocks[blockIndex].get();
545         if (!block)
546             continue;
547         block->isReachable = false;
548         block->predecessors.clear();
549     }
550     
551     determineReachability();
552 }
553
554 void Graph::killBlockAndItsContents(BasicBlock* block)
555 {
556     for (unsigned phiIndex = block->phis.size(); phiIndex--;)
557         m_allocator.free(block->phis[phiIndex]);
558     for (unsigned nodeIndex = block->size(); nodeIndex--;)
559         m_allocator.free(block->at(nodeIndex));
560     
561     killBlock(block);
562 }
563
564 void Graph::killUnreachableBlocks()
565 {
566     for (BlockIndex blockIndex = 0; blockIndex < numBlocks(); ++blockIndex) {
567         BasicBlock* block = this->block(blockIndex);
568         if (!block)
569             continue;
570         if (block->isReachable)
571             continue;
572         
573         killBlockAndItsContents(block);
574     }
575 }
576
577 void Graph::resetExitStates()
578 {
579     for (BlockIndex blockIndex = 0; blockIndex < m_blocks.size(); ++blockIndex) {
580         BasicBlock* block = m_blocks[blockIndex].get();
581         if (!block)
582             continue;
583         for (unsigned indexInBlock = block->size(); indexInBlock--;)
584             block->at(indexInBlock)->setCanExit(true);
585     }
586 }
587
588 void Graph::invalidateCFG()
589 {
590     m_dominators.invalidate();
591     m_naturalLoops.invalidate();
592 }
593
594 void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
595 {
596     if (variableAccessData->isCaptured()) {
597         // Let CSE worry about this one.
598         return;
599     }
600     for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
601         Node* node = block[indexInBlock];
602         bool shouldContinue = true;
603         switch (node->op()) {
604         case SetLocal: {
605             if (node->local() == variableAccessData->local())
606                 shouldContinue = false;
607             break;
608         }
609                 
610         case GetLocal: {
611             if (node->variableAccessData() != variableAccessData)
612                 continue;
613             substitute(block, indexInBlock, node, newGetLocal);
614             Node* oldTailNode = block.variablesAtTail.operand(variableAccessData->local());
615             if (oldTailNode == node)
616                 block.variablesAtTail.operand(variableAccessData->local()) = newGetLocal;
617             shouldContinue = false;
618             break;
619         }
620                 
621         default:
622             break;
623         }
624         if (!shouldContinue)
625             break;
626     }
627 }
628
629 void Graph::addForDepthFirstSort(Vector<BasicBlock*>& result, Vector<BasicBlock*, 16>& worklist, HashSet<BasicBlock*>& seen, BasicBlock* block)
630 {
631     if (seen.contains(block))
632         return;
633     
634     result.append(block);
635     worklist.append(block);
636     seen.add(block);
637 }
638
639 void Graph::getBlocksInDepthFirstOrder(Vector<BasicBlock*>& result)
640 {
641     Vector<BasicBlock*, 16> worklist;
642     HashSet<BasicBlock*> seen;
643     addForDepthFirstSort(result, worklist, seen, block(0));
644     while (!worklist.isEmpty()) {
645         BasicBlock* block = worklist.takeLast();
646         for (unsigned i = block->numSuccessors(); i--;)
647             addForDepthFirstSort(result, worklist, seen, block->successor(i));
648     }
649 }
650
651 void Graph::clearReplacements()
652 {
653     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
654         BasicBlock* block = m_blocks[blockIndex].get();
655         if (!block)
656             continue;
657         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
658             block->phis[phiIndex]->misc.replacement = 0;
659         for (unsigned nodeIndex = block->size(); nodeIndex--;)
660             block->at(nodeIndex)->misc.replacement = 0;
661     }
662 }
663
664 void Graph::initializeNodeOwners()
665 {
666     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
667         BasicBlock* block = m_blocks[blockIndex].get();
668         if (!block)
669             continue;
670         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
671             block->phis[phiIndex]->misc.owner = block;
672         for (unsigned nodeIndex = block->size(); nodeIndex--;)
673             block->at(nodeIndex)->misc.owner = block;
674     }
675 }
676
677 void Graph::clearFlagsOnAllNodes(NodeFlags flags)
678 {
679     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
680         BasicBlock* block = m_blocks[blockIndex].get();
681         if (!block)
682             continue;
683         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
684             block->phis[phiIndex]->clearFlags(flags);
685         for (unsigned nodeIndex = block->size(); nodeIndex--;)
686             block->at(nodeIndex)->clearFlags(flags);
687     }
688 }
689
690 FullBytecodeLiveness& Graph::livenessFor(CodeBlock* codeBlock)
691 {
692     HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>>::iterator iter = m_bytecodeLiveness.find(codeBlock);
693     if (iter != m_bytecodeLiveness.end())
694         return *iter->value;
695     
696     std::unique_ptr<FullBytecodeLiveness> liveness = std::make_unique<FullBytecodeLiveness>();
697     codeBlock->livenessAnalysis().computeFullLiveness(*liveness);
698     FullBytecodeLiveness& result = *liveness;
699     m_bytecodeLiveness.add(codeBlock, WTF::move(liveness));
700     return result;
701 }
702
703 FullBytecodeLiveness& Graph::livenessFor(InlineCallFrame* inlineCallFrame)
704 {
705     return livenessFor(baselineCodeBlockFor(inlineCallFrame));
706 }
707
708 bool Graph::isLiveInBytecode(VirtualRegister operand, CodeOrigin codeOrigin)
709 {
710     for (;;) {
711         VirtualRegister reg = VirtualRegister(
712             operand.offset() - codeOrigin.stackOffset());
713         
714         if (operand.offset() < codeOrigin.stackOffset() + JSStack::CallFrameHeaderSize) {
715             if (reg.isArgument()) {
716                 RELEASE_ASSERT(reg.offset() < JSStack::CallFrameHeaderSize);
717                 
718                 if (!codeOrigin.inlineCallFrame->isClosureCall)
719                     return false;
720                 
721                 if (reg.offset() == JSStack::Callee)
722                     return true;
723                 if (reg.offset() == JSStack::ScopeChain)
724                     return true;
725                 
726                 return false;
727             }
728             
729             return livenessFor(codeOrigin.inlineCallFrame).operandIsLive(
730                 reg.offset(), codeOrigin.bytecodeIndex);
731         }
732         
733         InlineCallFrame* inlineCallFrame = codeOrigin.inlineCallFrame;
734         if (!inlineCallFrame)
735             break;
736
737         // Arguments are always live. This would be redundant if it wasn't for our
738         // op_call_varargs inlining.
739         // FIXME: 'this' might not be live, but we don't have a way of knowing.
740         // https://bugs.webkit.org/show_bug.cgi?id=128519
741         if (reg.isArgument()
742             && static_cast<size_t>(reg.toArgument()) < inlineCallFrame->arguments.size())
743             return true;
744         
745         codeOrigin = inlineCallFrame->caller;
746     }
747     
748     return true;
749 }
750
751 unsigned Graph::frameRegisterCount()
752 {
753     unsigned result = m_nextMachineLocal + std::max(m_parameterSlots, static_cast<unsigned>(maxFrameExtentForSlowPathCallInRegisters));
754     return roundLocalRegisterCountForFramePointerOffset(result);
755 }
756
757 unsigned Graph::stackPointerOffset()
758 {
759     return virtualRegisterForLocal(frameRegisterCount() - 1).offset();
760 }
761
762 unsigned Graph::requiredRegisterCountForExit()
763 {
764     unsigned count = JIT::frameRegisterCountFor(m_profiledBlock);
765     for (InlineCallFrameSet::iterator iter = m_plan.inlineCallFrames->begin(); !!iter; ++iter) {
766         InlineCallFrame* inlineCallFrame = *iter;
767         CodeBlock* codeBlock = baselineCodeBlockForInlineCallFrame(inlineCallFrame);
768         unsigned requiredCount = VirtualRegister(inlineCallFrame->stackOffset).toLocal() + 1 + JIT::frameRegisterCountFor(codeBlock);
769         count = std::max(count, requiredCount);
770     }
771     return count;
772 }
773
774 unsigned Graph::requiredRegisterCountForExecutionAndExit()
775 {
776     return std::max(frameRegisterCount(), requiredRegisterCountForExit());
777 }
778
779 JSActivation* Graph::tryGetActivation(Node* node)
780 {
781     if (!node->hasConstant())
782         return 0;
783     return jsDynamicCast<JSActivation*>(valueOfJSConstant(node));
784 }
785
786 WriteBarrierBase<Unknown>* Graph::tryGetRegisters(Node* node)
787 {
788     JSActivation* activation = tryGetActivation(node);
789     if (!activation)
790         return 0;
791     if (!activation->isTornOff())
792         return 0;
793     return activation->registers();
794 }
795
796 JSArrayBufferView* Graph::tryGetFoldableView(Node* node)
797 {
798     if (!node->hasConstant())
799         return 0;
800     JSArrayBufferView* view = jsDynamicCast<JSArrayBufferView*>(valueOfJSConstant(node));
801     if (!view)
802         return 0;
803     if (!watchpoints().isStillValid(view))
804         return 0;
805     return view;
806 }
807
808 JSArrayBufferView* Graph::tryGetFoldableView(Node* node, ArrayMode arrayMode)
809 {
810     if (arrayMode.typedArrayType() == NotTypedArray)
811         return 0;
812     return tryGetFoldableView(node);
813 }
814
815 JSArrayBufferView* Graph::tryGetFoldableViewForChild1(Node* node)
816 {
817     return tryGetFoldableView(child(node, 0).node(), node->arrayMode());
818 }
819
820 void Graph::visitChildren(SlotVisitor& visitor)
821 {
822     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
823         BasicBlock* block = this->block(blockIndex);
824         if (!block)
825             continue;
826         
827         for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
828             Node* node = block->at(nodeIndex);
829             
830             switch (node->op()) {
831             case JSConstant:
832             case WeakJSConstant:
833                 visitor.appendUnbarrieredReadOnlyValue(valueOfJSConstant(node));
834                 break;
835                 
836             case CheckFunction:
837                 visitor.appendUnbarrieredReadOnlyPointer(node->function());
838                 break;
839                 
840             case CheckExecutable:
841                 visitor.appendUnbarrieredReadOnlyPointer(node->executable());
842                 break;
843                 
844             case CheckStructure:
845                 for (unsigned i = node->structureSet().size(); i--;)
846                     visitor.appendUnbarrieredReadOnlyPointer(node->structureSet()[i]);
847                 break;
848                 
849             case StructureTransitionWatchpoint:
850             case NewObject:
851             case ArrayifyToStructure:
852             case NewStringObject:
853                 visitor.appendUnbarrieredReadOnlyPointer(node->structure());
854                 break;
855                 
856             case PutStructure:
857             case PhantomPutStructure:
858             case AllocatePropertyStorage:
859             case ReallocatePropertyStorage:
860                 visitor.appendUnbarrieredReadOnlyPointer(
861                     node->structureTransitionData().previousStructure);
862                 visitor.appendUnbarrieredReadOnlyPointer(
863                     node->structureTransitionData().newStructure);
864                 break;
865                 
866             default:
867                 break;
868             }
869         }
870     }
871 }
872
873 } } // namespace JSC::DFG
874
875 #endif // ENABLE(DFG_JIT)