a54d6edecd25d3d86032872336b57c860abda76c
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGPlan.cpp
1 /*
2  * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "DFGPlan.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGArgumentsEliminationPhase.h"
32 #include "DFGBackwardsPropagationPhase.h"
33 #include "DFGByteCodeParser.h"
34 #include "DFGCFAPhase.h"
35 #include "DFGCFGSimplificationPhase.h"
36 #include "DFGCPSRethreadingPhase.h"
37 #include "DFGCSEPhase.h"
38 #include "DFGConstantFoldingPhase.h"
39 #include "DFGCriticalEdgeBreakingPhase.h"
40 #include "DFGDCEPhase.h"
41 #include "DFGFailedFinalizer.h"
42 #include "DFGFixupPhase.h"
43 #include "DFGGraphSafepoint.h"
44 #include "DFGIntegerCheckCombiningPhase.h"
45 #include "DFGInvalidationPointInjectionPhase.h"
46 #include "DFGJITCompiler.h"
47 #include "DFGLICMPhase.h"
48 #include "DFGLivenessAnalysisPhase.h"
49 #include "DFGLoopPreHeaderCreationPhase.h"
50 #include "DFGOSRAvailabilityAnalysisPhase.h"
51 #include "DFGOSREntrypointCreationPhase.h"
52 #include "DFGObjectAllocationSinkingPhase.h"
53 #include "DFGPhantomCanonicalizationPhase.h"
54 #include "DFGPhantomRemovalPhase.h"
55 #include "DFGPredictionInjectionPhase.h"
56 #include "DFGPredictionPropagationPhase.h"
57 #include "DFGPutStackSinkingPhase.h"
58 #include "DFGResurrectionForValidationPhase.h"
59 #include "DFGSSAConversionPhase.h"
60 #include "DFGSSALoweringPhase.h"
61 #include "DFGStackLayoutPhase.h"
62 #include "DFGStaticExecutionCountEstimationPhase.h"
63 #include "DFGStoreBarrierElisionPhase.h"
64 #include "DFGStrengthReductionPhase.h"
65 #include "DFGStructureRegistrationPhase.h"
66 #include "DFGTierUpCheckInjectionPhase.h"
67 #include "DFGTypeCheckHoistingPhase.h"
68 #include "DFGUnificationPhase.h"
69 #include "DFGValidate.h"
70 #include "DFGVarargsForwardingPhase.h"
71 #include "DFGVirtualRegisterAllocationPhase.h"
72 #include "DFGWatchpointCollectionPhase.h"
73 #include "Debugger.h"
74 #include "JSCInlines.h"
75 #include "OperandsInlines.h"
76 #include "ProfilerDatabase.h"
77 #include <wtf/CurrentTime.h>
78
79 #if ENABLE(FTL_JIT)
80 #include "FTLCapabilities.h"
81 #include "FTLCompile.h"
82 #include "FTLFail.h"
83 #include "FTLLink.h"
84 #include "FTLLowerDFGToLLVM.h"
85 #include "FTLState.h"
86 #include "InitializeLLVM.h"
87 #endif
88
89 namespace JSC { namespace DFG {
90
91 static void dumpAndVerifyGraph(Graph& graph, const char* text, bool forceDump = false)
92 {
93     GraphDumpMode modeForFinalValidate = DumpGraph;
94     if (verboseCompilationEnabled(graph.m_plan.mode) || forceDump) {
95         dataLog(text, "\n");
96         graph.dump();
97         modeForFinalValidate = DontDumpGraph;
98     }
99     if (validationEnabled())
100         validate(graph, modeForFinalValidate);
101 }
102
103 static Profiler::CompilationKind profilerCompilationKindForMode(CompilationMode mode)
104 {
105     switch (mode) {
106     case InvalidCompilationMode:
107         RELEASE_ASSERT_NOT_REACHED();
108         return Profiler::DFG;
109     case DFGMode:
110         return Profiler::DFG;
111     case FTLMode:
112         return Profiler::FTL;
113     case FTLForOSREntryMode:
114         return Profiler::FTLForOSREntry;
115     }
116     RELEASE_ASSERT_NOT_REACHED();
117     return Profiler::DFG;
118 }
119
120 Plan::Plan(PassRefPtr<CodeBlock> passedCodeBlock, CodeBlock* profiledDFGCodeBlock,
121     CompilationMode mode, unsigned osrEntryBytecodeIndex,
122     const Operands<JSValue>& mustHandleValues)
123     : vm(*passedCodeBlock->vm())
124     , codeBlock(passedCodeBlock)
125     , profiledDFGCodeBlock(profiledDFGCodeBlock)
126     , mode(mode)
127     , osrEntryBytecodeIndex(osrEntryBytecodeIndex)
128     , mustHandleValues(mustHandleValues)
129     , compilation(codeBlock->vm()->m_perBytecodeProfiler ? adoptRef(new Profiler::Compilation(codeBlock->vm()->m_perBytecodeProfiler->ensureBytecodesFor(codeBlock.get()), profilerCompilationKindForMode(mode))) : 0)
130     , inlineCallFrames(adoptRef(new InlineCallFrameSet()))
131     , identifiers(codeBlock.get())
132     , weakReferences(codeBlock.get())
133     , willTryToTierUp(false)
134     , stage(Preparing)
135 {
136 }
137
138 Plan::~Plan()
139 {
140 }
141
142 bool Plan::reportCompileTimes() const
143 {
144     return Options::reportCompileTimes()
145         || (Options::reportFTLCompileTimes() && isFTL(mode));
146 }
147
148 void Plan::compileInThread(LongLivedState& longLivedState, ThreadData* threadData)
149 {
150     this->threadData = threadData;
151     
152     double before = 0;
153     CString codeBlockName;
154     if (reportCompileTimes()) {
155         before = monotonicallyIncreasingTimeMS();
156         codeBlockName = toCString(*codeBlock);
157     }
158     
159     SamplingRegion samplingRegion("DFG Compilation (Plan)");
160     CompilationScope compilationScope;
161
162     if (logCompilationChanges(mode))
163         dataLog("DFG(Plan) compiling ", *codeBlock, " with ", mode, ", number of instructions = ", codeBlock->instructionCount(), "\n");
164
165     CompilationPath path = compileInThreadImpl(longLivedState);
166
167     RELEASE_ASSERT(path == CancelPath || finalizer);
168     RELEASE_ASSERT((path == CancelPath) == (stage == Cancelled));
169     
170     if (reportCompileTimes()) {
171         const char* pathName;
172         switch (path) {
173         case FailPath:
174             pathName = "N/A (fail)";
175             break;
176         case DFGPath:
177             pathName = "DFG";
178             break;
179         case FTLPath:
180             pathName = "FTL";
181             break;
182         case CancelPath:
183             pathName = "Cancelled";
184             break;
185         default:
186             RELEASE_ASSERT_NOT_REACHED();
187 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
188             pathName = "";
189 #endif
190             break;
191         }
192         double now = monotonicallyIncreasingTimeMS();
193         dataLog("Optimized ", codeBlockName, " using ", mode, " with ", pathName, " into ", finalizer ? finalizer->codeSize() : 0, " bytes in ", now - before, " ms");
194         if (path == FTLPath)
195             dataLog(" (DFG: ", m_timeBeforeFTL - before, ", LLVM: ", now - m_timeBeforeFTL, ")");
196         dataLog(".\n");
197     }
198 }
199
200 Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
201 {
202     if (verboseCompilationEnabled(mode) && osrEntryBytecodeIndex != UINT_MAX) {
203         dataLog("\n");
204         dataLog("Compiler must handle OSR entry from bc#", osrEntryBytecodeIndex, " with values: ", mustHandleValues, "\n");
205         dataLog("\n");
206     }
207     
208     Graph dfg(vm, *this, longLivedState);
209     
210     if (!parse(dfg)) {
211         finalizer = std::make_unique<FailedFinalizer>(*this);
212         return FailPath;
213     }
214     
215     // By this point the DFG bytecode parser will have potentially mutated various tables
216     // in the CodeBlock. This is a good time to perform an early shrink, which is more
217     // powerful than a late one. It's safe to do so because we haven't generated any code
218     // that references any of the tables directly, yet.
219     codeBlock->shrinkToFit(CodeBlock::EarlyShrink);
220
221     if (validationEnabled())
222         validate(dfg);
223     
224     if (Options::dumpGraphAfterParsing()) {
225         dataLog("Graph after parsing:\n");
226         dfg.dump();
227     }
228     
229     performCPSRethreading(dfg);
230     performUnification(dfg);
231     performPredictionInjection(dfg);
232     
233     performStaticExecutionCountEstimation(dfg);
234     
235     if (mode == FTLForOSREntryMode) {
236         bool result = performOSREntrypointCreation(dfg);
237         if (!result) {
238             finalizer = std::make_unique<FailedFinalizer>(*this);
239             return FailPath;
240         }
241         performCPSRethreading(dfg);
242     }
243     
244     if (validationEnabled())
245         validate(dfg);
246     
247     performBackwardsPropagation(dfg);
248     performPredictionPropagation(dfg);
249     performFixup(dfg);
250     performStructureRegistration(dfg);
251     performInvalidationPointInjection(dfg);
252     performTypeCheckHoisting(dfg);
253     
254     dfg.m_fixpointState = FixpointNotConverged;
255     
256     // For now we're back to avoiding a fixpoint. Note that we've ping-ponged on this decision
257     // many times. For maximum throughput, it's best to fixpoint. But the throughput benefit is
258     // small and not likely to show up in FTL anyway. On the other hand, not fixpointing means
259     // that the compiler compiles more quickly. We want the third tier to compile quickly, which
260     // not fixpointing accomplishes; and the fourth tier shouldn't need a fixpoint.
261     if (validationEnabled())
262         validate(dfg);
263         
264     performStrengthReduction(dfg);
265     performLocalCSE(dfg);
266     performCPSRethreading(dfg);
267     performCFA(dfg);
268     performConstantFolding(dfg);
269     bool changed = false;
270     changed |= performCFGSimplification(dfg);
271     changed |= performLocalCSE(dfg);
272     
273     if (validationEnabled())
274         validate(dfg);
275     
276     performCPSRethreading(dfg);
277     if (!isFTL(mode)) {
278         // Only run this if we're not FTLing, because currently for a LoadVarargs that is forwardable and
279         // in a non-varargs inlined call frame, this will generate ForwardVarargs while the FTL
280         // ArgumentsEliminationPhase will create a sequence of GetStack+PutStacks. The GetStack+PutStack
281         // sequence then gets sunk, eliminating anything that looks like an escape for subsequent phases,
282         // while the ForwardVarargs doesn't get simplified until later (or not at all) and looks like an
283         // escape for all of the arguments. This then disables object allocation sinking.
284         //
285         // So, for now, we just disable this phase for the FTL.
286         //
287         // If we wanted to enable it, we'd have to do any of the following:
288         // - Enable ForwardVarargs->GetStack+PutStack strength reduction, and have that run before
289         //   PutStack sinking and object allocation sinking.
290         // - Make VarargsForwarding emit a GetLocal+SetLocal sequence, that we can later turn into
291         //   GetStack+PutStack.
292         //
293         // But, it's not super valuable to enable those optimizations, since the FTL
294         // ArgumentsEliminationPhase does everything that this phase does, and it doesn't introduce this
295         // pathology.
296         
297         changed |= performVarargsForwarding(dfg); // Do this after CFG simplification and CPS rethreading.
298     }
299     if (changed) {
300         performCFA(dfg);
301         performConstantFolding(dfg);
302     }
303     
304     // If we're doing validation, then run some analyses, to give them an opportunity
305     // to self-validate. Now is as good a time as any to do this.
306     if (validationEnabled()) {
307         dfg.m_dominators.computeIfNecessary(dfg);
308         dfg.m_naturalLoops.computeIfNecessary(dfg);
309         dfg.m_prePostNumbering.computeIfNecessary(dfg);
310     }
311
312     switch (mode) {
313     case DFGMode: {
314         dfg.m_fixpointState = FixpointConverged;
315     
316         performTierUpCheckInjection(dfg);
317
318         performStoreBarrierElision(dfg);
319         performPhantomRemoval(dfg);
320         performCPSRethreading(dfg);
321         performDCE(dfg);
322         performStackLayout(dfg);
323         performVirtualRegisterAllocation(dfg);
324         performWatchpointCollection(dfg);
325         dumpAndVerifyGraph(dfg, "Graph after optimization:");
326         
327         JITCompiler dataFlowJIT(dfg);
328         if (codeBlock->codeType() == FunctionCode)
329             dataFlowJIT.compileFunction();
330         else
331             dataFlowJIT.compile();
332         
333         return DFGPath;
334     }
335     
336     case FTLMode:
337     case FTLForOSREntryMode: {
338 #if ENABLE(FTL_JIT)
339         if (FTL::canCompile(dfg) == FTL::CannotCompile) {
340             finalizer = std::make_unique<FailedFinalizer>(*this);
341             return FailPath;
342         }
343         
344         performPhantomRemoval(dfg); // Reduce the graph size a bit.
345         performCriticalEdgeBreaking(dfg);
346         performLoopPreHeaderCreation(dfg);
347         performCPSRethreading(dfg);
348         performSSAConversion(dfg);
349         performSSALowering(dfg);
350         
351         // Ideally, these would be run to fixpoint with the object allocation sinking phase.
352         performArgumentsElimination(dfg);
353         performPutStackSinking(dfg);
354         
355         performGlobalCSE(dfg);
356         performLivenessAnalysis(dfg);
357         performCFA(dfg);
358         performConstantFolding(dfg);
359         performPhantomCanonicalization(dfg); // Reduce the graph size a lot.
360         changed = false;
361         changed |= performStrengthReduction(dfg);
362         if (Options::enableObjectAllocationSinking()) {
363             changed |= performCriticalEdgeBreaking(dfg);
364             changed |= performObjectAllocationSinking(dfg);
365         }
366         if (changed) {
367             // State-at-tail and state-at-head will be invalid if we did strength reduction since
368             // it might increase live ranges.
369             performLivenessAnalysis(dfg);
370             performCFA(dfg);
371             performConstantFolding(dfg);
372         }
373         
374         // Currently, this relies on pre-headers still being valid. That precludes running CFG
375         // simplification before it, unless we re-created the pre-headers. There wouldn't be anything
376         // wrong with running LICM earlier, if we wanted to put other CFG transforms above this point.
377         // Alternatively, we could run loop pre-header creation after SSA conversion - but if we did that
378         // then we'd need to do some simple SSA fix-up.
379         performLICM(dfg);
380         
381         performPhantomCanonicalization(dfg);
382         performIntegerCheckCombining(dfg);
383         performGlobalCSE(dfg);
384         
385         // At this point we're not allowed to do any further code motion because our reasoning
386         // about code motion assumes that it's OK to insert GC points in random places.
387         dfg.m_fixpointState = FixpointConverged;
388         
389         performStoreBarrierElision(dfg);
390         performPhantomCanonicalization(dfg);
391         performLivenessAnalysis(dfg);
392         performCFA(dfg);
393         if (Options::validateFTLOSRExitLiveness())
394             performResurrectionForValidation(dfg);
395         performDCE(dfg); // We rely on this to kill dead code that won't be recognized as dead by LLVM.
396         performStackLayout(dfg);
397         performLivenessAnalysis(dfg);
398         performOSRAvailabilityAnalysis(dfg);
399         performWatchpointCollection(dfg);
400         
401         if (FTL::canCompile(dfg) == FTL::CannotCompile) {
402             finalizer = std::make_unique<FailedFinalizer>(*this);
403             return FailPath;
404         }
405
406         dumpAndVerifyGraph(dfg, "Graph just before FTL lowering:", shouldShowDisassembly(mode));
407         
408         bool haveLLVM;
409         Safepoint::Result safepointResult;
410         {
411             GraphSafepoint safepoint(dfg, safepointResult);
412             haveLLVM = initializeLLVM();
413         }
414         if (safepointResult.didGetCancelled())
415             return CancelPath;
416         
417         if (!haveLLVM) {
418             if (Options::ftlCrashesIfCantInitializeLLVM()) {
419                 dataLog("LLVM can't be initialized.\n");
420                 CRASH();
421             }
422             finalizer = std::make_unique<FailedFinalizer>(*this);
423             return FailPath;
424         }
425
426         FTL::State state(dfg);
427         FTL::lowerDFGToLLVM(state);
428         
429         if (reportCompileTimes())
430             m_timeBeforeFTL = monotonicallyIncreasingTimeMS();
431         
432         if (Options::llvmAlwaysFailsBeforeCompile()) {
433             FTL::fail(state);
434             return FTLPath;
435         }
436         
437         FTL::compile(state, safepointResult);
438         if (safepointResult.didGetCancelled())
439             return CancelPath;
440         
441         if (Options::llvmAlwaysFailsBeforeLink()) {
442             FTL::fail(state);
443             return FTLPath;
444         }
445         
446         if (state.allocationFailed) {
447             FTL::fail(state);
448             return FTLPath;
449         }
450
451         if (state.jitCode->stackmaps.stackSize() > Options::llvmMaxStackSize()) {
452             FTL::fail(state);
453             return FTLPath;
454         }
455
456         FTL::link(state);
457         
458         if (state.allocationFailed) {
459             FTL::fail(state);
460             return FTLPath;
461         }
462         
463         return FTLPath;
464 #else
465         RELEASE_ASSERT_NOT_REACHED();
466         return FailPath;
467 #endif // ENABLE(FTL_JIT)
468     }
469         
470     default:
471         RELEASE_ASSERT_NOT_REACHED();
472         return FailPath;
473     }
474 }
475
476 bool Plan::isStillValid()
477 {
478     CodeBlock* replacement = codeBlock->replacement();
479     if (!replacement)
480         return false;
481     // FIXME: This is almost certainly not necessary. There's no way for the baseline
482     // code to be replaced during a compilation, except if we delete the plan, in which
483     // case we wouldn't be here.
484     // https://bugs.webkit.org/show_bug.cgi?id=132707
485     if (codeBlock->alternative() != replacement->baselineVersion())
486         return false;
487     if (!watchpoints.areStillValid())
488         return false;
489     return true;
490 }
491
492 void Plan::reallyAdd(CommonData* commonData)
493 {
494     watchpoints.reallyAdd(codeBlock.get(), *commonData);
495     identifiers.reallyAdd(vm, commonData);
496     weakReferences.reallyAdd(vm, commonData);
497     transitions.reallyAdd(vm, commonData);
498     writeBarriers.trigger(vm);
499 }
500
501 void Plan::notifyCompiling()
502 {
503     stage = Compiling;
504 }
505
506 void Plan::notifyCompiled()
507 {
508     stage = Compiled;
509 }
510
511 void Plan::notifyReady()
512 {
513     callback->compilationDidBecomeReadyAsynchronously(codeBlock.get());
514     stage = Ready;
515 }
516
517 CompilationResult Plan::finalizeWithoutNotifyingCallback()
518 {
519     if (!isStillValid())
520         return CompilationInvalidated;
521
522     bool result;
523     if (codeBlock->codeType() == FunctionCode)
524         result = finalizer->finalizeFunction();
525     else
526         result = finalizer->finalize();
527     
528     if (!result)
529         return CompilationFailed;
530     
531     reallyAdd(codeBlock->jitCode()->dfgCommon());
532     
533     return CompilationSuccessful;
534 }
535
536 void Plan::finalizeAndNotifyCallback()
537 {
538     callback->compilationDidComplete(codeBlock.get(), finalizeWithoutNotifyingCallback());
539 }
540
541 CompilationKey Plan::key()
542 {
543     return CompilationKey(codeBlock->alternative(), mode);
544 }
545
546 void Plan::checkLivenessAndVisitChildren(SlotVisitor& visitor, CodeBlockSet& codeBlocks)
547 {
548     if (!isKnownToBeLiveDuringGC())
549         return;
550     
551     for (unsigned i = mustHandleValues.size(); i--;)
552         visitor.appendUnbarrieredValue(&mustHandleValues[i]);
553     
554     codeBlocks.mark(codeBlock->alternative());
555     codeBlocks.mark(codeBlock.get());
556     codeBlocks.mark(profiledDFGCodeBlock.get());
557     
558     weakReferences.visitChildren(visitor);
559     writeBarriers.visitChildren(visitor);
560     transitions.visitChildren(visitor);
561 }
562
563 bool Plan::isKnownToBeLiveDuringGC()
564 {
565     if (stage == Cancelled)
566         return false;
567     if (!Heap::isMarked(codeBlock->ownerExecutable()))
568         return false;
569     if (!codeBlock->alternative()->isKnownToBeLiveDuringGC())
570         return false;
571     if (!!profiledDFGCodeBlock && !profiledDFGCodeBlock->isKnownToBeLiveDuringGC())
572         return false;
573     return true;
574 }
575
576 void Plan::cancel()
577 {
578     codeBlock = nullptr;
579     profiledDFGCodeBlock = nullptr;
580     mustHandleValues.clear();
581     compilation = nullptr;
582     finalizer = nullptr;
583     inlineCallFrames = nullptr;
584     watchpoints = DesiredWatchpoints();
585     identifiers = DesiredIdentifiers();
586     weakReferences = DesiredWeakReferences();
587     writeBarriers = DesiredWriteBarriers();
588     transitions = DesiredTransitions();
589     callback = nullptr;
590     stage = Cancelled;
591 }
592
593 } } // namespace JSC::DFG
594
595 #endif // ENABLE(DFG_JIT)
596