We should support CreateThis in the FTL
[WebKit-https.git] / Source / JavaScriptCore / bytecode / CallLinkStatus.cpp
1 /*
2  * Copyright (C) 2012-2018 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 "InterpreterInlines.h"
34 #include "LLIntCallLinkInfo.h"
35 #include "JSCInlines.h"
36 #include <wtf/CommaPrinter.h>
37 #include <wtf/ListDump.h>
38
39 namespace JSC {
40
41 namespace CallLinkStatusInternal {
42 static const bool verbose = false;
43 }
44
45 CallLinkStatus::CallLinkStatus(JSValue value)
46     : m_couldTakeSlowPath(false)
47     , m_isProved(false)
48 {
49     if (!value || !value.isCell()) {
50         m_couldTakeSlowPath = true;
51         return;
52     }
53     
54     m_variants.append(CallVariant(value.asCell()));
55 }
56
57 CallLinkStatus CallLinkStatus::computeFromLLInt(const ConcurrentJSLocker&, CodeBlock* profiledBlock, unsigned bytecodeIndex)
58 {
59     UNUSED_PARAM(profiledBlock);
60     UNUSED_PARAM(bytecodeIndex);
61 #if ENABLE(DFG_JIT)
62     if (profiledBlock->unlinkedCodeBlock()->hasExitSite(DFG::FrequentExitSite(bytecodeIndex, BadCell))) {
63         // We could force this to be a closure call, but instead we'll just assume that it
64         // takes slow path.
65         return takesSlowPath();
66     }
67 #endif
68
69     Instruction* instruction = &profiledBlock->instructions()[bytecodeIndex];
70     OpcodeID op = Interpreter::getOpcodeID(instruction[0].u.opcode);
71     if (op != op_call && op != op_construct && op != op_tail_call)
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 ICStatusMap& map,
81     ExitSiteData exitSiteData)
82 {
83     ConcurrentJSLocker locker(profiledBlock->m_lock);
84     
85     UNUSED_PARAM(profiledBlock);
86     UNUSED_PARAM(bytecodeIndex);
87     UNUSED_PARAM(map);
88 #if ENABLE(DFG_JIT)
89     CallLinkInfo* callLinkInfo = map.get(CodeOrigin(bytecodeIndex)).callLinkInfo;
90     if (!callLinkInfo) {
91         if (exitSiteData.takesSlowPath)
92             return takesSlowPath();
93         return computeFromLLInt(locker, profiledBlock, bytecodeIndex);
94     }
95     
96     return computeFor(locker, profiledBlock, *callLinkInfo, exitSiteData);
97 #else
98     return CallLinkStatus();
99 #endif
100 }
101
102 CallLinkStatus CallLinkStatus::computeFor(
103     CodeBlock* profiledBlock, unsigned bytecodeIndex, const ICStatusMap& map)
104 {
105     return computeFor(profiledBlock, bytecodeIndex, map, computeExitSiteData(profiledBlock, bytecodeIndex));
106 }
107
108 CallLinkStatus::ExitSiteData CallLinkStatus::computeExitSiteData(CodeBlock* profiledBlock, unsigned bytecodeIndex)
109 {
110     ExitSiteData exitSiteData;
111 #if ENABLE(DFG_JIT)
112     UnlinkedCodeBlock* codeBlock = profiledBlock->unlinkedCodeBlock();
113     ConcurrentJSLocker locker(codeBlock->m_lock);
114
115     auto takesSlowPath = [&] (ExitingInlineKind inlineKind) -> ExitFlag {
116         return ExitFlag(
117             codeBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadType, ExitFromAnything, inlineKind))
118             || codeBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadExecutable, ExitFromAnything, inlineKind)),
119             inlineKind);
120     };
121     
122     auto badFunction = [&] (ExitingInlineKind inlineKind) -> ExitFlag {
123         return ExitFlag(codeBlock->hasExitSite(locker, DFG::FrequentExitSite(bytecodeIndex, BadCell, ExitFromAnything, inlineKind)), inlineKind);
124     };
125     
126     exitSiteData.takesSlowPath |= takesSlowPath(ExitFromNotInlined);
127     exitSiteData.takesSlowPath |= takesSlowPath(ExitFromInlined);
128     exitSiteData.badFunction |= badFunction(ExitFromNotInlined);
129     exitSiteData.badFunction |= badFunction(ExitFromInlined);
130 #else
131     UNUSED_PARAM(profiledBlock);
132     UNUSED_PARAM(bytecodeIndex);
133 #endif
134     
135     return exitSiteData;
136 }
137
138 #if ENABLE(JIT)
139 CallLinkStatus CallLinkStatus::computeFor(
140     const ConcurrentJSLocker& locker, CodeBlock* profiledBlock, CallLinkInfo& callLinkInfo)
141 {
142     // We don't really need this, but anytime we have to debug this code, it becomes indispensable.
143     UNUSED_PARAM(profiledBlock);
144     
145     CallLinkStatus result = computeFromCallLinkInfo(locker, callLinkInfo);
146     result.m_maxNumArguments = callLinkInfo.maxNumArguments();
147     return result;
148 }
149
150 CallLinkStatus CallLinkStatus::computeFromCallLinkInfo(
151     const ConcurrentJSLocker&, CallLinkInfo& callLinkInfo)
152 {
153     // We cannot tell you anything about direct calls.
154     if (callLinkInfo.isDirect())
155         return CallLinkStatus();
156     
157     if (callLinkInfo.clearedByGC() || callLinkInfo.clearedByVirtual())
158         return takesSlowPath();
159     
160     // Note that despite requiring that the locker is held, this code is racy with respect
161     // to the CallLinkInfo: it may get cleared while this code runs! This is because
162     // CallLinkInfo::unlink() may be called from a different CodeBlock than the one that owns
163     // the CallLinkInfo and currently we save space by not having CallLinkInfos know who owns
164     // them. So, there is no way for either the caller of CallLinkInfo::unlock() or unlock()
165     // itself to figure out which lock to lock.
166     //
167     // Fortunately, that doesn't matter. The only things we ask of CallLinkInfo - the slow
168     // path count, the stub, and the target - can all be asked racily. Stubs and targets can
169     // only be deleted at next GC, so if we load a non-null one, then it must contain data
170     // that is still marginally valid (i.e. the pointers ain't stale). This kind of raciness
171     // is probably OK for now.
172     
173     // PolymorphicCallStubRoutine is a GCAwareJITStubRoutine, so if non-null, it will stay alive
174     // until next GC even if the CallLinkInfo is concurrently cleared. Also, the variants list is
175     // never mutated after the PolymorphicCallStubRoutine is instantiated. We have some conservative
176     // fencing in place to make sure that we see the variants list after construction.
177     if (PolymorphicCallStubRoutine* stub = callLinkInfo.stub()) {
178         WTF::loadLoadFence();
179         
180         if (!stub->hasEdges()) {
181             // This means we have an FTL profile, which has incomplete information.
182             //
183             // It's not clear if takesSlowPath() or CallLinkStatus() are appropriate here, but I
184             // think that takesSlowPath() is a narrow winner.
185             //
186             // Either way, this is telling us that the FTL had been led to believe that it's
187             // profitable not to inline anything.
188             return takesSlowPath();
189         }
190         
191         CallEdgeList edges = stub->edges();
192         
193         // Now that we've loaded the edges list, there are no further concurrency concerns. We will
194         // just manipulate and prune this list to our liking - mostly removing entries that are too
195         // infrequent and ensuring that it's sorted in descending order of frequency.
196         
197         RELEASE_ASSERT(edges.size());
198         
199         std::sort(
200             edges.begin(), edges.end(),
201             [] (CallEdge a, CallEdge b) {
202                 return a.count() > b.count();
203             });
204         RELEASE_ASSERT(edges.first().count() >= edges.last().count());
205         
206         double totalCallsToKnown = 0;
207         double totalCallsToUnknown = callLinkInfo.slowPathCount();
208         CallVariantList variants;
209         for (size_t i = 0; i < edges.size(); ++i) {
210             CallEdge edge = edges[i];
211             // If the call is at the tail of the distribution, then we don't optimize it and we
212             // treat it as if it was a call to something unknown. We define the tail as being either
213             // a call that doesn't belong to the N most frequent callees (N =
214             // maxPolymorphicCallVariantsForInlining) or that has a total call count that is too
215             // small.
216             if (i >= Options::maxPolymorphicCallVariantsForInlining()
217                 || edge.count() < Options::frequentCallThreshold())
218                 totalCallsToUnknown += edge.count();
219             else {
220                 totalCallsToKnown += edge.count();
221                 variants.append(edge.callee());
222             }
223         }
224         
225         // Bail if we didn't find any calls that qualified.
226         RELEASE_ASSERT(!!totalCallsToKnown == !!variants.size());
227         if (variants.isEmpty())
228             return takesSlowPath();
229         
230         // We require that the distribution of callees is skewed towards a handful of common ones.
231         if (totalCallsToKnown / totalCallsToUnknown < Options::minimumCallToKnownRate())
232             return takesSlowPath();
233         
234         RELEASE_ASSERT(totalCallsToKnown);
235         RELEASE_ASSERT(variants.size());
236         
237         CallLinkStatus result;
238         result.m_variants = variants;
239         result.m_couldTakeSlowPath = !!totalCallsToUnknown;
240         result.m_isBasedOnStub = true;
241         return result;
242     }
243     
244     CallLinkStatus result;
245     
246     if (JSObject* target = callLinkInfo.lastSeenCallee()) {
247         CallVariant variant(target);
248         if (callLinkInfo.hasSeenClosure())
249             variant = variant.despecifiedClosure();
250         result.m_variants.append(variant);
251     }
252     
253     result.m_couldTakeSlowPath = !!callLinkInfo.slowPathCount();
254
255     return result;
256 }
257
258 CallLinkStatus CallLinkStatus::computeFor(
259     const ConcurrentJSLocker& locker, CodeBlock* profiledBlock, CallLinkInfo& callLinkInfo,
260     ExitSiteData exitSiteData, ExitingInlineKind inlineKind)
261 {
262     CallLinkStatus result = computeFor(locker, profiledBlock, callLinkInfo);
263     result.accountForExits(exitSiteData, inlineKind);
264     return result;
265 }
266 #endif
267
268 void CallLinkStatus::accountForExits(ExitSiteData exitSiteData, ExitingInlineKind inlineKind)
269 {
270     if (exitSiteData.badFunction.isSet(inlineKind)) {
271         if (isBasedOnStub()) {
272             // If we have a polymorphic stub, then having an exit site is not quite so useful. In
273             // most cases, the information in the stub has higher fidelity.
274             makeClosureCall();
275         } else {
276             // We might not have a polymorphic stub for any number of reasons. When this happens, we
277             // are in less certain territory, so exit sites mean a lot.
278             m_couldTakeSlowPath = true;
279         }
280     }
281     
282     if (exitSiteData.takesSlowPath.isSet(inlineKind))
283         m_couldTakeSlowPath = true;
284 }
285
286 CallLinkStatus CallLinkStatus::computeFor(
287     CodeBlock* profiledBlock, CodeOrigin codeOrigin,
288     const ICStatusMap& baselineMap, const ICStatusContextStack& optimizedStack)
289 {
290     if (CallLinkStatusInternal::verbose)
291         dataLog("Figuring out call profiling for ", codeOrigin, "\n");
292     ExitSiteData exitSiteData = computeExitSiteData(profiledBlock, codeOrigin.bytecodeIndex);
293     if (CallLinkStatusInternal::verbose) {
294         dataLog("takesSlowPath = ", exitSiteData.takesSlowPath, "\n");
295         dataLog("badFunction = ", exitSiteData.badFunction, "\n");
296     }
297     
298     for (const ICStatusContext* context : optimizedStack) {
299         if (CallLinkStatusInternal::verbose)
300             dataLog("Examining status in ", pointerDump(context->optimizedCodeBlock), "\n");
301         ICStatus status = context->get(codeOrigin);
302         
303         // If we have both a CallLinkStatus and a callLinkInfo for the same origin, then it means
304         // one of two things:
305         //
306         // 1) We initially thought that we'd be able to inline this call so we recorded a status
307         //    but then we realized that it was pointless and gave up and emitted a normal call
308         //    anyway.
309         //
310         // 2) We did a polymorphic call inline that had a slow path case.
311         //
312         // In the first case, it's essential that we use the callLinkInfo, since the status may
313         // be polymorphic but the link info benefits from polyvariant profiling.
314         //
315         // In the second case, it's essential that we use the status, since the callLinkInfo
316         // corresponds to the slow case.
317         //
318         // It would be annoying to distinguish those two cases. However, we know that:
319         //
320         // If the first case happens in the FTL, then it means that even with polyvariant
321         // profiling, we failed to do anything useful. That suggests that in the FTL, it's OK to
322         // prioritize the status. That status will again tell us to not do anything useful.
323         //
324         // The second case only happens in the FTL.
325         //
326         // Therefore, we prefer the status in the FTL and the info in the DFG.
327         //
328         // Luckily, this case doesn't matter for the other ICStatuses, since they never do the
329         // fast-path-slow-path control-flow-diamond style of IC inlining. It's either all fast
330         // path or it's a full IC. So, for them, if there is an IC status then it means case (1).
331         
332         bool checkStatusFirst = context->optimizedCodeBlock->jitType() == JITCode::FTLJIT;
333         
334         auto bless = [&] (CallLinkStatus& result) {
335             if (!context->isInlined(codeOrigin))
336                 result.merge(computeFor(profiledBlock, codeOrigin.bytecodeIndex, baselineMap, exitSiteData));
337         };
338         
339         auto checkInfo = [&] () -> CallLinkStatus {
340             if (!status.callLinkInfo)
341                 return CallLinkStatus();
342             
343             if (CallLinkStatusInternal::verbose)
344                 dataLog("Have CallLinkInfo with CodeOrigin = ", status.callLinkInfo->codeOrigin(), "\n");
345             CallLinkStatus result;
346             {
347                 ConcurrentJSLocker locker(context->optimizedCodeBlock->m_lock);
348                 result = computeFor(
349                     locker, context->optimizedCodeBlock, *status.callLinkInfo, exitSiteData,
350                     context->inlineKind(codeOrigin));
351                 if (CallLinkStatusInternal::verbose)
352                     dataLog("Got result: ", result, "\n");
353             }
354             bless(result);
355             return result;
356         };
357         
358         auto checkStatus = [&] () -> CallLinkStatus {
359             if (!status.callStatus)
360                 return CallLinkStatus();
361             CallLinkStatus result = *status.callStatus;
362             if (CallLinkStatusInternal::verbose)
363                 dataLog("Have callStatus: ", result, "\n");
364             result.accountForExits(exitSiteData, context->inlineKind(codeOrigin));
365             bless(result);
366             return result;
367         };
368         
369         if (checkStatusFirst) {
370             if (CallLinkStatus result = checkStatus())
371                 return result;
372             if (CallLinkStatus result = checkInfo())
373                 return result;
374             continue;
375         }
376         
377         if (CallLinkStatus result = checkInfo())
378             return result;
379         if (CallLinkStatus result = checkStatus())
380             return result;
381     }
382     
383     return computeFor(profiledBlock, codeOrigin.bytecodeIndex, baselineMap, exitSiteData);
384 }
385
386 void CallLinkStatus::setProvenConstantCallee(CallVariant variant)
387 {
388     m_variants = CallVariantList{ variant };
389     m_couldTakeSlowPath = false;
390     m_isProved = true;
391 }
392
393 bool CallLinkStatus::isClosureCall() const
394 {
395     for (unsigned i = m_variants.size(); i--;) {
396         if (m_variants[i].isClosureCall())
397             return true;
398     }
399     return false;
400 }
401
402 void CallLinkStatus::makeClosureCall()
403 {
404     m_variants = despecifiedVariantList(m_variants);
405 }
406
407 bool CallLinkStatus::finalize()
408 {
409     for (CallVariant& variant : m_variants) {
410         if (!variant.finalize())
411             return false;
412     }
413     return true;
414 }
415
416 void CallLinkStatus::merge(const CallLinkStatus& other)
417 {
418     m_couldTakeSlowPath |= other.m_couldTakeSlowPath;
419     
420     for (const CallVariant& otherVariant : other.m_variants) {
421         bool found = false;
422         for (CallVariant& thisVariant : m_variants) {
423             if (thisVariant.merge(otherVariant)) {
424                 found = true;
425                 break;
426             }
427         }
428         if (!found)
429             m_variants.append(otherVariant);
430     }
431 }
432
433 void CallLinkStatus::filter(VM& vm, JSValue value)
434 {
435     m_variants.removeAllMatching(
436         [&] (CallVariant& variant) -> bool {
437             variant.filter(vm, value);
438             return !variant;
439         });
440 }
441
442 void CallLinkStatus::dump(PrintStream& out) const
443 {
444     if (!isSet()) {
445         out.print("Not Set");
446         return;
447     }
448     
449     CommaPrinter comma;
450     
451     if (m_isProved)
452         out.print(comma, "Statically Proved");
453     
454     if (m_couldTakeSlowPath)
455         out.print(comma, "Could Take Slow Path");
456     
457     if (m_isBasedOnStub)
458         out.print(comma, "Based On Stub");
459     
460     if (!m_variants.isEmpty())
461         out.print(comma, listDump(m_variants));
462     
463     if (m_maxNumArguments)
464         out.print(comma, "maxNumArguments = ", m_maxNumArguments);
465 }
466
467 } // namespace JSC
468