hphp/runtime/vm/jit/array-layout.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-layout.h"
  18
  19 #include "hphp/runtime/base/bespoke/layout.h"
  20 #include "hphp/runtime/base/bespoke/logging-array.h"
  21 #include "hphp/runtime/base/bespoke/logging-profile.h"
  22 #include "hphp/runtime/base/bespoke/monotype-dict.h"
  23 #include "hphp/runtime/base/bespoke/monotype-vec.h"
  24 #include "hphp/runtime/base/bespoke/struct-dict.h"
  25 #include "hphp/runtime/base/bespoke-array.h"
  26 #include "hphp/runtime/vm/jit/irgen-internal.h"
  27 #include "hphp/runtime/vm/jit/prof-data-serialize.h"
  28 #include "hphp/runtime/vm/jit/ssa-tmp.h"
  29
  30 namespace HPHP { namespace jit {
  31
  32 //////////////////////////////////////////////////////////////////////////////
  33
  34 namespace {
  35
  36 using Sort = ArrayLayout::Sort;
  37
  38 auto constexpr kBasicSortMask    = 0b11;
  39 auto constexpr kBasicSortShift   = 0b11;
  40 auto constexpr kBasicSortUnshift = 0b01;
  41
  42 // A "basic sort" is just one of the four named Sort enum values. If `sort`
  43 // is non-basic, then Sort::Bottom < sort < Sort::Bespoke.
  44 constexpr bool isBasicSort(Sort sort) {
  45   return sort <= Sort::Bespoke;
  46 }
  47
  48 // Converts non-basic sorts (which are subtypes of Bespoke) to Bespoke.
  49 constexpr Sort toBasicSort(Sort sort) {
  50   return std::min(sort, Sort::Bespoke);
  51 }
  52
  53 // If we mask a basic sort, we'll get a value such that | and & bit ops on
  54 // that value correspond to | and & type operations on the original sort.
  55 constexpr int maskBasicSort(Sort sort) {
  56   assertx(isBasicSort(sort));
  57   return kBasicSortMask & (int(sort) + kBasicSortShift);
  58 }
  59
  60 static_assert(maskBasicSort(Sort::Top)     == 0b11);
  61 static_assert(maskBasicSort(Sort::Vanilla) == 0b01);
  62 static_assert(maskBasicSort(Sort::Bespoke) == 0b10);
  63 static_assert(maskBasicSort(Sort::Bottom)  == 0b00);
  64
  65 // This operation is the inverse of the maskBasicSort operation above.
  66 constexpr Sort unmaskBasicSort(int masked) {
  67   auto const result = Sort(kBasicSortMask & (masked + kBasicSortUnshift));
  68   assertx(isBasicSort(result));
  69   return result;
  70 }
  71
  72 static_assert(unmaskBasicSort(maskBasicSort(Sort::Top))     == Sort::Top);
  73 static_assert(unmaskBasicSort(maskBasicSort(Sort::Vanilla)) == Sort::Vanilla);
  74 static_assert(unmaskBasicSort(maskBasicSort(Sort::Bespoke)) == Sort::Bespoke);
  75 static_assert(unmaskBasicSort(maskBasicSort(Sort::Bottom))  == Sort::Bottom);
  76
  77 // Returns the basic sort that is the intersection of the given basic sorts.
  78 constexpr Sort intersectBasicSort(Sort a, Sort b) {
  79   return unmaskBasicSort(maskBasicSort(a) & maskBasicSort(b));
  80 }
  81
  82 // Returns the basic sort that is the union of the given basic sorts.
  83 constexpr Sort unionBasicSort(Sort a, Sort b) {
  84   return unmaskBasicSort(maskBasicSort(a) | maskBasicSort(b));
  85 }
  86
  87 // Returns the sort (either Bespoke, or non-basic) for this bespoke layout.
  88 Sort sortFromLayoutIndex(bespoke::LayoutIndex index) {
  89   return Sort(index.raw + int(Sort::Bespoke));
  90 }
  91
  92 const bespoke::Layout& assertBespoke(ArrayLayout layout) {
  93   auto const result = layout.bespokeLayout();
  94   assertx(result != nullptr);
  95   return *result;
  96 }
  97
  98 }
  99
 100 //////////////////////////////////////////////////////////////////////////////
 101
 102 ArrayLayout::ArrayLayout(bespoke::LayoutIndex index)
 103   : sort(sortFromLayoutIndex(index))
 104 {
 105   assertx(bespoke::Layout::FromIndex(*layoutIndex()));
 106 }
 107
 108 ArrayLayout::ArrayLayout(const bespoke::Layout* layout)
 109   : sort(sortFromLayoutIndex(layout->index()))
 110 {
 111   assertx(bespoke::Layout::FromIndex(*layoutIndex()));
 112 }
 113
 114 bool ArrayLayout::operator<=(const ArrayLayout& o) const {
 115   if (*this == o) return true;
 116   if (o == Top()) return true;
 117   if (*this == Bottom()) return true;
 118
 119   // The max chain length on basic sorts alone is three:
 120   //
 121   //   Bottom < {Vanilla,Bespoke} < Top
 122   //
 123   // We took care of the Bottom, Top, and equality cases above. Further, if o
 124   // is non-basic, it's a strict subtype of Bespoke. So we can return here.
 125   if (isBasicSort(sort)) return false;
 126
 127   if (isBasicSort(o.sort)) return o == Bespoke();
 128   return assertBespoke(*this) <= assertBespoke(o);
 129 }
 130
 131 ArrayLayout ArrayLayout::operator|(const ArrayLayout& o) const {
 132   if (*this == o) return o;
 133   if (o == Bottom()) return *this;
 134   if (*this == Bottom()) return o;
 135
 136   // If either side is captured as a basic sort, then the result is, too.
 137   if (isBasicSort(sort) || isBasicSort(o.sort)) {
 138     return ArrayLayout(unionBasicSort(toBasicSort(sort), toBasicSort(o.sort)));
 139   }
 140
 141   return ArrayLayout(assertBespoke(*this) | assertBespoke(o));
 142 }
 143
 144 ArrayLayout ArrayLayout::operator&(const ArrayLayout& o) const {
 145   if (*this == o) return o;
 146   if (o == Top()) return *this;
 147   if (*this == Top()) return o;
 148
 149   // We only intersect bespoke layouts if toBasicSort is Bespoke for both.
 150   auto const meet = intersectBasicSort(toBasicSort(sort), toBasicSort(o.sort));
 151   if (meet != Sort::Bespoke) return ArrayLayout(meet);
 152
 153   // If either type is Bespoke (i.e. "bespoke top"), return the other type.
 154   if (o == Bespoke()) return *this;
 155   if (*this == Bespoke()) return o;
 156   auto const result = assertBespoke(*this) & assertBespoke(o);
 157   return result ? ArrayLayout(result) : Bottom();
 158 }
 159
 160 bool ArrayLayout::logging() const {
 161   auto const index = layoutIndex();
 162   return index && *index == bespoke::LoggingArray::GetLayoutIndex();
 163 }
 164
 165 bool ArrayLayout::monotype() const {
 166   auto const index = layoutIndex();
 167   if (!index) return false;
 168   return bespoke::isMonotypeVecLayout(*index) ||
 169          bespoke::isMonotypeDictLayout(*index);
 170 }
 171
 172 bool ArrayLayout::is_struct() const {
 173   auto const index = layoutIndex();
 174   return index && bespoke::StructLayout::IsStructLayout(*index);
 175 }
 176
 177 bool ArrayLayout::is_concrete() const {
 178   auto const layout = bespokeLayout();
 179   return layout && layout->isConcrete();
 180 }
 181
 182 const bespoke::Layout* ArrayLayout::bespokeLayout() const {
 183   auto const index = layoutIndex();
 184   if (!index) return nullptr;
 185   return bespoke::Layout::FromIndex(*index);
 186 }
 187
 188 Optional<bespoke::LayoutIndex> ArrayLayout::layoutIndex() const {
 189   auto const index = int(sort) - int(Sort::Bespoke);
 190   if (index < 0) return {};
 191   return bespoke::LayoutIndex { safe_cast<uint16_t>(index) };
 192 }
 193
 194 LayoutTest ArrayLayout::bespokeLayoutTest() const {
 195   assertx(!isBasicSort(sort));
 196   auto const& layout = assertBespoke(*this);
 197   return layout.getLayoutTest();
 198 }
 199
 200 const bespoke::Layout* ArrayLayout::irgenLayout() const {
 201   auto const index = std::max(int(sort) - int(Sort::Bespoke), 0);
 202   return bespoke::Layout::FromIndex({safe_cast<uint16_t>(index)});
 203 }
 204
 205 std::string ArrayLayout::describe() const {
 206   if (isBasicSort(sort)) {
 207     switch (sort) {
 208       case Sort::Top:     return "Top";
 209       case Sort::Vanilla: return "Vanilla";
 210       case Sort::Bespoke: return "Bespoke";
 211       case Sort::Bottom:  return "Bottom";
 212     }
 213   }
 214   return assertBespoke(*this).describe();
 215 }
 216
 217 ArrayData* ArrayLayout::apply(ArrayData* ad) const {
 218   assertx(ad->isStatic());
 219   assertx(ad->isVanilla());
 220
 221   auto const result = [&]() -> ArrayData* {
 222     if (vanilla() || logging()) return ad;
 223     return bespokeLayout()->coerce(ad);
 224   }();
 225
 226   SCOPE_ASSERT_DETAIL("ArrayLayout::apply") { return describe(); };
 227   always_assert(result != nullptr);
 228   return result;
 229 }
 230
 231 //////////////////////////////////////////////////////////////////////////////
 232
 233 ArrayLayout ArrayLayout::appendType(Type val) const {
 234   if (vanilla()) return ArrayLayout::Vanilla();
 235   if (isBasicSort(sort)) return ArrayLayout::Top();
 236   return bespokeLayout()->appendType(val);
 237 }
 238
 239 ArrayLayout ArrayLayout::removeType(Type key) const {
 240   if (vanilla()) return ArrayLayout::Vanilla();
 241   if (isBasicSort(sort)) return ArrayLayout::Top();
 242   return bespokeLayout()->removeType(key);
 243 }
 244
 245 ArrayLayout ArrayLayout::setType(Type key, Type val) const {
 246   if (vanilla()) return ArrayLayout::Vanilla();
 247   if (isBasicSort(sort)) return ArrayLayout::Top();
 248   return bespokeLayout()->setType(key, val);
 249 }
 250
 251 std::pair<Type, bool> ArrayLayout::elemType(Type key) const {
 252   if (isBasicSort(sort)) return {TInitCell, false};
 253   return bespokeLayout()->elemType(key);
 254 }
 255
 256 std::pair<Type, bool> ArrayLayout::firstLastType(
 257     bool isFirst, bool isKey) const {
 258   if (isBasicSort(sort)) return {isKey ? (TInt | TStr) : TInitCell, false};
 259   return bespokeLayout()->firstLastType(isFirst, isKey);
 260 }
 261
 262 Type ArrayLayout::iterPosType(Type pos, bool isKey) const {
 263   if (isBasicSort(sort)) return isKey ? (TInt | TStr) : TInitCell;
 264   return bespokeLayout()->iterPosType(pos, isKey);
 265 }
 266
 267 //////////////////////////////////////////////////////////////////////////////
 268
 269 namespace {
 270
 271 using bespoke::LoggingProfileKey;
 272 using bespoke::SinkProfileKey;
 273 using bespoke::StructLayout;
 274 using FieldVector = bespoke::StructLayout::FieldVector;
 275
 276 void write_field_vector(ProfDataSerializer& ser, const StructLayout* layout) {
 277   auto const num = layout->numFields();
 278   write_raw(ser, num);
 279   for (auto slot = 0; slot < num; ++slot) {
 280     auto const& f = layout->field(slot);
 281     write_string(ser, f.key);
 282     write_raw(ser, f.required);
 283     write_raw(ser, f.type_mask);
 284   }
 285 }
 286
 287 FieldVector read_field_vector(ProfDataDeserializer& des) {
 288   auto data = FieldVector{};
 289   auto const num = read_raw<size_t>(des);
 290   for (auto i = 0; i < num; i++) {
 291     auto const key = read_string(des);
 292     auto const required = read_raw<bool>(des);
 293     auto const type_mask = read_raw<uint8_t>(des);
 294     data.push_back({key, required, type_mask});
 295   }
 296   return data;
 297 }
 298
 299 void write_source_key(ProfDataSerializer& ser, const LoggingProfileKey& key) {
 300   write_raw(ser, key.locationType);
 301   switch (key.locationType) {
 302     case bespoke::LocationType::SrcKey:
 303       write_srckey(ser, key.sk);
 304       break;
 305     case bespoke::LocationType::APCKey:
 306       write_raw(ser, key.ak);
 307       break;
 308     case bespoke::LocationType::InstanceProperty:
 309     case bespoke::LocationType::StaticProperty:
 310       write_class(ser, key.cls);
 311       write_raw(ser, key.slot);
 312       break;
 313     case bespoke::LocationType::Runtime:
 314       write_string(ser, key.runtimeStruct->getStableIdentifier());
 315       break;
 316     default: always_assert(false);
 317   }
 318 }
 319
 320 LoggingProfileKey read_source_key(ProfDataDeserializer& des) {
 321   LoggingProfileKey key(SrcKey{});
 322   read_raw(des, key.locationType);
 323   switch (key.locationType) {
 324     case bespoke::LocationType::SrcKey:
 325       key.sk = read_srckey(des);
 326       break;
 327     case bespoke::LocationType::APCKey:
 328       read_raw(des, key.ak);
 329       break;
 330     case bespoke::LocationType::InstanceProperty:
 331     case bespoke::LocationType::StaticProperty:
 332       key.cls = read_class(des);
 333       read_raw(des, key.slot);
 334       break;
 335     case bespoke::LocationType::Runtime: {
 336       auto const stableIdentifier = read_string(des);
 337       key.runtimeStruct = RuntimeStruct::findById(stableIdentifier);
 338       break;
 339     }
 340     default: always_assert(false);
 341   }
 342   return key;
 343 }
 344
 345 void write_sink_key(ProfDataSerializer& ser, const SinkProfileKey& key) {
 346   write_raw(ser, key.first);
 347   write_srckey(ser, key.second);
 348 }
 349
 350 SinkProfileKey read_sink_key(ProfDataDeserializer& des) {
 351   auto const trans = read_raw<TransID>(des);
 352   return SinkProfileKey(trans, read_srckey(des));
 353 }
 354
 355 void write_sink_layout(ProfDataSerializer& ser, bespoke::SinkLayout sl) {
 356   write_raw(ser, sl.layout);
 357   write_raw(ser, sl.sideExit);
 358 }
 359
 360 bespoke::SinkLayout read_sink_layout(ProfDataDeserializer& des) {
 361   auto result = bespoke::SinkLayout{};
 362   result.layout = read_layout(des);
 363   read_raw(des, result.sideExit);
 364   return result;
 365 }
 366
 367 }
 368
 369 struct RuntimeStructSerde {
 370   static void write_runtime_struct(
 371       ProfDataSerializer& ser, const RuntimeStruct* runtimeStruct) {
 372     write_string(ser, runtimeStruct->m_stableIdentifier);
 373
 374     write_raw(ser, runtimeStruct->m_fields.size());
 375     for (auto const key : runtimeStruct->m_fields) {
 376       if (key) {
 377         write_raw(ser, true);
 378         write_string(ser, key);
 379       } else {
 380         write_raw(ser, false);
 381       }
 382     }
 383
 384     auto const layout = runtimeStruct->m_assignedLayout.load();
 385     if (layout) {
 386       write_raw(ser, true);
 387       write_raw(ser, layout->index());
 388     } else {
 389       write_raw(ser, false);
 390     }
 391   }
 392
 393   static void deserialize_runtime_struct(ProfDataDeserializer& des) {
 394     auto const stableIdentifier = read_string(des);
 395     auto const fieldSize = read_raw<size_t>(des);
 396
 397     auto fields = RuntimeStruct::FieldKeys(fieldSize, nullptr);
 398     for (int i = 0; i < fieldSize; i ++) {
 399       auto const present = read_raw<bool>(des);
 400       if (present) fields[i] = read_string(des);
 401     }
 402
 403     auto const runtimeStruct =
 404       RuntimeStruct::deserialize(stableIdentifier, std::move(fields));
 405
 406     auto const hasLayout = read_raw<bool>(des);
 407     if (hasLayout) {
 408       auto const layoutIdx = read_raw<bespoke::LayoutIndex>(des);
 409       auto const layout = bespoke::Layout::FromIndex(layoutIdx);
 410       runtimeStruct->applyLayout(bespoke::StructLayout::As(layout));
 411     }
 412   }
 413 };
 414
 415 void serializeBespokeLayouts(ProfDataSerializer& ser) {
 416   // For now, we only need to serialize and deserialize StructLayouts,
 417   // because they are the only dynamically-constructed layouts.
 418   std::vector<const StructLayout*> layouts;
 419   bespoke::eachLayout([&](auto const& layout) {
 420     if (!layout.isConcrete() || !ArrayLayout(&layout).is_struct()) return;
 421     layouts.push_back(StructLayout::As(&layout));
 422   });
 423   write_raw(ser, layouts.size());
 424   for (auto const layout : layouts) {
 425     write_raw(ser, layout->index());
 426     write_field_vector(ser, layout);
 427   }
 428
 429   // Serialize the runtime sources.
 430   std::vector<const RuntimeStruct*> runtimeStructs;
 431   RuntimeStruct::eachRuntimeStruct([&](RuntimeStruct* runtimeStruct) {
 432     runtimeStructs.push_back(runtimeStruct);
 433   });
 434   write_raw(ser, runtimeStructs.size());
 435   for (auto const runtimeStruct : runtimeStructs) {
 436     RuntimeStructSerde::write_runtime_struct(ser, runtimeStruct);
 437   }
 438
 439   // Serialize the decisions we made at all sources and sinks.
 440   write_raw(ser, bespoke::countSources());
 441   bespoke::eachSource([&](auto const& profile) {
 442     write_source_key(ser, profile.key);
 443     write_raw(ser, profile.getLayout());
 444   });
 445   write_raw(ser, bespoke::countSinks());
 446   bespoke::eachSink([&](auto const& profile) {
 447     write_sink_key(ser, profile.key);
 448     write_sink_layout(ser, profile.getLayout());
 449   });
 450 }
 451
 452 void deserializeBespokeLayouts(ProfDataDeserializer& des) {
 453   always_assert(bespoke::countSources() == 0);
 454   always_assert(bespoke::countSinks() == 0);
 455   bespoke::setLoggingEnabled(false);
 456   always_assert(bespoke::countSources() == 0);
 457   always_assert(bespoke::countSinks() == 0);
 458
 459   auto const layouts = read_raw<size_t>(des);
 460   for (auto i = 0; i < layouts; i++) {
 461     auto const index = read_raw<bespoke::LayoutIndex>(des);
 462     auto const fields = read_field_vector(des);
 463     auto const layout = StructLayout::Deserialize(index, fields);
 464     layout->createColoringHashMap();
 465   }
 466   auto const runtimeStructs = read_raw<size_t>(des);
 467   for (auto i = 0; i < runtimeStructs; i++) {
 468     RuntimeStructSerde::deserialize_runtime_struct(des);
 469   }
 470   auto const sources = read_raw<size_t>(des);
 471   for (auto i = 0; i < sources; i++) {
 472     assertx(bespoke::countSources() == i);
 473     auto const key = read_source_key(des);
 474     bespoke::deserializeSource(key, read_layout(des));
 475     assertx(bespoke::countSources() == i + 1);
 476   }
 477   auto const sinks = read_raw<size_t>(des);
 478   for (auto i = 0; i < sinks; i++) {
 479     assertx(bespoke::countSinks() == i);
 480     auto const key = read_sink_key(des);
 481     bespoke::deserializeSink(key, read_sink_layout(des));
 482     assertx(bespoke::countSinks() == i + 1);
 483   }
 484   bespoke::Layout::FinalizeHierarchy();
 485 }
 486
 487 //////////////////////////////////////////////////////////////////////////////
 488
 489 }}