Rename ArrayOffset -> ArrayAccess

[hiphop-php.git] / hphp / runtime / vm / jit / memory-effects.cpp

/*
   +----------------------------------------------------------------------+
   | 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/memory-effects.h"

#include "hphp/util/match.h"
#include "hphp/util/safe-cast.h"
#include "hphp/util/assertions.h"

#include "hphp/runtime/vm/bytecode.h"
#include "hphp/runtime/vm/jit/analysis.h"
#include "hphp/runtime/vm/jit/dce.h"
#include "hphp/runtime/vm/jit/ir-instruction.h"
#include "hphp/runtime/vm/jit/ssa-tmp.h"

#include <folly/Optional.h>

namespace HPHP { namespace jit {

namespace {

AliasClass pointee(
  const SSATmp* ptr,
  jit::flat_set<const IRInstruction*>* visited_labels
) {
  auto const type = ptr->type();
  always_assert(type <= TMemToGen);
  auto const maybeRef = type.maybe(TMemToRefGen);
  auto const typeNR = type - TMemToRefGen;
  auto const canonPtr = canonical(ptr);
  if (!canonPtr->isA(TMemToGen)) {
    // This can happen when ptr is TBottom from a passthrough instruction with
    // a src that isn't TBottom. The most common cause of this is something
    // like "t5:Bottom = CheckType<Str> t2:Int". It means ptr isn't really a
    // pointer, so return AEmpty to avoid unnecessarily pessimizing any
    // optimizations.
    always_assert(ptr->isA(TBottom));
    return AEmpty;
  }

  auto const sinst = canonPtr->inst();

  if (sinst->is(UnboxPtr)) {
    return ARefAny | pointee(sinst->src(0), visited_labels);
  }

  if (sinst->is(LdRDSAddr, LdInitRDSAddr)) {
    return ARds { sinst->extra<RDSHandleData>()->handle };
  }

  // For phis, union all incoming values, taking care to not recurse infinitely
  // in the presence of loops.
  if (sinst->is(DefLabel)) {
    if (visited_labels && visited_labels->count(sinst)) {
      return AEmpty;
    }

    auto const dsts = sinst->dsts();
    auto const dstIdx =
      std::find(dsts.begin(), dsts.end(), canonPtr) - dsts.begin();
    always_assert(dstIdx >= 0 && dstIdx < sinst->numDsts());

    folly::Optional<jit::flat_set<const IRInstruction*>> label_set;
    if (visited_labels == nullptr) {
      label_set.emplace();
      visited_labels = &label_set.value();
    }
    visited_labels->insert(sinst);

    auto ret = AEmpty;
    sinst->block()->forEachSrc(
      dstIdx, [&](const IRInstruction* /*jmp*/, const SSATmp* thePtr) {
        ret = ret | pointee(thePtr, visited_labels);
      });
    return ret;
  }

  auto specific = [&] () -> folly::Optional<AliasClass> {
    if (typeNR <= TBottom) return AEmpty;

    if (typeNR <= TMemToFrameGen) {
      if (sinst->is(LdLocAddr)) {
        return AliasClass {
          AFrame { sinst->src(0), sinst->extra<LdLocAddr>()->locId }
        };
      }
      return AFrameAny;
    }

    if (typeNR <= TMemToStkGen) {
      if (sinst->is(LdStkAddr)) {
        return AliasClass {
          AStack { sinst->src(0), sinst->extra<LdStkAddr>()->offset, 1 }
        };
      }
      return AStackAny;
    }

    if (typeNR <= TMemToPropGen) {
      if (sinst->is(LdPropAddr, LdInitPropAddr)) {
        return AliasClass {
          AProp {
            sinst->src(0),
            safe_cast<uint32_t>(sinst->extra<ByteOffsetData>()->offsetBytes)
          }
        };
      }
      return APropAny;
    }

    if (typeNR <= TMemToMISGen) {
      if (sinst->is(LdMIStateAddr)) {
        return mis_from_offset(sinst->src(0)->intVal());
      }
      if (ptr->hasConstVal() && ptr->rawVal() == 0) {
        // nullptr tvRef pointer, representing an instruction that doesn't use
        // it.
        return AEmpty;
      }
      return AMIStateTV;
    }

    auto elem = [&] () -> AliasClass {
      auto base = sinst->src(0);
      auto key  = sinst->src(1);

      always_assert(base->isA(TArrLike));

      if (key->isA(TInt)) {
        if (key->hasConstVal()) return AElemI { base, key->intVal() };
        return AElemIAny;
      }
      if (key->hasConstVal(TStr)) {
        assertx(!base->isA(TVec));
        return AElemS { base, key->strVal() };
      }
      return AElemAny;
    };

    if (typeNR <= TMemToElemGen) {
      if (sinst->is(LdPackedArrayDataElemAddr)) return elem();
      return AElemAny;
    }

    // The result of ElemArray{,W,U} is either the address of an array element,
    // or &immutable_null_base.
    if (typeNR <= TMemToMembGen) {
      if (sinst->is(ElemArrayX, ElemDictX, ElemKeysetX)) return elem();

      // Takes a PtrToGen as its first operand, so we can't easily grab an array
      // base.
      if (sinst->is(ElemArrayU, ElemVecU, ElemDictU, ElemKeysetU)) {
        return AElemAny;
      }

      // These instructions can only get at tvRef when given it as a
      // src. Otherwise they can only return pointers to properties or
      // &immutable_null_base.
      if (sinst->is(PropX, PropDX, PropQ)) {
        auto const src = [&]{
          if (sinst->is(PropDX)) {
            assertx(sinst->src(sinst->numSrcs() - 2)->isA(TMemToMISGen));
            assertx(
              sinst->src(sinst->numSrcs() - 1)->isA(TMIPropSPtr | TNullptr)
            );
            return sinst->src(sinst->numSrcs() - 2);
          } else {
            assertx(sinst->srcs().back()->isA(TPtrToMISGen));
            return sinst->srcs().back();
          }
        }();
        return APropAny | pointee(src, visited_labels);
      }

      // Like the Prop* instructions, but for array elements. These could also
      // return pointers to collection elements but those don't exist in
      // AliasClass yet.
      if (sinst->is(ElemX, ElemDX, ElemUX)) {
        auto const src = [&]{
          if (sinst->is(ElemDX)) {
            assertx(sinst->src(sinst->numSrcs() - 2)->isA(TMemToMISGen));
            assertx(
              sinst->src(sinst->numSrcs() - 1)->isA(TMIPropSPtr | TNullptr)
            );
            return sinst->src(sinst->numSrcs() - 2);
          } else {
            assertx(sinst->srcs().back()->isA(TPtrToMISGen));
            return sinst->srcs().back();
          }
        }();
        return AElemAny | pointee(src, visited_labels);
      }

      return folly::none;
    }

    return folly::none;
  }();

  auto ret = maybeRef ? ARefAny : AEmpty;
  if (specific) return *specific | ret;

  /*
   * None of the above worked, so try to make the smallest union we can based
   * on the pointer type.
   */
  if (typeNR.maybe(TMemToStkGen))     ret = ret | AStackAny;
  if (typeNR.maybe(TMemToFrameGen))   ret = ret | AFrameAny;
  if (typeNR.maybe(TMemToPropGen))    ret = ret | APropAny;
  if (typeNR.maybe(TMemToElemGen))    ret = ret | AElemAny;
  if (typeNR.maybe(TMemToMISGen))     ret = ret | AMIStateTV;
  if (typeNR.maybe(TMemToClsInitGen)) ret = ret | AHeapAny;
  if (typeNR.maybe(TMemToClsCnsGen))  ret = ret | AHeapAny;
  if (typeNR.maybe(TMemToSPropGen))   ret = ret | ARdsAny;
  return ret;
}

//////////////////////////////////////////////////////////////////////

AliasClass all_pointees(folly::Range<SSATmp**> srcs) {
  auto ret = AliasClass{AEmpty};
  for (auto const& src : srcs) {
    if (src->isA(TMemToGen)) {
      ret = ret | pointee(src);
    }
  }
  return ret;
}

// Return an AliasClass containing all locations pointed to by any MemToGen
// sources to an instruction.
AliasClass all_pointees(const IRInstruction& inst) {
  return all_pointees(inst.srcs());
}

// Return an AliasClass representing a range of the eval stack that contains
// everything below a logical depth.
template<typename Off>
AliasClass stack_below(SSATmp* base, Off offset) {
  return AStack { base, offset, std::numeric_limits<int32_t>::max() };
}

//////////////////////////////////////////////////////////////////////

/*
 * Helper functions for alias classes representing an ActRec on the stack
 * (whether pre-live or live).
 */

// Return an AliasClass representing an entire ActRec at base + offset.
AliasClass actrec(SSATmp* base, IRSPRelOffset offset) {
  return AStack {
    base,
    // The offset is the bottom of where the ActRec is stored, but AliasClass
    // needs an offset to the highest cell.
    offset + int32_t{kNumActRecCells} - 1,
    int32_t{kNumActRecCells}
  };
}

// Return an AliasClass representing just the context field of an ActRec at base
// + offset.
AliasClass actrec_ctx(SSATmp* base, IRSPRelOffset offset) {
  return AStack { base, offset + int32_t{kActRecCtxCellOff}, 1 };
}

// Return AliasClass representing just the func field of an ActRec at base +
// offset.
AliasClass actrec_func(SSATmp* base, IRSPRelOffset offset) {
  return AStack { base, offset + int32_t{kActRecFuncCellOff}, 1 };
}

InlineExitEffects inline_exit_effects(SSATmp* fp) {
  fp = canonical(fp);
  auto fpInst = fp->inst();
  if (UNLIKELY(fpInst->is(DefLabel))) fpInst = resolveFpDefLabel(fp);
  assertx(fpInst && fpInst->is(DefInlineFP));
  auto const func = fpInst->extra<DefInlineFP>()->target;
  auto const frame = [&] () -> AliasClass {
    if (!func->numLocals()) return AEmpty;
    return AFrame {fp, AliasIdSet::IdRange(0, func->numLocals())};
  }();
  auto const stack = stack_below(fp, FPRelOffset{2});
  AliasClass clsref = func->numClsRefSlots() ? AClsRefSlotAny : AEmpty;
  return InlineExitEffects{ stack, frame, clsref | AMIStateAny };
}

