bytecode/CallLinkStatus.cpp

   1 /*
   2  * Copyright (C) 2012-2015 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 "CallLinkStatus.h"
  28
  29 #include "CallLinkInfo.h"
  30 #include "CodeBlock.h"
  31 #include "DFGJITCode.h"
  32 #include "LLIntCallLinkInfo.h"
  33 #include "JSCInlines.h"
  34 #include <wtf/CommaPrinter.h>
  35 #include <wtf/ListDump.h>
  36
  37 namespace JSC {
  38
  39 static const bool verbose = false;
  40
  41 CallLinkStatus::CallLinkStatus(JSValue value)
  42     : m_couldTakeSlowPath(false)
  43     , m_isProved(false)
  44 {
  45     if (!value || !value.isCell()) {
  46         m_couldTakeSlowPath = true;
  47         return;
  48     }
  49
  50     m_variants.append(CallVariant(value.asCell()));
  51 }
  52
  53 CallLinkStatus CallLinkStatus::computeFromLLInt(const ConcurrentJITLocker& locker, CodeBlock* profiledBlock, unsigned bytecodeIndex)
  54 {
  55     UNUSED_PARAM(profiledBlock);
  56     UNUSED_PARAM(bytecodeIndex);
  57 #if ENABLE(DFG_JIT)
  58     if (profiledBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadCell))) {
  59         // We could force this to be a closure call, but instead we'll just assume that it
  60         // takes slow path.
  61         return takesSlowPath();
  62     }
  63 #else
  64     UNUSED_PARAM(locker);
  65 #endif
  66
  67     VM& vm = *profiledBlock->vm();
  68
  69     Instruction* instruction = profiledBlock->instructions().begin() + bytecodeIndex;
  70     OpcodeID op = vm.interpreter->getOpcodeID(instruction[0].u.opcode);
  71     if (op != op_call && op != op_construct)
  72         return CallLinkStatus();
  73
  74     LLIntCallLinkInfo* callLinkInfo = instruction[5].u.callLinkInfo;
  75
  76     return CallLinkStatus(callLinkInfo->lastSeenCallee.get());
  77 }
  78
  79 CallLinkStatus CallLinkStatus::computeFor(
  80     CodeBlock* profiledBlock, unsigned bytecodeIndex, const CallLinkInfoMap& map)
  81 {
  82     ConcurrentJITLocker locker(profiledBlock->m_lock);
  83
  84     UNUSED_PARAM(profiledBlock);
  85     UNUSED_PARAM(bytecodeIndex);
  86     UNUSED_PARAM(map);
  87 #if ENABLE(DFG_JIT)
  88     ExitSiteData exitSiteData = computeExitSiteData(locker, profiledBlock, bytecodeIndex);
  89
  90     CallLinkInfo* callLinkInfo = map.get(CodeOrigin(bytecodeIndex));
  91     if (!callLinkInfo) {
  92         if (exitSiteData.m_takesSlowPath)
  93             return takesSlowPath();
  94         return computeFromLLInt(locker, profiledBlock, bytecodeIndex);
  95     }
  96
  97     return computeFor(locker, profiledBlock, *callLinkInfo, exitSiteData);
  98 #else
  99     return CallLinkStatus();
 100 #endif
 101 }
 102
 103 CallLinkStatus::ExitSiteData CallLinkStatus::computeExitSiteData(
 104     const ConcurrentJITLocker& locker, CodeBlock* profiledBlock, unsigned bytecodeIndex)
 105 {
 106     ExitSiteData exitSiteData;
 107
 108 #if ENABLE(DFG_JIT)
 109     exitSiteData.m_takesSlowPath =
 110         profiledBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadType))
 111         || profiledBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadExecutable));
 112     exitSiteData.m_badFunction =
 113         profiledBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadCell));
 114 #else
 115     UNUSED_PARAM(locker);
 116     UNUSED_PARAM(profiledBlock);
 117     UNUSED_PARAM(bytecodeIndex);
 118 #endif
 119
 120     return exitSiteData;
 121 }
 122
 123 #if ENABLE(JIT)
 124 CallLinkStatus CallLinkStatus::computeFor(
 125     const ConcurrentJITLocker& locker, CodeBlock* profiledBlock, CallLinkInfo& callLinkInfo)
 126 {
 127     // We don't really need this, but anytime we have to debug this code, it becomes indispensable.
 128     UNUSED_PARAM(profiledBlock);
 129
 130     CallLinkStatus result = computeFromCallLinkInfo(locker, callLinkInfo);
 131     result.m_maxNumArguments = callLinkInfo.maxNumArguments();
 132     return result;
 133 }
 134
 135 CallLinkStatus CallLinkStatus::computeFromCallLinkInfo(
 136     const ConcurrentJITLocker&, CallLinkInfo& callLinkInfo)
 137 {
 138     if (callLinkInfo.clearedByGC())
 139         return takesSlowPath();
 140
 141     // Note that despite requiring that the locker is held, this code is racy with respect
 142     // to the CallLinkInfo: it may get cleared while this code runs! This is because
 143     // CallLinkInfo::unlink() may be called from a different CodeBlock than the one that owns
 144     // the CallLinkInfo and currently we save space by not having CallLinkInfos know who owns
 145     // them. So, there is no way for either the caller of CallLinkInfo::unlock() or unlock()
 146     // itself to figure out which lock to lock.
 147     //
 148     // Fortunately, that doesn't matter. The only things we ask of CallLinkInfo - the slow
 149     // path count, the stub, and the target - can all be asked racily. Stubs and targets can
 150     // only be deleted at next GC, so if we load a non-null one, then it must contain data
 151     // that is still marginally valid (i.e. the pointers ain't stale). This kind of raciness
 152     // is probably OK for now.
 153
 154     // PolymorphicCallStubRoutine is a GCAwareJITStubRoutine, so if non-null, it will stay alive
 155     // until next GC even if the CallLinkInfo is concurrently cleared. Also, the variants list is
 156     // never mutated after the PolymorphicCallStubRoutine is instantiated. We have some conservative
 157     // fencing in place to make sure that we see the variants list after construction.
 158     if (PolymorphicCallStubRoutine* stub = callLinkInfo.stub()) {
 159         WTF::loadLoadFence();
 160
 161         CallEdgeList edges = stub->edges();
 162
 163         // Now that we've loaded the edges list, there are no further concurrency concerns. We will
 164         // just manipulate and prune this list to our liking - mostly removing entries that are too
 165         // infrequent and ensuring that it's sorted in descending order of frequency.
 166
 167         RELEASE_ASSERT(edges.size());
 168
 169         std::sort(
 170             edges.begin(), edges.end(),
 171             [] (CallEdge a, CallEdge b) {
 172                 return a.count() > b.count();
 173             });
 174         RELEASE_ASSERT(edges.first().count() >= edges.last().count());
 175
 176         double totalCallsToKnown = 0;
 177         double totalCallsToUnknown = callLinkInfo.slowPathCount();
 178         CallVariantList variants;
 179         for (size_t i = 0; i < edges.size(); ++i) {
 180             CallEdge edge = edges[i];
 181             // If the call is at the tail of the distribution, then we don't optimize it and we
 182             // treat it as if it was a call to something unknown. We define the tail as being either
 183             // a call that doesn't belong to the N most frequent callees (N =
 184             // maxPolymorphicCallVariantsForInlining) or that has a total call count that is too
 185             // small.
 186             if (i >= Options::maxPolymorphicCallVariantsForInlining()
 187                 || edge.count() < Options::frequentCallThreshold())
 188                 totalCallsToUnknown += edge.count();
 189             else {
 190                 totalCallsToKnown += edge.count();
 191                 variants.append(edge.callee());
 192             }
 193         }
 194
 195         // Bail if we didn't find any calls that qualified.
 196         RELEASE_ASSERT(!!totalCallsToKnown == !!variants.size());
 197         if (variants.isEmpty())
 198             return takesSlowPath();
 199
 200         // We require that the distribution of callees is skewed towards a handful of common ones.
 201         if (totalCallsToKnown / totalCallsToUnknown < Options::minimumCallToKnownRate())
 202             return takesSlowPath();
 203
 204         RELEASE_ASSERT(totalCallsToKnown);
 205         RELEASE_ASSERT(variants.size());
 206
 207         CallLinkStatus result;
 208         result.m_variants = variants;
 209         result.m_couldTakeSlowPath = !!totalCallsToUnknown;
 210         return result;
 211     }
 212
 213     CallLinkStatus result;
 214
 215     if (JSFunction* target = callLinkInfo.lastSeenCallee()) {
 216         CallVariant variant(target);
 217         if (callLinkInfo.hasSeenClosure())
 218             variant = variant.despecifiedClosure();
 219         result.m_variants.append(variant);
 220     }
 221
 222     result.m_couldTakeSlowPath = !!callLinkInfo.slowPathCount();
 223
 224     return result;
 225 }
 226
 227 CallLinkStatus CallLinkStatus::computeFor(
 228     const ConcurrentJITLocker& locker, CodeBlock* profiledBlock, CallLinkInfo& callLinkInfo,
 229     ExitSiteData exitSiteData)
 230 {
 231     CallLinkStatus result = computeFor(locker, profiledBlock, callLinkInfo);
 232     if (exitSiteData.m_badFunction)
 233         result.makeClosureCall();
 234     if (exitSiteData.m_takesSlowPath)
 235         result.m_couldTakeSlowPath = true;
 236
 237     return result;
 238 }
 239 #endif
 240
 241 void CallLinkStatus::computeDFGStatuses(
 242     CodeBlock* dfgCodeBlock, CallLinkStatus::ContextMap& map)
 243 {
 244 #if ENABLE(DFG_JIT)
 245     RELEASE_ASSERT(dfgCodeBlock->jitType() == JITCode::DFGJIT);
 246     CodeBlock* baselineCodeBlock = dfgCodeBlock->alternative();
 247     for (auto iter = dfgCodeBlock->callLinkInfosBegin(); !!iter; ++iter) {
 248         CallLinkInfo& info = **iter;
 249         CodeOrigin codeOrigin = info.codeOrigin();
 250
 251         // Check if we had already previously made a terrible mistake in the FTL for this
 252         // code origin. Note that this is approximate because we could have a monovariant
 253         // inline in the FTL that ended up failing. We should fix that at some point by
 254         // having data structures to track the context of frequent exits. This is currently
 255         // challenging because it would require creating a CodeOrigin-based database in
 256         // baseline CodeBlocks, but those CodeBlocks don't really have a place to put the
 257         // InlineCallFrames.
 258         CodeBlock* currentBaseline =
 259             baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, baselineCodeBlock);
 260         ExitSiteData exitSiteData;
 261         {
 262             ConcurrentJITLocker locker(currentBaseline->m_lock);
 263             exitSiteData = computeExitSiteData(
 264                 locker, currentBaseline, codeOrigin.bytecodeIndex);
 265         }
 266
 267         {
 268             ConcurrentJITLocker locker(dfgCodeBlock->m_lock);
 269             map.add(info.codeOrigin(), computeFor(locker, dfgCodeBlock, info, exitSiteData));
 270         }
 271     }
 272 #else
 273     UNUSED_PARAM(dfgCodeBlock);
 274 #endif // ENABLE(DFG_JIT)
 275
 276     if (verbose) {
 277         dataLog("Context map:\n");
 278         ContextMap::iterator iter = map.begin();
 279         ContextMap::iterator end = map.end();
 280         for (; iter != end; ++iter) {
 281             dataLog("    ", iter->key, ":\n");
 282             dataLog("        ", iter->value, "\n");
 283         }
 284     }
 285 }
 286
 287 CallLinkStatus CallLinkStatus::computeFor(
 288     CodeBlock* profiledBlock, CodeOrigin codeOrigin,
 289     const CallLinkInfoMap& baselineMap, const CallLinkStatus::ContextMap& dfgMap)
 290 {
 291     auto iter = dfgMap.find(codeOrigin);
 292     if (iter != dfgMap.end())
 293         return iter->value;
 294
 295     return computeFor(profiledBlock, codeOrigin.bytecodeIndex, baselineMap);
 296 }
 297
 298 void CallLinkStatus::setProvenConstantCallee(CallVariant variant)
 299 {
 300     m_variants = CallVariantList{ variant };
 301     m_couldTakeSlowPath = false;
 302     m_isProved = true;
 303 }
 304
 305 bool CallLinkStatus::isClosureCall() const
 306 {
 307     for (unsigned i = m_variants.size(); i--;) {
 308         if (m_variants[i].isClosureCall())
 309             return true;
 310     }
 311     return false;
 312 }
 313
 314 void CallLinkStatus::makeClosureCall()
 315 {
 316     m_variants = despecifiedVariantList(m_variants);
 317 }
 318
 319 void CallLinkStatus::dump(PrintStream& out) const
 320 {
 321     if (!isSet()) {
 322         out.print("Not Set");
 323         return;
 324     }
 325
 326     CommaPrinter comma;
 327
 328     if (m_isProved)
 329         out.print(comma, "Statically Proved");
 330
 331     if (m_couldTakeSlowPath)
 332         out.print(comma, "Could Take Slow Path");
 333
 334     if (!m_variants.isEmpty())
 335         out.print(comma, listDump(m_variants));
 336
 337     if (m_maxNumArguments)
 338         out.print(comma, "maxNumArguments = ", m_maxNumArguments);
 339 }
 340
 341 } // namespace JSC
 342