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
48namespace JSC { namespace DFG {
49
50// Creates an array of stringized names.
51static 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
57Graph::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
78Graph::~Graph()
79{
80    m_allocator.freeAll();
81}
82
83const char *Graph::opName(NodeType op)
84{
85    return dfgOpNames[op];
86}
87
88static void printWhiteSpace(PrintStream& out, unsigned amount)
89{
90    while (amount-- > 0)
91        out.print(" ");
92}
93
94bool 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
134int Graph::amountOfNodeWhiteSpace(Node* node)
135{
136    return (node->origin.semantic.inlineDepth() - 1) * 2;
137}
138
139void Graph::printNodeWhiteSpace(PrintStream& out, Node* node)
140{
141    printWhiteSpace(out, amountOfNodeWhiteSpace(node));
142}
143
144void 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
357void 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
424void 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
496void 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
519void 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
529void 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
541void 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
554void 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
564void 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
577void 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
588void Graph::invalidateCFG()
589{
590    m_dominators.invalidate();
591    m_naturalLoops.invalidate();
592}
593
594void 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
629void 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
639void 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
651void 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
664void 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
677void 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
690FullBytecodeLiveness& 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
703FullBytecodeLiveness& Graph::livenessFor(InlineCallFrame* inlineCallFrame)
704{
705    return livenessFor(baselineCodeBlockFor(inlineCallFrame));
706}
707
708bool 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
751unsigned Graph::frameRegisterCount()
752{
753    unsigned result = m_nextMachineLocal + std::max(m_parameterSlots, static_cast<unsigned>(maxFrameExtentForSlowPathCallInRegisters));
754    return roundLocalRegisterCountForFramePointerOffset(result);
755}
756
757unsigned Graph::stackPointerOffset()
758{
759    return virtualRegisterForLocal(frameRegisterCount() - 1).offset();
760}
761
762unsigned 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
774unsigned Graph::requiredRegisterCountForExecutionAndExit()
775{
776    return std::max(frameRegisterCount(), requiredRegisterCountForExit());
777}
778
779JSActivation* Graph::tryGetActivation(Node* node)
780{
781    if (!node->hasConstant())
782        return 0;
783    return jsDynamicCast<JSActivation*>(valueOfJSConstant(node));
784}
785
786WriteBarrierBase<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
796JSArrayBufferView* 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
808JSArrayBufferView* Graph::tryGetFoldableView(Node* node, ArrayMode arrayMode)
809{
810    if (arrayMode.typedArrayType() == NotTypedArray)
811        return 0;
812    return tryGetFoldableView(node);
813}
814
815JSArrayBufferView* Graph::tryGetFoldableViewForChild1(Node* node)
816{
817    return tryGetFoldableView(child(node, 0).node(), node->arrayMode());
818}
819
820void 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)
876