//////////////////////////////////////////////////////////////////////

// Determine an AliasClass representing any locals in the instruction's frame
// which might be accessed via debug_backtrace().

AliasClass backtrace_locals(const IRInstruction& inst) {
  auto const func = [&]() -> const Func* {
    auto fp = inst.marker().fp();
    if (!fp) return nullptr;
    fp = canonical(fp);
    auto fpInst = fp->inst();
    if (UNLIKELY(fpInst->is(DefLabel))) {
      fpInst = resolveFpDefLabel(fp);
      assertx(fpInst);
    }
    if (fpInst->is(DefFP)) return fpInst->marker().func();
    if (fpInst->is(DefInlineFP)) return fpInst->extra<DefInlineFP>()->target;
    always_assert(false);
  }();

  // Either there's no func or no frame-pointer. Either way, be conservative and
  // assume anything can be read. This can happen in test code, for instance.
  if (!func) return AFrameAny;

  auto const add86meta = [&] (AliasClass ac) {
    // The 86metadata variable can also exist in a VarEnv, but accessing that is
    // considered a heap effect, so we can ignore it.
    auto const local = func->lookupVarId(s_86metadata.get());
    if (local == kInvalidId) return ac;
    return ac | AFrame { inst.marker().fp(), (uint32_t)local };
  };

  auto ac = AEmpty;
  auto const numParams = func->numParams();

  if (!RuntimeOption::EnableArgsInBacktraces) return add86meta(ac);

  if (func->hasReifiedGenerics()) {
    // First non param local contains reified generics
    AliasIdSet reifiedgenerics{ AliasIdSet::IdRange{numParams, numParams + 1} };
    ac |= AFrame { inst.marker().fp(), reifiedgenerics };
  }

  if (func->cls() && func->cls()->hasReifiedGenerics()) {
    // There is no way to access the SSATmp for ObjectData of `this` here,
    // so be very pessimistic
    ac |= APropAny;
  }

  if (!numParams) return add86meta(ac);

  AliasIdSet params{ AliasIdSet::IdRange{0, numParams} };
  return add86meta(ac | AFrame { inst.marker().fp(), params });
}

/////////////////////////////////////////////////////////////////////

/*
 * Modify a GeneralEffects to take potential VM re-entry into account.  This
 * affects may-load, may-store, and kills information for the instruction.  The
 * GeneralEffects should already contain AHeapAny in both loads and stores if
 * it affects those locations for reasons other than re-entry, but does not
 * need to if it doesn't.
 *
 * For loads, we need to take into account any locals potentially accessed by
 * debug_backtrace().
 *
 * For kills, locations on the eval stack below the re-entry depth should all
 * be added.
 *
 * Important note: because of the `kills' set modifications, an instruction may
 * not report that it can re-enter if it actually can't.  The reason this can
 * go wrong is that if the instruction was in an inlined function, if we've
 * removed the DefInlineFP its spOff will not be meaningful (unless it's a
 * DecRef instruction, which we explicitly adjust in dce.cpp).  In this case
 * the `kills' set will refer to the wrong stack locations.  In general this
 * means instructions that can re-enter must have catch traces---but a few
 * other instructions are exceptions, either since they are not allowed in
 * inlined functions or because they take the (possibly-inlined) FramePtr as a
 * source.
 */
GeneralEffects may_reenter(const IRInstruction& inst, GeneralEffects x) {
  auto const may_reenter_is_ok =
    (inst.taken() && inst.taken()->isCatch()) ||
    inst.is(DecRef,
            ReleaseVVAndSkip,
            LIterInit,
            LIterInitK,
            LIterNext,
            LIterNextK,
            IterFree,
            GenericRetDecRefs,
            MemoSetStaticCache,
            MemoSetLSBCache,
            MemoSetInstanceCache,
            MemoSetStaticValue,
            MemoSetLSBValue,
            MemoSetInstanceValue);
  always_assert_flog(
    may_reenter_is_ok,
    "instruction {} claimed may_reenter, but it isn't allowed to say that",
    inst
  );

  /*
   * We want to union `killed_stack' into whatever else the instruction already
   * said it must kill, but if we end up with an unrepresentable AliasClass we
   * can't return a set that's too big (the `kills' set is unlike the other
   * AliasClasses in GeneralEffects in that means it kills /everything/ in the
   * set, since it's must-information).
   *
   * If we can't represent the union, just take the stack, in part because we
   * have some debugging asserts about this right now---but also nothing
   * actually uses may_reenter with a non-AEmpty kills at the time of this
   * writing anyway.
   */
  auto const new_kills = [&] {
    if (inst.marker().fp() == nullptr) return AEmpty;

    auto const killed_stack = stack_below(
      inst.marker().fp(),
      -inst.marker().spOff() - 1
    );
    auto const kills_union = x.kills.precise_union(killed_stack);
    return kills_union ? *kills_union : killed_stack;
  }();

  return GeneralEffects {
    x.loads | AHeapAny | backtrace_locals(inst),
    x.stores | AHeapAny,
    x.moves,
    new_kills
  };
}

//////////////////////////////////////////////////////////////////////

GeneralEffects may_load_store(AliasClass loads, AliasClass stores) {
  return GeneralEffects { loads, stores, AEmpty, AEmpty };
}

GeneralEffects may_load_store_kill(AliasClass loads,
                                   AliasClass stores,
                                   AliasClass kill) {
  return GeneralEffects { loads, stores, AEmpty, kill };
}

GeneralEffects may_load_store_move(AliasClass loads,
                                   AliasClass stores,
                                   AliasClass move) {
  assertx(move <= loads);
  return GeneralEffects { loads, stores, move, AEmpty };
}

//////////////////////////////////////////////////////////////////////

/*
 * Helper for iterator instructions.  They all affect some locals, but are
 * otherwise the same.
 *
 * N.B. Currently the memory for frame iterator slots is not part of the
 * AliasClass lattice, since we never really manipulate them from the TC yet,
 * so we don't report the effect these instructions have on it.
 */
GeneralEffects iter_effects(const IRInstruction& inst,
                            SSATmp* fp,
                            AliasClass locals) {
  auto const iterID = inst.extra<IterData>()->iterId;
  AliasClass const iterPos = AIterPos { fp, iterID };
  AliasClass const iterBase = AIterBase { fp, iterID };
  auto const iterMem = iterPos | iterBase;
  return may_reenter(
    inst,
    may_load_store_kill(
      locals | AHeapAny | iterMem,
      locals | AHeapAny | iterMem,
      AMIStateAny
    )
  );
}

/*
 * Construct effects for InterpOne, using the information in its extra data.
 *
 * We always consider an InterpOne as potentially doing anything to the heap,
 * potentially re-entering, potentially raising warnings in the current frame,
 * potentially reading any locals, and potentially reading/writing any stack
 * location that isn't below the bottom of the stack.
 *
 * The extra data for the InterpOne comes with some additional information
 * about which local(s) it may modify, which is all we try to be more precise
 * about right now.
 */
GeneralEffects interp_one_effects(const IRInstruction& inst) {
  auto const extra  = inst.extra<InterpOne>();
  auto loads  = AHeapAny | AStackAny | AFrameAny | ARdsAny;
  auto stores = AHeapAny | AStackAny | ARdsAny;
  if (extra->smashesAllLocals) {
    stores = stores | AFrameAny;
  } else {
    for (auto i = uint32_t{0}; i < extra->nChangedLocals; ++i) {
      stores = stores | AFrame { inst.src(1), extra->changedLocals[i].id };
    }
  }

  for (auto i = uint32_t{0}; i < extra->nChangedClsRefSlots; ++i) {
    auto const& slot = extra->changedClsRefSlots[i];
    if (slot.write) {
      stores = stores | AClsRefClsSlot { inst.src(1), slot.id } |
               AClsRefTSSlot { inst.src(1), slot.id };
    } else {
      loads = loads | AClsRefClsSlot { inst.src(1), slot.id } |
              AClsRefTSSlot { inst.src(1), slot.id };
    }
  }

  auto kills = AEmpty;
  if (isMemberBaseOp(extra->opcode)) {
    stores = stores | AMIStateAny;
    kills = kills | AMIStateAny;
  } else if (isMemberDimOp(extra->opcode) || isMemberFinalOp(extra->opcode)) {
    stores = stores | AMIStateAny;
    loads = loads | AMIStateAny;
  } else {
    kills = kills | AMIStateAny;
  }

  return may_load_store_kill(loads, stores, kills);
}

////////////////////////////////////////////////////////////////////////////////

/*
 * Construct effects for member instructions that take &tvRef as their last
 * argument.
 *
 * These instructions never load tvRef, but they might store to it.
 */
MemEffects minstr_with_tvref(const IRInstruction& inst) {
  auto loads = AHeapAny;
  auto stores = AHeapAny | all_pointees(inst);
  auto kills = AEmpty;

  auto const srcs = inst.srcs();
  if (inst.is(ElemDX, PropDX)) {
    assertx(inst.src(inst.numSrcs() - 2)->isA(TMemToMISGen));
    assertx(inst.src(inst.numSrcs() - 1)->isA(TMIPropSPtr | TNullptr));
    loads |= all_pointees(srcs.subpiece(0, srcs.size() - 2));

    auto const propPtr = inst.src(inst.numSrcs() - 1);
    if (RuntimeOption::EvalCheckPropTypeHints <= 0 || propPtr->isA(TNullptr)) {
      kills = AMIStatePropS;
    } else if (inst.is(ElemDX)) {
      loads |= AMIStatePropS;
    } else {
      assertx(inst.is(PropDX));
      if (RuntimeOption::EvalPromoteEmptyObject) loads |= AMIStatePropS;
      stores |= AMIStatePropS;
    }
  } else {
    assertx(srcs.back()->isA(TMemToMISGen));
    loads |= all_pointees(srcs.subpiece(0, srcs.size() - 1));
    kills = AMIStatePropS;
  }

  return may_load_store_kill(loads, stores, kills);
}

//////////////////////////////////////////////////////////////////////

