text: /*
     +----------------------------------------------------------------------+
     | HipHop for PHP                                                       |
     +----------------------------------------------------------------------+
     | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
     +----------------------------------------------------------------------+
     | This source file is subject to version 3.01 of the PHP license,      |
     | that is bundled with this package in the file LICENSE, and is        |
     | available through the world-wide-web at the following url:           |
     | http://www.php.net/license/3_01.txt                                  |
     | If you did not receive a copy of the PHP license and are unable to   |
     | obtain it through the world-wide-web, please send a note to          |
     | license@php.net so we can mail you a copy immediately.               |
     +----------------------------------------------------------------------+
  */
  #include "hphp/hhbbc/interp.h"
  
  #include <algorithm>
  #include <vector>
  #include <string>
  #include <iterator>
  
  #include <folly/gen/Base.h>
  #include <folly/gen/String.h>
  
  #include "hphp/util/hash-set.h"
  #include "hphp/util/trace.h"
  #include "hphp/runtime/base/array-init.h"
  #include "hphp/runtime/base/array-iterator.h"
  #include "hphp/runtime/base/collections.h"
  #include "hphp/runtime/base/static-string-table.h"
  #include "hphp/runtime/base/tv-arith.h"
  #include "hphp/runtime/base/tv-comparisons.h"
  #include "hphp/runtime/base/tv-conversions.h"
  #include "hphp/runtime/base/type-structure.h"
  #include "hphp/runtime/base/type-structure-helpers.h"
  #include "hphp/runtime/base/type-structure-helpers-defs.h"
  #include "hphp/runtime/vm/runtime.h"
  #include "hphp/runtime/vm/unit-util.h"
  
  #include "hphp/runtime/ext/hh/ext_hh.h"
  
  #include "hphp/hhbbc/analyze.h"
  #include "hphp/hhbbc/bc.h"
  #include "hphp/hhbbc/cfg.h"
  #include "hphp/hhbbc/class-util.h"
  #include "hphp/hhbbc/eval-cell.h"
  #include "hphp/hhbbc/index.h"
  #include "hphp/hhbbc/interp-state.h"
  #include "hphp/hhbbc/optimize.h"
  #include "hphp/hhbbc/representation.h"
  #include "hphp/hhbbc/type-builtins.h"
  #include "hphp/hhbbc/type-ops.h"
  #include "hphp/hhbbc/type-structure.h"
  #include "hphp/hhbbc/type-system.h"
  #include "hphp/hhbbc/unit-util.h"
  #include "hphp/hhbbc/wide-func.h"
  
  #include "hphp/hhbbc/stats.h"
  
  #include "hphp/hhbbc/interp-internal.h"
  
  namespace HPHP { namespace HHBBC {
  
  //////////////////////////////////////////////////////////////////////
  
  namespace {
  
  const StaticString s_MethCallerHelper("__SystemLib\\MethCallerHelper");
  const StaticString s_PHP_Incomplete_Class("__PHP_Incomplete_Class");
  const StaticString s_IMemoizeParam("HH\\IMemoizeParam");
  const StaticString s_getInstanceKey("getInstanceKey");
  const StaticString s_Closure("Closure");
  const StaticString s_this("HH\\this");
  
  bool poppable(Op op) {
    switch (op) {
      case Op::Dup:
      case Op::Null:
      case Op::False:
      case Op::True:
      case Op::Int:
      case Op::Double:
      case Op::String:
      case Op::Vec:
      case Op::Dict:
      case Op::Keyset:
      case Op::NewDictArray:
      case Op::NewCol:
      case Op::LazyClass:
        return true;
      default:
        return false;
    }
  }
  
  void interpStep(ISS& env, const Bytecode& bc);
  
  void record(ISS& env, const Bytecode& bc) {
    if (bc.srcLoc != env.srcLoc) {
      Bytecode tmp = bc;
      tmp.srcLoc = env.srcLoc;
      return record(env, tmp);
    }
  
    if (!env.replacedBcs.size() &&
        env.unchangedBcs < env.blk.hhbcs.size() &&
        bc == env.blk.hhbcs[env.unchangedBcs]) {
      env.unchangedBcs++;
      return;
    }
  
    ITRACE(2, "  => {}\n", show(env.ctx.func, bc));
    env.replacedBcs.push_back(bc);
  }
  
  // The number of pops as seen by interp.
  uint32_t numPop(const Bytecode& bc) {
    if (bc.op == Op::CGetL2) return 1;
    return bc.numPop();
  }
  
  // The number of pushes as seen by interp.
  uint32_t numPush(const Bytecode& bc) {
    if (bc.op == Op::CGetL2) return 2;
    return bc.numPush();
  }
  
  void reprocess(ISS& env) {
    env.reprocess = true;
  }
  
  ArrayData** add_elem_array(ISS& env) {
    auto const idx = env.trackedElems.back().idx;
    if (idx < env.unchangedBcs) {
      auto const DEBUG_ONLY& bc = env.blk.hhbcs[idx];
      assertx(bc.op == Op::Concat);
      return nullptr;
    }
    assertx(idx >= env.unchangedBcs);
    auto& bc = env.replacedBcs[idx - env.unchangedBcs];
    auto arr = [&] () -> const ArrayData** {
      switch (bc.op) {
        case Op::Vec:     return &bc.Vec.arr1;
        case Op::Dict:    return &bc.Dict.arr1;
        case Op::Keyset:  return &bc.Keyset.arr1;
        case Op::Concat:  return nullptr;
        default:          not_reached();
      }
    }();
    return const_cast<ArrayData**>(arr);
  }
  
  bool start_add_elem(ISS& env, Type& ty, Op op) {
    auto value = tvNonStatic(ty);
    if (!value || !isArrayLikeType(value->m_type)) return false;
  
    if (op == Op::AddElemC) {
      reduce(env, bc::PopC {}, bc::PopC {}, bc::PopC {});
    } else {
      reduce(env, bc::PopC {}, bc::PopC {});
    }
    env.trackedElems.emplace_back(
      env.state.stack.size(),
      env.unchangedBcs + env.replacedBcs.size()
    );
  
    auto const arr = value->m_data.parr;
    env.replacedBcs.push_back(
      [&] () -> Bytecode {
        if (arr->isVecType())    return bc::Vec { arr };
        if (arr->isDictType())   return bc::Dict { arr };
        if (arr->isKeysetType()) return bc::Keyset { arr };
        always_assert(false);
      }()
    );
    env.replacedBcs.back().srcLoc = env.srcLoc;
    ITRACE(2, "(addelem* -> {}\n",
           show(env.ctx.func, env.replacedBcs.back()));
    push(env, std::move(ty));
    effect_free(env);
    return true;
  }
  
  /*
   * Alter the saved add_elem array in a way that preserves its provenance tag
   * or adds a new one if applicable (i.e. the array is a vec or dict)
   *
   * The `mutate` parameter should be callable with an ArrayData** pointing to the
   * add_elem array cached in the interp state and should write to it directly.
   */
  template <typename Fn>
  bool mutate_add_elem_array(ISS& env, Fn&& mutate) {
    auto const arr = add_elem_array(env);
    if (!arr) return false;
    mutate(arr);
    return true;
  }
  
  void finish_tracked_elem(ISS& env) {
    auto const arr = add_elem_array(env);
    env.trackedElems.pop_back();
    if (arr) ArrayData::GetScalarArray(arr);
  }
  
  void finish_tracked_elems(ISS& env, size_t depth) {
    while (!env.trackedElems.empty() && env.trackedElems.back().depth >= depth) {
      finish_tracked_elem(env);
    }
  }
  
  uint32_t id_from_slot(ISS& env, int slot) {
    auto const id = (env.state.stack.end() - (slot + 1))->id;
    assertx(id == StackElem::NoId ||
            id < env.unchangedBcs + env.replacedBcs.size());
    return id;
  }
  
  const Bytecode* op_from_id(ISS& env, uint32_t id) {
    if (id == StackElem::NoId) return nullptr;
    if (id < env.unchangedBcs) return &env.blk.hhbcs[id];
    auto const off = id - env.unchangedBcs;
    assertx(off < env.replacedBcs.size());
    return &env.replacedBcs[off];
  }
  
  void ensure_mutable(ISS& env, uint32_t id) {
    if (id < env.unchangedBcs) {
      auto const delta = env.unchangedBcs - id;
      env.replacedBcs.resize(env.replacedBcs.size() + delta);
      for (auto i = env.replacedBcs.size(); i-- > delta; ) {
        env.replacedBcs[i] = std::move(env.replacedBcs[i - delta]);
      }
      for (auto i = 0; i < delta; i++) {
        env.replacedBcs[i] = env.blk.hhbcs[id + i];
      }
      env.unchangedBcs = id;
    }
  }
  
  /*
   * Turn the instruction that wrote the slot'th element from the top of
   * the stack into a Nop, adjusting the stack appropriately. If its the
   * previous instruction, just rewind.
   */
  int kill_by_slot(ISS& env, int slot) {
    assertx(!env.undo);
    auto const id = id_from_slot(env, slot);
    assertx(id != StackElem::NoId);
    auto const sz = env.state.stack.size();
    // if its the last bytecode we processed, we can rewind and avoid
    // the reprocess overhead.
    if (id == env.unchangedBcs + env.replacedBcs.size() - 1) {
      rewind(env, 1);
      return env.state.stack.size() - sz;
    }
    ensure_mutable(env, id);
    auto& bc = env.replacedBcs[id - env.unchangedBcs];
    auto const pop = numPop(bc);
    auto const push = numPush(bc);
    ITRACE(2, "kill_by_slot: slot={}, id={}, was {}\n",
           slot, id, show(env.ctx.func, bc));
    bc = bc_with_loc(bc.srcLoc, bc::Nop {});
    env.state.stack.kill(pop, push, id);
    reprocess(env);
    return env.state.stack.size() - sz;
  }
  
  /*
   * Check whether an instruction can be inserted immediately after the
   * slot'th stack entry was written. This is only possible if slot was
   * the last thing written by the instruction that wrote it (ie some
   * bytecodes push more than one value - there's no way to insert a
   * bytecode that will write *between* those values on the stack).
   */
  bool can_insert_after_slot(ISS& env, int slot) {
    auto const it = env.state.stack.end() - (slot + 1);
    if (it->id == StackElem::NoId) return false;
    if (auto const next = it.next_elem(1)) {
      return next->id != it->id;
    }
    return true;
  }
  
  /*
   * Insert a sequence of bytecodes after the instruction that wrote the
   * slot'th element from the top of the stack.
   *
   * The entire sequence pops numPop, and pushes numPush stack
   * elements. Only the last bytecode can push anything onto the stack,
   * and the types it pushes are pointed to by types (if you have more
   * than one bytecode that pushes, call this more than once).
   */
  void insert_after_slot(ISS& env, int slot,
                         int numPop, int numPush, const Type* types,
                         const BytecodeVec& bcs) {
    assertx(can_insert_after_slot(env, slot));
    assertx(!env.undo);
    auto const id = id_from_slot(env, slot);
    assertx(id != StackElem::NoId);
    ensure_mutable(env, id + 1);
    env.state.stack.insert_after(numPop, numPush, types, bcs.size(), id);
    env.replacedBcs.insert(env.replacedBcs.begin() + (id + 1 - env.unchangedBcs),
                           bcs.begin(), bcs.end());
    using namespace folly::gen;
    ITRACE(2, "insert_after_slot: slot={}, id={}  [{}]\n",
           slot, id,
           from(bcs) |
           map([&] (const Bytecode& bc) { return show(env.ctx.func, bc); }) |
           unsplit<std::string>(", "));
  }
  
  Bytecode& mutate_last_op(ISS& env) {
    assertx(will_reduce(env));
  
    if (!env.replacedBcs.size()) {
      assertx(env.unchangedBcs);
      env.replacedBcs.push_back(env.blk.hhbcs[--env.unchangedBcs]);
    }
    return env.replacedBcs.back();
  }
  
  /*
   * Can be used to replace one op with another when rewind/reduce isn't
   * safe (eg to change a SetL to a PopL - its not safe to rewind/reduce
   * because the SetL changed both the Type and the equiv of its local).
   */
  void replace_last_op(ISS& env, Bytecode&& bc) {
    auto& last = mutate_last_op(env);
    auto const newPush = numPush(bc);
    auto const oldPush = numPush(last);
    auto const newPops = numPop(bc);
    auto const oldPops = numPop(last);
  
    assertx(newPush <= oldPush);
    assertx(newPops <= oldPops);
  
    if (newPush != oldPush || newPops != oldPops) {
      assertx(!env.undo);
      env.state.stack.rewind(oldPops - newPops, oldPush - newPush);
    }
    ITRACE(2, "(replace: {}->{}\n",
           show(env.ctx.func, last), show(env.ctx.func, bc));
    last = bc_with_loc(last.srcLoc, bc);
  }
  
  }
  
  //////////////////////////////////////////////////////////////////////
  
  const Bytecode* op_from_slot(ISS& env, int slot, int prev /* = 0 */) {
    if (!will_reduce(env)) return nullptr;
    auto const id = id_from_slot(env, slot);
    if (id == StackElem::NoId) return nullptr;
    if (id < prev) return nullptr;
    return op_from_id(env, id - prev);
  }
  
  const Bytecode* last_op(ISS& env, int idx /* = 0 */) {
    if (!will_reduce(env)) return nullptr;
  
    if (env.replacedBcs.size() > idx) {
      return &env.replacedBcs[env.replacedBcs.size() - idx - 1];
    }
  
    idx -= env.replacedBcs.size();
    if (env.unchangedBcs > idx) {
      return &env.blk.hhbcs[env.unchangedBcs - idx - 1];
    }
    return nullptr;
  }
  
  /*
   * Assuming bc was just interped, rewind to the state immediately
   * before it was interped.
   *
   * This is rarely what you want. Its used for constprop, where the
   * bytecode has been interped, but not yet committed to the bytecode
   * stream. We want to undo its effects, the spit out pops for its
   * inputs, and commit a constant-generating bytecode.
   */
  void rewind(ISS& env, const Bytecode& bc) {
    assertx(!env.undo);
    ITRACE(2, "(rewind: {}\n", show(env.ctx.func, bc));
    env.state.stack.rewind(numPop(bc), numPush(bc));
  }
  
  /*
   * Used for peephole opts. Will undo the *stack* effects of the last n
   * committed byte codes, and remove them from the bytecode stream, in
   * preparation for writing out an optimized replacement sequence.
   *
   * WARNING: Does not undo other changes to state, such as local types,
   * local equivalency, and thisType. Take care when rewinding such
   * things.
   */
  void rewind(ISS& env, int n) {
    assertx(n);
    assertx(!env.undo);
    while (env.replacedBcs.size()) {
      rewind(env, env.replacedBcs.back());
      env.replacedBcs.pop_back();
      if (!--n) return;
    }
    while (n--) {
      rewind(env, env.blk.hhbcs[--env.unchangedBcs]);
    }
  }
  
  void impl_vec(ISS& env, bool reduce, BytecodeVec&& bcs) {
    if (!will_reduce(env)) reduce = false;
  
    if (reduce) {
      using namespace folly::gen;
      ITRACE(2, "(reduce: {}\n",
             from(bcs) |
             map([&] (const Bytecode& bc) { return show(env.ctx.func, bc); }) |
             unsplit<std::string>(", "));
      if (bcs.size()) {
        auto ef = !env.flags.reduced || env.flags.effectFree;
        Trace::Indent _;
        for (auto const& bc : bcs) {
          assertx(
            env.flags.jmpDest == NoBlockId &&
            "you can't use impl with branching opcodes before last position"
          );
          interpStep(env, bc);
          if (!env.flags.effectFree) ef = false;
          if (env.state.unreachable || env.flags.jmpDest != NoBlockId) break;
        }
        env.flags.effectFree = ef;
      } else if (!env.flags.reduced) {
        effect_free(env);
      }
      env.flags.reduced = true;
      return;
    }
  
    env.analyzeDepth++;
    SCOPE_EXIT { env.analyzeDepth--; };
  
    // We should be at the start of a bytecode.
    assertx(env.flags.wasPEI &&
            !env.flags.canConstProp &&
            !env.flags.effectFree);
  
    env.flags.wasPEI          = false;
    env.flags.canConstProp    = true;
    env.flags.effectFree      = true;
  
    for (auto const& bc : bcs) {
      assertx(env.flags.jmpDest == NoBlockId &&
             "you can't use impl with branching opcodes before last position");
  
      auto const wasPEI = env.flags.wasPEI;
      auto const canConstProp = env.flags.canConstProp;
      auto const effectFree = env.flags.effectFree;
  
      ITRACE(3, "    (impl {}\n", show(env.ctx.func, bc));
      env.flags.wasPEI          = true;
      env.flags.canConstProp    = false;
      env.flags.effectFree      = false;
      default_dispatch(env, bc);
  
      if (env.flags.canConstProp) {
        [&] {
          if (env.flags.effectFree && !env.flags.wasPEI) return;
          auto stk = env.state.stack.end();
          for (auto i = bc.numPush(); i--; ) {
            --stk;
            if (!is_scalar(stk->type)) return;
          }
          env.flags.effectFree = true;
          env.flags.wasPEI = false;
        }();
      }
  
      // If any of the opcodes in the impl list said they could throw,
      // then the whole thing could throw.
      env.flags.wasPEI = env.flags.wasPEI || wasPEI;
      env.flags.canConstProp = env.flags.canConstProp && canConstProp;
      env.flags.effectFree = env.flags.effectFree && effectFree;
      if (env.state.unreachable || env.flags.jmpDest != NoBlockId) break;
    }
  }
  
  LocalId equivLocalRange(ISS& env, const LocalRange& range) {
    auto bestRange = range.first;
    auto equivFirst = findLocEquiv(env, range.first);
    if (equivFirst == NoLocalId) return bestRange;
    do {
      if (equivFirst < bestRange) {
        auto equivRange = [&] {
          // local equivalency includes differing by Uninit, so we need
          // to check the types.
          if (peekLocRaw(env, equivFirst) != peekLocRaw(env, range.first)) {
            return false;
          }
  
          for (uint32_t i = 1; i < range.count; ++i) {
            if (!locsAreEquiv(env, equivFirst + i, range.first + i) ||
                peekLocRaw(env, equivFirst + i) !=
                peekLocRaw(env, range.first + i)) {
              return false;
            }
          }
  
          return true;
        }();
  
        if (equivRange) {
          bestRange = equivFirst;
        }
      }
      equivFirst = findLocEquiv(env, equivFirst);
      assertx(equivFirst != NoLocalId);
    } while (equivFirst != range.first);
  
    return bestRange;
  }
  
  SString getNameFromType(const Type& t) {
    if (!t.subtypeOf(BStr) && !t.subtypeOf(BLazyCls)) return nullptr;
    if (is_specialized_string(t)) return sval_of(t);
    if (is_specialized_lazycls(t)) return lazyclsval_of(t);
    return nullptr;
  }
  
  //////////////////////////////////////////////////////////////////////
  
  namespace {
  
  /*
   * Very simple check to see if the top level class is reified or not
   * If not we can reduce a VerifyTypeTS to a regular VerifyType
   */
  bool shouldReduceToNonReifiedVerifyType(ISS& env, SArray ts) {
    if (get_ts_kind(ts) != TypeStructure::Kind::T_unresolved) return false;
    auto const clsName = get_ts_classname(ts);
    auto const rcls = env.index.resolve_class(env.ctx, clsName);
    if (rcls && rcls->resolved()) return !rcls->cls()->hasReifiedGenerics;
    // Type aliases cannot have reified generics
    return env.index.lookup_type_alias(clsName) != nullptr;
  }
  
  }
  
  //////////////////////////////////////////////////////////////////////
  
  namespace interp_step {
  
  void in(ISS& env, const bc::Nop&)  { reduce(env); }
  
  void in(ISS& env, const bc::PopC&) {
    if (auto const last = last_op(env)) {
      if (poppable(last->op)) {
        rewind(env, 1);
        return reduce(env);
      }
      if (last->op == Op::This) {
        // can't rewind This because it removed null from thisType (so
        // CheckThis at this point is a no-op) - and note that it must
        // have *been* nullable, or we'd have turned it into a
        // `BareThis NeverNull`
        replace_last_op(env, bc::CheckThis {});
        return reduce(env);
      }
      if (last->op == Op::SetL) {
        // can't rewind a SetL because it changes local state
        replace_last_op(env, bc::PopL { last->SetL.loc1 });
        return reduce(env);
      }
      if (last->op == Op::CGetL2) {
        auto loc = last->CGetL2.nloc1;
        rewind(env, 1);
        return reduce(env, bc::PopC {}, bc::CGetL { loc });
      }
    }
  
    effect_free(env);
    popC(env);
  }
  
  void in(ISS& env, const bc::PopU&) {
    if (auto const last = last_op(env)) {
      if (last->op == Op::NullUninit) {
        rewind(env, 1);
        return reduce(env);
      }
    }
    effect_free(env); popU(env);
  }
  
  void in(ISS& env, const bc::PopU2&) {
    effect_free(env);
    auto equiv = topStkEquiv(env);
    auto val = popC(env);
    popU(env);
    push(env, std::move(val), equiv != StackDupId ? equiv : NoLocalId);
  }
  
  void in(ISS& env, const bc::EntryNop&) { effect_free(env); }
  
  void in(ISS& env, const bc::Dup& /*op*/) {
    effect_free(env);
    auto equiv = topStkEquiv(env);
    auto val = popC(env);
    push(env, val, equiv);
    push(env, std::move(val), StackDupId);
  }
  
  void in(ISS& env, const bc::AssertRATL& op) {
    mayReadLocal(env, op.loc1);
    effect_free(env);
  }
  
  void in(ISS& env, const bc::AssertRATStk&) {
    effect_free(env);
  }
  
  void in(ISS& env, const bc::BreakTraceHint&) { effect_free(env); }
  
  void in(ISS& env, const bc::CGetCUNop&) {
    effect_free(env);
    auto const t = popCU(env);
    push(env, remove_uninit(t));
  }
  
  void in(ISS& env, const bc::UGetCUNop&) {
    effect_free(env);
    popCU(env);
    push(env, TUninit);
  }
  
  void in(ISS& env, const bc::Null&) {
    effect_free(env);
    push(env, TInitNull);
  }
  
  void in(ISS& env, const bc::NullUninit&) {
    effect_free(env);
    push(env, TUninit);
  }
  
  void in(ISS& env, const bc::True&) {
    effect_free(env);
    push(env, TTrue);
  }
  
  void in(ISS& env, const bc::False&) {
    effect_free(env);
    push(env, TFalse);
  }
  
  void in(ISS& env, const bc::Int& op) {
    effect_free(env);
    push(env, ival(op.arg1));
  }
  
  void in(ISS& env, const bc::Double& op) {
    effect_free(env);
    push(env, dval(op.dbl1));
  }
  
  void in(ISS& env, const bc::String& op) {
    effect_free(env);
    push(env, sval(op.str1));
  }
  
  void in(ISS& env, const bc::Vec& op) {
    assertx(op.arr1->isVecType());
    effect_free(env);
    push(env, vec_val(op.arr1));
  }
  
  void in(ISS& env, const bc::Dict& op) {
    assertx(op.arr1->isDictType());
    effect_free(env);
    push(env, dict_val(op.arr1));
  }
  
  void in(ISS& env, const bc::Keyset& op) {
    assertx(op.arr1->isKeysetType());
    effect_free(env);
    push(env, keyset_val(op.arr1));
  }
  
  void in(ISS& env, const bc::NewDictArray& op) {
    effect_free(env);
    push(env, op.arg1 == 0 ? dict_empty() : some_dict_empty());
  }
  
  void in(ISS& env, const bc::NewStructDict& op) {
    auto map = MapElems{};
    for (auto it = op.keys.end(); it != op.keys.begin(); ) {
      map.emplace_front(
        make_tv<KindOfPersistentString>(*--it),
        MapElem::SStrKey(popC(env))
      );
    }
    push(env, dict_map(std::move(map)));
    effect_free(env);
    constprop(env);
  }
  
  void in(ISS& env, const bc::NewVec& op) {
    auto elems = std::vector<Type>{};
    elems.reserve(op.arg1);
    for (auto i = uint32_t{0}; i < op.arg1; ++i) {
      elems.push_back(std::move(topC(env, op.arg1 - i - 1)));
    }
    discard(env, op.arg1);
    effect_free(env);
    constprop(env);
    push(env, vec(std::move(elems)));
  }
  
  void in(ISS& env, const bc::NewKeysetArray& op) {
    assertx(op.arg1 > 0);
    auto map = MapElems{};
    auto ty = TBottom;
    auto useMap = true;
    auto bad = false;
    auto effectful = false;
    for (auto i = uint32_t{0}; i < op.arg1; ++i) {
      auto [key, promotion] = promote_classlike_to_key(popC(env));
  
      auto const keyValid = key.subtypeOf(BArrKey);
      if (!keyValid) key = intersection_of(std::move(key), TArrKey);
      if (key.is(BBottom)) {
        bad = true;
        useMap = false;
        effectful = true;
      }
  
      if (useMap) {
        if (auto const v = tv(key)) {
          map.emplace_front(*v, MapElem::KeyFromType(key, key));
        } else {
          useMap = false;
        }
      }
  
      ty |= std::move(key);
      effectful |= !keyValid || (promotion == Promotion::YesMightThrow);
    }
  
    if (!effectful) {
      effect_free(env);
      constprop(env);
    }
  
    if (useMap) {
      push(env, keyset_map(std::move(map)));
    } else if (!bad) {
      push(env, keyset_n(ty));
    } else {
      assertx(effectful);
      unreachable(env);
      push(env, TBottom);
    }
  }
  
  void in(ISS& env, const bc::AddElemC&) {
    auto const v = topC(env, 0);
    auto const [k, promotion] = promote_classlike_to_key(topC(env, 1));
    auto const promoteMayThrow = (promotion == Promotion::YesMightThrow);
  
    auto inTy = (env.state.stack.end() - 3).unspecialize();
    // Unspecialize modifies the stack location
    if (env.undo) env.undo->onStackWrite(env.state.stack.size() - 3, inTy);
  
    auto outTy = [&] (const Type& key) -> Optional<Type> {
      if (!key.subtypeOf(BArrKey)) return std::nullopt;
      if (inTy.subtypeOf(BDict)) {
        auto const r = array_like_set(std::move(inTy), key, v);
        if (!r.second) return r.first;
      }
      return std::nullopt;
    }(k);
  
    if (outTy && !promoteMayThrow && will_reduce(env)) {
      if (!env.trackedElems.empty() &&
          env.trackedElems.back().depth + 3 == env.state.stack.size()) {
        auto const handled = [&] (const Type& key) {
          if (!key.subtypeOf(BArrKey)) return false;
          auto ktv = tv(key);
          if (!ktv) return false;
          auto vtv = tv(v);
          if (!vtv) return false;
          return mutate_add_elem_array(env, [&](ArrayData** arr) {
            *arr = (*arr)->setMove(*ktv, *vtv);
          });
        }(k);
        if (handled) {
          (env.state.stack.end() - 3)->type = std::move(*outTy);
          reduce(env, bc::PopC {}, bc::PopC {});
          ITRACE(2, "(addelem* -> {}\n",
                 show(env.ctx.func,
                      env.replacedBcs[env.trackedElems.back().idx - env.unchangedBcs]));
          return;
        }
      } else {
        if (start_add_elem(env, *outTy, Op::AddElemC)) return;
      }
    }
  
    discard(env, 3);
    finish_tracked_elems(env, env.state.stack.size());
  
    if (!outTy) return push(env, TInitCell);
  
    if (outTy->subtypeOf(BBottom)) {
      unreachable(env);
    } else if (!promoteMayThrow) {
      effect_free(env);
      constprop(env);
    }
    push(env, std::move(*outTy));
  }
  
  void in(ISS& env, const bc::AddNewElemC&) {
    auto v = topC(env);
    auto inTy = (env.state.stack.end() - 2).unspecialize();
    // Unspecialize modifies the stack location
    if (env.undo) env.undo->onStackWrite(env.state.stack.size() - 2, inTy);
  
    auto outTy = [&] () -> Optional<Type> {
      if (inTy.subtypeOf(BVec | BKeyset)) {
        auto const r = array_like_newelem(std::move(inTy), v);
        if (!r.second) return r.first;
      }
      return std::nullopt;
    }();
  
    if (outTy && will_reduce(env)) {
      if (!env.trackedElems.empty() &&
          env.trackedElems.back().depth + 2 == env.state.stack.size()) {
        auto const handled = [&] {
          auto vtv = tv(v);
          if (!vtv) return false;
          return mutate_add_elem_array(env, [&](ArrayData** arr) {
            *arr = (*arr)->appendMove(*vtv);
          });
        }();
        if (handled) {
          (env.state.stack.end() - 2)->type = std::move(*outTy);
          reduce(env, bc::PopC {});
          ITRACE(2, "(addelem* -> {}\n",
                 show(env.ctx.func,
                      env.replacedBcs[env.trackedElems.back().idx - env.unchangedBcs]));
          return;
        }
      } else {
        if (start_add_elem(env, *outTy, Op::AddNewElemC)) {
          return;
        }
      }
    }
  
    discard(env, 2);
    finish_tracked_elems(env, env.state.stack.size());
  
    if (!outTy) return push(env, TInitCell);
  
    if (outTy->is(BBottom)) {
      unreachable(env);
    } else {
      constprop(env);
    }
    push(env, std::move(*outTy));
  }
  
  void in(ISS& env, const bc::NewCol& op) {
    auto const type = static_cast<CollectionType>(op.subop1);
    auto const name = collections::typeToString(type);
    push(env, objExact(env.index.builtin_class(name)));
    effect_free(env);
  }
  
  void in(ISS& env, const bc::NewPair& /*op*/) {
    popC(env); popC(env);
    auto const name = collections::typeToString(CollectionType::Pair);
    push(env, objExact(env.index.builtin_class(name)));
    effect_free(env);
  }
  
  void in(ISS& env, const bc::ColFromArray& op) {
    auto const src = popC(env);
    auto const type = static_cast<CollectionType>(op.subop1);
    assertx(type != CollectionType::Pair);
    if (type == CollectionType::Vector || type == CollectionType::ImmVector) {
      if (src.subtypeOf(TVec)) effect_free(env);
    } else {
      assertx(type == CollectionType::Map ||
              type == CollectionType::ImmMap ||
              type == CollectionType::Set ||
              type == CollectionType::ImmSet);
      if (src.subtypeOf(TDict)) effect_free(env);
    }
    auto const name = collections::typeToString(type);
    push(env, objExact(env.index.builtin_class(name)));
  }
  
  void in(ISS& env, const bc::CnsE& op) {
    auto t = env.index.lookup_constant(env.ctx, op.str1);
    if (t.strictSubtypeOf(TInitCell)) {
      // constprop will take care of nothrow *if* its a constant; and if
      // its not, we might trigger autoload.
      constprop(env);
    }
    push(env, std::move(t));
  }
  
  namespace {
  
  void clsCnsImpl(ISS& env, const Type& cls, const Type& name) {
    if (!cls.couldBe(BCls) || !name.couldBe(BStr)) {
      push(env, TBottom);
      unreachable(env);
      return;
    }
  
    auto lookup = env.index.lookup_class_constant(env.ctx, cls, name);
    if (lookup.found == TriBool::No) {
      push(env, TBottom);
      unreachable(env);
      return;
    }
  
    if (cls.subtypeOf(BCls) &&
        name.subtypeOf(BStr) &&
        lookup.found == TriBool::Yes &&
        !lookup.mightThrow) {
      constprop(env);
      effect_free(env);
    }
  
    push(env, std::move(lookup.ty));
  }
  
  }
  
  void in(ISS& env, const bc::ClsCns& op) {
    auto const cls = topC(env);
  
    if (cls.subtypeOf(BCls) && is_specialized_cls(cls)) {
      auto const dcls = dcls_of(cls);
      if (dcls.type == DCls::Exact) {
        return reduce(env, bc::PopC {}, bc::ClsCnsD { op.str1, dcls.cls.name() });
      }
    }
  
    popC(env);
    clsCnsImpl(env, cls, sval(op.str1));
  }
  
  void in(ISS& env, const bc::ClsCnsL& op) {
    auto const cls = topC(env);
    auto const name = locRaw(env, op.loc1);
  
    if (name.subtypeOf(BStr) && is_specialized_string(name)) {
      return reduce(env, bc::ClsCns { sval_of(name) });
    }
  
    popC(env);
    clsCnsImpl(env, cls, name);
  }
  
  void in(ISS& env, const bc::ClsCnsD& op) {
    auto const rcls = env.index.resolve_class(env.ctx, op.str2);
    if (!rcls || !rcls->resolved()) {
      push(env, TInitCell);
      return;
    }
    clsCnsImpl(env, clsExact(*rcls), sval(op.str1));
  }
  
  void in(ISS& env, const bc::File&)   { effect_free(env); push(env, TSStr); }
  void in(ISS& env, const bc::Dir&)    { effect_free(env); push(env, TSStr); }
  void in(ISS& env, const bc::Method&) { effect_free(env); push(env, TSStr); }
  
  void in(ISS& env, const bc::FuncCred&) { effect_free(env); push(env, TObj); }
  
  void in(ISS& env, const bc::ClassName& op) {
    auto const ty = topC(env);
    if (ty.subtypeOf(BCls) && is_specialized_cls(ty)) {
      auto const dcls = dcls_of(ty);
      if (dcls.type == DCls::Exact) {
        return reduce(env,
                      bc::PopC {},
                      bc::String { dcls.cls.name() });
      }
      effect_free(env);
    }
    popC(env);
    push(env, TSStr);
  }
  
  void in(ISS& env, const bc::LazyClassFromClass&) {
    auto const ty = topC(env);
    if (ty.subtypeOf(BCls) && is_specialized_cls(ty)) {
      auto const dcls = dcls_of(ty);
      if (dcls.type == DCls::Exact) {
        return reduce(env,
                      bc::PopC {},
                      bc::LazyClass { dcls.cls.name() });
      }
      effect_free(env);
    }
    popC(env);
    push(env, TLazyCls);
  }
  
  void concatHelper(ISS& env, uint32_t n) {
    auto changed = false;
    auto side_effects = false;
    if (will_reduce(env)) {
      auto litstr = [&] (SString next, uint32_t i) -> SString {
        auto const t = topC(env, i);
        auto const v = tv(t);
        if (!v) return nullptr;
        if (!isStringType(v->m_type) && !isIntType(v->m_type)) return nullptr;
        auto const cell = eval_cell_value(
          [&] {
            auto const s = makeStaticString(
              next ?
              StringData::Make(tvAsCVarRef(&*v).toString().get(), next) :
              tvAsCVarRef(&*v).toString().get());
            return make_tv<KindOfString>(s);
          }
        );
        if (!cell) return nullptr;
        return cell->m_data.pstr;
      };
  
      auto fold = [&] (uint32_t slot, uint32_t num, SString result) {
        auto const cell = make_tv<KindOfPersistentString>(result);
        auto const ty = from_cell(cell);
        BytecodeVec bcs{num, bc::PopC {}};
        if (num > 1) bcs.push_back(gen_constant(cell));
        if (slot == 0) {
          reduce(env, std::move(bcs));
        } else {
          insert_after_slot(env, slot, num, num > 1 ? 1 : 0, &ty, bcs);
          reprocess(env);
        }
        n -= num - 1;
        changed = true;
      };
  
      for (auto i = 0; i < n; i++) {
        if (!topC(env, i).subtypeOf(BArrKey)) {
          side_effects = true;
          break;
        }
      }
  
      if (!side_effects) {
        for (auto i = 0; i < n; i++) {
          auto const tracked = !env.trackedElems.empty() &&
            env.trackedElems.back().depth + i + 1 == env.state.stack.size();
          if (tracked) finish_tracked_elems(env, env.trackedElems.back().depth);
          auto const prev = op_from_slot(env, i);
          if (!prev) continue;
          if ((prev->op == Op::Concat && tracked) || prev->op == Op::ConcatN) {
            auto const extra = kill_by_slot(env, i);
            changed = true;
            n += extra;
            i += extra;
          }
        }
      }
  
      SString result = nullptr;
      uint32_t i = 0;
      uint32_t nlit = 0;
      while (i < n) {
        // In order to collapse literals, we need to be able to insert
        // pops, and a constant after the sequence that generated the
        // literals. We can always insert after the last instruction
        // though, and we only need to check the first slot of a
        // sequence.
        auto const next = !i || result || can_insert_after_slot(env, i) ?
          litstr(result, i) : nullptr;
        if (next == staticEmptyString()) {
          if (n == 1) break;
          // don't fold away empty strings if the concat could trigger exceptions
          if (i == 0 && !topC(env, 1).subtypeOf(BArrKey)) break;
          if (n == 2 && i == 1 && !topC(env, 0).subtypeOf(BArrKey)) break;
          assertx(nlit == 0);
          fold(i, 1, next);
          n--;
          continue;
        }
        if (!next) {
          if (nlit > 1) {
            fold(i - nlit, nlit, result);
            i -= nlit - 1;
          }
          nlit = 0;
        } else {
          nlit++;
        }
        result = next;
        i++;
      }
      if (nlit > 1) fold(i - nlit, nlit, result);
    }
  
    if (!changed) {
      discard(env, n);
      if (n == 2 && !side_effects && will_reduce(env)) {
        env.trackedElems.emplace_back(
          env.state.stack.size(),
          env.unchangedBcs + env.replacedBcs.size()
        );
      }
      push(env, TStr);
      return;
    }
  
    if (n == 1) {
      if (!topC(env).subtypeOf(BStr)) {
        return reduce(env, bc::CastString {});
      }
      return reduce(env);
    }
  
    reduce(env);
    // We can't reduce the emitted concats, or we'll end up with
    // infinite recursion.
    env.flags.wasPEI = true;
    env.flags.effectFree = false;
    env.flags.canConstProp = false;
  
    auto concat = [&] (uint32_t num) {
      discard(env, num);
      push(env, TStr);
      if (num == 2) {
        record(env, bc::Concat {});
      } else {
        record(env, bc::ConcatN { num });
      }
    };
  
    while (n >= 4) {
      concat(4);
      n -= 3;
    }
    if (n > 1) concat(n);
  }
  
  void in(ISS& env, const bc::Concat& /*op*/) {
    concatHelper(env, 2);
  }
  
  void in(ISS& env, const bc::ConcatN& op) {
    if (op.arg1 == 2) return reduce(env, bc::Concat {});
    concatHelper(env, op.arg1);
  }
  
  template <class Op, class Fun>
  void arithImpl(ISS& env, const Op& /*op*/, Fun fun) {
    constprop(env);
    auto const t1 = popC(env);
    auto const t2 = popC(env);
    push(env, fun(t2, t1));
  }
  
  void in(ISS& env, const bc::Add& op)    { arithImpl(env, op, typeAdd); }
  void in(ISS& env, const bc::Sub& op)    { arithImpl(env, op, typeSub); }
  void in(ISS& env, const bc::Mul& op)    { arithImpl(env, op, typeMul); }
  void in(ISS& env, const bc::Div& op)    { arithImpl(env, op, typeDiv); }
  void in(ISS& env, const bc::Mod& op)    { arithImpl(env, op, typeMod); }
  void in(ISS& env, const bc::Pow& op)    { arithImpl(env, op, typePow); }
  void in(ISS& env, const bc::BitAnd& op) { arithImpl(env, op, typeBitAnd); }
  void in(ISS& env, const bc::BitOr& op)  { arithImpl(env, op, typeBitOr); }
  void in(ISS& env, const bc::BitXor& op) { arithImpl(env, op, typeBitXor); }
  void in(ISS& env, const bc::AddO& op)   { arithImpl(env, op, typeAddO); }
  void in(ISS& env, const bc::SubO& op)   { arithImpl(env, op, typeSubO); }
  void in(ISS& env, const bc::MulO& op)   { arithImpl(env, op, typeMulO); }
  void in(ISS& env, const bc::Shl& op)    { arithImpl(env, op, typeShl); }
  void in(ISS& env, const bc::Shr& op)    { arithImpl(env, op, typeShr); }
  
  void in(ISS& env, const bc::BitNot& /*op*/) {
    auto const t = popC(env);
    auto const v = tv(t);
    if (!t.couldBe(BInt | BStr | BSStr | BLazyCls | BCls)) {
      return push(env, TBottom);
    }
  
    if (v) {
      constprop(env);
      auto cell = eval_cell([&] {
        auto c = *v;
        tvBitNot(c);
        return c;
      });
      if (cell) return push(env, std::move(*cell));
    }
    push(env, TInitCell);
  }
  
  namespace {
  
  template<bool NSame>
  std::pair<Type,bool> resolveSame(ISS& env) {
    auto const l1 = topStkEquiv(env, 0);
    auto const t1 = topC(env, 0);
    auto const l2 = topStkEquiv(env, 1);
    auto const t2 = topC(env, 1);
  
    auto warningsEnabled =
      (RuntimeOption::EvalEmitClsMethPointers ||
       RuntimeOption::EvalRaiseClassConversionWarning);
  
    auto const result = [&] {
      auto const v1 = tv(t1);
      auto const v2 = tv(t2);
  
      if (l1 == StackDupId ||
          (l1 == l2 && l1 != NoLocalId) ||
          (l1 <= MaxLocalId && l2 <= MaxLocalId && locsAreEquiv(env, l1, l2))) {
        if (!t1.couldBe(BDbl) || !t2.couldBe(BDbl) ||
            (v1 && (v1->m_type != KindOfDouble || !std::isnan(v1->m_data.dbl))) ||
            (v2 && (v2->m_type != KindOfDouble || !std::isnan(v2->m_data.dbl)))) {
          return NSame ? TFalse : TTrue;
        }
      }
  
      if (v1 && v2) {
        if (auto r = eval_cell_value([&]{ return tvSame(*v2, *v1); })) {
          // we wouldn't get here if cellSame raised a warning
          warningsEnabled = false;
          return r != NSame ? TTrue : TFalse;
        }
      }
  
      return NSame ? typeNSame(t1, t2) : typeSame(t1, t2);
    }();
  
    if (warningsEnabled && result == (NSame ? TFalse : TTrue)) {
      warningsEnabled = false;
    }
    return { result, warningsEnabled && compare_might_raise(t1, t2) };
  }
  
  template<bool Negate>
  void sameImpl(ISS& env) {
    if (auto const last = last_op(env)) {
      if (last->op == Op::Null) {
        rewind(env, 1);
        reduce(env, bc::IsTypeC { IsTypeOp::Null });
        if (Negate) reduce(env, bc::Not {});
        return;
      }
      if (auto const prev = last_op(env, 1)) {
        if (prev->op == Op::Null &&
            (last->op == Op::CGetL || last->op == Op::CGetL2 ||
             last->op == Op::CGetQuietL)) {
          auto const loc = [&]() {
            if (last->op == Op::CGetL) {
              return last->CGetL.nloc1;
            } else if (last->op == Op::CGetL2) {
              return last->CGetL2.nloc1;
            } else if (last->op == Op::CGetQuietL) {
              return NamedLocal{kInvalidLocalName, last->CGetQuietL.loc1};
            }
            always_assert(false);
          }();
          rewind(env, 2);
          reduce(env, bc::IsTypeL { loc, IsTypeOp::Null });
          if (Negate) reduce(env, bc::Not {});
          return;
        }
      }
    }
  
    auto pair = resolveSame<Negate>(env);
    discard(env, 2);
  
    if (!pair.second) {
      nothrow(env);
      constprop(env);
    }
  
    push(env, std::move(pair.first));
  }
  
  template<class JmpOp>
  bool sameJmpImpl(ISS& env, Op sameOp, const JmpOp& jmp) {
    const StackElem* elems[2];
    env.state.stack.peek(2, elems, 1);
  
    auto const loc0 = elems[1]->equivLoc;
    auto const loc1 = elems[0]->equivLoc;
    // If loc0 == loc1, either they're both NoLocalId, so there's
    // nothing for us to deduce, or both stack elements are the same
    // value, so the only thing we could deduce is that they are or are
    // not NaN. But we don't track that, so just bail.
    if (loc0 == loc1 || loc0 == StackDupId) return false;
  
    auto const ty0 = elems[1]->type;
    auto const ty1 = elems[0]->type;
    auto const val0 = tv(ty0);
    auto const val1 = tv(ty1);
  
    assertx(!val0 || !val1);
    if ((loc0 == NoLocalId && !val0 && ty1.subtypeOf(ty0)) ||
        (loc1 == NoLocalId && !val1 && ty0.subtypeOf(ty1))) {
      return false;
    }
  
    // Same currently lies about the distinction between Func/Cls/Str
    if (ty0.couldBe(BCls) && ty1.couldBe(BStr)) return false;
    if (ty1.couldBe(BCls) && ty0.couldBe(BStr)) return false;
    if (ty0.couldBe(BLazyCls) && ty1.couldBe(BStr)) return false;
    if (ty1.couldBe(BLazyCls) && ty0.couldBe(BStr)) return false;
  
    auto isect = intersection_of(ty0, ty1);
  
    // Unfortunately, floating point negative zero and positive zero are
    // different, but are identical using as far as Same is concerened. We should
    // avoid refining a value to 0.0 because it compares identically to 0.0
    if (isect.couldBe(dval(0.0)) || isect.couldBe(dval(-0.0))) {
      isect = union_of(isect, TDbl);
    }
  
    discard(env, 1);
  
    auto handle_same = [&] {
      // Currently dce uses equivalency to prove that something isn't
      // the last reference - so we can only assert equivalency here if
      // we know that won't be affected. Its irrelevant for uncounted
      // things, and for TObj and TRes, $x === $y iff $x and $y refer to
      // the same thing.
      if (loc0 <= MaxLocalId &&
          (ty0.subtypeOf(BObj | BRes | BPrim) ||
           ty1.subtypeOf(BObj | BRes | BPrim) ||
           (ty0.subtypeOf(BUnc) && ty1.subtypeOf(BUnc)))) {
        if (loc1 == StackDupId) {
          setStkLocal(env, loc0, 0);
        } else if (loc1 <= MaxLocalId && !locsAreEquiv(env, loc0, loc1)) {
          auto loc = loc0;
          while (true) {
            auto const other = findLocEquiv(env, loc);
            if (other == NoLocalId) break;
            killLocEquiv(env, loc);
            addLocEquiv(env, loc, loc1);
            loc = other;
          }
          addLocEquiv(env, loc, loc1);
        }
      }
      return refineLocation(env, loc1 != NoLocalId ? loc1 : loc0, [&] (Type ty) {
          auto const needsUninit =
            ty.couldBe(BUninit) &&
            !isect.couldBe(BUninit) &&
            isect.couldBe(BInitNull);
          auto ret = ty.subtypeOf(BUnc) ? isect : loosen_staticness(isect);
          if (needsUninit) ret = union_of(std::move(ret), TUninit);
          return ret;
        }
      );
    };
  
    auto handle_differ_side = [&] (LocalId location, const Type& ty) {
      if (!ty.subtypeOf(BInitNull) && !ty.strictSubtypeOf(TBool)) return true;
      return refineLocation(env, location, [&] (Type t) {
        if (ty.subtypeOf(BNull)) {
          t = remove_uninit(std::move(t));
          if (t.couldBe(BInitNull) && !t.subtypeOf(BInitNull)) {
            t = unopt(std::move(t));
          }
          return t;
        } else if (ty.strictSubtypeOf(TBool) && t.subtypeOf(BBool)) {
          return ty == TFalse ? TTrue : TFalse;
        }
        return t;
      });
    };
  
    auto handle_differ = [&] {
      return
        (loc0 == NoLocalId || handle_differ_side(loc0, ty1)) &&
        (loc1 == NoLocalId || handle_differ_side(loc1, ty0));
    };
  
    auto const sameIsJmpTarget =
      (sameOp == Op::Same) == (JmpOp::op == Op::JmpNZ);
  
    auto save = env.state;
    auto const target_reachable = sameIsJmpTarget ?
      handle_same() : handle_differ();
    if (!target_reachable) jmp_nevertaken(env);
    // swap, so we can restore this state if the branch is always taken.
    env.state.swap(save);
    if (!(sameIsJmpTarget ? handle_differ() : handle_same())) {
      jmp_setdest(env, jmp.target1);
      env.state.copy_from(std::move(save));
    } else if (target_reachable) {
      env.propagate(jmp.target1, &save);
    }
  
    return true;
  }
  
  bc::JmpNZ invertJmp(const bc::JmpZ& jmp) { return bc::JmpNZ { jmp.target1 }; }
  bc::JmpZ invertJmp(const bc::JmpNZ& jmp) { return bc::JmpZ { jmp.target1 }; }
  
  }
  
  void in(ISS& env, const bc::Same&)  { sameImpl<false>(env); }
  void in(ISS& env, const bc::NSame&) { sameImpl<true>(env); }
  
  template<class Fun>
  void cmpImpl(ISS& env, Fun fun) {
    auto const t1 = popC(env);
    auto const t2 = popC(env);
    auto const v1 = tv(t1);
    auto const v2 = tv(t2);
    if (v1 && v2) {
      if (auto r = eval_cell_value([&]{ return fun(*v2, *v1); })) {
        constprop(env);
        return push(env, *r ? TTrue : TFalse);
      }
    }
    // TODO_4: evaluate when these can throw, non-constant type stuff.
    push(env, TBool);
  }
  
  namespace {
  
  bool couldBeStringish(const Type& t) {
    return t.couldBe(BCls | BLazyCls | BStr);
  }
  
  bool everEq(const Type& t1, const Type& t2) {
    // for comparison purposes we need to be careful about these coercions
    if (couldBeStringish(t1) && couldBeStringish(t2)) return true;
    return loosen_all(t1).couldBe(loosen_all(t2));
  }
  
  bool cmpWillThrow(const Type& t1, const Type& t2) {
    // for comparison purposes we need to be careful about these coercions
    if (couldBeStringish(t1) && couldBeStringish(t2)) return false;
  
    auto couldBeIntAndDbl = [](const Type& t1, const Type& t2) {
      return t1.couldBe(BInt) && t2.couldBe(BDbl);
    };
     // relational comparisons allow for int v dbl
    if (couldBeIntAndDbl(t1, t2) || couldBeIntAndDbl(t2, t1)) return false;
  
    return !loosen_to_datatype(t1).couldBe(loosen_to_datatype(t2));
  }
  
  void eqImpl(ISS& env, bool eq) {
   auto rs = resolveSame<false>(env);
    if (rs.first == TTrue) {
      if (!rs.second) constprop(env);
      discard(env, 2);
      return push(env, eq ? TTrue : TFalse);
    }
  
    if (!everEq(topC(env, 0), topC(env, 1))) {
      discard(env, 2);
      return push(env, eq ? TFalse : TTrue);
    }
  
    cmpImpl(env, [&] (TypedValue c1, TypedValue c2) {
      return tvEqual(c1, c2) == eq;
    });
  }
  
  bool cmpThrowCheck(ISS& env, const Type& t1, const Type& t2) {
    if (!cmpWillThrow(t1, t2)) return false;
    discard(env, 2);
    push(env, TBottom);
    unreachable(env);
    return true;
  }
  
  }
  
  void in(ISS& env, const bc::Eq&) { eqImpl(env, true); }
  void in(ISS& env, const bc::Neq&) { eqImpl(env, false); }
  
  void in(ISS& env, const bc::Lt&) {
    if (cmpThrowCheck(env, topC(env, 0), topC(env, 1))) return;
    cmpImpl(env, static_cast<bool (*)(TypedValue, TypedValue)>(tvLess));
  }
  void in(ISS& env, const bc::Gt&) {
    if (cmpThrowCheck(env, topC(env, 0), topC(env, 1))) return;
    cmpImpl(env, static_cast<bool (*)(TypedValue, TypedValue)>(tvGreater));
  }
  void in(ISS& env, const bc::Lte&) {
    if (cmpThrowCheck(env, topC(env, 0), topC(env, 1))) return;
    cmpImpl(env, tvLessOrEqual);
  }
  void in(ISS& env, const bc::Gte&) {
    if (cmpThrowCheck(env, topC(env, 0), topC(env, 1))) return;
    cmpImpl(env, tvGreaterOrEqual);
  }
  
  void in(ISS& env, const bc::Cmp&) {
    auto const t1 = topC(env, 0);
    auto const t2 = topC(env, 1);
    if (cmpThrowCheck(env, t1, t2)) return;
    discard(env, 2);
    if (t1 == t2) {
      auto const v1 = tv(t1);
      auto const v2 = tv(t2);
      if (v1 && v2) {
        if (auto r = eval_cell_value([&]{ return ival(tvCompare(*v2, *v1)); })) {
          constprop(env);
          return push(env, std::move(*r));
        }
      }
    }
    // TODO_4: evaluate when these can throw, non-constant type stuff.
    push(env, TInt);
  }
  
  void castBoolImpl(ISS& env, const Type& t, bool negate) {
    nothrow(env);
    constprop(env);
  
    auto const e = emptiness(t);
    switch (e) {
      case Emptiness::Empty:
      case Emptiness::NonEmpty:
        return push(env, (e == Emptiness::Empty) == negate ? TTrue : TFalse);
      case Emptiness::Maybe:
        break;
    }
  
    push(env, TBool);
  }
  
  void in(ISS& env, const bc::Not&) {
    castBoolImpl(env, popC(env), true);
  }
  
  void in(ISS& env, const bc::CastBool&) {
    auto const t = topC(env);
    if (t.subtypeOf(BBool)) return reduce(env);
    castBoolImpl(env, popC(env), false);
  }
  
  void in(ISS& env, const bc::CastInt&) {
    auto const t = topC(env);
    if (t.subtypeOf(BInt)) return reduce(env);
    constprop(env);
    popC(env);
    // Objects can raise a warning about converting to int.
    if (!t.couldBe(BObj)) nothrow(env);
    if (auto const v = tv(t)) {
      auto cell = eval_cell([&] {
        return make_tv<KindOfInt64>(tvToInt(*v));
      });
      if (cell) return push(env, std::move(*cell));
    }
    push(env, TInt);
  }
  
  // Handle a casting operation, where "target" is the type being casted to. If
  // "fn" is provided, it will be called to cast any constant inputs. If "elide"
  // is set to true, if the source type is the same as the destination, the cast
  // will be optimized away.
  void castImpl(ISS& env, Type target, void(*fn)(TypedValue*)) {
    auto const t = topC(env);
    if (t.subtypeOf(target)) return reduce(env);
    popC(env);
  
    if (fn) {
      if (auto val = tv(t)) {
        if (auto result = eval_cell([&] { fn(&*val); return *val; })) {
          constprop(env);
          target = *result;
        }
      }
    }
    push(env, std::move(target));
  }
  
  void in(ISS& env, const bc::CastDouble&) {
    castImpl(env, TDbl, tvCastToDoubleInPlace);
  }
  
  void in(ISS& env, const bc::CastString&) {
    castImpl(env, TStr, tvCastToStringInPlace);
  }
  
  void in(ISS& env, const bc::CastDict&)   {
    castImpl(env, TDict, tvCastToDictInPlace);
  }
  
  void in(ISS& env, const bc::CastVec&)    {
    castImpl(env, TVec, tvCastToVecInPlace);
  }
  
  void in(ISS& env, const bc::CastKeyset&) {
    castImpl(env, TKeyset, tvCastToKeysetInPlace);
  }
  
  void in(ISS& env, const bc::DblAsBits&) {
    effect_free(env);
    constprop(env);
  
    auto const ty = popC(env);
    if (!ty.couldBe(BDbl)) return push(env, ival(0));
  
    if (auto val = tv(ty)) {
      assertx(isDoubleType(val->m_type));
      val->m_type = KindOfInt64;
      push(env, from_cell(*val));
      return;
    }
  
    push(env, TInt);
  }
  
  void in(ISS& env, const bc::Print& /*op*/) {
    popC(env);
    push(env, ival(1));
  }
  
  void in(ISS& env, const bc::Clone& /*op*/) {
    auto val = popC(env);
    if (!val.subtypeOf(BObj)) {
      val &= TObj;
      if (val.is(BBottom)) unreachable(env);
    }
    push(env, std::move(val));
  }
  
  void in(ISS& env, const bc::Exit&)  { popC(env); push(env, TInitNull); }
  void in(ISS& env, const bc::Fatal&) { popC(env); }
  
  void in(ISS& /*env*/, const bc::JmpNS&) {
    always_assert(0 && "blocks should not contain JmpNS instructions");
  }
  
  void in(ISS& /*env*/, const bc::Jmp&) {
    always_assert(0 && "blocks should not contain Jmp instructions");
  }
  
  void in(ISS& env, const bc::Select& op) {
    auto const cond = topC(env);
    auto const t = topC(env, 1);
    auto const f = topC(env, 2);
  
    effect_free(env);
    constprop(env);
  
    switch (emptiness(cond)) {
      case Emptiness::Maybe:
        discard(env, 3);
        push(env, union_of(t, f));
        return;
      case Emptiness::NonEmpty:
        discard(env, 3);
        push(env, t);
        return;
      case Emptiness::Empty:
        return reduce(env, bc::PopC {}, bc::PopC {});
    }
    not_reached();
  }
  
  namespace {
  
  template<class JmpOp>
  bool isTypeHelper(ISS& env,
                    IsTypeOp typeOp,
                    LocalId location,
                    Op op,
                    const JmpOp& jmp) {
    if (typeOp == IsTypeOp::Scalar || typeOp == IsTypeOp::LegacyArrLike ||
        typeOp == IsTypeOp::Func) {
      return false;
    }
  
    auto const val = [&] {
      if (op != Op::IsTypeC) return locRaw(env, location);
      const StackElem* elem;
      env.state.stack.peek(1, &elem, 1);
      location = elem->equivLoc;
      return elem->type;
    }();
  
    if (location == NoLocalId || !val.subtypeOf(BCell)) return false;
  
    // If the type could be ClsMeth and Arr/Vec, skip location refining.
    // Otherwise, refine location based on the testType.
    auto testTy = type_of_istype(typeOp);
  
    assertx(val.couldBe(testTy) &&
            (!val.subtypeOf(testTy) || val.subtypeOf(BObj)));
  
    discard(env, 1);
  
    if (op == Op::IsTypeC) {
      if (!is_type_might_raise(testTy, val)) nothrow(env);
    } else if (op == Op::IssetL) {
      nothrow(env);
    } else if (!locCouldBeUninit(env, location) &&
               !is_type_might_raise(testTy, val)) {
      nothrow(env);
    }
  
    auto const negate = (jmp.op == Op::JmpNZ) == (op != Op::IssetL);
    auto const was_true = [&] (Type t) {
      if (testTy.subtypeOf(BNull)) return intersection_of(t, TNull);
      assertx(!testTy.couldBe(BNull));
      return intersection_of(t, testTy);
    };
    auto const was_false = [&] (Type t) {
      auto tinit = remove_uninit(t);
      if (testTy.subtypeOf(BNull)) {
        return (tinit.couldBe(BInitNull) && !tinit.subtypeOf(BInitNull))
          ? unopt(std::move(tinit)) : tinit;
      }
      if (t.couldBe(BInitNull) && !t.subtypeOf(BInitNull)) {
        assertx(!testTy.couldBe(BNull));
        if (unopt(tinit).subtypeOf(testTy)) return TNull;
      }
      return t;
    };
  
    auto const pre = [&] (Type t) {
      return negate ? was_true(std::move(t)) : was_false(std::move(t));
    };
  
    auto const post = [&] (Type t) {
      return negate ? was_false(std::move(t)) : was_true(std::move(t));
    };
  
    refineLocation(env, location, pre, jmp.target1, post);
    return true;
  }
  
  // If the current function is a memoize wrapper, return the inferred return type
  // of the function being wrapped along with if the wrapped function is effect
  // free.
  std::pair<Type, bool> memoizeImplRetType(ISS& env) {
    always_assert(env.ctx.func->isMemoizeWrapper);
  
    // Lookup the wrapped function. This should always resolve to a precise
    // function but we don't rely on it.
    auto const memo_impl_func = [&] {
      if (env.ctx.func->cls) {
        auto const clsTy = selfClsExact(env);
        return env.index.resolve_method(
          env.ctx,
          clsTy ? *clsTy : TCls,
          memoize_impl_name(env.ctx.func)
        );
      }
      return env.index.resolve_func(env.ctx, memoize_impl_name(env.ctx.func));
    }();
  
    // Infer the return type of the wrapped function, taking into account the
    // types of the parameters for context sensitive types.
    auto const numArgs = env.ctx.func->params.size();
    CompactVector<Type> args{numArgs};
    for (auto i = LocalId{0}; i < numArgs; ++i) {
      args[i] = locAsCell(env, i);
    }
  
    // Determine the context the wrapped function will be called on.
    auto const ctxType = [&]() -> Type {
      if (env.ctx.func->cls) {
        if (env.ctx.func->attrs & AttrStatic) {
          // The class context for static methods is the method's class,
          // if LSB is not specified.
          auto const clsTy =
            env.ctx.func->isMemoizeWrapperLSB ?
            selfCls(env) :
            selfClsExact(env);
          return clsTy ? *clsTy : TCls;
        } else {
          return thisTypeNonNull(env);
        }
      }
      return TBottom;
    }();
  
    auto retTy = env.index.lookup_return_type(
      env.ctx,
      &env.collect.methods,
      args,
      ctxType,
      memo_impl_func
    );
    auto const effectFree = env.index.is_effect_free(memo_impl_func);
    // Regardless of anything we know the return type will be an InitCell (this is
    // a requirement of memoize functions).
    if (!retTy.subtypeOf(BInitCell)) return { TInitCell, effectFree };
    return { retTy, effectFree };
  }
  
  template<class JmpOp>
  bool instanceOfJmpImpl(ISS& env,
                         const bc::InstanceOfD& inst,
                         const JmpOp& jmp) {
  
    const StackElem* elem;
    env.state.stack.peek(1, &elem, 1);
  
    auto const locId = elem->equivLoc;
    if (locId == NoLocalId || interface_supports_non_objects(inst.str1)) {
      return false;
    }
    auto const rcls = env.index.resolve_class(env.ctx, inst.str1);
    if (!rcls) return false;
  
    auto const val = elem->type;
    auto const instTy = subObj(*rcls);
    assertx(!val.subtypeOf(instTy) && val.couldBe(instTy));
  
    // If we have an optional type, whose unopt is guaranteed to pass
    // the instanceof check, then failing to pass implies it was null.
    auto const fail_implies_null =
      val.couldBe(BInitNull) &&
      !val.subtypeOf(BInitNull) &&
      unopt(val).subtypeOf(instTy);
  
    discard(env, 1);
    auto const negate = jmp.op == Op::JmpNZ;
    auto const result = [&] (Type t, bool pass) {
      return pass ? instTy : fail_implies_null ? TNull : t;
    };
    auto const pre  = [&] (Type t) { return result(t, negate); };
    auto const post = [&] (Type t) { return result(t, !negate); };
    refineLocation(env, locId, pre, jmp.target1, post);
    return true;
  }
  
  template<class JmpOp>
  bool isTypeStructCJmpImpl(ISS& env,
                            const bc::IsTypeStructC& inst,
                            const JmpOp& jmp) {
  
    const StackElem* elems[2];
    env.state.stack.peek(2, elems, 1);
  
    auto const locId = elems[0]->equivLoc;
    if (locId == NoLocalId) return false;
  
    auto const a = tv(elems[1]->type);
    if (!a) return false;
    // if it wasn't valid, the JmpOp wouldn't be reachable
    assertx(isValidTSType(*a, false));
  
    auto const is_nullable_ts = is_ts_nullable(a->m_data.parr);
    auto const ts_kind = get_ts_kind(a->m_data.parr);
    // type_of_type_structure does not resolve these types.  It is important we
    // do resolve them here, or we may have issues when we reduce the checks to
    // InstanceOfD checks.  This logic performs the same exact refinement as
    // instanceOfD will.
    if (is_nullable_ts ||
        (ts_kind != TypeStructure::Kind::T_class &&
         ts_kind != TypeStructure::Kind::T_interface &&
         ts_kind != TypeStructure::Kind::T_xhp &&
         ts_kind != TypeStructure::Kind::T_unresolved)) {
      return false;
    }
  
    auto const clsName = get_ts_classname(a->m_data.parr);
    auto const rcls = env.index.resolve_class(env.ctx, clsName);
    if (!rcls ||
        !rcls->resolved() ||
        rcls->cls()->attrs & AttrEnum ||
        interface_supports_non_objects(clsName)) {
      return false;
    }
  
    auto const val = elems[0]->type;
    auto const instTy = subObj(*rcls);
    if (val.subtypeOf(instTy) || !val.couldBe(instTy)) {
      return false;
    }
  
    // If we have an optional type, whose unopt is guaranteed to pass
    // the instanceof check, then failing to pass implies it was null.
    auto const fail_implies_null =
      val.couldBe(BInitNull) &&
      !val.subtypeOf(BInitNull) &&
      unopt(val).subtypeOf(instTy);
  
    discard(env, 1);
  
    auto const negate = jmp.op == Op::JmpNZ;
    auto const result = [&] (Type t, bool pass) {
      return pass ? instTy : fail_implies_null ? TNull : t;
    };
    auto const pre  = [&] (Type t) { return result(t, negate); };
    auto const post = [&] (Type t) { return result(t, !negate); };
    refineLocation(env, locId, pre, jmp.target1, post);
    return true;
  }
  
  template<class JmpOp>
  void jmpImpl(ISS& env, const JmpOp& op) {
    auto const Negate = std::is_same<JmpOp, bc::JmpNZ>::value;
    auto const location = topStkEquiv(env);
    auto const e = emptiness(topC(env));
    if (e == (Negate ? Emptiness::NonEmpty : Emptiness::Empty)) {
      reduce(env, bc::PopC {});
      return jmp_setdest(env, op.target1);
    }
  
    if (e == (Negate ? Emptiness::Empty : Emptiness::NonEmpty) ||
        (next_real_block(env.ctx.func, env.blk.fallthrough) ==
         next_real_block(env.ctx.func, op.target1))) {
      return reduce(env, bc::PopC{});
    }
  
    auto fix = [&] {
      if (env.flags.jmpDest == NoBlockId) return;
      auto const jmpDest = env.flags.jmpDest;
      env.flags.jmpDest = NoBlockId;
      rewind(env, op);
      reduce(env, bc::PopC {});
      env.flags.jmpDest = jmpDest;
    };
  
    if (auto const last = last_op(env)) {
      if (last->op == Op::Not) {
        rewind(env, 1);
        return reduce(env, invertJmp(op));
      }
      if (last->op == Op::Same || last->op == Op::NSame) {
        if (sameJmpImpl(env, last->op, op)) return fix();
      } else if (last->op == Op::IssetL) {
        if (isTypeHelper(env,
                         IsTypeOp::Null,
                         last->IssetL.loc1,
                         last->op,
                         op)) {
          return fix();
        }
      } else if (last->op == Op::IsTypeL) {
        if (isTypeHelper(env,
                         last->IsTypeL.subop2,
                         last->IsTypeL.nloc1.id,
                         last->op,
                         op)) {
          return fix();
        }
      } else if (last->op == Op::IsTypeC) {
        if (isTypeHelper(env,
                         last->IsTypeC.subop1,
                         NoLocalId,
                         last->op,
                         op)) {
          return fix();
        }
      } else if (last->op == Op::InstanceOfD) {
        if (instanceOfJmpImpl(env, last->InstanceOfD, op)) return fix();
      } else if (last->op == Op::IsTypeStructC) {
        if (isTypeStructCJmpImpl(env, last->IsTypeStructC, op)) return fix();
      }
    }
  
    popC(env);
    effect_free(env);
  
    if (location == NoLocalId) return env.propagate(op.target1, &env.state);
  
    refineLocation(env, location,
                   Negate ? assert_nonemptiness : assert_emptiness,
                   op.target1,
                   Negate ? assert_emptiness : assert_nonemptiness);
    return fix();
  }
  
  } // namespace
  
  void in(ISS& env, const bc::JmpNZ& op) { jmpImpl(env, op); }
  void in(ISS& env, const bc::JmpZ& op)  { jmpImpl(env, op); }
  
  void in(ISS& env, const bc::Switch& op) {
    const auto t = topC(env);
    const auto v = tv(t);
  
    auto bail = [&] {
      popC(env);
      forEachTakenEdge(op, [&] (BlockId id) {
          env.propagate(id, &env.state);
      });
    };
  
    auto go = [&] (BlockId blk) {
      reduce(env, bc::PopC {});
      return jmp_setdest(env, blk);
    };
  
    if (!t.couldBe(BInt)) {
      if (op.subop1 == SwitchKind::Unbounded) return bail();
      return go(op.targets.back());
    }
  
    if (!v) return bail();
  
    auto num_elems = op.targets.size();
    if (op.subop1 == SwitchKind::Unbounded) {
      if (v->m_data.num < 0 || v->m_data.num >= num_elems) return bail();
      return go(op.targets[v->m_data.num]);
    }
  
    assertx(num_elems > 2);
    num_elems -= 2;
    auto const i = v->m_data.num - op.arg2;
    return i >= 0 && i < num_elems ? go(op.targets[i]) : go(op.targets.back());
  }
  
  void in(ISS& env, const bc::SSwitch& op) {
    const auto t = topC(env);
    const auto v = tv(t);
  
    if (!couldBeStringish(t)) {
      reduce(env, bc::PopC {});
      return jmp_setdest(env, op.targets.back().second);
    }
  
    if (v) {
      for (auto& kv : op.targets) {
        auto match = eval_cell_value([&] {
          if (!kv.first) return true;
          return v->m_data.pstr->equal(kv.first);
        });
  
        if (!match) break;
        if (*match) {
          reduce(env, bc::PopC {});
          return jmp_setdest(env, kv.second);
        }
      }
    }
  
    popC(env);
    forEachTakenEdge(op, [&] (BlockId id) {
        env.propagate(id, &env.state);
    });
  }
  
  void in(ISS& env, const bc::RetC& /*op*/) {
    auto const locEquiv = topStkLocal(env);
    doRet(env, popC(env), false);
    if (locEquiv != NoLocalId && locEquiv < env.ctx.func->params.size()) {
      env.flags.retParam = locEquiv;
    }
  }
  void in(ISS& env, const bc::RetM& op) {
    std::vector<Type> ret(op.arg1);
    for (int i = 0; i < op.arg1; i++) {
      ret[op.arg1 - i - 1] = popC(env);
    }
    doRet(env, vec(std::move(ret)), false);
  }
  
  void in(ISS& env, const bc::RetCSuspended&) {
    always_assert(env.ctx.func->isAsync && !env.ctx.func->isGenerator);
  
    auto const t = popC(env);
    doRet(
      env,
      is_specialized_wait_handle(t) ? wait_handle_inner(t) : TInitCell,
      false
    );
  }
  
  void in(ISS& env, const bc::Throw& /*op*/) {
    popC(env);
  }
  
  void in(ISS& env, const bc::ThrowNonExhaustiveSwitch& /*op*/) {}
  
  void in(ISS& env, const bc::RaiseClassStringConversionWarning& /*op*/) {}
  
  void in(ISS& env, const bc::ChainFaults&) {
    popC(env);
  }
  
  void in(ISS& env, const bc::NativeImpl&) {
    killLocals(env);
  
    if (is_collection_method_returning_this(env.ctx.cls, env.ctx.func)) {
      auto const resCls = env.index.builtin_class(env.ctx.cls->name);
      return doRet(env, objExact(resCls), true);
    }
  
    if (env.ctx.func->nativeInfo) {
      return doRet(env, native_function_return_type(env.ctx.func), true);
    }
    doRet(env, TInitCell, true);
  }
  
  void in(ISS& env, const bc::CGetL& op) {
    if (locIsThis(env, op.nloc1.id)) {
      auto const& ty = peekLocRaw(env, op.nloc1.id);
      if (!ty.subtypeOf(BInitNull)) {
        auto const subop = ty.couldBe(BUninit) ?
          BareThisOp::Notice : ty.couldBe(BNull) ?
          BareThisOp::NoNotice : BareThisOp::NeverNull;
        return reduce(env, bc::BareThis { subop });
      }
    }
    if (auto const last = last_op(env)) {
      if (last->op == Op::PopL &&
          op.nloc1.id == last->PopL.loc1) {
        reprocess(env);
        rewind(env, 1);
        setLocRaw(env, op.nloc1.id, TCell);
        return reduce(env, bc::SetL { op.nloc1.id });
      }
    }
    if (!peekLocCouldBeUninit(env, op.nloc1.id)) {
      auto const minLocEquiv = findMinLocEquiv(env, op.nloc1.id, false);
      auto const loc = minLocEquiv != NoLocalId ? minLocEquiv : op.nloc1.id;
      return reduce(env, bc::CGetQuietL { loc });
    }
    mayReadLocal(env, op.nloc1.id);
    push(env, locAsCell(env, op.nloc1.id), op.nloc1.id);
  }
  
  void in(ISS& env, const bc::CGetQuietL& op) {
    if (locIsThis(env, op.loc1)) {
      return reduce(env, bc::BareThis { BareThisOp::NoNotice });
    }
    if (auto const last = last_op(env)) {
      if (last->op == Op::PopL &&
          op.loc1 == last->PopL.loc1) {
        reprocess(env);
        rewind(env, 1);
        setLocRaw(env, op.loc1, TCell);
        return reduce(env, bc::SetL { op.loc1 });
      }
    }
    auto const minLocEquiv = findMinLocEquiv(env, op.loc1, true);
    if (minLocEquiv != NoLocalId) {
      return reduce(env, bc::CGetQuietL { minLocEquiv });
    }
  
    effect_free(env);
    constprop(env);
    mayReadLocal(env, op.loc1);
    push(env, locAsCell(env, op.loc1), op.loc1);
  }
  
  void in(ISS& env, const bc::CUGetL& op) {
    auto ty = locRaw(env, op.loc1);
    effect_free(env);
    constprop(env);
    push(env, std::move(ty), op.loc1);
  }
  
  void in(ISS& env, const bc::PushL& op) {
    auto const minLocEquiv = findMinLocEquiv(env, op.loc1, false);
    if (minLocEquiv != NoLocalId) {
      return reduce(env, bc::CGetQuietL { minLocEquiv }, bc::UnsetL { op.loc1 });
    }
  
    if (auto const last = last_op(env)) {
      if (last->op == Op::PopL &&
          last->PopL.loc1 == op.loc1) {
        // rewind is ok, because we're just going to unset the local
        // (and note the unset can't be a no-op because the PopL set it
        // to an InitCell). But its possible that before the PopL, the
        // local *was* unset, so maybe would have killed the no-op. The
        // only way to fix that is to reprocess the block with the new
        // instruction sequence and see what happens.
        reprocess(env);
        rewind(env, 1);
        return reduce(env, bc::UnsetL { op.loc1 });
      }
    }
  
    if (auto val = tv(peekLocRaw(env, op.loc1))) {
      return reduce(env, bc::UnsetL { op.loc1 }, gen_constant(*val));
    }
  
    impl(env, bc::CGetQuietL { op.loc1 }, bc::UnsetL { op.loc1 });
  }
  
  void in(ISS& env, const bc::CGetL2& op) {
    if (auto const last = last_op(env)) {
      if ((poppable(last->op) && !numPop(*last)) ||
          ((last->op == Op::CGetL || last->op == Op::CGetQuietL) &&
           !peekLocCouldBeUninit(env, op.nloc1.id))) {
        auto const other = *last;
        rewind(env, 1);
        return reduce(env, bc::CGetL { op.nloc1 }, other);
      }
    }
  
    if (!peekLocCouldBeUninit(env, op.nloc1.id)) {
      auto const minLocEquiv = findMinLocEquiv(env, op.nloc1.id, false);
      if (minLocEquiv != NoLocalId) {
        return reduce(env, bc::CGetL2 { { kInvalidLocalName, minLocEquiv } });
      }
      effect_free(env);
    }
    mayReadLocal(env, op.nloc1.id);
    auto loc = locAsCell(env, op.nloc1.id);
    auto topEquiv = topStkLocal(env);
    auto top = popT(env);
    push(env, std::move(loc), op.nloc1.id);
    push(env, std::move(top), topEquiv);
  }
  
  void in(ISS& env, const bc::CGetG&) { popC(env); push(env, TInitCell); }
  
  void in(ISS& env, const bc::CGetS& op) {
    auto const tcls  = popC(env);
    auto const tname = popC(env);
  
    auto const throws = [&] {
      unreachable(env);
      return push(env, TBottom);
    };
  
    if (!tcls.couldBe(BCls)) return throws();
  
    auto lookup = env.index.lookup_static(
      env.ctx,
      env.collect.props,
      tcls,
      tname
    );
  
    if (lookup.found == TriBool::No || lookup.ty.subtypeOf(BBottom)) {
      return throws();
    }
  
    if (checkReadonlyOpThrows(ReadonlyOp::Mutable, op.subop1) &&
      lookup.readOnly == TriBool::Yes) {
      return throws();
    }
    auto const mightReadOnlyThrow = checkReadonlyOpMaybeThrows(ReadonlyOp::Mutable, op.subop1) &&
      (lookup.readOnly == TriBool::Yes || lookup.readOnly == TriBool::Maybe);
  
    if (lookup.found == TriBool::Yes &&
        lookup.lateInit == TriBool::No &&
        !lookup.classInitMightRaise &&
        !mightReadOnlyThrow &&
        tcls.subtypeOf(BCls) &&
        tname.subtypeOf(BStr)) {
      effect_free(env);
      constprop(env);
    }
  
    push(env, std::move(lookup.ty));
  }
  
  void in(ISS& env, const bc::ClassGetC& op) {
    auto const t = topC(env);
  
    if (t.subtypeOf(BCls)) return reduce(env, bc::Nop {});
    popC(env);
  
    if (!t.couldBe(BObj | BCls | BStr | BLazyCls)) {
      unreachable(env);
      push(env, TBottom);
      return;
    }
  
    if (t.subtypeOf(BObj)) {
      effect_free(env);
      push(env, objcls(t));
      return;
    }
  
    if (auto const clsname = getNameFromType(t)) {
      if (auto const rcls = env.index.resolve_class(env.ctx, clsname)) {
        if (rcls->cls()) effect_free(env);
        push(env, clsExact(*rcls));
        return;
      }
    }
  
    push(env, TCls);
  }
  
  void in(ISS& env, const bc::ClassGetTS& op) {
    // TODO(T31677864): implement real optimizations
    auto const ts = popC(env);
    if (!ts.couldBe(BDict)) {
      push(env, TBottom);
      push(env, TBottom);
      return;
    }
  
    push(env, TCls);
    push(env, TOptVec);
  }
  
  void in(ISS& env, const bc::AKExists&) {
    auto const base = popC(env);
    auto const [key, promotion] = promote_classlike_to_key(popC(env));
  
    auto result = TBottom;
    auto effectFree = promotion != Promotion::YesMightThrow;
  
    if (!base.subtypeOf(BObj | BArrLike)) {
      effectFree = false;
      result |= TFalse;
    }
  
    if (base.couldBe(BObj)) {
      effectFree = false;
      result |= TBool;
    }
    if (base.couldBe(BArrLike)) {
      auto const validKey = key.subtypeOf(BArrKey);
      if (!validKey) effectFree = false;
      if (key.couldBe(BArrKey)) {
        auto const elem =
          array_like_elem(base, validKey ? key : intersection_of(key, TArrKey));
        if (elem.first.is(BBottom)) {
          result |= TFalse;
        } else if (elem.second) {
          result |= TTrue;
        } else {
          result |= TBool;
        }
      }
    }
  
    if (result.is(BBottom)) {
      assertx(!effectFree);
      unreachable(env);
    }
    if (effectFree) {
      constprop(env);
      effect_free(env);
    }
    push(env, std::move(result));
  }
  
  void in(ISS& env, const bc::GetMemoKeyL& op) {
    auto const& func = env.ctx.func;
    auto const name = folly::to<std::string>(
      func && func->cls ? func->cls->name->data() : "",
      func && func->cls ? "::" : "",
      func ? func->name->data() : "");
    always_assert(func->isMemoizeWrapper);
  
    auto const rclsIMemoizeParam = env.index.builtin_class(s_IMemoizeParam.get());
    auto const tyIMemoizeParam = subObj(rclsIMemoizeParam);
  
    auto const inTy = locAsCell(env, op.nloc1.id);
  
    // If the local could be uninit, we might raise a warning (as
    // usual). Converting an object to a memo key might invoke PHP code if it has
    // the IMemoizeParam interface, and if it doesn't, we'll throw.
    if (!locCouldBeUninit(env, op.nloc1.id) &&
        !inTy.couldBe(BObj | BVec | BDict)) {
      effect_free(env);
      constprop(env);
    }
  
    // If type constraints are being enforced and the local being turned into a
    // memo key is a parameter, then we can possibly using the type constraint to
    // infer a more efficient memo key mode.
    using MK = MemoKeyConstraint;
    Optional<res::Class> resolvedCls;
    auto const mkc = [&] {
      if (op.nloc1.id >= env.ctx.func->params.size()) return MK::None;
      auto tc = env.ctx.func->params[op.nloc1.id].typeConstraint;
      if (tc.type() == AnnotType::Object) {
        auto res = env.index.resolve_type_name(tc.typeName());
        if (res.type != AnnotType::Object) {
          tc.resolveType(res.type, res.nullable || tc.isNullable());
        } else {
          resolvedCls = env.index.resolve_class(env.ctx, tc.typeName());
        }
      }
      return memoKeyConstraintFromTC(tc);
    }();
  
    // Use the type-constraint to reduce this operation to a more efficient memo
    // mode. Some of the modes can be reduced to simple bytecode operations
    // inline. Even with the type-constraints, we still need to check the inferred
    // type of the local. Something may have possibly clobbered the local between
    // the type-check and this op.
    switch (mkc) {
      case MK::Int:
        // Always an int, so the key is always an identity mapping
        if (inTy.subtypeOf(BInt)) return reduce(env, bc::CGetL { op.nloc1 });
        break;
      case MK::Bool:
        // Always a bool, so the key is the bool cast to an int
        if (inTy.subtypeOf(BBool)) {
          return reduce(env, bc::CGetL { op.nloc1 }, bc::CastInt {});
        }
        break;
      case MK::Str:
        // Always a string, so the key is always an identity mapping
        if (inTy.subtypeOf(BStr)) return reduce(env, bc::CGetL { op.nloc1 });
        break;
      case MK::IntOrStr:
        // Either an int or string, so the key can be an identity mapping
        if (inTy.subtypeOf(BArrKey)) return reduce(env, bc::CGetL { op.nloc1 });
        break;
      case MK::StrOrNull:
        // A nullable string. The key will either be the string or the integer
        // zero.
        if (inTy.subtypeOf(BOptStr)) {
          return reduce(
            env,
            bc::CGetL { op.nloc1 },
            bc::Int { 0 },
            bc::IsTypeL { op.nloc1, IsTypeOp::Null },
            bc::Select {}
          );
        }
        break;
      case MK::IntOrNull:
        // A nullable int. The key will either be the integer, or the static empty
        // string.
        if (inTy.subtypeOf(BOptInt)) {
          return reduce(
            env,
            bc::CGetL { op.nloc1 },
            bc::String { staticEmptyString() },
            bc::IsTypeL { op.nloc1, IsTypeOp::Null },
            bc::Select {}
          );
        }
        break;
      case MK::BoolOrNull:
        // A nullable bool. The key will either be 0, 1, or 2.
        if (inTy.subtypeOf(BOptBool)) {
          return reduce(
            env,
            bc::CGetL { op.nloc1 },
            bc::CastInt {},
            bc::Int { 2 },
            bc::IsTypeL { op.nloc1, IsTypeOp::Null },
            bc::Select {}
          );
        }
        break;
      case MK::Dbl:
        // The double will be converted (losslessly) to an integer.
        if (inTy.subtypeOf(BDbl)) {
          return reduce(env, bc::CGetL { op.nloc1 }, bc::DblAsBits {});
        }
        break;
      case MK::DblOrNull:
        // A nullable double. The key will be an integer, or the static empty
        // string.
        if (inTy.subtypeOf(BOptDbl)) {
          return reduce(
            env,
            bc::CGetL { op.nloc1 },
            bc::DblAsBits {},
            bc::String { staticEmptyString() },
            bc::IsTypeL { op.nloc1, IsTypeOp::Null },
            bc::Select {}
          );
        }
        break;
      case MK::Object:
        // An object. If the object is definitely known to implement IMemoizeParam
        // we can simply call that method, casting the output to ensure its always
        // a string (which is what the generic mode does). If not, it will use the
        // generic mode, which can handle collections or classes which don't
        // implement getInstanceKey.
        if (resolvedCls &&
            resolvedCls->mustBeSubtypeOf(rclsIMemoizeParam) &&
            inTy.subtypeOf(tyIMemoizeParam)) {
          return reduce(
            env,
            bc::CGetL { op.nloc1 },
            bc::NullUninit {},
            bc::FCallObjMethodD {
              FCallArgs(0),
              staticEmptyString(),
              ObjMethodOp::NullThrows,
              s_getInstanceKey.get()
            },
            bc::CastString {}
          );
        }
        break;
      case MK::ObjectOrNull:
        // An object or null. We can use the null safe version of a function call
        // when invoking getInstanceKey and then select from the result of that,
        // or the integer 0. This might seem wasteful, but the JIT does a good job
        // inlining away the call in the null case.
        if (resolvedCls &&
            resolvedCls->mustBeSubtypeOf(rclsIMemoizeParam) &&
            inTy.subtypeOf(opt(tyIMemoizeParam))) {
          return reduce(
            env,
            bc::CGetL { op.nloc1 },
            bc::NullUninit {},
            bc::FCallObjMethodD {
              FCallArgs(0),
              staticEmptyString(),
              ObjMethodOp::NullSafe,
              s_getInstanceKey.get()
            },
            bc::CastString {},
            bc::Int { 0 },
            bc::IsTypeL { op.nloc1, IsTypeOp::Null },
            bc::Select {}
          );
        }
        break;
      case MK::None:
        break;
    }
  
    // No type constraint, or one that isn't usuable. Use the generic memoization
    // scheme which can handle any type:
  
    if (auto const val = tv(inTy)) {
      auto const key = eval_cell(
        [&]{ return HHVM_FN(serialize_memoize_param)(*val); }
      );
      if (key) return push(env, *key);
    }
  
    // Integer keys are always mapped to themselves
    if (inTy.subtypeOf(BInt)) return reduce(env, bc::CGetL { op.nloc1 });
    if (inTy.subtypeOf(BOptInt)) {
      return reduce(
        env,
        bc::CGetL { op.nloc1 },
        bc::String { s_nullMemoKey.get() },
        bc::IsTypeL { op.nloc1, IsTypeOp::Null },
        bc::Select {}
      );
    }
    if (inTy.subtypeOf(BBool)) {
      return reduce(
        env,
        bc::String { s_falseMemoKey.get() },
        bc::String { s_trueMemoKey.get() },
        bc::CGetL { op.nloc1 },
        bc::Select {}
      );
    }
  
    // A memo key can be an integer if the input might be an integer, and is a
    // string otherwise. Booleans and nulls are always static strings.
    auto keyTy = [&]{
      if (inTy.subtypeOf(BOptBool)) return TSStr;
      if (inTy.couldBe(BInt))       return union_of(TInt, TStr);
      return TStr;
    }();
    push(env, std::move(keyTy));
  }
  
  void in(ISS& env, const bc::IssetL& op) {
    if (locIsThis(env, op.loc1)) {
      return reduce(env,
                    bc::BareThis { BareThisOp::NoNotice },
                    bc::IsTypeC { IsTypeOp::Null },
                    bc::Not {});
    }
    effect_free(env);
    constprop(env);
    auto const loc = locAsCell(env, op.loc1);
    if (loc.subtypeOf(BNull))  return push(env, TFalse);
    if (!loc.couldBe(BNull))   return push(env, TTrue);
    push(env, TBool);
  }
  
  void in(ISS& env, const bc::IsUnsetL& op) {
    effect_free(env);
    constprop(env);
    auto const loc = locAsCell(env, op.loc1);
    if (loc.subtypeOf(BUninit))  return push(env, TTrue);
    if (!loc.couldBe(BUninit))   return push(env, TFalse);
    push(env, TBool);
  }
  
  void in(ISS& env, const bc::IssetS& op) {
    auto const tcls  = popC(env);
    auto const tname = popC(env);
  
    if (!tcls.couldBe(BCls)) {
      unreachable(env);
      return push(env, TBottom);
    }
  
    auto lookup = env.index.lookup_static(
      env.ctx,
      env.collect.props,
      tcls,
      tname
    );
  
    if (!lookup.classInitMightRaise &&
        tcls.subtypeOf(BCls) &&
        tname.subtypeOf(BStr)) {
      effect_free(env);
      constprop(env);
    }
  
    if (lookup.ty.subtypeOf(BNull)) return push(env, TFalse);
    if (!lookup.ty.couldBe(BNull) && lookup.lateInit == TriBool::No) {
      return push(env, TTrue);
    }
    push(env, TBool);
  }
  
  void in(ISS& env, const bc::IssetG&) { popC(env); push(env, TBool); }
  
  void isTypeImpl(ISS& env, const Type& locOrCell, const Type& test) {
    if (locOrCell.subtypeOf(test))  return push(env, TTrue);
    if (!locOrCell.couldBe(test))   return push(env, TFalse);
    push(env, TBool);
  }
  
  void isTypeObj(ISS& env, const Type& ty) {
    if (!ty.couldBe(BObj)) return push(env, TFalse);
    if (ty.subtypeOf(BObj)) {
      auto const incompl = objExact(
        env.index.builtin_class(s_PHP_Incomplete_Class.get()));
      if (RO::EvalBuildMayNoticeOnMethCallerHelperIsObject) {
        auto const c =
          objExact(env.index.builtin_class(s_MethCallerHelper.get()));
        if (ty.couldBe(c)) return push(env, TBool);
      }
      if (!ty.couldBe(incompl))  return push(env, TTrue);
      if (ty.subtypeOf(incompl)) return push(env, TFalse);
    }
    push(env, TBool);
  }
  
  template<class Op>
  void isTypeLImpl(ISS& env, const Op& op) {
    auto const loc = locAsCell(env, op.nloc1.id);
    if (!locCouldBeUninit(env, op.nloc1.id) &&
        !is_type_might_raise(op.subop2, loc)) {
      constprop(env);
      effect_free(env);
    }
  
    switch (op.subop2) {
    case IsTypeOp::Scalar: return push(env, TBool);
    case IsTypeOp::LegacyArrLike: return push(env, TBool);
    case IsTypeOp::Obj: return isTypeObj(env, loc);
    case IsTypeOp::Func:
      return loc.couldBe(TFunc) ? push(env, TBool) : push(env, TFalse);
    default: return isTypeImpl(env, loc, type_of_istype(op.subop2));
    }
  }
  
  template<class Op>
  void isTypeCImpl(ISS& env, const Op& op) {
    auto const t1 = popC(env);
    if (!is_type_might_raise(op.subop1, t1)) {
      constprop(env);
      effect_free(env);
    }
  
    switch (op.subop1) {
    case IsTypeOp::Scalar: return push(env, TBool);
    case IsTypeOp::LegacyArrLike: return push(env, TBool);
    case IsTypeOp::Obj: return isTypeObj(env, t1);
    case IsTypeOp::Func:
      return t1.couldBe(TFunc) ? push(env, TBool) : push(env, TFalse);
    default: return isTypeImpl(env, t1, type_of_istype(op.subop1));
    }
  }
  
  void in(ISS& env, const bc::IsTypeC& op) { isTypeCImpl(env, op); }
  void in(ISS& env, const bc::IsTypeL& op) { isTypeLImpl(env, op); }
  
  void in(ISS& env, const bc::InstanceOfD& op) {
    auto t1 = topC(env);
    // Note: InstanceOfD can do autoload if the type might be a type
    // alias, so it's not nothrow unless we know it's an object type.
    if (auto const rcls = env.index.resolve_class(env.ctx, op.str1)) {
      auto result = [&] (const Type& r) {
        nothrow(env);
        if (r != TBool) constprop(env);
        popC(env);
        push(env, r);
      };
      if (!interface_supports_non_objects(rcls->name())) {
        auto const testTy = subObj(*rcls);
        if (t1.subtypeOf(testTy)) return result(TTrue);
        if (!t1.couldBe(testTy)) return result(TFalse);
        if (t1.couldBe(BInitNull) && !t1.subtypeOf(BInitNull)) {
          t1 = unopt(std::move(t1));
          if (t1.subtypeOf(testTy)) {
            return reduce(env, bc::IsTypeC { IsTypeOp::Null }, bc::Not {});
          }
        }
        return result(TBool);
      }
    }
    popC(env);
    push(env, TBool);
  }
  
  void in(ISS& env, const bc::InstanceOf& /*op*/) {
    auto const t1 = topC(env);
    auto const v1 = tv(t1);
    if (v1 && v1->m_type == KindOfPersistentString) {
      return reduce(env, bc::PopC {},
                         bc::InstanceOfD { v1->m_data.pstr });
    }
  
    if (t1.subtypeOf(BObj) && is_specialized_obj(t1)) {
      auto const dobj = dobj_of(t1);
      switch (dobj.type) {
      case DObj::Sub:
        break;
      case DObj::Exact:
        return reduce(env, bc::PopC {},
                           bc::InstanceOfD { dobj.cls.name() });
      }
    }
  
    popC(env);
    popC(env);
    push(env, TBool);
  }
  
  void in(ISS& env, const bc::IsLateBoundCls& op) {
    auto const cls = env.ctx.cls;
    if (cls && !(cls->attrs & AttrTrait)) effect_free(env);
    popC(env);
    return push(env, TBool);
  }
  
  namespace {
  
  bool isValidTypeOpForIsAs(const IsTypeOp& op) {
    switch (op) {
      case IsTypeOp::Null:
      case IsTypeOp::Bool:
      case IsTypeOp::Int:
      case IsTypeOp::Dbl:
      case IsTypeOp::Str:
      case IsTypeOp::Obj:
        return true;
      case IsTypeOp::Res:
      case IsTypeOp::Vec:
      case IsTypeOp::Dict:
      case IsTypeOp::Keyset:
      case IsTypeOp::ArrLike:
      case IsTypeOp::LegacyArrLike:
      case IsTypeOp::Scalar:
      case IsTypeOp::ClsMeth:
      case IsTypeOp::Func:
      case IsTypeOp::Class:
        return false;
    }
    not_reached();
  }
  
  void isTypeStructImpl(ISS& env, SArray inputTS) {
    auto const ts = inputTS;
    auto const t = loosen_likeness(topC(env, 1)); // operand to is/as
  
    bool may_raise = true;
    auto result = [&] (const Type& out) {
      popC(env); // type structure
      popC(env); // operand to is/as
      constprop(env);
      if (!may_raise) nothrow(env);
      return push(env, out);
    };
  
    auto check = [&] (
      const Optional<Type> type,
      const Optional<Type> deopt = std::nullopt
    ) {
      if (!type || is_type_might_raise(*type, t)) return result(TBool);
      auto test = type.value();
      if (t.subtypeOf(test)) return result(TTrue);
      if (!t.couldBe(test) && (!deopt || !t.couldBe(deopt.value()))) {
        return result(TFalse);
      }
      auto const op = type_to_istypeop(test);
      if (!op || !isValidTypeOpForIsAs(op.value())) return result(TBool);
      return reduce(env, bc::PopC {}, bc::IsTypeC { *op });
    };
  
    auto const is_nullable_ts = is_ts_nullable(ts);
    auto const is_definitely_null = t.subtypeOf(BNull);
    auto const is_definitely_not_null = !t.couldBe(BNull);
  
    if (is_nullable_ts && is_definitely_null) return result(TTrue);
  
    auto const ts_type = type_of_type_structure(env.index, env.ctx, ts);
  
    if (is_nullable_ts && !is_definitely_not_null && ts_type == std::nullopt) {
      // Ts is nullable and we know that t could be null but we dont know for sure
      // Also we didn't get a type out of the type structure
      return result(TBool);
    }
  
    if (ts_type && !is_type_might_raise(*ts_type, t)) may_raise = false;
    switch (get_ts_kind(ts)) {
      case TypeStructure::Kind::T_int:
      case TypeStructure::Kind::T_bool:
      case TypeStructure::Kind::T_float:
      case TypeStructure::Kind::T_string:
      case TypeStructure::Kind::T_num:
      case TypeStructure::Kind::T_arraykey:
      case TypeStructure::Kind::T_keyset:
      case TypeStructure::Kind::T_void:
      case TypeStructure::Kind::T_null:
        return check(ts_type);
      case TypeStructure::Kind::T_tuple:
        return check(ts_type, TVec);
      case TypeStructure::Kind::T_shape:
        return check(ts_type, TDict);
      case TypeStructure::Kind::T_dict:
        return check(ts_type);
      case TypeStructure::Kind::T_vec:
        return check(ts_type);
      case TypeStructure::Kind::T_nothing:
      case TypeStructure::Kind::T_noreturn:
        return result(TFalse);
      case TypeStructure::Kind::T_mixed:
      case TypeStructure::Kind::T_dynamic:
        return result(TTrue);
      case TypeStructure::Kind::T_nonnull:
        if (is_definitely_null) return result(TFalse);
        if (is_definitely_not_null) return result(TTrue);
        return reduce(env,
                      bc::PopC {},
                      bc::IsTypeC { IsTypeOp::Null },
                      bc::Not {});
      case TypeStructure::Kind::T_class:
      case TypeStructure::Kind::T_interface:
      case TypeStructure::Kind::T_xhp: {
        auto clsname = get_ts_classname(ts);
        auto const rcls = env.index.resolve_class(env.ctx, clsname);
        if (!rcls || !rcls->resolved() || (ts->exists(s_generic_types) &&
                                           (rcls->cls()->hasReifiedGenerics ||
                                           !isTSAllWildcards(ts)))) {
          // If it is a reified class or has non wildcard generics,
          // we need to bail
          return result(TBool);
        }
        return reduce(env, bc::PopC {}, bc::InstanceOfD { clsname });
      }
      case TypeStructure::Kind::T_unresolved: {
        auto classname = get_ts_classname(ts);
        auto const has_generics = ts->exists(s_generic_types);
        if (!has_generics && classname->isame(s_this.get())) {
          return reduce(env, bc::PopC {}, bc::IsLateBoundCls {});
        }
        auto const rcls = env.index.resolve_class(env.ctx, classname);
        // We can only reduce to instance of if we know for sure that this class
        // can be resolved since instanceof undefined class does not throw
        if (!rcls || !rcls->resolved() || rcls->cls()->attrs & AttrEnum) {
          return result(TBool);
        }
        if (has_generics &&
           (rcls->cls()->hasReifiedGenerics || !isTSAllWildcards(ts))) {
            // If it is a reified class or has non wildcard generics,
            // we need to bail
          return result(TBool);
        }
        return reduce(env, bc::PopC {}, bc::InstanceOfD { rcls->name() });
      }
      case TypeStructure::Kind::T_enum:
      case TypeStructure::Kind::T_resource:
      case TypeStructure::Kind::T_vec_or_dict:
      case TypeStructure::Kind::T_any_array:
        // TODO(T29232862): implement
        return result(TBool);
      case TypeStructure::Kind::T_typeaccess:
      case TypeStructure::Kind::T_darray:
      case TypeStructure::Kind::T_varray:
      case TypeStructure::Kind::T_varray_or_darray:
      case TypeStructure::Kind::T_reifiedtype:
        return result(TBool);
      case TypeStructure::Kind::T_fun:
      case TypeStructure::Kind::T_typevar:
      case TypeStructure::Kind::T_trait:
        // We will error on these at the JIT
        return result(TBool);
    }
  
    not_reached();
  }
  
  const StaticString s_hh_type_structure_no_throw("HH\\type_structure_no_throw");
  
  } // namespace
  
  void in(ISS& env, const bc::IsTypeStructC& op) {
    if (!topC(env).couldBe(BDict)) {
      popC(env);
      popC(env);
      return unreachable(env);
    }
    auto const a = tv(topC(env));
    if (!a || !isValidTSType(*a, false)) {
      popC(env);
      popC(env);
      return push(env, TBool);
    }
    if (op.subop1 == TypeStructResolveOp::Resolve) {
      if (auto const ts = resolve_type_structure(env, a->m_data.parr).sarray()) {
        return reduce(
          env,
          bc::PopC {},
          bc::Dict { ts },
          bc::IsTypeStructC { TypeStructResolveOp::DontResolve }
        );
      }
      if (auto const val = get_ts_this_type_access(a->m_data.parr)) {
        // Convert `$x is this::T` into
        // `$x is type_structure_no_throw(static::class, 'T')`
        // to take advantage of the caching that comes with the type_structure
        return reduce(
          env,
          bc::PopC {},
          bc::NullUninit {},
          bc::NullUninit {},
          bc::LateBoundCls {},
          bc::String {val},
          bc::FCallFuncD {FCallArgs(2), s_hh_type_structure_no_throw.get()},
          bc::IsTypeStructC { TypeStructResolveOp::DontResolve }
        );
      }
    }
    isTypeStructImpl(env, a->m_data.parr);
  }
  
  void in(ISS& env, const bc::ThrowAsTypeStructException& op) {
    popC(env);
    popC(env);
    unreachable(env);
  }
  
  void in(ISS& env, const bc::CombineAndResolveTypeStruct& op) {
    assertx(op.arg1 > 0);
    auto valid = true;
    auto const first = tv(topC(env));
    if (first && isValidTSType(*first, false)) {
      auto const ts = first->m_data.parr;
      // Optimize single input that does not need any combination
      if (op.arg1 == 1) {
        if (auto const r = resolve_type_structure(env, ts).sarray()) {
          return reduce(
            env,
            bc::PopC {},
            bc::Dict { r }
          );
        }
      }
  
      // Optimize double input that needs a single combination and looks of the
      // form ?T, @T or ~T
      if (op.arg1 == 2 && get_ts_kind(ts) == TypeStructure::Kind::T_reifiedtype) {
        BytecodeVec instrs { bc::PopC {} };
        auto const tv_true = gen_constant(make_tv<KindOfBoolean>(true));
        if (ts->exists(s_like.get())) {
          instrs.push_back(gen_constant(make_tv<KindOfString>(s_like.get())));
          instrs.push_back(tv_true);
          instrs.push_back(bc::AddElemC {});
        }
        if (ts->exists(s_nullable.get())) {
          instrs.push_back(gen_constant(make_tv<KindOfString>(s_nullable.get())));
          instrs.push_back(tv_true);
          instrs.push_back(bc::AddElemC {});
        }
        if (ts->exists(s_soft.get())) {
          instrs.push_back(gen_constant(make_tv<KindOfString>(s_soft.get())));
          instrs.push_back(tv_true);
          instrs.push_back(bc::AddElemC {});
        }
        return reduce(env, std::move(instrs));
      }
    }
  
    for (int i = 0; i < op.arg1; ++i) {
      auto const t = popC(env);
      valid &= t.couldBe(BDict);
    }
    if (!valid) return unreachable(env);
    nothrow(env);
    push(env, TDict);
  }
  
  void in(ISS& env, const bc::RecordReifiedGeneric& op) {
    // TODO(T31677864): implement real optimizations
    auto const t = popC(env);
    if (!t.couldBe(BVec)) return unreachable(env);
    if (t.subtypeOf(BVec)) nothrow(env);
    push(env, TSVec);
  }
  
  void in(ISS& env, const bc::CheckReifiedGenericMismatch& op) {
    auto const location = topStkEquiv(env, 0);
    popC(env);
  
    if (location == NoLocalId) return;
    auto const ok = refineLocation(
      env, location,
      [&] (Type) {
        return get_type_of_reified_list(env.ctx.cls->userAttributes);
      }
    );
    if (!ok) unreachable(env);
  }
  
  namespace {
  
  /*
   * If the value on the top of the stack is known to be equivalent to the local
   * its being moved/copied to, return std::nullopt without modifying any
   * state. Otherwise, pop the stack value, perform the set, and return a pair
   * giving the value's type, and any other local its known to be equivalent to.
   */
  template <typename Set>
  Optional<std::pair<Type, LocalId>> moveToLocImpl(ISS& env,
                                                   const Set& op) {
    if (auto const prev = last_op(env, 1)) {
      if (prev->op == Op::CGetL2 &&
          prev->CGetL2.nloc1.id == op.loc1 &&
          last_op(env)->op == Op::Concat) {
        rewind(env, 2);
        reduce(env, bc::SetOpL { op.loc1, SetOpOp::ConcatEqual });
        return std::nullopt;
      }
    }
  
    auto equivLoc = topStkEquiv(env);
    // If the local could be a Ref, don't record equality because the stack
    // element and the local won't actually have the same type.
    if (equivLoc == StackThisId && env.state.thisLoc != NoLocalId) {
      if (env.state.thisLoc == op.loc1 ||
                 locsAreEquiv(env, env.state.thisLoc, op.loc1)) {
        return std::nullopt;
      } else {
        equivLoc = env.state.thisLoc;
      }
    }
    if (!is_volatile_local(env.ctx.func, op.loc1)) {
      if (equivLoc <= MaxLocalId) {
        if (equivLoc == op.loc1 ||
            locsAreEquiv(env, equivLoc, op.loc1)) {
          // We allow equivalency to ignore Uninit, so we need to check
          // the types here.
          if (peekLocRaw(env, op.loc1) == topC(env)) {
            return std::nullopt;
          }
        }
      } else if (equivLoc == NoLocalId) {
        equivLoc = op.loc1;
      }
      if (!any(env.collect.opts & CollectionOpts::Speculating)) {
        effect_free(env);
      }
    } else {
      equivLoc = NoLocalId;
    }
    nothrow(env);
    auto val = popC(env);
    setLoc(env, op.loc1, val);
    if (equivLoc == StackThisId) {
      assertx(env.state.thisLoc == NoLocalId);
      equivLoc = env.state.thisLoc = op.loc1;
    }
    if (equivLoc == StackDupId) {
      setStkLocal(env, op.loc1);
    } else if (equivLoc != op.loc1 && equivLoc != NoLocalId) {
      addLocEquiv(env, op.loc1, equivLoc);
    }
    return { std::make_pair(std::move(val), equivLoc) };
  }
  
  }
  
  void in(ISS& env, const bc::PopL& op) {
    // If the same value is already in the local, do nothing but pop
    // it. Otherwise, the set has been done by moveToLocImpl.
    if (!moveToLocImpl(env, op)) return reduce(env, bc::PopC {});
  }
  
  void in(ISS& env, const bc::SetL& op) {
    // If the same value is already in the local, do nothing because SetL keeps
    // the value on the stack. If it isn't, we need to push it back onto the stack
    // because moveToLocImpl popped it.
    if (auto p = moveToLocImpl(env, op)) {
      push(env, std::move(p->first), p->second);
    } else {
      reduce(env);
    }
  }
  
  void in(ISS& env, const bc::SetG&) {
    auto t1 = popC(env);
    popC(env);
    push(env, std::move(t1));
  }
  
  void in(ISS& env, const bc::SetS& op) {
    auto const val   = popC(env);
    auto const tcls  = popC(env);
    auto const tname = popC(env);
  
    auto const throws = [&] {
      unreachable(env);
      return push(env, TBottom);
    };
  
    if (!tcls.couldBe(BCls)) return throws();
  
    auto merge = env.index.merge_static_type(
      env.ctx,
      env.collect.publicSPropMutations,
      env.collect.props,
      tcls,
      tname,
      val,
      true,
      false,
      checkReadonlyOpThrows(ReadonlyOp::Readonly, op.subop1)
    );
  
    if (merge.throws == TriBool::Yes || merge.adjusted.subtypeOf(BBottom)) {
      return throws();
    }
  
    if (merge.throws == TriBool::No &&
        tcls.subtypeOf(BCls) &&
        tname.subtypeOf(BStr)) {
      nothrow(env);
    }
  
    push(env, std::move(merge.adjusted));
  }
  
  void in(ISS& env, const bc::SetOpL& op) {
    auto const t1     = popC(env);
    auto const loc    = locAsCell(env, op.loc1);
  
    auto resultTy = typeSetOp(op.subop2, loc, t1);
    setLoc(env, op.loc1, resultTy);
    push(env, std::move(resultTy));
  }
  
  void in(ISS& env, const bc::SetOpG&) {
    popC(env); popC(env);
    push(env, TInitCell);
  }
  
  void in(ISS& env, const bc::SetOpS& op) {
    auto const rhs   = popC(env);
    auto const tcls  = popC(env);
    auto const tname = popC(env);
  
    auto const throws = [&] {
      unreachable(env);
      return push(env, TBottom);
    };
  
    if (!tcls.couldBe(BCls)) return throws();
  
    auto const lookup = env.index.lookup_static(
      env.ctx,
      env.collect.props,
      tcls,
      tname
    );
  
    if (lookup.found == TriBool::No || lookup.ty.subtypeOf(BBottom)) {
      return throws();
    }
  
    auto const newTy = typeSetOp(op.subop1, lookup.ty, rhs);
    if (newTy.subtypeOf(BBottom)) return throws();
  
    auto merge = env.index.merge_static_type(
      env.ctx,
      env.collect.publicSPropMutations,
      env.collect.props,
      tcls,
      tname,
      newTy
    );
  
    if (merge.throws == TriBool::Yes || merge.adjusted.subtypeOf(BBottom)) {
      return throws();
    }
  
    // NB: Unlike IncDecS, SetOpS pushes the post-TypeConstraint
    // adjustment value.
    push(env, std::move(merge.adjusted));
  }
  
  void in(ISS& env, const bc::IncDecL& op) {
    auto loc = locAsCell(env, op.nloc1.id);
    auto newT = typeIncDec(op.subop2, loc);
  
    if (newT.subtypeOf(BBottom)) {
      unreachable(env);
      return push(env, TBottom);
    }
  
    if (!locCouldBeUninit(env, op.nloc1.id) && loc.subtypeOf(BNum)) nothrow(env);
  
    auto const pre = isPre(op.subop2);
    if (!pre) push(env, std::move(loc));
    setLoc(env, op.nloc1.id, newT);
    if (pre)  push(env, std::move(newT));
  }
  
  void in(ISS& env, const bc::IncDecG&) { popC(env); push(env, TInitCell); }
  
  void in(ISS& env, const bc::IncDecS& op) {
    auto const tcls  = popC(env);
    auto const tname = popC(env);
    auto const pre = isPre(op.subop1);
  
    auto const throws = [&] {
      unreachable(env);
      return push(env, TBottom);
    };
  
    if (!tcls.couldBe(BCls)) return throws();
  
    auto lookup = env.index.lookup_static(
      env.ctx,
      env.collect.props,
      tcls,
      tname
    );
  
    if (lookup.found == TriBool::No || lookup.ty.subtypeOf(BBottom)) {
      return throws();
    }
  
    auto newTy = typeIncDec(op.subop1, lookup.ty);
    if (newTy.subtypeOf(BBottom)) return throws();
  
    auto const merge = env.index.merge_static_type(
      env.ctx,
      env.collect.publicSPropMutations,
      env.collect.props,
      tcls,
      tname,
      newTy
    );
  
    if (merge.throws == TriBool::Yes || merge.adjusted.subtypeOf(BBottom)) {
      return throws();
    }
  
    if (lookup.found == TriBool::Yes &&
        lookup.lateInit == TriBool::No &&
        !lookup.classInitMightRaise &&
        merge.throws == TriBool::No &&
        tcls.subtypeOf(BCls) &&
        tname.subtypeOf(BStr) &&
        lookup.ty.subtypeOf(BNum)) {
      nothrow(env);
    }
  
    // NB: IncDecS pushes the value pre-TypeConstraint modification
    push(env, pre ? std::move(newTy) : std::move(lookup.ty));
  }
  
  void in(ISS& env, const bc::UnsetL& op) {
    if (locRaw(env, op.loc1).subtypeOf(TUninit)) {
      return reduce(env);
    }
  
    if (auto const last = last_op(env)) {
      // No point in popping into the local if we're just going to
      // immediately unset it.
      if (last->op == Op::PopL &&
          last->PopL.loc1 == op.loc1) {
        reprocess(env);
        rewind(env, 1);
        setLocRaw(env, op.loc1, TCell);
        return reduce(env, bc::PopC {}, bc::UnsetL { op.loc1 });
      }
    }
  
    if (any(env.collect.opts & CollectionOpts::Speculating)) {
      nothrow(env);
    } else {
      effect_free(env);
    }
    setLocRaw(env, op.loc1, TUninit);
  }
  
  void in(ISS& env, const bc::UnsetG& /*op*/) {
    auto const t1 = popC(env);
    if (!t1.couldBe(BObj | BRes)) nothrow(env);
  }
  
  bool fcallCanSkipRepack(ISS& env, const FCallArgs& fca, const res::Func& func) {
    // Can't skip repack if potentially calling a function with too many args.
    if (fca.numArgs() > func.minNonVariadicParams()) return false;
    // Repack not needed if not unpacking and not having too many arguments.
    if (!fca.hasUnpack()) return true;
    // Can't skip repack if unpack args are in a wrong position.
    if (fca.numArgs() != func.maxNonVariadicParams()) return false;
  
    // Repack not needed if unpack args have the correct type.
    auto const unpackArgs = topC(env, fca.hasGenerics() ? 1 : 0);
    return unpackArgs.subtypeOf(BVec);
  }
  
  bool coeffectRulesMatch(ISS& env,
                          const FCallArgs& fca,
                          const res::Func& func,
                          uint32_t numExtraInputs,
                          const CoeffectRule& caller,
                          const CoeffectRule& callee) {
    if (caller.m_type != callee.m_type) return false;
    switch (caller.m_type) {
      case CoeffectRule::Type::CCThis: {
        if (caller.m_name != callee.m_name ||
            caller.m_types != callee.m_types) {
          return false;
        }
        if (!thisAvailable(env)) return false;
        auto const loc = topStkEquiv(env, fca.numInputs() + numExtraInputs + 1);
        return loc == StackThisId || (loc <= MaxLocalId && locIsThis(env, loc));
      }
      case CoeffectRule::Type::CCParam:
        if (caller.m_name != callee.m_name) return false;
        // fallthrough
      case CoeffectRule::Type::FunParam: {
        if (fca.hasUnpack()) return false;
        if (fca.numArgs() <= callee.m_index) return false;
        auto const l1 = caller.m_index;
        auto const l2 = topStkEquiv(env, fca.numInputs() - callee.m_index - 1);
        return l1 == l2 ||
               (l1 <= MaxLocalId &&
                l2 <= MaxLocalId &&
                locsAreEquiv(env, l1, l2));
      }
      case CoeffectRule::Type::CCReified:
        // TODO: optimize these
        return false;
      case CoeffectRule::Type::ClosureParentScope:
      case CoeffectRule::Type::GeneratorThis:
      case CoeffectRule::Type::Caller:
      case CoeffectRule::Type::Invalid:
        return false;
    }
    not_reached();
  }
  
  bool fcallCanSkipCoeffectsCheck(ISS& env,
                                  const FCallArgs& fca,
                                  const res::Func& func,
                                  uint32_t numExtraInputs) {
    auto const requiredCoeffectsOpt = func.requiredCoeffects();
    if (!requiredCoeffectsOpt) return false;
    auto const required = *requiredCoeffectsOpt;
    auto const provided =
      RuntimeCoeffects::fromValue(env.ctx.func->requiredCoeffects.value() |
                                  env.ctx.func->coeffectEscapes.value());
    if (!provided.canCall(required)) return false;
    auto const calleeRules = func.coeffectRules();
    // If we couldn't tell whether callee has rules or not, punt.
    if (!calleeRules) return false;
    if (calleeRules->empty()) return true;
    if (calleeRules->size() == 1 && (*calleeRules)[0].isCaller()) return true;
    auto const callerRules = env.ctx.func->coeffectRules;
    return std::is_permutation(callerRules.begin(), callerRules.end(),
                               calleeRules->begin(), calleeRules->end(),
                               [&] (const CoeffectRule& a,
                                    const CoeffectRule& b) {
                                 return coeffectRulesMatch(env, fca, func,
                                                           numExtraInputs,
                                                           a, b);
                                });
  }
  
  template<typename FCallWithFCA>
  bool fcallOptimizeChecks(
    ISS& env,
    const FCallArgs& fca,
    const res::Func& func,
    FCallWithFCA fcallWithFCA,
    Optional<uint32_t> inOutNum,
    bool maybeNullsafe,
    uint32_t numExtraInputs
  ) {
    // Don't optimize away in-out checks if we might use the null safe
    // operator. If we do so, we need the in-out bits to shuffle the
    // stack properly.
    if (!maybeNullsafe && fca.enforceInOut()) {
      if (inOutNum == fca.numRets() - 1) {
        bool match = true;
        for (auto i = 0; i < fca.numArgs(); ++i) {
          auto const kind = env.index.lookup_param_prep(env.ctx, func, i);
          if (kind.inOut == TriBool::Maybe) {
            match = false;
            break;
          }
  
          if (yesOrNo(fca.isInOut(i)) != kind.inOut) {
            // The function/method may not exist, in which case we should raise a
            // different error. Just defer the checks to the runtime.
            if (!func.exactFunc()) return false;
  
            // inout mismatch
            auto const exCls = makeStaticString("InvalidArgumentException");
            auto const err = makeStaticString(formatParamInOutMismatch(
                                                func.name()->data(), i, !fca.isInOut(i)));
  
            reduce(
              env,
              bc::NewObjD { exCls },
              bc::Dup {},
              bc::NullUninit {},
              bc::String { err },
              bc::FCallCtor { FCallArgs(1), staticEmptyString() },
              bc::PopC {},
              bc::LockObj {},
              bc::Throw {}
            );
            return true;
          }
        }
  
        if (match) {
          // Optimize away the runtime inout-ness check.
          reduce(env, fcallWithFCA(fca.withoutInOut()));
          return true;
        }
      }
    }
  
    if (fca.enforceReadonly()) {
      bool match = true;
      for (auto i = 0; i < fca.numArgs(); ++i) {
        if (!fca.isReadonly(i)) continue;
        auto const kind = env.index.lookup_param_prep(env.ctx, func, i);
        if (kind.readonly == TriBool::Maybe) {
          match = false;
          break;
        }
  
        if (kind.readonly != TriBool::Yes) {
          // The function/method may not exist, in which case we should raise a
          // different error. Just defer the checks to the runtime.
          if (!func.exactFunc()) return false;
          match = false;
          break;
        }
      }
  
      if (match) {
        // Optimize away the runtime readonly-ness check.
        reduce(env, fcallWithFCA(fca.withoutReadonly()));
        return true;
      }
    }
  
    if (fca.enforceMutableReturn()) {
      if (env.index.lookup_return_readonly(env.ctx, func) == TriBool::No) {
        reduce(env, fcallWithFCA(fca.withoutEnforceMutableReturn()));
        return true;
      }
    }
  
    if (fca.enforceReadonlyThis()) {
      if (env.index.lookup_readonly_this(env.ctx, func) == TriBool::Yes) {
        reduce(env, fcallWithFCA(fca.withoutEnforceReadonlyThis()));
        return true;
      }
    }
  
    // Infer whether the callee supports async eager return.
    if (fca.asyncEagerTarget() != NoBlockId) {
      auto const status = env.index.supports_async_eager_return(func);
      if (status && !*status) {
        reduce(env, fcallWithFCA(fca.withoutAsyncEagerTarget()));
        return true;
      }
    }
  
    if (!fca.skipRepack() && fcallCanSkipRepack(env, fca, func)) {
      reduce(env, fcallWithFCA(fca.withoutRepack()));
      return true;
    }
  
    if (!fca.skipCoeffectsCheck() &&
        fcallCanSkipCoeffectsCheck(env, fca, func, numExtraInputs)) {
      reduce(env, fcallWithFCA(fca.withoutCoeffectsCheck()));
      return true;
    }
  
    return false;
  }
  
  bool fcallTryFold(
    ISS& env,
    const FCallArgs& fca,
    const res::Func& func,
    Type context,
    bool maybeDynamic,
    uint32_t numExtraInputs
  ) {
    auto const foldableFunc = func.exactFunc();
    if (!foldableFunc) return false;
    if (!shouldAttemptToFold(env, foldableFunc, fca, context, maybeDynamic)) {
      return false;
    }
  
    assertx(!fca.hasUnpack() && !fca.hasGenerics() && fca.numRets() == 1);
    assertx(options.ConstantFoldBuiltins);
  
    auto const finish = [&] (Type ty) {
      auto const v = tv(ty);
      if (!v) return false;
      BytecodeVec repl;
      for (uint32_t i = 0; i < numExtraInputs; ++i) repl.push_back(bc::PopC {});
      for (uint32_t i = 0; i < fca.numArgs(); ++i) repl.push_back(bc::PopC {});
      repl.push_back(bc::PopU {});
      if (topT(env, fca.numArgs() + 1 + numExtraInputs).subtypeOf(TInitCell)) {
        repl.push_back(bc::PopC {});
      } else {
        assertx(topT(env, fca.numArgs() + 1 + numExtraInputs).subtypeOf(TUninit));
        repl.push_back(bc::PopU {});
      }
      repl.push_back(gen_constant(*v));
      reduce(env, std::move(repl));
      return true;
    };
  
    if (foldableFunc->attrs & AttrBuiltin &&
        foldableFunc->attrs & AttrIsFoldable) {
      auto ret = const_fold(env, fca.numArgs(), numExtraInputs, *foldableFunc,
                            false);
      if (!ret) return false;
      return finish(std::move(*ret));
    }
  
    CompactVector<Type> args(fca.numArgs());
    auto const firstArgPos = numExtraInputs + fca.numInputs() - 1;
    for (auto i = uint32_t{0}; i < fca.numArgs(); ++i) {
      auto const& arg = topT(env, firstArgPos - i);
      auto const isScalar = is_scalar(arg);
      if (!isScalar &&
          (env.index.func_depends_on_arg(foldableFunc, i) ||
           !arg.subtypeOf(BInitCell))) {
        return false;
      }
      args[i] = isScalar ? scalarize(arg) : arg;
    }
  
    auto calleeCtx = CallContext {
      foldableFunc,
      std::move(args),
      std::move(context)
    };
    if (env.collect.unfoldableFuncs.count(calleeCtx)) return false;
  
    if (finish(env.index.lookup_foldable_return_type(env.ctx, calleeCtx))) {
      return true;
    }
    env.collect.unfoldableFuncs.emplace(std::move(calleeCtx));
    return false;
  }
  
  Type typeFromWH(Type t) {
    if (!t.couldBe(BObj)) {
      // Exceptions will be thrown if a non-object is awaited.
      return TBottom;
    }
  
    // Throw away non-obj component.
    t &= TObj;
  
    // If we aren't even sure this is a wait handle, there's nothing we can
    // infer here.
    if (!is_specialized_wait_handle(t)) {
      return TInitCell;
    }
  
    return wait_handle_inner(t);
  }
  
  void pushCallReturnType(ISS& env,
                          Type ty,
                          const FCallArgs& fca,
                          bool nullsafe,
                          std::vector<Type> inOuts) {
    auto const numRets = fca.numRets();
    if (numRets != 1) {
      assertx(fca.asyncEagerTarget() == NoBlockId);
      assertx(IMPLIES(nullsafe, inOuts.size() == numRets - 1));
  
      for (auto i = uint32_t{0}; i < numRets - 1; ++i) popU(env);
      if (!ty.couldBe(BVecN)) {
        // Function cannot have an in-out args match, so call will
        // always fail.
        if (!nullsafe) {
          for (int32_t i = 0; i < numRets; i++) push(env, TBottom);
          return unreachable(env);
        }
        // We'll only hit the nullsafe null case, so the outputs are the
        // inout inputs.
        for (auto& t : inOuts) push(env, std::move(t));
        push(env, TInitNull);
        return;
      }
  
      // If we might use the nullsafe operator, we need to union in the
      // null case (which means the inout args are unchanged).
      if (is_specialized_array_like(ty)) {
        for (int32_t i = 1; i < numRets; i++) {
          auto elem = array_like_elem(ty, ival(i)).first;
          if (nullsafe) elem |= inOuts[i-1];
          push(env, std::move(elem));
        }
        push(
          env,
          nullsafe
            ? opt(array_like_elem(ty, ival(0)).first)
            : array_like_elem(ty, ival(0)).first
        );
      } else {
        for (int32_t i = 0; i < numRets; ++i) push(env, TInitCell);
      }
      return;
    }
    if (fca.asyncEagerTarget() != NoBlockId) {
      assertx(!ty.is(BBottom));
      push(env, typeFromWH(ty));
      assertx(!topC(env).subtypeOf(BBottom));
      env.propagate(fca.asyncEagerTarget(), &env.state);
      popC(env);
    }
    if (nullsafe) ty = opt(std::move(ty));
    if (ty.is(BBottom)) {
      // The callee function never returns.  It might throw, or loop
      // forever.
      push(env, TBottom);
      return unreachable(env);
    }
    return push(env, std::move(ty));
  }
  
  const StaticString s_defined { "defined" };
  const StaticString s_function_exists { "function_exists" };
  
  template<typename FCallWithFCA>
  void fcallKnownImpl(
    ISS& env,
    const FCallArgs& fca,
    const res::Func& func,
    Type context,
    bool nullsafe,
    uint32_t numExtraInputs,
    FCallWithFCA fcallWithFCA,
    Optional<uint32_t> inOutNum
  ) {
    auto const numArgs = fca.numArgs();
    auto returnType = [&] {
      CompactVector<Type> args(numArgs);
      auto const firstArgPos = numExtraInputs + fca.numInputs() - 1;
      for (auto i = uint32_t{0}; i < numArgs; ++i) {
        args[i] = topCV(env, firstArgPos - i);
      }
  
      return fca.hasUnpack()
        ? env.index.lookup_return_type(env.ctx, &env.collect.methods, func)
        : env.index.lookup_return_type(
            env.ctx, &env.collect.methods, args, context, func
          );
    }();
  
    // If there's a caller/callee inout mismatch, then the call will
    // always fail.
    if (fca.enforceInOut()) {
      if (inOutNum && (*inOutNum + 1 != fca.numRets())) {
        returnType = TBottom;
      }
    }
  
    if (fca.asyncEagerTarget() != NoBlockId && typeFromWH(returnType) == TBottom) {
      // Kill the async eager target if the function never returns.
      reduce(env, fcallWithFCA(std::move(fca.withoutAsyncEagerTarget())));
      return;
    }
  
    if (func.name()->isame(s_function_exists.get()) &&
        (numArgs == 1 || numArgs == 2) &&
        !fca.hasUnpack() && !fca.hasGenerics()) {
      handle_function_exists(env, topT(env, numExtraInputs + numArgs - 1));
    }
  
    for (auto i = uint32_t{0}; i < numExtraInputs; ++i) popC(env);
    if (fca.hasGenerics()) popC(env);
    if (fca.hasUnpack()) popC(env);
    std::vector<Type> inOuts;
    for (auto i = uint32_t{0}; i < numArgs; ++i) {
      if (nullsafe && fca.isInOut(numArgs - i - 1)) {
        inOuts.emplace_back(popCV(env));
      } else {
        popCV(env);
      }
    }
    popU(env);
    popCU(env);
    pushCallReturnType(env, std::move(returnType),
                       fca, nullsafe, std::move(inOuts));
  }
  
  void fcallUnknownImpl(ISS& env,
                        const FCallArgs& fca,
                        const Type& retTy = TInitCell) {
    if (fca.hasGenerics()) popC(env);
    if (fca.hasUnpack()) popC(env);
    auto const numArgs = fca.numArgs();
    auto const numRets = fca.numRets();
    for (auto i = uint32_t{0}; i < numArgs; ++i) popCV(env);
    popU(env);
    popCU(env);
    if (fca.asyncEagerTarget() != NoBlockId) {
      assertx(numRets == 1);
      assertx(!retTy.is(BBottom));
      push(env, retTy);
      env.propagate(fca.asyncEagerTarget(), &env.state);
      popC(env);
    }
    for (auto i = uint32_t{0}; i < numRets - 1; ++i) popU(env);
    for (auto i = uint32_t{0}; i < numRets; ++i) push(env, retTy);
  }
  
  void in(ISS& env, const bc::FCallFuncD& op) {
    auto const rfunc = env.index.resolve_func(env.ctx, op.str2);
  
    if (op.fca.hasGenerics()) {
      auto const tsList = topC(env);
      if (!tsList.couldBe(BVec)) {
        return unreachable(env);
      }
  
      if (!rfunc.couldHaveReifiedGenerics()) {
        return reduce(
          env,
          bc::PopC {},
          bc::FCallFuncD { op.fca.withoutGenerics(), op.str2 }
        );
      }
    }
  
    auto const updateBC = [&] (FCallArgs fca) {
      return bc::FCallFuncD { std::move(fca), op.str2 };
    };
  
    auto const numInOut = op.fca.enforceInOut()
      ? env.index.lookup_num_inout_params(env.ctx, rfunc)
      : std::nullopt;
  
    if (fcallOptimizeChecks(env, op.fca, rfunc, updateBC, numInOut, false, 0) ||
        fcallTryFold(env, op.fca, rfunc, TBottom, false, 0)) {
      return;
    }
  
    if (auto const func = rfunc.exactFunc()) {
      if (optimize_builtin(env, func, op.fca)) return;
    }
  
    fcallKnownImpl(env, op.fca, rfunc, TBottom, false, 0, updateBC, numInOut);
  }
  
  namespace {
  
  void fcallFuncUnknown(ISS& env, const bc::FCallFunc& op) {
    popC(env);
    fcallUnknownImpl(env, op.fca);
  }
  
  void fcallFuncClsMeth(ISS& env, const bc::FCallFunc& op) {
    assertx(topC(env).subtypeOf(BClsMeth));
  
    // TODO: optimize me
    fcallFuncUnknown(env, op);
  }
  
  void fcallFuncFunc(ISS& env, const bc::FCallFunc& op) {
    assertx(topC(env).subtypeOf(BFunc));
  
    // TODO: optimize me
    fcallFuncUnknown(env, op);
  }
  
  void fcallFuncObj(ISS& env, const bc::FCallFunc& op) {
    assertx(topC(env).subtypeOf(BObj));
  
    // TODO: optimize me
    fcallFuncUnknown(env, op);
  }
  
  void fcallFuncStr(ISS& env, const bc::FCallFunc& op) {
    assertx(topC(env).subtypeOf(BStr));
    auto funcName = getNameFromType(topC(env));
    if (!funcName) return fcallFuncUnknown(env, op);
  
    funcName = normalizeNS(funcName);
    if (!isNSNormalized(funcName) || !notClassMethodPair(funcName)) {
      return fcallFuncUnknown(env, op);
    }
  
    auto const rfunc = env.index.resolve_func(env.ctx, funcName);
    if (!rfunc.mightCareAboutDynCalls()) {
      return reduce(env, bc::PopC {}, bc::FCallFuncD { op.fca, funcName });
    }
  
    auto const updateBC = [&] (FCallArgs fca) {
      return bc::FCallFunc { std::move(fca) };
    };
  
    auto const numInOut = op.fca.enforceInOut()
      ? env.index.lookup_num_inout_params(env.ctx, rfunc)
      : std::nullopt;
  
    if (fcallOptimizeChecks(env, op.fca, rfunc, updateBC, numInOut, false, 0)) {
      return;
    }
    fcallKnownImpl(env, op.fca, rfunc, TBottom, false, 1, updateBC, numInOut);
  }
  
  } // namespace
  
  void in(ISS& env, const bc::FCallFunc& op) {
    auto const callable = topC(env);
    if (callable.subtypeOf(BFunc)) return fcallFuncFunc(env, op);
    if (callable.subtypeOf(BClsMeth)) return fcallFuncClsMeth(env, op);
    if (callable.subtypeOf(BObj)) return fcallFuncObj(env, op);
    if (callable.subtypeOf(BStr)) return fcallFuncStr(env, op);
    fcallFuncUnknown(env, op);
  }
  
  void in(ISS& env, const bc::ResolveFunc& op) {
    push(env, TFunc);
  }
  
  void in(ISS& env, const bc::ResolveMethCaller& op) {
    // TODO (T29639296)
    push(env, TFunc);
  }
  
  void in(ISS& env, const bc::ResolveRFunc& op) {
    popC(env);
    push(env, union_of(TFunc, TRFunc));
  }
  
  namespace {
  
  Type ctxCls(ISS& env) {
    auto const s = selfCls(env);
    return setctx(s ? *s : TCls);
  }
  
  Type specialClsRefToCls(ISS& env, SpecialClsRef ref) {
    if (!env.ctx.cls) return TCls;
    auto const op = [&]()-> Optional<Type> {
      switch (ref) {
        case SpecialClsRef::Static: return ctxCls(env);
        case SpecialClsRef::Self:   return selfClsExact(env);
        case SpecialClsRef::Parent: return parentClsExact(env);
      }
      always_assert(false);
    }();
    return op ? *op : TCls;
  }
  
  template<bool reifiedVersion = false>
  void resolveClsMethodSImpl(ISS& env, SpecialClsRef ref, LSString meth_name) {
    auto const clsTy = specialClsRefToCls(env, ref);
    auto const rfunc = env.index.resolve_method(env.ctx, clsTy, meth_name);
    if (is_specialized_cls(clsTy) && dcls_of(clsTy).type == DCls::Exact &&
        !rfunc.couldHaveReifiedGenerics()) {
      auto const clsName = dcls_of(clsTy).cls.name();
      return reduce(env, bc::ResolveClsMethodD { clsName, meth_name });
    }
    if (reifiedVersion) popC(env);
    if (!reifiedVersion || !rfunc.couldHaveReifiedGenerics()) {
      push(env, TClsMeth);
    } else {
      push(env, union_of(TClsMeth, TRClsMeth));
    }
  }
  
  } // namespace
  
  void in(ISS& env, const bc::ResolveClsMethod& op) {
    popC(env);
    push(env, TClsMeth);
  }
  
  void in(ISS& env, const bc::ResolveClsMethodD& op) {
    push(env, TClsMeth);
  }
  
  void in(ISS& env, const bc::ResolveClsMethodS& op) {
    resolveClsMethodSImpl<false>(env, op.subop1, op.str2);
  }
  
  void in(ISS& env, const bc::ResolveRClsMethod&) {
    popC(env);
    popC(env);
    push(env, union_of(TClsMeth, TRClsMeth));
  }
  
  void in(ISS& env, const bc::ResolveRClsMethodD&) {
    popC(env);
    push(env, union_of(TClsMeth, TRClsMeth));
  }
  
  void in(ISS& env, const bc::ResolveRClsMethodS& op) {
    resolveClsMethodSImpl<true>(env, op.subop1, op.str2);
  }
  
  void in(ISS& env, const bc::ResolveClass& op) {
    // TODO (T61651936)
    auto cls = env.index.resolve_class(env.ctx, op.str1);
    if (cls && cls->resolved()) {
      push(env, clsExact(*cls));
    } else {
      // If the class is not resolved,
      // it might not be unique or it might not be a valid classname.
      push(env, union_of(TArrKey, TCls, TLazyCls));
    }
  }
  
  void in(ISS& env, const bc::LazyClass& op) {
    effect_free(env);
    push(env, lazyclsval(op.str1));
  }
  
  namespace {
  
  const StaticString
    s_DynamicContextOverrideUnsafe("__SystemLib\\DynamicContextOverrideUnsafe");
  
  bool isBadContext(const FCallArgs& fca) {
    return fca.context() &&
      fca.context()->isame(s_DynamicContextOverrideUnsafe.get());
  }
  
  Context getCallContext(const ISS& env, const FCallArgs& fca) {
    if (auto const name = fca.context()) {
      auto const rcls = env.index.resolve_class(env.ctx, name);
      if (rcls && rcls->cls()) {
        return Context { env.ctx.unit, env.ctx.func, rcls->cls() };
      }
      return Context { env.ctx.unit, env.ctx.func, nullptr };
    }
    return env.ctx;
  }
  
  void fcallObjMethodNullsafeNoFold(ISS& env,
                                    const FCallArgs& fca,
                                    bool extraInput) {
    assertx(fca.asyncEagerTarget() == NoBlockId);
    if (extraInput) popC(env);
    if (fca.hasGenerics()) popC(env);
    if (fca.hasUnpack()) popC(env);
    auto const numArgs = fca.numArgs();
    auto const numRets = fca.numRets();
    std::vector<Type> inOuts;
    for (auto i = uint32_t{0}; i < numArgs; ++i) {
      if (fca.enforceInOut() && fca.isInOut(numArgs - i - 1)) {
        inOuts.emplace_back(popCV(env));
      } else {
        popCV(env);
      }
    }
    popU(env);
    popCU(env);
    for (auto i = uint32_t{0}; i < numRets - 1; ++i) popU(env);
    assertx(inOuts.size() == numRets - 1);
    for (auto& t : inOuts) push(env, std::move(t));
    push(env, TInitNull);
  }
  
  void fcallObjMethodNullsafe(ISS& env, const FCallArgs& fca, bool extraInput) {
    // Don't fold if there's inout arguments. We could, in principal,
    // fold away the inout case like we do below, but we don't have the
    // bytecodes necessary to shuffle the stack.
    if (fca.enforceInOut()) {
      for (uint32_t i = 0; i < fca.numArgs(); ++i) {
        if (fca.isInOut(i)) {
          return fcallObjMethodNullsafeNoFold(env, fca, extraInput);
        }
      }
    }
  
    BytecodeVec repl;
    if (extraInput) repl.push_back(bc::PopC {});
    if (fca.hasGenerics()) repl.push_back(bc::PopC {});
    if (fca.hasUnpack()) repl.push_back(bc::PopC {});
  
    auto const numArgs = fca.numArgs();
    for (uint32_t i = 0; i < numArgs; ++i) {
      assertx(topC(env, repl.size()).subtypeOf(BInitCell));
      repl.push_back(bc::PopC {});
    }
    repl.push_back(bc::PopU {});
    repl.push_back(bc::PopC {});
    assertx(fca.numRets() == 1);
    repl.push_back(bc::Null {});
  
    reduce(env, std::move(repl));
  }
  
  template <typename Op, class UpdateBC>
  void fcallObjMethodImpl(ISS& env, const Op& op, SString methName, bool dynamic,
                          bool extraInput, UpdateBC updateBC) {
    auto const nullThrows = op.subop3 == ObjMethodOp::NullThrows;
    auto const inputPos = op.fca.numInputs() + (extraInput ? 2 : 1);
    auto const input = topC(env, inputPos);
    auto const location = topStkEquiv(env, inputPos);
    auto const mayCallMethod = input.couldBe(BObj);
    auto const mayUseNullsafe = !nullThrows && input.couldBe(BNull);
    auto const mayThrowNonObj = !input.subtypeOf(nullThrows ? BObj : BOptObj);
  
    auto const refineLoc = [&] {
      if (location == NoLocalId) return;
      if (!refineLocation(env, location, [&] (Type t) {
        if (nullThrows) return intersection_of(t, TObj);
        if (!t.couldBe(BUninit)) return intersection_of(t, TOptObj);
        if (!t.couldBe(BObj)) return intersection_of(t, TNull);
        return t;
      })) {
        unreachable(env);
      }
    };
  
    auto const throws = [&] {
      if (op.fca.asyncEagerTarget() != NoBlockId) {
        // Kill the async eager target if the function never returns.
        return reduce(env, updateBC(op.fca.withoutAsyncEagerTarget()));
      }
      if (extraInput) popC(env);
      fcallUnknownImpl(env, op.fca, TBottom);
      unreachable(env);
    };
  
    if (!mayCallMethod && !mayUseNullsafe) {
      // This FCallObjMethodD may only throw
      return throws();
    }
  
    if (!mayCallMethod && !mayThrowNonObj) {
      // Null input, this may only return null, so do that.
      return fcallObjMethodNullsafe(env, op.fca, extraInput);
    }
  
    if (!mayCallMethod) {
      // May only return null, but can't fold as we may still throw.
      assertx(mayUseNullsafe && mayThrowNonObj);
      if (op.fca.asyncEagerTarget() != NoBlockId) {
        return reduce(env, updateBC(op.fca.withoutAsyncEagerTarget()));
      }
      return fcallObjMethodNullsafeNoFold(env, op.fca, extraInput);
    }
  
    if (isBadContext(op.fca)) return throws();
  
    auto const ctx = getCallContext(env, op.fca);
    auto const ctxTy = input.couldBe(BObj)
      ? intersection_of(input, TObj)
      : TObj;
    auto const clsTy = objcls(ctxTy);
    auto const rfunc = env.index.resolve_method(ctx, clsTy, methName);
  
    auto const numInOut = op.fca.enforceInOut()
      ? env.index.lookup_num_inout_params(env.ctx, rfunc)
      : std::nullopt;
  
    auto const canFold = !mayUseNullsafe && !mayThrowNonObj;
    auto const numExtraInputs = extraInput ? 1 : 0;
    if (fcallOptimizeChecks(env, op.fca, rfunc, updateBC,
                            numInOut, mayUseNullsafe, numExtraInputs) ||
        (canFold && fcallTryFold(env, op.fca, rfunc, ctxTy, dynamic,
                                 numExtraInputs))) {
      return;
    }
  
    if (rfunc.exactFunc() && op.str2->empty()) {
      return reduce(env, updateBC(op.fca, rfunc.exactFunc()->cls->name));
    }
  
    fcallKnownImpl(env, op.fca, rfunc, ctxTy, mayUseNullsafe, extraInput ? 1 : 0,
                   updateBC, numInOut);
    refineLoc();
  }
  
  } // namespace
  
  void in(ISS& env, const bc::FCallObjMethodD& op) {
    if (op.fca.hasGenerics()) {
      auto const tsList = topC(env);
      if (!tsList.couldBe(BVec)) {
        return unreachable(env);
      }
  
      auto const input = topC(env, op.fca.numInputs() + 1);
      auto const clsTy = input.couldBe(BObj)
        ? objcls(intersection_of(input, TObj))
        : TCls;
      auto const rfunc = env.index.resolve_method(env.ctx, clsTy, op.str4);
      if (!rfunc.couldHaveReifiedGenerics()) {
        return reduce(
          env,
          bc::PopC {},
          bc::FCallObjMethodD {
            op.fca.withoutGenerics(), op.str2, op.subop3, op.str4 }
        );
      }
    }
  
    auto const updateBC = [&] (FCallArgs fca, SString clsHint = nullptr) {
      if (!clsHint) clsHint = op.str2;
      return bc::FCallObjMethodD { std::move(fca), clsHint, op.subop3, op.str4 };
    };
    fcallObjMethodImpl(env, op, op.str4, false, false, updateBC);
  }
  
  void in(ISS& env, const bc::FCallObjMethod& op) {
    auto const methName = getNameFromType(topC(env));
    if (!methName) {
      popC(env);
      fcallUnknownImpl(env, op.fca);
      return;
    }
  
    auto const input = topC(env, op.fca.numInputs() + 2);
    auto const clsTy = input.couldBe(BObj)
      ? objcls(intersection_of(input, TObj))
      : TCls;
    auto const rfunc = env.index.resolve_method(env.ctx, clsTy, methName);
    if (!rfunc.mightCareAboutDynCalls()) {
      return reduce(
        env,
        bc::PopC {},
        bc::FCallObjMethodD { op.fca, op.str2, op.subop3, methName }
      );
    }
  
    auto const updateBC = [&] (FCallArgs fca, SString clsHint = nullptr) {
      if (!clsHint) clsHint = op.str2;
      return bc::FCallObjMethod { std::move(fca), clsHint, op.subop3 };
    };
    fcallObjMethodImpl(env, op, methName, true, true, updateBC);
  }
  
  namespace {
  
  template <typename Op, class UpdateBC>
  void fcallClsMethodImpl(ISS& env, const Op& op, Type clsTy, SString methName,
                          bool dynamic, uint32_t numExtraInputs,
                          UpdateBC updateBC) {
    if (isBadContext(op.fca)) {
      for (auto i = uint32_t{0}; i < numExtraInputs; ++i) popC(env);
      fcallUnknownImpl(env, op.fca);
      unreachable(env);
      return;
    }
  
    auto const ctx = getCallContext(env, op.fca);
    auto const rfunc = env.index.resolve_method(ctx, clsTy, methName);
  
    auto const numInOut = op.fca.enforceInOut()
      ? env.index.lookup_num_inout_params(env.ctx, rfunc)
      : std::nullopt;
  
    if (fcallOptimizeChecks(env, op.fca, rfunc, updateBC, numInOut, false,
                            numExtraInputs) ||
        fcallTryFold(env, op.fca, rfunc, clsTy, dynamic, numExtraInputs)) {
      return;
    }
  
    if (rfunc.exactFunc() && op.str2->empty()) {
      return reduce(env, updateBC(op.fca, rfunc.exactFunc()->cls->name));
    }
  
    fcallKnownImpl(env, op.fca, rfunc, clsTy, false /* nullsafe */,
                   numExtraInputs, updateBC, numInOut);
  }
  
  } // namespace
  
  void in(ISS& env, const bc::FCallClsMethodD& op) {
    auto const rcls = env.index.resolve_class(env.ctx, op.str3);
    auto const clsTy = rcls ? clsExact(*rcls) : TCls;
    auto const rfunc = env.index.resolve_method(env.ctx, clsTy, op.str4);
  
    if (op.fca.hasGenerics() && !rfunc.couldHaveReifiedGenerics()) {
      return reduce(
        env,
        bc::PopC {},
        bc::FCallClsMethodD {
          op.fca.withoutGenerics(), op.str2, op.str3, op.str4 }
      );
    }
  
    if (auto const func = rfunc.exactFunc()) {
      assertx(func->cls != nullptr);
      if (func->cls->name->same(op.str3) &&
          optimize_builtin(env, func, op.fca)) {
        // When we use FCallBuiltin to call a static method, the litstr method
        // name will be a fully qualified cls::fn (e.g. "HH\Map::fromItems").
        //
        // As a result, we can only do this optimization if the name of the
        // builtin function's class matches this op's class name immediate.
        return;
      }
    }
  
    auto const updateBC = [&] (FCallArgs fca, SString clsHint = nullptr) {
      if (!clsHint) clsHint = op.str2;
      return bc::FCallClsMethodD { std::move(fca), clsHint, op.str3, op.str4 };
    };
    fcallClsMethodImpl(env, op, clsTy, op.str4, false, 0, updateBC);
  }
  
  void in(ISS& env, const bc::FCallClsMethod& op) {
    auto const methName = getNameFromType(topC(env, 1));
    if (!methName) {
      popC(env);
      popC(env);
      fcallUnknownImpl(env, op.fca);
      return;
    }
  
    auto const clsTy = topC(env);
    auto const rfunc = env.index.resolve_method(env.ctx, clsTy, methName);
    auto const skipLogAsDynamicCall =
      !RuntimeOption::EvalLogKnownMethodsAsDynamicCalls &&
        op.subop3 == IsLogAsDynamicCallOp::DontLogAsDynamicCall;
    if (is_specialized_cls(clsTy) && dcls_of(clsTy).type == DCls::Exact &&
        (!rfunc.mightCareAboutDynCalls() || skipLogAsDynamicCall)) {
      auto const clsName = dcls_of(clsTy).cls.name();
      return reduce(
        env,
        bc::PopC {},
        bc::PopC {},
        bc::FCallClsMethodD { op.fca, op.str2, clsName, methName }
      );
    }
  
    auto const updateBC = [&] (FCallArgs fca, SString clsHint = nullptr) {
      if (!clsHint) clsHint = op.str2;
      return bc::FCallClsMethod { std::move(fca), clsHint, op.subop3 };
    };
    fcallClsMethodImpl(env, op, clsTy, methName, true, 2, updateBC);
  }
  
  namespace {
  
  template <typename Op, class UpdateBC>
  void fcallClsMethodSImpl(ISS& env, const Op& op, SString methName, bool dynamic,
                           bool extraInput, UpdateBC updateBC) {
    auto const clsTy = specialClsRefToCls(env, op.subop3);
    if (is_specialized_cls(clsTy) && dcls_of(clsTy).type == DCls::Exact &&
        !dynamic && op.subop3 == SpecialClsRef::Static) {
      auto const clsName = dcls_of(clsTy).cls.name();
      reduce(env, bc::FCallClsMethodD { op.fca, op.str2, clsName, methName });
      return;
    }
  
    auto const rfunc = env.index.resolve_method(env.ctx, clsTy, methName);
  
    auto const numInOut = op.fca.enforceInOut()
      ? env.index.lookup_num_inout_params(env.ctx, rfunc)
      : std::nullopt;
  
    auto const numExtraInputs = extraInput ? 1 : 0;
    if (fcallOptimizeChecks(env, op.fca, rfunc, updateBC, numInOut, false,
                            numExtraInputs) ||
        fcallTryFold(env, op.fca, rfunc, ctxCls(env), dynamic,
                     numExtraInputs)) {
      return;
    }
  
    if (rfunc.exactFunc() && op.str2->empty()) {
      return reduce(env, updateBC(op.fca, rfunc.exactFunc()->cls->name));
    }
  
    fcallKnownImpl(env, op.fca, rfunc, ctxCls(env), false /* nullsafe */,
                   extraInput ? 1 : 0, updateBC, numInOut);
  }
  
  } // namespace
  
  void in(ISS& env, const bc::FCallClsMethodSD& op) {
    if (op.fca.hasGenerics()) {
      auto const clsTy = specialClsRefToCls(env, op.subop3);
      auto const rfunc = env.index.resolve_method(env.ctx, clsTy, op.str4);
      if (!rfunc.couldHaveReifiedGenerics()) {
        return reduce(
          env,
          bc::PopC {},
          bc::FCallClsMethodSD {
            op.fca.withoutGenerics(), op.str2, op.subop3, op.str4  }
        );
      }
    }
  
    auto const updateBC = [&] (FCallArgs fca, SString clsHint = nullptr) {
      if (!clsHint) clsHint = op.str2;
      return bc::FCallClsMethodSD { std::move(fca), clsHint, op.subop3, op.str4 };
    };
    fcallClsMethodSImpl(env, op, op.str4, false, false, updateBC);
  }
  
  void in(ISS& env, const bc::FCallClsMethodS& op) {
    auto const methName = getNameFromType(topC(env));
    if (!methName) {
      popC(env);
      fcallUnknownImpl(env, op.fca);
      return;
    }
  
    auto const clsTy = specialClsRefToCls(env, op.subop3);
    auto const rfunc = env.index.resolve_method(env.ctx, clsTy, methName);
    if (!rfunc.mightCareAboutDynCalls() && !rfunc.couldHaveReifiedGenerics()) {
      return reduce(
        env,
        bc::PopC {},
        bc::FCallClsMethodSD { op.fca, op.str2, op.subop3, methName }
      );
    }
  
    auto const updateBC = [&] (FCallArgs fca, SString clsHint = nullptr) {
      if (!clsHint) clsHint = op.str2;
      return bc::FCallClsMethodS { std::move(fca), clsHint, op.subop3 };
    };
    fcallClsMethodSImpl(env, op, methName, true, true, updateBC);
  }
  
  namespace {
  
  void newObjDImpl(ISS& env, const StringData* className, bool rflavor) {
    auto const rcls = env.index.resolve_class(env.ctx, className);
    if (!rcls) {
      if (rflavor) popC(env);
      push(env, TObj);
      return;
    }
    if (rflavor && !rcls->couldHaveReifiedGenerics()) {
      return reduce(env, bc::PopC {}, bc::NewObjD { className });
    }
    auto const isCtx = !rcls->couldBeOverriden() && env.ctx.cls &&
      rcls->same(env.index.resolve_class(env.ctx.cls));
    if (rflavor) popC(env);
    push(env, setctx(objExact(*rcls), isCtx));
  }
  
  } // namespace
  
  void in(ISS& env, const bc::NewObjD& op)  { newObjDImpl(env, op.str1, false); }
  void in(ISS& env, const bc::NewObjRD& op) { newObjDImpl(env, op.str1, true);  }
  
  void in(ISS& env, const bc::NewObjS& op) {
    auto const cls = specialClsRefToCls(env, op.subop1);
    if (!is_specialized_cls(cls)) {
      push(env, TObj);
      return;
    }
  
    auto const dcls = dcls_of(cls);
    auto const exact = dcls.type == DCls::Exact;
    if (exact && !dcls.cls.couldHaveReifiedGenerics() &&
        (!dcls.cls.couldBeOverriden() || equivalently_refined(cls, unctx(cls)))) {
      return reduce(env, bc::NewObjD { dcls.cls.name() });
    }
  
    push(env, toobj(cls));
  }
  
  void in(ISS& env, const bc::NewObj& op) {
    auto const cls = topC(env);
    if (!cls.subtypeOf(BCls) || !is_specialized_cls(cls)) {
      popC(env);
      push(env, TObj);
      return;
    }
  
    auto const dcls = dcls_of(cls);
    auto const exact = dcls.type == DCls::Exact;
    if (exact && !dcls.cls.mightCareAboutDynConstructs()) {
      return reduce(
        env,
        bc::PopC {},
        bc::NewObjD { dcls.cls.name() }
      );
    }
  
    popC(env);
    push(env, toobj(cls));
  }
  
  void in(ISS& env, const bc::NewObjR& op) {
    auto const generics = topC(env);
    auto const cls = topC(env, 1);
  
    if (generics.subtypeOf(BInitNull)) {
      return reduce(
        env,
        bc::PopC {},
        bc::NewObj {}
      );
    }
  
    if (!cls.subtypeOf(BCls) || !is_specialized_cls(cls)) {
      popC(env);
      popC(env);
      push(env, TObj);
      return;
    }
  
    auto const dcls = dcls_of(cls);
    auto const exact = dcls.type == DCls::Exact;
    if (exact && !dcls.cls.couldHaveReifiedGenerics()) {
      return reduce(
        env,
        bc::PopC {},
        bc::NewObj {}
      );
    }
  
    popC(env);
    popC(env);
    push(env, toobj(cls));
  }
  
  namespace {
  
  bool objMightHaveConstProps(const Type& t) {
    assertx(t.subtypeOf(BObj));
    assertx(is_specialized_obj(t));
    auto const dobj = dobj_of(t);
    switch (dobj.type) {
      case DObj::Exact:
        return dobj.cls.couldHaveConstProp();
      case DObj::Sub:
        return dobj.cls.derivedCouldHaveConstProp();
    }
    not_reached();
  }
  
  }
  
  void in(ISS& env, const bc::FCallCtor& op) {
    auto const obj = topC(env, op.fca.numInputs() + 1);
    assertx(op.fca.numRets() == 1);
  
    if (!is_specialized_obj(obj)) {
      return fcallUnknownImpl(env, op.fca);
    }
  
    if (op.fca.lockWhileUnwinding() && !objMightHaveConstProps(obj)) {
      return reduce(
        env, bc::FCallCtor { op.fca.withoutLockWhileUnwinding(), op.str2 }
      );
    }
  
    auto const dobj = dobj_of(obj);
    auto const exact = dobj.type == DObj::Exact;
    auto const rfunc = env.index.resolve_ctor(env.ctx, dobj.cls, exact);
    if (!rfunc) {
      return fcallUnknownImpl(env, op.fca);
    }
  
    auto const updateFCA = [&] (FCallArgs&& fca) {
      return bc::FCallCtor { std::move(fca), op.str2 };
    };
  
    auto const numInOut = op.fca.enforceInOut()
      ? env.index.lookup_num_inout_params(env.ctx, *rfunc)
      : std::nullopt;
  
    auto const canFold = obj.subtypeOf(BObj);
    if (fcallOptimizeChecks(env, op.fca, *rfunc, updateFCA, numInOut, false, 0) ||
        (canFold && fcallTryFold(env, op.fca, *rfunc,
                                 obj, false /* dynamic */, 0))) {
      return;
    }
  
    if (rfunc->exactFunc() && op.str2->empty()) {
      // We've found the exact func that will be called, set the hint.
      return reduce(env, bc::FCallCtor { op.fca, rfunc->exactFunc()->cls->name });
    }
  
    fcallKnownImpl(env, op.fca, *rfunc, obj, false /* nullsafe */, 0,
                   updateFCA, numInOut);
  }
  
  void in(ISS& env, const bc::LockObj& op) {
    auto const t = topC(env);
    auto bail = [&]() {
      discard(env, 1);
      return push(env, t);
    };
    if (!t.subtypeOf(BObj)) return bail();
    if (!is_specialized_obj(t) || objMightHaveConstProps(t)) {
      nothrow(env);
      return bail();
    }
    reduce(env);
  }
  
  namespace {
  
  // baseLoc is NoLocalId for non-local iterators.
  void iterInitImpl(ISS& env, IterArgs ita, BlockId target, LocalId baseLoc) {
    auto const local = baseLoc != NoLocalId;
    auto const sourceLoc = local ? baseLoc : topStkLocal(env);
    auto const base = local ? locAsCell(env, baseLoc) : topC(env);
    auto ity = iter_types(base);
  
    auto const fallthrough = [&] {
      auto const baseCannotBeObject = !base.couldBe(BObj);
      setIter(env, ita.iterId, LiveIter { ity, sourceLoc, NoLocalId, env.bid,
                                          false, baseCannotBeObject });
      // Do this after setting the iterator, in case it clobbers the base local
      // equivalency.
      setLoc(env, ita.valId, std::move(ity.value));
      if (ita.hasKey()) {
        setLoc(env, ita.keyId, std::move(ity.key));
        setIterKey(env, ita.iterId, ita.keyId);
      }
    };
  
    assertx(iterIsDead(env, ita.iterId));
  
    if (!ity.mayThrowOnInit) {
      if (ity.count == IterTypes::Count::Empty && will_reduce(env)) {
        if (local) {
          reduce(env);
        } else {
          reduce(env, bc::PopC{});
        }
        return jmp_setdest(env, target);
      }
      nothrow(env);
    }
  
    if (!local) popC(env);
  
    switch (ity.count) {
      case IterTypes::Count::Empty:
        mayReadLocal(env, ita.valId);
        if (ita.hasKey()) mayReadLocal(env, ita.keyId);
        jmp_setdest(env, target);
        return;
      case IterTypes::Count::Single:
      case IterTypes::Count::NonEmpty:
        fallthrough();
        return jmp_nevertaken(env);
      case IterTypes::Count::ZeroOrOne:
      case IterTypes::Count::Any:
        // Take the branch before setting locals if the iter is already
        // empty, but after popping.  Similar for the other IterInits
        // below.
        env.propagate(target, &env.state);
        fallthrough();
        return;
    }
    always_assert(false);
  }
  
  // baseLoc is NoLocalId for non-local iterators.
  void iterNextImpl(ISS& env, IterArgs ita, BlockId target, LocalId baseLoc) {
    auto const curVal = peekLocRaw(env, ita.valId);
    auto const curKey = ita.hasKey() ? peekLocRaw(env, ita.keyId) : TBottom;
  
    auto noThrow = false;
    auto const noTaken = match<bool>(
      env.state.iters[ita.iterId],
      [&] (DeadIter)           {
        always_assert(false && "IterNext on dead iter");
        return false;
      },
      [&] (const LiveIter& ti) {
        if (!ti.types.mayThrowOnNext) noThrow = true;
        if (ti.baseLocal != NoLocalId) hasInvariantIterBase(env);
        switch (ti.types.count) {
          case IterTypes::Count::Single:
          case IterTypes::Count::ZeroOrOne:
            return true;
          case IterTypes::Count::NonEmpty:
          case IterTypes::Count::Any:
            setLoc(env, ita.valId, ti.types.value);
            if (ita.hasKey()) {
              setLoc(env, ita.keyId, ti.types.key);
              setIterKey(env, ita.iterId, ita.keyId);
            }
            return false;
          case IterTypes::Count::Empty:
            always_assert(false);
        }
        not_reached();
      }
    );
  
    if (noTaken && noThrow && will_reduce(env)) {
      auto const iterId = safe_cast<IterId>(ita.iterId);
      return baseLoc == NoLocalId
        ? reduce(env, bc::IterFree { iterId })
        : reduce(env, bc::LIterFree { iterId, baseLoc });
    }
  
    mayReadLocal(env, baseLoc);
    mayReadLocal(env, ita.valId);
    if (ita.hasKey()) mayReadLocal(env, ita.keyId);
  
    if (noThrow) nothrow(env);
  
    if (noTaken) {
      jmp_nevertaken(env);
      freeIter(env, ita.iterId);
      return;
    }
  
    env.propagate(target, &env.state);
  
    freeIter(env, ita.iterId);
    setLocRaw(env, ita.valId, curVal);
    if (ita.hasKey()) setLocRaw(env, ita.keyId, curKey);
  }
  
  }
  
  void in(ISS& env, const bc::IterInit& op) {
    iterInitImpl(env, op.ita, op.target2, NoLocalId);
  }
  
  void in(ISS& env, const bc::LIterInit& op) {
    iterInitImpl(env, op.ita, op.target3, op.loc2);
  }
  
  void in(ISS& env, const bc::IterNext& op) {
    iterNextImpl(env, op.ita, op.target2, NoLocalId);
  }
  
  void in(ISS& env, const bc::LIterNext& op) {
    iterNextImpl(env, op.ita, op.target3, op.loc2);
  }
  
  void in(ISS& env, const bc::IterFree& op) {
    // IterFree is used for weak iterators too, so we can't assert !iterIsDead.
    auto const isNop = match<bool>(
      env.state.iters[op.iter1],
      []  (DeadIter) {
        return true;
      },
      [&] (const LiveIter& ti) {
        if (ti.baseLocal != NoLocalId) hasInvariantIterBase(env);
        return false;
      }
    );
  
    if (isNop && will_reduce(env)) return reduce(env);
  
    nothrow(env);
    freeIter(env, op.iter1);
  }
  
  void in(ISS& env, const bc::LIterFree& op) {
    nothrow(env);
    mayReadLocal(env, op.loc2);
    freeIter(env, op.iter1);
  }
  
  /*
   * Any include/require (or eval) op kills all locals, and private properties.
   */
  void inclOpImpl(ISS& env) {
    popC(env);
    killLocals(env);
    killThisProps(env);
    killPrivateStatics(env);
    push(env, TInitCell);
  }
  
  void in(ISS& env, const bc::Incl&)      { inclOpImpl(env); }
  void in(ISS& env, const bc::InclOnce&)  { inclOpImpl(env); }
  void in(ISS& env, const bc::Req&)       { inclOpImpl(env); }
  void in(ISS& env, const bc::ReqOnce&)   { inclOpImpl(env); }
  void in(ISS& env, const bc::ReqDoc&)    { inclOpImpl(env); }
  void in(ISS& env, const bc::Eval&)      { inclOpImpl(env); }
  
  void in(ISS& env, const bc::This&) {
    if (thisAvailable(env)) {
      return reduce(env, bc::BareThis { BareThisOp::NeverNull });
    }
    auto const ty = thisTypeNonNull(env);
    push(env, ty, StackThisId);
    setThisAvailable(env);
    if (ty.subtypeOf(BBottom)) unreachable(env);
  }
  
  void in(ISS& env, const bc::LateBoundCls& op) {
    if (env.ctx.cls) effect_free(env);
    auto const ty = selfCls(env);
    push(env, setctx(ty ? *ty : TCls));
  }
  
  void in(ISS& env, const bc::CheckThis&) {
    if (thisAvailable(env)) {
      return reduce(env);
    }
    setThisAvailable(env);
  }
  
  void in(ISS& env, const bc::BareThis& op) {
    if (thisAvailable(env)) {
      if (op.subop1 != BareThisOp::NeverNull) {
        return reduce(env, bc::BareThis { BareThisOp::NeverNull });
      }
    }
  
    auto const ty = thisType(env);
    switch (op.subop1) {
      case BareThisOp::Notice:
        break;
      case BareThisOp::NoNotice:
        effect_free(env);
        break;
      case BareThisOp::NeverNull:
        setThisAvailable(env);
        if (!env.state.unreachable) effect_free(env);
        return push(env, ty, StackThisId);
    }
  
    push(env, ty, StackThisId);
  }
  
  /*
   * Amongst other things, we use this to mark units non-persistent.
   */
  void in(ISS& env, const bc::OODeclExists& op) {
    auto flag = popC(env);
    auto name = popC(env);
    push(env, [&] {
        if (!name.strictSubtypeOf(TStr)) return TBool;
        auto const v = tv(name);
        if (!v) return TBool;
        auto rcls = env.index.resolve_class(env.ctx, v->m_data.pstr);
        if (!rcls || !rcls->cls()) return TFalse;
        auto const exist = [&] () -> bool {
          switch (op.subop1) {
            case OODeclExistsOp::Class:
              return !(rcls->cls()->attrs & (AttrInterface | AttrTrait));
            case OODeclExistsOp::Interface:
              return rcls->cls()->attrs & AttrInterface;
            case OODeclExistsOp::Trait:
              return rcls->cls()->attrs & AttrTrait;
          }
          not_reached();
        }();
        constprop(env);
        return exist ? TTrue : TFalse;
      } ());
  }
  
  namespace {
  bool couldBeMocked(const Type& t) {
    if (is_specialized_cls(t)) {
      return dcls_of(t).cls.couldBeMocked();
    } else if (is_specialized_obj(t)) {
      return dobj_of(t).cls.couldBeMocked();
    }
    // In practice this should not occur since this is used mostly on the result
    // of looked up type constraints.
    return true;
  }
  }
  
  using TCVec = std::vector<const TypeConstraint*>;
  
  void in(ISS& env, const bc::VerifyParamType& op) {
    IgnoreUsedParams _{env};
  
    if (env.ctx.func->isMemoizeImpl) {
      // a MemoizeImpl's params have already been checked by the wrapper
      return reduce(env);
    }
  
    auto const& pinfo = env.ctx.func->params[op.loc1];
    // Generally we won't know anything about the params, but
    // analyze_func_inline does - and this can help with effect-free analysis
    TCVec tcs = {&pinfo.typeConstraint};
    for (auto const& t : pinfo.upperBounds) tcs.push_back(&t);
    if (std::all_of(std::begin(tcs), std::end(tcs),
          [&](const TypeConstraint* tc) {
            return env.index.satisfies_constraint(env.ctx,
                                                  locAsCell(env, op.loc1),
                                                  *tc);
            })) {
      if (!locAsCell(env, op.loc1).couldBe(BCls)) {
        return reduce(env);
      }
    }
  
    /*
     * We assume that if this opcode doesn't throw, the parameter was of the
     * specified type.
     */
    auto tcT = TTop;
    for (auto const& constraint : tcs) {
      if (constraint->hasConstraint() && !constraint->isTypeVar() &&
        !constraint->isTypeConstant()) {
        auto t = env.index.lookup_constraint(env.ctx, *constraint);
        if (constraint->isThis() && couldBeMocked(t)) {
          t = unctx(std::move(t));
        }
        FTRACE(2, "     {} ({})\n", constraint->fullName(), show(t));
        tcT = intersection_of(std::move(tcT), std::move(t));
        if (tcT.subtypeOf(BBottom)) unreachable(env);
      }
    }
    if (tcT != TTop) setLoc(env, op.loc1, std::move(tcT));
  }
  
  void in(ISS& env, const bc::VerifyParamTypeTS& op) {
    auto const a = topC(env);
    if (!a.couldBe(BDict)) {
      unreachable(env);
      popC(env);
      return;
    }
    auto const constraint = env.ctx.func->params[op.loc1].typeConstraint;
    // TODO(T31677864): We are being extremely pessimistic here, relax it
    if (!env.ctx.func->isReified &&
        (!env.ctx.cls || !env.ctx.cls->hasReifiedGenerics) &&
        !env.index.could_have_reified_type(env.ctx, constraint)) {
      return reduce(env, bc::PopC {}, bc::VerifyParamType { op.loc1 });
    }
  
    if (auto const inputTS = tv(a)) {
      if (!isValidTSType(*inputTS, false)) {
        unreachable(env);
        popC(env);
        return;
      }
      auto const resolvedTS =
        resolve_type_structure(env, inputTS->m_data.parr).sarray();
      if (resolvedTS && resolvedTS != inputTS->m_data.parr) {
        reduce(env, bc::PopC {});
        reduce(env, bc::Dict { resolvedTS });
        reduce(env, bc::VerifyParamTypeTS { op.loc1 });
        return;
      }
      if (shouldReduceToNonReifiedVerifyType(env, inputTS->m_data.parr)) {
        return reduce(env, bc::PopC {}, bc::VerifyParamType { op.loc1 });
      }
    }
    if (auto const last = last_op(env)) {
      if (last->op == Op::CombineAndResolveTypeStruct) {
        if (auto const last2 = last_op(env, 1)) {
          if (last2->op == Op::Dict &&
              shouldReduceToNonReifiedVerifyType(env, last2->Dict.arr1)) {
            return reduce(env, bc::PopC {}, bc::VerifyParamType { op.loc1 });
          }
        }
      }
    }
    popC(env);
  }
  
  void verifyRetImpl(ISS& env, const TCVec& tcs,
                     bool reduce_this, bool ts_flavor) {
    // If it is the ts flavor, then second thing on the stack, otherwise first
    auto stackT = topC(env, (int)ts_flavor);
    auto const stackEquiv = topStkEquiv(env, (int)ts_flavor);
  
    // If there is no return type constraint, or if the return type
    // constraint is a typevar, or if the top of stack is the same or a
    // subtype of the type constraint, then this is a no-op, unless
    // reified types could be involved.
    if (std::all_of(std::begin(tcs), std::end(tcs),
                    [&](const TypeConstraint* tc) {
                      return env.index.satisfies_constraint(env.ctx, stackT, *tc);
                    })) {
      if (ts_flavor) {
        // we wouldn't get here if reified types were definitely not
        // involved, so just bail.
        popC(env);
        popC(env);
        push(env, std::move(stackT), stackEquiv);
        return;
      }
      return reduce(env);
    }
  
    std::vector<Type> constraintTypes;
    auto dont_reduce = false;
  
    for (auto const& constraint : tcs) {
      // When the constraint is not soft.
      // We can safely assume that either VerifyRetTypeC will
      // throw or it will produce a value whose type is compatible with the
      // return type constraint.
      auto tcT = remove_uninit(env.index.lookup_constraint(env.ctx, *constraint));
      constraintTypes.push_back(tcT);
  
      // In some circumstances, verifyRetType can modify the type. If it
      // does that we can't reduce even when we know it succeeds.
      // VerifyRetType will convert a TCls to a TStr implicitly
      // (and possibly warn)
      if (tcT.couldBe(BStr) && stackT.couldBe(BCls | BLazyCls)) {
        stackT |= TSStr;
        dont_reduce = true;
      }
  
      // If the constraint is soft, then there are no optimizations we can safely
      // do here, so just leave the top of stack as is.
      if (constraint->isSoft() ||
          (RuntimeOption::EvalEnforceGenericsUB < 2 &&
           constraint->isUpperBound()))
      {
        if (ts_flavor) popC(env);
        popC(env);
        push(env, std::move(stackT), stackEquiv);
        return;
      }
    }
  
    // In cases where we have a `this` hint where stackT is an TOptObj known to
    // be this, we can replace the check with a non null check.  These cases are
    // likely from a BareThis that could return Null.  Since the runtime will
    // split these translations, it will rarely in practice return null.
    if (reduce_this &&
        !dont_reduce &&
        stackT.couldBe(BInitNull) &&
        !stackT.subtypeOf(BInitNull) &&
        std::all_of(std::begin(tcs), std::end(tcs),
                    [&](const TypeConstraint* constraint) {
                      return constraint->isThis() &&
                             !constraint->isNullable() &&
                             env.index.satisfies_constraint(
                               env.ctx, unopt(stackT), *constraint);
                      }
                    )
    ) {
      if (ts_flavor) {
        return reduce(env, bc::PopC {}, bc::VerifyRetNonNullC {});
      }
      return reduce(env, bc::VerifyRetNonNullC {});
    }
  
    auto retT = std::move(stackT);
    for (auto& tcT : constraintTypes) {
      retT = intersection_of(std::move(tcT), std::move(retT));
      if (retT.subtypeOf(BBottom)) {
        unreachable(env);
        if (ts_flavor) popC(env); // the type structure
        return;
      }
    }
  
    if (ts_flavor) popC(env); // the type structure
    popC(env);
    push(env, std::move(retT));
  }
  
  void in(ISS& env, const bc::VerifyOutType& op) {
    TCVec tcs;
    auto const& pinfo = env.ctx.func->params[op.arg1];
    tcs.push_back(&pinfo.typeConstraint);
    for (auto const& t : pinfo.upperBounds) tcs.push_back(&t);
    verifyRetImpl(env, tcs, false, false);
  }
  
  void in(ISS& env, const bc::VerifyRetTypeC& /*op*/) {
    TCVec tcs;
    tcs.push_back(&env.ctx.func->retTypeConstraint);
    for (auto const& t : env.ctx.func->returnUBs) tcs.push_back(&t);
    verifyRetImpl(env, tcs, true, false);
  }
  
  void in(ISS& env, const bc::VerifyRetTypeTS& /*op*/) {
    auto const a = topC(env);
    if (!a.couldBe(BDict)) {
      unreachable(env);
      popC(env);
      return;
    }
    auto const constraint = env.ctx.func->retTypeConstraint;
    // TODO(T31677864): We are being extremely pessimistic here, relax it
    if (!env.ctx.func->isReified &&
        (!env.ctx.cls || !env.ctx.cls->hasReifiedGenerics) &&
        !env.index.could_have_reified_type(env.ctx, constraint)) {
      return reduce(env, bc::PopC {}, bc::VerifyRetTypeC {});
    }
    if (auto const inputTS = tv(a)) {
      if (!isValidTSType(*inputTS, false)) {
        unreachable(env);
        popC(env);
        return;
      }
      auto const resolvedTS =
        resolve_type_structure(env, inputTS->m_data.parr).sarray();
      if (resolvedTS && resolvedTS != inputTS->m_data.parr) {
        reduce(env, bc::PopC {});
        reduce(env, bc::Dict { resolvedTS });
        reduce(env, bc::VerifyRetTypeTS {});
        return;
      }
      if (shouldReduceToNonReifiedVerifyType(env, inputTS->m_data.parr)) {
        return reduce(env, bc::PopC {}, bc::VerifyRetTypeC {});
      }
    }
    if (auto const last = last_op(env)) {
      if (last->op == Op::CombineAndResolveTypeStruct) {
        if (auto const last2 = last_op(env, 1)) {
          if (last2->op == Op::Dict &&
              shouldReduceToNonReifiedVerifyType(env, last2->Dict.arr1)) {
            return reduce(env, bc::PopC {}, bc::VerifyRetTypeC {});
          }
        }
      }
    }
    TCVec tcs {&constraint};
    for (auto const& t : env.ctx.func->returnUBs) tcs.push_back(&t);
    verifyRetImpl(env, tcs, true, true);
  }
  
  void in(ISS& env, const bc::VerifyRetNonNullC& /*op*/) {
    auto const constraint = env.ctx.func->retTypeConstraint;
    if (constraint.isSoft()) {
      return;
    }
  
    auto stackT = topC(env);
  
    if (!stackT.couldBe(BInitNull)) {
      reduce(env);
      return;
    }
  
    if (stackT.subtypeOf(BNull)) return unreachable(env);
  
    auto const equiv = topStkEquiv(env);
  
    stackT = unopt(std::move(stackT));
  
    popC(env);
    push(env, stackT, equiv);
  }
  
  void in(ISS& env, const bc::Self& op) {
    auto const self = selfClsExact(env);
    if (self) {
      effect_free(env);
      push(env, *self);
    } else {
      push(env, TCls);
    }
  }
  
  void in(ISS& env, const bc::Parent& op) {
    auto const parent = parentClsExact(env);
    if (parent) {
      effect_free(env);
      push(env, *parent);
    } else {
      push(env, TCls);
    }
  }
  
  void in(ISS& env, const bc::CreateCl& op) {
    auto const nargs   = op.arg1;
    auto const clsPair = env.index.resolve_closure_class(env.ctx, op.arg2);
  
    /*
     * Every closure should have a unique allocation site, but we may see it
     * multiple times in a given round of analyzing this function.  Each time we
     * may have more information about the used variables; the types should only
     * possibly grow.  If it's already there we need to merge the used vars in
     * with what we saw last time.
     */
    if (nargs) {
      CompactVector<Type> usedVars(nargs);
      for (auto i = uint32_t{0}; i < nargs; ++i) {
        usedVars[nargs - i - 1] = unctx(popCU(env));
      }
      merge_closure_use_vars_into(
        env.collect.closureUseTypes,
        clsPair.second,
        std::move(usedVars)
      );
    }
  
    // Closure classes can be cloned and rescoped at runtime, so it's not safe to
    // assert the exact type of closure objects. The best we can do is assert
    // that it's a subclass of Closure.
    auto const closure = env.index.builtin_class(s_Closure.get());
  
    return push(env, subObj(closure));
  }
  
  void in(ISS& env, const bc::CreateCont& /*op*/) {
    // First resume is always next() which pushes null.
    push(env, TInitNull);
  }
  
  void in(ISS& env, const bc::ContEnter&) { popC(env); push(env, TInitCell); }
  void in(ISS& env, const bc::ContRaise&) { popC(env); push(env, TInitCell); }
  
  void in(ISS& env, const bc::Yield&) {
    popC(env);
    push(env, TInitCell);
  }
  
  void in(ISS& env, const bc::YieldK&) {
    popC(env);
    popC(env);
    push(env, TInitCell);
  }
  
  void in(ISS& /*env*/, const bc::ContCheck&) {}
  void in(ISS& env, const bc::ContValid&)   { push(env, TBool); }
  void in(ISS& env, const bc::ContKey&)     { push(env, TInitCell); }
  void in(ISS& env, const bc::ContCurrent&) { push(env, TInitCell); }
  void in(ISS& env, const bc::ContGetReturn&) { push(env, TInitCell); }
  
  void pushTypeFromWH(ISS& env, Type t) {
    auto inner = typeFromWH(t);
    // The next opcode is unreachable if awaiting a non-object or WaitH<Bottom>.
    if (inner.subtypeOf(BBottom)) unreachable(env);
    push(env, std::move(inner));
  }
  
  void in(ISS& env, const bc::WHResult&) {
    pushTypeFromWH(env, popC(env));
  }
  
  void in(ISS& env, const bc::Await&) {
    pushTypeFromWH(env, popC(env));
  }
  
  void in(ISS& env, const bc::AwaitAll& op) {
    auto const equiv = equivLocalRange(env, op.locrange);
    if (equiv != op.locrange.first) {
      return reduce(
        env,
        bc::AwaitAll {LocalRange {equiv, op.locrange.count}}
      );
    }
  
    for (uint32_t i = 0; i < op.locrange.count; ++i) {
      mayReadLocal(env, op.locrange.first + i);
    }
  
    push(env, TInitNull);
  }
  
  void in(ISS& env, const bc::SetImplicitContextByValue&) {
    popC(env);
    push(env, TInt);
  }
  
  void in(ISS& env, const bc::Idx&) {
    auto const def = popC(env);
    auto const [key, promotion] = promote_classlike_to_key(popC(env));
    auto const base = popC(env);
  
    assertx(!def.is(BBottom));
  
    auto effectFree = promotion != Promotion::YesMightThrow;
    auto result = TBottom;
  
    auto const finish = [&] {
      if (result.is(BBottom)) {
        assertx(!effectFree);
        unreachable(env);
      }
      if (effectFree) {
        constprop(env);
        effect_free(env);
      }
      push(env, std::move(result));
    };
  
    if (key.couldBe(BNull)) result |= def;
    if (key.subtypeOf(BNull)) return finish();
  
    if (!base.subtypeOf(BArrLike | BObj | BStr)) result |= def;
  
    if (base.couldBe(BArrLike)) {
      if (!key.subtypeOf(BOptArrKey)) effectFree = false;
      if (key.couldBe(BArrKey)) {
        auto elem = array_like_elem(
          base,
          key.subtypeOf(BArrKey) ? key : intersection_of(key, TArrKey)
        );
        result |= std::move(elem.first);
        if (!elem.second) result |= def;
      }
    }
    if (base.couldBe(BObj)) {
      result |= TInitCell;
      effectFree = false;
    }
    if (base.couldBe(BStr)) {
      result |= TSStr;
      result |= def;
      if (!key.subtypeOf(BOptArrKey)) effectFree = false;
    }
  
    finish();
  }
  
  void in(ISS& env, const bc::ArrayIdx&) {
    auto def = popC(env);
    auto const [key, promotion] = promote_classlike_to_key(popC(env));
    auto const base = popC(env);
  
    assertx(!def.is(BBottom));
  
    auto effectFree = promotion != Promotion::YesMightThrow;
    auto result = TBottom;
  
    auto const finish = [&] {
      if (result.is(BBottom)) {
        assertx(!effectFree);
        unreachable(env);
      }
      if (effectFree) {
        constprop(env);
        effect_free(env);
      }
      push(env, std::move(result));
    };
  
    if (key.couldBe(BNull)) result |= def;
    if (key.subtypeOf(BNull)) return finish();
  
    if (!base.subtypeOf(BArrLike)) effectFree = false;
    if (!base.couldBe(BArrLike)) return finish();
  
    if (!key.subtypeOf(BOptArrKey)) effectFree = false;
    if (!key.couldBe(BArrKey)) return finish();
  
    auto elem = array_like_elem(
      base,
      key.subtypeOf(BArrKey) ? key : intersection_of(key, TArrKey)
    );
    result |= std::move(elem.first);
    if (!elem.second) result |= std::move(def);
    finish();
  }
  
  namespace {
  void implArrayMarkLegacy(ISS& env, bool legacy) {
    auto const recursive = popC(env);
    auto const value = popC(env);
  
    if (auto const tv_recursive = tv(recursive)) {
      if (auto const tv_value = tv(value)) {
        if (tvIsBool(*tv_recursive)) {
          auto const result = eval_cell([&]{
            return val(*tv_recursive).num
              ? arrprov::markTvRecursively(*tv_value, legacy)
              : arrprov::markTvShallow(*tv_value, legacy);
          });
          if (result) {
            push(env, *result);
            effect_free(env);
            constprop(env);
            return;
          }
        }
      }
    }
  
    // TODO(kshaunak): We could add some type info here.
    push(env, TInitCell);
  }
  }
  
  void in(ISS& env, const bc::ArrayMarkLegacy&) {
    implArrayMarkLegacy(env, true);
  }
  
  void in(ISS& env, const bc::ArrayUnmarkLegacy&) {
    implArrayMarkLegacy(env, false);
  }
  
  void in(ISS& env, const bc::CheckProp&) {
    if (env.ctx.cls->attrs & AttrNoOverride) {
      return reduce(env, bc::False {});
    }
    effect_free(env);
    push(env, TBool);
  }
  
  void in(ISS& env, const bc::InitProp& op) {
    auto const t = topC(env);
    switch (op.subop2) {
      case InitPropOp::Static:
        env.index.merge_static_type(
          env.ctx,
          env.collect.publicSPropMutations,
          env.collect.props,
          clsExact(env.index.resolve_class(env.ctx.cls)),
          sval(op.str1),
          t,
          false,
          true
        );
        break;
      case InitPropOp::NonStatic:
        mergeThisProp(env, op.str1, t);
        break;
    }
  
    for (auto& prop : env.ctx.func->cls->properties) {
      if (prop.name != op.str1) continue;
  
      ITRACE(1, "InitProp: {} = {}\n", op.str1, show(t));
  
      if (env.index.satisfies_constraint(env.ctx, t, prop.typeConstraint) &&
          std::all_of(prop.ubs.begin(), prop.ubs.end(),
                      [&](TypeConstraint ub) {
                        applyFlagsToUB(ub, prop.typeConstraint);
                        return env.index.satisfies_constraint(env.ctx, t, ub);
                      })) {
        prop.attrs |= AttrInitialSatisfiesTC;
      } else {
        badPropInitialValue(env);
        prop.attrs = (Attr)(prop.attrs & ~AttrInitialSatisfiesTC);
        continue;
      }
  
      auto const v = tv(t);
      if (v || !could_contain_objects(t)) {
        prop.attrs = (Attr)(prop.attrs & ~AttrDeepInit);
        if (!v) break;
        prop.val = *v;
        env.index.update_static_prop_init_val(env.ctx.func->cls, op.str1);
        return reduce(env, bc::PopC {});
      }
    }
  
    popC(env);
  }
  
  void in(ISS& env, const bc::Silence& op) {
    nothrow(env);
    switch (op.subop2) {
      case SilenceOp::Start:
        setLoc(env, op.loc1, TInt);
        break;
      case SilenceOp::End:
        locRaw(env, op.loc1);
        break;
    }
  }
  
  namespace {
  
  template <typename Op, typename Rebind>
  bool memoGetImpl(ISS& env, const Op& op, Rebind&& rebind) {
    always_assert(env.ctx.func->isMemoizeWrapper);
    always_assert(op.locrange.first + op.locrange.count
                  <= env.ctx.func->locals.size());
  
    if (will_reduce(env)) {
      // If we can use an equivalent, earlier range, then use that instead.
      auto const equiv = equivLocalRange(env, op.locrange);
      if (equiv != op.locrange.first) {
        reduce(env, rebind(LocalRange { equiv, op.locrange.count }));
        return true;
      }
    }
  
    auto retTy = memoizeImplRetType(env);
  
    // MemoGet can raise if we give a non arr-key local, or if we're in a method
    // and $this isn't available.
    auto allArrKey = true;
    for (uint32_t i = 0; i < op.locrange.count; ++i) {
      allArrKey &= locRaw(env, op.locrange.first + i).subtypeOf(BArrKey);
    }
    if (allArrKey &&
        (!env.ctx.func->cls ||
         (env.ctx.func->attrs & AttrStatic) ||
         thisAvailable(env))) {
      if (will_reduce(env)) {
        if (retTy.first.subtypeOf(BBottom)) {
          reduce(env);
          jmp_setdest(env, op.target1);
          return true;
        }
        // deal with constprop manually; otherwise we will propagate the
        // taken edge and *then* replace the MemoGet with a constant.
        if (retTy.second) {
          if (auto v = tv(retTy.first)) {
            reduce(env, gen_constant(*v));
            return true;
          }
        }
      }
      effect_free(env);
    }
  
    if (retTy.first == TBottom) {
      jmp_setdest(env, op.target1);
      return true;
    }
  
    env.propagate(op.target1, &env.state);
    push(env, std::move(retTy.first));
    return false;
  }
  
  }
  
  void in(ISS& env, const bc::MemoGet& op) {
    memoGetImpl(
      env, op,
      [&] (const LocalRange& l) { return bc::MemoGet { op.target1, l }; }
    );
  }
  
  void in(ISS& env, const bc::MemoGetEager& op) {
    always_assert(env.ctx.func->isAsync && !env.ctx.func->isGenerator);
  
    auto const reduced = memoGetImpl(
      env, op,
      [&] (const LocalRange& l) {
        return bc::MemoGetEager { op.target1, op.target2, l };
      }
    );
    if (reduced) return;
  
    env.propagate(op.target2, &env.state);
    auto const t = popC(env);
    push(
      env,
      is_specialized_wait_handle(t) ? wait_handle_inner(t) : TInitCell
    );
  }
  
  namespace {
  
  template <typename Op>
  void memoSetImpl(ISS& env, const Op& op) {
    always_assert(env.ctx.func->isMemoizeWrapper);
    always_assert(op.locrange.first + op.locrange.count
                  <= env.ctx.func->locals.size());
  
    // If we can use an equivalent, earlier range, then use that instead.
    auto const equiv = equivLocalRange(env, op.locrange);
    if (equiv != op.locrange.first) {
      return reduce(
        env,
        Op { LocalRange { equiv, op.locrange.count } }
      );
    }
  
    // MemoSet can raise if we give a non arr-key local, or if we're in a method
    // and $this isn't available.
    auto allArrKey = true;
    for (uint32_t i = 0; i < op.locrange.count; ++i) {
      allArrKey &= locRaw(env, op.locrange.first + i).subtypeOf(BArrKey);
    }
    if (allArrKey &&
        (!env.ctx.func->cls ||
         (env.ctx.func->attrs & AttrStatic) ||
         thisAvailable(env))) {
      nothrow(env);
    }
    push(env, popC(env));
  }
  
  }
  
  void in(ISS& env, const bc::MemoSet& op) {
    memoSetImpl(env, op);
  }
  
  void in(ISS& env, const bc::MemoSetEager& op) {
    always_assert(env.ctx.func->isAsync && !env.ctx.func->isGenerator);
    memoSetImpl(env, op);
  }
  
  }
  
  namespace {
  
  //////////////////////////////////////////////////////////////////////
  
  void dispatch(ISS& env, const Bytecode& op) {
  #define O(opcode, ...) case Op::opcode: interp_step::in(env, op.opcode); return;
    switch (op.op) { OPCODES }
  #undef O
    not_reached();
  }
  
  //////////////////////////////////////////////////////////////////////
  
  void interpStep(ISS& env, const Bytecode& bc) {
    ITRACE(2, "  {} ({})\n",
           show(env.ctx.func, bc),
           env.unchangedBcs + env.replacedBcs.size());
    Trace::Indent _;
  
    // If there are throw exit edges, make a copy of the state (except
    // stacks) in case we need to propagate across throw exits (if
    // it's a PEI).
    if (!env.stateBefore && env.blk.throwExit != NoBlockId) {
      env.stateBefore.emplace(with_throwable_only(env.index, env.state));
    }
  
    env.flags = {};
  
    default_dispatch(env, bc);
  
    if (env.flags.reduced) return;
  
    auto const_prop = [&] {
      if (!options.ConstantProp || !env.flags.canConstProp) return false;
  
      auto const numPushed   = bc.numPush();
      TinyVector<TypedValue> cells;
  
      auto i = size_t{0};
      while (i < numPushed) {
        auto const v = tv(topT(env, i));
        if (!v) return false;
        cells.push_back(*v);
        ++i;
      }
  
      if (env.flags.wasPEI) {
        ITRACE(2, "   nothrow (due to constprop)\n");
        env.flags.wasPEI = false;
      }
      if (!env.flags.effectFree) {
        ITRACE(2, "   effect_free (due to constprop)\n");
        env.flags.effectFree = true;
      }
  
      // If we're doing inline interp, don't actually perform the
      // constprop. If we do, we can infer static types that won't
      // actually exist at runtime.
      if (any(env.collect.opts & CollectionOpts::Inlining)) {
        ITRACE(2, "   inlining, skipping actual constprop\n");
        return false;
      }
  
      rewind(env, bc);
  
      auto const numPop = bc.numPop();
      for (auto j = 0; j < numPop; j++) {
        auto const flavor = bc.popFlavor(j);
        if (flavor == Flavor::C) {
          interpStep(env, bc::PopC {});
        } else if (flavor == Flavor::U) {
          interpStep(env, bc::PopU {});
        } else {
          assertx(flavor == Flavor::CU);
          auto const& popped = topT(env);
          if (popped.subtypeOf(BUninit)) {
            interpStep(env, bc::PopU {});
          } else {
            assertx(popped.subtypeOf(BInitCell));
            interpStep(env, bc::PopC {});
          }
        }
      }
  
      while (i--) {
        push(env, from_cell(cells[i]));
        record(env, gen_constant(cells[i]));
      }
      return true;
    };
  
    if (const_prop()) {
      return;
    }
  
    assertx(!env.flags.effectFree || !env.flags.wasPEI);
    if (env.flags.wasPEI) {
      ITRACE(2, "   PEI.\n");
      if (env.stateBefore) {
        env.propagate(env.blk.throwExit, &*env.stateBefore);
      }
    }
    env.stateBefore.reset();
  
    record(env, bc);
  }
  
  void interpOne(ISS& env, const Bytecode& bc) {
    env.srcLoc = bc.srcLoc;
    interpStep(env, bc);
  }
  
  BlockId speculate(Interp& interp) {
    auto low_water = interp.state.stack.size();
  
    interp.collect.opts = interp.collect.opts | CollectionOpts::Speculating;
    SCOPE_EXIT {
      interp.collect.opts = interp.collect.opts - CollectionOpts::Speculating;
    };
  
    auto failed = false;
    ISS env { interp, [&] (BlockId, const State*) { failed = true; } };
  
    FTRACE(4, "  Speculate B{}\n", interp.bid);
    for (auto const& bc : interp.blk->hhbcs) {
      assertx(!interp.state.unreachable);
      auto const numPop = bc.numPop() +
        (bc.op == Op::CGetL2 ? 1 :
         bc.op == Op::Dup ? -1 : 0);
      if (interp.state.stack.size() - numPop < low_water) {
        low_water = interp.state.stack.size() - numPop;
      }
  
      interpOne(env, bc);
      if (failed) {
        env.collect.mInstrState.clear();
        FTRACE(3, "  Bailing from speculate because propagate was called\n");
        return NoBlockId;
      }
  
      auto const& flags = env.flags;
      if (!flags.effectFree) {
        env.collect.mInstrState.clear();
        FTRACE(3, "  Bailing from speculate because not effect free\n");
        return NoBlockId;
      }
  
      assertx(!flags.returned);
  
      if (flags.jmpDest != NoBlockId && interp.state.stack.size() == low_water) {
        FTRACE(2, "  Speculate found target block {}\n", flags.jmpDest);
        return flags.jmpDest;
      }
    }
  
    if (interp.state.stack.size() != low_water) {
      FTRACE(3,
             "  Bailing from speculate because the speculated block "
             "left items on the stack\n");
      return NoBlockId;
    }
  
    if (interp.blk->fallthrough == NoBlockId) {
      FTRACE(3,
             "  Bailing from speculate because there was no fallthrough");
      return NoBlockId;
    }
  
    FTRACE(2, "  Speculate found fallthrough block {}\n",
           interp.blk->fallthrough);
  
    return interp.blk->fallthrough;
  }
  
  BlockId speculateHelper(ISS& env, BlockId orig, bool updateTaken) {
    assertx(orig != NoBlockId);
  
    if (!will_reduce(env)) return orig;
  
    auto const last = last_op(env);
    bool endsInControlFlow = last && instrIsNonCallControlFlow(last->op);
    auto target = orig;
    auto pops = 0;
  
    if (options.RemoveDeadBlocks) {
      State temp{env.state, State::Compact{}};
      while (true) {
        auto const& func = env.ctx.func;
        auto const targetBlk = func.blocks()[target].get();
        if (!targetBlk->multiPred) break;
        auto const ok = [&] {
          switch (targetBlk->hhbcs.back().op) {
            case Op::JmpZ:
            case Op::JmpNZ:
            case Op::SSwitch:
            case Op::Switch:
            return true;
            default:
            return false;
          }
        }();
  
        if (!ok) break;
  
        Interp interp {
          env.index, env.ctx, env.collect, target, targetBlk, temp
        };
  
        auto const old_size = temp.stack.size();
        auto const new_target = speculate(interp);
        if (new_target == NoBlockId) break;
  
        const ssize_t delta = old_size - temp.stack.size();
        assertx(delta >= 0);
        if (delta && endsInControlFlow) break;
  
        pops += delta;
        target = new_target;
        temp.stack.compact();
      }
    }
  
    if (endsInControlFlow && updateTaken) {
      assertx(!pops);
      auto needsUpdate = target != orig;
      if (!needsUpdate) {
        forEachTakenEdge(
          *last,
          [&] (BlockId bid) {
            if (bid != orig) needsUpdate = true;
          }
        );
      }
      if (needsUpdate) {
        auto& bc = mutate_last_op(env);
        forEachTakenEdge(
          bc,
          [&] (BlockId& bid) {
            bid = bid == orig ? target : NoBlockId;
          }
        );
      }
    }
  
    while (pops--) {
      auto const& popped = topT(env);
      if (popped.subtypeOf(BInitCell)) {
        interpStep(env, bc::PopC {});
      } else {
        assertx(popped.subtypeOf(BUninit));
        interpStep(env, bc::PopU {});
      }
    }
  
    return target;
  }
  
  }
  
  //////////////////////////////////////////////////////////////////////
  
  RunFlags run(Interp& interp, const State& in, PropagateFn propagate) {
    SCOPE_EXIT {
      FTRACE(2, "out {}{}\n",
             state_string(*interp.ctx.func, interp.state, interp.collect),
             property_state_string(interp.collect.props));
    };
  
    auto env = ISS { interp, propagate };
    auto ret = RunFlags {};
    auto finish = [&] (BlockId fallthrough) {
      ret.updateInfo.fallthrough = fallthrough;
      ret.updateInfo.unchangedBcs = env.unchangedBcs;
      ret.updateInfo.replacedBcs = std::move(env.replacedBcs);
      return ret;
    };
  
    BytecodeVec retryBcs;
    auto retryOffset = interp.blk->hhbcs.size();
    auto size = retryOffset;
    BlockId retryFallthrough = interp.blk->fallthrough;
    size_t idx = 0;
  
    while (true) {
      if (idx == size) {
        finish_tracked_elems(env, 0);
        if (!env.reprocess) break;
        FTRACE(2, "  Reprocess mutated block {}\n", interp.bid);
        assertx(env.unchangedBcs < retryOffset || env.replacedBcs.size());
        assertx(!env.undo);
        retryOffset = env.unchangedBcs;
        retryBcs = std::move(env.replacedBcs);
        env.unchangedBcs = 0;
        env.state.copy_from(in);
        env.reprocess = false;
        env.replacedBcs.clear();
        size = retryOffset + retryBcs.size();
        idx = 0;
        continue;
      }
  
      auto const& bc = idx < retryOffset ?
        interp.blk->hhbcs[idx] : retryBcs[idx - retryOffset];
      ++idx;
  
      interpOne(env, bc);
      auto const& flags = env.flags;
  
      if (flags.wasPEI) ret.noThrow = false;
  
      if (interp.collect.effectFree && !flags.effectFree) {
        interp.collect.effectFree = false;
        if (any(interp.collect.opts & CollectionOpts::EffectFreeOnly)) {
          env.collect.mInstrState.clear();
          FTRACE(2, "  Bailing because not effect free\n");
          return finish(NoBlockId);
        }
      }
  
      if (flags.returned) {
        always_assert(idx == size);
        if (env.reprocess) continue;
  
        always_assert(interp.blk->fallthrough == NoBlockId);
        assertx(!ret.returned);
        FTRACE(2, "  returned {}\n", show(*flags.returned));
        ret.retParam = flags.retParam;
        ret.returned = flags.returned;
        return finish(NoBlockId);
      }
  
      if (flags.jmpDest != NoBlockId) {
        always_assert(idx == size);
        auto const hasFallthrough = [&] {
          if (flags.jmpDest != interp.blk->fallthrough) {
            FTRACE(2, "  <took branch; no fallthrough>\n");
            auto const last = last_op(env);
            return !last || !instrIsNonCallControlFlow(last->op);
          } else {
            FTRACE(2, "  <branch never taken>\n");
            return true;
          }
        }();
        if (hasFallthrough) retryFallthrough = flags.jmpDest;
        if (env.reprocess) continue;
        finish_tracked_elems(env, 0);
        auto const newDest = speculateHelper(env, flags.jmpDest, true);
        propagate(newDest, &interp.state);
        return finish(hasFallthrough ? newDest : NoBlockId);
      }
  
      if (interp.state.unreachable) {
        if (env.reprocess) {
          idx = size;
          continue;
        }
        FTRACE(2, "  <bytecode fallthrough is unreachable>\n");
        finish_tracked_elems(env, 0);
        return finish(NoBlockId);
      }
    }
  
    FTRACE(2, "  <end block>\n");
    if (retryFallthrough != NoBlockId) {
      retryFallthrough = speculateHelper(env, retryFallthrough, false);
      propagate(retryFallthrough, &interp.state);
    }
    return finish(retryFallthrough);
  }
  
  StepFlags step(Interp& interp, const Bytecode& op) {
    auto noop    = [] (BlockId, const State*) {};
    ISS env { interp, noop };
    env.analyzeDepth++;
    default_dispatch(env, op);
    if (env.state.unreachable) {
      env.collect.mInstrState.clear();
    }
    assertx(env.trackedElems.empty());
    return env.flags;
  }
  
  void default_dispatch(ISS& env, const Bytecode& op) {
    if (!env.trackedElems.empty()) {
      auto const pops = [&] () -> uint32_t {
        switch (op.op) {
          case Op::AddElemC:
          case Op::AddNewElemC:
            return numPop(op) - 1;
          case Op::Concat:
          case Op::ConcatN:
            return 0;
          default:
            return numPop(op);
        }
      }();
  
      finish_tracked_elems(env, env.state.stack.size() - pops);
    }
    dispatch(env, op);
    if (instrFlags(op.op) & TF && env.flags.jmpDest == NoBlockId) {
      unreachable(env);
    } else if (env.state.unreachable) {
      env.collect.mInstrState.clear();
    }
  }
  
  Optional<Type> thisType(const Index& index, Context ctx) {
    return thisTypeFromContext(index, ctx);
  }
  
  //////////////////////////////////////////////////////////////////////
  
  }}
  