4a6a6170b9165035c797de4652212c9e36910cea
[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
28 #if ENABLE(DFG_JIT)
29
30 #include "DFGPlan.h"
31
32 #include "DFGArgumentsSimplificationPhase.h"
33 #include "DFGBackwardsPropagationPhase.h"
34 #include "DFGByteCodeParser.h"
35 #include "DFGCFAPhase.h"
36 #include "DFGCFGSimplificationPhase.h"
37 #include "DFGCPSRethreadingPhase.h"
38 #include "DFGCSEPhase.h"
39 #include "DFGConstantFoldingPhase.h"
40 #include "DFGCriticalEdgeBreakingPhase.h"
41 #include "DFGDCEPhase.h"
42 #include "DFGFailedFinalizer.h"
43 #include "DFGFlushLivenessAnalysisPhase.h"
44 #include "DFGFixupPhase.h"
45 #include "DFGGraphSafepoint.h"
46 #include "DFGIntegerCheckCombiningPhase.h"
47 #include "DFGInvalidationPointInjectionPhase.h"
48 #include "DFGJITCompiler.h"
49 #include "DFGLICMPhase.h"
50 #include "DFGLivenessAnalysisPhase.h"
51 #include "DFGLoopPreHeaderCreationPhase.h"
52 #include "DFGOSRAvailabilityAnalysisPhase.h"
53 #include "DFGOSREntrypointCreationPhase.h"
54 #include "DFGPredictionInjectionPhase.h"
55 #include "DFGPredictionPropagationPhase.h"
56 #include "DFGResurrectionForValidationPhase.h"
57 #include "DFGSSAConversionPhase.h"
58 #include "DFGSSALoweringPhase.h"
59 #include "DFGStackLayoutPhase.h"
60 #include "DFGStoreBarrierElisionPhase.h"
61 #include "DFGStrengthReductionPhase.h"
62 #include "DFGTierUpCheckInjectionPhase.h"
63 #include "DFGTypeCheckHoistingPhase.h"
64 #include "DFGUnificationPhase.h"
65 #include "DFGValidate.h"
66 #include "DFGVirtualRegisterAllocationPhase.h"
67 #include "DFGWatchpointCollectionPhase.h"
68 #include "Debugger.h"
69 #include "OperandsInlines.h"
70 #include "JSCInlines.h"
71 #include <wtf/CurrentTime.h>
72
73 #if ENABLE(FTL_JIT)
74 #include "FTLCapabilities.h"
75 #include "FTLCompile.h"
76 #include "FTLFail.h"
77 #include "FTLLink.h"
78 #include "FTLLowerDFGToLLVM.h"
79 #include "FTLState.h"
80 #include "InitializeLLVM.h"
81 #endif
82
83 namespace JSC { namespace DFG {
84
85 static void dumpAndVerifyGraph(Graph& graph, const char* text)
86 {
87     GraphDumpMode modeForFinalValidate = DumpGraph;
88     if (verboseCompilationEnabled(graph.m_plan.mode)) {
89         dataLog(text, "\n");
90         graph.dump();
91         modeForFinalValidate = DontDumpGraph;
92     }
93     if (validationEnabled())
94         validate(graph, modeForFinalValidate);
95 }
96
97 static Profiler::CompilationKind profilerCompilationKindForMode(CompilationMode mode)
98 {
99     switch (mode) {
100     case InvalidCompilationMode:
101         RELEASE_ASSERT_NOT_REACHED();
102         return Profiler::DFG;
103     case DFGMode:
104         return Profiler::DFG;
105     case FTLMode:
106         return Profiler::FTL;
107     case FTLForOSREntryMode:
108         return Profiler::FTLForOSREntry;
109     }
110     RELEASE_ASSERT_NOT_REACHED();
111     return Profiler::DFG;
112 }
113
114 Plan::Plan(PassRefPtr<CodeBlock> passedCodeBlock, CodeBlock* profiledDFGCodeBlock,
115     CompilationMode mode, unsigned osrEntryBytecodeIndex,
116     const Operands<JSValue>& mustHandleValues)
117     : vm(*passedCodeBlock->vm())
118     , codeBlock(passedCodeBlock)
119     , profiledDFGCodeBlock(profiledDFGCodeBlock)
120     , mode(mode)
121     , osrEntryBytecodeIndex(osrEntryBytecodeIndex)
122     , mustHandleValues(mustHandleValues)
123     , compilation(codeBlock->vm()->m_perBytecodeProfiler ? adoptRef(new Profiler::Compilation(codeBlock->vm()->m_perBytecodeProfiler->ensureBytecodesFor(codeBlock.get()), profilerCompilationKindForMode(mode))) : 0)
124     , identifiers(codeBlock.get())
125     , weakReferences(codeBlock.get())
126     , willTryToTierUp(false)
127     , isCompiled(false)
128 {
129 }
130
131 Plan::~Plan()
132 {
133 }
134
135 bool Plan::reportCompileTimes() const
136 {
137     return Options::reportCompileTimes()
138         || (Options::reportFTLCompileTimes() && isFTL(mode));
139 }
140
141 void Plan::compileInThread(LongLivedState& longLivedState, ThreadData* threadData)
142 {
143     this->threadData = threadData;
144     
145     double before = 0;
146     if (reportCompileTimes())
147         before = currentTimeMS();
148     
149     SamplingRegion samplingRegion("DFG Compilation (Plan)");
150     CompilationScope compilationScope;
151
152     if (logCompilationChanges(mode))
153         dataLog("DFG(Plan) compiling ", *codeBlock, " with ", mode, ", number of instructions = ", codeBlock->instructionCount(), "\n");
154
155     CompilationPath path = compileInThreadImpl(longLivedState);
156
157     RELEASE_ASSERT(finalizer);
158     
159     if (reportCompileTimes()) {
160         const char* pathName;
161         switch (path) {
162         case FailPath:
163             pathName = "N/A (fail)";
164             break;
165         case DFGPath:
166             pathName = "DFG";
167             break;
168         case FTLPath:
169             pathName = "FTL";
170             break;
171         default:
172             RELEASE_ASSERT_NOT_REACHED();
173             pathName = "";
174             break;
175         }
176         double now = currentTimeMS();
177         dataLog("Optimized ", *codeBlock, " using ", mode, " with ", pathName, " into ", finalizer->codeSize(), " bytes in ", now - before, " ms");
178         if (path == FTLPath)
179             dataLog(" (DFG: ", beforeFTL - before, ", LLVM: ", now - beforeFTL, ")");
180         dataLog(".\n");
181     }
182 }
183
184 Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
185 {
186     if (verboseCompilationEnabled(mode) && osrEntryBytecodeIndex != UINT_MAX) {
187         dataLog("\n");
188         dataLog("Compiler must handle OSR entry from bc#", osrEntryBytecodeIndex, " with values: ", mustHandleValues, "\n");
189         dataLog("\n");
190     }
191     
192     Graph dfg(vm, *this, longLivedState);
193     
194     if (!parse(dfg)) {
195         finalizer = adoptPtr(new FailedFinalizer(*this));
196         return FailPath;
197     }
198     
199     // By this point the DFG bytecode parser will have potentially mutated various tables
200     // in the CodeBlock. This is a good time to perform an early shrink, which is more
201     // powerful than a late one. It's safe to do so because we haven't generated any code
202     // that references any of the tables directly, yet.
203     codeBlock->shrinkToFit(CodeBlock::EarlyShrink);
204
205     if (validationEnabled())
206         validate(dfg);
207     
208     performCPSRethreading(dfg);
209     performUnification(dfg);
210     performPredictionInjection(dfg);
211     
212     if (mode == FTLForOSREntryMode) {
213         bool result = performOSREntrypointCreation(dfg);
214         if (!result) {
215             finalizer = adoptPtr(new FailedFinalizer(*this));
216             return FailPath;
217         }
218         performCPSRethreading(dfg);
219     }
220     
221     if (validationEnabled())
222         validate(dfg);
223     
224     performBackwardsPropagation(dfg);
225     performPredictionPropagation(dfg);
226     performFixup(dfg);
227     performInvalidationPointInjection(dfg);
228     performTypeCheckHoisting(dfg);
229     
230     unsigned count = 1;
231     dfg.m_fixpointState = FixpointNotConverged;
232     for (;; ++count) {
233         if (logCompilationChanges(mode))
234             dataLogF("DFG beginning optimization fixpoint iteration #%u.\n", count);
235         bool changed = false;
236         
237         if (validationEnabled())
238             validate(dfg);
239         
240         changed |= performStrengthReduction(dfg);
241         performCFA(dfg);
242         changed |= performConstantFolding(dfg);
243         changed |= performArgumentsSimplification(dfg);
244         changed |= performCFGSimplification(dfg);
245         changed |= performCSE(dfg);
246         
247         if (!changed)
248             break;
249         
250         performCPSRethreading(dfg);
251     }
252     
253     if (logCompilationChanges(mode))
254         dataLogF("DFG optimization fixpoint converged in %u iterations.\n", count);
255
256     dfg.m_fixpointState = FixpointConverged;
257
258     performStoreBarrierElision(dfg);
259     
260     // If we're doing validation, then run some analyses, to give them an opportunity
261     // to self-validate. Now is as good a time as any to do this.
262     if (validationEnabled()) {
263         dfg.m_dominators.computeIfNecessary(dfg);
264         dfg.m_naturalLoops.computeIfNecessary(dfg);
265     }
266
267     switch (mode) {
268     case DFGMode: {
269         performTierUpCheckInjection(dfg);
270
271         performStoreElimination(dfg);
272         performCPSRethreading(dfg);
273         performDCE(dfg);
274         performStackLayout(dfg);
275         performVirtualRegisterAllocation(dfg);
276         performWatchpointCollection(dfg);
277         dumpAndVerifyGraph(dfg, "Graph after optimization:");
278         
279         JITCompiler dataFlowJIT(dfg);
280         if (codeBlock->codeType() == FunctionCode) {
281             dataFlowJIT.compileFunction();
282             dataFlowJIT.linkFunction();
283         } else {
284             dataFlowJIT.compile();
285             dataFlowJIT.link();
286         }
287         
288         return DFGPath;
289     }
290     
291     case FTLMode:
292     case FTLForOSREntryMode: {
293 #if ENABLE(FTL_JIT)
294         if (FTL::canCompile(dfg) == FTL::CannotCompile) {
295             finalizer = adoptPtr(new FailedFinalizer(*this));
296             return FailPath;
297         }
298         
299         performCriticalEdgeBreaking(dfg);
300         performLoopPreHeaderCreation(dfg);
301         performCPSRethreading(dfg);
302         performSSAConversion(dfg);
303         performSSALowering(dfg);
304         performCSE(dfg);
305         performLivenessAnalysis(dfg);
306         performCFA(dfg);
307         performLICM(dfg);
308         performIntegerCheckCombining(dfg);
309         performCSE(dfg);
310         performLivenessAnalysis(dfg);
311         performCFA(dfg);
312         if (Options::validateFTLOSRExitLiveness())
313             performResurrectionForValidation(dfg);
314         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.
315         performStackLayout(dfg);
316         performLivenessAnalysis(dfg);
317         performFlushLivenessAnalysis(dfg);
318         performOSRAvailabilityAnalysis(dfg);
319         performWatchpointCollection(dfg);
320         
321         dumpAndVerifyGraph(dfg, "Graph just before FTL lowering:");
322         
323         {
324             GraphSafepoint safepoint(dfg);
325             initializeLLVM();
326         }
327             
328         FTL::State state(dfg);
329         FTL::lowerDFGToLLVM(state);
330         
331         if (reportCompileTimes())
332             beforeFTL = currentTimeMS();
333         
334         if (Options::llvmAlwaysFailsBeforeCompile()) {
335             FTL::fail(state);
336             return FTLPath;
337         }
338         
339         FTL::compile(state);
340             
341         if (Options::llvmAlwaysFailsBeforeLink()) {
342             FTL::fail(state);
343             return FTLPath;
344         }
345
346         if (state.jitCode->stackmaps.stackSize() > Options::llvmMaxStackSize()) {
347             FTL::fail(state);
348             return FTLPath;
349         }
350
351         FTL::link(state);
352         return FTLPath;
353 #else
354         RELEASE_ASSERT_NOT_REACHED();
355         return FailPath;
356 #endif // ENABLE(FTL_JIT)
357     }
358         
359     default:
360         RELEASE_ASSERT_NOT_REACHED();
361         return FailPath;
362     }
363 }
364
365 bool Plan::isStillValid()
366 {
367     return watchpoints.areStillValid()
368         && chains.areStillValid();
369 }
370
371 void Plan::reallyAdd(CommonData* commonData)
372 {
373     watchpoints.reallyAdd(codeBlock.get(), *commonData);
374     identifiers.reallyAdd(vm, commonData);
375     weakReferences.reallyAdd(vm, commonData);
376     transitions.reallyAdd(vm, commonData);
377     writeBarriers.trigger(vm);
378 }
379
380 void Plan::notifyReady()
381 {
382     callback->compilationDidBecomeReadyAsynchronously(codeBlock.get());
383     isCompiled = true;
384 }
385
386 CompilationResult Plan::finalizeWithoutNotifyingCallback()
387 {
388     if (!isStillValid())
389         return CompilationInvalidated;
390
391     if (vm.enabledProfiler())
392         return CompilationInvalidated;
393
394     Debugger* debugger = codeBlock->globalObject()->debugger();
395     if (debugger && (debugger->isStepping() || codeBlock->baselineAlternative()->hasDebuggerRequests()))
396         return CompilationInvalidated;
397
398     bool result;
399     if (codeBlock->codeType() == FunctionCode)
400         result = finalizer->finalizeFunction();
401     else
402         result = finalizer->finalize();
403     
404     if (!result)
405         return CompilationFailed;
406     
407     reallyAdd(codeBlock->jitCode()->dfgCommon());
408     
409     return CompilationSuccessful;
410 }
411
412 void Plan::finalizeAndNotifyCallback()
413 {
414     callback->compilationDidComplete(codeBlock.get(), finalizeWithoutNotifyingCallback());
415 }
416
417 CompilationKey Plan::key()
418 {
419     return CompilationKey(codeBlock->alternative(), mode);
420 }
421
422 void Plan::visitChildren(SlotVisitor& visitor, CodeBlockSet& codeBlocks)
423 {
424     for (unsigned i = mustHandleValues.size(); i--;)
425         visitor.appendUnbarrieredValue(&mustHandleValues[i]);
426     
427     codeBlocks.mark(codeBlock.get());
428     codeBlocks.mark(profiledDFGCodeBlock.get());
429     
430     chains.visitChildren(visitor);
431     weakReferences.visitChildren(visitor);
432     writeBarriers.visitChildren(visitor);
433     transitions.visitChildren(visitor);
434 }
435
436 } } // namespace JSC::DFG
437
438 #endif // ENABLE(DFG_JIT)
439