MemEffects minstr_final_with_prop_state(const IRInstruction& inst) {
  auto const propSLoads = [&]{
    auto const propPtr = inst.srcs().back();
    assertx(propPtr->isA(TMIPropSPtr | TNullptr));
    if (RuntimeOption::EvalCheckPropTypeHints <= 0) return AEmpty;
    if (propPtr->isA(TNullptr)) return AEmpty;
    if (!RuntimeOption::EvalPromoteEmptyObject &&
        inst.is(IncDecProp, SetOpProp, SetProp)) {
      return AEmpty;
    }
    return AMIStatePropS;
  }();

  return may_load_store_kill(
    AHeapAny | propSLoads | all_pointees(inst),
    AHeapAny | all_pointees(inst),
    AMIStatePropS
  );
}

//////////////////////////////////////////////////////////////////////

MemEffects memory_effects_impl(const IRInstruction& inst) {
  switch (inst.op()) {

  //////////////////////////////////////////////////////////////////////
  // Region exits

  // These exits don't leave the current php function, and could head to code
  // that could read or write anything as far as we know (including frame
  // locals).
  case ReqBindJmp:
    return ExitEffects {
      AUnknown,
      stack_below(inst.src(0), inst.extra<ReqBindJmp>()->irSPOff - 1)
    };
  case ReqRetranslate:
    return ExitEffects {
      AUnknown,
      stack_below(inst.src(0), inst.extra<ReqRetranslate>()->irSPOff - 1)
    };
  case ReqRetranslateOpt:
    return ExitEffects {
      AUnknown,
      stack_below(inst.src(0), inst.extra<ReqRetranslateOpt>()->offset - 1)
    };
  case JmpSwitchDest:
    return ExitEffects {
      AUnknown,
      *stack_below(inst.src(1),
                   inst.extra<JmpSwitchDest>()->spOffBCFromIRSP - 1).
        precise_union(AMIStateAny)
    };
  case JmpSSwitchDest:
    return ExitEffects {
      AUnknown,
      *stack_below(inst.src(1),
                   inst.extra<JmpSSwitchDest>()->offset - 1).
        precise_union(AMIStateAny)
    };

  //////////////////////////////////////////////////////////////////////
  // Unusual instructions

  /*
   * The ReturnHook sets up the ActRec so the unwinder knows everything is
   * already released (i.e. it calls ar->setLocalsDecRefd()).
   *
   * The eval stack is also dead at this point (the return value is passed to
   * ReturnHook as src(1), and the ReturnHook may not access the stack).
   */
  case ReturnHook:
    // Note, this instruction can re-enter, but doesn't need the may_reenter()
    // treatmeant because of the special kill semantics for locals and stack.
    return may_load_store_kill(
      AHeapAny, AHeapAny,
      *AStackAny.precise_union(AFrameAny)->precise_union(AMIStateAny)
    );

  // The suspend hooks can load anything (re-entering the VM), but can't write
  // to frame locals.
  case SuspendHookAwaitEF:
  case SuspendHookAwaitEG:
  case SuspendHookAwaitR:
  case SuspendHookCreateCont:
  case SuspendHookYield:
    // TODO: may-load here probably doesn't need to include AFrameAny normally.
    return may_reenter(inst,
                       may_load_store_kill(AUnknown, AHeapAny, AMIStateAny));

  /*
   * If we're returning from a function, it's ReturnEffects.  The RetCtrl
   * opcode also suspends resumables, which we model as having any possible
   * effects.
   */
  case RetCtrl:
    if (inst.extra<RetCtrl>()->suspendingResumed) {
      // Suspending can go anywhere, and doesn't even kill locals.
      return UnknownEffects {};
    }
    return ReturnEffects {
      AStackAny | AFrameAny | AClsRefSlotAny | AMIStateAny
    };

  case AsyncFuncRet:
  case AsyncFuncRetSlow:
    return ReturnEffects { AStackAny | AMIStateAny };

  case AsyncSwitchFast:
    // Suspending can go anywhere, and doesn't even kill locals.
    return UnknownEffects {};

  case GenericRetDecRefs:
    /*
     * The may-store information here is AUnknown: even though we know it
     * doesn't really "store" to the frame locals, the values that used to be
     * there are no longer available because they are DecRef'd, which we are
     * required to report as may-store information to make it visible to
     * reference count optimizations.  It's conceptually the same as if it was
     * storing an Uninit over each of the locals, but the stores of uninits
     * would be dead so we're not actually doing that.
     */
    return may_reenter(inst,
                       may_load_store_kill(AUnknown, AUnknown, AMIStateAny));

  case EndCatch: {
    auto const stack_kills = stack_below(
      inst.src(1),
      inst.extra<EndCatch>()->offset - 1
    );
    return ExitEffects {
      AUnknown,
      stack_kills | AMIStateTempBase | AMIStateBase | AMIStatePropS
    };
  }

  /*
   * DefInlineFP has some special treatment here.
   *
   * It's logically `publishing' a pointer to a pre-live ActRec, making it
   * live.  It doesn't actually load from this ActRec, but after it's done this
   * the set of things that can load from it is large enough that the easiest
   * way to model this is to consider it as a load on behalf of `publishing'
   * the ActRec.  Once it's published, it's a live activation record, and
   * doesn't get written to as if it were a stack slot anymore (we've
   * effectively converted AStack locations into a frame until the
   * InlineReturn).
   *
   * Note: We may push the publishing of the inline frame below the start of
   * the inline function so that we can avoid spilling the inline frame in the
   * common case. Because of this we cannot add the stack positions within the
   * inline function to the kill set here as they may be live having been stored
   * on the main trace.
   *
   * TODO(#3634984): Additionally, DefInlineFP is marking may-load on all the
   * locals of the outer frame.  This is probably not necessary anymore, but we
   * added it originally because a store sinking prototype needed to know it
   * can't push StLocs past a DefInlineFP, because of reserved registers.
   * Right now it's just here because we need to think about and test it before
   * removing that set.
   */
  case DefInlineFP: {
    auto const func = inst.extra<DefInlineFP>()->target;
    AliasClass stack = func->numLocals()
      ? AStack{inst.dst(), FPRelOffset{-1}, func->numLocals()}
      : AEmpty;
    AliasClass frame = func->numLocals()
      ? AFrame{inst.dst(), AliasIdSet::IdRange(0, func->numLocals())}
      : AEmpty;
    AliasClass clsrefs = func->numClsRefSlots() ? AClsRefSlotAny : AEmpty;
    /*
     * Notice that the stack positions and frame locals described here are
     * exactly the set of alias locations that are about to be overlapping
     * inside the inlined frame. Likewise, ClsRefSlots from the caller and the
     * callee are about to be jumbled.
     */
    return InlineEnterEffects{ stack, frame | clsrefs, inline_fp_frame(&inst) };
  }

  /*
   * BeginInlining is similar to DefInlineFP, however, it must always be the
   * first instruction in the inlined call and has no effect serving only as
   * a marker to memory effects that the stack cells within the inlined call
   * are now dead.
   *
   * Unlike DefInlineFP it does not load the SpillFrame, which we hope to push
   * off the main trace or elide entirely.
   */
  case BeginInlining: {
    /*
     * SP relative offset of the first non-frame cell within the inlined call.
     */
    auto inlineStackOff = inst.extra<BeginInlining>()->offset;
    return may_load_store_kill(
      AEmpty,
      AEmpty,
      /*
       * This prevents stack slots from the caller from being sunk into the
       * callee. Note that some of these stack slots overlap with the frame
       * locals of the callee-- those slots are inacessible in the inlined
       * call as frame and stack locations may not alias.
       */
      stack_below(inst.src(0), inlineStackOff)
    );
  }

  case InlineSuspend:
  case InlineReturn: {
    return inline_exit_effects(inst.src(0));
  }

  case InlineReturnNoFrame: {
    auto const callee = AliasClass(AStack {
      inst.extra<InlineReturnNoFrame>()->offset,
      std::numeric_limits<int32_t>::max()
    }) | AMIStateAny;
    return may_load_store_kill(AEmpty, AEmpty, callee);
  }

  case SyncReturnBC: {
    auto const spOffset = inst.extra<SyncReturnBC>()->spOffset;
    auto const arStack = actrec(inst.src(0), spOffset);
    // This instruction doesn't actually load but SpillFrame cannot be pushed
    // past it
    return may_load_store(arStack, arStack);
  }

  case InterpOne:
    return interp_one_effects(inst);
  case InterpOneCF:
    return ExitEffects {
      AUnknown,
      stack_below(inst.src(1), -inst.marker().spOff() - 1) | AMIStateAny
    };

  case NativeImpl:
    return UnknownEffects {};

  // NB: on the failure path, these C++ helpers do a fixup and read frame
  // locals before they throw.  They can also invoke the user error handler and
  // go do whatever they want to non-frame locations.
  //
  // TODO(#5372569): if we combine dv inits into the same regions we could
  // possibly avoid storing KindOfUninits if we modify this.
  case VerifyParamCallable:
  case VerifyParamCls:
  case VerifyParamFailHard:
    return may_load_store(AUnknown, AHeapAny);
  // VerifyParamFail might coerce the parameter to the desired type rather than
  // throwing.
  case VerifyParamFail: {
    auto const localId = inst.src(0)->intVal();
    assertx(localId >= 0);
    auto const stores =
      AHeapAny | AFrame{inst.marker().fp(), safe_cast<uint32_t>(localId)};
    return may_load_store(AUnknown, stores);
  }
  case VerifyReifiedLocalType: {
    auto const extra = inst.extra<ParamData>();
    assertx(extra->paramId >= 0);
    auto const stores =
      AHeapAny | AFrame{inst.marker().fp(),safe_cast<uint32_t>(extra->paramId)};
    return may_load_store(AUnknown, stores);
  }
  // However the following ones can't read locals from our frame on the way
  // out, except as a side effect of raising a warning.
  case VerifyRetCallable:
  case VerifyRetCls:
  case VerifyReifiedReturnType:
    return may_load_store(AHeapAny, AHeapAny);

  case VerifyRetFail:
  case VerifyRetFailHard:
    return may_load_store(AHeapAny | AStackAny, AHeapAny);

  case VerifyPropCls:
  case VerifyPropFail:
  case VerifyPropFailHard:
  case VerifyProp:
    return may_load_store(AHeapAny, AHeapAny);

  case CallUnpack:
    {
      auto const extra = inst.extra<CallUnpack>();
      return CallEffects {
        // Kills. Everything on the stack below the incoming parameters.
        stack_below(inst.src(0), extra->spOffset - 1) | AMIStateAny,
        // Stack. The act-rec, incoming parameters, and everything below.
        stack_below(
          inst.src(0),
          extra->spOffset + extra->numParams + kNumActRecCells +
          extra->numOut - 1
        ),
        // Locals.
        backtrace_locals(inst),
        // Callee.
        actrec_func(inst.src(0), extra->spOffset + extra->numParams)
      };
    }

  case ContEnter:
    {
      auto const extra = inst.extra<ContEnter>();
      return CallEffects {
        // Kills. Everything on the stack below the sent value.
        stack_below(inst.src(0), extra->spOffset - 1) | AMIStateAny,
        // Stack. The value being sent, and everything below.
        stack_below(inst.src(0), extra->spOffset),
        // Locals.
        backtrace_locals(inst),
        // Callee. Stored inside the generator object, not used by ContEnter.
        AEmpty
      };
    }

  case Call:
    {
      auto const extra = inst.extra<Call>();
      return CallEffects {
        // Kills. Everything on the stack below the incoming parameters.
        stack_below(inst.src(0), extra->spOffset - 1) | AMIStateAny,
        // Stack. The act-rec, incoming parameters, and everything below.
        stack_below(
          inst.src(0),
          extra->spOffset + extra->numParams + kNumActRecCells +
          extra->numOut - 1
        ),
        // Locals.
        backtrace_locals(inst),
        // Callee.
        actrec_func(inst.src(0), extra->spOffset + extra->numParams)
      };
    }

  case CallBuiltin:
    {
      auto const stk = [&] () -> AliasClass {
        AliasClass ret = AEmpty;
        for (auto i = uint32_t{2}; i < inst.numSrcs(); ++i) {
          if (inst.src(i)->type() <= TPtrToGen) {
            auto const cls = pointee(inst.src(i));
            if (cls.maybe(AStackAny)) {
              ret = ret | cls;
            }
          }
        }
        return ret;
      }();
      auto const callee = inst.extra<CallBuiltin>()->callee;
      if (callee->isFoldable()) {
        return may_load_store_kill(stk | AHeapAny, AHeapAny, AMIStateAny);
      } else {
        return may_load_store_kill(
          stk | AHeapAny | ARdsAny,
          AHeapAny | ARdsAny,
          AMIStateAny
        );
      }
    }

  // Resumable suspension takes everything from the frame and moves it into the
  // heap.
  case CreateGen:
  case CreateAGen:
  case CreateAFWH:
  case CreateAFWHNoVV: {
    auto const fp = canonical(inst.src(0));
    auto fpInst = fp->inst();
    if (fpInst->is(DefLabel)) fpInst = resolveFpDefLabel(fp);
    auto const frame = [&] () -> AliasClass {
      if (fpInst->is(DefFP)) return AFrameAny;
      assertx(fpInst->is(DefInlineFP));
      auto const nlocals = fpInst->extra<DefInlineFP>()->target->numLocals();
      return nlocals
        ? AFrame { fp, AliasIdSet::IdRange(0, nlocals)}
        : AEmpty;
    }();
    auto const clsrefs = [&] () -> AliasClass {
      if (fpInst->is(DefFP)) return AClsRefSlotAny;
      assertx(fpInst->is(DefInlineFP));
      auto const nrefs = fpInst->extra<DefInlineFP>()->target->numClsRefSlots();
      return nrefs ? AClsRefSlotAny : AEmpty;
    }();
    return may_load_store_move(
      frame | clsrefs,
      AHeapAny,
      frame | clsrefs
    );
  }

  // AGWH construction updates the AsyncGenerator object.
  case CreateAGWH:
    return may_load_store(AHeapAny, AHeapAny);

  case CreateAAWH:
    {
      auto const extra = inst.extra<CreateAAWH>();
      auto const frame = AFrame {
        inst.src(0),
        AliasIdSet {
          AliasIdSet::IdRange{ extra->first, extra->first + extra->count }
        }
      };
      return may_reenter(inst, may_load_store(frame, AHeapAny));
    }

  case CountWHNotDone:
    {
      auto const extra = inst.extra<CountWHNotDone>();
      auto const frame = AFrame {
        inst.src(0),
        AliasIdSet {
          AliasIdSet::IdRange{ extra->first, extra->first + extra->count }
        }
      };
      return may_load_store(frame, AEmpty);
    }

  // This re-enters to call extension-defined instance constructors.
  case ConstructInstance:
    return may_reenter(inst, may_load_store(AHeapAny, AHeapAny));

  // Closures don't ever throw or reenter on construction
  case ConstructClosure:
    return IrrelevantEffects{};

  case CheckStackOverflow:
  case CheckSurpriseFlagsEnter:
  case CheckSurpriseAndStack:
    return may_load_store(AEmpty, AEmpty);

  case InitExtraArgs:
    return UnknownEffects {};

  //////////////////////////////////////////////////////////////////////
  // Iterator instructions

  case IterInit:
  case LIterInit:
  case LIterNext:
    return iter_effects(
      inst,
      inst.src(1),
      AFrame { inst.src(1), inst.extra<IterData>()->valId }
    );
  case IterNext:
    return iter_effects(
      inst,
      inst.src(0),
      AFrame { inst.src(0), inst.extra<IterData>()->valId }
    );

  case IterInitK:
  case LIterInitK:
  case LIterNextK:
    {
      AliasClass key = AFrame { inst.src(1), inst.extra<IterData>()->keyId };
      AliasClass val = AFrame { inst.src(1), inst.extra<IterData>()->valId };
      return iter_effects(inst, inst.src(1), key | val);
    }

  case IterNextK:
    {
      AliasClass key = AFrame { inst.src(0), inst.extra<IterData>()->keyId };
      AliasClass val = AFrame { inst.src(0), inst.extra<IterData>()->valId };
      return iter_effects(inst, inst.src(0), key | val);
    }

  case IterFree:
    return may_reenter(inst, may_load_store(AHeapAny, AHeapAny));

  //////////////////////////////////////////////////////////////////////
  // Instructions that explicitly manipulate locals

  case StLoc:
    return PureStore {
      AFrame { inst.src(0), inst.extra<StLoc>()->locId },
      inst.src(1),
      nullptr
    };

  case StLocRange:
    {
      auto const extra = inst.extra<StLocRange>();
      auto acls = AEmpty;

      for (auto locId = extra->start; locId < extra->end; ++locId) {
        acls = acls | AFrame { inst.src(0), locId };
      }
      return PureStore { acls, inst.src(1), nullptr };
    }

  case LdLoc:
    return PureLoad { AFrame { inst.src(0), inst.extra<LocalId>()->locId } };

  case CheckLoc:
  case LdLocPseudoMain:
    // Note: LdLocPseudoMain is both a guard and a load, so it must not be a
    // PureLoad.
    return may_load_store(
      AFrame { inst.src(0), inst.extra<LocalId>()->locId },
      AEmpty
    );

  case StLocPseudoMain:
    // This can store to globals or locals, but we don't have globals supported
    // in AliasClass yet.
    return PureStore { AUnknown, inst.src(1), nullptr };

  //////////////////////////////////////////////////////////////////////
  // Instructions that manipulate class-ref slots

  case LdClsRefCls:
    return PureLoad {
      AClsRefClsSlot { inst.src(0), inst.extra<LdClsRefCls>()->slot }
    };

  case LdClsRefTS:
    return PureLoad {
      AClsRefTSSlot { inst.src(0), inst.extra<LdClsRefTS>()->slot }
    };

  case StClsRefCls:
    return PureStore {
      AClsRefClsSlot { inst.src(0), inst.extra<StClsRefCls>()->slot },
      inst.src(1),
      nullptr
    };

  case StClsRefTS:
    return PureStore {
      AClsRefTSSlot { inst.src(0), inst.extra<StClsRefTS>()->slot },
      inst.src(1),
      nullptr
    };

  case KillClsRefCls:
    return may_load_store_kill(
      AEmpty, AEmpty,
      AClsRefClsSlot { inst.src(0), inst.extra<KillClsRefCls>()->slot }
    );

  case KillClsRefTS:
    return may_load_store_kill(
      AEmpty, AEmpty,
      AClsRefTSSlot { inst.src(0), inst.extra<KillClsRefTS>()->slot }
    );

  //////////////////////////////////////////////////////////////////////
  // Pointer-based loads and stores

  case LdMem:
    return PureLoad { pointee(inst.src(0)) };
  case StMem:
    return PureStore { pointee(inst.src(0)), inst.src(1), inst.src(0) };

  // TODO(#5962341): These take non-constant offset arguments, and are
  // currently only used for collections and class property inits, so we aren't
  // hooked up yet.
  case StElem:
    return PureStore {
      inst.src(0)->type() <= TPtrToRMembCell
        ? AHeapAny
        : AUnknown,
      inst.src(2),
      inst.src(0)
    };
  case LdElem:
    return PureLoad {
      inst.src(0)->type() <= TPtrToRMembCell
        ? AHeapAny
        : AUnknown
    };

  case LdMBase:
    return PureLoad { AMIStateBase };

  case StMBase:
    return PureStore { AMIStateBase, inst.src(0), nullptr };

  case StMIPropState:
    return PureStore { AMIStatePropS, nullptr, nullptr };

  case FinishMemberOp:
    return may_load_store_kill(AEmpty, AEmpty, AMIStateAny);

  case BoxPtr:
    {
      auto const mem = pointee(inst.src(0));
      return may_load_store(mem, mem);
    }
  case UnboxPtr:
    return may_load_store(pointee(inst.src(0)), AEmpty);

  case IsNTypeMem:
  case IsTypeMem:
  case CheckTypeMem:
  case CheckInitMem:
    return may_load_store(pointee(inst.src(0)), AEmpty);

  case CheckRDSInitialized:
    return may_load_store(
      ARds { inst.extra<CheckRDSInitialized>()->handle },
      AEmpty
    );
  case MarkRDSInitialized:
    return may_load_store(
      AEmpty,
      ARds { inst.extra<MarkRDSInitialized>()->handle }
    );

  case InitProps:
    return may_load_store(
      AHeapAny,
      AHeapAny | ARds { inst.extra<InitProps>()->cls->propHandle() }
    );

  case InitSProps:
    return may_load_store(
      AHeapAny,
      AHeapAny | ARds { inst.extra<InitSProps>()->cls->sPropInitHandle() }
    );

  case LdClsFromClsMeth:
  case LdFuncFromClsMeth:
    return may_load_store(AHeapAny, AEmpty);

  //////////////////////////////////////////////////////////////////////
  // Object/Ref loads/stores

  case CheckRefInner:
    return may_load_store(ARef { inst.src(0) }, AEmpty);
  case LdRef:
    return PureLoad { ARef { inst.src(0) } };
  case StRef:
    return PureStore { ARef { inst.src(0) }, inst.src(1), inst.src(0) };

  case InitObjProps:
    return may_load_store(AEmpty, APropAny);

  case InitObjMemoSlots:
    // Writes to memo slots, but these are not modeled.
    return IrrelevantEffects {};

  // Loads $obj->trace, stores $obj->file and $obj->line.
  case InitThrowableFileAndLine:
    return may_load_store(AHeapAny, APropAny);

  //////////////////////////////////////////////////////////////////////
  // Array loads and stores

  case InitPackedLayoutArray:
    return PureStore {
      AElemI { inst.src(0), inst.extra<InitPackedLayoutArray>()->index },
      inst.src(1),
      inst.src(0)
    };

  case LdVecElem:
  case LdPackedElem: {
    auto const base = inst.src(0);
    auto const key  = inst.src(1);
    return PureLoad {
      key->hasConstVal() ? AElemI { base, key->intVal() } : AElemIAny
    };
  }

  case InitPackedLayoutArrayLoop:
    {
      auto const extra = inst.extra<InitPackedLayoutArrayLoop>();
      auto const stack_in = AStack {
        inst.src(1),
        extra->offset + static_cast<int32_t>(extra->size) - 1,
        static_cast<int32_t>(extra->size)
      };
      return may_load_store_move(stack_in, AElemIAny, stack_in);
    }

  case NewKeysetArray:
    {
      // NewKeysetArray is reading elements from the stack, but writes to a
      // completely new array, so we can treat the store set as empty.
      auto const extra = inst.extra<NewKeysetArray>();
      auto const stack_in = AStack {
        inst.src(0),
        extra->offset + static_cast<int32_t>(extra->size) - 1,
        static_cast<int32_t>(extra->size)
      };
      return may_load_store_move(stack_in, AEmpty, stack_in);
    }

  case NewStructArray:
  case NewStructDArray:
  case NewStructDict:
    {
      // NewStructArray is reading elements from the stack, but writes to a
      // completely new array, so we can treat the store set as empty.
      auto const extra = inst.extra<NewStructData>();
      auto const stack_in = AStack {
        inst.src(0),
        extra->offset + static_cast<int32_t>(extra->numKeys) - 1,
        static_cast<int32_t>(extra->numKeys)
      };
      return may_load_store_move(stack_in, AEmpty, stack_in);
    }

  case NewRecord:
    {
      auto const extra = inst.extra<NewStructData>();
      auto const stack_in = AStack {
        inst.src(1),
        extra->offset + static_cast<int32_t>(extra->numKeys) - 1,
        static_cast<int32_t>(extra->numKeys)
      };
      return may_load_store_move(stack_in, AEmpty, stack_in);
    }
  case MemoGetStaticValue:
  case MemoGetLSBValue:
  case MemoGetInstanceValue:
    // Only reads the memo value (which isn't modeled here).
    return may_load_store(AEmpty, AEmpty);

  case MemoSetStaticValue:
  case MemoSetLSBValue:
  case MemoSetInstanceValue:
    // Writes to the memo value (which isn't modeled), but can re-enter to run
    // a destructor.
    return may_reenter(inst, may_load_store(AEmpty, AEmpty));

  case MemoGetStaticCache:
  case MemoGetLSBCache:
  case MemoSetStaticCache:
  case MemoSetLSBCache: {
    // Reads some (non-zero) set of locals for keys, and reads/writes from the
    // memo cache (which isn't modeled). The set can re-enter to run a
    // destructor.
    auto const extra = inst.extra<MemoCacheStaticData>();
    auto const loc = [&] () -> AliasClass {
      if (inst.src(0)->isA(TFramePtr)) {
        return AFrame {
          inst.src(0),
          AliasIdSet{
            AliasIdSet::IdRange{
              extra->keys.first,
              extra->keys.first + extra->keys.count
            }
          }
        };
      }
      assertx(inst.src(0)->isA(TStkPtr));
      assertx(extra->stackOffset);
      return AStack {
        inst.src(0),
        *extra->stackOffset,
        static_cast<int32_t>(extra->keys.count)
      };
    }();

    auto effects = may_load_store(loc, AEmpty);
    if (inst.op() == MemoSetStaticCache || inst.op() == MemoSetLSBCache) {
      effects = may_reenter(inst, effects);
    }
    return effects;
  }

  case MemoGetInstanceCache:
  case MemoSetInstanceCache: {
    // Reads some set of locals for keys, and reads/writes from the memo cache
    // (which isn't modeled). The set can re-enter to run a destructor.
    auto const extra = inst.extra<MemoCacheInstanceData>();
    auto const loc = [&]() -> AliasClass {
      // Unlike MemoGet/SetStaticCache, we can have an empty key range here.
      if (extra->keys.count == 0) return AEmpty;

      if (inst.src(0)->isA(TFramePtr)) {
        return AFrame {
          inst.src(0),
          AliasIdSet{
            AliasIdSet::IdRange{
              extra->keys.first,
              extra->keys.first + extra->keys.count
            }
          }
        };
      }
      assertx(inst.src(0)->isA(TStkPtr));
      assertx(extra->stackOffset);
      return AStack {
        inst.src(0),
        *extra->stackOffset,
        static_cast<int32_t>(extra->keys.count)
      };
    }();
    auto effects = may_load_store(loc, AEmpty);
    if (inst.op() == MemoSetInstanceCache) effects = may_reenter(inst, effects);
    return effects;
  }

  case MixedArrayGetK:
  case DictGetK:
  case KeysetGetK: {
    auto const base = inst.src(0);
    auto const key  = inst.src(1);
    always_assert(key->isA(TInt | TStr));
    if (key->isA(TInt)) {
      return PureLoad {
        key->hasConstVal() ? AElemI { base, key->intVal() } : AElemIAny
      };
    }
    if (key->isA(TStr)) {
      return PureLoad {
        key->hasConstVal() ? AElemS { base, key->strVal() } : AElemSAny
      };
    }
    return PureLoad { AElemAny };
  }

  case ElemMixedArrayK:
  case ElemDictK:
  case ElemKeysetK:
    return IrrelevantEffects {};

  case VecFirst: {
    auto const base = inst.src(0);
    return may_load_store(AElemI { base, 0 }, AEmpty);
  }
  case VecLast: {
    auto const base = inst.src(0);
    if (base->hasConstVal(TArr)) {
      return may_load_store(
          AElemI { base, static_cast<int64_t>(base->arrVal()->size() - 1) },
          AEmpty);
    }
    return may_load_store(AElemIAny, AEmpty);
  }
  case DictFirst:
  case DictLast:
  case KeysetFirst:
  case KeysetLast:
    return may_load_store(AElemAny, AEmpty);

  case DictFirstKey:
  case DictLastKey:
    return may_load_store(AEmpty, AEmpty);

  case ProfileMixedArrayAccess:
  case CheckMixedArrayOffset:
  case CheckArrayCOW:
  case ProfileDictAccess:
  case ProfileKeysetAccess:
  case CheckDictOffset:
  case CheckKeysetOffset:
    return may_load_store(AHeapAny, AEmpty);

  case ArrayIsset:
  case AKExistsArr:
    return may_load_store(AElemAny, AEmpty);

  case ArrayIdx:
    return may_load_store(AElemAny | ARefAny, AEmpty);

  case SameArr:
  case NSameArr:
    return may_load_store(AEmpty, AEmpty);

  case DictGetQuiet:
  case DictIsset:
  case DictEmptyElem:
  case DictIdx:
  case KeysetGetQuiet:
  case KeysetIsset:
  case KeysetEmptyElem:
  case KeysetIdx:
  case AKExistsDict:
  case AKExistsKeyset:
    return may_load_store(AElemAny, AEmpty);

  case SameVec:
  case NSameVec:
  case SameDict:
  case NSameDict:
  case EqKeyset:
  case NeqKeyset:
  case SameKeyset:
  case NSameKeyset:
    return may_load_store(AElemAny, AEmpty);

  case SameShape:
  case NSameShape:
    return may_load_store(
        RuntimeOption::EvalHackArrDVArrs ? AElemAny : AEmpty,
        AEmpty);

  case AKExistsObj:
    return may_load_store(AHeapAny, AHeapAny);

  //////////////////////////////////////////////////////////////////////
  // Member instructions

  case CheckMBase:
    return may_load_store(pointee(inst.src(0)), AEmpty);

  /*
   * Various minstr opcodes that take a PtrToGen in src 0, which may or may not
   * point to a frame local or the evaluation stack. Some may read or write to
   * that pointer while some only read. They can all re-enter the VM and access
   * arbitrary heap locations.
   */
  case CGetElem:
  case EmptyElem:
  case IssetElem:
  case CGetProp:
  case CGetPropQ:
  case EmptyProp:
  case IssetProp:
    return may_load_store_kill(
      AHeapAny | all_pointees(inst),
      AHeapAny,
      AMIStatePropS
    );

  case IncDecElem:
  case IncDecProp:
  case SetElem:
  case SetNewElem:
  case SetOpElem:
  case SetOpProp:
  case SetProp:
    return minstr_final_with_prop_state(inst);

  /*
   * SetRange behaves like a simpler version of SetElem.
   */
  case SetRange:
  case SetRangeRev:
    return may_load_store_kill(
      AHeapAny | all_pointees(inst),
      AHeapAny | pointee(inst.src(0)),
      AMIStatePropS
    );

  case SetNewElemArray:
  case SetNewElemVec:
  case SetNewElemKeyset:
  case UnsetElem:
  case ElemArrayD:
  case ElemArrayU:
  case ElemVecD:
  case ElemVecU:
  case ElemDictD:
  case ElemDictU:
  case ElemKeysetU:
  case UnsetProp:
    // Right now we generally can't limit any of these better than general
    // re-entry rules, since they can raise warnings and re-enter.
    return may_load_store_kill(
      AHeapAny | all_pointees(inst),
      AHeapAny | all_pointees(inst),
      AMIStatePropS
    );

  case ReservePackedArrayDataNewElem:
    return may_load_store(AHeapAny, AHeapAny);

  /*
   * Intermediate minstr operations. In addition to a base pointer like the
   * operations above, these may take a pointer to MInstrState::tvRef, which
   * they may store to (but not read from).
   */
  case ElemX:
  case ElemDX:
  case ElemUX:
  case PropX:
  case PropDX:
  case PropQ:
    return minstr_with_tvref(inst);

  /*
   * Collection accessors can read from their inner array buffer, but stores
   * COW and behave as if they only affect collection memory locations.  We
   * don't track those, so it's returning AEmpty for now.
   */
  case MapIsset:
  case PairIsset:
  case VectorIsset:
    return may_load_store(AHeapAny, AEmpty /* Note */);
  case MapGet:
  case MapSet:
  case VectorSet:
    return may_reenter(inst, may_load_store(AHeapAny, AEmpty /* Note */));

  case LdInitPropAddr:
    return may_load_store(
      AProp {
        inst.src(0),
        safe_cast<uint32_t>(inst.extra<LdInitPropAddr>()->offsetBytes)
      },
      AEmpty
    );
  case LdInitRDSAddr:
    return may_load_store(
      ARds { inst.extra<LdInitRDSAddr>()->handle },
      AEmpty
    );

  //////////////////////////////////////////////////////////////////////
  // Instructions that allocate new objects, without reading any other memory
  // at all, so any effects they have on some types of memory locations we
  // track are isolated from anything else we care about.

  case NewArray:
  case NewClsMeth:
  case NewCol:
  case NewColFromArray:
  case NewPair:
  case NewInstanceRaw:
  case NewMixedArray:
  case NewDArray:
  case NewDictArray:
  case AllocPackedArray:
  case AllocVArray:
  case AllocVecArray:
  case ConvBoolToArr:
  case ConvDblToStr:
  case ConvDblToArr:
  case ConvIntToArr:
  case ConvIntToStr:
  case Box:  // conditional allocation
    return IrrelevantEffects {};

  case AllocObj:
    // AllocObj re-enters to call constructors, but if it weren't for that we
    // could ignore its loads and stores since it's a new object.
    return may_reenter(inst, may_load_store(AEmpty, AEmpty));
  case AllocObjReified:
    // Similar to AllocObj but also stores the reification
    return may_reenter(inst, may_load_store(AEmpty, AHeapAny));

  //////////////////////////////////////////////////////////////////////
  // Instructions that explicitly manipulate the stack.

  case LdStk:
    return PureLoad {
      AStack { inst.src(0), inst.extra<LdStk>()->offset, 1 }
    };

  case StStk:
    return PureStore {
      AStack { inst.src(0), inst.extra<StStk>()->offset, 1 },
      inst.src(1),
      nullptr
    };

  case StOutValue:
    // Technically these writes affect the caller's stack, but there is no way
    // to actually observe them from within the callee. They can also only
    // occur once on any exit path from a function.
    return may_load_store(AEmpty, AEmpty);

  case SpillFrame:
    {
      auto const spOffset = inst.extra<SpillFrame>()->spOffset;
      return PureSpillFrame {
        actrec(inst.src(0), spOffset),
        actrec_ctx(inst.src(0), spOffset),
        actrec_func(inst.src(0), spOffset),
        inst.src(1)
      };
    }

  case CheckStk:
    return may_load_store(
      AStack { inst.src(0), inst.extra<CheckStk>()->offset, 1 },
      AEmpty
    );

  case LdARCtx:
    return PureLoad {
      actrec_ctx(inst.src(0), inst.extra<LdARCtx>()->offset)
    };
  case LdARFuncPtr:
    return PureLoad {
      actrec_func(inst.src(0), inst.extra<LdARFuncPtr>()->offset)
    };

  case DbgAssertARFunc:
    return may_load_store(
      actrec_func(inst.src(0), inst.extra<DbgAssertARFunc>()->offset),
      AEmpty
    );

  case Unreachable:
    // Unreachable code kills every memory location.
    return may_load_store_kill(AEmpty, AEmpty, AUnknown);

  case ResolveTypeStruct: {
    auto const extra = inst.extra<ResolveTypeStructData>();
    auto const stack_in = AStack {
      inst.src(0),
      extra->offset + static_cast<int32_t>(extra->size) - 1,
      static_cast<int32_t>(extra->size)
    };
    return may_load_store(AliasClass(stack_in)|AHeapAny, AHeapAny);
  }

  //////////////////////////////////////////////////////////////////////
  // Instructions that never read or write memory locations tracked by this
  // module.

  case AbsDbl:
  case AddDbl:
  case AddInt:
  case AddIntO:
  case AndInt:
  case AssertType:
  case AssertLoc:
  case AssertStk:
  case AssertMBase:
  case AssertARFunc:
  case FuncGuard:
  case DefFP:
  case DefSP:
  case EndGuards:
  case EqBool:
  case EqCls:
  case EqFunc:
  case EqStrPtr:
  case EqArrayDataPtr:
  case EqDbl:
  case EqInt:
  case GteBool:
  case GteInt:
  case GtBool:
  case GtInt:
  case HintLocInner:
  case HintStkInner:
  case HintMBaseInner:
  case Jmp:
  case JmpNZero:
  case JmpZero:
  case LdPropAddr:
  case LdStkAddr:
  case LdPackedArrayDataElemAddr:
  case LteBool:
  case LteDbl:
  case LteInt:
  case LtBool:
  case LtInt:
  case GtDbl:
  case GteDbl:
  case LtDbl:
  case DivDbl:
  case DivInt:
  case MulDbl:
  case MulInt:
  case MulIntO:
  case NeqBool:
  case NeqDbl:
  case NeqInt:
  case SameObj:
  case NSameObj:
  case EqRes:
  case NeqRes:
  case CmpBool:
  case CmpInt:
  case CmpDbl:
  case SubDbl:
  case SubInt:
  case SubIntO:
  case XorBool:
  case XorInt:
  case OrInt:
  case AssertNonNull:
  case CheckNonNull:
  case CheckNullptr:
  case CheckFuncMMNonMagic:
  case CheckSmashableClass:
  case Ceil:
  case Floor:
  case DefLabel:
  case CheckInit:
  case Nop:
  case Mod:
  case Conjure:
  case ConjureUse:
  case EndBlock:
  case ConvBoolToInt:
  case ConvBoolToDbl:
  case DefConst:
  case LdLocAddr:
  case Sqrt:
  case Shl:
  case Shr:
  case Lshr:
  case IsNType:
  case IsType:
  case Mov:
  case ConvClsToCctx:
  case ConvDblToBool:
  case ConvDblToInt:
  case DblAsBits:
  case LdMIPropStateAddr:
  case LdMIStateAddr:
  case LdPairBase:
  case LdClsCns:
  case LdSubClsCns:
  case LdSubClsCnsClsName:
  case LdTypeCns:
  case CheckSubClsCns:
  case LdClsCnsVecLen:
  case ProfileSubClsCns:
  case CheckCtxThis:
  case FuncSupportsAsyncEagerReturn:
  case IsFunReifiedGenericsMatched:
  case IsFuncDynCallable:
  case IsClsDynConstructible:
  case LdFuncMFunc:
  case LdFuncRxLevel:
  case LdSmashable:
  case LdSmashableFunc:
  case IsReifiedName:
  case LdARNumParams:
  case LdRDSAddr:
  case ExitPlaceholder:
  case CheckRange:
  case ProfileType:
  case LdIfaceMethod:
  case InstanceOfIfaceVtable:
  case CheckARMagicFlag:
  case LdARNumArgsAndFlags:
  case StARNumArgsAndFlags:
  case LdARReifiedGenerics:
  case KillARReifiedGenerics:
  case LdTVAux:
  case LdARInvName:
  case StARInvName:
  case MethodExists:
  case GetTime:
  case GetTimeNs:
  case ProfileInstanceCheck:
  case Select:
  case LookupSPropSlot:
  case ConvPtrToLval:
  case MangleReifiedName:
    return IrrelevantEffects {};

  case StClosureArg:
    return PureStore {
      AProp {
        inst.src(0),
        safe_cast<uint32_t>(inst.extra<StClosureArg>()->offsetBytes)
      },
      inst.src(1),
      inst.src(0)
    };

  //////////////////////////////////////////////////////////////////////
  // Instructions that technically do some things w/ memory, but not in any way
  // we currently care about.  They however don't return IrrelevantEffects
  // because we assume (in refcount-opts) that IrrelevantEffects instructions
  // can't even inspect Countable reference count fields, and several of these
  // can.  All GeneralEffects instructions are assumed to possibly do so.

  case DecRefNZ:
  case AFWHBlockOn:
  case IncRef:
  case LdClosureCtx:
  case StClosureCtx:
  case StContArKey:
  case StContArValue:
  case LdRetVal:
  case ConvStrToInt:
  case ConvResToInt:
  case OrdStr:
  case ChrInt:
  case CreateSSWH:
  case NewLikeArray:
  case CheckRefs:
  case LdClsCctx:
  case BeginCatch:
  case CheckSurpriseFlags:
  case CheckType:
  case CheckVArray:
  case CheckDArray:
  case StArResumeAddr:
  case StContArState:
  case ZeroErrorLevel:
  case RestoreErrorLevel:
  case CheckCold:
  case ContArIncIdx:
  case ContArIncKey:
  case ContArUpdateIdx:
  case ContValid:
  case ContStarted:
  case IncProfCounter:
  case IncStat:
  case ContPreNext:
  case ContStartedCheck:
  case ConvArrToBool:
  case ConvArrToDbl:
  case CountArray:
  case CountArrayFast:
  case CountVec:
  case CountDict:
  case CountShape:
  case CountKeyset:
  case InstanceOf:
  case InstanceOfBitmask:
  case NInstanceOfBitmask:
  case InstanceOfIface:
  case InterfaceSupportsArr:
  case InterfaceSupportsVec:
  case InterfaceSupportsDict:
  case InterfaceSupportsKeyset:
  case InterfaceSupportsDbl:
  case InterfaceSupportsInt:
  case InterfaceSupportsStr:
  case IsWaitHandle:
  case IsCol:
  case IsDVArray:
  case HasToString:
  case DbgAssertRefCount:
  case GtStr:
  case GteStr:
  case LtStr:
  case LteStr:
  case EqStr:
  case NeqStr:
  case SameStr:
  case NSameStr:
  case CmpStr:
  case GtStrInt:
  case GteStrInt:
  case LtStrInt:
  case LteStrInt:
  case EqStrInt:
  case NeqStrInt:
  case CmpStrInt:
  case GtRes:
  case GteRes:
  case LtRes:
  case LteRes:
  case CmpRes:
  case LdBindAddr:
  case LdSSwitchDestFast:
  case RBTraceEntry:
  case RBTraceMsg:
  case ConvIntToBool:
  case ConvIntToDbl:
  case ConvStrToArr:   // decrefs src, but src is a string
  case ConvStrToBool:
  case ConvStrToDbl:
  case ConvResToDbl:
  case EagerSyncVMRegs:
  case ExtendsClass:
  case LdUnwinderValue:
  case LdCtx:
  case LdCctx:
  case LdClosure:
  case LdClsName:
  case LdAFWHActRec:
  case LdClsCtx:
  case LdContActRec:
  case LdContArKey:
  case LdContArValue:
  case LdContField:
  case LdContResumeAddr:
  case LdClsCachedSafe:
  case LdClsInitData:
  case UnwindCheckSideExit:
  case LdCns:
  case LdFuncVecLen:
  case LdClsMethod:
  case LdClsMethodCacheCls:
  case LdClsMethodCacheFunc:
  case LdClsMethodFCacheFunc:
  case LdClsTypeCns:
  case LdClsTypeCnsClsName:
  case FwdCtxStaticCall:
  case ProfileArrayKind:
  case ProfileSwitchDest:
  case LdFuncNumParams:
  case LdFuncName:
  case LdGblAddr:
  case LdGblAddrDef:
  case LdObjClass:
  case LdObjInvoke:
  case LdObjMethod:
  case LdStrLen:
  case StringIsset:
  case LdSwitchDblIndex:
  case LdSwitchStrIndex:
  case LdVectorBase:
  case LdWHResult:
  case LdWHState:
  case LdWHNotDone:
  case LookupClsRDS:
  case DbgTraceCall:
  case InitCtx:
  case PackMagicArgs:
  case StrictlyIntegerConv:
  case DbgAssertFunc:
  case ProfileMethod:
    return may_load_store(AEmpty, AEmpty);

  // Some that touch memory we might care about later, but currently don't:
  case ColIsEmpty:
  case ColIsNEmpty:
  case ConvCellToBool:
  case ConvObjToBool:
  case CountCollection:
  case LdVectorSize:
  case CheckPackedArrayDataBounds:
  case LdColVec:
  case LdColDict:
  case EnterFrame:
    return may_load_store(AEmpty, AEmpty);

  //////////////////////////////////////////////////////////////////////
  // Instructions that can re-enter the VM and touch most heap things.  They
  // also may generally write to the eval stack below an offset (see
  // alias-class.h above AStack for more).

  case DecRef:
    {
      auto const src = inst.src(0);
      // It could decref the inner ref.
      auto affected = src->isA(TBoxedCell) ? ARef { src } :
                      src->type().maybe(TBoxedCell) ? ARefAny : AEmpty;
      if (src->type().maybe(TKeyset | TBoxedKeyset)) {
        // TKeyset can't re-enter, but it will decref any contained
        // strings. Without this, an incref of a string contained in
        // a Keyset could be sunk past the decref of the Keyset.
        affected |= AHeapAny;
      }
      // Need to add affected to the `store' set. See comments about
      // `GeneralEffects' in memory-effects.h.
      auto const effect = may_load_store(affected, affected);
      if (src->type().maybe(TArr | TVec | TDict | TObj | TRes |
                            TBoxedArr | TBoxedVec | TBoxedDict |
                            TBoxedObj | TBoxedRes)) {
        // Could re-enter to run a destructor. Keysets are exempt because they
        // can only contain strings or integers.
        return may_reenter(inst, effect);
      }
      return effect;
    }

  case GetMemoKey:
    return may_load_store(AHeapAny, AHeapAny);

  case GetMemoKeyScalar:
    return IrrelevantEffects{};

  case LdArrFuncCtx:
  case LdFunc: // these all can autoload
    {
      AliasClass effects =
        actrec(inst.src(1), inst.extra<IRSPRelOffsetData>()->offset);
      return may_load_store(effects, effects);
    }

  case LookupClsMethod:   // autoload, and it writes part of the new actrec
    {
      AliasClass effects =
        actrec(inst.src(2), inst.extra<LookupClsMethod>()->calleeAROffset);
      return may_load_store(effects, effects);
    }

  case LdClsPropAddrOrNull:   // may run 86{s,p}init, which can autoload
  case LdClsPropAddrOrRaise:  // raises errors, and 86{s,p}init
  case BaseG:
  case Clone:
  case ThrowArrayIndexException:
  case ThrowArrayKeyException:
  case RaiseUninitLoc:
  case RaiseUndefProp:
  case RaiseMissingArg:
  case RaiseTooManyArg:
  case RaiseError:
  case RaiseErrorOnInvalidIsAsExpressionType:
  case RaiseNotice:
  case RaiseWarning:
  case RaiseHackArrCompatNotice:
  case RaiseHackArrParamNotice:
  case RaiseHackArrPropNotice:
  case RaiseForbiddenDynCall:
  case RaiseForbiddenDynConstruct:
  case RaiseRxCallViolation:
  case RaiseStrToClassNotice:
  case CheckClsReifiedGenericMismatch:
  case CheckFunReifiedGenericMismatch:
  case ConvCellToStr:
  case ConvObjToStr:
  case Count:      // re-enters on CountableClass
  case GtObj:
  case GteObj:
  case LtObj:
  case LteObj:
  case EqObj:
  case NeqObj:
  case CmpObj:
  case GtArr:
  case GteArr:
  case LtArr:
  case LteArr:
  case EqArr:
  case NeqArr:
  case CmpArr:
  case GtShape:
  case GteShape:
  case LtShape:
  case LteShape:
  case EqShape:
  case NeqShape:
  case CmpShape:
  case GtVec:
  case GteVec:
  case LtVec:
  case LteVec:
  case EqVec:
  case NeqVec:
  case CmpVec:
  case EqDict:
  case NeqDict:
  case ConvCellToArr:  // decrefs src, may read obj props
  case ConvCellToObj:  // decrefs src
  case ConvObjToArr:   // decrefs src
  case ConvObjToVArr:  // can invoke PHP
  case ConvObjToDArr:  // can invoke PHP
  case OODeclExists:
  case DefCls:         // autoload
  case LdCls:          // autoload
  case LdClsCached:    // autoload
  case LdFuncCached:   // autoload
  case LdRecCached:    // autoload
  case LdSwitchObjIndex:  // decrefs arg
  case InitClsCns:      // autoload
  case LookupClsMethodCache:  // autoload
  case LookupClsMethodFCache: // autoload
  case LookupCnsE:
  case LookupFuncCached: // autoload
  case StringGet:      // raise_notice
  case OrdStrIdx:      // raise_notice
  case ArrayAdd:       // decrefs source
  case AddElemIntKey:
  case AddElemStrKey:
  case AddNewElem:         // can re-enter
  case AddNewElemKeyset:   // can re-enter
  case DictAddElemIntKey:  // decrefs value
  case DictAddElemStrKey:  // decrefs value
  case ArrayGet:       // kVPackedKind warnings
  case ArraySet:       // kVPackedKind warnings
  case ArraySetRef:    // kVPackedKind warnings
  case DictGet:
  case KeysetGet:
  case VecSet:
  case VecSetRef:
  case DictSet:
  case DictSetRef:
  case ElemArrayX:
  case ElemDictX:
  case ElemKeysetX:
  case LdClsCtor:
  case ConcatStrStr:
  case PrintStr:
  case PrintBool:
  case PrintInt:
  case ConcatIntStr:
  case ConcatStrInt:
  case LdSSwitchDestSlow:
  case ConvObjToDbl:
  case ConvObjToInt:
  case ConvCellToInt:
  case ConvResToStr:
  case ConcatStr3:
  case ConcatStr4:
  case ConvCellToDbl:
  case ConvArrToVec:
  case ConvArrToDict:
  case ConvShapeToDict:
  case ConvObjToVec:
  case ConvObjToDict:
  case ConvObjToKeyset:
  case ThrowOutOfBounds:
  case ThrowInvalidArrayKey:
  case ThrowInvalidOperation:
  case ThrowArithmeticError:
  case ThrowDivisionByZeroError:
  case ThrowDivisionByZeroException:
  case ThrowHasThisNeedStatic:
  case ThrowLateInitPropError:
  case ThrowMissingThis:
  case ThrowParameterWrongType:
  case ThrowParamRefMismatch:
  case ThrowParamRefMismatchRange:
  case SetOpCell:
  case SetOpCellVerify:
  case ThrowAsTypeStructException:
  case PropTypeRedefineCheck: // Can raise and autoload
  case HandleRequestSurprise:
    return may_load_store(AHeapAny, AHeapAny);

  case AddNewElemVec:
  case IsTypeStruct:
  case LdReifiedGeneric:
  case RecordReifiedGenericsAndGetName:
  case RecordReifiedGenericsAndGetTSList:
    return may_load_store(AElemAny, AEmpty);

  case ConvArrToKeyset: // Decrefs input values
  case ConvVecToKeyset:
  case ConvDictToKeyset:
  case ConvShapeToKeyset:
  case ConvDictToDArr: // These 4 may raise Hack array compat notices
  case ConvShapeToDArr:
  case ConvKeysetToDArr:
  case ConvDictToArr:
  case ConvShapeToArr:
  case ConvKeysetToArr:
    return may_load_store(AElemAny, AEmpty);

  case ConvVecToArr:
  case ConvArrToNonDVArr:
  case ConvDictToVec:
  case ConvShapeToVec:
  case ConvKeysetToVec:
  case ConvVecToDict:
  case ConvKeysetToDict:
  case ConvArrToVArr:
  case ConvVecToVArr:
  case ConvDictToVArr:
  case ConvShapeToVArr:
  case ConvKeysetToVArr:
  case ConvArrToDArr:
  case ConvVecToDArr:
    return may_load_store(AElemAny, AEmpty);

  case ReleaseVVAndSkip:  // can decref ExtraArgs or VarEnv and Locals
    return may_reenter(inst,
                       may_load_store(AHeapAny|AFrameAny, AHeapAny|AFrameAny));

  // debug_backtrace() traverses stack and WaitHandles on the heap.
  case DebugBacktrace:
  case DebugBacktraceFast:
    return may_load_store(AHeapAny|AFrameAny|AStackAny, AHeapAny);

  // This instruction doesn't touch memory we track, except that it may
  // re-enter to construct php Exception objects.  During this re-entry anything
  // can happen (e.g. a surprise flag check could cause a php signal handler to
  // run arbitrary code).
  case AFWHPrepareChild:
    return may_reenter(inst, may_load_store(AEmpty, AEmpty));

  //////////////////////////////////////////////////////////////////////
  // The following instructions are used for debugging memory optimizations.
  // We can't ignore them, because they can prevent future optimizations;
  // eg t1 = LdStk<N>; DbgTrashStk<N>; StStk<N> t1
  // If we ignore the DbgTrashStk it looks like the StStk is redundant

  case DbgTrashStk:
    return GeneralEffects {
      AEmpty, AEmpty, AEmpty,
      AStack { inst.src(0), inst.extra<DbgTrashStk>()->offset, 1 }
    };
  case DbgTrashFrame:
    return GeneralEffects {
      AEmpty, AEmpty, AEmpty,
      actrec(inst.src(0), inst.extra<DbgTrashFrame>()->offset)
    };
  case DbgTrashMem:
    return GeneralEffects {
      AEmpty, AEmpty, AEmpty,
      pointee(inst.src(0))
    };
  case DbgTrashRetVal:
    return IrrelevantEffects {};

  //////////////////////////////////////////////////////////////////////

  }

  not_reached();
}

