hphp/hhbbc/emit.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 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/emit.h"
  17
  18 #include <vector>
  19 #include <algorithm>
  20 #include <iterator>
  21 #include <map>
  22 #include <memory>
  23 #include <type_traits>
  24
  25 #include <folly/gen/Base.h>
  26 #include <folly/Conv.h>
  27 #include <folly/Optional.h>
  28 #include <folly/Memory.h>
  29
  30 #include "hphp/runtime/base/repo-auth-type.h"
  31 #include "hphp/runtime/base/repo-auth-type-array.h"
  32 #include "hphp/runtime/base/repo-auth-type-codec.h"
  33 #include "hphp/runtime/vm/bytecode.h"
  34 #include "hphp/runtime/vm/func-emitter.h"
  35 #include "hphp/runtime/vm/preclass-emitter.h"
  36 #include "hphp/runtime/vm/unit-emitter.h"
  37 #include "hphp/hhbbc/representation.h"
  38 #include "hphp/hhbbc/cfg.h"
  39 #include "hphp/hhbbc/unit-util.h"
  40 #include "hphp/hhbbc/class-util.h"
  41 #include "hphp/hhbbc/index.h"
  42
  43 namespace HPHP { namespace HHBBC {
  44
  45 TRACE_SET_MOD(hhbbc_emit);
  46
  47 namespace {
  48
  49 //////////////////////////////////////////////////////////////////////
  50
  51 const StaticString s_empty("");
  52
  53 //////////////////////////////////////////////////////////////////////
  54
  55 struct EmitUnitState {
  56   explicit EmitUnitState(const Index& index) : index(index) {}
  57
  58   /*
  59    * Access to the Index for this program.
  60    */
  61   const Index& index;
  62
  63   /*
  64    * While emitting bytecode, we keep track of where the DefCls
  65    * opcodes for each class are.  The PreClass runtime structures
  66    * require knowing these offsets.
  67    */
  68   std::vector<Offset> defClsMap;
  69 };
  70
  71 //////////////////////////////////////////////////////////////////////
  72
  73 /*
  74  * Order the blocks for bytecode emission.
  75  *
  76  * Rules about block order:
  77  *
  78  *   - The "primary function body" must come first.  This is all blocks
  79  *     that aren't part of a fault funclet.
  80  *
  81  *   - Each funclet must have all of its blocks contiguous, with the
  82  *     entry block first.
  83  *
  84  *   - Main entry point must be the first block.
  85  *
  86  * It is not a requirement, but we attempt to locate all the DV entry
  87  * points after the rest of the primary function body.  The normal
  88  * case for DV initializers is that each one falls through to the
  89  * next, with the block jumping back to the main entry point.
  90  */
  91 std::vector<borrowed_ptr<php::Block>> order_blocks(const php::Func& f) {
  92   auto sorted = rpoSortFromMain(f);
  93
  94   // Get the DV blocks, without the rest of the primary function body,
  95   // and then add them to the end of sorted.
  96   auto const dvBlocks = [&] {
  97     auto withDVs = rpoSortAddDVs(f);
  98     withDVs.erase(
  99       std::find(begin(withDVs), end(withDVs), sorted.front()),
 100       end(withDVs)
 101     );
 102     return withDVs;
 103   }();
 104   sorted.insert(end(sorted), begin(dvBlocks), end(dvBlocks));
 105
 106   // This stable sort will keep the blocks only reachable from DV
 107   // entry points after all other main code, and move fault funclets
 108   // after all that.
 109   std::stable_sort(
 110     begin(sorted), end(sorted),
 111     [&] (borrowed_ptr<php::Block> a, borrowed_ptr<php::Block> b) {
 112       using T = std::underlying_type<php::Block::Section>::type;
 113       return static_cast<T>(a->section) < static_cast<T>(b->section);
 114     }
 115   );
 116
 117   FTRACE(2, "      block order:{}\n",
 118     [&] {
 119       std::string ret;
 120       for (auto& b : sorted) {
 121         ret += " ";
 122         if (b->section != php::Block::Section::Main) {
 123           ret += "f";
 124         }
 125         ret += folly::to<std::string>(b->id);
 126       }
 127       return ret;
 128     }()
 129   );
 130   return sorted;
 131 }
 132
 133 // While emitting bytecode, we learn about some metadata that will
 134 // need to be registered in the FuncEmitter.
 135 struct EmitBcInfo {
 136   struct FPI {
 137     Offset fpushOff;
 138     Offset fcallOff;
 139     int32_t fpDelta;
 140   };
 141
 142   struct JmpFixup { Offset instrOff; Offset jmpImmedOff; };
 143
 144   struct BlockInfo {
 145     BlockInfo()
 146       : offset(kInvalidOffset)
 147       , past(kInvalidOffset)
 148     {}
 149
 150     // The offset of the block, if we've already emitted it.
 151     // Otherwise kInvalidOffset.
 152     Offset offset;
 153
 154     // The offset past the end of this block.
 155     Offset past;
 156
 157     // When we emit a forward jump to a block we haven't seen yet, we
 158     // write down where the jump was so we can fix it up when we get
 159     // to that block.
 160     std::vector<JmpFixup> forwardJumps;
 161
 162     // When we see a forward jump to a block, we record the stack
 163     // depth at the jump site here.  This is needed to track
 164     // currentStackDepth correctly (and we also assert all the jumps
 165     // have the same depth).
 166     folly::Optional<uint32_t> expectedStackDepth;
 167   };
 168
 169   std::vector<borrowed_ptr<php::Block>> blockOrder;
 170   uint32_t maxStackDepth;
 171   uint32_t maxFpiDepth;
 172   bool containsCalls;
 173   std::vector<FPI> fpiRegions;
 174   std::vector<BlockInfo> blockInfo;
 175 };
 176
 177 EmitBcInfo emit_bytecode(EmitUnitState& euState,
 178                          UnitEmitter& ue,
 179                          const php::Func& func) {
 180   EmitBcInfo ret = {};
 181   auto& blockInfo = ret.blockInfo;
 182   blockInfo.resize(func.nextBlockId);
 183
 184   // Track the stack depth while emitting to determine maxStackDepth.
 185   int32_t currentStackDepth { 0 };
 186
 187   // Stack of in-progress fpi regions.
 188   std::vector<EmitBcInfo::FPI> fpiStack;
 189
 190   // Temporary buffer for vector immediates.  (Hoisted so it's not
 191   // allocated in the loop.)
 192   std::vector<uint8_t> immVec;
 193
 194   auto emit_inst = [&] (const Bytecode& inst) {
 195     auto const startOffset = ue.bcPos();
 196
 197     FTRACE(4, " emit: {} -- {} @ {}\n", currentStackDepth, show(inst),
 198       show(inst.srcLoc));
 199
 200     auto count_stack_elems = [&] (const MVector& mvec) {
 201       int32_t ret = numLocationCodeStackVals(mvec.lcode);
 202       for (auto& m : mvec.mcodes) ret += mcodeStackVals(m.mcode);
 203       return ret;
 204     };
 205
 206     auto emit_mvec = [&] (const MVector& mvec) {
 207       immVec.clear();
 208
 209       auto const lcodeImms = numLocationCodeImms(mvec.lcode);
 210       immVec.push_back(mvec.lcode);
 211       assert(lcodeImms == 0 || lcodeImms == 1);
 212       if (lcodeImms) encodeIvaToVector(immVec, mvec.locBase->id);
 213
 214       for (auto& m : mvec.mcodes) {
 215         immVec.push_back(m.mcode);
 216         switch (memberCodeImmType(m.mcode)) {
 217         case MCodeImm::None:
 218           break;
 219         case MCodeImm::Local:
 220           encodeIvaToVector(immVec, m.immLoc->id);
 221           break;
 222         case MCodeImm::Int:
 223           encodeToVector(immVec, int64_t{m.immInt});
 224           break;
 225         case MCodeImm::String:
 226           encodeToVector(immVec, int32_t{ue.mergeLitstr(m.immStr)});
 227           break;
 228         }
 229       }
 230
 231       ue.emitInt32(immVec.size());
 232       ue.emitInt32(count_stack_elems(mvec));
 233       for (size_t i = 0; i < immVec.size(); ++i) ue.emitByte(immVec[i]);
 234     };
 235
 236     auto emit_vsa = [&] (const std::vector<SString>& keys) {
 237       auto n = keys.size();
 238       ue.emitInt32(n);
 239       for (size_t i = 0; i < n; ++i) {
 240         ue.emitInt32(ue.mergeLitstr(keys[i]));
 241       }
 242     };
 243
 244     auto emit_branch = [&] (const php::Block& target) {
 245       auto& info = blockInfo[target.id];
 246
 247       if (info.expectedStackDepth) {
 248         assert(*info.expectedStackDepth == currentStackDepth);
 249       } else {
 250         info.expectedStackDepth = currentStackDepth;
 251       }
 252
 253       if (info.offset != kInvalidOffset) {
 254         ue.emitInt32(info.offset - startOffset);
 255       } else {
 256         info.forwardJumps.push_back({ startOffset, ue.bcPos() });
 257         ue.emitInt32(0);
 258       }
 259     };
 260
 261     auto emit_switch = [&] (const SwitchTab& targets) {
 262       ue.emitInt32(targets.size());
 263       for (auto& t : targets) emit_branch(*t);
 264     };
 265
 266     auto emit_sswitch = [&] (const SSwitchTab& targets) {
 267       ue.emitInt32(targets.size());
 268       for (size_t i = 0; i < targets.size() - 1; ++i) {
 269         ue.emitInt32(ue.mergeLitstr(targets[i].first));
 270         emit_branch(*targets[i].second);
 271       }
 272       ue.emitInt32(-1);
 273       emit_branch(*targets[targets.size() - 1].second);
 274     };
 275
 276     auto emit_itertab = [&] (const IterTab& iterTab) {
 277       ue.emitInt32(iterTab.size());
 278       for (auto& kv : iterTab) {
 279         ue.emitInt32(kv.first);
 280         ue.emitInt32(kv.second->id);
 281       }
 282     };
 283
 284     auto emit_srcloc = [&] {
 285       if (!inst.srcLoc.isValid()) return;
 286       Location loc;
 287       loc.first(inst.srcLoc.start.line, inst.srcLoc.start.col);
 288       loc.last(inst.srcLoc.past.line, inst.srcLoc.past.col);
 289       ue.recordSourceLocation(&loc, startOffset);
 290     };
 291
 292     auto pop = [&] (int32_t n) {
 293       currentStackDepth -= n;
 294       assert(currentStackDepth >= 0);
 295     };
 296     auto push = [&] (int32_t n) {
 297       currentStackDepth += n;
 298       if (currentStackDepth > ret.maxStackDepth) {
 299         ret.maxStackDepth = currentStackDepth;
 300       }
 301     };
 302
 303     auto fpush = [&] {
 304       fpiStack.push_back({startOffset, kInvalidOffset, currentStackDepth});
 305       ret.maxFpiDepth = std::max<uint32_t>(ret.maxFpiDepth, fpiStack.size());
 306     };
 307
 308     auto fcall = [&] {
 309       auto fpi = fpiStack.back();
 310       fpiStack.pop_back();
 311       fpi.fcallOff = startOffset;
 312       ret.fpiRegions.push_back(fpi);
 313     };
 314
 315     auto ret_assert = [&] { assert(currentStackDepth == 1); };
 316
 317     auto defcls = [&] {
 318       auto const id = inst.DefCls.arg1;
 319       always_assert(euState.defClsMap[id] == kInvalidOffset);
 320       euState.defClsMap[id] = startOffset;
 321     };
 322
 323     auto defclsnop = [&] {
 324       auto const id = inst.DefCls.arg1;
 325       always_assert(euState.defClsMap[id] == kInvalidOffset);
 326       euState.defClsMap[id] = startOffset;
 327     };
 328
 329 #define IMM_MA(n)      emit_mvec(data.mvec);
 330 #define IMM_BLA(n)     emit_switch(data.targets);
 331 #define IMM_SLA(n)     emit_sswitch(data.targets);
 332 #define IMM_ILA(n)     emit_itertab(data.iterTab);
 333 #define IMM_IVA(n)     ue.emitIVA(data.arg##n);
 334 #define IMM_I64A(n)    ue.emitInt64(data.arg##n);
 335 #define IMM_LA(n)      ue.emitIVA(data.loc##n->id);
 336 #define IMM_IA(n)      ue.emitIVA(data.iter##n->id);
 337 #define IMM_DA(n)      ue.emitDouble(data.dbl##n);
 338 #define IMM_SA(n)      ue.emitInt32(ue.mergeLitstr(data.str##n));
 339 #define IMM_RATA(n)    encodeRAT(ue, data.rat);
 340 #define IMM_AA(n)      ue.emitInt32(ue.mergeArray(data.arr##n));
 341 #define IMM_OA_IMPL(n) ue.emitByte(static_cast<uint8_t>(data.subop));
 342 #define IMM_OA(type)   IMM_OA_IMPL
 343 #define IMM_BA(n)      emit_branch(*data.target);
 344 #define IMM_VSA(n)     emit_vsa(data.keys);
 345
 346 #define IMM_NA
 347 #define IMM_ONE(x)           IMM_##x(1)
 348 #define IMM_TWO(x, y)        IMM_##x(1);         IMM_##y(2);
 349 #define IMM_THREE(x, y, z)   IMM_TWO(x, y);      IMM_##z(3);
 350 #define IMM_FOUR(x, y, z, n) IMM_THREE(x, y, z); IMM_##n(4);
 351
 352 #define POP_NOV
 353 #define POP_ONE(x)            pop(1);
 354 #define POP_TWO(x, y)         pop(2);
 355 #define POP_THREE(x, y, z)    pop(3);
 356
 357 #define POP_MMANY      pop(count_stack_elems(data.mvec));
 358 #define POP_C_MMANY    pop(1); pop(count_stack_elems(data.mvec));
 359 #define POP_R_MMANY    pop(1); pop(count_stack_elems(data.mvec));
 360 #define POP_V_MMANY    pop(1); pop(count_stack_elems(data.mvec));
 361 #define POP_CMANY      pop(data.arg##1);
 362 #define POP_SMANY      pop(data.keys.size());
 363 #define POP_FMANY      pop(data.arg##1);
 364 #define POP_CVMANY     pop(data.arg##1);
 365 #define POP_CVUMANY    pop(data.arg##1);
 366
 367 #define PUSH_NOV
 368 #define PUSH_ONE(x)            push(1);
 369 #define PUSH_TWO(x, y)         push(2);
 370 #define PUSH_THREE(x, y, z)    push(3);
 371 #define PUSH_INS_1(x)          push(1);
 372 #define PUSH_INS_2(x)          push(1);
 373
 374 #define O(opcode, imms, inputs, outputs, flags)                   \
 375     auto emit_##opcode = [&] (const bc::opcode& data) {           \
 376       if (Op::opcode == Op::DefCls)    defcls();                  \
 377       if (Op::opcode == Op::DefClsNop) defclsnop();               \
 378       if (isRet(Op::opcode))           ret_assert();              \
 379       ue.emitOp(Op::opcode);                                      \
 380       POP_##inputs                                                \
 381       PUSH_##outputs                                              \
 382       IMM_##imms                                                  \
 383       if (isFPush(Op::opcode))     fpush();                       \
 384       if (isFCallStar(Op::opcode)) fcall();                       \
 385       if (flags & TF) currentStackDepth = 0;                      \
 386       if (Op::opcode == Op::FCall || Op::opcode == Op::FCallD) {  \
 387         ret.containsCalls = true;                                 \
 388       }                                                           \
 389       emit_srcloc();                                              \
 390     };
 391
 392     OPCODES
 393
 394 #undef O
 395
 396 #undef IMM_MA
 397 #undef IMM_BLA
 398 #undef IMM_SLA
 399 #undef IMM_ILA
 400 #undef IMM_IVA
 401 #undef IMM_I64A
 402 #undef IMM_LA
 403 #undef IMM_IA
 404 #undef IMM_DA
 405 #undef IMM_SA
 406 #undef IMM_RATA
 407 #undef IMM_AA
 408 #undef IMM_BA
 409 #undef IMM_OA_IMPL
 410 #undef IMM_OA
 411 #undef IMM_VSA
 412
 413 #undef IMM_NA
 414 #undef IMM_ONE
 415 #undef IMM_TWO
 416 #undef IMM_THREE
 417 #undef IMM_FOUR
 418
 419 #undef POP_NOV
 420 #undef POP_ONE
 421 #undef POP_TWO
 422 #undef POP_THREE
 423
 424 #undef POP_CMANY
 425 #undef POP_SMANY
 426 #undef POP_MMANY
 427 #undef POP_FMANY
 428 #undef POP_CVMANY
 429 #undef POP_CVUMANY
 430 #undef POP_C_MMANY
 431 #undef POP_R_MMANY
 432 #undef POP_V_MMANY
 433
 434 #undef PUSH_NOV
 435 #undef PUSH_ONE
 436 #undef PUSH_TWO
 437 #undef PUSH_THREE
 438 #undef PUSH_INS_1
 439 #undef PUSH_INS_2
 440
 441 #define O(opcode, ...)                                        \
 442     case Op::opcode:                                          \
 443       if (Op::opcode != Op::Nop) emit_##opcode(inst.opcode);  \
 444       break;
 445     switch (inst.op) { OPCODES }
 446 #undef O
 447   };
 448
 449   ret.blockOrder        = order_blocks(func);
 450   auto blockIt          = begin(ret.blockOrder);
 451   auto const endBlockIt = end(ret.blockOrder);
 452   for (; blockIt != endBlockIt; ++blockIt) {
 453     auto& b = *blockIt;
 454     auto& info = blockInfo[b->id];
 455     info.offset = ue.bcPos();
 456     FTRACE(2, "      block {}: {}\n", b->id, info.offset);
 457
 458     for (auto& fixup : info.forwardJumps) {
 459       ue.emitInt32(info.offset - fixup.instrOff, fixup.jmpImmedOff);
 460     }
 461
 462     if (info.expectedStackDepth) {
 463       currentStackDepth = *info.expectedStackDepth;
 464     }
 465
 466     for (auto& inst : b->hhbcs) emit_inst(inst);
 467
 468     if (b->fallthrough) {
 469       if (std::next(blockIt) == endBlockIt || blockIt[1] != b->fallthrough) {
 470         if (b->fallthroughNS) {
 471           emit_inst(bc::JmpNS { b->fallthrough });
 472         } else {
 473           emit_inst(bc::Jmp { b->fallthrough });
 474         }
 475       }
 476     }
 477
 478     info.past = ue.bcPos();
 479     FTRACE(2, "      block {} end: {}\n", b->id, info.past);
 480   }
 481
 482   return ret;
 483 }
 484
 485 void emit_locals_and_params(FuncEmitter& fe,
 486                             const php::Func& func,
 487                             const EmitBcInfo& info) {
 488   Id id = 0;
 489
 490   for (auto& loc : func.locals) {
 491     if (id < func.params.size()) {
 492       auto& param = func.params[id];
 493       FuncEmitter::ParamInfo pinfo;
 494       pinfo.defaultValue = param.defaultValue;
 495       pinfo.typeConstraint = param.typeConstraint;
 496       pinfo.userType = param.userTypeConstraint;
 497       pinfo.phpCode = param.phpCode;
 498       pinfo.userAttributes = param.userAttributes;
 499       pinfo.builtinType = param.builtinType;
 500       pinfo.byRef = param.byRef;
 501       pinfo.variadic = param.isVariadic;
 502       fe.appendParam(func.locals[id]->name, pinfo);
 503       if (auto const dv = param.dvEntryPoint) {
 504         fe.params[id].funcletOff = info.blockInfo[dv->id].offset;
 505       }
 506     } else {
 507       if (loc->name) {
 508         fe.allocVarId(loc->name);
 509         assert(fe.lookupVarId(loc->name) == id);
 510       } else {
 511         fe.allocUnnamedLocal();
 512       }
 513     }
 514
 515     ++id;
 516   }
 517   assert(fe.numLocals() == id);
 518   fe.setNumIterators(func.iters.size());
 519
 520   for (auto& sv : func.staticLocals) {
 521     fe.staticVars.push_back(Func::SVInfo {sv.name, sv.phpCode});
 522   }
 523 }
 524
 525 struct EHRegion {
 526   borrowed_ptr<const php::ExnNode> node;
 527   borrowed_ptr<EHRegion> parent;
 528   Offset start;
 529   Offset past;
 530 };
 531
 532 template<class BlockInfo, class ParentIndexMap>
 533 void emit_eh_region(FuncEmitter& fe,
 534                     borrowed_ptr<const EHRegion> region,
 535                     const BlockInfo& blockInfo,
 536                     ParentIndexMap& parentIndexMap) {
 537   // A region on a single empty block.
 538   if (region->start == region->past) return;
 539
 540   auto& eh = fe.addEHEnt();
 541   eh.m_base = region->start;
 542   eh.m_past = region->past;
 543   assert(eh.m_past >= eh.m_base);
 544   assert(eh.m_base != kInvalidOffset && eh.m_past != kInvalidOffset);
 545
 546   if (region->parent) {
 547     auto parentIt = parentIndexMap.find(region->parent);
 548     assert(parentIt != end(parentIndexMap));
 549     eh.m_parentIndex = parentIt->second;
 550   } else {
 551     eh.m_parentIndex = -1;
 552   }
 553   parentIndexMap[region] = fe.ehtab.size() - 1;
 554
 555   match<void>(
 556     region->node->info,
 557     [&] (const php::TryRegion& tr) {
 558       eh.m_type = EHEnt::Type::Catch;
 559       for (auto& c : tr.catches) {
 560         eh.m_catches.emplace_back(
 561           fe.ue().mergeLitstr(c.first),
 562           blockInfo[c.second->id].offset
 563         );
 564       }
 565       eh.m_fault = kInvalidOffset;
 566       eh.m_iterId = -1;
 567       eh.m_itRef = false;
 568     },
 569     [&] (const php::FaultRegion& fr) {
 570       eh.m_type = EHEnt::Type::Fault;
 571       eh.m_fault = blockInfo[fr.faultEntry->id].offset;
 572       eh.m_iterId = fr.iterId;
 573       eh.m_itRef = fr.itRef;
 574     }
 575   );
 576 }
 577
 578 void exn_path(std::vector<const php::ExnNode*>& ret, const php::ExnNode* n) {
 579   if (!n) return;
 580   exn_path(ret, n->parent);
 581   ret.push_back(n);
 582 }
 583
 584 // Return the count of shared elements in the front of two forward
 585 // ranges.
 586 template<class ForwardRange1, class ForwardRange2>
 587 size_t shared_prefix(ForwardRange1& r1, ForwardRange2& r2) {
 588   auto r1it = begin(r1);
 589   auto r2it = begin(r2);
 590   auto const r1end = end(r1);
 591   auto const r2end = end(r2);
 592   auto ret = size_t{0};
 593   while (r1it != r1end && r2it != r2end && *r1it == *r2it) {
 594     ++ret; ++r1it; ++r2it;
 595   }
 596   return ret;
 597 }
 598
 599 /*
 600  * Traverse the actual block layout, and find out the intervals for
 601  * each exception region in the tree.
 602  *
 603  * The basic idea here is that we haven't constrained block layout
 604  * based on the exception tree, but adjacent blocks are still
 605  * reasonably likely to have the same ExnNode.  Try to coalesce the EH
 606  * regions we create for in those cases.
 607  */
 608 void emit_ehent_tree(FuncEmitter& fe,
 609                      const php::Func& func,
 610                      const EmitBcInfo& info) {
 611   std::map<
 612     borrowed_ptr<const php::ExnNode>,
 613     std::vector<std::unique_ptr<EHRegion>>
 614   > exnMap;
 615
 616   /*
 617    * While walking over the blocks in layout order, we track the set
 618    * of "active" exnNodes.  This are a list of exnNodes that inherit
 619    * from each other.  When a new active node is pushed, begin an
 620    * EHEnt, and when it's popped, it's done.
 621    */
 622   std::vector<borrowed_ptr<const php::ExnNode>> activeList;
 623
 624   auto pop_active = [&] (Offset past) {
 625     auto p = activeList.back();
 626     activeList.pop_back();
 627     exnMap[p].back()->past = past;
 628   };
 629
 630   auto push_active = [&] (const php::ExnNode* p, Offset start) {
 631     auto const parent = activeList.empty()
 632       ? nullptr
 633       : borrow(exnMap[activeList.back()].back());
 634     exnMap[p].push_back(
 635       folly::make_unique<EHRegion>(
 636         EHRegion { p, parent, start, kInvalidOffset }
 637       )
 638     );
 639     activeList.push_back(p);
 640   };
 641
 642   /*
 643    * Walk over the blocks, and compare the new block's exnNode path to
 644    * the active one.  Find the least common ancestor of the two paths,
 645    * then modify the active list by popping and then pushing nodes to
 646    * set it to the new block's path.
 647    */
 648   for (auto& b : info.blockOrder) {
 649     auto const offset = info.blockInfo[b->id].offset;
 650
 651     if (!b->exnNode) {
 652       while (!activeList.empty()) pop_active(offset);
 653       continue;
 654     }
 655
 656     std::vector<borrowed_ptr<const php::ExnNode>> current;
 657     exn_path(current, b->exnNode);
 658
 659     auto const prefix = shared_prefix(current, activeList);
 660     for (size_t i = prefix, sz = activeList.size(); i < sz; ++i) {
 661       pop_active(offset);
 662     }
 663     for (size_t i = prefix, sz = current.size(); i < sz; ++i) {
 664       push_active(current[i], offset);
 665     }
 666
 667     if (debug && !activeList.empty()) {
 668       current.clear();
 669       exn_path(current, activeList.back());
 670       assert(current == activeList);
 671     }
 672   }
 673
 674   while (!activeList.empty()) {
 675     pop_active(info.blockInfo[info.blockOrder.back()->id].past);
 676   }
 677
 678   /*
 679    * We've created all our regions, but we need to sort them instead
 680    * of trying to get the UnitEmitter to do it.
 681    *
 682    * The UnitEmitter expects EH regions that look a certain way
 683    * (basically the way emitter.cpp likes them).  There are some rules
 684    * about the order it needs to have at runtime, which we set up
 685    * here.
 686    *
 687    * Essentially, an entry a is less than an entry b iff:
 688    *
 689    *   - a starts before b
 690    *   - a starts at the same place, but encloses b entirely
 691    *   - a has the same extents as b, but is a parent of b
 692    */
 693   std::vector<borrowed_ptr<EHRegion>> regions;
 694   for (auto& mapEnt : exnMap) {
 695     for (auto& region : mapEnt.second) {
 696       regions.push_back(borrow(region));
 697     }
 698   }
 699   std::sort(
 700     begin(regions), end(regions),
 701     [&] (borrowed_ptr<const EHRegion> a, borrowed_ptr<const EHRegion> b) {
 702       if (a == b) return false;
 703       if (a->start == b->start) {
 704         if (a->past == b->past) {
 705           // When regions exactly overlap, the parent is less than the
 706           // child.
 707           for (auto p = b->parent; p != nullptr; p = p->parent) {
 708             if (p == a) return true;
 709           }
 710           // If a is not a parent of b, and they have the same region;
 711           // then b better be a parent of a.
 712           if (debug) {
 713             auto p = a->parent;
 714             for (; p != b && p != nullptr; p = p->parent) continue;
 715             assert(p == b);
 716           }
 717           return false;
 718         }
 719         return a->past > b->past;
 720       }
 721       return a->start < b->start;
 722     }
 723   );
 724
 725   std::map<borrowed_ptr<const EHRegion>,uint32_t> parentIndexMap;
 726   for (auto& r : regions) {
 727     emit_eh_region(fe, r, info.blockInfo, parentIndexMap);
 728   }
 729   fe.setEHTabIsSorted();
 730 }
 731
 732 void emit_finish_func(const php::Func& func,
 733                       FuncEmitter& fe,
 734                       const EmitBcInfo& info) {
 735   if (info.containsCalls) fe.containsCalls = true;;
 736
 737   for (auto& fpi : info.fpiRegions) {
 738     auto& e = fe.addFPIEnt();
 739     e.m_fpushOff = fpi.fpushOff;
 740     e.m_fcallOff = fpi.fcallOff;
 741     e.m_fpOff    = fpi.fpDelta;
 742   }
 743
 744   emit_locals_and_params(fe, func, info);
 745   emit_ehent_tree(fe, func, info);
 746
 747   fe.userAttributes = func.userAttributes;
 748   fe.retUserType = func.returnUserType;
 749   fe.originalFilename = func.originalFilename;
 750   fe.isClosureBody = func.isClosureBody;
 751   fe.isAsync = func.isAsync;
 752   fe.isGenerator = func.isGenerator;
 753   fe.isPairGenerator = func.isPairGenerator;
 754   if (func.nativeInfo) {
 755     fe.returnType = func.nativeInfo->returnType;
 756   }
 757   fe.retTypeConstraint = func.retTypeConstraint;
 758
 759   fe.maxStackCells = info.maxStackDepth +
 760                      fe.numLocals() +
 761                      fe.numIterators() * kNumIterCells +
 762                      info.maxFpiDepth * kNumActRecCells;
 763
 764   fe.finish(fe.ue().bcPos(), false /* load */);
 765   fe.ue().recordFunction(&fe);
 766 }
 767
 768 void emit_init_func(FuncEmitter& fe, const php::Func& func) {
 769   fe.init(
 770     std::get<0>(func.srcInfo.loc),
 771     std::get<1>(func.srcInfo.loc),
 772     fe.ue().bcPos(),
 773     func.attrs,
 774     func.top,
 775     func.srcInfo.docComment
 776   );
 777 }
 778
 779 void emit_func(EmitUnitState& state, UnitEmitter& ue, const php::Func& func) {
 780   FTRACE(2,  "    func {}\n", func.name->data());
 781   auto const fe = ue.newFuncEmitter(func.name);
 782   emit_init_func(*fe, func);
 783   auto const info = emit_bytecode(state, ue, func);
 784   emit_finish_func(func, *fe, info);
 785 }
 786
 787 void emit_pseudomain(EmitUnitState& state,
 788                      UnitEmitter& ue,
 789                      const php::Unit& unit) {
 790   FTRACE(2,  "    pseudomain\n");
 791   auto& pm = *unit.pseudomain;
 792   ue.initMain(std::get<0>(pm.srcInfo.loc),
 793               std::get<1>(pm.srcInfo.loc));
 794   auto const fe = ue.getMain();
 795   auto const info = emit_bytecode(state, ue, pm);
 796   emit_finish_func(pm, *fe, info);
 797 }
 798
 799 void merge_repo_auth_type(UnitEmitter& ue, RepoAuthType rat) {
 800   using T = RepoAuthType::Tag;
 801
 802   switch (rat.tag()) {
 803   case T::OptBool:
 804   case T::OptInt:
 805   case T::OptSStr:
 806   case T::OptStr:
 807   case T::OptDbl:
 808   case T::OptRes:
 809   case T::OptObj:
 810   case T::Null:
 811   case T::Cell:
 812   case T::Ref:
 813   case T::InitUnc:
 814   case T::Unc:
 815   case T::InitCell:
 816   case T::InitGen:
 817   case T::Gen:
 818   case T::Uninit:
 819   case T::InitNull:
 820   case T::Bool:
 821   case T::Int:
 822   case T::Dbl:
 823   case T::Res:
 824   case T::SStr:
 825   case T::Str:
 826   case T::Obj:
 827     return;
 828
 829   case T::OptSArr:
 830   case T::OptArr:
 831   case T::SArr:
 832   case T::Arr:
 833     // We don't need to merge the litstrs in the array, because rats
 834     // in arrays in the array type table must be using global litstr
 835     // ids.  (As the array type table itself is not associated with
 836     // any unit.)
 837     return;
 838
 839   case T::OptSubObj:
 840   case T::OptExactObj:
 841   case T::SubObj:
 842   case T::ExactObj:
 843     ue.mergeLitstr(rat.clsName());
 844     return;
 845   }
 846 }
 847
 848 void emit_class(EmitUnitState& state,
 849                 UnitEmitter& ue,
 850                 const php::Class& cls) {
 851   FTRACE(2, "    class: {}\n", cls.name->data());
 852   auto const pce = ue.newPreClassEmitter(
 853     cls.name,
 854     cls.hoistability
 855   );
 856   pce->init(
 857     std::get<0>(cls.srcInfo.loc),
 858     std::get<1>(cls.srcInfo.loc),
 859     ue.bcPos(),
 860     cls.attrs,
 861     cls.parentName ? cls.parentName : s_empty.get(),
 862     cls.srcInfo.docComment
 863   );
 864   pce->setUserAttributes(cls.userAttributes);
 865
 866   for (auto& x : cls.interfaceNames)     pce->addInterface(x);
 867   for (auto& x : cls.usedTraitNames)     pce->addUsedTrait(x);
 868   for (auto& x : cls.requirements)       pce->addClassRequirement(x);
 869   for (auto& x : cls.traitPrecRules)     pce->addTraitPrecRule(x);
 870   for (auto& x : cls.traitAliasRules)    pce->addTraitAliasRule(x);
 871   pce->setNumDeclMethods(cls.numDeclMethods);
 872
 873   for (auto& m : cls.methods) {
 874     FTRACE(2, "    method: {}\n", m->name->data());
 875     auto const fe = ue.newMethodEmitter(m->name, pce);
 876     emit_init_func(*fe, *m);
 877     pce->addMethod(fe);
 878     auto const info = emit_bytecode(state, ue, *m);
 879     emit_finish_func(*m, *fe, info);
 880   }
 881
 882   auto const privateProps   = state.index.lookup_private_props(&cls);
 883   auto const privateStatics = state.index.lookup_private_statics(&cls);
 884   for (auto& prop : cls.properties) {
 885     auto const repoTy = [&] (const PropState& ps) -> RepoAuthType {
 886       /*
 887        * Skip closures, because the types of their used vars can be
 888        * communicated via assert opcodes right now.  At the time of this
 889        * writing there was nothing to gain by including RAT's for the
 890        * properties, since closure properties are only used internally by the
 891        * runtime, not directly via opcodes like CGetM.
 892        */
 893       if (is_closure(cls)) return RepoAuthType{};
 894
 895       auto it = ps.find(prop.name);
 896       if (it == end(ps)) return RepoAuthType{};
 897       auto const rat = make_repo_type(*state.index.array_table_builder(),
 898                                       it->second);
 899       merge_repo_auth_type(ue, rat);
 900       return rat;
 901     };
 902
 903     pce->addProperty(
 904       prop.name,
 905       prop.attrs,
 906       prop.typeConstraint,
 907       prop.docComment,
 908       &prop.val,
 909       (prop.attrs & AttrStatic) ? repoTy(privateStatics) : repoTy(privateProps)
 910     );
 911   }
 912
 913   for (auto& cconst : cls.constants) {
 914     if (!cconst.val.hasValue()) {
 915       pce->addAbstractConstant(
 916         cconst.name,
 917         cconst.typeConstraint,
 918         cconst.isTypeconst
 919       );
 920     } else {
 921       pce->addConstant(
 922         cconst.name,
 923         cconst.typeConstraint,
 924         &cconst.val.value(),
 925         cconst.phpCode,
 926         cconst.isTypeconst
 927       );
 928     }
 929   }
 930
 931   pce->setEnumBaseTy(cls.enumBaseTy);
 932 }
 933
 934 //////////////////////////////////////////////////////////////////////
 935
 936 }
 937
 938 std::unique_ptr<UnitEmitter> emit_unit(const Index& index,
 939                                        const php::Unit& unit) {
 940   auto const is_systemlib = is_systemlib_part(unit);
 941   Trace::Bump bumper{Trace::hhbbc_emit, kSystemLibBump, is_systemlib};
 942
 943   auto ue = folly::make_unique<UnitEmitter>(unit.md5);
 944   FTRACE(1, "  unit {}\n", unit.filename->data());
 945   ue->m_filepath = unit.filename;
 946   ue->m_preloadPriority = unit.preloadPriority;
 947
 948   EmitUnitState state { index };
 949   state.defClsMap.resize(unit.classes.size(), kInvalidOffset);
 950
 951   /*
 952    * Unfortunate special case for Systemlib units.
 953    *
 954    * We need to ensure these units end up mergeOnly, at runtime there
 955    * are things that assume this (right now no other HHBBC units end
 956    * up being merge only, because of the returnSeen stuff below).
 957    *
 958    * (Merge-only-ness provides no measurable perf win in repo mode now
 959    * that we have persistent classes, so we're not too worried about
 960    * this.)
 961    */
 962   if (is_systemlib) {
 963     ue->m_mergeOnly = true;
 964     auto const tv = make_tv<KindOfInt64>(1);
 965     ue->m_mainReturn = tv;
 966   } else {
 967     /*
 968      * TODO(#3017265): UnitEmitter is very coupled to emitter.cpp, and
 969      * expects classes and things to be added in an order that isn't
 970      * quite clear.  If you don't set returnSeen things relating to
 971      * hoistability break.
 972      */
 973     ue->m_returnSeen = true;
 974   }
 975
 976   emit_pseudomain(state, *ue, unit);
 977   for (auto& c : unit.classes)     emit_class(state, *ue, *c);
 978   for (auto& f : unit.funcs)       emit_func(state, *ue, *f);
 979   for (auto& t : unit.typeAliases) ue->addTypeAlias(*t);
 980
 981   for (size_t id = 0; id < unit.classes.size(); ++id) {
 982     // We may not have a DefCls PC if we're a closure, or a
 983     // non-top-level class declaration is DCE'd.
 984     if (state.defClsMap[id] != kInvalidOffset) {
 985       ue->pce(id)->setOffset(state.defClsMap[id]);
 986     }
 987   }
 988
 989   return ue;
 990 }
 991
 992 //////////////////////////////////////////////////////////////////////
 993
 994 }}