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 "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
  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     , inlineCallFrames(adoptRef(new InlineCallFrameSet()))
 125     , identifiers(codeBlock.get())
 126     , weakReferences(codeBlock.get())
 127     , willTryToTierUp(false)
 128     , stage(Preparing)
 129 {
 130 }
 131
 132 Plan::~Plan()
 133 {
 134 }
 135
 136 bool Plan::reportCompileTimes() const
 137 {
 138     return Options::reportCompileTimes()
 139         || (Options::reportFTLCompileTimes() && isFTL(mode));
 140 }
 141
 142 void 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
 192 Plan::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         if (!FTL::lowerDFGToLLVM(state)) {
 352             FTL::fail(state);
 353             return FTLPath;
 354         }
 355
 356         if (reportCompileTimes())
 357             beforeFTL = currentTimeMS();
 358
 359         if (Options::llvmAlwaysFailsBeforeCompile()) {
 360             FTL::fail(state);
 361             return FTLPath;
 362         }
 363
 364         FTL::compile(state, safepointResult);
 365         if (safepointResult.didGetCancelled())
 366             return CancelPath;
 367
 368         if (Options::llvmAlwaysFailsBeforeLink()) {
 369             FTL::fail(state);
 370             return FTLPath;
 371         }
 372
 373         if (state.jitCode->stackmaps.stackSize() > Options::llvmMaxStackSize()) {
 374             FTL::fail(state);
 375             return FTLPath;
 376         }
 377
 378         FTL::link(state);
 379         return FTLPath;
 380 #else
 381         RELEASE_ASSERT_NOT_REACHED();
 382         return FailPath;
 383 #endif // ENABLE(FTL_JIT)
 384     }
 385
 386     default:
 387         RELEASE_ASSERT_NOT_REACHED();
 388         return FailPath;
 389     }
 390 }
 391
 392 bool Plan::isStillValid()
 393 {
 394     CodeBlock* replacement = codeBlock->replacement();
 395     if (!replacement)
 396         return false;
 397     // FIXME: This is almost certainly not necessary. There's no way for the baseline
 398     // code to be replaced during a compilation, except if we delete the plan, in which
 399     // case we wouldn't be here.
 400     // https://bugs.webkit.org/show_bug.cgi?id=132707
 401     if (codeBlock->alternative() != replacement->baselineVersion())
 402         return false;
 403     if (!watchpoints.areStillValid())
 404         return false;
 405     if (!chains.areStillValid())
 406         return false;
 407     return true;
 408 }
 409
 410 void Plan::reallyAdd(CommonData* commonData)
 411 {
 412     watchpoints.reallyAdd(codeBlock.get(), *commonData);
 413     identifiers.reallyAdd(vm, commonData);
 414     weakReferences.reallyAdd(vm, commonData);
 415     transitions.reallyAdd(vm, commonData);
 416     writeBarriers.trigger(vm);
 417 }
 418
 419 void Plan::notifyCompiling()
 420 {
 421     stage = Compiling;
 422 }
 423
 424 void Plan::notifyCompiled()
 425 {
 426     stage = Compiled;
 427 }
 428
 429 void Plan::notifyReady()
 430 {
 431     callback->compilationDidBecomeReadyAsynchronously(codeBlock.get());
 432     stage = Ready;
 433 }
 434
 435 CompilationResult Plan::finalizeWithoutNotifyingCallback()
 436 {
 437     if (!isStillValid())
 438         return CompilationInvalidated;
 439
 440     bool result;
 441     if (codeBlock->codeType() == FunctionCode)
 442         result = finalizer->finalizeFunction();
 443     else
 444         result = finalizer->finalize();
 445
 446     if (!result)
 447         return CompilationFailed;
 448
 449     reallyAdd(codeBlock->jitCode()->dfgCommon());
 450
 451     return CompilationSuccessful;
 452 }
 453
 454 void Plan::finalizeAndNotifyCallback()
 455 {
 456     callback->compilationDidComplete(codeBlock.get(), finalizeWithoutNotifyingCallback());
 457 }
 458
 459 CompilationKey Plan::key()
 460 {
 461     return CompilationKey(codeBlock->alternative(), mode);
 462 }
 463
 464 void Plan::checkLivenessAndVisitChildren(SlotVisitor& visitor, CodeBlockSet& codeBlocks)
 465 {
 466     if (!isKnownToBeLiveDuringGC())
 467         return;
 468
 469     for (unsigned i = mustHandleValues.size(); i--;)
 470         visitor.appendUnbarrieredValue(&mustHandleValues[i]);
 471
 472     codeBlocks.mark(codeBlock->alternative());
 473     codeBlocks.mark(codeBlock.get());
 474     codeBlocks.mark(profiledDFGCodeBlock.get());
 475
 476     chains.visitChildren(visitor);
 477     weakReferences.visitChildren(visitor);
 478     writeBarriers.visitChildren(visitor);
 479     transitions.visitChildren(visitor);
 480 }
 481
 482 bool Plan::isKnownToBeLiveDuringGC()
 483 {
 484     if (stage == Cancelled)
 485         return false;
 486     if (!Heap::isMarked(codeBlock->ownerExecutable()))
 487         return false;
 488     if (!codeBlock->alternative()->isKnownToBeLiveDuringGC())
 489         return false;
 490     if (!!profiledDFGCodeBlock && !profiledDFGCodeBlock->isKnownToBeLiveDuringGC())
 491         return false;
 492     return true;
 493 }
 494
 495 void Plan::cancel()
 496 {
 497     codeBlock = nullptr;
 498     profiledDFGCodeBlock = nullptr;
 499     mustHandleValues.clear();
 500     compilation = nullptr;
 501     finalizer.clear();
 502     inlineCallFrames = nullptr;
 503     watchpoints = DesiredWatchpoints();
 504     identifiers = DesiredIdentifiers();
 505     chains = DesiredStructureChains();
 506     weakReferences = DesiredWeakReferences();
 507     writeBarriers = DesiredWriteBarriers();
 508     transitions = DesiredTransitions();
 509     callback = nullptr;
 510     stage = Cancelled;
 511 }
 512
 513 } } // namespace JSC::DFG
 514
 515 #endif // ENABLE(DFG_JIT)
 516