hphp/hhbbc/parse.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2015 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/parse.h"
  17
  18 #include <thread>
  19 #include <mutex>
  20 #include <unordered_map>
  21 #include <map>
  22
  23 #include <boost/variant.hpp>
  24 #include <algorithm>
  25 #include <iterator>
  26 #include <memory>
  27 #include <set>
  28 #include <unordered_set>
  29 #include <utility>
  30 #include <vector>
  31
  32 #include <folly/gen/Base.h>
  33 #include <folly/gen/String.h>
  34 #include <folly/ScopeGuard.h>
  35 #include <folly/Memory.h>
  36
  37 #include "hphp/runtime/base/repo-auth-type-codec.h"
  38 #include "hphp/runtime/base/repo-auth-type.h"
  39 #include "hphp/runtime/vm/func-emitter.h"
  40 #include "hphp/runtime/vm/hhbc-codec.h"
  41 #include "hphp/runtime/vm/preclass-emitter.h"
  42 #include "hphp/runtime/vm/unit-emitter.h"
  43
  44 #include "hphp/hhbbc/representation.h"
  45 #include "hphp/hhbbc/cfg.h"
  46 #include "hphp/hhbbc/unit-util.h"
  47
  48 namespace HPHP { namespace HHBBC {
  49
  50 TRACE_SET_MOD(hhbbc);
  51
  52 namespace {
  53
  54 //////////////////////////////////////////////////////////////////////
  55
  56 const StaticString s_Closure("Closure");
  57 const StaticString s_toString("__toString");
  58 const StaticString s_Stringish("Stringish");
  59
  60 //////////////////////////////////////////////////////////////////////
  61
  62 struct ParseUnitState {
  63   /*
  64    * This is computed once for each unit and stashed here.  We support
  65    * having either a SourceLocTable or a LineTable.  If we're
  66    * optimizing a repo that was already created by hphpc, it won't
  67    * have the full SourceLocTable information in it, so we're limited
  68    * to line numbers.
  69    */
  70   boost::variant< SourceLocTable
  71                 , LineTable
  72                 > srcLocInfo;
  73
  74   /*
  75    * Map from class id to the function containing its DefCls
  76    * instruction.  We use this to compute whether classes are defined
  77    * at top-level.
  78    *
  79    * TODO_4: if we don't end up with a use for this, remove it.
  80    */
  81   std::vector<borrowed_ptr<php::Func>> defClsMap;
  82
  83   /*
  84    * Map from Closure names to the function(s) containing their
  85    * associated CreateCl opcode(s).
  86    */
  87   std::unordered_map<
  88     SString,
  89     std::unordered_set<borrowed_ptr<php::Func>>,
  90     string_data_hash,
  91     string_data_isame
  92   > createClMap;
  93 };
  94
  95 //////////////////////////////////////////////////////////////////////
  96
  97 std::set<Offset> findBasicBlocks(const FuncEmitter& fe) {
  98   std::set<Offset> blockStarts;
  99   auto markBlock = [&] (Offset off) { blockStarts.insert(off); };
 100
 101   // Each entry point for a DV funclet is the start of a basic
 102   // block.
 103   for (auto& param : fe.params) {
 104     if (param.hasDefaultValue()) markBlock(param.funcletOff);
 105   }
 106
 107   // The main entry point is also a basic block start.
 108   markBlock(fe.base);
 109
 110   /*
 111    * For each instruction, add it to the set if it must be the start
 112    * of a block.  It is the start of a block if it is:
 113    *
 114    *   - A jump target
 115    *
 116    *   - Immediatelly following a control flow instruction, other than
 117    *     a call.
 118    */
 119   auto offset = fe.base;
 120   for (;;) {
 121     auto const bc = fe.ue().bc();
 122     auto const pc = bc + offset;
 123     auto const nextOff = offset + instrLen(pc);
 124     auto const atLast = nextOff == fe.past;
 125     auto const op = peek_op(pc);
 126     auto const breaksBB = instrIsNonCallControlFlow(op) || instrFlags(op) & TF;
 127
 128     if (breaksBB && !atLast) {
 129       markBlock(nextOff);
 130     }
 131
 132     if (isSwitch(op)) {
 133       foreachSwitchTarget(pc, [&] (Offset delta) {
 134         markBlock(offset + delta);
 135       });
 136     } else {
 137       auto const target = instrJumpTarget(bc, offset);
 138       if (target != InvalidAbsoluteOffset) markBlock(target);
 139     }
 140
 141     offset = nextOff;
 142     if (atLast) break;
 143   }
 144
 145   /*
 146    * Find blocks associated with exception handlers.
 147    *
 148    *   - The start of each fault-protected region begins a block.
 149    *
 150    *   - The instruction immediately after the end of any
 151    *     fault-protected region begins a block.
 152    *
 153    *   - Each fault or catch entry point begins a block.
 154    */
 155   for (auto& eh : fe.ehtab) {
 156     markBlock(eh.m_base);
 157     markBlock(eh.m_past);
 158     switch (eh.m_type) {
 159     case EHEnt::Type::Catch:
 160       for (auto& centry : eh.m_catches) markBlock(centry.second);
 161       break;
 162     case EHEnt::Type::Fault:
 163       markBlock(eh.m_fault);
 164       break;
 165     }
 166   }
 167
 168   // Now, each interval in blockStarts delinates a basic block.
 169   blockStarts.insert(fe.past);
 170   return blockStarts;
 171 }
 172
 173 struct ExnTreeInfo {
 174   /*
 175    * Map from EHEnt to the ExnNode that will represent exception
 176    * behavior in that region.
 177    */
 178   std::map<const EHEntEmitter*,borrowed_ptr<php::ExnNode>> ehMap;
 179
 180   /*
 181    * Fault funclets don't actually fall in the EHEnt region for all of
 182    * their parent handlers in HHBC.  There may be EHEnt regions
 183    * covering the fault funclet, but if an exception occurs in the
 184    * funclet it can also propagate to any EH region from the code that
 185    * entered the funclet.  We want factored exit edges from the fault
 186    * funclets to any of these enclosing catch blocks (or other
 187    * enclosing funclet blocks).
 188    *
 189    * Moreover, funclet offsets can be entered from multiple protected
 190    * regions, so we need to keep a map of all the possible regions
 191    * that could have entered a given funclet, so we can add exit edges
 192    * to all their parent EHEnt handlers.
 193    */
 194   std::map<borrowed_ptr<php::Block>,std::vector<borrowed_ptr<php::ExnNode>>>
 195     funcletNodes;
 196
 197   /*
 198    * Keep track of the start offsets for all fault funclets.  This is
 199    * used to find the extents of each handler for find_fault_funclets.
 200    * It is assumed that each fault funclet handler extends from its
 201    * entry offset until the next fault funclet entry offset (or end of
 202    * the function).
 203    *
 204    * This relies on the following bytecode invariants:
 205    *
 206    *   - All fault funclets come after the primary function body.
 207    *
 208    *   - Each fault funclet is a contiguous region of bytecode that
 209    *     does not jump into other fault funclets or into the primary
 210    *     function body.
 211    *
 212    *   - Nothing comes after the fault funclets.
 213    */
 214   std::set<Offset> faultFuncletStarts;
 215 };
 216
 217 template<class FindBlock>
 218 ExnTreeInfo build_exn_tree(const FuncEmitter& fe,
 219                            php::Func& func,
 220                            FindBlock findBlock) {
 221   ExnTreeInfo ret;
 222   auto nextExnNode = uint32_t{0};
 223
 224   for (auto& eh : fe.ehtab) {
 225     auto node = folly::make_unique<php::ExnNode>();
 226     node->id = nextExnNode++;
 227     node->parent = nullptr;
 228
 229     switch (eh.m_type) {
 230     case EHEnt::Type::Fault:
 231       {
 232         auto const fault = findBlock(eh.m_fault);
 233         ret.funcletNodes[fault].push_back(borrow(node));
 234         ret.faultFuncletStarts.insert(eh.m_fault);
 235         node->info = php::FaultRegion { fault, eh.m_iterId, eh.m_itRef };
 236       }
 237       break;
 238     case EHEnt::Type::Catch:
 239       {
 240         auto treg = php::TryRegion {};
 241         for (auto& centry : eh.m_catches) {
 242           auto const catchBlk = findBlock(centry.second);
 243           treg.catches.emplace_back(
 244             fe.ue().lookupLitstr(centry.first),
 245             catchBlk
 246           );
 247         }
 248         node->info = treg;
 249       }
 250       break;
 251     }
 252
 253     ret.ehMap[&eh] = borrow(node);
 254
 255     if (eh.m_parentIndex != -1) {
 256       auto it = ret.ehMap.find(&fe.ehtab[eh.m_parentIndex]);
 257       assert(it != end(ret.ehMap));
 258       node->parent = it->second;
 259       it->second->children.emplace_back(std::move(node));
 260     } else {
 261       func.exnNodes.emplace_back(std::move(node));
 262     }
 263   }
 264
 265   ret.faultFuncletStarts.insert(fe.past);
 266
 267   return ret;
 268 }
 269
 270 /*
 271  * Instead of breaking blocks on instructions that could throw, we
 272  * represent the control flow edges for exception paths as a set of
 273  * factored edges at the end of each block.
 274  *
 275  * When we initially add them here, no attempt is made to determine if
 276  * the edge is actually possible to traverse.
 277  */
 278 void add_factored_exits(php::Block& blk,
 279                         borrowed_ptr<const php::ExnNode> node) {
 280   for (; node; node = node->parent) {
 281     match<void>(
 282       node->info,
 283       [&] (const php::TryRegion& tr) {
 284         /*
 285          * Note: it seems like we should be able to stop adding edges
 286          * when we see a catch handler for Exception; however, fatal
 287          * errors don't stop there (and still run Fault handlers).
 288          *
 289          * For now we add all the edges, although we might be able to be
 290          * less pessimistic later.
 291          */
 292         for (auto& c : tr.catches) {
 293           blk.factoredExits.push_back(c.second);
 294         }
 295       },
 296       [&] (const php::FaultRegion& fr) {
 297         blk.factoredExits.push_back(fr.faultEntry);
 298       }
 299     );
 300   }
 301 }
 302
 303 /*
 304  * Locate all the basic blocks associated with fault funclets, and
 305  * mark them as such.  Also, add factored exit edges for exceptional
 306  * control flow through any parent protected regions of the region(s)
 307  * that pointed at each fault handler.
 308  */
 309 template<class BlockStarts, class FindBlock>
 310 void find_fault_funclets(ExnTreeInfo& tinfo,
 311                          const php::Func& func,
 312                          const BlockStarts& blockStarts,
 313                          FindBlock findBlock) {
 314   auto sectionId = uint32_t{1};
 315
 316   for (auto funcletStartIt = begin(tinfo.faultFuncletStarts);
 317       std::next(funcletStartIt) != end(tinfo.faultFuncletStarts);
 318       ++funcletStartIt, ++sectionId) {
 319     auto const nextFunclet = *std::next(funcletStartIt);
 320
 321     auto offIt = blockStarts.find(*funcletStartIt);
 322     assert(offIt != end(blockStarts));
 323
 324     auto const firstBlk  = findBlock(*offIt);
 325     auto const funcletIt = tinfo.funcletNodes.find(firstBlk);
 326     assert(funcletIt != end(tinfo.funcletNodes));
 327     assert(!funcletIt->second.empty());
 328
 329     do {
 330       auto const blk = findBlock(*offIt);
 331       blk->section   = static_cast<php::Block::Section>(sectionId);
 332
 333       // Propagate the exit edges to the containing fault/try handlers,
 334       // if there were any.
 335       for (auto& node : funcletIt->second) {
 336         add_factored_exits(*blk, node->parent);
 337       }
 338
 339       // Fault funclets can have protected regions which may point to
 340       // handlers that are also listed in parents of the EH-region that
 341       // targets the funclet.  This means we might have duplicate
 342       // factored exits now, so we need to remove them.
 343       std::sort(begin(blk->factoredExits), end(blk->factoredExits));
 344       blk->factoredExits.erase(
 345         std::unique(begin(blk->factoredExits), end(blk->factoredExits)),
 346         end(blk->factoredExits)
 347       );
 348
 349       ++offIt;
 350     } while (offIt != end(blockStarts) && *offIt < nextFunclet);
 351   }
 352 }
 353
 354 template<class T> T decode(PC& pc) {
 355   auto const ret = *reinterpret_cast<const T*>(pc);
 356   pc += sizeof ret;
 357   return ret;
 358 }
 359
 360 template<class T> void decode(PC& pc, T& val) {
 361   val = decode<T>(pc);
 362 }
 363
 364 template<class FindBlock>
 365 void populate_block(ParseUnitState& puState,
 366                     const FuncEmitter& fe,
 367                     php::Func& func,
 368                     php::Block& blk,
 369                     PC pc,
 370                     PC const past,
 371                     FindBlock findBlock) {
 372   auto const& ue = fe.ue();
 373
 374   auto decode_minstr = [&] {
 375     auto const immVec = ImmVector::createFromStream(pc);
 376     pc += immVec.size() + sizeof(int32_t) + sizeof(int32_t);
 377
 378     auto ret = MVector {};
 379     auto vec = immVec.vec();
 380
 381     ret.lcode = static_cast<LocationCode>(*vec++);
 382     if (numLocationCodeImms(ret.lcode)) {
 383       assert(numLocationCodeImms(ret.lcode) == 1);
 384       ret.locBase = borrow(func.locals[decodeVariableSizeImm(&vec)]);
 385     }
 386
 387     while (vec < pc) {
 388       auto elm = MElem {};
 389       elm.mcode = static_cast<MemberCode>(*vec++);
 390       switch (memberCodeImmType(elm.mcode)) {
 391       case MCodeImm::None: break;
 392       case MCodeImm::Local:
 393         elm.immLoc = borrow(func.locals[decodeMemberCodeImm(&vec, elm.mcode)]);
 394         break;
 395       case MCodeImm::String:
 396         elm.immStr = ue.lookupLitstr(decodeMemberCodeImm(&vec, elm.mcode));
 397         break;
 398       case MCodeImm::Int:
 399         elm.immInt = decodeMemberCodeImm(&vec, elm.mcode);
 400         break;
 401       }
 402       ret.mcodes.push_back(elm);
 403     }
 404     assert(vec == pc);
 405
 406     return ret;
 407   };
 408
 409   auto decode_stringvec = [&] {
 410     auto const vecLen = decode<int32_t>(pc);
 411     std::vector<SString> keys;
 412     for (auto i = size_t{0}; i < vecLen; ++i) {
 413       keys.push_back(ue.lookupLitstr(decode<int32_t>(pc)));
 414     }
 415     return keys;
 416   };
 417
 418   auto decode_switch = [&] (PC opPC) {
 419     SwitchTab ret;
 420     auto const vecLen = decode<int32_t>(pc);
 421     for (int32_t i = 0; i < vecLen; ++i) {
 422       ret.push_back(findBlock(
 423         opPC + decode<Offset>(pc) - ue.bc()
 424       ));
 425     }
 426     return ret;
 427   };
 428
 429   auto decode_sswitch = [&] (PC opPC) {
 430     SSwitchTab ret;
 431
 432     auto const vecLen = decode<int32_t>(pc);
 433     for (int32_t i = 0; i < vecLen - 1; ++i) {
 434       auto const id = decode<Id>(pc);
 435       auto const offset = decode<Offset>(pc);
 436       ret.emplace_back(
 437         ue.lookupLitstr(id),
 438         findBlock(opPC + offset - ue.bc())
 439       );
 440     }
 441
 442     // Final case is the default, and must have a litstr id of -1.
 443     DEBUG_ONLY auto const defId = decode<Id>(pc);
 444     auto const defOff = decode<Offset>(pc);
 445     assert(defId == -1);
 446     ret.emplace_back(nullptr, findBlock(opPC + defOff - ue.bc()));
 447     return ret;
 448   };
 449
 450   auto decode_itertab = [&] {
 451     IterTab ret;
 452     auto const vecLen = decode<int32_t>(pc);
 453     for (int32_t i = 0; i < vecLen; ++i) {
 454       auto const kind = static_cast<IterKind>(decode<int32_t>(pc));
 455       auto const id = decode<int32_t>(pc);
 456       ret.emplace_back(kind, borrow(func.iters[id]));
 457     }
 458     return ret;
 459   };
 460
 461   auto defcls = [&] (const Bytecode& b) {
 462     puState.defClsMap[b.DefCls.arg1] = &func;
 463   };
 464   auto defclsnop = [&] (const Bytecode& b) {
 465     puState.defClsMap[b.DefClsNop.arg1] = &func;
 466   };
 467   auto createcl = [&] (const Bytecode& b) {
 468     puState.createClMap[b.CreateCl.str2].insert(&func);
 469   };
 470
 471 #define IMM_MA(n)      auto mvec = decode_minstr();
 472 #define IMM_BLA(n)     auto targets = decode_switch(opPC);
 473 #define IMM_SLA(n)     auto targets = decode_sswitch(opPC);
 474 #define IMM_ILA(n)     auto iterTab = decode_itertab();
 475 #define IMM_IVA(n)     auto arg##n = decodeVariableSizeImm(&pc);
 476 #define IMM_I64A(n)    auto arg##n = decode<int64_t>(pc);
 477 #define IMM_LA(n)      auto loc##n = [&] {                       \
 478                          auto id = decodeVariableSizeImm(&pc);   \
 479                          always_assert(id < func.locals.size()); \
 480                          return borrow(func.locals[id]);         \
 481                        }();
 482 #define IMM_IA(n)      auto iter##n = [&] {                      \
 483                          auto id = decodeVariableSizeImm(&pc);   \
 484                          always_assert(id < func.iters.size());  \
 485                          return borrow(func.iters[id]);          \
 486                        }();
 487 #define IMM_DA(n)      auto dbl##n = decode<double>(pc);
 488 #define IMM_SA(n)      auto str##n = ue.lookupLitstr(decode<Id>(pc));
 489 #define IMM_RATA(n)    auto rat = decodeRAT(ue, pc);
 490 #define IMM_AA(n)      auto arr##n = ue.lookupArray(decode<Id>(pc));
 491 #define IMM_BA(n)      assert(next == past); \
 492                        auto target = findBlock(  \
 493                          opPC + decode<Offset>(pc) - ue.bc());
 494 #define IMM_OA_IMPL(n) subop##n; decode(pc, subop##n);
 495 #define IMM_OA(type)   type IMM_OA_IMPL
 496 #define IMM_VSA(n)     auto keys = decode_stringvec();
 497
 498 #define IMM_NA
 499 #define IMM_ONE(x)           IMM_##x(1)
 500 #define IMM_TWO(x, y)        IMM_##x(1)          IMM_##y(2)
 501 #define IMM_THREE(x, y, z)   IMM_TWO(x, y)       IMM_##z(3)
 502 #define IMM_FOUR(x, y, z, n) IMM_THREE(x, y, z)  IMM_##n(4)
 503
 504 #define IMM_ARG(which, n)         IMM_NAME_##which(n)
 505 #define IMM_ARG_NA
 506 #define IMM_ARG_ONE(x)            IMM_ARG(x, 1)
 507 #define IMM_ARG_TWO(x, y)         IMM_ARG(x, 1), IMM_ARG(y, 2)
 508 #define IMM_ARG_THREE(x, y, z)    IMM_ARG(x, 1), IMM_ARG(y, 2), \
 509                                     IMM_ARG(z, 3)
 510 #define IMM_ARG_FOUR(x, y, z, l)  IMM_ARG(x, 1), IMM_ARG(y, 2), \
 511                                    IMM_ARG(z, 3), IMM_ARG(l, 4)
 512
 513
 514 #define O(opcode, imms, inputs, outputs, flags)       \
 515   case Op::opcode:                                    \
 516     {                                                 \
 517       auto b = Bytecode {};                           \
 518       b.op = Op::opcode;                              \
 519       b.srcLoc = srcLoc;                              \
 520       IMM_##imms                                      \
 521       new (&b.opcode) bc::opcode { IMM_ARG_##imms };  \
 522       if (Op::opcode == Op::DefCls)    defcls(b);     \
 523       if (Op::opcode == Op::DefClsNop) defclsnop(b);  \
 524       if (Op::opcode == Op::CreateCl)  createcl(b);   \
 525       blk.hhbcs.push_back(std::move(b));              \
 526       assert(pc == next);                             \
 527     }                                                 \
 528     break;
 529
 530   assert(pc != past);
 531   do {
 532     auto const opPC = pc;
 533     auto const next = pc + instrLen(opPC);
 534     assert(next <= past);
 535
 536     auto const srcLoc = match<php::SrcLoc>(
 537       puState.srcLocInfo,
 538       [&] (const SourceLocTable& tab) {
 539         SourceLoc sloc;
 540         if (getSourceLoc(tab, opPC - ue.bc(), sloc)) {
 541           return php::SrcLoc {
 542             { static_cast<uint32_t>(sloc.line0),
 543               static_cast<uint32_t>(sloc.char0) },
 544             { static_cast<uint32_t>(sloc.line1),
 545               static_cast<uint32_t>(sloc.char1) }
 546           };
 547         }
 548         return php::SrcLoc{};
 549       },
 550       [&] (const LineTable& tab) {
 551         auto const line = getLineNumber(tab, opPC - ue.bc());
 552         if (line != -1) {
 553           return php::SrcLoc {
 554             { static_cast<uint32_t>(line), 0 },
 555             { static_cast<uint32_t>(line), 0 },
 556           };
 557         };
 558         return php::SrcLoc{};
 559       }
 560     );
 561
 562     auto const op = decode_op(pc);
 563     switch (op) { OPCODES }
 564
 565     if (next == past) {
 566       if (instrAllowsFallThru(op)) {
 567         blk.fallthrough = findBlock(next - ue.bc());
 568       }
 569     }
 570
 571     pc = next;
 572   } while (pc != past);
 573
 574 #undef O
 575
 576 #undef IMM_MA
 577 #undef IMM_BLA
 578 #undef IMM_SLA
 579 #undef IMM_ILA
 580 #undef IMM_IVA
 581 #undef IMM_I64A
 582 #undef IMM_LA
 583 #undef IMM_IA
 584 #undef IMM_DA
 585 #undef IMM_SA
 586 #undef IMM_RATA
 587 #undef IMM_AA
 588 #undef IMM_BA
 589 #undef IMM_OA_IMPL
 590 #undef IMM_OA
 591 #undef IMM_VSA
 592
 593 #undef IMM_NA
 594 #undef IMM_ONE
 595 #undef IMM_TWO
 596 #undef IMM_THREE
 597 #undef IMM_FOUR
 598
 599 #undef IMM_ARG
 600 #undef IMM_ARG_NA
 601 #undef IMM_ARG_ONE
 602 #undef IMM_ARG_TWO
 603 #undef IMM_ARG_THREE
 604 #undef IMM_ARG_FOUR
 605
 606   /*
 607    * If a block ends with an unconditional jump, change it to a
 608    * fallthrough edge.
 609    *
 610    * Just convert the opcode to a Nop, because this could create an
 611    * empty block and we have an invariant that no blocks are empty.
 612    */
 613
 614   auto make_fallthrough = [&] {
 615     blk.fallthrough = blk.hhbcs.back().Jmp.target;
 616     blk.hhbcs.back() = bc_with_loc(blk.hhbcs.back().srcLoc, bc::Nop{});
 617   };
 618
 619   switch (blk.hhbcs.back().op) {
 620   case Op::Jmp:   make_fallthrough();                           break;
 621   case Op::JmpNS: make_fallthrough(); blk.fallthroughNS = true; break;
 622   default:                                                      break;
 623   }
 624 }
 625
 626 template<class FindBlk>
 627 void link_entry_points(php::Func& func,
 628                        const FuncEmitter& fe,
 629                        FindBlk findBlock) {
 630   func.dvEntries.resize(fe.params.size());
 631   for (size_t i = 0, sz = fe.params.size(); i < sz; ++i) {
 632     if (fe.params[i].hasDefaultValue()) {
 633       auto const dv = findBlock(fe.params[i].funcletOff);
 634       func.params[i].dvEntryPoint = dv;
 635       func.dvEntries[i] = dv;
 636     }
 637   }
 638   func.mainEntry = findBlock(fe.base);
 639 }
 640
 641 void build_cfg(ParseUnitState& puState,
 642                php::Func& func,
 643                const FuncEmitter& fe) {
 644   auto const blockStarts = findBasicBlocks(fe);
 645
 646   FTRACE(3, "    blocks are at: {}\n",
 647     [&]() -> std::string {
 648       using namespace folly::gen;
 649       return from(blockStarts)
 650         | eachTo<std::string>()
 651         | unsplit<std::string>(" ");
 652     }()
 653   );
 654
 655   std::map<Offset,std::unique_ptr<php::Block>> blockMap;
 656   auto const bc = fe.ue().bc();
 657
 658   auto findBlock = [&] (Offset off) {
 659     auto& ptr = blockMap[off];
 660     if (!ptr) {
 661       ptr               = folly::make_unique<php::Block>();
 662       ptr->id           = func.nextBlockId++;
 663       ptr->section      = php::Block::Section::Main;
 664       ptr->exnNode      = nullptr;
 665     }
 666     return borrow(ptr);
 667   };
 668
 669   auto exnTreeInfo = build_exn_tree(fe, func, findBlock);
 670
 671   for (auto it = begin(blockStarts);
 672       std::next(it) != end(blockStarts);
 673       ++it) {
 674     auto const block   = findBlock(*it);
 675     auto const bcStart = bc + *it;
 676     auto const bcStop  = bc + *std::next(it);
 677
 678     if (auto const eh = findEH(fe.ehtab, *it)) {
 679       auto it = exnTreeInfo.ehMap.find(eh);
 680       assert(it != end(exnTreeInfo.ehMap));
 681       block->exnNode = it->second;
 682       add_factored_exits(*block, block->exnNode);
 683     }
 684
 685     populate_block(puState, fe, func, *block, bcStart, bcStop, findBlock);
 686   }
 687
 688   link_entry_points(func, fe, findBlock);
 689   find_fault_funclets(exnTreeInfo, func, blockStarts, findBlock);
 690
 691   for (auto& kv : blockMap) {
 692     func.blocks.emplace_back(std::move(kv.second));
 693   }
 694 }
 695
 696 void add_frame_variables(php::Func& func, const FuncEmitter& fe) {
 697   for (auto& param : fe.params) {
 698     func.params.push_back(
 699       php::Param {
 700         param.defaultValue,
 701         nullptr,
 702         param.typeConstraint,
 703         param.userType,
 704         param.phpCode,
 705         param.userAttributes,
 706         param.builtinType,
 707         param.byRef,
 708         param.variadic
 709       }
 710     );
 711   }
 712
 713   func.locals.resize(fe.numLocals());
 714   for (size_t id = 0; id < func.locals.size(); ++id) {
 715     auto& loc = func.locals[id];
 716     loc = folly::make_unique<php::Local>();
 717     loc->id = id;
 718     loc->name = nullptr;
 719   }
 720   for (auto& kv : fe.localNameMap()) {
 721     func.locals[kv.second]->name = kv.first;
 722   }
 723
 724   func.iters.resize(fe.numIterators());
 725   for (uint32_t i = 0; i < func.iters.size(); ++i) {
 726     func.iters[i] = folly::make_unique<php::Iter>();
 727     func.iters[i]->id = i;
 728   }
 729
 730   func.staticLocals.reserve(fe.staticVars.size());
 731   for (auto& sv : fe.staticVars) {
 732     func.staticLocals.push_back(
 733       php::StaticLocalInfo { sv.name, sv.phpCode }
 734     );
 735   }
 736 }
 737
 738 std::unique_ptr<php::Func> parse_func(ParseUnitState& puState,
 739                                       borrowed_ptr<php::Unit> unit,
 740                                       borrowed_ptr<php::Class> cls,
 741                                       const FuncEmitter& fe) {
 742   FTRACE(2, "  func: {}\n",
 743     fe.name->data() && *fe.name->data() ? fe.name->data() : "pseudomain");
 744
 745   auto ret             = folly::make_unique<php::Func>();
 746   ret->name            = fe.name;
 747   ret->srcInfo         = php::SrcInfo { fe.getLocation(),
 748                                         fe.docComment };
 749   ret->unit            = unit;
 750   ret->cls             = cls;
 751   ret->nextBlockId     = 0;
 752
 753   ret->attrs              = static_cast<Attr>(fe.attrs & ~AttrNoOverride);
 754   ret->userAttributes     = fe.userAttributes;
 755   ret->returnUserType     = fe.retUserType;
 756   ret->retTypeConstraint  = fe.retTypeConstraint;
 757   ret->originalFilename   = fe.originalFilename;
 758
 759   ret->top                = fe.top;
 760   ret->isClosureBody      = fe.isClosureBody;
 761   ret->isAsync            = fe.isAsync;
 762   ret->isGenerator        = fe.isGenerator;
 763   ret->isPairGenerator    = fe.isPairGenerator;
 764
 765   /*
 766    * Builtin functions get some extra information.  The returnType flag is only
 767    * non-folly::none for these, but note that something may be a builtin and
 768    * still have a folly::none return type.
 769    */
 770   if (fe.attrs & AttrBuiltin) {
 771     ret->nativeInfo             = folly::make_unique<php::NativeInfo>();
 772     ret->nativeInfo->returnType = fe.returnType;
 773   }
 774
 775   add_frame_variables(*ret, fe);
 776   build_cfg(puState, *ret, fe);
 777
 778   return ret;
 779 }
 780
 781 void parse_methods(ParseUnitState& puState,
 782                    borrowed_ptr<php::Class> ret,
 783                    borrowed_ptr<php::Unit> unit,
 784                    const PreClassEmitter& pce) {
 785   for (auto& me : pce.methods()) {
 786     auto f = parse_func(puState, unit, ret, *me);
 787     ret->methods.push_back(std::move(f));
 788   }
 789 }
 790
 791 void add_stringish(borrowed_ptr<php::Class> cls) {
 792   // The runtime adds Stringish to any class providing a __toString() function,
 793   // so we mirror that here to make sure analysis of interfaces is correct.
 794   if (cls->attrs & AttrInterface && cls->name->isame(s_Stringish.get())) {
 795     return;
 796   }
 797
 798   for (auto& iface : cls->interfaceNames) {
 799     if (iface->isame(s_Stringish.get())) return;
 800   }
 801
 802   for (auto& func : cls->methods) {
 803     if (func->name->isame(s_toString.get())) {
 804       FTRACE(2, "Adding Stringish to {}\n", cls->name->data());
 805       cls->interfaceNames.push_back(s_Stringish.get());
 806       return;
 807     }
 808   }
 809 }
 810
 811 std::unique_ptr<php::Class> parse_class(ParseUnitState& puState,
 812                                         borrowed_ptr<php::Unit> unit,
 813                                         const PreClassEmitter& pce) {
 814   FTRACE(2, "  class: {}\n", pce.name()->data());
 815
 816   auto ret               = folly::make_unique<php::Class>();
 817   ret->name              = pce.name();
 818   ret->srcInfo           = php::SrcInfo { pce.getLocation(),
 819                                           pce.docComment() };
 820   ret->unit              = unit;
 821   ret->closureContextCls = nullptr;
 822   ret->parentName        = pce.parentName()->empty() ? nullptr
 823                                                      : pce.parentName();
 824   ret->attrs             = static_cast<Attr>(pce.attrs() & ~AttrNoOverride);
 825   ret->hoistability      = pce.hoistability();
 826   ret->userAttributes    = pce.userAttributes();
 827
 828   for (auto& iface : pce.interfaces()) {
 829     ret->interfaceNames.push_back(iface);
 830   }
 831
 832   ret->usedTraitNames    = pce.usedTraits();
 833   ret->traitPrecRules    = pce.traitPrecRules();
 834   ret->traitAliasRules   = pce.traitAliasRules();
 835   ret->requirements      = pce.requirements();
 836   ret->numDeclMethods    = pce.numDeclMethods();
 837
 838   parse_methods(puState, borrow(ret), unit, pce);
 839   add_stringish(borrow(ret));
 840
 841   auto& propMap = pce.propMap();
 842   for (size_t idx = 0; idx < propMap.size(); ++idx) {
 843     auto& prop = propMap[idx];
 844     ret->properties.push_back(
 845       php::Prop {
 846         prop.name(),
 847         prop.attrs(),
 848         prop.docComment(),
 849         prop.typeConstraint(),
 850         prop.val()
 851       }
 852     );
 853   }
 854
 855   auto& constMap = pce.constMap();
 856   for (size_t idx = 0; idx < constMap.size(); ++idx) {
 857     auto& cconst = constMap[idx];
 858     ret->constants.push_back(
 859       php::Const {
 860         cconst.name(),
 861         borrow(ret),
 862         cconst.valOption(),
 863         cconst.phpCode(),
 864         cconst.typeConstraint(),
 865         cconst.isTypeconst()
 866       }
 867     );
 868   }
 869
 870   ret->enumBaseTy = pce.enumBaseTy();
 871
 872   return ret;
 873 }
 874
 875 //////////////////////////////////////////////////////////////////////
 876
 877 void assign_closure_context(const ParseUnitState&, borrowed_ptr<php::Class>);
 878
 879 borrowed_ptr<php::Class>
 880 find_closure_context(const ParseUnitState& puState,
 881                      borrowed_ptr<php::Func> createClFunc) {
 882   if (auto const cls = createClFunc->cls) {
 883     if (cls->parentName &&
 884         cls->parentName->isame(s_Closure.get())) {
 885       // We have a closure created by a closure's invoke method, which
 886       // means it should inherit the outer closure's context, so we
 887       // have to know that first.
 888       assign_closure_context(puState, cls);
 889       return cls->closureContextCls;
 890     }
 891     return cls;
 892   }
 893   return nullptr;
 894 }
 895
 896 void assign_closure_context(const ParseUnitState& puState,
 897                             borrowed_ptr<php::Class> clo) {
 898   if (clo->closureContextCls) return;
 899
 900   auto clIt = puState.createClMap.find(clo->name);
 901   if (clIt == end(puState.createClMap)) {
 902     // Unused closure class.  Technically not prohibited by the spec.
 903     return;
 904   }
 905
 906   /*
 907    * Any route to the closure context must yield the same class, or
 908    * things downstream won't understand.  We try every route and
 909    * assert they are all the same here.
 910    *
 911    * See bytecode.specification for CreateCl for the relevant
 912    * invariants.
 913    */
 914   always_assert(!clIt->second.empty());
 915   auto it = begin(clIt->second);
 916   auto const representative = find_closure_context(puState, *it);
 917   if (debug) {
 918     ++it;
 919     for (; it != end(clIt->second); ++it) {
 920       assert(find_closure_context(puState, *it) == representative);
 921     }
 922   }
 923   clo->closureContextCls = representative;
 924 }
 925
 926 void find_additional_metadata(const ParseUnitState& puState,
 927                               borrowed_ptr<php::Unit> unit) {
 928   for (auto& c : unit->classes) {
 929     if (!c->parentName || !c->parentName->isame(s_Closure.get())) {
 930       continue;
 931     }
 932     assign_closure_context(puState, borrow(c));
 933   }
 934 }
 935
 936 //////////////////////////////////////////////////////////////////////
 937
 938 }
 939
 940 std::unique_ptr<php::Unit> parse_unit(const UnitEmitter& ue) {
 941   Trace::Bump bumper{Trace::hhbbc, kSystemLibBump, ue.isASystemLib()};
 942   FTRACE(2, "parse_unit {}\n", ue.m_filepath->data());
 943
 944   auto ret      = folly::make_unique<php::Unit>();
 945   ret->md5      = ue.md5();
 946   ret->filename = ue.m_filepath;
 947   ret->preloadPriority = ue.m_preloadPriority;
 948
 949   ParseUnitState puState;
 950   if (ue.hasSourceLocInfo()) {
 951     puState.srcLocInfo = ue.createSourceLocTable();
 952   } else {
 953     puState.srcLocInfo = ue.lineTable();
 954   }
 955   puState.defClsMap.resize(ue.numPreClasses(), nullptr);
 956
 957   for (size_t i = 0; i < ue.numPreClasses(); ++i) {
 958     auto cls = parse_class(puState, borrow(ret), *ue.pce(i));
 959     ret->classes.push_back(std::move(cls));
 960   }
 961
 962   for (auto& fe : ue.fevec()) {
 963     auto func = parse_func(puState, borrow(ret), nullptr, *fe);
 964     assert(!fe->pce());
 965     if (fe->isPseudoMain()) {
 966       ret->pseudomain = std::move(func);
 967     } else {
 968       ret->funcs.push_back(std::move(func));
 969     }
 970   }
 971
 972   for (auto& ta : ue.typeAliases()) {
 973     ret->typeAliases.push_back(
 974       folly::make_unique<php::TypeAlias>(ta)
 975     );
 976   }
 977
 978   find_additional_metadata(puState, borrow(ret));
 979
 980   return ret;
 981 }
 982
 983 //////////////////////////////////////////////////////////////////////
 984
 985 }}