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