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