hphp/runtime/vm/jit/array-access-profile.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #pragma once
  18
  19 #include "hphp/runtime/vm/jit/extra-data.h"
  20
  21 #include <folly/dynamic.h>
  22
  23 #include <cstdint>
  24
  25 namespace HPHP {
  26
  27 struct ArrayData;
  28 struct StringData;
  29
  30 namespace jit {
  31
  32 ///////////////////////////////////////////////////////////////////////////////
  33
  34 /*
  35  * Target profile used to optimize vanilla dict and keyset hash table lookups.
  36  * This profile can be used for two types of optimizations:
  37  *
  38  *  - Offset profiling: If the array used at a certain source location always
  39  *    has the same "shape" (the same keys, inserted in the same order), then a
  40  *    given string will always be at the same offset. We can check it directly.
  41  *
  42  *  - Size profiling: If the array used at a certain source location tends to
  43  *    be small, we might want to do the lookup by scanning instead of hashing.
  44  *
  45  *  - Empty profiling: If the array is empty, any lookup will fail. In this
  46  *    case, we first check the size of the array.
  47  *
  48  *  - Missing element profiling: If the array used at a certain source location
  49  *    with the given key tends to not have the given key, we first check
  50  *    whether this key exists in the array by a fast side table lookup.
  51  */
  52 struct ArrayAccessProfile {
  53   enum class Action { None, Cold, Exit };
  54   /*
  55    * The result of both profiling types. Prefer the offset to the size hint.
  56    */
  57   struct Result {
  58     std::pair<Action, uint32_t> offset;
  59     SizeHintData size_hint;
  60     Action empty;
  61     Action missing;
  62     Action nocow;
  63     std::string toString() const;
  64   };
  65
  66   /*
  67    * Returns profiling results based on questionable heuristics.
  68    */
  69   Result choose() const;
  70
  71   /*
  72    * Update the profile to register an access at `key' in `ad'.
  73    */
  74   void update(const ArrayData* ad, int64_t key, DecRefProfileEntry*);
  75   void update(const ArrayData* ad, const StringData* key, DecRefProfileEntry*);
  76
  77   /*
  78    * Combine `l' and `r', retaining the kNumTrackedSamples with the highest
  79    * counts.
  80    */
  81   static void reduce(ArrayAccessProfile& l, const ArrayAccessProfile& r);
  82
  83   std::string toString() const;
  84   folly::dynamic toDynamic() const;
  85
  86 private:
  87   /*
  88    * Initialize the samples.
  89    *
  90    * The default `pos' values need to be -1, but since this is stored in RDS,
  91    * we need to manually initialize.
  92    */
  93   void init();
  94
  95   /*
  96    * Update the profile for `pos' by `count'.
  97    *
  98    * Returns whether or not we were able to account for the update precisely.
  99    */
 100   bool update(int32_t pos, uint32_t count);
 101
 102 private:
 103   struct Line {
 104     int32_t pos{-1};
 105     uint32_t count{0};
 106   };
 107
 108   static const size_t kNumTrackedSamples = 4;
 109
 110 private:
 111   Line m_hits[kNumTrackedSamples];
 112   uint32_t m_untracked{0};
 113   uint32_t m_small{0};
 114   uint32_t m_empty{0};
 115   uint32_t m_missing{0};
 116   uint32_t m_nocow{0};
 117   bool m_init{false};
 118 };
 119
 120 ///////////////////////////////////////////////////////////////////////////////
 121
 122 }}