hphp/hhbbc/interp-state.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 #include "hphp/hhbbc/interp-state.h"
  17
  18 #include <string>
  19
  20 #include <folly/Format.h>
  21 #include <folly/Conv.h>
  22 #include <folly/gen/Base.h>
  23 #include <folly/gen/String.h>
  24
  25 #include "hphp/util/match.h"
  26 #include "hphp/hhbbc/analyze.h"
  27 #include "hphp/hhbbc/interp-internal.h"
  28 #include "hphp/hhbbc/context.h"
  29
  30 namespace HPHP { namespace HHBBC {
  31
  32 //////////////////////////////////////////////////////////////////////
  33
  34 namespace {
  35
  36 const StaticString s_Throwable("Throwable");
  37
  38 template<class JoinOp>
  39 bool merge_into(Iter& dst, const Iter& src, JoinOp join) {
  40   auto const mergeCounts = [](IterTypes::Count c1, IterTypes::Count c2) {
  41     if (c1 == c2) return c1;
  42     if (c1 == IterTypes::Count::Any) return c1;
  43     if (c2 == IterTypes::Count::Any) return c2;
  44     auto const nonEmpty = [](IterTypes::Count c) {
  45       if (c == IterTypes::Count::Empty || c == IterTypes::Count::ZeroOrOne) {
  46         return IterTypes::Count::Any;
  47       }
  48       return IterTypes::Count::NonEmpty;
  49     };
  50     if (c1 == IterTypes::Count::NonEmpty) return nonEmpty(c2);
  51     if (c2 == IterTypes::Count::NonEmpty) return nonEmpty(c1);
  52     return IterTypes::Count::ZeroOrOne;
  53   };
  54
  55   return match<bool>(
  56     dst,
  57     [&] (DeadIter) {
  58       match<void>(
  59         src,
  60         [] (DeadIter) {},
  61         [] (const LiveIter&) {
  62           always_assert(false && "merging dead iter with live iter");
  63         }
  64       );
  65       return false;
  66     },
  67     [&] (LiveIter& diter) {
  68       return match<bool>(
  69         src,
  70         [&] (DeadIter) {
  71           always_assert(false && "merging live iter with dead iter");
  72           return false;
  73         },
  74         [&] (const LiveIter& siter) {
  75           auto key = join(diter.types.key, siter.types.key);
  76           auto value = join(diter.types.value, siter.types.value);
  77           auto const count = mergeCounts(diter.types.count, siter.types.count);
  78           auto const throws1 =
  79             diter.types.mayThrowOnInit || siter.types.mayThrowOnInit;
  80           auto const throws2 =
  81             diter.types.mayThrowOnNext || siter.types.mayThrowOnNext;
  82           auto const baseUpdated = diter.baseUpdated || siter.baseUpdated;
  83           auto const baseLocal = (diter.baseLocal != siter.baseLocal)
  84             ? NoLocalId
  85             : diter.baseLocal;
  86           auto const keyLocal = (diter.keyLocal != siter.keyLocal)
  87             ? NoLocalId
  88             : diter.keyLocal;
  89           auto const initBlock = (diter.initBlock != siter.initBlock)
  90             ? NoBlockId
  91             : diter.initBlock;
  92           auto const baseCannotBeObject =
  93             diter.baseCannotBeObject && siter.baseCannotBeObject;
  94           auto const changed =
  95             !equivalently_refined(key, diter.types.key) ||
  96             !equivalently_refined(value, diter.types.value) ||
  97             count != diter.types.count ||
  98             throws1 != diter.types.mayThrowOnInit ||
  99             throws2 != diter.types.mayThrowOnNext ||
 100             keyLocal != diter.keyLocal ||
 101             baseLocal != diter.baseLocal ||
 102             baseUpdated != diter.baseUpdated ||
 103             initBlock != diter.initBlock ||
 104             baseCannotBeObject != diter.baseCannotBeObject;
 105           diter.types =
 106             IterTypes {
 107               std::move(key),
 108               std::move(value),
 109               count,
 110               throws1,
 111               throws2
 112             };
 113           diter.baseUpdated = baseUpdated;
 114           diter.baseLocal = baseLocal;
 115           diter.keyLocal = keyLocal;
 116           diter.initBlock = initBlock;
 117           diter.baseCannotBeObject = baseCannotBeObject;
 118           return changed;
 119         }
 120       );
 121     }
 122   );
 123 }
 124
 125 }
 126
 127 //////////////////////////////////////////////////////////////////////
 128
 129 std::string show(const php::Func& f, const Iter& iter) {
 130   return match<std::string>(
 131     iter,
 132     [&] (DeadIter) { return "dead"; },
 133     [&] (const LiveIter& ti) {
 134       auto str = folly::sformat(
 135         "{}, {}",
 136         show(ti.types.key),
 137         show(ti.types.value)
 138       );
 139       if (ti.initBlock != NoBlockId) {
 140         folly::format(&str, " (init=blk:{})", ti.initBlock);
 141       }
 142       if (ti.baseLocal != NoLocalId) {
 143         folly::format(&str, " (base={})", local_string(f, ti.baseLocal));
 144       }
 145       if (ti.keyLocal != NoLocalId) {
 146         folly::format(&str, " (key={})", local_string(f, ti.keyLocal));
 147       }
 148       if (ti.baseUpdated) folly::format(&str, " (updated)");
 149       return str;
 150     }
 151   );
 152 }
 153
 154 //////////////////////////////////////////////////////////////////////
 155
 156 CollectedInfo::CollectedInfo(const Index& index,
 157                              Context ctx,
 158                              ClassAnalysis* cls,
 159                              CollectionOpts opts,
 160                              const FuncAnalysis* fa)
 161     : props{index, ctx, cls}
 162     , opts{fa ? opts | CollectionOpts::Optimizing : opts}
 163 {
 164   if (fa) {
 165     unfoldableFuncs = fa->unfoldableFuncs;
 166   }
 167 }
 168
 169 //////////////////////////////////////////////////////////////////////
 170
 171 State with_throwable_only(const Index& index, const State& src) {
 172   auto throwable = subObj(index.builtin_class(s_Throwable.get()));
 173   auto ret          = State{};
 174   ret.initialized   = src.initialized;
 175   ret.thisType      = src.thisType;
 176   ret.thisLoc       = src.thisLoc;
 177
 178   if (UNLIKELY(src.locals.size() > (1LL << 50))) {
 179     // gcc 4.9 has a bug where it will spit out a warning:
 180     //
 181     // > In function 'HPHP::HHBBC::State HPHP::HHBBC::without_stacks':
 182     // > cc1plus: error: iteration 461168601842738791u invokes undefined
 183     // >   behavior [-Werror=aggressive-loop-optimizations]
 184     // > include/c++/4.9.x/bits/stl_algobase.h:334:4: note: containing loop
 185     //
 186     // The warning is a bug because it computes the number of
 187     // iterations by subtracting two pointers; and the result *cannot*
 188     // exceed 461168601842738790.  (its also a bug because it
 189     // shouldn't generate such warnings in its own headers).
 190     //
 191     // in any case, this disables it, and generates no code in O3 builds
 192     not_reached();
 193   }
 194
 195   ret.locals        = src.locals;
 196   ret.iters         = src.iters;
 197   ret.stack.push_elem(std::move(throwable), NoLocalId);
 198   return ret;
 199 }
 200
 201 //////////////////////////////////////////////////////////////////////
 202
 203 PropertiesInfo::PropertiesInfo(const Index& index,
 204                                Context ctx,
 205                                ClassAnalysis* cls)
 206   : m_cls(cls)
 207 {
 208   if (m_cls == nullptr && ctx.cls != nullptr) {
 209     m_privateProperties = index.lookup_private_props(ctx.cls);
 210     m_privateStatics    = index.lookup_private_statics(ctx.cls);
 211   }
 212 }
 213
 214 PropState& PropertiesInfo::privateProperties() {
 215   if (m_cls != nullptr) {
 216     return m_cls->privateProperties;
 217   }
 218   return m_privateProperties;
 219 }
 220
 221 PropState& PropertiesInfo::privateStatics() {
 222   if (m_cls != nullptr) {
 223     return m_cls->privateStatics;
 224   }
 225   return m_privateStatics;
 226 }
 227
 228 const PropState& PropertiesInfo::privateProperties() const {
 229   return const_cast<PropertiesInfo*>(this)->privateProperties();
 230 }
 231
 232 const PropState& PropertiesInfo::privateStatics() const {
 233   return const_cast<PropertiesInfo*>(this)->privateStatics();
 234 }
 235
 236 void PropertiesInfo::setBadPropInitialValues() {
 237   if (m_cls) m_cls->badPropInitialValues = true;
 238 }
 239
 240 //////////////////////////////////////////////////////////////////////
 241
 242 void merge_closure_use_vars_into(ClosureUseVarMap& dst,
 243                                  php::Class* clo,
 244                                  CompactVector<Type> types) {
 245   auto& current = dst[clo];
 246   if (current.empty()) {
 247     current = std::move(types);
 248     return;
 249   }
 250
 251   assert(types.size() == current.size());
 252   for (auto i = uint32_t{0}; i < current.size(); ++i) {
 253     current[i] |= std::move(types[i]);
 254   }
 255 }
 256
 257 void widen_props(PropState& props) {
 258   for (auto& prop : props) {
 259     prop.second.ty = widen_type(std::move(prop.second.ty));
 260   }
 261 }
 262
 263 template<class JoinOp>
 264 bool merge_impl(State& dst, const State& src, JoinOp join) {
 265   if (!dst.initialized) {
 266     dst.copy_and_compact(src);
 267     return true;
 268   }
 269
 270   assert(src.initialized);
 271   assert(dst.locals.size() == src.locals.size());
 272   assert(dst.iters.size() == src.iters.size());
 273   assert(dst.stack.size() == src.stack.size());
 274
 275   if (src.unreachable) {
 276     // If we're coming from unreachable code and the dst is already
 277     // initialized, it doesn't change the dst (whether it is reachable or not).
 278     return false;
 279   }
 280   if (dst.unreachable) {
 281     // If we're going to code currently believed to be unreachable, take the
 282     // src state, and consider the dest state changed only if the source state
 283     // was reachable.
 284     dst.copy_and_compact(src);
 285     return !src.unreachable;
 286   }
 287
 288   auto changed = false;
 289
 290   auto const thisType = join(dst.thisType, src.thisType);
 291   if (thisType != dst.thisType) {
 292     changed = true;
 293     dst.thisType = thisType;
 294   }
 295
 296   if (dst.thisLoc != src.thisLoc) {
 297     if (dst.thisLoc != NoLocalId) {
 298       dst.thisLoc = NoLocalId;
 299       changed = true;
 300     }
 301   }
 302
 303   for (auto i = size_t{0}; i < dst.stack.size(); ++i) {
 304     auto newT = join(dst.stack[i].type, src.stack[i].type);
 305     if (!equivalently_refined(dst.stack[i].type, newT)) {
 306       changed = true;
 307       dst.stack[i].type = std::move(newT);
 308     }
 309     if (dst.stack[i].equivLoc != src.stack[i].equivLoc) {
 310       changed = true;
 311       dst.stack[i].equivLoc = NoLocalId;
 312     }
 313   }
 314
 315   for (auto i = size_t{0}; i < dst.locals.size(); ++i) {
 316     auto newT = join(dst.locals[i], src.locals[i]);
 317     if (!equivalently_refined(dst.locals[i], newT)) {
 318       changed = true;
 319       dst.locals[i] = std::move(newT);
 320     }
 321   }
 322
 323   for (auto i = size_t{0}; i < dst.iters.size(); ++i) {
 324     if (merge_into(dst.iters[i], src.iters[i], join)) {
 325       changed = true;
 326     }
 327   }
 328
 329   if (src.equivLocals.size() < dst.equivLocals.size()) {
 330     for (auto i = src.equivLocals.size(); i < dst.equivLocals.size(); ++i) {
 331       if (dst.equivLocals[i] != NoLocalId) {
 332         killLocEquiv(dst, i);
 333         changed = true;
 334       }
 335     }
 336     dst.equivLocals.resize(src.equivLocals.size());
 337   }
 338
 339   auto processed = uint64_t{0};
 340   for (auto i = LocalId{0}; i < dst.equivLocals.size(); ++i) {
 341     if (i < sizeof(uint64_t) * CHAR_BIT && (processed >> i) & 1) continue;
 342     auto dstLoc = dst.equivLocals[i];
 343     if (dstLoc == NoLocalId) continue;
 344     auto srcLoc = i < src.equivLocals.size() ? src.equivLocals[i] : NoLocalId;
 345     if (srcLoc != dstLoc) {
 346       if (srcLoc != NoLocalId &&
 347           dst.equivLocals.size() < sizeof(uint64_t) * CHAR_BIT) {
 348
 349         auto computeSet = [&] (const State& s, LocalId start) {
 350           auto result = uint64_t{0};
 351           auto l = start;
 352           do {
 353             result |= uint64_t{1} << l;
 354             l = s.equivLocals[l];
 355           } while (l != start);
 356           return result;
 357         };
 358
 359         auto dstSet = computeSet(dst, i);
 360         auto srcSet = computeSet(src, i);
 361
 362         auto newSet = dstSet & srcSet;
 363         if (!(newSet & (newSet - 1))) {
 364           newSet = 0;
 365         }
 366         auto killSet = dstSet - newSet;
 367         if (killSet) {
 368           auto l = i;
 369           do {
 370             processed |= uint64_t{1} << l;
 371             auto const next = dst.equivLocals[l];
 372             if ((killSet >> l) & 1) {
 373               killLocEquiv(dst, l);
 374             }
 375             l = next;
 376           } while (l != i && l != NoLocalId);
 377           assert(l == i || killSet == dstSet);
 378           changed = true;
 379         }
 380       } else {
 381         killLocEquiv(dst, i);
 382         changed = true;
 383       }
 384     }
 385   }
 386
 387   return changed;
 388 }
 389
 390 bool merge_into(State& dst, const State& src) {
 391   return merge_impl(dst, src, union_of);
 392 }
 393
 394 bool widen_into(State& dst, const State& src) {
 395   return merge_impl(dst, src, widening_union);
 396 }
 397
 398 void InterpStack::refill(size_t elemIx, size_t indexLow,
 399                          int numPop, int numPush) {
 400   auto constexpr NoIndex =
 401     std::numeric_limits<decltype(index)::value_type>::max();
 402
 403   if (numPush) {
 404     index.erase(index.begin() + indexLow, index.begin() + indexLow + numPush);
 405     elems.erase(elems.begin() + elemIx, elems.begin() + elemIx + numPush);
 406     for (auto i = indexLow; i < index.size(); i++) {
 407       if (index[i] >= elemIx) {
 408         auto DEBUG_ONLY ii = index[i] -= numPush;
 409         assertx(ii >= elemIx);
 410       }
 411     }
 412   }
 413
 414   if (numPush != numPop) {
 415     for (auto i = elemIx; i < elems.size(); i++) {
 416       auto& elem = elems[i];
 417       if (elem.index >= indexLow) {
 418         elem.index += numPop - numPush;
 419       }
 420     }
 421   }
 422
 423   if (!numPop) return;
 424
 425   auto const indexHigh = indexLow + numPop;
 426   index.insert(index.begin() + indexLow, numPop, NoIndex);
 427   for (auto i = elemIx; i--; ) {
 428     auto const& elm = elems[i];
 429     if (elm.index >= indexLow &&
 430         elm.index < indexHigh &&
 431         index[elm.index] == NoIndex) {
 432       index[elm.index] = i;
 433       if (!--numPop) return;
 434     }
 435   }
 436
 437   always_assert(false);
 438 }
 439
 440 void InterpStack::rewind(int numPop, int numPush) {
 441   refill(elems.size() - numPush, index.size() - numPush, numPop, numPush);
 442 }
 443
 444 void InterpStack::kill(int numPop, int numPush, uint32_t id) {
 445   for (auto i = elems.size(); i--; ) {
 446     auto const &elem = elems[i];
 447     if (elem.id == id) {
 448       for (auto j = 1; j < numPush; j++) {
 449         if (!i || elems[--i].id != id) always_assert(false);
 450       }
 451       return refill(i, elems[i].index, numPop, numPush);
 452     }
 453   }
 454
 455   always_assert(false);
 456 }
 457
 458 void InterpStack::insert_after(int numPop, int numPush, const Type* types,
 459                                uint32_t numInst, uint32_t id) {
 460   for (auto i = elems.size(); i--; ) {
 461     auto const &elem = elems[i];
 462     if (elem.id == id) {
 463       auto const indexLow = elem.index + 1 - numPop;
 464       index.erase(index.begin() + indexLow, index.begin() + indexLow + numPop);
 465       auto const elemIx = i + 1;
 466       elems.resize(elems.size() + numPush);
 467       for (auto j = elems.size() - numPush; j-- > elemIx; ) {
 468         auto& e = elems[j + numPush];
 469         e = std::move(elems[j]);
 470         e.index += numPush - numPop;
 471         if (e.id != StackElem::NoId) e.id += numInst;
 472       }
 473       for (auto j = indexLow; j < index.size(); j++) {
 474         index[j] += numPush;
 475       }
 476       index.insert(index.begin() + indexLow, numPush, uint32_t{});
 477       for (auto j = 0; j < numPush; j++) {
 478         auto& e = elems[elemIx + j];
 479         e.type = types[j];
 480         e.equivLoc = NoLocalId;
 481         e.index = indexLow + j;
 482         e.id = id + numInst;
 483         index[indexLow + j] = elemIx + j;
 484       }
 485       return;
 486     }
 487   }
 488
 489   always_assert(false);
 490 }
 491
 492 void InterpStack::peek(int numPop,
 493                        const StackElem** values,
 494                        int numPush) const {
 495   for (auto i = 0; i < numPop; i++) values[i] = nullptr;
 496
 497   auto const sz = index.size() - numPush;
 498   for (auto i = elems.size() - numPush; i--; ) {
 499     auto const& elm = elems[i];
 500     if (elm.index >= sz &&
 501         elm.index - sz < numPop &&
 502         values[elm.index - sz] == nullptr) {
 503       values[elm.index - sz] = &elm;
 504       if (!--numPop) return;
 505     }
 506   }
 507
 508   always_assert(false);
 509 }
 510
 511 //////////////////////////////////////////////////////////////////////
 512
 513 std::string show(const php::Func& f, const Base& b) {
 514   auto const locName = [&]{
 515     return b.locName ? folly::sformat("\"{}\"", b.locName) : "-";
 516   };
 517   auto const local = [&]{
 518     return b.locLocal != NoLocalId ? local_string(f, b.locLocal) : "-";
 519   };
 520
 521   switch (b.loc) {
 522     case BaseLoc::None:
 523       return "none";
 524     case BaseLoc::Elem:
 525       return folly::to<std::string>(
 526         "elem{", show(b.type), ",", show(b.locTy), "}"
 527       );
 528     case BaseLoc::Prop:
 529       return folly::to<std::string>(
 530         "prop{", show(b.type), ",", show(b.locTy), ",", locName(), "}"
 531       );
 532     case BaseLoc::StaticProp:
 533       return folly::to<std::string>(
 534         "sprop{", show(b.type), ",", show(b.locTy), ",", locName(), "}"
 535       );
 536     case BaseLoc::Local:
 537       return folly::to<std::string>(
 538         "local{", show(b.type), ",", locName(), ",", local(), "}"
 539       );
 540     case BaseLoc::This:
 541       return folly::to<std::string>("this{", show(b.type), "}");
 542     case BaseLoc::Stack:
 543       return folly::to<std::string>(
 544         "stack{", show(b.type), ",", b.locSlot, "}"
 545       );
 546     case BaseLoc::Global:
 547       return folly::to<std::string>("global{", show(b.type), "}");
 548   }
 549   not_reached();
 550 }
 551
 552 std::string show(const php::Func& f, const CollectedInfo::MInstrState& s) {
 553   if (s.arrayChain.empty()) return show(f, s.base);
 554   return folly::sformat(
 555     "{} ({})",
 556     show(f, s.base),
 557     [&]{
 558       using namespace folly::gen;
 559       return from(s.arrayChain)
 560         | map([&] (const CollectedInfo::MInstrState::ArrayChainEnt& e) {
 561             return folly::sformat("<{},{}>", show(e.key), show(e.base));
 562           })
 563         | unsplit<std::string>(" -> ");
 564     }()
 565   );
 566 }
 567
 568 std::string state_string(const php::Func& f, const State& st,
 569                          const CollectedInfo& collect) {
 570   std::string ret;
 571
 572   if (!st.initialized) {
 573     ret = "state: uninitialized\n";
 574     return ret;
 575   }
 576
 577   folly::format(&ret, "state{}:\n", st.unreachable ? " (unreachable)" : "");
 578   if (f.cls) {
 579     folly::format(&ret, "thisType({})\n", show(st.thisType));
 580   }
 581
 582   if (st.thisLoc != NoLocalId) {
 583     folly::format(&ret, "thisLoc({})\n", st.thisLoc);
 584   }
 585
 586   for (auto i = size_t{0}; i < st.locals.size(); ++i) {
 587     folly::format(&ret, "{: <8} :: {}\n",
 588                   local_string(f, i),
 589                   show(st.locals[i]));
 590   }
 591
 592   for (auto i = size_t{0}; i < st.iters.size(); ++i) {
 593     folly::format(&ret, "iter {: <2}  :: {}\n", i, show(f, st.iters[i]));
 594   }
 595
 596   for (auto i = size_t{0}; i < st.stack.size(); ++i) {
 597     folly::format(&ret, "stk[{:02}] :: {} [{}]\n",
 598                   i,
 599                   show(st.stack[i].type),
 600                   st.stack[i].equivLoc == NoLocalId ? "" :
 601                   local_string(f, st.stack[i].equivLoc));
 602   }
 603
 604   for (auto i = size_t{0}; i < st.equivLocals.size(); ++i) {
 605     if (st.equivLocals[i] == NoLocalId) continue;
 606     folly::format(&ret, "{: <8} ==", local_string(f, i));
 607     for (auto j = st.equivLocals[i]; j != i; j = st.equivLocals[j]) {
 608       ret += " ";
 609       ret += local_string(f, j);
 610     }
 611     ret += "\n";
 612   }
 613
 614   if (collect.mInstrState.base.loc != BaseLoc::None) {
 615     folly::format(&ret, "mInstrState   :: {}\n", show(f, collect.mInstrState));
 616   }
 617
 618   return ret;
 619 }
 620
 621 std::string property_state_string(const PropertiesInfo& props) {
 622   std::string ret;
 623
 624   for (auto& kv : props.privateProperties()) {
 625     folly::format(&ret, "$this->{: <14} :: {}\n", kv.first, show(kv.second.ty));
 626   }
 627   for (auto& kv : props.privateStatics()) {
 628     folly::format(&ret, "self::${: <14} :: {}\n", kv.first, show(kv.second.ty));
 629   }
 630
 631   return ret;
 632 }
 633
 634 //////////////////////////////////////////////////////////////////////
 635
 636 }}