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