Polymorphic call inlining should be based on polymorphic call inline caching rather...
[WebKit-https.git] / Source / JavaScriptCore / 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     ExitingJITType exitingJITType)
106 {
107     ExitSiteData exitSiteData;
108     
109 #if ENABLE(DFG_JIT)
110     exitSiteData.m_takesSlowPath =
111         profiledBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadType, exitingJITType))
112         || profiledBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadExecutable, exitingJITType));
113     exitSiteData.m_badFunction =
114         profiledBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadCell, exitingJITType));
115 #else
116     UNUSED_PARAM(locker);
117     UNUSED_PARAM(profiledBlock);
118     UNUSED_PARAM(bytecodeIndex);
119     UNUSED_PARAM(exitingJITType);
120 #endif
121     
122     return exitSiteData;
123 }
124
125 #if ENABLE(JIT)
126 CallLinkStatus CallLinkStatus::computeFor(
127     const ConcurrentJITLocker& locker, CodeBlock* profiledBlock, CallLinkInfo& callLinkInfo)
128 {
129     // We don't really need this, but anytime we have to debug this code, it becomes indispensable.
130     UNUSED_PARAM(profiledBlock);
131     
132     return computeFromCallLinkInfo(locker, callLinkInfo);
133 }
134
135 CallLinkStatus CallLinkStatus::computeFromCallLinkInfo(
136     const ConcurrentJITLocker&, CallLinkInfo& callLinkInfo)
137 {
138     // Note that despite requiring that the locker is held, this code is racy with respect
139     // to the CallLinkInfo: it may get cleared while this code runs! This is because
140     // CallLinkInfo::unlink() may be called from a different CodeBlock than the one that owns
141     // the CallLinkInfo and currently we save space by not having CallLinkInfos know who owns
142     // them. So, there is no way for either the caller of CallLinkInfo::unlock() or unlock()
143     // itself to figure out which lock to lock.
144     //
145     // Fortunately, that doesn't matter. The only things we ask of CallLinkInfo - the slow
146     // path count, the stub, and the target - can all be asked racily. Stubs and targets can
147     // only be deleted at next GC, so if we load a non-null one, then it must contain data
148     // that is still marginally valid (i.e. the pointers ain't stale). This kind of raciness
149     // is probably OK for now.
150     
151     // PolymorphicCallStubRoutine is a GCAwareJITStubRoutine, so if non-null, it will stay alive
152     // until next GC even if the CallLinkInfo is concurrently cleared. Also, the variants list is
153     // never mutated after the PolymorphicCallStubRoutine is instantiated. We have some conservative
154     // fencing in place to make sure that we see the variants list after construction.
155     if (PolymorphicCallStubRoutine* stub = callLinkInfo.stub.get()) {
156         WTF::loadLoadFence();
157         
158         CallEdgeList edges = stub->edges();
159         
160         // Now that we've loaded the edges list, there are no further concurrency concerns. We will
161         // just manipulate and prune this list to our liking - mostly removing entries that are too
162         // infrequent and ensuring that it's sorted in descending order of frequency.
163         
164         RELEASE_ASSERT(edges.size());
165         
166         std::sort(
167             edges.begin(), edges.end(),
168             [] (CallEdge a, CallEdge b) {
169                 return a.count() > b.count();
170             });
171         RELEASE_ASSERT(edges.first().count() >= edges.last().count());
172         
173         double totalCallsToKnown = 0;
174         double totalCallsToUnknown = callLinkInfo.slowPathCount;
175         CallVariantList variants;
176         for (size_t i = 0; i < edges.size(); ++i) {
177             CallEdge edge = edges[i];
178             // If the call is at the tail of the distribution, then we don't optimize it and we
179             // treat it as if it was a call to something unknown. We define the tail as being either
180             // a call that doesn't belong to the N most frequent callees (N =
181             // maxPolymorphicCallVariantsForInlining) or that has a total call count that is too
182             // small.
183             if (i >= Options::maxPolymorphicCallVariantsForInlining()
184                 || edge.count() < Options::frequentCallThreshold())
185                 totalCallsToUnknown += edge.count();
186             else {
187                 totalCallsToKnown += edge.count();
188                 variants.append(edge.callee());
189             }
190         }
191         
192         // Bail if we didn't find any calls that qualified.
193         RELEASE_ASSERT(!!totalCallsToKnown == !!variants.size());
194         if (variants.isEmpty())
195             return takesSlowPath();
196         
197         // We require that the distribution of callees is skewed towards a handful of common ones.
198         if (totalCallsToKnown / totalCallsToUnknown < Options::minimumCallToKnownRate())
199             return takesSlowPath();
200         
201         RELEASE_ASSERT(totalCallsToKnown);
202         RELEASE_ASSERT(variants.size());
203         
204         CallLinkStatus result;
205         result.m_variants = variants;
206         result.m_couldTakeSlowPath = !!totalCallsToUnknown;
207         return result;
208     }
209     
210     if (callLinkInfo.slowPathCount >= Options::couldTakeSlowCaseMinimumCount())
211         return takesSlowPath();
212     
213     JSFunction* target = callLinkInfo.lastSeenCallee.get();
214     if (!target)
215         return takesSlowPath();
216     
217     if (callLinkInfo.hasSeenClosure)
218         return CallLinkStatus(target->executable());
219
220     return CallLinkStatus(target);
221 }
222
223 CallLinkStatus CallLinkStatus::computeFor(
224     const ConcurrentJITLocker& locker, CodeBlock* profiledBlock, CallLinkInfo& callLinkInfo,
225     ExitSiteData exitSiteData)
226 {
227     CallLinkStatus result = computeFor(locker, profiledBlock, callLinkInfo);
228     if (exitSiteData.m_badFunction)
229         result.makeClosureCall();
230     if (exitSiteData.m_takesSlowPath)
231         result.m_couldTakeSlowPath = true;
232     
233     return result;
234 }
235 #endif
236
237 void CallLinkStatus::computeDFGStatuses(
238     CodeBlock* dfgCodeBlock, CallLinkStatus::ContextMap& map)
239 {
240 #if ENABLE(DFG_JIT)
241     RELEASE_ASSERT(dfgCodeBlock->jitType() == JITCode::DFGJIT);
242     CodeBlock* baselineCodeBlock = dfgCodeBlock->alternative();
243     for (auto iter = dfgCodeBlock->callLinkInfosBegin(); !!iter; ++iter) {
244         CallLinkInfo& info = **iter;
245         CodeOrigin codeOrigin = info.codeOrigin;
246         
247         // Check if we had already previously made a terrible mistake in the FTL for this
248         // code origin. Note that this is approximate because we could have a monovariant
249         // inline in the FTL that ended up failing. We should fix that at some point by
250         // having data structures to track the context of frequent exits. This is currently
251         // challenging because it would require creating a CodeOrigin-based database in
252         // baseline CodeBlocks, but those CodeBlocks don't really have a place to put the
253         // InlineCallFrames.
254         CodeBlock* currentBaseline =
255             baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, baselineCodeBlock);
256         ExitSiteData exitSiteData;
257         {
258             ConcurrentJITLocker locker(currentBaseline->m_lock);
259             exitSiteData = computeExitSiteData(
260                 locker, currentBaseline, codeOrigin.bytecodeIndex, ExitFromFTL);
261         }
262         
263         {
264             ConcurrentJITLocker locker(dfgCodeBlock->m_lock);
265             map.add(info.codeOrigin, computeFor(locker, dfgCodeBlock, info, exitSiteData));
266         }
267     }
268 #else
269     UNUSED_PARAM(dfgCodeBlock);
270 #endif // ENABLE(DFG_JIT)
271     
272     if (verbose) {
273         dataLog("Context map:\n");
274         ContextMap::iterator iter = map.begin();
275         ContextMap::iterator end = map.end();
276         for (; iter != end; ++iter) {
277             dataLog("    ", iter->key, ":\n");
278             dataLog("        ", iter->value, "\n");
279         }
280     }
281 }
282
283 CallLinkStatus CallLinkStatus::computeFor(
284     CodeBlock* profiledBlock, CodeOrigin codeOrigin,
285     const CallLinkInfoMap& baselineMap, const CallLinkStatus::ContextMap& dfgMap)
286 {
287     auto iter = dfgMap.find(codeOrigin);
288     if (iter != dfgMap.end())
289         return iter->value;
290     
291     return computeFor(profiledBlock, codeOrigin.bytecodeIndex, baselineMap);
292 }
293
294 bool CallLinkStatus::isClosureCall() const
295 {
296     for (unsigned i = m_variants.size(); i--;) {
297         if (m_variants[i].isClosureCall())
298             return true;
299     }
300     return false;
301 }
302
303 void CallLinkStatus::makeClosureCall()
304 {
305     m_variants = despecifiedVariantList(m_variants);
306 }
307
308 void CallLinkStatus::dump(PrintStream& out) const
309 {
310     if (!isSet()) {
311         out.print("Not Set");
312         return;
313     }
314     
315     CommaPrinter comma;
316     
317     if (m_isProved)
318         out.print(comma, "Statically Proved");
319     
320     if (m_couldTakeSlowPath)
321         out.print(comma, "Could Take Slow Path");
322     
323     if (!m_variants.isEmpty())
324         out.print(comma, listDump(m_variants));
325 }
326
327 } // namespace JSC
328