hphp/hhbbc/parse.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/parse.h"
  17
  18 #include <thread>
  19 #include <unordered_map>
  20 #include <map>
  21
  22 #include <boost/variant.hpp>
  23 #include <algorithm>
  24 #include <iterator>
  25 #include <memory>
  26 #include <set>
  27 #include <unordered_set>
  28 #include <utility>
  29 #include <vector>
  30
  31 #include <folly/gen/Base.h>
  32 #include <folly/gen/String.h>
  33 #include <folly/Memory.h>
  34 #include <folly/ScopeGuard.h>
  35 #include <folly/sorted_vector_types.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/ext/std/ext_std_misc.h"
  40 #include "hphp/runtime/vm/func-emitter.h"
  41 #include "hphp/runtime/vm/hhbc-codec.h"
  42 #include "hphp/runtime/vm/preclass-emitter.h"
  43 #include "hphp/runtime/vm/unit-emitter.h"
  44
  45 #include "hphp/hhbbc/cfg.h"
  46 #include "hphp/hhbbc/eval-cell.h"
  47 #include "hphp/hhbbc/func-util.h"
  48 #include "hphp/hhbbc/optimize.h"
  49 #include "hphp/hhbbc/representation.h"
  50 #include "hphp/hhbbc/unit-util.h"
  51
  52 namespace HPHP { namespace HHBBC {
  53
  54 TRACE_SET_MOD(hhbbc_parse);
  55
  56 namespace {
  57
  58 //////////////////////////////////////////////////////////////////////
  59
  60 const StaticString s_Closure("Closure");
  61 const StaticString s_toString("__toString");
  62 const StaticString s_Stringish("Stringish");
  63 const StaticString s_XHPChild("XHPChild");
  64 const StaticString s_attr_Deprecated("__Deprecated");
  65 const StaticString s___NoContextSensitiveAnalysis(
  66     "__NoContextSensitiveAnalysis");
  67
  68 //////////////////////////////////////////////////////////////////////
  69
  70 struct ParseUnitState {
  71   std::atomic<uint32_t>& nextFuncId;
  72
  73   /*
  74    * This is computed once for each unit and stashed here.  We support
  75    * having either a SourceLocTable or a LineTable.  If we're
  76    * optimizing a repo that was already created by hphpc, it won't
  77    * have the full SourceLocTable information in it, so we're limited
  78    * to line numbers.
  79    */
  80   boost::variant< SourceLocTable
  81                 , LineTable
  82                 > srcLocInfo;
  83
  84   /*
  85    * Map from class id to the function containing its DefCls
  86    * instruction.  We use this to compute whether classes are defined
  87    * at top-level.
  88    *
  89    * TODO_4: if we don't end up with a use for this, remove it.
  90    */
  91   std::vector<php::Func*> defClsMap;
  92
  93   /*
  94    * Map from Closure index to the function(s) containing their
  95    * associated CreateCl opcode(s).
  96    */
  97   hphp_fast_map<
  98     int32_t,
  99     hphp_fast_set<php::Func*>
 100   > createClMap;
 101
 102   struct SrcLocHash {
 103     size_t operator()(const php::SrcLoc& sl) const {
 104       auto const h1 = ((size_t)sl.start.col << 32) | sl.start.line;
 105       auto const h2 = ((size_t)sl.past.col << 32) | sl.past.line;
 106       return hash_int64_pair(h1, h2);
 107     }
 108   };
 109   hphp_fast_map<php::SrcLoc, int32_t, SrcLocHash> srcLocs;
 110
 111   /*
 112    * Set of functions that should be processed in the constant
 113    * propagation pass.
 114    *
 115    * Must include every function with a DefCns for correctness; cinit,
 116    * pinit and sinit functions are added to improve overall
 117    * performance.
 118    */
 119   hphp_fast_set<php::Func*> constPassFuncs;
 120
 121 };
 122
 123 //////////////////////////////////////////////////////////////////////
 124
 125 std::set<Offset> findBasicBlocks(const FuncEmitter& fe) {
 126   std::set<Offset> blockStarts;
 127   auto markBlock = [&] (Offset off) { blockStarts.insert(off); };
 128
 129   // Each entry point for a DV funclet is the start of a basic
 130   // block.
 131   for (auto& param : fe.params) {
 132     if (param.hasDefaultValue()) markBlock(param.funcletOff);
 133   }
 134
 135   // The main entry point is also a basic block start.
 136   markBlock(fe.base);
 137
 138   bool traceBc = false;
 139
 140   /*
 141    * For each instruction, add it to the set if it must be the start
 142    * of a block.  It is the start of a block if it is:
 143    *
 144    *   - A jump target
 145    *
 146    *   - Immediatelly following a control flow instruction, other than
 147    *     a call.
 148    */
 149   auto offset = fe.base;
 150   for (;;) {
 151     auto const bc = fe.ue().bc();
 152     auto const pc = bc + offset;
 153     auto const nextOff = offset + instrLen(pc);
 154     auto const atLast = nextOff == fe.past;
 155     auto const op = peek_op(pc);
 156     auto const breaksBB =
 157       instrIsNonCallControlFlow(op) ||
 158       instrFlags(op) & TF ||
 159       (isFCall(op) && !instrJumpOffsets(pc).empty());
 160
 161     if (options.TraceBytecodes.count(op)) traceBc = true;
 162
 163     if (breaksBB && !atLast) {
 164       markBlock(nextOff);
 165     }
 166
 167     auto const targets = instrJumpTargets(bc, offset);
 168     for (auto const& target : targets) markBlock(target);
 169
 170     offset = nextOff;
 171     if (atLast) break;
 172   }
 173
 174   /*
 175    * Find blocks associated with exception handlers.
 176    *
 177    *   - The start of each EH protected region begins a block.
 178    *
 179    *   - The instruction immediately after the end of any
 180    *     EH protected region begins a block.
 181    *
 182    *   - Each catch entry point begins a block.
 183    *
 184    *   - The instruction immediately after the end of any
 185    *     catch region begins a block.
 186    */
 187   for (auto& eh : fe.ehtab) {
 188     markBlock(eh.m_base);
 189     markBlock(eh.m_past);
 190     markBlock(eh.m_handler);
 191     if (eh.m_end != kInvalidOffset) {
 192       markBlock(eh.m_end);
 193     }
 194   }
 195
 196   // Now, each interval in blockStarts delinates a basic block.
 197   blockStarts.insert(fe.past);
 198
 199   if (traceBc) {
 200     FTRACE(0, "TraceBytecode (parse): {}::{} in {}\n",
 201            fe.pce() ? fe.pce()->name()->data() : "",
 202            fe.name, fe.ue().m_filepath);
 203   }
 204
 205   return blockStarts;
 206 }
 207
 208 struct ExnTreeInfo {
 209   /*
 210    * Map from EHEnt to the ExnNode that will represent exception
 211    * behavior in that region.
 212    */
 213   hphp_fast_map<const EHEnt*,ExnNodeId> ehMap;
 214 };
 215
 216 template<class FindBlock>
 217 ExnTreeInfo build_exn_tree(const FuncEmitter& fe,
 218                            php::Func& func,
 219                            FindBlock findBlock) {
 220   ExnTreeInfo ret;
 221   func.exnNodes.reserve(fe.ehtab.size());
 222   for (auto& eh : fe.ehtab) {
 223     auto const catchBlk = findBlock(eh.m_handler, true);
 224     auto node = php::ExnNode{};
 225     node.idx = func.exnNodes.size();
 226     node.parent = NoExnNodeId;
 227     node.depth = 1; // 0 depth means no ExnNode
 228     node.region = php::CatchRegion { catchBlk, eh.m_iterId };
 229     ret.ehMap[&eh] = node.idx;
 230
 231     if (eh.m_parentIndex != -1) {
 232       auto it = ret.ehMap.find(&fe.ehtab[eh.m_parentIndex]);
 233       assert(it != end(ret.ehMap));
 234       assert(it->second < node.idx);
 235       node.parent = it->second;
 236       auto& parent = func.exnNodes[node.parent];
 237       node.depth = parent.depth + 1;
 238       parent.children.emplace_back(node.idx);
 239     }
 240     func.exnNodes.emplace_back(std::move(node));
 241   }
 242
 243   return ret;
 244 }
 245
 246 template<class T> T decode(PC& pc) {
 247   auto const ret = *reinterpret_cast<const T*>(pc);
 248   pc += sizeof ret;
 249   return ret;
 250 }
 251
 252 template<class T> void decode(PC& pc, T& val) {
 253   val = decode<T>(pc);
 254 }
 255
 256 MKey make_mkey(const php::Func& /*func*/, MemberKey mk) {
 257   switch (mk.mcode) {
 258     case MEL: case MPL:
 259       return MKey{mk.mcode, mk.local};
 260     case MEC: case MPC:
 261       return MKey{mk.mcode, mk.iva};
 262     case MET: case MPT: case MQT:
 263       return MKey{mk.mcode, mk.litstr};
 264     case MEI:
 265       return MKey{mk.mcode, mk.int64};
 266     case MW:
 267       return MKey{};
 268   }
 269   not_reached();
 270 }
 271
 272 template<class FindBlock>
 273 void populate_block(ParseUnitState& puState,
 274                     const FuncEmitter& fe,
 275                     php::Func& func,
 276                     php::Block& blk,
 277                     PC pc,
 278                     PC const past,
 279                     FindBlock findBlock) {
 280   auto const& ue = fe.ue();
 281
 282   auto decode_stringvec = [&] {
 283     auto const vecLen = decode_iva(pc);
 284     CompactVector<LSString> keys;
 285     for (auto i = size_t{0}; i < vecLen; ++i) {
 286       keys.push_back(ue.lookupLitstr(decode<int32_t>(pc)));
 287     }
 288     return keys;
 289   };
 290
 291   auto decode_switch = [&] (PC opPC) {
 292     SwitchTab ret;
 293     auto const vecLen = decode_iva(pc);
 294     for (int32_t i = 0; i < vecLen; ++i) {
 295       ret.push_back(findBlock(
 296         opPC + decode<Offset>(pc) - ue.bc()
 297       ));
 298     }
 299     return ret;
 300   };
 301
 302   auto decode_sswitch = [&] (PC opPC) {
 303     SSwitchTab ret;
 304
 305     auto const vecLen = decode_iva(pc);
 306     for (int32_t i = 0; i < vecLen - 1; ++i) {
 307       auto const id = decode<Id>(pc);
 308       auto const offset = decode<Offset>(pc);
 309       ret.emplace_back(ue.lookupLitstr(id),
 310                        findBlock(opPC + offset - ue.bc()));
 311     }
 312
 313     // Final case is the default, and must have a litstr id of -1.
 314     DEBUG_ONLY auto const defId = decode<Id>(pc);
 315     auto const defOff = decode<Offset>(pc);
 316     assert(defId == -1);
 317     ret.emplace_back(nullptr, findBlock(opPC + defOff - ue.bc()));
 318     return ret;
 319   };
 320
 321   auto defcns = [&] () {
 322     puState.constPassFuncs.insert(&func);
 323   };
 324   auto defcls = [&] (const Bytecode& b) {
 325     puState.defClsMap[b.DefCls.arg1] = &func;
 326   };
 327   auto defclsnop = [&] (const Bytecode& b) {
 328     puState.defClsMap[b.DefClsNop.arg1] = &func;
 329   };
 330   auto createcl = [&] (const Bytecode& b) {
 331     puState.createClMap[b.CreateCl.arg2].insert(&func);
 332   };
 333
 334 #define IMM_BLA(n)     auto targets = decode_switch(opPC);
 335 #define IMM_SLA(n)     auto targets = decode_sswitch(opPC);
 336 #define IMM_IVA(n)     auto arg##n = decode_iva(pc);
 337 #define IMM_I64A(n)    auto arg##n = decode<int64_t>(pc);
 338 #define IMM_LA(n)      auto loc##n = [&] {                       \
 339                          LocalId id = decode_iva(pc);            \
 340                          always_assert(id < func.locals.size()); \
 341                          return id;                              \
 342                        }();
 343 #define IMM_NLA(n)     auto nloc##n = [&] {                         \
 344                          NamedLocal loc = decode_named_local(pc);   \
 345                          always_assert(loc.id < func.locals.size());\
 346                          return loc;                                \
 347                        }();
 348 #define IMM_ILA(n)     auto loc##n = [&] {                       \
 349                          LocalId id = decode_iva(pc);            \
 350                          always_assert(id < func.locals.size()); \
 351                          return id;                              \
 352                        }();
 353 #define IMM_IA(n)      auto iter##n = [&] {                      \
 354                          IterId id = decode_iva(pc);             \
 355                          always_assert(id < func.numIters);      \
 356                          return id;                              \
 357                        }();
 358 #define IMM_DA(n)      auto dbl##n = decode<double>(pc);
 359 #define IMM_SA(n)      auto str##n = ue.lookupLitstr(decode<Id>(pc));
 360 #define IMM_RATA(n)    auto rat = decodeRAT(ue, pc);
 361 #define IMM_AA(n)      auto arr##n = ue.lookupArray(decode<Id>(pc));
 362 #define IMM_BA(n)      assert(next == past);     \
 363                        auto target##n = findBlock(  \
 364                          opPC + decode<Offset>(pc) - ue.bc());
 365 #define IMM_OA_IMPL(n) subop##n; decode(pc, subop##n);
 366 #define IMM_OA(type)   type IMM_OA_IMPL
 367 #define IMM_VSA(n)     auto keys = decode_stringvec();
 368 #define IMM_KA(n)      auto mkey = make_mkey(func, decode_member_key(pc, &ue));
 369 #define IMM_LAR(n)     auto locrange = [&] {                             \
 370                          auto const range = decodeLocalRange(pc);        \
 371                          always_assert(range.first + range.count         \
 372                                        <= func.locals.size());           \
 373                          return LocalRange { range.first, range.count }; \
 374                        }();
 375 #define IMM_ITA(n)     auto ita = decodeIterArgs(pc);
 376 #define IMM_FCA(n)     auto fca = [&] {                                      \
 377                          auto const fca = decodeFCallArgs(op, pc, &ue);      \
 378                          auto const numBytes = (fca.numArgs + 7) / 8;        \
 379                          auto inoutArgs = fca.enforceInOut()                 \
 380                            ? std::make_unique<uint8_t[]>(numBytes)           \
 381                            : nullptr;                                        \
 382                          if (inoutArgs) {                                    \
 383                            memcpy(inoutArgs.get(), fca.inoutArgs, numBytes); \
 384                          }                                                   \
 385                          auto const aeOffset = fca.asyncEagerOffset;         \
 386                          auto const aeTarget = aeOffset != kInvalidOffset    \
 387                            ? findBlock(opPC + aeOffset - ue.bc())            \
 388                            : NoBlockId;                                      \
 389                          assertx(aeTarget == NoBlockId || next == past);     \
 390                          return FCallArgs(fca.flags, fca.numArgs,            \
 391                                           fca.numRets, std::move(inoutArgs), \
 392                                           aeTarget, fca.lockWhileUnwinding,  \
 393                                           fca.skipNumArgsCheck, fca.context);\
 394                        }();
 395
 396 #define IMM_NA
 397 #define IMM_ONE(x)                IMM_##x(1)
 398 #define IMM_TWO(x, y)             IMM_##x(1) IMM_##y(2)
 399 #define IMM_THREE(x, y, z)        IMM_TWO(x, y) IMM_##z(3)
 400 #define IMM_FOUR(x, y, z, n)      IMM_THREE(x, y, z) IMM_##n(4)
 401 #define IMM_FIVE(x, y, z, n, m)   IMM_FOUR(x, y, z, n) IMM_##m(5)
 402 #define IMM_SIX(x, y, z, n, m, o) IMM_FIVE(x, y, z, n, m) IMM_##o(6)
 403
 404 #define IMM_ARG(which, n)         IMM_NAME_##which(n)
 405 #define IMM_ARG_NA
 406 #define IMM_ARG_ONE(x)                IMM_ARG(x, 1)
 407 #define IMM_ARG_TWO(x, y)             IMM_ARG(x, 1), IMM_ARG(y, 2)
 408 #define IMM_ARG_THREE(x, y, z)        IMM_ARG(x, 1), IMM_ARG(y, 2), \
 409                                       IMM_ARG(z, 3)
 410 #define IMM_ARG_FOUR(x, y, z, l)      IMM_ARG(x, 1), IMM_ARG(y, 2), \
 411                                       IMM_ARG(z, 3), IMM_ARG(l, 4)
 412 #define IMM_ARG_FIVE(x, y, z, l, m)   IMM_ARG(x, 1), IMM_ARG(y, 2), \
 413                                       IMM_ARG(z, 3), IMM_ARG(l, 4), \
 414                                       IMM_ARG(m, 5)
 415 #define IMM_ARG_SIX(x, y, z, l, m, n) IMM_ARG(x, 1), IMM_ARG(y, 2), \
 416                                       IMM_ARG(z, 3), IMM_ARG(l, 4), \
 417                                       IMM_ARG(m, 5), IMM_ARG(n, 6)
 418
 419 #define FLAGS_NF
 420 #define FLAGS_TF
 421 #define FLAGS_CF
 422 #define FLAGS_FF
 423 #define FLAGS_CF_TF
 424 #define FLAGS_CF_FF
 425
 426 #define FLAGS_ARG_NF
 427 #define FLAGS_ARG_TF
 428 #define FLAGS_ARG_CF
 429 #define FLAGS_ARG_FF
 430 #define FLAGS_ARG_CF_TF
 431 #define FLAGS_ARG_CF_FF
 432
 433 #define O(opcode, imms, inputs, outputs, flags)                    \
 434   case Op::opcode:                                                 \
 435     {                                                              \
 436       auto b = [&] () -> Bytecode {                                \
 437         IMM_##imms /*these two macros advance the pc as required*/ \
 438         FLAGS_##flags                                              \
 439         if (isTypeAssert(op)) return bc::Nop {};                   \
 440         return bc::opcode { IMM_ARG_##imms FLAGS_ARG_##flags };    \
 441       }();                                                         \
 442       b.srcLoc = srcLocIx;                                         \
 443       if (Op::opcode == Op::DefCns)      defcns();                 \
 444       if (Op::opcode == Op::DefCls)      defcls(b);                \
 445       if (Op::opcode == Op::DefClsNop)   defclsnop(b);             \
 446       if (Op::opcode == Op::CreateCl)    createcl(b);              \
 447       blk.hhbcs.push_back(std::move(b));                           \
 448       assert(pc == next);                                          \
 449     }                                                              \
 450     break;
 451
 452   assert(pc != past);
 453   do {
 454     auto const opPC = pc;
 455     auto const next = pc + instrLen(opPC);
 456     assert(next <= past);
 457
 458     auto const srcLoc = match<php::SrcLoc>(
 459       puState.srcLocInfo,
 460       [&] (const SourceLocTable& tab) {
 461         SourceLoc sloc;
 462         if (getSourceLoc(tab, opPC - ue.bc(), sloc)) {
 463           return php::SrcLoc {
 464             { static_cast<uint32_t>(sloc.line0),
 465               static_cast<uint32_t>(sloc.char0) },
 466             { static_cast<uint32_t>(sloc.line1),
 467               static_cast<uint32_t>(sloc.char1) }
 468           };
 469         }
 470         return php::SrcLoc{};
 471       },
 472       [&] (const LineTable& tab) {
 473         auto const line = getLineNumber(tab, opPC - ue.bc());
 474         if (line != -1) {
 475           return php::SrcLoc {
 476             { static_cast<uint32_t>(line), 0 },
 477             { static_cast<uint32_t>(line), 0 },
 478           };
 479         };
 480         return php::SrcLoc{};
 481       }
 482     );
 483
 484     auto const srcLocIx = puState.srcLocs.emplace(
 485       srcLoc, puState.srcLocs.size()).first->second;
 486
 487     auto op = decode_op(pc);
 488     switch (op) { OPCODES }
 489
 490     if (next == past) {
 491       if (instrAllowsFallThru(op)) {
 492         blk.fallthrough = findBlock(next - ue.bc());
 493       }
 494     }
 495
 496     pc = next;
 497   } while (pc != past);
 498
 499 #undef O
 500
 501 #undef FLAGS_NF
 502 #undef FLAGS_TF
 503 #undef FLAGS_CF
 504 #undef FLAGS_FF
 505 #undef FLAGS_CF_TF
 506 #undef FLAGS_CF_FF
 507
 508 #undef FLAGS_ARG_NF
 509 #undef FLAGS_ARG_TF
 510 #undef FLAGS_ARG_CF
 511 #undef FLAGS_ARG_FF
 512 #undef FLAGS_ARG_CF_TF
 513 #undef FLAGS_ARG_CF_FF
 514
 515 #undef IMM_BLA
 516 #undef IMM_SLA
 517 #undef IMM_IVA
 518 #undef IMM_I64A
 519 #undef IMM_LA
 520 #undef IMM_NLA
 521 #undef IMM_ILA
 522 #undef IMM_IA
 523 #undef IMM_DA
 524 #undef IMM_SA
 525 #undef IMM_RATA
 526 #undef IMM_AA
 527 #undef IMM_BA
 528 #undef IMM_OA_IMPL
 529 #undef IMM_OA
 530 #undef IMM_VSA
 531 #undef IMM_LAR
 532 #undef IMM_ITA
 533 #undef IMM_FCA
 534
 535 #undef IMM_NA
 536 #undef IMM_ONE
 537 #undef IMM_TWO
 538 #undef IMM_THREE
 539 #undef IMM_FOUR
 540 #undef IMM_FIVE
 541
 542 #undef IMM_ARG
 543 #undef IMM_ARG_NA
 544 #undef IMM_ARG_ONE
 545 #undef IMM_ARG_TWO
 546 #undef IMM_ARG_THREE
 547 #undef IMM_ARG_FOUR
 548 #undef IMM_ARG_FIVE
 549 #undef IMM_ARG_SIX
 550
 551   /*
 552    * If a block ends with an unconditional jump, change it to a
 553    * fallthrough edge.
 554    *
 555    * If the jmp is the only instruction, convert it to a Nop, to avoid
 556    * creating an empty block (we have an invariant that no blocks are
 557    * empty).
 558    */
 559
 560   auto make_fallthrough = [&] {
 561     blk.fallthrough = blk.hhbcs.back().Jmp.target1;
 562     if (blk.hhbcs.size() == 1) {
 563       blk.hhbcs.back() = bc_with_loc(blk.hhbcs.back().srcLoc, bc::Nop{});
 564     } else {
 565       blk.hhbcs.pop_back();
 566     }
 567   };
 568
 569   switch (blk.hhbcs.back().op) {
 570   case Op::Jmp:   make_fallthrough();                           break;
 571   case Op::JmpNS: make_fallthrough(); blk.fallthroughNS = true; break;
 572   default:                                                      break;
 573   }
 574 }
 575
 576 template<class FindBlk>
 577 void link_entry_points(php::Func& func,
 578                        const FuncEmitter& fe,
 579                        FindBlk findBlock) {
 580   func.dvEntries.resize(fe.params.size(), NoBlockId);
 581   for (size_t i = 0, sz = fe.params.size(); i < sz; ++i) {
 582     if (fe.params[i].hasDefaultValue()) {
 583       auto const dv = findBlock(fe.params[i].funcletOff);
 584       func.params[i].dvEntryPoint = dv;
 585       func.dvEntries[i] = dv;
 586     }
 587   }
 588   func.mainEntry = findBlock(fe.base);
 589 }
 590
 591 void build_cfg(ParseUnitState& puState,
 592                php::Func& func,
 593                const FuncEmitter& fe) {
 594   auto const blockStarts = findBasicBlocks(fe);
 595
 596   FTRACE(3, "    blocks are at: {}\n",
 597     [&]() -> std::string {
 598       using namespace folly::gen;
 599       return from(blockStarts)
 600         | eachTo<std::string>()
 601         | unsplit<std::string>(" ");
 602     }()
 603   );
 604
 605   std::map<Offset,std::pair<BlockId, copy_ptr<php::Block>>> blockMap;
 606   auto const bc = fe.ue().bc();
 607
 608   auto findBlock = [&] (Offset off, bool catchEntry = false) {
 609     auto& ent = blockMap[off];
 610     if (!ent.second) {
 611       auto blk         = php::Block{};
 612       ent.first        = blockMap.size() - 1;
 613       blk.exnNodeId    = NoExnNodeId;
 614       blk.catchEntry   = catchEntry;
 615       ent.second.emplace(std::move(blk));
 616     } else if (catchEntry) {
 617       ent.second.mutate()->catchEntry = true;
 618     }
 619     return ent.first;
 620   };
 621
 622   auto exnTreeInfo = build_exn_tree(fe, func, findBlock);
 623
 624   hphp_fast_map<BlockId, std::pair<int, int>> predSuccCounts;
 625
 626   for (auto it = begin(blockStarts);
 627        std::next(it) != end(blockStarts);
 628        ++it) {
 629     auto const bid     = findBlock(*it);
 630     auto const block   = blockMap[*it].second.mutate();
 631     auto const bcStart = bc + *it;
 632     auto const bcStop  = bc + *std::next(it);
 633
 634     if (auto const eh = Func::findEH(fe.ehtab, *it)) {
 635       auto it = exnTreeInfo.ehMap.find(eh);
 636       assert(it != end(exnTreeInfo.ehMap));
 637       block->exnNodeId = it->second;
 638       block->throwExit = func.exnNodes[it->second].region.catchEntry;
 639     }
 640
 641     populate_block(puState, fe, func, *block, bcStart, bcStop, findBlock);
 642     forEachNonThrowSuccessor(*block, [&] (BlockId blkId) {
 643         predSuccCounts[blkId].first++;
 644         predSuccCounts[bid].second++;
 645     });
 646   }
 647
 648   link_entry_points(func, fe, findBlock);
 649
 650   func.blocks.resize(blockMap.size());
 651   for (auto& kv : blockMap) {
 652     auto const blk = kv.second.second.mutate();
 653     auto const id = kv.second.first;
 654     blk->multiSucc = predSuccCounts[id].second > 1;
 655     blk->multiPred = predSuccCounts[id].first > 1;
 656     func.blocks[id] = std::move(kv.second.second);
 657   }
 658 }
 659
 660 void add_frame_variables(php::Func& func, const FuncEmitter& fe) {
 661   for (auto& param : fe.params) {
 662     func.params.push_back(
 663       php::Param {
 664         param.defaultValue,
 665         NoBlockId,
 666         param.typeConstraint,
 667         param.userType,
 668         param.upperBounds,
 669         param.phpCode,
 670         param.userAttributes,
 671         param.builtinType,
 672         param.isInOut(),
 673         param.isVariadic()
 674       }
 675     );
 676   }
 677
 678   func.locals.reserve(fe.numLocals());
 679   for (LocalId id = 0; id < fe.numLocals(); ++id) {
 680     func.locals.push_back({
 681       .name = nullptr,
 682       .id = id,
 683       .killed = false,
 684       .nameId = id,
 685       .unusedName = false
 686     });
 687   }
 688   for (auto& kv : fe.localNameMap()) {
 689     func.locals[kv.second].name = kv.first;
 690   }
 691
 692   func.numIters = fe.numIterators();
 693 }
 694
 695 std::unique_ptr<php::Func> parse_func(ParseUnitState& puState,
 696                                       php::Unit* unit,
 697                                       php::Class* cls,
 698                                       const FuncEmitter& fe) {
 699   FTRACE(2, "  func: {}\n",
 700     fe.name->data() && *fe.name->data() ? fe.name->data() : "pseudomain");
 701
 702   auto ret         = std::make_unique<php::Func>();
 703   ret->idx         = puState.nextFuncId.fetch_add(1, std::memory_order_relaxed);
 704   ret->name        = fe.name;
 705   ret->srcInfo     = php::SrcInfo { fe.getLocation(),
 706                                     fe.docComment };
 707   ret->unit        = unit;
 708   ret->cls         = cls;
 709
 710   ret->attrs              = static_cast<Attr>(fe.attrs & ~AttrNoOverride);
 711   ret->userAttributes     = fe.userAttributes;
 712   ret->returnUserType     = fe.retUserType;
 713   ret->retTypeConstraint  = fe.retTypeConstraint;
 714   ret->hasParamsWithMultiUBs = fe.hasParamsWithMultiUBs;
 715   ret->hasReturnWithMultiUBs = fe.hasReturnWithMultiUBs;
 716   ret->returnUBs          = fe.retUpperBounds;
 717   ret->originalFilename   = fe.originalFilename;
 718
 719   ret->top                 = fe.top;
 720   ret->isClosureBody       = fe.isClosureBody;
 721   ret->isAsync             = fe.isAsync;
 722   ret->isGenerator         = fe.isGenerator;
 723   ret->isPairGenerator     = fe.isPairGenerator;
 724   ret->isMemoizeWrapper    = fe.isMemoizeWrapper;
 725   ret->isMemoizeWrapperLSB = fe.isMemoizeWrapperLSB;
 726   ret->isMemoizeImpl       = Func::isMemoizeImplName(fe.name);
 727   ret->isReified           = fe.userAttributes.find(s___Reified.get()) !=
 728                              fe.userAttributes.end();
 729   ret->isRxDisabled        = fe.isRxDisabled;
 730   ret->noContextSensitiveAnalysis = fe.userAttributes.find(
 731     s___NoContextSensitiveAnalysis.get()) != fe.userAttributes.end();
 732   ret->hasInOutArgs        = [&] {
 733     for (auto& a : fe.params) if (a.isInOut()) return true;
 734     return false;
 735   }();
 736
 737   add_frame_variables(*ret, fe);
 738
 739   if (!RuntimeOption::ConstantFunctions.empty()) {
 740     auto const name = [&] {
 741       if (!cls) return fe.name->toCppString();
 742       return folly::sformat("{}::{}", cls->name, ret->name);
 743     }();
 744     auto const it = RuntimeOption::ConstantFunctions.find(name);
 745     if (it != RuntimeOption::ConstantFunctions.end()) {
 746       ret->locals.resize(fe.params.size());
 747       ret->numIters = 0;
 748       ret->attrs |= AttrIsFoldable;
 749
 750       auto const mainEntry = BlockId{0};
 751
 752       auto blk         = php::Block{};
 753       blk.exnNodeId    = NoExnNodeId;
 754
 755       blk.hhbcs.push_back(gen_constant(it->second));
 756       blk.hhbcs.push_back(bc::RetC {});
 757       ret->blocks.emplace_back(std::move(blk));
 758
 759       ret->dvEntries.resize(fe.params.size(), NoBlockId);
 760       ret->mainEntry = mainEntry;
 761
 762       for (size_t i = 0, sz = fe.params.size(); i < sz; ++i) {
 763         if (fe.params[i].hasDefaultValue()) {
 764           ret->params[i].dvEntryPoint = mainEntry;
 765           ret->dvEntries[i] = mainEntry;
 766         }
 767       }
 768       return ret;
 769     }
 770   }
 771
 772   /*
 773    * Builtin functions get some extra information.  The returnType flag is only
 774    * non-folly::none for these, but note that something may be a builtin and
 775    * still have a folly::none return type.
 776    */
 777   if (fe.isNative) {
 778     auto const f = [&] () -> HPHP::Func* {
 779       if (ret->cls) {
 780         auto const cls = Unit::lookupClass(ret->cls->name);
 781         return cls ? cls->lookupMethod(ret->name) : nullptr;
 782       } else {
 783         return Unit::lookupBuiltin(ret->name);
 784       }
 785     }();
 786
 787     ret->nativeInfo                   = std::make_unique<php::NativeInfo>();
 788     ret->nativeInfo->returnType       = fe.hniReturnType;
 789     if (f && ret->params.size()) {
 790       for (auto i = 0; i < ret->params.size(); i++) {
 791         auto& pi = ret->params[i];
 792         if (pi.isVariadic || !f->params()[i].hasDefaultValue()) continue;
 793         if (pi.defaultValue.m_type == KindOfUninit &&
 794             pi.phpCode != nullptr) {
 795           auto res = eval_cell_value([&] {
 796               auto val = f_constant(StrNR(pi.phpCode));
 797               val.setEvalScalar();
 798               return *val.asTypedValue();
 799             });
 800           if (!res) {
 801             FTRACE(4, "Argument {} to {}: Failed to evaluate {}\n",
 802                    i, f->fullName(), pi.phpCode);
 803             continue;
 804           }
 805           pi.defaultValue = *res;
 806         }
 807       }
 808     }
 809     if (!f || !f->nativeFuncPtr() ||
 810         (f->userAttributes().count(
 811           LowStringPtr(s_attr_Deprecated.get())))) {
 812       ret->attrs |= AttrNoFCallBuiltin;
 813     }
 814   }
 815
 816   build_cfg(puState, *ret, fe);
 817
 818   return ret;
 819 }
 820
 821 void parse_methods(ParseUnitState& puState,
 822                    php::Class* ret,
 823                    php::Unit* unit,
 824                    const PreClassEmitter& pce) {
 825   std::unique_ptr<php::Func> cinit;
 826   for (auto& me : pce.methods()) {
 827     auto f = parse_func(puState, unit, ret, *me);
 828     if (f->name == s_86cinit.get()) {
 829       puState.constPassFuncs.insert(f.get());
 830       cinit = std::move(f);
 831     } else {
 832       if (f->name == s_86pinit.get() ||
 833           f->name == s_86sinit.get() ||
 834           f->name == s_86linit.get()) {
 835         puState.constPassFuncs.insert(f.get());
 836       }
 837       ret->methods.push_back(std::move(f));
 838     }
 839   }
 840   if (cinit) ret->methods.push_back(std::move(cinit));
 841 }
 842
 843 void add_stringish(php::Class* cls) {
 844   // The runtime adds Stringish to any class providing a __toString() function,
 845   // so we mirror that here to make sure analysis of interfaces is correct.
 846   // All Stringish are also XHPChild, so handle it here as well.
 847   if (cls->attrs & AttrInterface && cls->name->isame(s_Stringish.get())) {
 848     return;
 849   }
 850
 851   bool hasXHP = false;
 852   for (auto& iface : cls->interfaceNames) {
 853     if (iface->isame(s_Stringish.get())) return;
 854     if (iface->isame(s_XHPChild.get())) { hasXHP = true; }
 855   }
 856
 857   for (auto& func : cls->methods) {
 858     if (func->name->isame(s_toString.get())) {
 859       FTRACE(2, "Adding Stringish and XHPChild to {}\n", cls->name->data());
 860       cls->interfaceNames.push_back(s_Stringish.get());
 861       if (!hasXHP && !cls->name->isame(s_XHPChild.get())) {
 862         cls->interfaceNames.push_back(s_XHPChild.get());
 863       }
 864       return;
 865     }
 866   }
 867 }
 868
 869 std::unique_ptr<php::Record> parse_record(php::Unit* unit,
 870                                           const RecordEmitter& re) {
 871   FTRACE(2, "  record: {}\n", re.name()->data());
 872
 873   auto ret                = std::make_unique<php::Record>();
 874   ret->unit               = unit;
 875   ret->srcInfo            = php::SrcInfo {re.getLocation(), re.docComment()};
 876   ret->name               = re.name();
 877   ret->attrs              = static_cast<Attr>(re.attrs() & ~AttrNoOverride);
 878   ret->parentName         = re.parentName()->empty()? nullptr: re.parentName();
 879   ret->id                 = re.id();
 880   ret->userAttributes     = re.userAttributes();
 881
 882   auto& fieldMap = re.fieldMap();
 883   for (size_t idx = 0; idx < fieldMap.size(); ++idx) {
 884     auto& field = fieldMap[idx];
 885     ret->fields.push_back(
 886       php::RecordField {
 887         field.name(),
 888         field.attrs(),
 889         field.userType(),
 890         field.docComment(),
 891         field.val(),
 892         field.typeConstraint(),
 893         field.userAttributes()
 894       }
 895     );
 896   }
 897   return ret;
 898 }
 899
 900 std::unique_ptr<php::Class> parse_class(ParseUnitState& puState,
 901                                         php::Unit* unit,
 902                                         const PreClassEmitter& pce) {
 903   FTRACE(2, "  class: {}\n", pce.name()->data());
 904
 905   auto ret                = std::make_unique<php::Class>();
 906   ret->name               = pce.name();
 907   ret->srcInfo            = php::SrcInfo { pce.getLocation(),
 908                                            pce.docComment() };
 909   ret->unit               = unit;
 910   ret->closureContextCls  = nullptr;
 911   ret->parentName         = pce.parentName()->empty() ? nullptr
 912                                                       : pce.parentName();
 913   ret->attrs              = static_cast<Attr>(pce.attrs() & ~AttrNoOverride);
 914   ret->hoistability       = pce.hoistability();
 915   ret->userAttributes     = pce.userAttributes();
 916   ret->id                 = pce.id();
 917   ret->hasReifiedGenerics = ret->userAttributes.find(s___Reified.get()) !=
 918                             ret->userAttributes.end();
 919   ret->hasConstProp       = false;
 920
 921   for (auto& iface : pce.interfaces()) {
 922     ret->interfaceNames.push_back(iface);
 923   }
 924
 925   copy(ret->usedTraitNames,  pce.usedTraits());
 926   copy(ret->traitPrecRules,  pce.traitPrecRules());
 927   copy(ret->traitAliasRules, pce.traitAliasRules());
 928   copy(ret->requirements,    pce.requirements());
 929
 930   parse_methods(puState, ret.get(), unit, pce);
 931   add_stringish(ret.get());
 932
 933   auto& propMap = pce.propMap();
 934   for (size_t idx = 0; idx < propMap.size(); ++idx) {
 935     auto& prop = propMap[idx];
 936     ret->properties.push_back(
 937       php::Prop {
 938         prop.name(),
 939         prop.attrs(),
 940         prop.userAttributes(),
 941         prop.docComment(),
 942         prop.userType(),
 943         prop.typeConstraint(),
 944         prop.val()
 945       }
 946     );
 947     if ((prop.attrs() & (AttrStatic | AttrIsConst)) == AttrIsConst) {
 948       ret->hasConstProp = true;
 949     }
 950   }
 951
 952   auto& constMap = pce.constMap();
 953   for (size_t idx = 0; idx < constMap.size(); ++idx) {
 954     auto& cconst = constMap[idx];
 955     // Set all constants as NoOverride, we'll clear this while building
 956     // the index
 957     ret->constants.push_back(
 958       php::Const {
 959         cconst.name(),
 960         ret.get(),
 961         cconst.valOption(),
 962         cconst.phpCode(),
 963         cconst.typeConstraint(),
 964         cconst.isTypeconst(),
 965         true // NoOverride
 966       }
 967     );
 968   }
 969
 970   if (ret->attrs & AttrBuiltin) {
 971     if (auto nativeConsts = Native::getClassConstants(ret->name)) {
 972       for (auto const& cnsMap : *nativeConsts) {
 973         TypedValueAux tvaux;
 974         tvCopy(cnsMap.second, tvaux);
 975         tvaux.constModifiers() = {};
 976         ret->constants.push_back(
 977           php::Const {
 978             cnsMap.first,
 979             ret.get(),
 980             tvaux,
 981             staticEmptyString(),
 982             staticEmptyString(),
 983             false
 984           }
 985         );
 986       }
 987     }
 988   }
 989
 990   ret->enumBaseTy = pce.enumBaseTy();
 991
 992   return ret;
 993 }
 994
 995 //////////////////////////////////////////////////////////////////////
 996
 997 void assign_closure_context(const ParseUnitState&, php::Class*);
 998
 999 php::Class*
