fourthTier: Rationalize Node::replacement
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGGraph.cpp
1 /*
2  * Copyright (C) 2011, 2013 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 #include "CodeBlock.h"
30 #include "CodeBlockWithJITType.h"
31 #include "DFGVariableAccessDataDump.h"
32 #include "FunctionExecutableDump.h"
33 #include "Operations.h"
34 #include <wtf/CommaPrinter.h>
35 #include <wtf/ListDump.h>
36
37 #if ENABLE(DFG_JIT)
38
39 namespace JSC { namespace DFG {
40
41 // Creates an array of stringized names.
42 static const char* dfgOpNames[] = {
43 #define STRINGIZE_DFG_OP_ENUM(opcode, flags) #opcode ,
44     FOR_EACH_DFG_OP(STRINGIZE_DFG_OP_ENUM)
45 #undef STRINGIZE_DFG_OP_ENUM
46 };
47
48 Graph::Graph(VM& vm, Plan& plan, LongLivedState& longLivedState)
49     : m_vm(vm)
50     , m_plan(plan)
51     , m_codeBlock(m_plan.codeBlock.get())
52     , m_profiledBlock(m_codeBlock->alternative())
53     , m_allocator(longLivedState.m_allocator)
54     , m_hasArguments(false)
55     , m_fixpointState(BeforeFixpoint)
56     , m_form(LoadStore)
57     , m_unificationState(LocallyUnified)
58     , m_refCountState(EverythingIsLive)
59 {
60     ASSERT(m_profiledBlock);
61 }
62
63 Graph::~Graph()
64 {
65     m_allocator.freeAll();
66 }
67
68 const char *Graph::opName(NodeType op)
69 {
70     return dfgOpNames[op];
71 }
72
73 static void printWhiteSpace(PrintStream& out, unsigned amount)
74 {
75     while (amount-- > 0)
76         out.print(" ");
77 }
78
79 bool Graph::dumpCodeOrigin(PrintStream& out, const char* prefix, Node* previousNode, Node* currentNode)
80 {
81     if (!previousNode)
82         return false;
83     
84     if (previousNode->codeOrigin.inlineCallFrame == currentNode->codeOrigin.inlineCallFrame)
85         return false;
86     
87     Vector<CodeOrigin> previousInlineStack = previousNode->codeOrigin.inlineStack();
88     Vector<CodeOrigin> currentInlineStack = currentNode->codeOrigin.inlineStack();
89     unsigned commonSize = std::min(previousInlineStack.size(), currentInlineStack.size());
90     unsigned indexOfDivergence = commonSize;
91     for (unsigned i = 0; i < commonSize; ++i) {
92         if (previousInlineStack[i].inlineCallFrame != currentInlineStack[i].inlineCallFrame) {
93             indexOfDivergence = i;
94             break;
95         }
96     }
97     
98     bool hasPrinted = false;
99     
100     // Print the pops.
101     for (unsigned i = previousInlineStack.size(); i-- > indexOfDivergence;) {
102         out.print(prefix);
103         printWhiteSpace(out, i * 2);
104         out.print("<-- ", *previousInlineStack[i].inlineCallFrame, "\n");
105         hasPrinted = true;
106     }
107     
108     // Print the pushes.
109     for (unsigned i = indexOfDivergence; i < currentInlineStack.size(); ++i) {
110         out.print(prefix);
111         printWhiteSpace(out, i * 2);
112         out.print("--> ", *currentInlineStack[i].inlineCallFrame, "\n");
113         hasPrinted = true;
114     }
115     
116     return hasPrinted;
117 }
118
119 int Graph::amountOfNodeWhiteSpace(Node* node)
120 {
121     return (node->codeOrigin.inlineDepth() - 1) * 2;
122 }
123
124 void Graph::printNodeWhiteSpace(PrintStream& out, Node* node)
125 {
126     printWhiteSpace(out, amountOfNodeWhiteSpace(node));
127 }
128
129 void Graph::dump(PrintStream& out, const char* prefix, Node* node)
130 {
131     NodeType op = node->op();
132
133     unsigned refCount = node->refCount();
134     bool skipped = !refCount;
135     bool mustGenerate = node->mustGenerate();
136     if (mustGenerate)
137         --refCount;
138
139     out.print(prefix);
140     printNodeWhiteSpace(out, node);
141
142     // Example/explanation of dataflow dump output
143     //
144     //   14:   <!2:7>  GetByVal(@3, @13)
145     //   ^1     ^2 ^3     ^4       ^5
146     //
147     // (1) The nodeIndex of this operation.
148     // (2) The reference count. The number printed is the 'real' count,
149     //     not including the 'mustGenerate' ref. If the node is
150     //     'mustGenerate' then the count it prefixed with '!'.
151     // (3) The virtual register slot assigned to this node.
152     // (4) The name of the operation.
153     // (5) The arguments to the operation. The may be of the form:
154     //         @#   - a NodeIndex referencing a prior node in the graph.
155     //         arg# - an argument number.
156     //         $#   - the index in the CodeBlock of a constant { for numeric constants the value is displayed | for integers, in both decimal and hex }.
157     //         id#  - the index in the CodeBlock of an identifier { if codeBlock is passed to dump(), the string representation is displayed }.
158     //         var# - the index of a var on the global object, used by GetGlobalVar/PutGlobalVar operations.
159     out.printf("% 4d:%s<%c%u:", (int)node->index(), skipped ? "  skipped  " : "           ", mustGenerate ? '!' : ' ', refCount);
160     if (node->hasResult() && !skipped && node->hasVirtualRegister())
161         out.print(node->virtualRegister());
162     else
163         out.print("-");
164     out.print(">\t", opName(op), "(");
165     CommaPrinter comma;
166     if (node->flags() & NodeHasVarArgs) {
167         for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
168             if (!m_varArgChildren[childIdx])
169                 continue;
170             out.print(comma, m_varArgChildren[childIdx]);
171         }
172     } else {
173         if (!!node->child1() || !!node->child2() || !!node->child3())
174             out.print(comma, node->child1());
175         if (!!node->child2() || !!node->child3())
176             out.print(comma, node->child2());
177         if (!!node->child3())
178             out.print(comma, node->child3());
179     }
180
181     if (toCString(NodeFlagsDump(node->flags())) != "<empty>")
182         out.print(comma, NodeFlagsDump(node->flags()));
183     if (node->hasArrayMode())
184         out.print(comma, node->arrayMode());
185     if (node->hasVarNumber())
186         out.print(comma, node->varNumber());
187     if (node->hasRegisterPointer())
188         out.print(comma, "global", globalObjectFor(node->codeOrigin)->findRegisterIndex(node->registerPointer()), "(", RawPointer(node->registerPointer()), ")");
189     if (node->hasIdentifier())
190         out.print(comma, "id", node->identifierNumber(), "{", identifiers()[node->identifierNumber()], "}");
191     if (node->hasStructureSet())
192         out.print(comma, node->structureSet());
193     if (node->hasStructure())
194         out.print(comma, *node->structure());
195     if (node->hasStructureTransitionData())
196         out.print(comma, *node->structureTransitionData().previousStructure, " -> ", *node->structureTransitionData().newStructure);
197     if (node->hasFunction()) {
198         out.print(comma, "function(", RawPointer(node->function()), ", ");
199         if (node->function()->inherits(&JSFunction::s_info)) {
200             JSFunction* function = jsCast<JSFunction*>(node->function());
201             if (function->isHostFunction())
202                 out.print("<host function>");
203             else
204                 out.print(FunctionExecutableDump(function->jsExecutable()));
205         } else
206             out.print("<not JSFunction>");
207         out.print(")");
208     }
209     if (node->hasExecutable()) {
210         if (node->executable()->inherits(&FunctionExecutable::s_info))
211             out.print(comma, "executable(", FunctionExecutableDump(jsCast<FunctionExecutable*>(node->executable())), ")");
212         else
213             out.print(comma, "executable(not function: ", RawPointer(node->executable()), ")");
214     }
215     if (node->hasFunctionDeclIndex()) {
216         FunctionExecutable* executable = m_codeBlock->functionDecl(node->functionDeclIndex());
217         out.print(comma, executable->inferredName().string(), "#", executable->hashFor(CodeForCall));
218     }
219     if (node->hasFunctionExprIndex()) {
220         FunctionExecutable* executable = m_codeBlock->functionExpr(node->functionExprIndex());
221         out.print(comma, executable->inferredName().string(), "#", executable->hashFor(CodeForCall));
222     }
223     if (node->hasStorageAccessData()) {
224         StorageAccessData& storageAccessData = m_storageAccessData[node->storageAccessDataIndex()];
225         out.print(comma, "id", storageAccessData.identifierNumber, "{", identifiers()[storageAccessData.identifierNumber], "}");
226         out.print(", ", static_cast<ptrdiff_t>(storageAccessData.offset));
227     }
228     ASSERT(node->hasVariableAccessData(*this) == node->hasLocal(*this));
229     if (node->hasVariableAccessData(*this)) {
230         VariableAccessData* variableAccessData = node->variableAccessData();
231         int operand = variableAccessData->operand();
232         if (operandIsArgument(operand))
233             out.print(comma, "arg", operandToArgument(operand), "(", VariableAccessDataDump(*this, variableAccessData), ")");
234         else
235             out.print(comma, "r", operand, "(", VariableAccessDataDump(*this, variableAccessData), ")");
236     }
237     if (node->hasConstantBuffer()) {
238         out.print(comma);
239         out.print(node->startConstant(), ":[");
240         CommaPrinter anotherComma;
241         for (unsigned i = 0; i < node->numConstants(); ++i)
242             out.print(anotherComma, m_codeBlock->constantBuffer(node->startConstant())[i]);
243         out.print("]");
244     }
245     if (node->hasIndexingType())
246         out.print(comma, IndexingTypeDump(node->indexingType()));
247     if (node->hasPhi())
248         out.print(comma, "^", node->phi()->index());
249     if (node->hasExecutionCounter())
250         out.print(comma, RawPointer(node->executionCounter()));
251     if (op == JSConstant) {
252         out.print(comma, "$", node->constantNumber());
253         JSValue value = valueOfJSConstant(node);
254         out.print(" = ", value);
255     }
256     if (op == WeakJSConstant)
257         out.print(comma, RawPointer(node->weakConstant()), " (structure: ", *node->weakConstant()->structure(), ")");
258     if (node->isBranch() || node->isJump())
259         out.print(comma, "T:", *node->takenBlock());
260     if (node->isBranch())
261         out.print(comma, "F:", *node->notTakenBlock());
262     if (node->isSwitch()) {
263         SwitchData* data = node->switchData();
264         out.print(comma, data->kind);
265         for (unsigned i = 0; i < data->cases.size(); ++i)
266             out.print(comma, data->cases[i].value, ":", *data->cases[i].target);
267         out.print(comma, "default:", *data->fallThrough);
268     }
269     out.print(comma, "bc#", node->codeOrigin.bytecodeIndex);
270     
271     out.print(")");
272
273     if (!skipped) {
274         if (node->hasVariableAccessData(*this))
275             out.print("  predicting ", SpeculationDump(node->variableAccessData()->prediction()), node->variableAccessData()->shouldUseDoubleFormat() ? ", forcing double" : "");
276         else if (node->hasHeapPrediction())
277             out.print("  predicting ", SpeculationDump(node->getHeapPrediction()));
278     }
279     
280     out.print("\n");
281 }
282
283 void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* block, PhiNodeDumpMode phiNodeDumpMode)
284 {
285     out.print(prefix, "Block ", *block, " (", block->at(0)->codeOrigin, "): ", block->isReachable ? "" : "(skipped)", block->isOSRTarget ? " (OSR target)" : "", "\n");
286     out.print(prefix, "  Predecessors:");
287     for (size_t i = 0; i < block->predecessors.size(); ++i)
288         out.print(" ", *block->predecessors[i]);
289     out.print("\n");
290     if (m_dominators.isValid()) {
291         out.print(prefix, "  Dominated by:");
292         for (size_t i = 0; i < m_blocks.size(); ++i) {
293             if (!m_dominators.dominates(i, block->index))
294                 continue;
295             out.print(" #", i);
296         }
297         out.print("\n");
298         out.print(prefix, "  Dominates:");
299         for (size_t i = 0; i < m_blocks.size(); ++i) {
300             if (!m_dominators.dominates(block->index, i))
301                 continue;
302             out.print(" #", i);
303         }
304         out.print("\n");
305     }
306     if (m_naturalLoops.isValid()) {
307         if (const NaturalLoop* loop = m_naturalLoops.headerOf(block)) {
308             out.print(prefix, "  Loop header, contains:");
309             Vector<BlockIndex> sortedBlockList;
310             for (unsigned i = 0; i < loop->size(); ++i)
311                 sortedBlockList.append(loop->at(i)->index);
312             std::sort(sortedBlockList.begin(), sortedBlockList.end());
313             for (unsigned i = 0; i < sortedBlockList.size(); ++i)
314                 out.print(" #", sortedBlockList[i]);
315             out.print("\n");
316         }
317         
318         Vector<const NaturalLoop*> containingLoops =
319             m_naturalLoops.loopsOf(block);
320         if (!containingLoops.isEmpty()) {
321             out.print(prefix, "  Containing loop headers:");
322             for (unsigned i = 0; i < containingLoops.size(); ++i)
323                 out.print(" ", *containingLoops[i]->header());
324             out.print("\n");
325         }
326     }
327     if (!block->phis.isEmpty()) {
328         out.print(prefix, "  Phi Nodes:");
329         for (size_t i = 0; i < block->phis.size(); ++i) {
330             Node* phiNode = block->phis[i];
331             if (!phiNode->shouldGenerate() && phiNodeDumpMode == DumpLivePhisOnly)
332                 continue;
333             out.print(" @", phiNode->index(), "<", phiNode->refCount(), ">->(");
334             if (phiNode->child1()) {
335                 out.print("@", phiNode->child1()->index());
336                 if (phiNode->child2()) {
337                     out.print(", @", phiNode->child2()->index());
338                     if (phiNode->child3())
339                         out.print(", @", phiNode->child3()->index());
340                 }
341             }
342             out.print(")", i + 1 < block->phis.size() ? "," : "");
343         }
344         out.print("\n");
345     }
346 }
347
348 void Graph::dump(PrintStream& out)
349 {
350     dataLog("DFG for ", CodeBlockWithJITType(m_codeBlock, JITCode::DFGJIT), ":\n");
351     dataLog("  Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "; Ref count state: ", m_refCountState, "\n");
352
353     out.print("  ArgumentPosition size: ", m_argumentPositions.size(), "\n");
354     for (size_t i = 0; i < m_argumentPositions.size(); ++i) {
355         out.print("    #", i, ": ");
356         ArgumentPosition& arguments = m_argumentPositions[i];
357         arguments.dump(out, this);
358     }
359
360     Node* lastNode = 0;
361     for (size_t b = 0; b < m_blocks.size(); ++b) {
362         BasicBlock* block = m_blocks[b].get();
363         if (!block)
364             continue;
365         dumpBlockHeader(out, "", block, DumpAllPhis);
366         switch (m_form) {
367         case LoadStore:
368         case ThreadedCPS: {
369             out.print("  vars before: ");
370             if (block->cfaHasVisited)
371                 out.print(block->valuesAtHead);
372             else
373                 out.print("<empty>");
374             out.print("\n");
375             out.print("  var links: ");
376             dumpOperands(block->variablesAtHead, out);
377             out.print("\n");
378             break;
379         }
380             
381         case SSA: {
382             RELEASE_ASSERT(block->ssa);
383             out.print("  Flush format: ", block->ssa->flushFormatAtHead, "\n");
384             out.print("  Availability: ", block->ssa->availabilityAtHead, "\n");
385             out.print("  Live: ", nodeListDump(block->ssa->liveAtHead), "\n");
386             out.print("  Values: ", nodeMapDump(block->ssa->valuesAtHead), "\n");
387             break;
388         } }
389         for (size_t i = 0; i < block->size(); ++i) {
390             dumpCodeOrigin(out, "", lastNode, block->at(i));
391             dump(out, "", block->at(i));
392             lastNode = block->at(i);
393         }
394         switch (m_form) {
395         case LoadStore:
396         case ThreadedCPS: {
397             out.print("  vars after: ");
398             if (block->cfaHasVisited)
399                 out.print(block->valuesAtTail);
400             else
401                 out.print("<empty>");
402             out.print("\n");
403             out.print("  var links: ");
404             dumpOperands(block->variablesAtTail, out);
405             out.print("\n");
406             break;
407         }
408             
409         case SSA: {
410             RELEASE_ASSERT(block->ssa);
411             out.print("  Flush format: ", block->ssa->flushFormatAtTail, "\n");
412             out.print("  Availability: ", block->ssa->availabilityAtTail, "\n");
413             out.print("  Live: ", nodeListDump(block->ssa->liveAtTail), "\n");
414             out.print("  Values: ", nodeMapDump(block->ssa->valuesAtTail), "\n");
415             break;
416         } }
417     }
418 }
419
420 void Graph::dethread()
421 {
422     if (m_form == LoadStore)
423         return;
424     
425     if (logCompilationChanges())
426         dataLog("Dethreading DFG graph.\n");
427     
428     SamplingRegion samplingRegion("DFG Dethreading");
429     
430     for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) {
431         BasicBlock* block = m_blocks[blockIndex].get();
432         if (!block)
433             continue;
434         for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
435             Node* phi = block->phis[phiIndex];
436             phi->children.reset();
437         }
438     }
439     
440     m_form = LoadStore;
441 }
442
443 void Graph::handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock* block, BasicBlock* successor)
444 {
445     if (!successor->isReachable) {
446         successor->isReachable = true;
447         worklist.append(successor);
448     }
449     
450     successor->predecessors.append(block);
451 }
452
453 void Graph::determineReachability()
454 {
455     Vector<BasicBlock*, 16> worklist;
456     worklist.append(block(0));
457     block(0)->isReachable = true;
458     while (!worklist.isEmpty()) {
459         BasicBlock* block = worklist.takeLast();
460         for (unsigned i = block->numSuccessors(); i--;)
461             handleSuccessor(worklist, block, block->successor(i));
462     }
463 }
464
465 void Graph::resetReachability()
466 {
467     for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) {
468         BasicBlock* block = m_blocks[blockIndex].get();
469         if (!block)
470             continue;
471         block->isReachable = false;
472         block->predecessors.clear();
473     }
474     
475     determineReachability();
476 }
477
478 void Graph::resetExitStates()
479 {
480     for (BlockIndex blockIndex = 0; blockIndex < m_blocks.size(); ++blockIndex) {
481         BasicBlock* block = m_blocks[blockIndex].get();
482         if (!block)
483             continue;
484         for (unsigned indexInBlock = block->size(); indexInBlock--;)
485             block->at(indexInBlock)->setCanExit(true);
486     }
487 }
488
489 void Graph::invalidateCFG()
490 {
491     m_dominators.invalidate();
492     m_naturalLoops.invalidate();
493 }
494
495 void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
496 {
497     if (variableAccessData->isCaptured()) {
498         // Let CSE worry about this one.
499         return;
500     }
501     for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
502         Node* node = block[indexInBlock];
503         bool shouldContinue = true;
504         switch (node->op()) {
505         case SetLocal: {
506             if (node->local() == variableAccessData->local())
507                 shouldContinue = false;
508             break;
509         }
510                 
511         case GetLocal: {
512             if (node->variableAccessData() != variableAccessData)
513                 continue;
514             substitute(block, indexInBlock, node, newGetLocal);
515             Node* oldTailNode = block.variablesAtTail.operand(variableAccessData->local());
516             if (oldTailNode == node)
517                 block.variablesAtTail.operand(variableAccessData->local()) = newGetLocal;
518             shouldContinue = false;
519             break;
520         }
521                 
522         default:
523             break;
524         }
525         if (!shouldContinue)
526             break;
527     }
528 }
529
530 void Graph::addForDepthFirstSort(Vector<BasicBlock*>& result, Vector<BasicBlock*, 16>& worklist, HashSet<BasicBlock*>& seen, BasicBlock* block)
531 {
532     if (seen.contains(block))
533         return;
534     
535     result.append(block);
536     worklist.append(block);
537     seen.add(block);
538 }
539
540 void Graph::getBlocksInDepthFirstOrder(Vector<BasicBlock*>& result)
541 {
542     Vector<BasicBlock*, 16> worklist;
543     HashSet<BasicBlock*> seen;
544     addForDepthFirstSort(result, worklist, seen, block(0));
545     while (!worklist.isEmpty()) {
546         BasicBlock* block = worklist.takeLast();
547         for (unsigned i = block->numSuccessors(); i--;)
548             addForDepthFirstSort(result, worklist, seen, block->successor(i));
549     }
550 }
551
552 void Graph::clearReplacements()
553 {
554     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
555         BasicBlock* block = m_blocks[blockIndex].get();
556         if (!block)
557             continue;
558         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
559             block->phis[phiIndex]->misc.replacement = 0;
560         for (unsigned nodeIndex = block->size(); nodeIndex--;)
561             block->at(nodeIndex)->misc.replacement = 0;
562     }
563 }
564     
565 } } // namespace JSC::DFG
566
567 #endif