//////////////////////////////////////////////////////////////////////

DEBUG_ONLY bool check_effects(const IRInstruction& inst, MemEffects me) {
  SCOPE_ASSERT_DETAIL("Memory Effects") {
    return folly::sformat("  inst: {}\n  effects: {}\n", inst, show(me));
  };

  auto check_fp = [&] (FPRelOffset base) {
    always_assert_flog(
      base.offset <= 0,
      "frame offset is above base frame"
    );
  };

  auto check_obj = [&] (SSATmp* obj) {
    always_assert_flog(
      obj->type() <= TObj,
      "Non obj pointer in memory effects"
    );
  };

  auto check = [&] (AliasClass a) {
    if (auto const fr = a.frame()) check_fp(fr->base);
    if (auto const sl = a.clsRefClsSlot()) check_fp(sl->base);
    if (auto const sl = a.clsRefTSSlot()) check_fp(sl->base);
    if (auto const pr = a.prop())  check_obj(pr->obj);
  };

  match<void>(
    me,
    [&] (GeneralEffects x) {
      check(x.loads);
      check(x.stores);
      check(x.moves);
      check(x.kills);

      // Locations may-moved always should also count as may-loads.
      always_assert(x.moves <= x.loads);

      if (inst.mayRaiseError()) {
        // Any instruction that can raise an error can run a user error handler
        // and have arbitrary effects on the heap.
        always_assert(AHeapAny <= x.loads);
        always_assert(AHeapAny <= x.stores);
        /*
         * They also ought to kill /something/ on the stack, because of
         * possible re-entry.  It's not incorrect to leave things out of the
         * kills set, but this assertion is here because we shouldn't do it on
         * purpose, so this is here until we have a reason not to assert it.
         *
         * The mayRaiseError instructions should all be going through
         * may_reenter right now, which will kill the stack below the re-entry
         * depth---unless the marker for `inst' doesn't have an fp set.
         */
        always_assert(inst.marker().fp() == nullptr ||
                      AStackAny.maybe(x.kills));
      }
    },
    [&] (PureLoad x)         { check(x.src); },
    [&] (PureStore x)        { check(x.dst); },
    [&] (PureSpillFrame x)   { check(x.stk); check(x.ctx); check(x.callee);
                               always_assert(x.ctx <= x.stk);
                               always_assert(x.callee <= x.stk); },
    [&] (ExitEffects x)      { check(x.live); check(x.kills); },
    [&] (IrrelevantEffects)  {},
    [&] (UnknownEffects)     {},
    [&] (CallEffects x)      { check(x.kills);
                               check(x.stack);
                               check(x.locals);
                               check(x.callee);
                               always_assert(x.callee <= x.stack); },
    [&] (InlineEnterEffects x){ check(x.inlStack);
                                check(x.inlFrame);
                                check(x.actrec); },
    [&] (InlineExitEffects x){ check(x.inlStack);
                               check(x.inlFrame);
                               check(x.inlMeta); },
    [&] (ReturnEffects x)    { check(x.kills); }
  );

  return true;
}

