hphp/runtime/vm/jit/array-offset-profile.cpp

   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 #include "hphp/runtime/vm/jit/array-offset-profile.h"
  18
  19 #include "hphp/runtime/base/array-data.h"
  20 #include "hphp/runtime/base/mixed-array.h"
  21 #include "hphp/runtime/base/mixed-array-defs.h"
  22 #include "hphp/runtime/base/set-array.h"
  23 #include "hphp/runtime/base/runtime-option.h"
  24 #include "hphp/runtime/base/string-data.h"
  25 #include "hphp/runtime/vm/member-operations.h"
  26
  27 #include "hphp/util/safe-cast.h"
  28
  29 #include <folly/Optional.h>
  30
  31 #include <algorithm>
  32 #include <cstring>
  33
  34 namespace HPHP { namespace jit {
  35
  36 ///////////////////////////////////////////////////////////////////////////////
  37
  38 std::string ArrayOffsetProfile::toString() const {
  39   if (!m_init) return std::string("uninitialized");
  40   std::ostringstream out;
  41   for (auto const& line : m_hits) {
  42     out << folly::format("{}:{},", line.pos, line.count);
  43   }
  44   out << folly::format("untracked:{}", m_untracked);
  45   return out.str();
  46 }
  47
  48 folly::Optional<uint32_t>
  49 ArrayOffsetProfile::choose() const {
  50   Line hottest;
  51   uint32_t total = 0;
  52
  53   if (!m_init) return folly::none;
  54
  55   for (auto i = 0; i < kNumTrackedSamples; ++i) {
  56     auto const& line = m_hits[i];
  57     if (!validPos(line.pos)) break;
  58
  59     if (line.count > hottest.count) hottest = line;
  60     total += line.count;
  61   }
  62   total += m_untracked;
  63
  64   auto const bound = total * RuntimeOption::EvalHHIRMixedArrayProfileThreshold;
  65   return hottest.count >= bound
  66     ? folly::make_optional(safe_cast<uint32_t>(hottest.pos))
  67     : folly::none;
  68 }
  69
  70 bool ArrayOffsetProfile::update(int32_t pos, uint32_t count) {
  71   if (!m_init) init();
  72
  73   if (!validPos(pos)) {
  74     m_untracked += count;
  75     return false;
  76   }
  77
  78   for (auto i = 0; i < kNumTrackedSamples; ++i) {
  79     auto& line = m_hits[i];
  80
  81     if (line.pos == pos) {
  82       line.count += count;
  83       return true;
  84     }
  85     if (line.pos == -1) {
  86       line.pos = pos;
  87       line.count = count;
  88       return true;
  89     }
  90   }
  91
  92   m_untracked += count;
  93   return false;
  94 }
  95
  96 void ArrayOffsetProfile::update(const ArrayData* ad, int64_t i) {
  97   auto h = hash_int64(i);
  98   auto const pos =
  99     ad->hasMixedLayout() ? MixedArray::asMixed(ad)->find(i, h) :
 100     ad->isKeyset() ? SetArray::asSet(ad)->find(i, h) :
 101     -1;
 102   update(pos, 1);
 103 }
 104
 105 void ArrayOffsetProfile::update(const ArrayData* ad,
 106                                 const StringData* sd,
 107                                 bool checkForInt) {
 108   auto const pos = [&]() -> int32_t {
 109     if (ad->hasMixedLayout()) {
 110       auto const a = MixedArray::asMixed(ad);
 111
 112       int64_t i;
 113       if (checkForInt && ad->convertKey(sd, i, false)) {
 114         return !checkHACIntishCast() ?
 115           a->find(i, hash_int64(i)) : -1;
 116       }
 117       return a->find(sd, sd->hash());
 118     } else if (ad->isKeyset()) {
 119       return SetArray::asSet(ad)->find(sd, sd->hash());
 120     } else {
 121       return -1;
 122     }
 123   }();
 124   update(pos, 1);
 125 }
 126
 127 void ArrayOffsetProfile::reduce(ArrayOffsetProfile& l,
 128                                 const ArrayOffsetProfile& r) {
 129   if (!r.m_init) return;
 130
 131   Line scratch[2 * kNumTrackedSamples];
 132   auto n = uint32_t{0};
 133
 134   for (auto i = 0; i < kNumTrackedSamples; ++i) {
 135     auto const& rline = r.m_hits[i];
 136     if (!validPos(rline.pos)) break;
 137
 138     // Update `l'.  If `l' can't record the update, save it to scratch.
 139     if (!l.update(rline.pos, rline.count)) {
 140       scratch[n++] = rline;
 141     }
 142   }
 143   l.m_untracked += r.m_untracked;
 144
 145   if (n == 0) return;
 146   assertx(n <= kNumTrackedSamples);
 147
 148   // Sort the combined samples, then copy the top hits back into `l'.
 149   std::memcpy(&scratch[n], &l.m_hits[0],
 150               kNumTrackedSamples * sizeof(Line));
 151   std::sort(&scratch[0], &scratch[n + kNumTrackedSamples],
 152             [] (Line a, Line b) { return a.count > b.count; });
 153   std::memcpy(l.m_hits, scratch, kNumTrackedSamples);
 154
 155   // Add the hits in the discarded tail to m_untracked.
 156   for (auto i = kNumTrackedSamples; i < n + kNumTrackedSamples; ++i) {
 157     auto const& line = scratch[i];
 158     if (!validPos(line.pos)) break;
 159
 160     l.m_untracked += line.count;
 161   }
 162 }
 163
 164 void ArrayOffsetProfile::init() {
 165   assertx(!m_init);
 166   for (auto i = 0; i < kNumTrackedSamples; ++i) {
 167     m_hits[i] = Line{};
 168   }
 169   m_init = true;
 170 }
 171
 172 ///////////////////////////////////////////////////////////////////////////////
 173
 174 }}