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/runtime/vm/jit/simplify.h"
  
  #include "hphp/runtime/base/array-data-defs.h"
  #include "hphp/runtime/base/array-init.h"
  #include "hphp/runtime/base/bespoke-array.h"
  #include "hphp/runtime/base/bespoke/struct-dict.h"
  #include "hphp/runtime/base/comparisons.h"
  #include "hphp/runtime/base/double-to-int64.h"
  #include "hphp/runtime/base/repo-auth-type-array.h"
  #include "hphp/runtime/base/tv-refcount.h"
  #include "hphp/runtime/base/tv-type.h"
  #include "hphp/runtime/base/type-structure-helpers.h"
  #include "hphp/runtime/base/type-structure-helpers-defs.h"
  #include "hphp/runtime/base/vanilla-dict-defs.h"
  #include "hphp/runtime/base/vanilla-dict.h"
  #include "hphp/runtime/base/vanilla-vec-defs.h"
  #include "hphp/runtime/base/vanilla-vec.h"
  #include "hphp/runtime/vm/hhbc.h"
  #include "hphp/runtime/vm/jit/ir-opcode.h"
  #include "hphp/runtime/vm/runtime.h"
  
  #include "hphp/runtime/vm/jit/analysis.h"
  #include "hphp/runtime/vm/jit/containers.h"
  #include "hphp/runtime/vm/jit/ir-builder.h"
  #include "hphp/runtime/vm/jit/irgen-internal.h"
  #include "hphp/runtime/vm/jit/mutation.h"
  #include "hphp/runtime/vm/jit/simple-propagation.h"
  #include "hphp/runtime/vm/jit/timer.h"
  #include "hphp/runtime/vm/jit/translator-runtime.h"
  #include "hphp/runtime/vm/jit/type-array-elem.h"
  #include "hphp/runtime/vm/jit/type.h"
  
  #include "hphp/runtime/ext/hh/ext_hh.h"
  #include "hphp/runtime/ext/asio/ext_static-wait-handle.h"
  #include "hphp/runtime/ext/std/ext_std_closure.h"
  
  #include "hphp/util/overflow.h"
  #include "hphp/util/trace.h"
  
  #include <limits>
  #include <sstream>
  #include <type_traits>
  
  namespace HPHP { namespace jit {
  
  TRACE_SET_MOD(simplify);
  
  //////////////////////////////////////////////////////////////////////
  
  namespace {
  
  //////////////////////////////////////////////////////////////////////
  
  const StaticString s_isEmpty("isEmpty");
  const StaticString s_count("count");
  const StaticString s_1("1");
  const StaticString s_invoke("__invoke");
  const StaticString s_isFinished("isFinished");
  const StaticString s_isSucceeded("isSucceeded");
  const StaticString s_isFailed("isFailed");
  const StaticString s_Awaitable("HH\\Awaitable");
  
  //////////////////////////////////////////////////////////////////////
  
  struct State {
    explicit State(IRUnit& unit) : unit(unit) {}
    IRUnit& unit;
  
    // The current instruction being simplified is always at insts.top(). This
    // has to be a stack instead of just a pointer because simplify is reentrant.
    jit::stack<const IRInstruction*> insts;
    jit::vector<IRInstruction*> newInsts;
  };
  
  //////////////////////////////////////////////////////////////////////
  
  SSATmp* simplifyWork(State&, const IRInstruction*);
  
  template<class... Args>
  SSATmp* cns(State& env, Args&&... cns) {
    return env.unit.cns(std::forward<Args>(cns)...);
  }
  
  template<class... Args>
  SSATmp* gen(State& env, Opcode op, Args&&... args);
  
  template<class... Args>
  SSATmp* gen(State& env, Opcode op, BCContext bcctx, Args&&... args) {
    return makeInstruction(
      [&] (IRInstruction* inst) -> SSATmp* {
        auto const prevNewCount = env.newInsts.size();
        auto const newDest = simplifyWork(env, inst);
  
        // If any simplification happened to this instruction, drop it. We have to
        // check that nothing was added to newInsts because that's the only way
        // we can tell simplification happened to a no-dest instruction.
        if (newDest || env.newInsts.size() != prevNewCount) {
          return newDest;
        } else {
          assertx(inst->isTransient());
          if (!env.newInsts.empty() && env.newInsts.back()->is(Unreachable)) {
            return cns(env, TBottom);
          }
  
          assertx(checkOperandTypes(inst));
          inst = env.unit.clone(inst);
          env.newInsts.push_back(inst);
  
          // If the new instruction's result is unreachable (and it is not block
          // ending), indicate this in the IR stream.
          if (inst->isNextEdgeUnreachable() && !inst->isBlockEnd()) {
            gen(env, Unreachable, ASSERT_REASON);
          }
  
          return inst->dst(0);
        }
      },
      op,
      bcctx,
      std::forward<Args>(args)...
    );
  }
  
  template<class... Args>
  SSATmp* gen(State& env, Opcode op, Args&&... args) {
    assertx(!env.insts.empty());
    return gen(env, op, env.insts.top()->bcctx(), std::forward<Args>(args)...);
  }
  
  //////////////////////////////////////////////////////////////////////
  
  DEBUG_ONLY bool validate(const State& env,
                           SSATmp* newDst,
                           const IRInstruction* origInst) {
    // simplify() rules are not allowed to add new uses to SSATmps that aren't
    // known to be available.  All the sources to the original instruction must
    // be available, and non-reference counted values reachable through the
    // source chain are also always available.  Anything else requires more
    // complicated analysis than belongs in the simplifier right now.
    auto known_available = [&] (SSATmp* src) -> bool {
      if (!src->type().maybe(TCounted)) return true;
      for (auto& oldSrc : origInst->srcs()) {
        if (oldSrc == src) return true;
  
        // Some instructions consume a counted SSATmp and produce a new SSATmp
        // which supports the consumed location. If the result of one such
        // instruction is available then the value whose count it supports must
        // also be available. For now CreateSSWH is the only instruction of this
        // form that we care about.
        if (oldSrc->inst()->is(CreateSSWH) && oldSrc->inst()->src(0) == src) {
          return true;
        }
      }
      return false;
    };
  
    // Return early for the no-simplification case.
    if (env.newInsts.empty() && !newDst) {
      return true;
    }
  
    const IRInstruction* last = nullptr;
  
    if (!env.newInsts.empty()) {
      for (size_t i = 0, n = env.newInsts.size(); i < n; ++i) {
        auto const newInst = env.newInsts[i];
  
        for (auto& src : newInst->srcs()) {
          always_assert_flog(
            known_available(src),
            "A simplification rule produced an instruction that used a value "
            "that wasn't known to be available:\n"
            "  original inst: {}\n"
            "  new inst:      {}\n"
            "  src:           {}\n",
            origInst->toString(),
            newInst->toString(),
            src->toString()
          );
        }
  
        if (i == n - 1) {
          last = newInst;
          continue;
        }
  
        always_assert_flog(
          !newInst->isBlockEnd(),
          "Block-ending instruction produced in the middle of a simplified "
          "instruction stream:\n"
          "  original inst: {}\n"
          "  new inst:      {}\n",
          origInst->toString(),
          newInst->toString()
        );
      }
    }
  
    if (newDst) {
      const bool available = known_available(newDst) ||
        std::any_of(env.newInsts.begin(), env.newInsts.end(),
                    [&] (IRInstruction* inst) { return newDst == inst->dst(); });
  
      always_assert_flog(
        available,
        "simplify() produced a new destination that wasn't known to be "
        "available:\n"
        "  original inst: {}\n"
        "  new dst:       {}\n",
        origInst->toString(),
        newDst->toString()
      );
    }
  
    if (!last) return true;
  
    auto assert_last = [&] (bool cond, const char* msg) {
      always_assert_flog(
        cond,
        "{}:\n"
        "  original inst: {}\n"
        "  last new inst: {}\n",
        msg,
        origInst->toString(),
        last->toString()
      );
    };
  
    assert_last(
      !origInst->naryDst(),
      "Nontrivial simplification returned for instruction with NaryDest"
    );
  
    assert_last(
      origInst->hasDst() == (newDst != nullptr),
      "HasDest mismatch between input and output"
    );
  
    if (last->hasEdges()) {
      assert_last(
        origInst->hasEdges(),
        "Instruction with edges produced for simplification of edge-free "
        "instruction"
      );
  
      assert_last(
        IMPLIES(last->next(), last->next() == origInst->next() ||
                              last->next() == origInst->taken()),
        "Last instruction of simplified stream has next edge not reachable from "
        "the input instruction"
      );
  
      assert_last(
        IMPLIES(last->taken(), last->taken() == origInst->next() ||
                               last->taken() == origInst->taken()),
        "Last instruction of simplified stream has taken edge not reachable "
        "from the input instruction"
      );
    }
  
    return true;
  }
  
  //////////////////////////////////////////////////////////////////////
  
  /*
   * Individual simplification routines return nullptr if they don't want to
   * change anything, or they can call gen any number of times to produce a
   * different IR sequence, returning the thing gen'd that should be used as the
   * value of the simplified instruction sequence.
   */
  
  SSATmp* mergeBranchDests(State& env, const IRInstruction* inst) {
    // Replace a conditional branch with a Jmp if both branches go to the same
    // block. Only work if the instruction does not have side effect.
    // JmpZero/JmpNZero is handled separately.
    assertx(inst->is(CheckTypeMem,
                     CheckLoc,
                     CheckStk,
                     CheckMBase,
                     CheckInit,
                     CheckInitMem,
                     CheckRDSInitialized,
                     CheckVecBounds,
                     CheckDictKeys,
                     CheckMissingKeyInArrLike,
                     CheckDictOffset,
                     CheckKeysetOffset));
    if (inst->next() != nullptr && inst->next() == inst->taken()) {
      return gen(env, Jmp, inst->next());
    }
    if (inst->taken() && inst->taken()->isUnreachable()) {
      return gen(env, Nop);
    }
    if (inst->next() && inst->next()->isUnreachable()) {
      assertx(inst->taken());
      return gen(env, Jmp, inst->taken());
    }
    return nullptr;
  }
  
  SSATmp* simplifyEqFunc(State& env, const IRInstruction* inst) {
    auto const src0 = inst->src(0);
    auto const src1 = inst->src(1);
    if (src0->hasConstVal() && src1->hasConstVal()) {
      return cns(env, src0->funcVal() == src1->funcVal());
    }
    return nullptr;
  }
  
  
  SSATmp* simplifyLdFuncInOutBits(State& env, const IRInstruction* inst) {
    auto const funcTmp = inst->src(0);
    return funcTmp->hasConstVal(TFunc)
      ? cns(env, funcTmp->funcVal()->inOutBits())
      : nullptr;
  }
  
  SSATmp* simplifyLdFuncNumParams(State& env, const IRInstruction* inst) {
    auto const funcTmp = inst->src(0);
    return funcTmp->hasConstVal(TFunc)
      ? cns(env, (funcTmp->funcVal()->numParams()))
      : nullptr;
  }
  
  SSATmp* simplifyFuncHasAttr(State& env, const IRInstruction* inst) {
    auto const funcTmp = inst->src(0);
    return funcTmp->hasConstVal(TFunc)
      ? cns(env, !!(funcTmp->funcVal()->attrs() & inst->extra<AttrData>()->attr))
      : nullptr;
  }
  
  SSATmp* simplifyClassHasAttr(State& env, const IRInstruction* inst) {
    auto const clsTmp = inst->src(0);
    return clsTmp->hasConstVal(TCls)
      ? cns(env, (clsTmp->clsVal()->attrs() & inst->extra<AttrData>()->attr))
      : nullptr;
  }
  
  SSATmp* simplifyLdFuncRequiredCoeffects(State& env, const IRInstruction* inst) {
    auto const funcTmp = inst->src(0);
    return funcTmp->hasConstVal(TFunc)
      ? cns(env, (funcTmp->funcVal()->requiredCoeffects().value()))
      : nullptr;
  }
  
  SSATmp* simplifyLookupClsCtxCns(State& env, const IRInstruction* inst) {
    auto const clsTmp = inst->src(0);
    auto const nameTmp = inst->src(1);
    if (!clsTmp->hasConstVal(TCls) || !nameTmp->hasConstVal(TStr)) return nullptr;
    auto const result = clsTmp->clsVal()->clsCtxCnsGet(nameTmp->strVal(), false);
    if (!result) return nullptr; // we will raise warning/error
    return cns(env, result->value());
  }
  
  SSATmp* simplifyLdResolvedTypeCns(State& env, const IRInstruction* inst) {
    auto const clsTmp = inst->src(0);
    auto const clsSpec = clsTmp->type().clsSpec();
    if (!clsSpec) return nullptr;
    auto const cls = clsSpec.cls();
    auto const extra = inst->extra<LdResolvedTypeCns>();
  
    assertx(cls->hasTypeConstant(extra->cnsName, true));
    assertx(extra->slot < cls->numConstants());
    auto const& typeCns = cls->constants()[extra->slot];
    auto const& resolved = typeCns.preConst->resolvedTypeStructure();
  
    if (clsSpec.exact()) {
      if (typeCns.isAbstractAndUninit()) {
        gen(env, Jmp, inst->taken());
        return cns(env, TBottom);
      }
      if (resolved.isNull()) return nullptr;
      return cns(env, resolved.get());
    }
    if (resolved.isNull()) return nullptr;
  
    switch (typeCns.preConst->invariance()) {
      case PreClass::Const::Invariance::None:
        return nullptr;
      case PreClass::Const::Invariance::Present:
      case PreClass::Const::Invariance::ClassnamePresent:
        return gen(env, LdResolvedTypeCnsNoCheck, *extra, clsTmp);
      case PreClass::Const::Invariance::Same:
        return cns(env, resolved.get());
    }
    always_assert(false);
  }
  
  SSATmp* simplifyLdResolvedTypeCnsNoCheck(State& env,
                                           const IRInstruction* inst) {
    auto const clsTmp = inst->src(0);
    auto const clsSpec = clsTmp->type().clsSpec();
    if (!clsSpec) return nullptr;
    auto const cls = clsSpec.cls();
    auto const extra = inst->extra<LdResolvedTypeCnsNoCheck>();
  
    assertx(cls->hasTypeConstant(extra->cnsName, true));
    assertx(extra->slot < cls->numConstants());
    auto const& typeCns = cls->constants()[extra->slot];
  
    auto const& resolved = typeCns.preConst->resolvedTypeStructure();
    if (resolved.isNull()) return nullptr;
  
    if (clsSpec.exact()) return cns(env, resolved.get());
    if (typeCns.preConst->invariance() == PreClass::Const::Invariance::Same) {
      return cns(env, resolved.get());
    }
    return nullptr;
  }
  
  SSATmp* simplifyLdResolvedTypeCnsClsName(State& env,
                                           const IRInstruction* inst) {
    auto const clsTmp = inst->src(0);
    auto const clsSpec = clsTmp->type().clsSpec();
    if (!clsSpec) return nullptr;
    auto const cls = clsSpec.cls();
    auto const extra = inst->extra<LdResolvedTypeCnsClsName>();
  
    assertx(cls->hasTypeConstant(extra->cnsName, true));
    assertx(extra->slot < cls->numConstants());
    auto const& typeCns = cls->constants()[extra->slot];
    auto const& resolved = typeCns.preConst->resolvedTypeStructure();
  
    auto const classname = [&] {
      auto const name = resolved->get(s_classname);
      if (tvIsString(name)) return cns(env, name);
      return cns(env, nullptr);
    };
  
    if (clsSpec.exact()) {
      if (typeCns.isAbstractAndUninit()) return cns(env, nullptr);
      if (resolved.isNull()) return nullptr;
      return classname();
    }
    if (resolved.isNull()) return nullptr;
  
    if (typeCns.preConst->invariance() == PreClass::Const::Invariance::Same) {
      return classname();
    }
    return nullptr;
  }
  
  SSATmp* simplifyLdCls(State& env, const IRInstruction* inst) {
    auto const str = inst->src(0);
    auto const cls = inst->src(1);
    if (str->inst()->is(LdClsName)) {
      return str->inst()->src(0);
    }
    if (str->inst()->is(LdLazyClsName)) {
      auto const lcls = str->inst()->src(0);
      if (lcls->inst()->is(LdLazyCls)) {
        return lcls->inst()->src(0);
      }
    }
    if (str->hasConstVal() && (cls->hasConstVal(TCls) || cls->isA(TNullptr))) {
      auto const sval = str->strVal();
      auto const cval = cls->hasConstVal(TCls) ? cls->clsVal() : nullptr;
      auto const result = Class::lookupUniqueInContext(sval, cval, nullptr);
      if (result) return cns(env, result);
    }
    return nullptr;
  }
  
  SSATmp* simplifyLdClsMethod(State& env, const IRInstruction* inst) {
    auto const clsTmp = inst->src(0);
    auto const idxTmp = inst->src(1);
  
    if (clsTmp->hasConstVal() && idxTmp->hasConstVal()) {
      auto const cls = clsTmp->clsVal();
      auto const idx = idxTmp->intVal();
      if (idx < cls->numMethods()) {
        return cns(env, cls->getMethod(idx));
      }
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyLdObjClass(State& env, const IRInstruction* inst) {
    auto const ty = inst->src(0)->type();
  
    if (!(ty < TObj)) return nullptr;
  
    if (auto const exact = ty.clsSpec().exactCls()) return cns(env, exact);
    return nullptr;
  }
  
  SSATmp* simplifyLdFrameCls(State& env, const IRInstruction* inst) {
    auto const ty = inst->typeParam();
  
    if (!(ty < TCls)) return nullptr;
  
    if (auto const cls = ty.clsSpec().exactCls()) {
      return cns(env, cls);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyLdObjInvoke(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (!src->hasConstVal(TCls)) return nullptr;
  
    auto const meth = src->clsVal()->getCachedInvoke();
    return meth == nullptr ? nullptr : cns(env, meth);
  }
  
  SSATmp* simplifyMov(State& /*env*/, const IRInstruction* inst) {
    return inst->src(0);
  }
  
  SSATmp* simplifyAbsDbl(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) return cns(env, fabs(src->dblVal()));
  
    return nullptr;
  }
  
  template<class Oper>
  SSATmp* constImpl(State& env, SSATmp* src1, SSATmp* src2, Oper op) {
    // don't canonicalize to the right, OP might not be commutative
    if (!src1->hasConstVal() || !src2->hasConstVal()) return nullptr;
  
    auto both = [&](Type ty) { return src1->type() <= ty && src2->type() <= ty; };
  
    if (both(TBool)) return cns(env, op(src1->boolVal(), src2->boolVal()));
    if (both(TInt))  return cns(env, op(src1->intVal(), src2->intVal()));
    if (both(TDbl))  return cns(env, op(src1->dblVal(), src2->dblVal()));
    return nullptr;
  }
  
  template<class Oper>
  SSATmp* commutativeImpl(State& env,
                          SSATmp* src1,
                          SSATmp* src2,
                          Opcode opcode,
                          Oper op) {
    if (auto simp = constImpl(env, src1, src2, op)) return simp;
  
    // Canonicalize constants to the right.
    if (src1->hasConstVal() && !src2->hasConstVal()) {
      return gen(env, opcode, src2, src1);
    }
  
    // Only handle integer operations for now.
    if (!src1->isA(TInt) || !src2->isA(TInt)) return nullptr;
  
    auto const inst1 = src1->inst();
    auto const inst2 = src2->inst();
    if (inst1->op() == opcode && inst1->src(1)->hasConstVal()) {
      // (X + C1) + C2 --> X + C3
      if (src2->hasConstVal()) {
        auto const right = op(inst1->src(1)->intVal(), src2->intVal());
        return gen(env, opcode, inst1->src(0), cns(env, right));
      }
      // (X + C1) + (Y + C2) --> X + Y + C3
      if (inst2->op() == opcode && inst2->src(1)->hasConstVal()) {
        auto const right = op(inst1->src(1)->intVal(), inst2->src(1)->intVal());
        auto const left = gen(env, opcode, inst1->src(0), inst2->src(0));
        return gen(env, opcode, left, cns(env, right));
      }
    }
    return nullptr;
  }
  
  /*
   * Assumes that outop is commutative, don't use with subtract!
   *
   * Assumes that the values we're going to add new uses to are not reference
   * counted.  (I.e. this is a distributive FooInt opcode.)
   */
  template <class OutOper, class InOper>
  SSATmp* distributiveImpl(State& env, SSATmp* src1, SSATmp* src2, Opcode outcode,
                           Opcode incode, OutOper outop, InOper /*inop*/) {
    if (auto simp = commutativeImpl(env, src1, src2, outcode, outop)) {
      return simp;
    }
  
    auto const inst1 = src1->inst();
    auto const inst2 = src2->inst();
    auto const op1 = inst1->op();
    auto const op2 = inst2->op();
    // all combinations of X * Y + X * Z --> X * (Y + Z)
    if (op1 == incode && op2 == incode) {
      if (inst1->src(0) == inst2->src(0)) {
        auto const fold = gen(env, outcode, inst1->src(1), inst2->src(1));
        return gen(env, incode, inst1->src(0), fold);
      }
      if (inst1->src(0) == inst2->src(1)) {
        auto const fold = gen(env, outcode, inst1->src(1), inst2->src(0));
        return gen(env, incode, inst1->src(0), fold);
      }
      if (inst1->src(1) == inst2->src(0)) {
        auto const fold = gen(env, outcode, inst1->src(0), inst2->src(1));
        return gen(env, incode, inst1->src(1), fold);
      }
      if (inst1->src(1) == inst2->src(1)) {
        auto const fold = gen(env, outcode, inst1->src(0), inst2->src(0));
        return gen(env, incode, inst1->src(1), fold);
      }
    }
    return nullptr;
  }
  
  SSATmp* simplifyAddInt(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    auto add = std::plus<uint64_t>();
    auto mul = std::multiplies<uint64_t>();
    if (auto simp = distributiveImpl(env, src1, src2, AddInt,
                                     MulInt, add, mul)) {
      return simp;
    }
    if (src2->hasConstVal()) {
      int64_t src2Val = src2->intVal();
      // X + 0 --> X
      if (src2Val == 0) return src1;
  
      // X + -C --> X - C
      // Weird, but can show up as a result of other simplifications.
      auto const min = std::numeric_limits<int64_t>::min();
      if (src2Val < 0 && src2Val > min) {
        return gen(env, SubInt, src1, cns(env, -src2Val));
      }
    }
    // X + (0 - Y) --> X - Y
    auto const inst2 = src2->inst();
    if (inst2->op() == SubInt) {
      auto const src = inst2->src(0);
      if (src->hasConstVal() && src->intVal() == 0) {
        return gen(env, SubInt, src1, inst2->src(1));
      }
    }
    auto const inst1 = src1->inst();
  
    // (X - C1) + ...
    if (inst1->op() == SubInt && inst1->src(1)->hasConstVal()) {
      auto const x = inst1->src(0);
      auto const c1 = inst1->src(1);
  
      // (X - C1) + C2 --> X + (C2 - C1)
      if (src2->hasConstVal()) {
        auto const rhs = gen(env, SubInt, cns(env, src2->intVal()), c1);
        return gen(env, AddInt, x, rhs);
      }
  
      // (X - C1) + (Y +/- C2)
      if ((inst2->op() == AddInt || inst2->op() == SubInt) &&
          inst2->src(1)->hasConstVal()) {
        auto const y = inst2->src(0);
        auto const c2 = inst2->src(1);
        auto const rhs = inst2->op() == SubInt ?
          // (X - C1) + (Y - C2) --> X + Y + (-C1 - C2)
          gen(env, SubInt, gen(env, SubInt, cns(env, 0), c1), c2) :
          // (X - C1) + (Y + C2) --> X + Y + (C2 - C1)
          gen(env, SubInt, c2, c1);
  
        auto const lhs = gen(env, AddInt, x, y);
        return gen(env, AddInt, lhs, rhs);
      }
      // (X - C1) + (Y + C2) --> X + Y + (C2 - C1)
      if (inst2->op() == AddInt && inst2->src(1)->hasConstVal()) {
        auto const y = inst2->src(0);
        auto const c2 = inst2->src(1);
  
        auto const lhs = gen(env, AddInt, x, y);
        auto const rhs = gen(env, SubInt, c2, c1);
        return gen(env, AddInt, lhs, rhs);
      }
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyAddIntO(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
    if (src1->hasConstVal() && src2->hasConstVal()) {
      auto const a = src1->intVal();
      auto const b = src2->intVal();
      if (add_overflow(a, b)) {
        gen(env, Jmp, inst->taken());
        return cns(env, TBottom);
      }
      return cns(env, a + b);
    }
    return nullptr;
  }
  
  SSATmp* simplifySubInt(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    auto const sub = std::minus<uint64_t>();
    if (auto simp = constImpl(env, src1, src2, sub)) return simp;
  
    // X - X --> 0
    if (src1 == src2) return cns(env, 0);
  
    if (src2->hasConstVal()) {
      auto const src2Val = src2->intVal();
      // X - 0 --> X
      if (src2Val == 0) return src1;
  
      // X - -C --> X + C
      // Need to check for C == INT_MIN, otherwise we'd infinite loop as
      // X + -C would send us back here.
      auto const min = std::numeric_limits<int64_t>::min();
      if (src2Val > min && src2Val < 0) {
        return gen(env, AddInt, src1, cns(env, -src2Val));
      }
    }
    // X - (0 - Y) --> X + Y
    auto const inst2 = src2->inst();
    if (inst2->op() == SubInt) {
      auto const src = inst2->src(0);
      if (src->hasConstVal(0)) return gen(env, AddInt, src1, inst2->src(1));
    }
    return nullptr;
  }
  
  SSATmp* simplifySubIntO(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
    if (src1->hasConstVal() && src2->hasConstVal()) {
      auto const a = src1->intVal();
      auto const b = src2->intVal();
      if (sub_overflow(a, b)) {
        gen(env, Jmp, inst->taken());
        return cns(env, TBottom);
      }
      return cns(env, a - b);
    }
    return nullptr;
  }
  
  SSATmp* simplifyMulInt(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    auto const mul = std::multiplies<uint64_t>();
    if (auto simp = commutativeImpl(env, src1, src2, MulInt, mul)) return simp;
  
    if (!src2->hasConstVal()) return nullptr;
  
    auto const rhs = src2->intVal();
  
    // X * (-1) --> -X
    if (rhs == -1) return gen(env, SubInt, cns(env, 0), src1);
    // X * 0 --> 0
    if (rhs == 0) return cns(env, 0);
    // X * 1 --> X
    if (rhs == 1) return src1;
    // X * 2 --> X + X
    if (rhs == 2) return gen(env, AddInt, src1, src1);
  
    auto isPowTwo = [](int64_t a) {
      return a > 0 && folly::isPowTwo<uint64_t>(a);
    };
    auto log2 = [](int64_t a) {
      assertx(a > 0);
      return folly::findLastSet<uint64_t>(a) - 1;
    };
  
    // X * 2^C --> X << C
    if (isPowTwo(rhs)) return gen(env, Shl, src1, cns(env, log2(rhs)));
  
    // X * (2^C + 1) --> ((X << C) + X)
    if (isPowTwo(rhs - 1)) {
      auto const lhs = gen(env, Shl, src1, cns(env, log2(rhs - 1)));
      return gen(env, AddInt, lhs, src1);
    }
    // X * (2^C - 1) --> ((X << C) - X)
    if (isPowTwo(rhs + 1)) {
      auto const lhs = gen(env, Shl, src1, cns(env, log2(rhs + 1)));
      return gen(env, SubInt, lhs, src1);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyAddDbl(State& env, const IRInstruction* inst) {
    return constImpl(env, inst->src(0), inst->src(1), std::plus<double>());
  }
  
  SSATmp* simplifySubDbl(State& env, const IRInstruction* inst) {
    return constImpl(env, inst->src(0), inst->src(1), std::minus<double>());
  }
  
  SSATmp* simplifyMulDbl(State& env, const IRInstruction* inst) {
    return constImpl(env, inst->src(0), inst->src(1), std::multiplies<double>());
  }
  
  SSATmp* simplifyMulIntO(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
    if (src1->hasConstVal() && src2->hasConstVal()) {
      auto const a = src1->intVal();
      auto const b = src2->intVal();
      if (mul_overflow(a, b)) {
        gen(env, Jmp, inst->taken());
        return cns(env, TBottom);
      }
      return cns(env, a * b);
    }
    return nullptr;
  }
  
  /*
  Integer Modulo/Remainder Operator: a % b = a - a / b * b
  */
  SSATmp* simplifyMod(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    if (!src2->hasConstVal()) return nullptr;
  
    auto const src2Val = src2->intVal();
  
    if (src2Val == 0) {
      // Undefined behavior, so we might as well constant propagate whatever we
      // want. If we're being asked to simplify this, it better be dynamically
      // unreachable code.
      // TODO we can do `return gen(env, Unreachable, ASSERT_REASON);` here
      return cns(env, 0);
    }
  
    // X % 1 --> 0, X % -1 --> 0
    if (src2Val == -1 || src2Val == 1) return cns(env, 0);
  
    if (src1->hasConstVal()) return cns(env, src1->intVal() % src2Val);
  
    // Optimization: x % 2^n == x & (2^n - 1)
    if (folly::popcount(llabs(src2Val)) == 1) {
      // long shft =
      //  static_cast<unsigned long>(x >> 63) >> (64 - __builtin_ctzll(y));
      // ret ((x + shft) & (y - 1)) - shft;
      auto const divisor = llabs(src2Val);
      auto const trailingZeros = cns(env, 64 - __builtin_ctzll(divisor));
      auto const shft = gen(env, Lshr,
                            gen(env, Shr, src1, cns(env, 63)), trailingZeros);
      return gen(env, SubInt,
                 gen(env, AndInt,
                     gen(env, AddInt, src1, shft), cns(env, divisor - 1)), shft);
    }
    return nullptr;
  }
  
  SSATmp* simplifyDivDbl(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    if (!src2->hasConstVal()) return nullptr;
  
    auto const src2Val = src2->dblVal();
  
    if (src2Val == 0.0) {
      // The branch emitted during irgen will deal with this
      return nullptr;
    }
  
    // statically compute X / Y
    return src1->hasConstVal() ? cns(env, src1->dblVal() / src2Val) : nullptr;
  }
  
  SSATmp* simplifyDivInt(State& env, const IRInstruction* inst) {
    auto const dividend = inst->src(0);
    auto const divisor  = inst->src(1);
  
    if (!divisor->hasConstVal()) return nullptr;
  
    auto const divisorVal = divisor->intVal();
  
    if (divisorVal == 0) {
      // The branch emitted during irgen will deal with this
      return nullptr;
    }
  
    if (!dividend->hasConstVal()) return nullptr;
  
    auto const dividendVal = dividend->intVal();
  
    if (dividendVal == LLONG_MIN || dividendVal % divisorVal) {
      // This should be unreachable
      return nullptr;
    }
  
    return cns(env, dividendVal / divisorVal);
  }
  
  SSATmp* simplifyAndInt(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
    auto bit_and = [](int64_t a, int64_t b) { return a & b; };
    auto bit_or = [](int64_t a, int64_t b) { return a | b; };
    auto const simp = distributiveImpl(env, src1, src2, AndInt, OrInt,
                                       bit_and, bit_or);
    if (simp != nullptr) {
      return simp;
    }
    // X & X --> X
    if (src1 == src2) {
      return src1;
    }
    if (src2->hasConstVal()) {
      // X & 0 --> 0
      if (src2->intVal() == 0) {
        return cns(env, 0);
      }
      // X & (~0) --> X
      if (src2->intVal() == ~0L) {
        return src1;
      }
    }
    return nullptr;
  }
  
  SSATmp* simplifyOrInt(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    auto bit_and = [](int64_t a, int64_t b) { return a & b; };
    auto bit_or = [](int64_t a, int64_t b) { return a | b; };
    auto const simp = distributiveImpl(env, src1, src2, OrInt, AndInt,
                                       bit_or, bit_and);
    if (simp != nullptr) {
      return simp;
    }
    // X | X --> X
    if (src1 == src2) {
      return src1;
    }
    if (src2->hasConstVal()) {
      // X | 0 --> X
      if (src2->intVal() == 0) {
        return src1;
      }
      // X | (~0) --> ~0
      if (src2->intVal() == ~uint64_t(0)) {
        return cns(env, ~uint64_t(0));
      }
    }
    return nullptr;
  }
  
  SSATmp* simplifyXorInt(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
    auto bitxor = [](int64_t a, int64_t b) { return a ^ b; };
    if (auto simp = commutativeImpl(env, src1, src2, XorInt, bitxor)) {
      return simp;
    }
    // X ^ X --> 0
    if (src1 == src2) return cns(env, 0);
    // X ^ 0 --> X
    if (src2->hasConstVal(0)) return src1;
    return nullptr;
  }
  
  SSATmp* xorTrueImpl(State& env, SSATmp* src) {
    auto const inst = src->inst();
    auto const op = inst->op();
  
    // !(X cmp Y) --> X opposite_cmp Y
    if (auto const negated = negateCmpOp(op)) {
      if (opcodeMayRaise(op)) return nullptr;
      auto const s0 = inst->src(0);
      auto const s1 = inst->src(1);
      // We can't add new uses to reference counted types without a more
      // advanced availability analysis.
      if (!s0->type().maybe(TCounted) && !s1->type().maybe(TCounted)) {
        return gen(env, *negated, s0, s1);
      }
      return nullptr;
    }
  
    switch (op) {
      // !!X --> X
      case XorBool:
        if (inst->src(1)->hasConstVal(true)) {
          // This is safe to add a new use to because inst->src(0) is a bool.
          assertx(inst->src(0)->isA(TBool));
          return inst->src(0);
        }
        return nullptr;
      case InstanceOfBitmask:
      case NInstanceOfBitmask:
        // This is safe because instanceofs don't take reference counted
        // arguments.
        assertx(!inst->src(0)->type().maybe(TCounted) &&
                !inst->src(1)->type().maybe(TCounted));
        return gen(
          env,
          (op == InstanceOfBitmask) ?
          NInstanceOfBitmask :
          InstanceOfBitmask,
          inst->src(0),
          inst->src(1)
        );
      default:
        break;
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyXorBool(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    // Both constants.
    if (src1->hasConstVal() && src2->hasConstVal()) {
      return cns(env, bool(src1->boolVal() ^ src2->boolVal()));
    }
  
    // Canonicalize constants to the right.
    if (src1->hasConstVal() && !src2->hasConstVal()) {
      return gen(env, XorBool, src2, src1);
    }
  
    // X^0 => X
    if (src2->hasConstVal(false)) return src1;
  
    // X^1 => simplify "not" logic
    if (src2->hasConstVal(true)) return xorTrueImpl(env, src1);
  
    // X^X => false
    if (src1 == src2) return cns(env, false);
  
    return nullptr;
  }
  
  template<class Oper>
  SSATmp* shiftImpl(State& env, const IRInstruction* inst, Oper op) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    if (src1->hasConstVal()) {
      if (src1->intVal() == 0) {
        return cns(env, 0);
      }
  
      if (src2->hasConstVal()) {
        return cns(env, op(src1->intVal(), src2->intVal() & 63));
      }
    }
  
    if (src2->hasConstVal() && src2->intVal() == 0) {
      return src1;
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyShl(State& env, const IRInstruction* inst) {
    return shiftImpl(env, inst,
                     [] (uint64_t a, int64_t b) -> int64_t {
                       return a << b;
                     });
  }
  
  SSATmp* simplifyLshr(State& env, const IRInstruction* inst) {
    return shiftImpl(env, inst,
                     [] (uint64_t a, int64_t b) -> int64_t {
                       return a >> b;
                     });
  }
  
  SSATmp* simplifyShr(State& env, const IRInstruction* inst) {
    return shiftImpl(env, inst,
                     [] (int64_t a, int64_t b) {
                       // avoid implementation defined behavior
                       // gcc optimizes this to a signed right shift.
                       return a >= 0 ? a >> b : -(-(a+1) >> b) - 1;
                     });
  }
  
  // This function isn't meant to perform the actual comparison at
  // compile-time. Instead, it performs the matching comparison against a
  // primitive type (usually bool).
  template<class T, class U>
  static bool cmpOp(Opcode opc, T a, U b) {
    switch (opc) {
    case GtBool:
    case GtInt:
    case GtDbl:
    case GtStr:
    case GtObj:
    case GtArrLike:
    case GtRes: return a > b;
    case GteBool:
    case GteInt:
    case GteDbl:
    case GteStr:
    case GteObj:
    case GteArrLike:
    case GteRes: return a >= b;
    case LtBool:
    case LtInt:
    case LtDbl:
    case LtStr:
    case LtObj:
    case LtArrLike:
    case LtRes: return a < b;
    case LteBool:
    case LteInt:
    case LteDbl:
    case LteStr:
    case LteObj:
    case LteArrLike:
    case LteRes: return a <= b;
    case SameStr:
    case SameObj:
    case SameArrLike:
    case EqBool:
    case EqInt:
    case EqDbl:
    case EqStr:
    case EqObj:
    case EqArrLike:
    case EqRes: return a == b;
    case NSameStr:
    case NSameObj:
    case NSameArrLike:
    case NeqBool:
    case NeqInt:
    case NeqDbl:
    case NeqStr:
    case NeqObj:
    case NeqArrLike:
    case NeqRes: return a != b;
    default:
      always_assert(false);
    }
  }
  
  SSATmp* cmpBoolImpl(State& env,
                      Opcode opc,
                      const IRInstruction* const inst,
                      SSATmp* left,
                      SSATmp* right) {
    assertx(left->type() <= TBool);
    assertx(right->type() <= TBool);
  
    auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
      return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
    };
  
    // Identity optimization
    if (left == right) {
      return cns(env, cmpOp(opc, true, true));
    }
  
    if (left->hasConstVal()) {
      // If both operands are constants, constant-fold them. Otherwise, move the
      // constant over to the right.
      if (right->hasConstVal()) {
        return cns(env, cmpOp(opc, left->boolVal(), right->boolVal()));
      } else {
        auto const newOpc = [](Opcode opcode) {
          switch (opcode) {
            case GtBool:  return LtBool;
            case GteBool: return LteBool;
            case LtBool:  return GtBool;
            case LteBool: return GteBool;
            case EqBool:  return EqBool;
            case NeqBool: return NeqBool;
            default: always_assert(false);
          }
        }(opc);
        return newInst(newOpc, right, left);
      }
    }
  
    if (right->hasConstVal()) {
      bool b = right->boolVal();
  
      // The result of the comparison might be independent of the truth
      // value of the LHS. If so, then simplify.
      if (cmpOp(opc, false, b) == cmpOp(opc, true, b)) {
        return cns(env, cmpOp(opc, false, b));
      }
  
      // There are only two distinct booleans - false and true (0 and 1).
      // From above, we know that (0 OP b) != (1 OP b).
      // Hence exactly one of (0 OP b) and (1 OP b) is true.
      // Hence there is exactly one boolean value of "left" that results in the
      // overall expression being true.
      // Hence we may check for equality with that boolean.
      if (opc != EqBool) {
        return newInst(EqBool, left, cns(env, !cmpOp(opc, false, b)));
      }
  
      // If we reach here, this is an equality comparison against a
      // constant. Testing for equality with true simplifies to just the left
      // operand, while equality with false is the negation of the left operand
      // (equivalent to XORing with true).
      return b ? left : newInst(XorBool, left, cns(env, true));
    }
  
    return nullptr;
  }
  
  SSATmp* cmpIntImpl(State& env,
                     Opcode opc,
                     const IRInstruction* const inst,
                     SSATmp* left,
                     SSATmp* right) {
    assertx(left->type() <= TInt);
    assertx(right->type() <= TInt);
  
    auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
      return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
    };
  
    // Identity optimization
    if (left == right) {
      return cns(env, cmpOp(opc, true, true));
    }
  
    // Arithmetic optimization
    if (opc == EqInt || opc == NeqInt) {
      if (left->inst()->is(AddInt)) {
        auto const add = left->inst();
        if (add->src(0) == right) return gen(env, opc, cns(env, 0), add->src(1));
        if (add->src(1) == right) return gen(env, opc, cns(env, 0), add->src(0));
      }
      if (right->inst()->is(AddInt)) {
        auto const add = right->inst();
        if (add->src(0) == left) return gen(env, opc, cns(env, 0), add->src(1));
        if (add->src(1) == left) return gen(env, opc, cns(env, 0), add->src(0));
      }
    }
  
    if (left->hasConstVal()) {
      // If both operands are constants, constant-fold them. Otherwise, move the
      // constant over to the right.
      if (right->hasConstVal()) {
        return cns(env, cmpOp(opc, left->intVal(), right->intVal()));
      } else {
        auto const newOpc = [](Opcode opcode) {
          switch (opcode) {
            case GtInt:  return LtInt;
            case GteInt: return LteInt;
            case LtInt:  return GtInt;
            case LteInt: return GteInt;
            case EqInt:  return EqInt;
            case NeqInt: return NeqInt;
            default: always_assert(false);
          }
        }(opc);
        return newInst(newOpc, right, left);
      }
    }
  
    return nullptr;
  }
  
  SSATmp* cmpDblImpl(State& env,
                     Opcode opc,
                     const IRInstruction* const inst,
                     SSATmp* left,
                     SSATmp* right) {
    assertx(left->type() <= TDbl);
    assertx(right->type() <= TDbl);
  
    // Identity optimization is not safe because Nan's compare unequal.
    if (left->hasConstVal() && right->hasConstVal()) {
      return cns(env, cmpOp(opc, left->dblVal(), right->dblVal()));
    }
  
    return nullptr;
  }
  
  SSATmp* cmpStrImpl(State& env,
                     Opcode opc,
                     const IRInstruction* const inst,
                     SSATmp* left,
                     SSATmp* right) {
    assertx(left->type() <= TStr);
    assertx(right->type() <= TStr);
  
    auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
      return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
    };
  
    // Identity optimization
    if (left == right) {
      return cns(env, cmpOp(opc, true, true));
    }
  
    if (left->hasConstVal()) {
      // If both operands are constants, constant-fold them. Otherwise, move the
      // constant over to the right.
      if (right->hasConstVal()) {
        if (opc == SameStr || opc == NSameStr) {
          return cns(
            env,
            cmpOp(opc, left->strVal()->same(right->strVal()), true)
          );
        } else if (opc == EqStr || opc == NeqStr) {
          // if we're going to be converting these to num and then comparing an
          // int and a float, block this fold because it needs to trigger a notice
          int64_t lval; double dval;
          auto ret1 = left->strVal()->isNumericWithVal(lval, dval, 0);
          auto ret2 = right->strVal()->isNumericWithVal(lval, dval, 0);
          if (ret1 == ret2 || ret1 == KindOfNull || ret2 == KindOfNull) {
            return cns(
              env,
              cmpOp(opc, left->strVal()->equal(right->strVal()), true)
            );
          }
        } else{
          return cns(
            env,
            cmpOp(opc, left->strVal()->compare(right->strVal()), 0)
          );
        }
      } else {
        auto const newOpc = [](Opcode opcode) {
          switch (opcode) {
            case GtStr:    return LtStr;
            case GteStr:   return LteStr;
            case LtStr:    return GtStr;
            case LteStr:   return GteStr;
            case EqStr:    return EqStr;
            case NeqStr:   return NeqStr;
            case SameStr:  return SameStr;
            case NSameStr: return NSameStr;
            default: always_assert(false);
          }
        }(opc);
        return newInst(newOpc, right, left);
      }
    }
  
    // Comparisons against the empty string can be optimized to checks on the
    // string length.
    if (right->hasConstVal() && right->strVal()->empty()) {
      const auto op =
       opc == EqStr || opc == SameStr || opc == LteStr ? EqInt : NeqInt;
      switch (opc) {
        case EqStr:
        case NeqStr: return gen(env, op, gen(env, LdStrLen, left), cns(env, 0));
        case SameStr:
        case LteStr:
        case NSameStr:
        case GtStr: return newInst(op, gen(env, LdStrLen, left), cns(env, 0));
        case LtStr: return cns(env, false);
        case GteStr: return cns(env, true);
        default: always_assert(false);
      }
    }
  
    return nullptr;
  }
  
  SSATmp* cmpObjImpl(State& env, Opcode opc, const IRInstruction* const /*inst*/,
                     SSATmp* left, SSATmp* right) {
    assertx(left->type() <= TObj);
    assertx(right->type() <= TObj);
  
    // Identity optimization. Object comparisons can produce arbitrary
    // side-effects, so we can only eliminate the comparison if its checking for
    // sameness.
    if ((opc == SameObj || opc == NSameObj) && left == right) {
      return cns(env, cmpOp(opc, true, true));
    }
  
    return nullptr;
  }
  
  SSATmp*
  cmpKeysetImpl(State& env, Opcode opc, SSATmp* left, SSATmp* right) {
    assertx(left->type() <= TKeyset);
    assertx(right->type() <= TKeyset);
  
    // Unlike other array types, keyset comparisons can never throw or re-enter
    // (because they can only store integers and strings). Therefore we can fully
    // simplify equality comparisons if both arrays are constants.
    if (left->hasConstVal() && right->hasConstVal()) {
      auto const leftVal = left->keysetVal();
      auto const rightVal = right->keysetVal();
      switch (opc) {
        case EqArrLike:
          return cns(env, VanillaKeyset::Equal(leftVal, rightVal));
        case SameArrLike:
          return cns(env, VanillaKeyset::Same(leftVal, rightVal));
        case NeqArrLike:
          return cns(env, VanillaKeyset::NotEqual(leftVal, rightVal));
        case NSameArrLike:
          return cns(env, VanillaKeyset::NotSame(leftVal, rightVal));
        default:
          break;
      }
    }
  
    // Even if not a constant, we can apply an identity simplification as long as
    // we're doing an equality comparison.
    if ((opc == SameArrLike || opc == NSameArrLike ||
         opc == EqArrLike || opc == NeqArrLike)
        && left == right) {
      return cns(env, cmpOp(opc, true, true));
    }
  
    return nullptr;
  }
  
  SSATmp* cmpArrLikeImpl(State& env, Opcode opc,
                         const IRInstruction* const /*inst*/,
                         SSATmp* left, SSATmp* right) {
    assertx(left->type() <= TArrLike);
    assertx(right->type() <= TArrLike);
  
    if (left->type() <= TKeyset && right->type() <= TKeyset) {
      return cmpKeysetImpl(env, opc, left, right);
    }
  
    // Identity optimization. Array comparisons can produce arbitrary
    // side-effects, so we can only eliminate the comparison if its checking for
    // sameness.
    if ((opc == SameArrLike || opc == NSameArrLike) && left == right) {
      return cns(env, cmpOp(opc, true, true));
    }
  
    return nullptr;
  }
  
  SSATmp* cmpResImpl(State& env, Opcode opc, const IRInstruction* const /*inst*/,
                     SSATmp* left, SSATmp* right) {
    assertx(left->type() <= TRes);
    assertx(right->type() <= TRes);
  
    // Identity optimization.
    if (left == right) {
      return cns(env, cmpOp(opc, true, true));
    }
  
    return nullptr;
  }
  
  #define X(name, type)                                                   \
    SSATmp* simplify##name(State& env, const IRInstruction* i) {          \
      return cmp##type##Impl(env, i->op(), i, i->src(0), i->src(1));      \
    }
  
  X(GtBool, Bool)
  X(GteBool, Bool)
  X(LtBool, Bool)
  X(LteBool, Bool)
  X(EqBool, Bool)
  X(NeqBool, Bool)
  
  X(GtInt, Int)
  X(GteInt, Int)
  X(LtInt, Int)
  X(LteInt, Int)
  X(EqInt, Int)
  X(NeqInt, Int)
  
  X(GtDbl, Dbl)
  X(GteDbl, Dbl)
  X(LtDbl, Dbl)
  X(LteDbl, Dbl)
  X(EqDbl, Dbl)
  X(NeqDbl, Dbl)
  
  X(GtStr, Str)
  X(GteStr, Str)
  X(LtStr, Str)
  X(LteStr, Str)
  X(EqStr, Str)
  X(NeqStr, Str)
  X(SameStr, Str)
  X(NSameStr, Str)
  
  X(GtObj, Obj)
  X(GteObj, Obj)
  X(LtObj, Obj)
  X(LteObj, Obj)
  X(EqObj, Obj)
  X(NeqObj, Obj)
  X(SameObj, Obj)
  X(NSameObj, Obj)
  
  X(GtArrLike, ArrLike)
  X(GteArrLike, ArrLike)
  X(LtArrLike, ArrLike)
  X(LteArrLike, ArrLike)
  X(EqArrLike, ArrLike)
  X(NeqArrLike, ArrLike)
  X(SameArrLike, ArrLike)
  X(NSameArrLike, ArrLike)
  
  X(GtRes, Res)
  X(GteRes, Res)
  X(LtRes, Res)
  X(LteRes, Res)
  X(EqRes, Res)
  X(NeqRes, Res)
  
  #undef X
  
  SSATmp* simplifyEqCls(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
    if (left->hasConstVal() && right->hasConstVal()) {
      return cns(env, left->clsVal() == right->clsVal());
    }
    return nullptr;
  }
  
  SSATmp* simplifyEqLazyCls(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
    if (left->hasConstVal() && right->hasConstVal()) {
      return cns(env, left->lclsVal().name() == right->lclsVal().name());
    }
    return nullptr;
  }
  
  SSATmp* simplifyEqStrPtr(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
    if (left == right) return cns(env, true);
    if (left->hasConstVal() && right->hasConstVal()) {
      return cns(env, left->strVal() == right->strVal());
    }
    return nullptr;
  }
  
  SSATmp* simplifyEqArrayDataPtr(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
    if (left == right) return cns(env, true);
    if (!left->type().maybe(right->type())) return cns(env, false);
    if (left->hasConstVal() && right->hasConstVal()) {
      return cns(env, left->arrLikeVal() == right->arrLikeVal());
    }
    return nullptr;
  }
  
  SSATmp* simplifyCmpBool(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
    assertx(left->type() <= TBool);
    assertx(right->type() <= TBool);
    if (left->hasConstVal() && right->hasConstVal()) {
      return cns(env, HPHP::compare(left->boolVal(), right->boolVal()));
    }
    return nullptr;
  }
  
  SSATmp* simplifyCmpInt(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
    assertx(left->type() <= TInt);
    assertx(right->type() <= TInt);
    if (left->hasConstVal() && right->hasConstVal()) {
      return cns(env, HPHP::compare(left->intVal(), right->intVal()));
    }
    return nullptr;
  }
  
  SSATmp* simplifyCmpDbl(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
    assertx(left->type() <= TDbl);
    assertx(right->type() <= TDbl);
    if (left->hasConstVal() && right->hasConstVal()) {
      return cns(env, HPHP::compare(left->dblVal(), right->dblVal()));
    }
    return nullptr;
  }
  
  SSATmp* simplifyCmpStr(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
  
    assertx(left->type() <= TStr);
    assertx(right->type() <= TStr);
  
    auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
      return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
    };
  
    if (left->hasConstVal()) {
      if (right->hasConstVal()) {
        return cns(env, HPHP::compare(left->strVal(), right->strVal()));
      } else if (left->strVal()->empty()) {
        // Comparisons against the empty string can be optimized to a comparison
        // on the string length.
        return newInst(CmpInt, cns(env, 0), gen(env, LdStrLen, right));
      }
    } else if (right->hasConstVal() && right->strVal()->empty()) {
      return newInst(CmpInt, gen(env, LdStrLen, left), cns(env, 0));
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyCmpRes(State& env, const IRInstruction* inst) {
    auto const left = inst->src(0);
    auto const right = inst->src(1);
    assertx(left->type() <= TRes);
    assertx(right->type() <= TRes);
    return (left == right) ? cns(env, 0) : nullptr;
  }
  
  SSATmp* simplifyCGetPropQ(State& env, const IRInstruction* inst) {
    if (inst->src(0)->isA(TNull)) return cns(env, TInitNull);
    return nullptr;
  }
  
  SSATmp* instanceOfImpl(State& env, SSATmp* ssatmp1, ClassSpec spec2) {
    assertx(ssatmp1->type() <= TCls);
    if (!spec2) return nullptr;
    auto const cls2 = spec2.cls();
  
    ClassSpec spec1 = ssatmp1->type().clsSpec();
    if (spec2.exact() && spec1 && spec1.cls()->classof(cls2)) {
      return cns(env, true);
    }
  
    // If spec2 is exact and we have an instance bit for it, use
    // InstanceOfBitmask.
    const bool useInstanceBits = InstanceBits::initted() ||
                                 env.unit.context().kind == TransKind::Optimize;
    if (spec2.exact() && useInstanceBits) {
      InstanceBits::init();
      if (InstanceBits::lookup(cls2->name()) != 0) {
        return gen(env, InstanceOfBitmask, ssatmp1, cns(env, cls2->name()));
      }
    }
  
    // If spec2 is an interface and we've assigned it a vtable slot, use that.
    if (spec2.exact() && isInterface(cls2) && RO::RepoAuthoritative) {
      auto const slot = cls2->preClass()->ifaceVtableSlot();
      if (slot != kInvalidSlot) {
        auto const data = InstanceOfIfaceVtableData{spec2.cls(), true};
        return gen(env, InstanceOfIfaceVtable, data, ssatmp1);
      }
    }
  
    if (!spec1) return nullptr;
    auto const cls1 = spec1.cls();
  
    if (cls1->classof(cls2)) {
      assertx(!spec2.exact()); // the exact case is handled above
      return nullptr;
    }
  
    if (isInterface(cls1)) return nullptr;
  
    if (spec1.exact()) return cns(env, false);
  
    // At this point cls1 is not a cls2, and its not exact, so:
    //
    //  - If cls2 is an interface, a descendent of cls1 could implement
    //    that interface
    //  - If cls2 is a descendent of cls1, then (clearly) a descendent
    //    of cls1 could be a cls2
    //  - Otherwise no descendent of cls1 can be a cls2 or any class
    //    that isa cls2
    if (!isInterface(cls2) && !cls2->classof(cls1)) {
      return cns(env, false);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyInstanceOf(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    if (src2->isA(TNullptr)) {
      return cns(env, false);
    }
  
    auto const spec2 = src2->type().clsSpec();
  
    if (auto const cls = spec2.exactCls()) {
      if (isNormalClass(cls) && (cls->attrs() & AttrUnique)) {
        return gen(env, ExtendsClass, ExtendsClassData{ cls }, src1);
      }
      if (isInterface(cls) && (cls->attrs() & AttrUnique)) {
        return gen(env, InstanceOfIface, src1, cns(env, cls->name()));
      }
    }
  
    return instanceOfImpl(env, src1, src2->type().clsSpec());
  }
  
  SSATmp* simplifyExtendsClass(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const cls2 = inst->extra<ExtendsClassData>()->cls;
    assertx(cls2 && isNormalClass(cls2));
    auto const spec2 = ClassSpec{cls2, ClassSpec::ExactTag{}};
    return instanceOfImpl(env, src1, spec2);
  }
  
  SSATmp* simplifyInstanceOfBitmask(State& env, const IRInstruction* inst) {
    auto const cls = inst->src(0);
    auto const name = inst->src(1);
  
    if (!name->hasConstVal(TStr)) return nullptr;
  
    auto const bit = InstanceBits::lookup(name->strVal());
    always_assert(bit && "cgInstanceOfBitmask had no bitmask");
  
    if (cls->type().clsSpec() &&
        cls->type().clsSpec().cls()->checkInstanceBit(bit)) {
      return cns(env, true);
    }
  
    if (!cls->hasConstVal(TCls)) return nullptr;
    return cns(env, false);
  }
  
  SSATmp* simplifyNInstanceOfBitmask(State& env, const IRInstruction* inst) {
    auto const cls = inst->src(0);
    auto const name = inst->src(1);
  
    if (!name->hasConstVal(TStr)) return nullptr;
  
    auto const bit = InstanceBits::lookup(name->strVal());
    always_assert(bit && "cgNInstanceOfBitmask had no bitmask");
  
    if (cls->type().clsSpec() &&
        cls->type().clsSpec().cls()->checkInstanceBit(bit)) {
      return cns(env, false);
    }
  
    if (!cls->hasConstVal(TCls)) return nullptr;
    return cns(env, true);
  }
  
  SSATmp* simplifyInstanceOfIface(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    auto const cls2 = Class::lookupUniqueInContext(
        src2->strVal(), inst->ctx(), nullptr);
    assertx(cls2 && isInterface(cls2));
    auto const spec2 = ClassSpec{cls2, ClassSpec::ExactTag{}};
  
    return instanceOfImpl(env, src1, spec2);
  }
  
  SSATmp* simplifyInstanceOfIfaceVtable(State& env, const IRInstruction* inst) {
    if (!inst->extra<InstanceOfIfaceVtable>()->canOptimize) return nullptr;
    auto const cls = inst->src(0);
    auto const iface = inst->extra<InstanceOfIfaceVtable>()->cls;
    if (cls->type().clsSpec() &&
        cls->type().clsSpec().cls()->classof(iface)) {
      return cns(env, true);
    }
  
    const bool useInstanceBits = InstanceBits::initted() ||
                                 env.unit.context().kind == TransKind::Optimize;
    if (useInstanceBits) {
      InstanceBits::init();
      auto const ifaceName = iface->name();
      if (InstanceBits::lookup(ifaceName) != 0) {
        return gen(env, InstanceOfBitmask, cls, cns(env, ifaceName));
      }
    }
    return nullptr;
  }
  
  SSATmp* isTypeImpl(State& env, const IRInstruction* inst, const Type& srcType) {
    assertx(inst->is(IsNType, IsType));
    auto const trueSense = inst->is(IsType);
    auto const type      = inst->typeParam();
  
    // Testing for StaticStr will make you miss out on CountedStr, and vice versa,
    // and similarly for arrays. PHP treats both types of string the same, so if
    // the distinction matters to you here, be careful.
    assertx(IMPLIES(type <= TStr, type == TStr));
    assertx(IMPLIES(type <= TVec, type == TVec));
    assertx(IMPLIES(type <= TDict, type == TDict));
    assertx(IMPLIES(type <= TKeyset, type == TKeyset));
  
    // The types are disjoint; the result must be false.
    if (!srcType.maybe(type)) {
      return cns(env, !trueSense);
    }
  
    // The src type is a subtype of the tested type; the result must be true.
    if (srcType <= type) {
      return cns(env, trueSense);
    }
  
    // At this point, either the tested type is a subtype of the src type, or they
    // are non-disjoint but neither is a subtype of the other. We can't simplify
    // this away.
    return nullptr;
  }
  
  SSATmp* simplifyIsType(State& env, const IRInstruction* i) {
    auto const src = i->src(0);
    return isTypeImpl(env, i, src->type());
  }
  
  SSATmp* simplifyIsNType(State& env, const IRInstruction* i) {
    auto const src = i->src(0);
    return isTypeImpl(env, i, src->type());
  }
  
  SSATmp* simplifyMethodExists(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
  
    auto const clsSpec = src1->type().clsSpec();
  
    if (clsSpec.cls() != nullptr && src2->hasConstVal(TStr)) {
      // If we don't have an exact type, then we can't say for sure the class
      // doesn't have the method.
      auto const result = clsSpec.cls()->lookupMethod(src2->strVal()) != nullptr;
      return (clsSpec.exact() || result) ? cns(env, result) : nullptr;
    }
    return nullptr;
  }
  
  static auto concat_litstrs(State& env, SSATmp* s1, SSATmp* s2) {
    auto const str1 = const_cast<StringData*>(s1->strVal());
    auto const str2 = const_cast<StringData*>(s2->strVal());
    auto const sval = String::attach(concat_ss(str1, str2));
    return cns(env, makeStaticString(sval.get()));
  }
  
  SSATmp* simplifyConcatStrStr(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
    if (src1->hasConstVal(TStaticStr) &&
        src2->hasConstVal(TStaticStr)) {
      return concat_litstrs(env, src1, src2);
    }
  
    // ConcatStrStr consumes a reference to src1 and produces a reference, so
    // anything we replace it with must do the same thing.
    if (src1->hasConstVal(staticEmptyString())) {
      // Produce a reference on src2.
      gen(env, IncRef, src2);
      return src2;
    }
    if (src2->hasConstVal(staticEmptyString())) {
      // Forward the reference on src1 from input to output.
      return src1;
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyConcatStr3(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
    auto const src3 = inst->src(2);
  
    if (src2->hasConstVal(TStaticStr)) {
      if (src1->hasConstVal(TStaticStr)) {
        return gen(env, ConcatStrStr, inst->taken(),
                   concat_litstrs(env, src1, src2), src3);
      }
      if (src3->hasConstVal(TStaticStr)) {
        return gen(env, ConcatStrStr, inst->taken(),
                   src1, concat_litstrs(env, src2, src3));
      }
      if (src2->hasConstVal(staticEmptyString())) {
        return gen(env, ConcatStrStr, inst->taken(), src1, src3);
      }
    }
  
    // ConcatStr3 consumes a reference to src1 and produces a reference, so
    // anything we replace it with must do the same thing.
    if (src1->hasConstVal(staticEmptyString())) {
      // Compensate for ConcatStrStr consuming src2.
      gen(env, IncRef, src2);
      return gen(env, ConcatStrStr, inst->taken(), src2, src3);
    }
    if (src3->hasConstVal(staticEmptyString())) {
      // ConcatStrStr also consumes a reference to src1
      return gen(env, ConcatStrStr, inst->taken(), src1, src2);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyConcatStr4(State& env, const IRInstruction* inst) {
    auto const src1 = inst->src(0);
    auto const src2 = inst->src(1);
    auto const src3 = inst->src(2);
    auto const src4 = inst->src(3);
  
    if (src2->hasConstVal(TStaticStr)) {
      if (src1->hasConstVal(TStaticStr)) {
        return gen(env, ConcatStr3, inst->taken(),
                   concat_litstrs(env, src1, src2), src3, src4);
      }
      if (src3->hasConstVal(TStaticStr)) {
        return gen(env, ConcatStr3, inst->taken(),
                   src1, concat_litstrs(env, src2, src3), src4);
      }
      if (src2->hasConstVal(staticEmptyString())) {
        return gen(env, ConcatStr3, inst->taken(), src1, src3, src4);
      }
    }
  
    if (src3->hasConstVal(TStaticStr)) {
      if (src4->hasConstVal(TStaticStr)) {
        return gen(env, ConcatStr3, inst->taken(),
                   src1, src2, concat_litstrs(env, src3, src4));
      }
      if (src3->hasConstVal(staticEmptyString())) {
        return gen(env, ConcatStr3, inst->taken(), src1, src2, src4);
      }
    }
  
    // ConcatStr4 consumes a reference to src1 and produces a reference, so
    // anything we replace it with must do the same thing.
    if (src1->hasConstVal(staticEmptyString())) {
      // Compensate for ConcatStrStr consuming src2.
      gen(env, IncRef, src2);
      return gen(env, ConcatStr3, inst->taken(), src2, src3, src4);
    }
    if (src4->hasConstVal(staticEmptyString())) {
      // ConcatStr3 also consumes a reference to src1
      return gen(env, ConcatStr3, inst->taken(), src1, src2, src3);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyConcatIntStr(State& env, const IRInstruction* inst) {
    auto const lhs = inst->src(0);
    auto const rhs = inst->src(1);
  
    if (lhs->hasConstVal()) {
      auto const lhsStr =
        cns(env, makeStaticString(folly::to<std::string>(lhs->intVal())));
      return gen(env, ConcatStrStr, inst->taken(), lhsStr, rhs);
    }
    if (rhs->hasConstVal(staticEmptyString())) {
      return gen(env, ConvIntToStr, lhs);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyConcatStrInt(State& env, const IRInstruction* inst) {
    auto const lhs = inst->src(0);
    auto const rhs = inst->src(1);
  
    if (rhs->hasConstVal()) {
      auto const rhsStr =
        cns(env, makeStaticString(folly::to<std::string>(rhs->intVal())));
      return gen(env, ConcatStrStr, inst->taken(), lhs, rhsStr);
    }
    if (lhs->hasConstVal(staticEmptyString())) {
      return gen(env, ConvIntToStr, rhs);
    }
  
    return nullptr;
  }
  
  namespace {
  
  template <typename C>
  SSATmp* arrayLikeConvImpl(State& env, const IRInstruction* inst, C convert) {
    auto const src = inst->src(0);
    if (!src->hasConstVal()) return nullptr;
    auto const before = src->arrLikeVal();
    auto converted = convert(const_cast<ArrayData*>(before));
    if (!converted) return nullptr;
    ArrayData::GetScalarArray(&converted);
    return cns(env, converted);
  }
  
  }
  
  SSATmp* simplifyConvArrLikeToVec(State& env, const IRInstruction* inst) {
    return arrayLikeConvImpl(
      env, inst,
      [&](ArrayData* a) { return a->toVec(true); }
    );
  }
  
  SSATmp* simplifyConvArrLikeToDict(State& env, const IRInstruction* inst) {
    return arrayLikeConvImpl(
      env, inst,
      [&](ArrayData* a) { return a->toDict(true); }
    );
  }
  
  SSATmp* simplifyConvArrLikeToKeyset(State& env, const IRInstruction* inst) {
    return arrayLikeConvImpl(
      env, inst,
      [&](ArrayData* a) {
        // We need to check if the array contains values suitable for keyset
        // before attempting the conversion. Otherwise, toKeyset() might re-enter
        // which we can't do from the simplifier.
        bool keylike = true;
        IterateV(
          a,
          [&](TypedValue v) {
            if (!isIntType(v.m_type) && !isStringType(v.m_type)) {
              keylike = false;
              return true;
            }
            return false;
          }
        );
        return keylike ? a->toKeyset(true) : nullptr;
      }
    );
  }
  
  SSATmp* simplifyConvDblToBool(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      bool const bval = src->dblVal();
      return cns(env, bval);
    }
    return nullptr;
  }
  
  SSATmp* simplifyConvIntToBool(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      bool const bval = src->intVal();
      return cns(env, bval);
    }
    return nullptr;
  }
  
  SSATmp* simplifyConvStrToBool(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      // only the strings "", and "0" convert to false, all other strings
      // are converted to true
      auto const str = src->strVal();
      return cns(env, !str->empty() && !str->isZero());
    }
    return nullptr;
  }
  
  SSATmp* simplifyConvBoolToDbl(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      double const dval = src->boolVal();
      return cns(env, dval);
    }
    return nullptr;
  }
  
  SSATmp* simplifyConvIntToDbl(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      double const dval = src->intVal();
      return cns(env, dval);
    }
    if (src->inst()->is(ConvBoolToInt)) {
      // This is safe, because the bool src is not reference counted.
      return gen(env, ConvBoolToDbl, src->inst()->src(0));
    }
    return nullptr;
  }
  
  SSATmp* simplifyConvStrToDbl(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    return src->hasConstVal() ? cns(env, src->strVal()->toDouble()) : nullptr;
  }
  
  SSATmp* simplifyConvBoolToInt(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) return cns(env, static_cast<int>(src->boolVal()));
    return nullptr;
  }
  
  SSATmp* simplifyConvDblToInt(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) return cns(env, double_to_int64(src->dblVal()));
    return nullptr;
  }
  
  SSATmp* simplifyConvStrToInt(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    return src->hasConstVal() ? cns(env, src->strVal()->toInt64()) : nullptr;
  }
  
  SSATmp* simplifyConvDblToStr(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      auto const dblStr = String::attach(buildStringData(src->dblVal()));
      return cns(env, makeStaticString(dblStr));
    }
    return nullptr;
  }
  
  SSATmp* simplifyConvIntToStr(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      return cns(env,
        makeStaticString(folly::to<std::string>(src->intVal()))
      );
    }
    return nullptr;
  }
  
  namespace {
  const StaticString
      s_msgArrToStr("Array to string conversion"),
      s_msgVecToStr("Vec to string conversion"),
      s_msgDictToStr("Dict to string conversion"),
      s_msgKeysetToStr("Keyset to string conversion"),
      s_msgClsMethToStr("Cannot convert clsmeth to string"),
      s_msgClsMethToInt("Cannot convert clsmeth to int"),
      s_msgClsMethToIntImpl("Implicit clsmeth to int conversion"),
      s_msgClsMethToDbl("Cannot convert clsmeth to double"),
      s_msgClsMethToDblImpl("Implicit clsmeth to double conversion");
  }
  
  SSATmp* simplifyConvTVToBool(State& env, const IRInstruction* inst) {
    auto const src     = inst->src(0);
    auto const srcType = src->type();
  
    if (srcType <= TBool) return src;
    if (srcType <= TNull) return cns(env, false);
    if (srcType <= TVec) {
      auto const length = gen(env, CountVec, src);
      return gen(env, NeqInt, length, cns(env, 0));
    }
    if (srcType <= TDict) {
      auto const length = gen(env, CountDict, src);
      return gen(env, NeqInt, length, cns(env, 0));
    }
    if (srcType <= TKeyset) {
      auto const length = gen(env, CountKeyset, src);
      return gen(env, NeqInt, length, cns(env, 0));
    }
    if (srcType <= TDbl)  return gen(env, ConvDblToBool, src);
    if (srcType <= TInt)  return gen(env, ConvIntToBool, src);
    if (srcType <= TStr)  return gen(env, ConvStrToBool, src);
    if (srcType <= TObj) {
      if (auto const cls = srcType.clsSpec().cls()) {
        // We need to exclude interfaces like ConstSet.  For now, just
        // skip anything that's an interface or extension.
        if (!(cls->attrs() & AttrInterface)) {
          if (!cls->instanceCtor()) {
            return cns(env, true);
          }
        }
      }
      return gen(env, ConvObjToBool, inst->taken(), src);
    }
    if (srcType <= TRes)  return cns(env, true);
    if (srcType <= TFunc) return cns(env, true);
    if (srcType <= TClsMeth) return cns(env, true);
  
    return nullptr;
  }
  
  // return true if throws
  bool handleConvNoticeLevel(
    State& env,
    Block* trace,
    const ConvNoticeData* notice_data,
    const char* const from,
    const char* const to) {
    // do this check here because if notice level is none, reason may be nullptr
    if (notice_data->level == ConvNoticeLevel::None) return false;
    assertx(notice_data->reason != nullptr);
    const auto str = cns(env, makeStaticString(folly::sformat(
      "Implicit {} to {} conversion for {}", from, to, notice_data->reason)));
    switch(notice_data->level) {
      case ConvNoticeLevel::Throw:
        gen(env, ThrowInvalidOperation, trace, str);
        return true;
      case ConvNoticeLevel::Log:
        gen(env, RaiseNotice, trace, str);
      // FALLTHROUGH
      case ConvNoticeLevel::None:
        return false;
    }
    not_reached();
  }
  
  SSATmp* simplifyConvTVToStr(State& env, const IRInstruction* inst) {
    auto const src           = inst->src(0);
    auto const srcType       = src->type();
    auto const catchTrace    = inst->taken();
    auto const notice_data   = inst->extra<ConvNoticeData>();
  
    if (srcType <= TBool) {
      const auto tmp = gen(
        env,
        Select,
        src,
        cns(env, s_1.get()),
        cns(env, staticEmptyString())
      );
      auto throws = handleConvNoticeLevel(
        env, catchTrace, notice_data, "bool", "string");
      return throws ? cns(env, TBottom) : tmp ;
    }
    if (srcType <= TNull) {
      auto throws = handleConvNoticeLevel(
        env, catchTrace, notice_data, "null", "string");
      return throws ? cns(env, TBottom) : cns(env, staticEmptyString());
    }
    if (srcType <= TVec) {
      gen(env, ThrowInvalidOperation, catchTrace, cns(env, s_msgVecToStr.get()));
      return cns(env, TBottom);
    }
    if (srcType <= TDict) {
      gen(env, ThrowInvalidOperation, catchTrace, cns(env, s_msgDictToStr.get()));
      return cns(env, TBottom);
    }
    if (srcType <= TKeyset) {
      auto const message = cns(env, s_msgKeysetToStr.get());
      gen(env, ThrowInvalidOperation, catchTrace, message);
      return cns(env, TBottom);
    }
  
    if (srcType <= TDbl) {
      const auto tmp = gen(env, ConvDblToStr, src);
      auto throws = handleConvNoticeLevel(
        env, catchTrace, notice_data, "double", "string");
      return throws ? cns(env, TBottom) : tmp;
    }
    if (srcType <= TInt)    return gen(env, ConvIntToStr, src);
    if (srcType <= TStr) {
      gen(env, IncRef, src);
      return src;
    }
    if (srcType <= TObj)    return gen(env, ConvObjToStr, catchTrace, src);
    if (srcType <= TClsMeth) {
      auto const message = cns(env, s_msgClsMethToStr.get());
      gen(env, ThrowInvalidOperation, catchTrace, message);
      return cns(env, TBottom);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyConvTVToInt(State& env, const IRInstruction* inst) {
    auto const src      = inst->src(0);
    auto const srcType  = src->type();
    auto const catchTrace = inst->taken();
  
    if (srcType <= TInt)  return src;
    if (srcType <= TNull) return cns(env, 0);
  
    auto genFromArray = [&](Opcode op) {
      return gen(env, Select, gen(env, op, src), cns(env, 1), cns(env, 0));
    };
  
    if (srcType <= TVec)    return genFromArray(CountVec);
    if (srcType <= TDict)   return genFromArray(CountDict);
    if (srcType <= TKeyset) return genFromArray(CountKeyset);
    if (srcType <= TBool) return gen(env, ConvBoolToInt, src);
    if (srcType <= TDbl)  return gen(env, ConvDblToInt, src);
    if (srcType <= TStr)  return gen(env, ConvStrToInt, src);
    if (srcType <= TObj)  return gen(env, ConvObjToInt, catchTrace, src);
    if (srcType <= TRes)  return gen(env, ConvResToInt, src);
    if (srcType <= TClsMeth) {
      gen(env, ThrowInvalidOperation, catchTrace,
          cns(env, s_msgClsMethToInt.get()));
      return cns(env, TBottom);
    }
    return nullptr;
  }
  
  SSATmp* simplifyConvTVToDbl(State& env, const IRInstruction* inst) {
    auto const src      = inst->src(0);
    auto const srcType  = src->type();
    auto const catchTrace = inst->taken();
  
    if (srcType <= TDbl)  return src;
    if (srcType <= TNull) return cns(env, 0.0);
    if (srcType <= TVec) {
      auto const length = gen(env, CountVec, src);
      return gen(env, ConvBoolToDbl, gen(env, ConvIntToBool, length));
    }
    if (srcType <= TDict) {
      auto const length = gen(env, CountDict, src);
      return gen(env, ConvBoolToDbl, gen(env, ConvIntToBool, length));
    }
    if (srcType <= TKeyset) {
      auto const length = gen(env, CountKeyset, src);
      return gen(env, ConvBoolToDbl, gen(env, ConvIntToBool, length));
    }
    if (srcType <= TBool) return gen(env, ConvBoolToDbl, src);
    if (srcType <= TInt)  return gen(env, ConvIntToDbl, src);
    if (srcType <= TStr)  return gen(env, ConvStrToDbl, src);
    if (srcType <= TObj)  return gen(env, ConvObjToDbl, inst->taken(), src);
    if (srcType <= TRes)  return gen(env, ConvResToDbl, src);
    if (srcType <= TClsMeth) {
      gen(env, ThrowInvalidOperation, catchTrace,
          cns(env, s_msgClsMethToDbl.get()));
      return cns(env, TBottom);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyConvObjToBool(State& env, const IRInstruction* inst) {
    auto const ty = inst->src(0)->type();
  
    if (ty < TObj &&
        ty.clsSpec().cls() &&
        ty.clsSpec().cls()->isCollectionClass()) {
      if (RuntimeOption::EvalNoticeOnCollectionToBool) return nullptr;
      return gen(env, ColIsNEmpty, inst->src(0));
    }
    return nullptr;
  }
  
  
  SSATmp* simplifyDblAsBits(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      union {
        int64_t i;
        double d;
      };
      d = src->dblVal();
      return cns(env, i);
    }
    return nullptr;
  }
  
  SSATmp* roundImpl(State& env, const IRInstruction* inst, double (*op)(double)) {
    auto const src  = inst->src(0);
  
    if (src->hasConstVal()) {
      return cns(env, op(src->dblVal()));
    }
  
    auto const srcInst = src->inst();
    if (srcInst->op() == ConvIntToDbl || srcInst->op() == ConvBoolToDbl) {
      return src;
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyFloor(State& env, const IRInstruction* inst) {
    return roundImpl(env, inst, floor);
  }
  
  SSATmp* simplifyCeil(State& env, const IRInstruction* inst) {
    return roundImpl(env, inst, ceil);
  }
  
  SSATmp* simplifyCheckInit(State& env, const IRInstruction* inst) {
    auto const srcType = inst->src(0)->type();
    assertx(!srcType.maybe(TMem));
    assertx(inst->taken());
    if (!srcType.maybe(TUninit)) return gen(env, Nop);
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyCheckInitMem(State& env, const IRInstruction* inst) {
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyCheckRDSInitialized(State& env, const IRInstruction* inst) {
    auto const handle = inst->extra<CheckRDSInitialized>()->handle;
    if (!rds::isNormalHandle(handle)) return gen(env, Jmp, inst->next());
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyMarkRDSInitialized(State& env, const IRInstruction* inst) {
    auto const handle = inst->extra<MarkRDSInitialized>()->handle;
    if (!rds::isNormalHandle(handle)) return gen(env, Nop);
    return nullptr;
  }
  
  SSATmp* simplifyMarkRDSAccess(State& env, const IRInstruction* inst) {
    auto const handle = inst->extra<MarkRDSAccess>()->handle;
    auto const profile = rds::profileForHandle(handle);
    if (profile == rds::kUninitHandle) return gen(env, Nop);
    return nullptr;
  }
  
  SSATmp* simplifyInitObjProps(State& env, const IRInstruction* inst) {
    auto const cls = inst->extra<InitObjProps>()->cls;
    if (cls->numDeclProperties() == 0 && !cls->hasMemoSlots()) {
      return gen(env, Nop);
    }
    return nullptr;
  }
  
  SSATmp* simplifyInitObjMemoSlots(State& env, const IRInstruction* inst) {
    auto const cls = inst->extra<InitObjMemoSlots>()->cls;
    if (!cls->hasMemoSlots()) {
      return gen(env, Nop);
    }
    return nullptr;
  }
  
  SSATmp* simplifyCheckType(State& env, const IRInstruction* inst) {
    auto const typeParam = inst->typeParam();
    auto const srcType = inst->src(0)->type();
  
    if (!srcType.maybe(typeParam) || inst->next() == inst->taken() ||
        (inst->next() && inst->next()->isUnreachable())) {
      /*
       * Convert the check into a Jmp.  The dest of the CheckType (which would've
       * been Bottom) is now never going to be defined, so we return a Bottom.
       */
      gen(env, Jmp, inst->taken());
      return cns(env, TBottom);
    }
  
    auto const newType = srcType & typeParam;
    if (srcType <= newType) {
      // The type of the src is the same or more refined than type, so the guard
      // is unnecessary.
      return inst->src(0);
    }
  
    if (inst->taken() && inst->taken()->isUnreachable()) {
      return gen(env, AssertType, newType, inst->src(0));
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyCheckTypeMem(State& env, const IRInstruction* inst) {
    if (inst->typeParam() == TBottom) {
      return gen(env, Jmp, inst->taken());
    }
  
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyAssertType(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
  
    auto const newType = src->type() & inst->typeParam();
    if (newType == TBottom) {
      return cns(env, TBottom);
    }
  
    return src->isA(newType) ? src : nullptr;
  }
  
  SSATmp* simplifyCheckLoc(State& env, const IRInstruction* inst) {
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyCheckStk(State& env, const IRInstruction* inst) {
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyCheckMBase(State& env, const IRInstruction* inst) {
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyCheckNonNull(State& env, const IRInstruction* inst) {
    auto const type = inst->src(0)->type();
  
    if (type <= TNullptr || inst->next() == inst->taken() ||
        (inst->next() && inst->next()->isUnreachable())) {
      gen(env, Jmp, inst->taken());
      return cns(env, TBottom);
    }
  
    if (inst->taken() && inst->taken()->isUnreachable()) {
      return gen(env, AssertType, type - TNullptr, inst->src(0));
    }
  
    if (!type.maybe(TNullptr)) return inst->src(0);
  
    return nullptr;
  }
  
  SSATmp* simplifyDefLabel(State& env, const IRInstruction* inst) {
    if (inst->numDsts() == 0) {
      return gen(env, Nop);
    }
    return nullptr;
  }
  
  SSATmp* decRefImpl(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (noop_decref || !src->type().maybe(TCounted)) {
      return gen(env, Nop);
    }
    return nullptr;
  }
  
  SSATmp* simplifyDecRef(State& env, const IRInstruction* inst) {
    return decRefImpl(env, inst);
  }
  
  SSATmp* simplifyDecRefNZ(State& env, const IRInstruction* inst) {
    return decRefImpl(env, inst);
  }
  
  SSATmp* simplifyIncRef(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (!src->type().maybe(TCounted)) {
      return gen(env, Nop);
    }
    return nullptr;
  }
  
  SSATmp* condJmpImpl(State& env, const IRInstruction* inst) {
    assertx(inst->is(JmpZero, JmpNZero));
    // Both ways go to the same block.
    if (inst->taken() == inst->next()) {
      assertx(inst->taken() != nullptr);
      return gen(env, Jmp, inst->taken());
    }
  
    if (inst->taken() && inst->taken()->isUnreachable()) {
      return gen(env, Nop);
    }
  
    if (inst->next() && inst->next()->isUnreachable()) {
      return gen(env, Jmp, inst->taken());
    }
  
    auto const src = inst->src(0);
    auto const srcInst = src->inst();
  
    // Constant propagate.
    if (src->hasConstVal()) {
      bool val = src->isA(TBool) ? src->boolVal()
                                 : static_cast<bool>(src->intVal());
      if (val == inst->is(JmpNZero)) {
        // always taken
        assertx(inst->taken());
        return gen(env, Jmp, inst->taken());
      }
      // Never taken. Since simplify() is also run when building the IR,
      // inst->next() could be nullptr at this moment.
      return gen(env, Nop);
    }
  
    auto absorb = [&](){
      return gen(env, inst->op(), inst->taken(), srcInst->src(0));
    };
    auto absorbOpp = [&](){
      return gen(env,
                 inst->op() == JmpZero ? JmpNZero : JmpZero,
                 inst->taken(),
                 srcInst->src(0)
                );
    };
  
    // Absorb negations.
    if (srcInst->is(XorBool) && srcInst->src(1)->hasConstVal(true)) {
      return absorbOpp();
    }
  
    // Absorb ConvIntToBool.
    if (srcInst->is(ConvIntToBool)) {
      return absorb();
    }
    if (srcInst->is(ConvBoolToInt)) {
      return absorb();
    }
  
    // Absorb boolean comparisons.
    if (srcInst->is(EqBool) && srcInst->src(1)->hasConstVal()) {
      return srcInst->src(1)->boolVal() ? absorb() : absorbOpp();
    }
    if (srcInst->is(NeqBool) && srcInst->src(1)->hasConstVal()) {
      return srcInst->src(1)->boolVal() ? absorbOpp() : absorb();
    }
  
    // Absorb integer comparisons against constant zero.
    if (srcInst->is(EqInt) && srcInst->src(1)->hasConstVal(0)) {
      return absorbOpp();
    }
    if (srcInst->is(NeqInt) && srcInst->src(1)->hasConstVal(0)) {
      return absorb();
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyJmpZero(State& env, const IRInstruction* i) {
    return condJmpImpl(env, i);
  }
  
  SSATmp* simplifyJmpNZero(State& env, const IRInstruction* i) {
    return condJmpImpl(env, i);
  }
  
  SSATmp* simplifyJmp(State& env, const IRInstruction* inst) {
    assertx(inst->taken());
    if (inst->taken()->isUnreachable()) {
      return gen(env, Unreachable, *inst->taken()->back().extra<Unreachable>());
    }
  
    return nullptr;
  }
  
  SSATmp* simplifySelect(State& env, const IRInstruction* inst) {
    auto const cond = inst->src(0);
    auto const tval = inst->src(1);
    auto const fval = inst->src(2);
  
    // Simplifications based on condition:
  
    if (cond->hasConstVal()) {
      auto const cval = cond->isA(TBool)
        ? cond->boolVal()
        : static_cast<bool>(cond->intVal());
      return cval ? tval : fval;
    }
  
    // The condition isn't statically known, but could be computed from a
    // different operation we can absorb.
    auto const condInst = cond->inst();
    auto const absorb = [&]{
      return gen(env, Select, condInst->src(0), tval, fval);
    };
    auto const absorbOpp = [&]{
      return gen(env, Select, condInst->src(0), fval, tval);
    };
  
    // Conversions between int and bool can't change which value is selected.
    if (condInst->is(ConvIntToBool)) return absorb();
    if (condInst->is(ConvBoolToInt)) return absorb();
  
    // Condition is negated, so check the pre-negated condition with flipped
    // values.
    if (condInst->is(XorBool) && condInst->src(1)->hasConstVal(true)) {
      return absorbOpp();
    }
  
    // Condition comes from comparisons against true/false or 0, which is
    // equivalent to selecting on original value (possibly with values flipped).
    if (condInst->is(EqBool) && condInst->src(1)->hasConstVal()) {
      return condInst->src(1)->boolVal() ? absorb() : absorbOpp();
    }
    if (condInst->is(NeqBool) && condInst->src(1)->hasConstVal()) {
      return condInst->src(1)->boolVal() ? absorbOpp() : absorb();
    }
    if (condInst->is(EqInt) && condInst->src(1)->hasConstVal(0)) {
      return absorbOpp();
    }
    if (condInst->is(NeqInt) && condInst->src(1)->hasConstVal(0)) {
      return absorb();
    }
  
    // Condition comes from Select C, X, 0 or Select C, 0, X (where X != 0), which
    // is equivalent to selecting on C directly.
    if (condInst->is(Select)) {
      auto const condInstT = condInst->src(1);
      auto const condInstF = condInst->src(2);
      if (condInstT->hasConstVal(TInt) &&
          condInstT->intVal() != 0 &&
          condInstF->hasConstVal(0)) {
        return absorb();
      }
      if (condInstT->hasConstVal(0) &&
          condInstF->hasConstVal(TInt) &&
          condInstF->intVal() != 0) {
        return absorbOpp();
      }
    }
  
    // Simplifications based on known value choices:
  
    // If the two values are the same tmp, or if they're both constants with the
    // same value, no need to do a select, as we'll always get the same value.
    if (tval == fval) return tval;
    if ((tval->type() == fval->type()) &&
        (tval->type().hasConstVal() ||
         tval->type().subtypeOfAny(TUninit, TInitNull, TNullptr))) {
      return tval;
    }
  
    // If either value isn't satisfiable, assume it comes from unreachable code.
    if (tval->isA(TBottom)) return fval;
    if (fval->isA(TBottom)) return tval;
  
    // If the values are true and false (and vice-versa), then its equal to the
    // value of the condition itself (or inverted).
    if (tval->hasConstVal(true) && fval->hasConstVal(false)) {
      if (cond->isA(TBool)) return cond;
      if (cond->isA(TInt)) return gen(env, NeqInt, cond, cns(env, 0));
    }
    if (tval->hasConstVal(false) && fval->hasConstVal(true)) {
      if (cond->isA(TBool)) return gen(env, XorBool, cond, cns(env, true));
      if (cond->isA(TInt)) return gen(env, EqInt, cond, cns(env, 0));
    }
  
    // Select C, 0, 1 or Select C, 1, 0 is the same as a bool -> int conversion.
    if (tval->hasConstVal(1) && fval->hasConstVal(0) && cond->isA(TBool)) {
      return gen(env, ConvBoolToInt, cond);
    }
    if (tval->hasConstVal(0) && fval->hasConstVal(1) && cond->isA(TBool)) {
      return gen(env, ConvBoolToInt, gen(env, XorBool, cond, cns(env, true)));
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyAssertNonNull(State& /*env*/, const IRInstruction* inst) {
    if (!inst->src(0)->type().maybe(TNullptr)) {
      return inst->src(0);
    }
    return nullptr;
  }
  
  SSATmp* simplifyCheckVecBounds(State& env, const IRInstruction* inst) {
    auto const array = inst->src(0);
    auto const idx   = inst->src(1);
  
    auto const idxVal = idx->hasConstVal()
      ? Optional<int64_t>(idx->intVal())
      : std::nullopt;
    switch (vecBoundsStaticCheck(array->type(), idxVal)) {
    case VecBounds::In:       return gen(env, Nop);
    case VecBounds::Out:      return gen(env, Jmp, inst->taken());
    case VecBounds::Unknown:  break;
    }
  
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyReserveVecNewElem(State& env, const IRInstruction* inst) {
    auto const base = inst->src(0);
  
    if (base->type() <= TPersistentVec) {
      return cns(env, TBottom);
    }
    return nullptr;
  }
  
  namespace {
  
  SSATmp* arrGetKImpl(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    if (!inst->src(2)->hasConstVal(TInt)) return nullptr;
    auto const pos = inst->src(2)->intVal();
    assertx(validPos(ssize_t(pos)));
    if (!arr->hasConstVal()) return nullptr;
  
    auto const mixed = VanillaDict::as(arr->arrLikeVal());
    auto const tv = mixed->getArrayElmPtr(pos);
  
    // The array doesn't contain a valid element at that offset. Since this
    // instruction should be guarded by a check, this (should be) unreachable.
    if (!tv) {
      return cns(env, TBottom);
    }
  
    assertx(tvIsPlausible(*tv));
    return cns(env, *tv);
  }
  
  template <typename I, typename S, typename F>
  SSATmp* hackArrQueryImpl(State& /*env*/, const IRInstruction* inst, I getInt,
                           S getStr, F finish) {
    auto const arr = inst->src(0);
    auto const key = inst->src(1);
  
    if (!arr->hasConstVal()) return nullptr;
    if (!key->hasConstVal(TInt) && !key->hasConstVal(TStr)) return nullptr;
  
    auto const value = key->hasConstVal(TInt)
      ? getInt(arr, key->intVal())
      : getStr(arr, key->strVal());
    return finish(value);
  }
  
  template <typename I, typename S>
  SSATmp* hackArrGetImpl(State& env, const IRInstruction* inst,
                         I getInt, S getStr) {
    return hackArrQueryImpl(
      env, inst,
      getInt, getStr,
      [&] (TypedValue tv) {
        if (tv.is_init()) return cns(env, tv);
        gen(env, ThrowOutOfBounds, inst->taken(), inst->src(0), inst->src(1));
        return cns(env, TBottom);
      }
    );
  }
  
  template <typename I, typename S>
  SSATmp* hackArrGetQuietImpl(State& env, const IRInstruction* inst,
                              I getInt, S getStr) {
    return hackArrQueryImpl(
      env, inst,
      getInt, getStr,
      [&] (TypedValue tv) {
        return tv.is_init() ? cns(env, tv) : cns(env, TInitNull);
      }
    );
  }
  
  template <typename I, typename S>
  SSATmp* hackArrIssetImpl(State& env, const IRInstruction* inst,
                           I getInt, S getStr) {
    return hackArrQueryImpl(
      env, inst,
      getInt, getStr,
      [&] (TypedValue tv) { return cns(env, !tvIsNull(tv)); }
    );
  }
  
  template <typename I, typename S>
  SSATmp* hackArrIdxImpl(State& env, const IRInstruction* inst,
                         I getInt, S getStr) {
    return hackArrQueryImpl(
      env, inst,
      getInt, getStr,
      [&] (TypedValue tv) { return tv.is_init() ? cns(env, tv) : inst->src(2); }
    );
  }
  
  template <typename I, typename S>
  SSATmp* hackArrAKExistsImpl(State& env, const IRInstruction* inst,
                              I getInt, S getStr) {
    return hackArrQueryImpl(
      env, inst,
      getInt, getStr,
      [&] (TypedValue tv) { return cns(env, tv.is_init()); }
    );
  }
  
  }
  
  #define X(Name, Action)                                               \
  SSATmp* simplify##Name(State& env, const IRInstruction* inst) {       \
    return hackArr##Action##Impl(                                       \
      env, inst,                                                        \
      [](SSATmp* a, int64_t k) {                                        \
        return VanillaDict::NvGetInt(a->arrLikeVal(), k);                \
      },                                                                \
      [](SSATmp* a, const StringData* k) {                              \
        return VanillaDict::NvGetStr(a->arrLikeVal(), k);                \
      }                                                                 \
    );                                                                  \
  }
  
  X(DictGet, Get)
  X(DictGetQuiet, GetQuiet)
  X(DictIsset, Isset)
  X(DictIdx, Idx)
  X(AKExistsDict, AKExists)
  
  #undef X
  
  #define X(Name, Action)                                               \
  SSATmp* simplify##Name(State& env, const IRInstruction* inst) {       \
    return hackArr##Action##Impl(                                       \
      env, inst,                                                        \
      [](SSATmp* a, int64_t k) {                                        \
        return VanillaKeyset::NvGetInt(a->keysetVal(), k);              \
      },                                                                \
      [](SSATmp* a, const StringData* k) {                              \
        return VanillaKeyset::NvGetStr(a->keysetVal(), k);              \
      }                                                                 \
    );                                                                  \
  }
  
  X(KeysetGet, Get)
  X(KeysetGetQuiet, GetQuiet)
  X(KeysetIsset, Isset)
  X(KeysetIdx, Idx)
  X(AKExistsKeyset, AKExists)
  
  #undef X
  
  SSATmp* simplifyDictGetK(State& env, const IRInstruction* inst) {
    return arrGetKImpl(env, inst);
  }
  
  SSATmp* simplifyKeysetGetK(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    if (!inst->src(2)->hasConstVal(TInt)) return nullptr;
    auto const pos = inst->src(2)->intVal();
  
    assertx(validPos(ssize_t(pos)));
    if (!arr->hasConstVal()) return nullptr;
  
    auto const set = VanillaKeyset::asSet(arr->keysetVal());
    auto const tv = set->tvOfPos(pos);
  
    // The array doesn't contain a valid element at that offset. Since this
    // instruction should be guarded by a check, this (should be) unreachable.
    if (!tv) {
      return cns(env, TBottom);
    }
  
    assertx(tvIsPlausible(*tv));
    assertx(isStringType(tv->m_type) || isIntType(tv->m_type));
    return cns(env, *tv);
  }
  
  SSATmp* simplifyGetDictPtrIter(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const idx = inst->src(1);
    if (!arr->hasConstVal(TArrLike)) return nullptr;
    if (!idx->hasConstVal(TInt)) return nullptr;
    auto const ad  = VanillaDict::as(arr->arrLikeVal());
    auto const elm = ad->data() + idx->intVal();
    return cns(env, Type::cns(elm, outputType(inst)));
  }
  
  SSATmp* simplifyCheckDictKeys(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (!src->hasConstVal()) return mergeBranchDests(env, inst);
    auto const arr = src->arrLikeVal();
  
    auto match = true;
    IterateKV(arr, [&](TypedValue key, TypedValue val){
      match &= Type::cns(key) <= inst->typeParam();
      return !match;
    });
    return match ? gen(env, Nop) : gen(env, Jmp, inst->taken());
  }
  
  SSATmp* simplifyCheckMissingKeyInArrLike(State& env,
                                           const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const key = inst->src(1);
    if (!arr->hasConstVal(TArrLike) || !key->hasConstVal(TStaticStr)) {
      return mergeBranchDests(env, inst);
    }
    auto const ad = arr->arrLikeVal();
    auto const sd = key->strVal();
    if (ad->hasStrKeyTable() && !ad->missingKeySideTable().mayContain(sd)) {
      return gen(env, Nop);
    }
    return gen(env, Jmp, inst->taken());
  }
  
  SSATmp* simplifyCheckOffsetImpl(State& env, const IRInstruction* inst) {
    assertx(inst->is(CheckDictOffset, CheckKeysetOffset));
    auto const arr = inst->src(0);
    auto const key = inst->src(1);
    auto const& extra = inst->extra<IndexData>();
    assertx(validPos(ssize_t(extra->index)));
  
    auto const keyType =
      arrLikePosType(arr->type(), Type::cns(extra->index), true, inst->ctx());
    assertx(keyType <= (TInt | TStr));
    assertx(key->isA(TInt | TStr));
    if (keyType <= TBottom) return gen(env, Jmp, inst->taken());
    if (keyType <= TInt) {
      if (!key->type().maybe(TInt)) return gen(env, Jmp, inst->taken());
    }
    if (keyType <= TStr) {
      if (!key->type().maybe(TStr)) return gen(env, Jmp, inst->taken());
    }
  
    if (key->isA(TInt) && keyType.hasConstVal(TInt)) {
      auto const idx = keyType.intVal();
      auto const cmp = gen(env, EqInt, key, cns(env, idx));
      return gen(env, JmpZero, inst->taken(), cmp);
    }
    if (key->isA(TStr) && keyType.hasConstVal(TStr)) {
      auto const str = keyType.strVal();
      auto const cmp = gen(env, EqStrPtr, key, cns(env, str));
      return gen(env, JmpZero, inst->taken(), cmp);
    }
    return mergeBranchDests(env, inst);
  }
  
  SSATmp* simplifyCheckDictOffset(State& env, const IRInstruction* inst) {
    return simplifyCheckOffsetImpl(env, inst);
  }
  
  SSATmp* simplifyCheckKeysetOffset(State& env, const IRInstruction* inst) {
    return simplifyCheckOffsetImpl(env, inst);
  }
  
  SSATmp* simplifyCheckArrayCOW(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    if (arr->isA(TPersistentArrLike)) {
      gen(env, Jmp, inst->taken());
      return cns(env, TBottom);
    }
    return nullptr;
  }
  
  SSATmp* simplifyCount(State& env, const IRInstruction* inst) {
    auto const val = inst->src(0);
    auto const ty = val->type();
  
    if (ty <= TNull) return cns(env, 0);
  
    auto const oneTy = TBool | TInt | TDbl | TStr | TRes;
    if (ty <= oneTy) return cns(env, 1);
  
    if (ty <= TVec) return gen(env, CountVec, val);
    if (ty <= TDict) return gen(env, CountDict, val);
    if (ty <= TKeyset) return gen(env, CountKeyset, val);
  
    if (ty < TObj) {
      auto const cls = ty.clsSpec().cls();
      if (cls != nullptr && cls->isCollectionClass()) {
        return gen(env, CountCollection, val);
      }
    }
    return nullptr;
  }
  
  SSATmp* simplifyCountHelper(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal(TArrLike)) return cns(env, src->arrLikeVal()->size());
  
    auto const at = src->type().arrSpec().type();
    if (!at) return nullptr;
    using A = RepoAuthType::Array;
    switch (at->tag()) {
    case A::Tag::Tuple:
      if (at->emptiness() == A::Empty::No) return cns(env, at->size());
      break;
    case A::Tag::Packed:
      break;
    }
    return nullptr;
  }
  
  #define X(Name)                                                 \
  SSATmp* simplify##Name(State& env, const IRInstruction* inst) { \
    return simplifyCountHelper(env, inst);                        \
  }
  
  X(CountVec)
  X(CountDict)
  X(CountKeyset)
  
  #undef X
  
  // Simplify generic bespoke getters, either based on the DataType (often we
  // can make simplifications for all varrays and vecs) or specific layout.
  
  SSATmp* simplifyBespokeGet(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const key = inst->src(1);
    assertx(key->type().subtypeOfAny(TInt, TStr));
  
    if (arr->hasConstVal()) {
      auto const ad = arr->arrLikeVal();
      if (ad->empty()) return cns(env, TUninit);
      if (key->hasConstVal()) {
        auto const tv = key->isA(TInt) ? ad->get(key->intVal())
                                       : ad->get(key->strVal());
        return cns(env, tv);
      }
    }
  
    if (arr->isA(TVec)) {
      if (key->isA(TStr)) return cns(env, TUninit);
      if (arr->type().arrSpec().monotype() &&
          inst->extra<BespokeGet>()->state == BespokeGetData::KeyState::Present) {
        return gen(env, LdMonotypeVecElem, arr, key);
      }
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyBespokeGetThrow(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const key = inst->src(1);
    assertx(key->type().subtypeOfAny(TInt, TStr));
  
    if (arr->hasConstVal()) {
      auto const ad = arr->arrLikeVal();
      if (ad->empty()) {
        gen(env, ThrowOutOfBounds, inst->taken(), arr, key);
        return cns(env, TBottom);
      }
      if (key->hasConstVal()) {
        auto const tv = key->isA(TInt) ? ad->get(key->intVal())
                                       : ad->get(key->strVal());
        if (tv.is_init()) {
          return cns(env, tv);
        } else {
          gen(env, ThrowOutOfBounds, inst->taken(), arr, key);
          return cns(env, TBottom);
        }
      }
    }
  
    if (arr->type().arrSpec().is_struct() && key->isA(TInt)) {
      gen(env, ThrowOutOfBounds, inst->taken(), arr, key);
      return cns(env, TBottom);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyStructDictSlot(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const key = inst->src(1);
    assertx(arr->type().arrSpec().is_struct());
  
    auto const& layout = arr->type().arrSpec().layout();
    if (key->hasConstVal(TStr) && layout.bespokeLayout()->isConcrete()) {
      auto const& slayout = bespoke::StructLayout::As(layout.bespokeLayout());
      auto const slot = slayout->keySlot(key->strVal());
      if (slot == kInvalidSlot) {
        gen(env, Jmp, inst->taken());
        return cns(env, TBottom);
      }
      return cns(env, slot);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyBespokeUnset(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const key = inst->src(1);
  
    // If the key is definitely missing, we can skip the remove.
    auto const missing = [&]{
      if (arr->isA(TVec) && key->isA(TStr)) return true;
      auto const type = arrLikeElemType(arr->type(), key->type(), inst->ctx());
      return type.first == TBottom;
    }();
    if (missing) return arr;
  
    if (arr->type().arrSpec().is_struct() && key->hasConstVal(TStr)) {
      return gen(env, StructDictUnset, arr, key);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyBespokeIterFirstPos(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
  
    if (arr->hasConstVal()) {
      auto const pos = arr->type().arrLikeVal()->iter_begin();
      return cns(env, pos);
    }
  
    if (arr->isA(TVec)) {
      return cns(env, 0);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyBespokeIterLastPos(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
  
    if (arr->hasConstVal()) {
      auto const pos = arr->type().arrLikeVal()->iter_last();
      return cns(env, pos);
    }
  
    if (arr->isA(TVec)) {
      auto const size = gen(env, CountVec, arr);
      return gen(env, SubInt, size, cns(env, 1));
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyBespokeIterEnd(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const spec = arr->type().arrSpec();
  
    if (arr->hasConstVal()) {
      auto const pos = arr->type().arrLikeVal()->iter_end();
      return cns(env, pos);
    }
  
    if (arr->isA(TVec)) {
      return gen(env, CountVec, arr);
    }
  
    if (arr->isA(TDict) && spec.monotype()) {
      auto const size = gen(env, CountDict, arr);
      auto const tombstones = gen(env, LdMonotypeDictTombstones, arr);
      return gen(env, AddInt, size, tombstones);
    }
  
    if (arr->isA(TDict) && spec.is_struct()) {
      return gen(env, CountDict, arr);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyBespokeIterGetKey(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const pos = inst->src(1);
  
    if (arr->hasConstVal() && pos->hasConstVal()) {
      auto const idx = pos->intVal();
      auto const ad = arr->type().arrLikeVal();
      if (idx < 0 || idx >= ad->size()) return cns(env, TBottom);
  
      auto const key = arr->type().arrLikeVal()->nvGetKey(pos->intVal());
      return cns(env, key);
    }
  
    if (arr->isA(TVec)) return pos;
  
    if (arr->isA(TDict) && arr->type().arrSpec().monotype()) {
      return gen(env, LdMonotypeDictKey, arr, pos);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyBespokeIterGetVal(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const pos = inst->src(1);
  
    if (arr->hasConstVal() && pos->hasConstVal()) {
      auto const idx = pos->intVal();
      auto const ad = arr->type().arrLikeVal();
      if (idx < 0 || idx >= ad->size()) return cns(env, TBottom);
  
      auto const val = arr->type().arrLikeVal()->nvGetVal(pos->intVal());
      return cns(env, val);
    }
  
    if (arr->isA(TVec)) {
      auto const data = BespokeGetData { BespokeGetData::KeyState::Present };
      return gen(env, BespokeGet, data, arr, pos);
    }
  
    if (arr->isA(TDict) && arr->type().arrSpec().monotype()) {
      return gen(env, LdMonotypeDictVal, arr, pos);
    }
  
    return nullptr;
  }
  
  // Simplify layout-specific bespoke helpers.
  
  SSATmp* simplifyLdMonotypeDictTombstones(
      State& env, const IRInstruction* inst) {
    auto const type = inst->src(0)->type();
  
    if (type.hasConstVal()) {
      auto const arr = type.arrLikeVal();
      return cns(env, arr->iter_end() - arr->size());
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyLdMonotypeDictKey(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const pos = inst->src(1);
    if (arr->hasConstVal() && pos->hasConstVal()) {
      auto const tv = arr->arrLikeVal()->nvGetKey(pos->intVal());
      return tv.is_init() ? cns(env, tv) : nullptr;
    }
    return nullptr;
  }
  
  SSATmp* simplifyLdMonotypeDictVal(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const pos = inst->src(1);
    if (arr->hasConstVal() && pos->hasConstVal()) {
      auto const tv = arr->arrLikeVal()->nvGetVal(pos->intVal());
      return tv.is_init() ? cns(env, tv) : nullptr;
    }
    return nullptr;
  }
  
  SSATmp* simplifyLdMonotypeVecElem(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    auto const key = inst->src(1);
    if (arr->hasConstVal() && key->hasConstVal()) {
      auto const tv = arr->arrLikeVal()->get(key->intVal());
      return tv.is_init() ? cns(env, tv) : nullptr;
    }
    return nullptr;
  }
  
  SSATmp* simplifyLdClsName(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    return src->hasConstVal(TCls) ? cns(env, src->clsVal()->name()) : nullptr;
  }
  
  SSATmp* simplifyLdLazyCls(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    return src->hasConstVal(TCls) ?
      cns(env, LazyClassData::create(src->clsVal()->name())) : nullptr;
  }
  
  SSATmp* simplifyLdLazyClsName(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    return src->hasConstVal(TLazyCls) ?
      cns(env, src->lclsVal().name()) : nullptr;
  }
  
  SSATmp* simplifyLookupClsRDS(State& env, const IRInstruction* inst) {
    auto const str = inst->src(0);
    if (str->inst()->is(LdClsName, LdLazyCls)) {
      return str->inst()->src(0);
    }
    if (str->hasConstVal()) {
      auto const sval = str->strVal();
      auto const result = Class::lookupUniqueInContext(sval, nullptr, nullptr);
      if (result) return cns(env, result);
    }
    return nullptr;
  }
  
  SSATmp* simplifyLookupSPropSlot(State& env, const IRInstruction* inst) {
    auto const cls = inst->src(0);
    auto const name = inst->src(1);
    if (!cls->hasConstVal(TCls) || !name->hasConstVal(TStr)) return nullptr;
    return cns(env, cls->clsVal()->lookupSProp(name->strVal()));
  }
  
  SSATmp* simplifyLdStrLen(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    return src->hasConstVal(TStr) ? cns(env, src->strVal()->size()) : nullptr;
  }
  
  SSATmp* simplifyLdVecElem(State& env, const IRInstruction* inst) {
    auto const src0 = inst->src(0);
    auto const src1 = inst->src(1);
    if (src0->hasConstVal() && src1->hasConstVal(TInt)) {
      auto const arr = src0->arrLikeVal();
      auto const idx = src1->intVal();
      assertx(arr->isVanillaVec());
      auto const tv = VanillaVec::NvGetInt(arr, idx);
      return tv.is_init() ? cns(env, tv) : nullptr;
    }
    return nullptr;
  }
  
  template <class F>
  SSATmp* simplifyByClass(State& /*env*/, const SSATmp* src, F f) {
    if (!src->isA(TObj)) return nullptr;
    if (auto const spec = src->type().clsSpec()) {
      return f(spec.cls(), spec.exact());
    }
    return nullptr;
  }
  
  SSATmp* simplifyCallBuiltin(State& env, const IRInstruction* inst) {
    if (inst->numSrcs() != 3) return nullptr;
  
    auto const thiz = inst->src(2);
    return simplifyByClass(
      env, thiz,
      [&](const Class* cls, bool) -> SSATmp* {
        auto const callee = inst->extra<CallBuiltin>()->callee;
        if (cls->isCollectionClass()) {
          if (callee->name()->isame(s_isEmpty.get())) {
            FTRACE(3, "simplifying collection: {}\n", callee->name()->data());
            return gen(env, ColIsEmpty, thiz);
          }
          if (callee->name()->isame(s_count.get())) {
            FTRACE(3, "simplifying collection: {}\n", callee->name()->data());
            return gen(env, CountCollection, thiz);
          }
          return nullptr;
        }
  
        if (cls->classof(c_Awaitable::classof())) {
          auto const genState = [&] (Opcode op, int64_t whstate) -> SSATmp* {
            // these methods all spring from the base class
            assertx(callee->cls()->name()->isame(s_Awaitable.get()));
            auto const state = gen(env, LdWHState, thiz);
            return gen(env, op, state, cns(env, whstate));
          };
          auto const methName = callee->name();
          if (methName->isame(s_isFinished.get())) {
            return genState(LteInt, int64_t{c_Awaitable::STATE_FAILED});
          }
          if (methName->isame(s_isSucceeded.get())) {
            return genState(EqInt, int64_t{c_Awaitable::STATE_SUCCEEDED});
          }
          if (methName->isame(s_isFailed.get())) {
            return genState(EqInt, int64_t{c_Awaitable::STATE_FAILED});
          }
        }
  
        return nullptr;
      });
  }
  
  SSATmp* simplifyIsWaitHandle(State& env, const IRInstruction* inst) {
    return simplifyByClass(
      env, inst->src(0),
      [&](const Class* cls, bool) -> SSATmp* {
        if (cls->classof(c_Awaitable::classof())) return cns(env, true);
        if (!isInterface(cls) &&
            !c_Awaitable::classof()->classof(cls)) {
          return cns(env, false);
        }
        return nullptr;
      });
  }
  
  SSATmp* simplifyLdWHState(State& env, const IRInstruction* inst) {
    auto const wh = canonical(inst->src(0));
    if (wh->inst()->is(CreateSSWH)) {
      return cns(env, int64_t{c_Awaitable::STATE_SUCCEEDED});
    }
    return nullptr;
  }
  
  SSATmp* simplifyLdWHResult(State& env, const IRInstruction* inst) {
    auto const wh = canonical(inst->src(0));
    if (wh->inst()->is(CreateSSWH)) {
      return wh->inst()->src(0);
    }
    return nullptr;
  }
  
  SSATmp* simplifyLdWHNotDone(State& env, const IRInstruction* inst) {
    return simplifyByClass(
      env, inst->src(0),
      [&](const Class* cls, bool) -> SSATmp* {
        if (cls->classof(c_StaticWaitHandle::classof())) return cns(env, 0);
        return nullptr;
      });
  }
  
  SSATmp* simplifyIsCol(State& env, const IRInstruction* inst) {
    return simplifyByClass(
      env, inst->src(0),
      [&](const Class* cls, bool) -> SSATmp* {
        if (cls->isCollectionClass()) return cns(env, true);
        if (!isInterface(cls)) return cns(env, false);
        return nullptr;
      });
  }
  
  SSATmp* simplifyIsLegacyArrLike(State& env, const IRInstruction* inst) {
    auto const arr = inst->src(0);
    if (arr->hasConstVal()) {
      return cns(env, arr->arrLikeVal()->isLegacyArray());
    }
    return nullptr;
  }
  
  SSATmp* simplifyHasToString(State& env, const IRInstruction* inst) {
    return simplifyByClass(
      env, inst->src(0),
      [&](const Class* cls, bool exact) -> SSATmp* {
        if (cls->getToString() != nullptr) return cns(env, true);
        if (exact) return cns(env, false);
        return nullptr;
      });
  }
  
  SSATmp* simplifyHasReifiedGenerics(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal()) {
      return cns(env, src->funcVal()->hasReifiedGenerics());
    }
    return nullptr;
  }
  
  SSATmp* simplifyChrInt(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal(TInt)) {
      auto const str = makeStaticString(char(src->intVal() & 255));
      return cns(env, str);
    }
    return nullptr;
  }
  
  SSATmp* simplifyOrdStr(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (src->hasConstVal(TStr)) {
      // a static string is passed in, resolve with a constant.
      unsigned char first = src->strVal()->data()[0];
      return cns(env, int64_t{first});
    }
    if (src->inst()->is(ChrInt)) {
      return gen(env, AndInt, src->inst()->src(0), cns(env, 255));
    }
    return nullptr;
  }
  
  SSATmp* simplifyJmpSwitchDest(State& env, const IRInstruction* inst) {
    auto const index = inst->src(0);
    if (!index->hasConstVal(TInt)) return nullptr;
  
    auto const indexVal = index->intVal();
    auto const sp = inst->src(1);
    auto const fp = inst->src(2);
    auto const& extra = *inst->extra<JmpSwitchDest>();
  
    if (indexVal < 0 || indexVal >= extra.cases) {
      // Instruction is unreachable.
      return gen(env, Unreachable, ASSERT_REASON);
    }
  
    auto const newExtra = ReqBindJmpData {
      extra.targets[indexVal],
      extra.spOffBCFromStackBase,
      extra.spOffBCFromIRSP
    };
    return gen(env, ReqBindJmp, newExtra, sp, fp);
  }
  
  SSATmp* simplifyCheckRange(State& env, const IRInstruction* inst) {
    auto const val = inst->src(0);
    auto const limit = inst->src(1);
  
    // CheckRange returns (0 <= val < limit).
    if (val && val->hasConstVal(TInt)) {
      if (val->intVal() < 0) return cns(env, false);
  
      if (limit && limit->hasConstVal(TInt)) {
        return cns(env, val->intVal() < limit->intVal());
      }
    }
  
    if (limit && limit->hasConstVal(TInt) && limit->intVal() <= 0) {
      return cns(env, false);
    }
  
    return nullptr;
  }
  
  SSATmp* simplifyGetMemoKeyScalar(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
  
    // Note: this all uses the fully generic memo key scheme. If we used a more
    // specific scheme, then the GetMemoKey op wouldn't have been emitted.
  
    if (src->hasConstVal()) {
      try {
        ThrowAllErrorsSetter taes;
        auto const key =
          HHVM_FN(serialize_memoize_param)(*src->variantVal().asTypedValue());
        SCOPE_EXIT { tvDecRefGen(key); };
        assertx(tvIsPlausible(key));
        if (tvIsString(&key)) {
          return cns(env, makeStaticString(key.m_data.pstr));
        } else {
          assertx(key.m_type == KindOfInt64);
          return cns(env, key.m_data.num);
        }
      } catch (...) {
      }
    }
  
    if (src->isA(TInt)) return src;
    if (src->isA(TBool)) {
      return gen(
        env,
        Select,
        src,
        cns(env, s_trueMemoKey.get()),
        cns(env, s_falseMemoKey.get())
      );
    }
    if (src->isA(TNull)) return cns(env, s_nullMemoKey.get());
  
    return nullptr;
  }
  
  SSATmp* simplifyGetMemoKey(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
  
    if (auto ret = simplifyGetMemoKeyScalar(env, inst)) return ret;
    if (src->isA(TUncounted|TStr) &&
        !RuntimeOption::EvalRaiseClassConversionWarning) {
      return gen(env, GetMemoKeyScalar, src);
    }
    return nullptr;
  }
  
  SSATmp* simplifyStrictlyIntegerConv(State& env, const IRInstruction* inst) {
    auto const src = inst->src(0);
    if (!src->hasConstVal()) return nullptr;
    int64_t n;
    if (src->strVal()->isStrictlyInteger(n)) return cns(env, n);
    gen(env, IncRef, src);
    return src;
  }
  
  SSATmp* simplifyRaiseErrorOnInvalidIsAsExpressionType(
    State& env,
    const IRInstruction* inst
  ) {
    auto const ts = inst->src(0);
    if (!ts->hasConstVal(TDict)) {
      return nullptr;
    }
    auto const tsVal = ts->arrLikeVal();
    if (errorOnIsAsExpressionInvalidTypes(ArrNR(tsVal), true)) {
      return nullptr;
    }
    return ts;
  }
  
  SSATmp* simplifyCheckClsMethFunc(State& env, const IRInstruction* inst) {
    if (!inst->src(0)->hasConstVal(TFunc)) return nullptr;
    auto const func = inst->src(0)->funcVal();
    if (func->isStaticInPrologue() && !func->isAbstract()) {
      return gen(env, Nop);
    }
    return nullptr;
  }
  
  SSATmp* simplifyNewClsMeth(State& env, const IRInstruction* inst) {
    auto const cls = inst->src(0);
    auto const func = inst->src(1);
    if (!cls->hasConstVal() || !func->hasConstVal()) return nullptr;
    auto const clsmeth = ClsMethDataRef::create(
        const_cast<Class*>(cls->clsVal()),
        const_cast<Func*>(func->funcVal()));
    return cns(env, clsmeth);
  }
  
  SSATmp* simplifyLdClsFromClsMeth(State& env, const IRInstruction* inst) {
    auto const clsmeth = inst->src(0);
    if (!clsmeth->hasConstVal()) return nullptr;
    return cns(env, clsmeth->clsmethVal()->getCls());
  }
  
  SSATmp* simplifyLdFuncFromClsMeth(State& env, const IRInstruction* inst) {
    auto const clsmeth = inst->src(0);
    if (!clsmeth->hasConstVal()) return nullptr;
    return cns(env, clsmeth->clsmethVal()->getFunc());
  }
  
  SSATmp* simplifyStructDictTypeBoundCheck(State& env,
                                           const IRInstruction* inst) {
    auto const val  = inst->src(0);
    auto const arr  = inst->src(1);
    auto const slot = inst->src(2);
  
    auto const& layout = arr->type().arrSpec().layout();
    assertx(layout.is_struct());
    if (!layout.bespokeLayout()->isConcrete()) return nullptr;
    auto const slayout = bespoke::StructLayout::As(layout.bespokeLayout());
  
    if (slot->hasConstVal()) {
      if (slot->intVal() >= slayout->numFields()) return cns(env, TBottom);
      return gen(
        env,
        CheckType,
        slayout->getTypeBound(slot->intVal()),
        inst->taken(),
        val
      );
    } else {
      auto const type = slayout->getUnionTypeBound();
      if (!type.isKnownDataType()) return nullptr;
      return gen(
        env,
        CheckType,
        type,
        inst->taken(),
        val
      );
    }
  
    return nullptr;
  }
  
  //////////////////////////////////////////////////////////////////////
  
  SSATmp* simplifyWork(State& env, const IRInstruction* inst) {
    env.insts.push(inst);
  
    SCOPE_EXIT {
      assertx(env.insts.top() == inst);
      env.insts.pop();
    };
  
    auto res = [&] () -> SSATmp* {
      switch (inst->op()) {
  #define X(x) case x: return simplify##x(env, inst);
        X(Shl)
        X(Shr)
        X(Lshr)
        X(AbsDbl)
        X(AssertNonNull)
        X(CallBuiltin)
        X(Ceil)
        X(CheckInit)
        X(CheckInitMem)
        X(CheckRDSInitialized)
        X(MarkRDSInitialized)
        X(MarkRDSAccess)
        X(CheckLoc)
        X(CheckMBase)
        X(CheckStk)
        X(CheckType)
        X(CheckTypeMem)
        X(AssertType)
        X(CheckNonNull)
        X(CheckVecBounds)
        X(ReserveVecNewElem)
        X(ConcatStrStr)
        X(ConcatStr3)
        X(ConcatStr4)
        X(ConcatIntStr)
        X(ConcatStrInt)
        X(ConvBoolToDbl)
        X(ConvBoolToInt)
        X(ConvTVToBool)
        X(ConvTVToDbl)
        X(ConvTVToInt)
        X(ConvTVToStr)
        X(ConvDblToBool)
        X(ConvDblToInt)
        X(ConvDblToStr)
        X(ConvIntToBool)
        X(ConvIntToDbl)
        X(ConvIntToStr)
        X(ConvObjToBool)
        X(ConvStrToBool)
        X(ConvStrToDbl)
        X(ConvStrToInt)
        X(ConvArrLikeToVec)
        X(ConvArrLikeToDict)
        X(ConvArrLikeToKeyset)
        X(DblAsBits)
        X(Count)
        X(CountVec)
        X(CountDict)
        X(CountKeyset)
        X(DecRef)
        X(DecRefNZ)
        X(DefLabel)
        X(DivDbl)
        X(DivInt)
        X(EqFunc)
        X(ExtendsClass)
        X(InstanceOfBitmask)
        X(NInstanceOfBitmask)
        X(Floor)
        X(IncRef)
        X(InitObjProps)
        X(InitObjMemoSlots)
        X(InstanceOf)
        X(InstanceOfIface)
        X(InstanceOfIfaceVtable)
        X(IsNType)
        X(IsType)
        X(IsLegacyArrLike)
        X(IsWaitHandle)
        X(IsCol)
        X(HasToString)
        X(HasReifiedGenerics)
        X(LdCls)
        X(LdClsName)
        X(LdLazyCls)
        X(LdLazyClsName)
        X(LdWHResult)
        X(LdWHState)
        X(LdWHNotDone)
        X(LookupClsRDS)
        X(LookupSPropSlot)
        X(LdClsMethod)
        X(LdStrLen)
        X(BespokeGet)
        X(BespokeUnset)
        X(BespokeGetThrow)
        X(StructDictSlot)
        X(BespokeIterFirstPos)
        X(BespokeIterLastPos)
        X(BespokeIterEnd)
        X(BespokeIterGetKey)
        X(BespokeIterGetVal)
        X(LdMonotypeDictTombstones)
        X(LdMonotypeDictKey)
        X(LdMonotypeDictVal)
        X(LdMonotypeVecElem)
        X(LdVecElem)
        X(MethodExists)
        X(LdFuncInOutBits)
        X(LdFuncNumParams)
        X(FuncHasAttr)
        X(ClassHasAttr)
        X(LdFuncRequiredCoeffects)
        X(LookupClsCtxCns)
        X(LdObjClass)
        X(LdObjInvoke)
        X(Mov)
        X(Jmp)
        X(JmpZero)
        X(JmpNZero)
        X(Select)
        X(OrInt)
        X(AddInt)
        X(SubInt)
        X(MulInt)
        X(AddDbl)
        X(SubDbl)
        X(MulDbl)
        X(Mod)
        X(AndInt)
        X(XorInt)
        X(XorBool)
        X(AddIntO)
        X(SubIntO)
        X(MulIntO)
        X(GtBool)
        X(GteBool)
        X(LtBool)
        X(LteBool)
        X(EqBool)
        X(NeqBool)
        X(CmpBool)
        X(GtInt)
        X(GteInt)
        X(LtInt)
        X(LteInt)
        X(EqInt)
        X(NeqInt)
        X(CmpInt)
        X(GtDbl)
        X(GteDbl)
        X(LtDbl)
        X(LteDbl)
        X(EqDbl)
        X(NeqDbl)
        X(CmpDbl)
        X(GtStr)
        X(GteStr)
        X(LtStr)
        X(LteStr)
        X(EqStr)
        X(NeqStr)
        X(SameStr)
        X(NSameStr)
        X(CmpStr)
        X(GtObj)
        X(GteObj)
        X(LtObj)
        X(LteObj)
        X(EqObj)
        X(NeqObj)
        X(SameObj)
        X(NSameObj)
        X(GtArrLike)
        X(GteArrLike)
        X(LtArrLike)
        X(LteArrLike)
        X(EqArrLike)
        X(NeqArrLike)
        X(SameArrLike)
        X(NSameArrLike)
        X(GtRes)
        X(GteRes)
        X(LtRes)
        X(LteRes)
        X(EqRes)
        X(NeqRes)
        X(CmpRes)
        X(EqCls)
        X(EqLazyCls)
        X(EqStrPtr)
        X(EqArrayDataPtr)
        X(DictGet)
        X(DictGetQuiet)
        X(DictGetK)
        X(KeysetGet)
        X(KeysetGetQuiet)
        X(KeysetGetK)
        X(GetDictPtrIter)
        X(CheckDictKeys)
        X(CheckDictOffset)
        X(CheckKeysetOffset)
        X(CheckArrayCOW)
        X(CheckMissingKeyInArrLike)
        X(DictIsset)
        X(KeysetIsset)
        X(DictIdx)
        X(AKExistsDict)
        X(KeysetIdx)
        X(AKExistsKeyset)
        X(OrdStr)
        X(ChrInt)
        X(JmpSwitchDest)
        X(CheckRange)
        X(GetMemoKey)
        X(GetMemoKeyScalar)
        X(StrictlyIntegerConv)
        X(RaiseErrorOnInvalidIsAsExpressionType)
        X(LdFrameCls)
        X(NewClsMeth)
        X(CheckClsMethFunc)
        X(LdClsFromClsMeth)
        X(LdFuncFromClsMeth)
        X(LdResolvedTypeCns)
        X(LdResolvedTypeCnsNoCheck)
        X(LdResolvedTypeCnsClsName)
        X(CGetPropQ)
        X(StructDictTypeBoundCheck)
  #undef X
        default: break;
      }
      return nullptr;
    }();
  
    // If the new instruction list is empty, we are either returning a known
    // value (res != nullptr), or leaving the instruction unchanged (res ==
    // nullptr). We should mark the instruction as unreachable if the known value
    // is Bottom. Cases where the new final instruction is a block-ending
    // instruction are handled by consumers.
  
    if (inst->hasDst() && !inst->naryDst() && env.newInsts.empty()) {
      if (res && res->type() == TBottom) {
        // The instruction has been simplified away, leaving only a bottom
        // constant. Mark it as unreachable.
        gen(env, Unreachable, ASSERT_REASON);
      } else if (!res && outputType(inst) == TBottom && !inst->isBlockEnd()) {
        // The instruction is passing through unchanged, but is known to have a
        // bottom result. Replace it with the proper unreachable annotations.
        res = cns(env, TBottom);
        gen(env, Unreachable, ASSERT_REASON);
      }
    }
  
    return res;
  }
  
  Block* unreachableBlock(IRUnit& unit, BCContext ctx) {
    auto const unreachableBlock = unit.defBlock(1, Block::Hint::Unused);
    makeInstruction(
      [&] (IRInstruction* inst) -> void {
        unreachableBlock->push_back(unit.clone(inst));
      },
      Unreachable,
      ctx,
      ASSERT_REASON
    );
    return unreachableBlock;
  }
  
  //////////////////////////////////////////////////////////////////////
  
  }
  
  ///////////////////////////////////////////////////////////////////////////////
  
  SimplifyResult simplify(IRUnit& unit, const IRInstruction* origInst) {
    auto env = State { unit };
  
    auto const newDst = simplifyWork(env, origInst);
  
    assertx(validate(env, newDst, origInst));
  
    return SimplifyResult { std::move(env.newInsts), newDst };
  }
  
  void simplifyInPlace(IRUnit& unit, IRInstruction* origInst) {
    assertx(!origInst->isTransient());
  
    copyProp(origInst);
    constProp(unit, origInst);
    retypeDests(origInst, &unit);
    auto res = simplify(unit, origInst);
  
    // No simplification occurred; nothing to do.
    if (res.instrs.empty() && !res.dst) {
      // If we have narrowed the result of a block end instruction to a bottom
      // type, its next block must be unreachable.
      if (origInst->isNextEdgeUnreachable() && origInst->isBlockEnd()) {
        origInst->setNext(unreachableBlock(unit, origInst->bcctx()));
      }
      return;
    }
  
    FTRACE(1, "simplifying: {}\n", origInst->toString());
  
    if (origInst->isBlockEnd()) {
      auto const next = origInst->block()->next();
  
      if (res.instrs.empty() || !res.instrs.back()->isBlockEnd()) {
        // Our block-end instruction was eliminated (most likely a Jmp* converted
        // to a Nop).  Replace it with a Jmp to the next block.
        res.instrs.push_back(unit.gen(Jmp, origInst->bcctx(), next));
      }
  
      auto const last = res.instrs.back();
      assertx(last->isBlockEnd());
  
      if (!last->isTerminal() && !last->next()) {
        // We converted the block-end instruction to a different one.  Set its
        // next block appropriately.
        last->setNext(next);
      }
    }
  
    size_t out_size = 0;
    bool need_mov = res.dst;
    IRInstruction* last = nullptr;
  
    for (auto const inst : res.instrs) {
      if (inst->is(Nop)) continue;
  
      ++out_size;
      last = inst;
  
      if (res.dst && res.dst == inst->dst()) {
        // One of the new instructions produced the new dst.  Since we're going
        // to drop `origInst', just use origInst->dst() instead.
        inst->setDst(origInst->dst());
        inst->dst()->setInstruction(inst);
        need_mov = false;
      }
    }
  
    auto const block = origInst->block();
    auto pos = ++block->iteratorTo(origInst);
  
    if (last != nullptr && last->isTerminal()) {
      // Delete remaining instructions in the block if a terminal is created.
      // This can happen, e.g., 'Unreachable' may be created when the block is
      // unreachable.
      while (pos != block->end()) pos = block->erase(pos);
    }
  
    // If the last instruction is block-ending and produces a Bottom result, its
    // next block should be unreachable.
    if (last != nullptr && last->isNextEdgeUnreachable() && last->isBlockEnd()) {
      last->setNext(unreachableBlock(unit, last->bcctx()));
    }
  
    if (need_mov) {
      /*
       * In `killed_edge_defining' we have the case that an instruction defining
       * a temp on an edge (like CheckType) determined it can never define that
       * tmp.  In this situation we just Nop out the instruction and leave the
       * old tmp dangling.  The reason this is ok is that one of the following
       * two things are happening:
       *
       *    o The old next() block is becoming unreachable.  It's ok not to make
       *      a new definition of this tmp, because the code running simplify is
       *      going to have to track unreachable blocks and avoid looking at
       *      them.  It will also have to remove unreachable blocks when it's
       *      finished to maintain IR invariants (e.g. through DCE::Minimal),
       *      which will mean the uses of the no-longer-defined tmp will go away.
       *
       *    o The old next() block is still reachable (e.g. if we're removing a
       *      CheckType because it had next == taken).  But in this case, the
       *      next() edge must have been a critical edge, and therefore nothing
       *      could have any use of the old destination of the CheckType, or the
       *      program would already not have been in SSA, because it was only
       *      defined in blocks dominated by the next edge.
       */
      auto const killed_edge_defining = res.dst->type() <= TBottom &&
        origInst->isBlockEnd();
      if (killed_edge_defining) {
        origInst->convertToNop();
      } else {
        unit.replace(origInst, Mov, res.dst);
        // Force the existing dst type to match that of `res.dst'.
        origInst->dst()->setType(res.dst->type());
      }
    } else {
      if (out_size == 1) {
        assertx(origInst->dst() == last->dst());
        FTRACE(1, "    {}\n", last->toString());
  
        // We only have a single instruction, so just become it.
        origInst->become(unit, last);
  
        // Make sure to reset our dst's inst pointer, if we have one.  (It may
        // have been set to `last'.
        if (origInst->dst()) {
          origInst->dst()->setInstruction(origInst);
        }
  
        // And we also need to kill `last', to update preds.
        last->convertToNop();
        return;
      }
  
      origInst->convertToNop();
    }
  
    FTRACE(1, "    {}\n", origInst->toString());
  
    for (auto const inst : res.instrs) {
      if (inst->is(Nop)) continue;
      block->insert(pos, inst);
      FTRACE(1, "    {}\n", inst->toString());
    }
  }
  
  ////////////////////////////////////////////////////////////////////////////////
  
  void simplifyPass(IRUnit& unit) {
    Timer timer{Timer::optimize_simplify, unit.logEntry().get_pointer()};
  
    auto reachable = boost::dynamic_bitset<>(unit.numBlocks());
    reachable.set(unit.entry()->id());
  
    auto const sortedBlocks = rpoSortCfg(unit);
    for (auto block : sortedBlocks) {
      if (!reachable.test(block->id())) continue;
  
      if (!block->isUnreachable()) {
        for (auto& inst : *block) simplifyInPlace(unit, &inst);
      }
  
      if (auto const b = block->next()) {
        if (!b->isUnreachable()) reachable.set(b->id());
      }
      if (auto const b = block->taken()) {
        if (!b->isUnreachable()) reachable.set(b->id());
      }
    }
  
    auto const markUnreachable = [&] (Block* block) {
      // Any code that's postdominated by Unreachable is also unreachable, so
      // erase everything else in this block.
      if (block->back().hasDst()) block->back().setDst(nullptr);
      unit.replace(&block->back(), Unreachable, ASSERT_REASON);
      for (auto it = block->skipHeader(), end = block->backIter(); it != end;) {
        auto toErase = it;
        ++it;
        block->erase(toErase);
      }
    };
  
    // We may have introduced new unreachable blocks.
    if (unit.numBlocks() > reachable.size()) reachable.resize(unit.numBlocks());
  
    auto const poBlocks = poSortCfg(unit);
    // Collapse unreachable blocks
    std::deque<Block*> workQ(poBlocks.cbegin(), poBlocks.cend());
    while (!workQ.empty()) {
      auto const block = workQ.front();
      workQ.pop_front();
      if (!reachable.test(block->id())) continue;
  
      auto& inst = block->back();
      if (inst.hasEdges() &&
          (!inst.next() || !reachable.test(inst.next()->id())) &&
          (!inst.taken() || !reachable.test(inst.taken()->id()))) {
        auto const& preds = block->preds();
        for (auto const& pred : preds) workQ.push_back(pred.from());
        markUnreachable(block);
      }
    }
  }
  
  ////////////////////////////////////////////////////////////////////////////////
  
  }}
  