//////////////////////////////////////////////////////////////////////

}

MemEffects memory_effects(const IRInstruction& inst) {
  auto const inner = memory_effects_impl(inst);
  auto const ret = [&] () -> MemEffects {
    // These instructions have special handling because they occur as functions
    // suspend or return. Their ability to reenter is handled in
    // memory_effects_impl, and comments in that function explain why.
    auto const is_special = inst.is(
      ReturnHook,
      SuspendHookAwaitEF,
      SuspendHookAwaitEG,
      SuspendHookAwaitR,
      SuspendHookCreateCont,
      SuspendHookYield
    );

    if (is_special || !inst.mayRaiseError()) return inner;

    auto fail = [&] {
      always_assert_flog(
        false,
        "Instruction {} has effects {}, but has been marked as MayRaiseError "
        "and must use a UnknownEffects, GeneralEffects, or CallEffects type.",
        inst,
        show(inner)
      );
      return may_load_store(AUnknown, AUnknown);
    };

    // Calls are implicitly MayRaise, all other instructions must use the
    // GeneralEffects or UnknownEffects class of memory effects
    return match<MemEffects>(
      inner,
      [&] (GeneralEffects x)   { return may_reenter(inst, x); },
      [&] (CallEffects x)      { return x; },
      [&] (UnknownEffects x)   { return x; },
      [&] (PureLoad)           { return fail(); },
      [&] (PureStore)          { return fail(); },
      [&] (PureSpillFrame)     { return fail(); },
      [&] (ExitEffects)        { return fail(); },
      [&] (InlineExitEffects)  { return fail(); },
      [&] (InlineEnterEffects) { return fail(); },
      [&] (IrrelevantEffects)  { return fail(); },
      [&] (ReturnEffects)      { return fail(); }
    );
  }();
  assertx(check_effects(inst, ret));
  return ret;
}

