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         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
 389 bool 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
 407 void 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
 416 void Plan::notifyCompiling()
 417 {
 418     stage = Compiling;
 419 }
 420
 421 void Plan::notifyCompiled()
 422 {
 423     stage = Compiled;
 424 }
 425
 426 void Plan::notifyReady()
 427 {
 428     callback->compilationDidBecomeReadyAsynchronously(codeBlock.get());
 429     stage = Ready;
 430 }
 431
 432 CompilationResult 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
 451 void Plan::finalizeAndNotifyCallback()
 452 {
 453     callback->compilationDidComplete(codeBlock.get(), finalizeWithoutNotifyingCallback());
 454 }
 455
 456 CompilationKey Plan::key()
 457 {
 458     return CompilationKey(codeBlock->alternative(), mode);
 459 }
 460
 461 void 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
 479 bool 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
 492 void 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