1000 find_closure_context(const ParseUnitState& puState,
1001                      php::Func* createClFunc) {
1002   if (auto const cls = createClFunc->cls) {
1003     if (cls->parentName &&
1004         cls->parentName->isame(s_Closure.get())) {
1005       // We have a closure created by a closure's invoke method, which
1006       // means it should inherit the outer closure's context, so we
1007       // have to know that first.
1008       assign_closure_context(puState, cls);
1009       return cls->closureContextCls;
1010     }
1011     return cls;
1012   }
1013   return nullptr;
1014 }
1015
1016 void assign_closure_context(const ParseUnitState& puState,
1017                             php::Class* clo) {
1018   if (clo->closureContextCls) return;
1019
1020   auto clIt = puState.createClMap.find(clo->id);
1021   if (clIt == end(puState.createClMap)) {
1022     // Unused closure class.  Technically not prohibited by the spec.
1023     return;
1024   }
1025
1026   /*
1027    * Any route to the closure context must yield the same class, or
1028    * things downstream won't understand.  We try every route and
1029    * assert they are all the same here.
1030    *
1031    * See bytecode.specification for CreateCl for the relevant
1032    * invariants.
1033    */
1034   always_assert(!clIt->second.empty());
1035   auto it = begin(clIt->second);
1036   auto const representative = find_closure_context(puState, *it);
1037   if (debug) {
1038     for (++it; it != end(clIt->second); ++it) {
1039       assert(find_closure_context(puState, *it) == representative);
1040     }
1041   }
1042   clo->closureContextCls = representative;
1043 }
1044
1045 void find_additional_metadata(const ParseUnitState& puState,
1046                               php::Unit* unit) {
1047   for (auto& c : unit->classes) {
1048     if (!c->parentName || !c->parentName->isame(s_Closure.get())) {
1049       continue;
1050     }
1051     assign_closure_context(puState, c.get());
1052   }
1053 }
1054
1055 //////////////////////////////////////////////////////////////////////
1056
1057 }
1058
1059 void parse_unit(php::Program& prog, const UnitEmitter* uep) {
1060   Trace::Bump bumper{Trace::hhbbc_parse, kSystemLibBump, uep->isASystemLib()};
1061   FTRACE(2, "parse_unit {}\n", uep->m_filepath->data());
1062
1063   if (RuntimeOption::EvalAbortBuildOnVerifyError && !uep->check(false)) {
1064     fprintf(
1065       stderr,
1066       "The unoptimized unit for %s did not pass verification, "
1067       "bailing because Eval.AbortBuildOnVerifyError is set\n",
1068       uep->m_filepath->data()
1069     );
1070     _Exit(1);
1071   }
1072
1073   auto const& ue = *uep;
1074
1075   auto ret      = std::make_unique<php::Unit>();
1076   ret->filename = ue.m_filepath;
1077   ret->isHHFile = ue.m_isHHFile;
1078   ret->metaData = ue.m_metaData;
1079   ret->fileAttributes = ue.m_fileAttributes;
1080
1081   ParseUnitState puState{ prog.nextFuncId };
1082   if (ue.hasSourceLocInfo()) {
1083     puState.srcLocInfo = ue.createSourceLocTable();
1084   } else {
1085     puState.srcLocInfo = ue.lineTable();
1086   }
1087   puState.defClsMap.resize(ue.numPreClasses(), nullptr);
1088
1089   for (size_t i = 0; i < ue.numPreClasses(); ++i) {
1090     auto cls = parse_class(puState, ret.get(), *ue.pce(i));
1091     ret->classes.push_back(std::move(cls));
1092   }
1093
1094   for (size_t i = 0; i < ue.numRecords(); ++i) {
1095     auto rec = parse_record(ret.get(), *ue.re(i));
1096     ret->records.push_back(std::move(rec));
1097   }
1098
1099   for (auto& fe : ue.fevec()) {
1100     auto func = parse_func(puState, ret.get(), nullptr, *fe);
1101     assert(!fe->pce());
1102     if (fe->isPseudoMain()) {
1103       ret->pseudomain = std::move(func);
1104     } else {
1105       ret->funcs.push_back(std::move(func));
1106     }
1107   }
1108
1109   ret->srcLocs.resize(puState.srcLocs.size());
1110   for (auto& srcInfo : puState.srcLocs) {
1111     ret->srcLocs[srcInfo.second] = srcInfo.first;
1112   }
1113
1114   for (auto& ta : ue.typeAliases()) {
1115     ret->typeAliases.push_back(
1116       std::make_unique<php::TypeAlias>(ta)
1117     );
1118   }
1119
1120   for (auto& c : ue.constants()) {
1121     ret->constants.push_back(
1122       std::make_unique<Constant>(c)
1123     );
1124   }
1125
1126   find_additional_metadata(puState, ret.get());
1127
1128   assert(check(*ret));
1129
1130   std::lock_guard<std::mutex> _{prog.lock};
1131   for (auto const item : puState.constPassFuncs) {
1132     prog.constInits.push_back(item);
1133   }
1134   auto unitSn = prog.units.size();
1135   ret->sn = unitSn;
1136   ret->sha1 = SHA1 { unitSn };
1137   prog.units.push_back(std::move(ret));
1138 }
1139
1140 //////////////////////////////////////////////////////////////////////
1141
1142 }}