AliasClass pointee(const SSATmp* tmp) {
  return pointee(tmp, nullptr);
}

//////////////////////////////////////////////////////////////////////

MemEffects canonicalize(MemEffects me) {
  using R = MemEffects;
  return match<R>(
    me,
    [&] (GeneralEffects x) -> R {
      return GeneralEffects {
        canonicalize(x.loads),
        canonicalize(x.stores),
        canonicalize(x.moves),
        canonicalize(x.kills)
      };
    },
    [&] (PureLoad x) -> R {
      return PureLoad { canonicalize(x.src) };
    },
    [&] (PureStore x) -> R {
      return PureStore { canonicalize(x.dst), x.value, x.dep };
    },
    [&] (PureSpillFrame x) -> R {
      return PureSpillFrame {
        canonicalize(x.stk),
        canonicalize(x.ctx),
        canonicalize(x.callee)
      };
    },
    [&] (ExitEffects x) -> R {
      return ExitEffects { canonicalize(x.live), canonicalize(x.kills) };
    },
    [&] (InlineEnterEffects x) -> R {
      return InlineEnterEffects {
        canonicalize(x.inlStack),
        canonicalize(x.inlFrame),
        canonicalize(x.actrec),
      };
    },
    [&] (InlineExitEffects x) -> R {
      return InlineExitEffects {
        canonicalize(x.inlStack),
        canonicalize(x.inlFrame),
        canonicalize(x.inlMeta)
      };
    },
    [&] (CallEffects x) -> R {
      return CallEffects {
        canonicalize(x.kills),
        canonicalize(x.stack),
        canonicalize(x.locals),
        canonicalize(x.callee)
      };
    },
    [&] (ReturnEffects x) -> R {
      return ReturnEffects { canonicalize(x.kills) };
    },
    [&] (IrrelevantEffects x) -> R { return x; },
    [&] (UnknownEffects x)    -> R { return x; }
  );
}

