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 "DFGPredictionInjectionPhase.h"
53#include "DFGPredictionPropagationPhase.h"
54#include "DFGResurrectionForValidationPhase.h"
55#include "DFGSSAConversionPhase.h"
56#include "DFGSSALoweringPhase.h"
57#include "DFGStackLayoutPhase.h"
58#include "DFGStaticExecutionCountEstimationPhase.h"
59#include "DFGStoreBarrierElisionPhase.h"
60#include "DFGStrengthReductionPhase.h"
61#include "DFGTierUpCheckInjectionPhase.h"
62#include "DFGTypeCheckHoistingPhase.h"
63#include "DFGUnificationPhase.h"
64#include "DFGValidate.h"
65#include "DFGVirtualRegisterAllocationPhase.h"
66#include "DFGWatchpointCollectionPhase.h"
67#include "Debugger.h"
68#include "JSCInlines.h"
69#include "OperandsInlines.h"
70#include "ProfilerDatabase.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
83namespace JSC { namespace DFG {
84
85static 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
97static 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
114Plan::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    , inlineCallFrames(adoptRef(new InlineCallFrameSet()))
125    , identifiers(codeBlock.get())
126    , weakReferences(codeBlock.get())
127    , willTryToTierUp(false)
128    , stage(Preparing)
129{
130}
131
132Plan::~Plan()
133{
134}
135
136bool Plan::reportCompileTimes() const
137{
138    return Options::reportCompileTimes()
139        || (Options::reportFTLCompileTimes() && isFTL(mode));
140}
141
142void Plan::compileInThread(LongLivedState& longLivedState, ThreadData* threadData)
143{
144    this->threadData = threadData;
145
146    double before = 0;
147    CString codeBlockName;
148    if (reportCompileTimes()) {
149        before = currentTimeMS();
150        codeBlockName = toCString(*codeBlock);
151    }
152
153    SamplingRegion samplingRegion("DFG Compilation (Plan)");
154    CompilationScope compilationScope;
155
156    if (logCompilationChanges(mode))
157        dataLog("DFG(Plan) compiling ", *codeBlock, " with ", mode, ", number of instructions = ", codeBlock->instructionCount(), "\n");
158
159    CompilationPath path = compileInThreadImpl(longLivedState);
160
161    RELEASE_ASSERT(path == CancelPath || finalizer);
162    RELEASE_ASSERT((path == CancelPath) == (stage == Cancelled));
163
164    if (reportCompileTimes()) {
165        const char* pathName;
166        switch (path) {
167        case FailPath:
168            pathName = "N/A (fail)";
169            break;
170        case DFGPath:
171            pathName = "DFG";
172            break;
173        case FTLPath:
174            pathName = "FTL";
175            break;
176        case CancelPath:
177            pathName = "Cancelled";
178            break;
179        default:
180            RELEASE_ASSERT_NOT_REACHED();
181            pathName = "";
182            break;
183        }
184        double now = currentTimeMS();
185        dataLog("Optimized ", codeBlockName, " using ", mode, " with ", pathName, " into ", finalizer ? finalizer->codeSize() : 0, " bytes in ", now - before, " ms");
186        if (path == FTLPath)
187            dataLog(" (DFG: ", beforeFTL - before, ", LLVM: ", now - beforeFTL, ")");
188        dataLog(".\n");
189    }
190}
191
192Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
193{
194    if (verboseCompilationEnabled(mode) && osrEntryBytecodeIndex != UINT_MAX) {
195        dataLog("\n");
196        dataLog("Compiler must handle OSR entry from bc#", osrEntryBytecodeIndex, " with values: ", mustHandleValues, "\n");
197        dataLog("\n");
198    }
199
200    Graph dfg(vm, *this, longLivedState);
201
202    if (!parse(dfg)) {
203        finalizer = adoptPtr(new FailedFinalizer(*this));
204        return FailPath;
205    }
206
207    // By this point the DFG bytecode parser will have potentially mutated various tables
208    // in the CodeBlock. This is a good time to perform an early shrink, which is more
209    // powerful than a late one. It's safe to do so because we haven't generated any code
210    // that references any of the tables directly, yet.
211    codeBlock->shrinkToFit(CodeBlock::EarlyShrink);
212
213    if (validationEnabled())
214        validate(dfg);
215
216    performCPSRethreading(dfg);
217    performUnification(dfg);
218    performPredictionInjection(dfg);
219
220    performStaticExecutionCountEstimation(dfg);
221
222    if (mode == FTLForOSREntryMode) {
223        bool result = performOSREntrypointCreation(dfg);
224        if (!result) {
225            finalizer = adoptPtr(new FailedFinalizer(*this));
226            return FailPath;
227        }
228        performCPSRethreading(dfg);
229    }
230
231    if (validationEnabled())
232        validate(dfg);
233
234    performBackwardsPropagation(dfg);
235    performPredictionPropagation(dfg);
236    performFixup(dfg);
237    performInvalidationPointInjection(dfg);
238    performTypeCheckHoisting(dfg);
239
240    unsigned count = 1;
241    dfg.m_fixpointState = FixpointNotConverged;
242    for (;; ++count) {
243        if (logCompilationChanges(mode))
244            dataLogF("DFG beginning optimization fixpoint iteration #%u.\n", count);
245        bool changed = false;
246
247        if (validationEnabled())
248            validate(dfg);
249
250        changed |= performStrengthReduction(dfg);
251        performCFA(dfg);
252        changed |= performConstantFolding(dfg);
253        changed |= performArgumentsSimplification(dfg);
254        changed |= performCFGSimplification(dfg);
255        changed |= performCSE(dfg);
256
257        if (!changed)
258            break;
259
260        performCPSRethreading(dfg);
261    }
262
263    if (logCompilationChanges(mode))
264        dataLogF("DFG optimization fixpoint converged in %u iterations.\n", count);
265
266    dfg.m_fixpointState = FixpointConverged;
267
268    // If we're doing validation, then run some analyses, to give them an opportunity
269    // to self-validate. Now is as good a time as any to do this.
270    if (validationEnabled()) {
271        dfg.m_dominators.computeIfNecessary(dfg);
272        dfg.m_naturalLoops.computeIfNecessary(dfg);
273    }
274
275    switch (mode) {
276    case DFGMode: {
277        performTierUpCheckInjection(dfg);
278
279        performStoreBarrierElision(dfg);
280        performStoreElimination(dfg);
281        performCPSRethreading(dfg);
282        performDCE(dfg);
283        performStackLayout(dfg);
284        performVirtualRegisterAllocation(dfg);
285        performWatchpointCollection(dfg);
286        dumpAndVerifyGraph(dfg, "Graph after optimization:");
287
288        JITCompiler dataFlowJIT(dfg);
289        if (codeBlock->codeType() == FunctionCode) {
290            dataFlowJIT.compileFunction();
291            dataFlowJIT.linkFunction();
292        } else {
293            dataFlowJIT.compile();
294            dataFlowJIT.link();
295        }
296
297        return DFGPath;
298    }
299
300    case FTLMode:
301    case FTLForOSREntryMode: {
302#if ENABLE(FTL_JIT)
303        if (FTL::canCompile(dfg) == FTL::CannotCompile) {
304            finalizer = adoptPtr(new FailedFinalizer(*this));
305            return FailPath;
306        }
307
308        performCriticalEdgeBreaking(dfg);
309        performLoopPreHeaderCreation(dfg);
310        performCPSRethreading(dfg);
311        performSSAConversion(dfg);
312        performSSALowering(dfg);
313        performCSE(dfg);
314        performLivenessAnalysis(dfg);
315        performCFA(dfg);
316        performLICM(dfg);
317        performIntegerCheckCombining(dfg);
318        performCSE(dfg);
319
320        // At this point we're not allowed to do any further code motion because our reasoning
321        // about code motion assumes that it's OK to insert GC points in random places.
322
323        performStoreBarrierElision(dfg);
324        performLivenessAnalysis(dfg);
325        performCFA(dfg);
326        if (Options::validateFTLOSRExitLiveness())
327            performResurrectionForValidation(dfg);
328        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.
329        performStackLayout(dfg);
330        performLivenessAnalysis(dfg);
331        performOSRAvailabilityAnalysis(dfg);
332        performWatchpointCollection(dfg);
333
334        dumpAndVerifyGraph(dfg, "Graph just before FTL lowering:");
335
336        bool haveLLVM;
337        Safepoint::Result safepointResult;
338        {
339            GraphSafepoint safepoint(dfg, safepointResult);
340            haveLLVM = initializeLLVM();
341        }
342        if (safepointResult.didGetCancelled())
343            return CancelPath;
344
345        if (!haveLLVM) {
346            finalizer = adoptPtr(new FailedFinalizer(*this));
347            return FailPath;
348        }
349
350        FTL::State state(dfg);
351        FTL::lowerDFGToLLVM(state);
352
353        if (reportCompileTimes())
354            beforeFTL = currentTimeMS();
355
356        if (Options::llvmAlwaysFailsBeforeCompile()) {
357            FTL::fail(state);
358            return FTLPath;
359        }
360
361        FTL::compile(state, safepointResult);
362        if (safepointResult.didGetCancelled())
363            return CancelPath;
364
365        if (Options::llvmAlwaysFailsBeforeLink()) {
366            FTL::fail(state);
367            return FTLPath;
368        }
369
370        if (state.jitCode->stackmaps.stackSize() > Options::llvmMaxStackSize()) {
371            FTL::fail(state);
372            return FTLPath;
373        }
374
375        FTL::link(state);
376        return FTLPath;
377#else
378        RELEASE_ASSERT_NOT_REACHED();
379        return FailPath;
380#endif // ENABLE(FTL_JIT)
381    }
382
383    default:
384        RELEASE_ASSERT_NOT_REACHED();
385        return FailPath;
386    }
387}
388
389bool Plan::isStillValid()
390{
391    CodeBlock* replacement = codeBlock->replacement();
392    if (!replacement)
393        return false;
394    // FIXME: This is almost certainly not necessary. There's no way for the baseline
395    // code to be replaced during a compilation, except if we delete the plan, in which
396    // case we wouldn't be here.
397    // https://bugs.webkit.org/show_bug.cgi?id=132707
398    if (codeBlock->alternative() != replacement->baselineVersion())
399        return false;
400    if (!watchpoints.areStillValid())
401        return false;
402    if (!chains.areStillValid())
403        return false;
404    return true;
405}
406
407void Plan::reallyAdd(CommonData* commonData)
408{
409    watchpoints.reallyAdd(codeBlock.get(), *commonData);
410    identifiers.reallyAdd(vm, commonData);
411    weakReferences.reallyAdd(vm, commonData);
412    transitions.reallyAdd(vm, commonData);
413    writeBarriers.trigger(vm);
414}
415
416void Plan::notifyCompiling()
417{
418    stage = Compiling;
419}
420
421void Plan::notifyCompiled()
422{
423    stage = Compiled;
424}
425
426void Plan::notifyReady()
427{
428    callback->compilationDidBecomeReadyAsynchronously(codeBlock.get());
429    stage = Ready;
430}
431
432CompilationResult Plan::finalizeWithoutNotifyingCallback()
433{
434    if (!isStillValid())
435        return CompilationInvalidated;
436
437    bool result;
438    if (codeBlock->codeType() == FunctionCode)
439        result = finalizer->finalizeFunction();
440    else
441        result = finalizer->finalize();
442
443    if (!result)
444        return CompilationFailed;
445
446    reallyAdd(codeBlock->jitCode()->dfgCommon());
447
448    return CompilationSuccessful;
449}
450
451void Plan::finalizeAndNotifyCallback()
452{
453    callback->compilationDidComplete(codeBlock.get(), finalizeWithoutNotifyingCallback());
454}
455
456CompilationKey Plan::key()
457{
458    return CompilationKey(codeBlock->alternative(), mode);
459}
460
461void Plan::checkLivenessAndVisitChildren(SlotVisitor& visitor, CodeBlockSet& codeBlocks)
462{
463    if (!isKnownToBeLiveDuringGC())
464        return;
465
466    for (unsigned i = mustHandleValues.size(); i--;)
467        visitor.appendUnbarrieredValue(&mustHandleValues[i]);
468
469    codeBlocks.mark(codeBlock->alternative());
470    codeBlocks.mark(codeBlock.get());
471    codeBlocks.mark(profiledDFGCodeBlock.get());
472
473    chains.visitChildren(visitor);
474    weakReferences.visitChildren(visitor);
475    writeBarriers.visitChildren(visitor);
476    transitions.visitChildren(visitor);
477}
478
479bool Plan::isKnownToBeLiveDuringGC()
480{
481    if (stage == Cancelled)
482        return false;
483    if (!Heap::isMarked(codeBlock->ownerExecutable()))
484        return false;
485    if (!codeBlock->alternative()->isKnownToBeLiveDuringGC())
486        return false;
487    if (!!profiledDFGCodeBlock && !profiledDFGCodeBlock->isKnownToBeLiveDuringGC())
488        return false;
489    return true;
490}
491
492void Plan::cancel()
493{
494    codeBlock = nullptr;
495    profiledDFGCodeBlock = nullptr;
496    mustHandleValues.clear();
497    compilation = nullptr;
498    finalizer.clear();
499    inlineCallFrames = nullptr;
500    watchpoints = DesiredWatchpoints();
501    identifiers = DesiredIdentifiers();
502    chains = DesiredStructureChains();
503    weakReferences = DesiredWeakReferences();
504    writeBarriers = DesiredWriteBarriers();
505    transitions = DesiredTransitions();
506    callback = nullptr;
507    stage = Cancelled;
508}
509
510} } // namespace JSC::DFG
511
512#endif // ENABLE(DFG_JIT)
513
514