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