//////////////////////////////////////////////////////////////////////

std::string show(MemEffects effects) {
  using folly::sformat;
  return match<std::string>(
    effects,
    [&] (GeneralEffects x) {
      return sformat("mlsmk({} ; {} ; {} ; {})",
        show(x.loads),
        show(x.stores),
        show(x.moves),
        show(x.kills)
      );
    },
    [&] (ExitEffects x) {
      return sformat("exit({} ; {})", show(x.live), show(x.kills));
    },
    [&] (InlineEnterEffects x) {
      return sformat("inline_enter({} ; {} ; {})",
        show(x.inlStack),
        show(x.inlFrame),
        show(x.actrec)
      );
    },
    [&] (InlineExitEffects x) {
      return sformat("inline_exit({} ; {} ; {})",
        show(x.inlStack),
        show(x.inlFrame),
        show(x.inlMeta)
      );
    },
    [&] (CallEffects x) {
      return sformat("call({} ; {} ; {} ; {})",
        show(x.kills),
        show(x.stack),
        show(x.locals),
        show(x.callee)
      );
    },
    [&] (PureSpillFrame x) {
      return sformat("stFrame({} ; {} ; {})",
        show(x.stk),
        show(x.ctx),
        show(x.callee)
      );
    },
    [&] (PureLoad x)        { return sformat("ld({})", show(x.src)); },
    [&] (PureStore x)       { return sformat("st({})", show(x.dst)); },
    [&] (ReturnEffects x)   { return sformat("return({})", show(x.kills)); },
    [&] (IrrelevantEffects) { return "IrrelevantEffects"; },
    [&] (UnknownEffects)    { return "UnknownEffects"; }
  );
}

//////////////////////////////////////////////////////////////////////

AliasClass inline_fp_frame(const IRInstruction* inst) {
  return AStack {
    inst->src(0),
    inst->extra<DefInlineFP>()->spOffset + int32_t{kNumActRecCells} - 1,
    int32_t{kNumActRecCells}
  };
}

//////////////////////////////////////////////////////////////////////

}}