js/src/jit/JitHints.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef jit_JitHints_h
   8 #define jit_JitHints_h
   9
  10 #include "mozilla/BloomFilter.h"
  11 #include "mozilla/HashTable.h"
  12 #include "mozilla/LinkedList.h"
  13 #include "jit/JitOptions.h"
  14 #include "vm/BytecodeLocation.h"
  15 #include "vm/JSScript.h"
  16
  17 namespace js::jit {
  18
  19 /*
  20  *
  21  * [SMDOC] JitHintsMap
  22  *
  23  * The Jit hints map is an in process cache used to collect Baseline and Ion
  24  * JIT hints to try and skip as much of the warmup as possible and jump
  25  * straight into those tiers.  Whenever a script enters one of these tiers
  26  * a hint is recorded in this cache using the script's filename+sourceStart
  27  * value, and if we ever encounter this script again later, e.g. during a
  28  * navigation, then we try to eagerly compile it into baseline and ion
  29  * based on its previous execution history.
  30  */
  31
  32 class JitHintsMap {
  33   // ScriptKey is a hash on the filename+sourceStart.
  34   using ScriptKey = HashNumber;
  35   ScriptKey getScriptKey(JSScript* script) const;
  36
  37   /* Ion Hints
  38    * -------------------------------------------------------------------------
  39    * This implementation uses a combination of a HashMap and PriorityQueue
  40    * to store a threshold value for each script that has been Ion compiled.
  41    * The PriorityQueue is used to track the least recently used entries so
  42    * that the cache does not exceed |IonHintMaxEntries| entries.
  43    *
  44    * After a script has entered Ion the first time, an eager threshold hint
  45    * value is set using the warmup counter of when the last IC stub was
  46    * attached, if available. This minimizes the risk that the script will
  47    * bailout. If that script is bailout invalidated, the threshold value
  48    * is incremented by |InvalidationThresholdIncrement| up to a maximum value of
  49    * |JitOptions.normalIonWarmUpThreshold|.
  50    *
  51    * Each IonHint object also contains a list of bytecode offsets for locations
  52    * of monomorphic inline calls that is used as a hint for future compilations.
  53    *
  54    */
  55   class IonHint : public mozilla::LinkedListElement<IonHint> {
  56     ScriptKey key_ = 0;
  57
  58     // We use a value of 0 to indicate that the script has not entered Ion
  59     // yet, but has been monomorphically inlined and Ion compiled into
  60     // another script and contains bytecode offsets of a nested call.
  61     uint32_t threshold_ = 0;
  62
  63     // List of bytecode offsets that have been successfully inlined with
  64     // a state of monomorphic inline.
  65     Vector<uint32_t, 0, SystemAllocPolicy> monomorphicInlineOffsets;
  66
  67    public:
  68     explicit IonHint(ScriptKey key) { key_ = key; }
  69
  70     void initThreshold(uint32_t lastStubCounter) {
  71       threshold_ = IonHintEagerThresholdValue(lastStubCounter);
  72     }
  73
  74     uint32_t threshold() { return threshold_; }
  75
  76     void incThreshold(uint32_t inc) {
  77       uint32_t newThreshold = threshold() + inc;
  78       threshold_ = (newThreshold > JitOptions.normalIonWarmUpThreshold)
  79                        ? JitOptions.normalIonWarmUpThreshold
  80                        : newThreshold;
  81     }
  82
  83     bool hasSpaceForMonomorphicInlineEntry() {
  84       return monomorphicInlineOffsets.length() < MonomorphicInlineMaxEntries;
  85     }
  86
  87     bool hasMonomorphicInlineOffset(uint32_t offset) {
  88       for (uint32_t iterOffset : monomorphicInlineOffsets) {
  89         if (iterOffset == offset) {
  90           return true;
  91         }
  92       }
  93       return false;
  94     }
  95
  96     bool addMonomorphicInlineOffset(uint32_t newOffset) {
  97       MOZ_ASSERT(hasSpaceForMonomorphicInlineEntry());
  98
  99       if (hasMonomorphicInlineOffset(newOffset)) {
 100         return true;
 101       }
 102       return monomorphicInlineOffsets.append(newOffset);
 103     }
 104
 105     ScriptKey key() {
 106       MOZ_ASSERT(key_ != 0, "Should have valid key.");
 107       return key_;
 108     }
 109   };
 110
 111   using ScriptToHintMap =
 112       HashMap<ScriptKey, IonHint*, js::DefaultHasher<ScriptKey>,
 113               js::SystemAllocPolicy>;
 114   using IonHintPriorityQueue = mozilla::LinkedList<IonHint>;
 115
 116   static constexpr uint32_t InvalidationThresholdIncrement = 500;
 117   static constexpr uint32_t IonHintMaxEntries = 5000;
 118   static constexpr uint32_t MonomorphicInlineMaxEntries = 16;
 119
 120   static uint32_t IonHintEagerThresholdValue(uint32_t lastStubCounter) {
 121     // Use the counter when the last IC stub was attached but add 10
 122     // for some wiggle room and to safeguard against cases where the
 123     // lastStubCounter is 0.
 124     uint32_t eagerThreshold = lastStubCounter + 10;
 125
 126     // Do not exceed the default Ion threshold value set in the options.
 127     return std::min(eagerThreshold, JitOptions.normalIonWarmUpThreshold);
 128   }
 129
 130   ScriptToHintMap ionHintMap_;
 131   IonHintPriorityQueue ionHintQueue_;
 132
 133   /* Baseline Hints
 134    * --------------------------------------------------------------------------
 135    * This implementation uses a BitBloomFilter to track whether or not a script
 136    * has been baseline compiled before in the same process.  This can occur
 137    * frequently during navigations.
 138    *
 139    * The bloom filter allows us to have very efficient storage and lookup costs,
 140    * at the expense of occasional false positives.  Using a bloom filter also
 141    * allows us to have many more entries at minimal memory and allocation cost.
 142    * The number of entries added to the bloom filter is monitored in order to
 143    * try and keep the false positivity rate below 1%.  If the entry count
 144    * exceeds MaxEntries_, which indicates the false positivity rate may exceed
 145    * 1.5%, then the filter is completely cleared to reset the cache.
 146    */
 147   static constexpr uint32_t EagerBaselineCacheSize_ = 16;
 148   mozilla::BitBloomFilter<EagerBaselineCacheSize_, ScriptKey> baselineHintMap_;
 149
 150   /*
 151    * MaxEntries_ is the approximate entry count for which the
 152    * false positivity rate will exceed p=0.015 using k=2 and m=2**CacheSize.
 153    * Formula is as follows:
 154    * MaxEntries_ = floor(m / (-k / ln(1-exp(ln(p) / k))))
 155    */
 156   static constexpr uint32_t MaxEntries_ = 4281;
 157   static_assert(EagerBaselineCacheSize_ == 16 && MaxEntries_ == 4281,
 158                 "MaxEntries should be recalculated for given CacheSize.");
 159
 160   uint32_t baselineEntryCount_ = 0;
 161   void incrementBaselineEntryCount();
 162
 163   void updateAsRecentlyUsed(IonHint* hint);
 164   IonHint* addIonHint(ScriptKey key, ScriptToHintMap::AddPtr& p);
 165
 166  public:
 167   ~JitHintsMap();
 168
 169   void setEagerBaselineHint(JSScript* script);
 170   bool mightHaveEagerBaselineHint(JSScript* script) const;
 171
 172   bool recordIonCompilation(JSScript* script);
 173   bool getIonThresholdHint(JSScript* script, uint32_t& thresholdOut);
 174
 175   bool addMonomorphicInlineLocation(JSScript* script, BytecodeLocation loc);
 176   bool hasMonomorphicInlineHintAtOffset(JSScript* script, uint32_t offset);
 177
 178   void recordInvalidation(JSScript* script);
 179 };
 180
 181 }  // namespace js::jit
 182 #endif /* jit_JitHints_h */