hphp/runtime/vm/jit/memory-effects.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #include "hphp/runtime/vm/jit/memory-effects.h"
  17
  18 #include "hphp/util/match.h"
  19 #include "hphp/util/safe-cast.h"
  20 #include "hphp/util/assertions.h"
  21
  22 #include "hphp/runtime/vm/bytecode.h"
  23 #include "hphp/runtime/vm/jit/analysis.h"
  24 #include "hphp/runtime/vm/jit/dce.h"
  25 #include "hphp/runtime/vm/jit/ir-instruction.h"
  26 #include "hphp/runtime/vm/jit/ssa-tmp.h"
  27 #include "hphp/runtime/vm/jit/type-array-elem.h"
  28
  29 #include <folly/Optional.h>
  30
  31 namespace HPHP { namespace jit {
  32
  33 namespace {
  34
  35 const StaticString s_GLOBALS("GLOBALS");
  36
  37 uint32_t iterId(const IRInstruction& inst) {
  38   return inst.extra<IterId>()->iterId;
  39 }
  40
  41 AliasClass pointee(
  42   const SSATmp* ptr,
  43   jit::flat_set<const IRInstruction*>* visited_labels
  44 ) {
  45   auto const type = ptr->type();
  46   always_assert(type <= TMemToCell);
  47   auto const canonPtr = canonical(ptr);
  48   if (!canonPtr->isA(TMemToCell)) {
  49     // This can happen when ptr is TBottom from a passthrough instruction with
  50     // a src that isn't TBottom. The most common cause of this is something
  51     // like "t5:Bottom = CheckType<Str> t2:Int". It means ptr isn't really a
  52     // pointer, so return AEmpty to avoid unnecessarily pessimizing any
  53     // optimizations.
  54     always_assert(ptr->isA(TBottom));
  55     return AEmpty;
  56   }
  57
  58   auto const sinst = canonPtr->inst();
  59
  60   if (sinst->is(LdRDSAddr, LdInitRDSAddr)) {
  61     return ARds { sinst->extra<RDSHandleData>()->handle };
  62   }
  63
  64   // For phis, union all incoming values, taking care to not recurse infinitely
  65   // in the presence of loops.
  66   if (sinst->is(DefLabel)) {
  67     if (visited_labels && visited_labels->count(sinst)) {
  68       return AEmpty;
  69     }
  70
  71     auto const dsts = sinst->dsts();
  72     auto const dstIdx =
  73       std::find(dsts.begin(), dsts.end(), canonPtr) - dsts.begin();
  74     always_assert(dstIdx >= 0 && dstIdx < sinst->numDsts());
  75
  76     folly::Optional<jit::flat_set<const IRInstruction*>> label_set;
  77     if (visited_labels == nullptr) {
  78       label_set.emplace();
  79       visited_labels = &label_set.value();
  80     }
  81     visited_labels->insert(sinst);
  82
  83     auto ret = AEmpty;
  84     sinst->block()->forEachSrc(
  85       dstIdx, [&](const IRInstruction* /*jmp*/, const SSATmp* thePtr) {
  86         ret = ret | pointee(thePtr, visited_labels);
  87       });
  88     return ret;
  89   }
  90
  91   auto specific = [&] () -> folly::Optional<AliasClass> {
  92     if (type <= TBottom) return AEmpty;
  93
  94     if (type <= TMemToFrameCell) {
  95       if (sinst->is(LdLocAddr)) {
  96         return AliasClass {
  97           ALocal { sinst->src(0), sinst->extra<LdLocAddr>()->locId }
  98         };
  99       }
 100       return ALocalAny;
 101     }
 102
 103     if (type <= TMemToStkCell) {
 104       if (sinst->is(LdStkAddr)) {
 105         return AliasClass {
 106           AStack { sinst->src(0), sinst->extra<LdStkAddr>()->offset, 1 }
 107         };
 108       }
 109       return AStackAny;
 110     }
 111
 112     if (type <= TMemToPropCell) {
 113       if (sinst->is(LdPropAddr, LdInitPropAddr)) {
 114         return AliasClass {
 115           AProp {
 116             sinst->src(0),
 117             safe_cast<uint16_t>(sinst->extra<IndexData>()->index)
 118           }
 119         };
 120       }
 121       return APropAny;
 122     }
 123
 124     if (type <= TMemToMISCell) {
 125       if (sinst->is(LdMIStateAddr)) {
 126         return mis_from_offset(sinst->src(0)->intVal());
 127       }
 128       if (ptr->hasConstVal() && ptr->rawVal() == 0) {
 129         // nullptr tvRef pointer, representing an instruction that doesn't use
 130         // it.
 131         return AEmpty;
 132       }
 133       return AMIStateTempBase;
 134     }
 135
 136     auto elem = [&] () -> AliasClass {
 137       auto base = sinst->src(0);
 138       auto key  = sinst->src(1);
 139
 140       always_assert(base->isA(TArrLike));
 141
 142       if (key->isA(TInt)) {
 143         if (key->hasConstVal()) return AElemI { base, key->intVal() };
 144         return AElemIAny;
 145       }
 146       if (key->hasConstVal(TStr)) {
 147         assertx(!base->isA(TVec));
 148         return AElemS { base, key->strVal() };
 149       }
 150       return AElemAny;
 151     };
 152
 153     if (type <= TMemToElemCell) {
 154       if (sinst->is(LdPackedArrayDataElemAddr)) return elem();
 155       return AElemAny;
 156     }
 157
 158     // The result of ElemArray{,W,U} is either the address of an array element,
 159     // or &immutable_null_base.
 160     if (type <= TMemToMembCell) {
 161       // Takes a PtrToCell as its first operand, so we can't easily grab an
 162       // array base.
 163       if (sinst->is(ElemArrayU, ElemVecU, ElemDictU, ElemKeysetU)) {
 164         return AElemAny;
 165       }
 166
 167       // These instructions can only get at tvRef when given it as a
 168       // src. Otherwise they can only return pointers to properties or
 169       // &immutable_null_base.
 170       if (sinst->is(PropX, PropDX, PropQ)) {
 171         assertx(sinst->srcs().back()->isA(TMemToMISCell));
 172         auto const src = sinst->srcs().back();
 173         return APropAny | pointee(src, visited_labels);
 174       }
 175
 176       // Like the Prop* instructions, but for array elements. These ops could
 177       // pointers to collection elements, which we don't have AliasClasses for.
 178       if (sinst->is(ElemDX, ElemUX)) {
 179         return AElemAny;
 180       }
 181
 182       return folly::none;
 183     }
 184
 185     return folly::none;
 186   }();
 187
 188   if (specific) return *specific;
 189
 190   /*
 191    * None of the above worked, so try to make the smallest union we can based
 192    * on the pointer type.
 193    */
 194   auto ret = AEmpty;
 195   if (type.maybe(TMemToStkCell))     ret = ret | AStackAny;
 196   if (type.maybe(TMemToFrameCell))   ret = ret | ALocalAny;
 197   if (type.maybe(TMemToPropCell))    ret = ret | APropAny;
 198   if (type.maybe(TMemToElemCell))    ret = ret | AElemAny;
 199   if (type.maybe(TMemToMISCell))     ret = ret | AMIStateTempBase;
 200   if (type.maybe(TMemToClsInitCell)) ret = ret | AHeapAny;
 201   if (type.maybe(TMemToClsCnsCell))  ret = ret | AHeapAny;
 202   if (type.maybe(TMemToSPropCell))   ret = ret | ARdsAny;
 203   return ret;
 204 }
 205
 206 //////////////////////////////////////////////////////////////////////
 207
 208 AliasClass all_pointees(folly::Range<SSATmp**> srcs) {
 209   auto ret = AliasClass{AEmpty};
 210   for (auto const& src : srcs) {
 211     if (src->isA(TMemToCell)) {
 212       ret = ret | pointee(src);
 213     }
 214   }
 215   return ret;
 216 }
 217
 218 // Return an AliasClass containing all locations pointed to by any MemToCell
 219 // sources to an instruction.
 220 AliasClass all_pointees(const IRInstruction& inst) {
 221   return all_pointees(inst.srcs());
 222 }
 223
 224 // Return an AliasClass representing a range of the eval stack that contains
 225 // everything below a logical depth.
 226 template<typename Off>
 227 AliasClass stack_below(SSATmp* base, Off offset) {
 228   return AStack { base, offset, std::numeric_limits<int32_t>::max() };
 229 }
 230
 231 //////////////////////////////////////////////////////////////////////
 232
 233 // Return an AliasClass representing an entire ActRec at base + offset.
 234 AliasClass actrec(SSATmp* base, IRSPRelOffset offset) {
 235   return AStack {
 236     base,
 237     // The offset is the bottom of where the ActRec is stored, but AliasClass
 238     // needs an offset to the highest cell.
 239     offset + int32_t{kNumActRecCells} - 1,
 240     int32_t{kNumActRecCells}
 241   };
 242 }
 243
 244 /*
 245  * AliasClass that can be used to represent effects on liveFrame().
 246  */
 247 AliasClass livefp(SSATmp* fp) {
 248   return AFBasePtr | AActRec { fp };
 249 }
 250
 251 AliasClass livefp(const IRInstruction& inst) {
 252   return livefp(inst.marker().fp());
 253 }
 254
 255 //////////////////////////////////////////////////////////////////////
 256
 257 // Determine an AliasClass representing any locals in the instruction's frame
 258 // which might be accessed via debug_backtrace().
 259
 260 const Func* func_from_fp(SSATmp* fp) {
 261   if (!fp) return nullptr;
 262   auto fpInst = fp->inst();
 263   if (fpInst->is(DefFP)) return fpInst->marker().func();
 264   if (fpInst->is(DefFuncEntryFP)) return fpInst->extra<DefFuncEntryFP>()->func;
 265   if (fpInst->is(BeginInlining)) return fpInst->extra<BeginInlining>()->func;
 266   always_assert(false);
 267 }
 268
 269 bool any_frame_has_metadata(SSATmp* fp) {
 270   while (fp) {
 271     auto const func = func_from_fp(fp);
 272     if (!func || func->lookupVarId(s_86metadata.get()) != kInvalidId) {
 273       return true;
 274     }
 275     fp = fp->inst()->is(BeginInlining) ? fp->inst()->src(1) : nullptr;
 276   }
 277   return false;
 278 }
 279
 280 AliasClass backtrace_locals(const IRInstruction& inst) {
 281   auto eachFunc = [&] (auto fn) {
 282     auto ac = AEmpty;
 283     for (auto fp = inst.marker().fp(); fp; ) {
 284       ac |= fn(func_from_fp(fp), fp);
 285       fp = fp->inst()->is(BeginInlining) ? fp->inst()->src(1) : nullptr;
 286     }
 287     return ac;
 288   };
 289
 290   auto const add86meta = [&] (const Func* func, SSATmp* fp) -> AliasClass {
 291     // The 86metadata variable can also exist in a VarEnv, but accessing that is
 292     // considered a heap effect, so we can ignore it.
 293     auto const local = func->lookupVarId(s_86metadata.get());
 294     if (local == kInvalidId) return AEmpty;
 295     return ALocal { fp, (uint32_t)local };
 296   };
 297
 298   // Either there's no func or no frame-pointer. Either way, be conservative and
 299   // assume anything can be read. This can happen in test code, for instance.
 300   if (!inst.marker().fp()) return ALocalAny;
 301
 302   if (!RuntimeOption::EnableArgsInBacktraces) return eachFunc(add86meta);
 303
 304   return eachFunc([&] (const Func* func, SSATmp* fp) {
 305     auto ac = AEmpty;
 306     auto const numParams = func->numParams();
 307
 308     if (func->hasReifiedGenerics()) {
 309       // First non param local contains reified generics
 310       AliasIdSet reifiedgenerics{ AliasIdSet::IdRange{numParams, numParams + 1} };
 311       ac |= ALocal { fp, reifiedgenerics };
 312     }
 313
 314     if (func->cls() && func->cls()->hasReifiedGenerics()) {
 315       // There is no way to access the SSATmp for ObjectData of `this` here,
 316       // so be very pessimistic
 317       ac |= APropAny;
 318     }
 319
 320     if (!numParams) return add86meta(func, fp) | ac;
 321
 322     AliasIdSet params{ AliasIdSet::IdRange{0, numParams} };
 323     return add86meta(func, fp) | ac | ALocal { fp, params };
 324   });
 325 }
 326
 327 /////////////////////////////////////////////////////////////////////
 328
 329 /*
 330  * Modify a GeneralEffects to take potential VM re-entry into account.  This
 331  * affects may-load, may-store, and kills information for the instruction.  The
 332  * GeneralEffects should already contain AHeapAny in both loads and stores if
 333  * it affects those locations for reasons other than re-entry, but does not
 334  * need to if it doesn't.
 335  *
 336  * For loads, we need to take into account any locals potentially accessed by
 337  * debug_backtrace().
 338  *
 339  * For kills, locations on the eval stack below the re-entry depth should all
 340  * be added.
 341  */
 342 GeneralEffects may_reenter(const IRInstruction& inst, GeneralEffects x) {
 343   auto const may_reenter_is_ok =
 344     inst.taken() && inst.taken()->isCatch();
 345   always_assert_flog(
 346     may_reenter_is_ok,
 347     "instruction {} claimed may_reenter, but it isn't allowed to say that",
 348     inst
 349   );
 350
 351   /*
 352    * We want to union `killed_stack' into whatever else the instruction already
 353    * said it must kill, but if we end up with an unrepresentable AliasClass we
 354    * can't return a set that's too big (the `kills' set is unlike the other
 355    * AliasClasses in GeneralEffects in that means it kills /everything/ in the
 356    * set, since it's must-information).
 357    *
 358    * If we can't represent the union, just take the stack, in part because we
 359    * have some debugging asserts about this right now---but also nothing
 360    * actually uses may_reenter with a non-AEmpty kills at the time of this
 361    * writing anyway.
 362    */
 363   auto const new_kills = [&] {
 364     if (inst.marker().fp() == nullptr) return AEmpty;
 365
 366     auto const killed_stack = stack_below(
 367       inst.marker().fp(),
 368       -inst.marker().spOff() - 1
 369     );
 370     auto const kills_union = x.kills.precise_union(killed_stack);
 371     return kills_union ? *kills_union : killed_stack;
 372   }();
 373
 374   return GeneralEffects {
 375     x.loads | AHeapAny | backtrace_locals(inst),
 376     x.stores | AHeapAny,
 377     x.moves,
 378     new_kills
 379   };
 380 }
 381
 382 //////////////////////////////////////////////////////////////////////
 383
 384 GeneralEffects may_load_store(AliasClass loads, AliasClass stores) {
 385   return GeneralEffects { loads, stores, AEmpty, AEmpty };
 386 }
 387
 388 GeneralEffects may_load_store_kill(AliasClass loads,
 389                                    AliasClass stores,
 390                                    AliasClass kill) {
 391   return GeneralEffects { loads, stores, AEmpty, kill };
 392 }
 393
 394 GeneralEffects may_load_store_move(AliasClass loads,
 395                                    AliasClass stores,
 396                                    AliasClass move) {
 397   assertx(move <= loads);
 398   return GeneralEffects { loads, stores, move, AEmpty };
 399 }
 400
 401 //////////////////////////////////////////////////////////////////////
 402
 403 /*
 404  * Helper for iterator instructions.  They all affect some locals, but are
 405  * otherwise the same. Value iters touch one local; key-value iters touch two.
 406  */
 407 GeneralEffects iter_effects(const IRInstruction& inst,
 408                             SSATmp* fp,
 409                             AliasClass locals) {
 410   auto const iters =
 411     AliasClass { aiter_all(fp, inst.extra<IterData>()->args.iterId) };
 412   return may_load_store_kill(
 413     iters | locals | AHeapAny,
 414     iters | locals | AHeapAny,
 415     AMIStateAny
 416   );
 417 }
 418
 419 /*
 420  * Construct effects for InterpOne, using the information in its extra data.
 421  *
 422  * We always consider an InterpOne as potentially doing anything to the heap,
 423  * potentially re-entering, potentially raising warnings in the current frame,
 424  * potentially reading any locals, and potentially reading/writing any stack
 425  * location that isn't below the bottom of the stack.
 426  *
 427  * The extra data for the InterpOne comes with some additional information
 428  * about which local(s) it may modify, which is all we try to be more precise
 429  * about right now.
 430  */
 431 GeneralEffects interp_one_effects(const IRInstruction& inst) {
 432   auto const extra  = inst.extra<InterpOne>();
 433   auto loads  = AHeapAny | AStackAny | ALocalAny | ARdsAny | livefp(inst);
 434   auto stores = AHeapAny | AStackAny | ARdsAny;
 435   if (extra->smashesAllLocals) {
 436     stores = stores | ALocalAny;
 437   } else {
 438     for (auto i = uint32_t{0}; i < extra->nChangedLocals; ++i) {
 439       stores = stores | ALocal { inst.src(1), extra->changedLocals[i].id };
 440     }
 441   }
 442
 443   auto kills = AEmpty;
 444   if (isMemberBaseOp(extra->opcode)) {
 445     stores = stores | AMIStateAny;
 446     kills = kills | AMIStateAny;
 447   } else if (isMemberDimOp(extra->opcode) || isMemberFinalOp(extra->opcode)) {
 448     stores = stores | AMIStateAny;
 449     loads = loads | AMIStateAny;
 450   } else {
 451     kills = kills | AMIStateAny;
 452   }
 453
 454   return may_load_store_kill(loads, stores, kills);
 455 }
 456
 457 ////////////////////////////////////////////////////////////////////////////////
 458
 459 /*
 460  * Construct effects for member instructions that take &tvRef as their last
 461  * argument.
 462  *
 463  * These instructions never load tvRef, but they might store to it.
 464  */
 465 MemEffects minstr_with_tvref(const IRInstruction& inst) {
 466   auto const srcs = inst.srcs();
 467   assertx(srcs.back()->isA(TMemToMISCell));
 468   auto const loads = AHeapAny | all_pointees(srcs.subpiece(0, srcs.size() - 1));
 469   auto const stores = AHeapAny | all_pointees(inst);
 470   return may_load_store(loads, stores);
 471 }
 472
 473 //////////////////////////////////////////////////////////////////////
 474
 475 MemEffects memory_effects_impl(const IRInstruction& inst) {
 476   switch (inst.op()) {
 477
 478   //////////////////////////////////////////////////////////////////////
 479   // Region exits
 480
 481   // These exits don't leave the current php function, and could head to code
 482   // that could read or write anything as far as we know (including frame
 483   // locals).
 484   case ReqBindJmp:
 485     return ExitEffects {
 486       AUnknown,
 487       stack_below(inst.src(0), inst.extra<ReqBindJmp>()->irSPOff - 1)
 488     };
 489   case ReqRetranslate:
 490     return ExitEffects {
 491       AUnknown,
 492       stack_below(inst.src(0), inst.extra<ReqRetranslate>()->irSPOff - 1)
 493     };
 494   case ReqRetranslateOpt:
 495     return ExitEffects {
 496       AUnknown,
 497       stack_below(inst.src(0), inst.extra<ReqRetranslateOpt>()->offset - 1)
 498     };
 499   case JmpSwitchDest:
 500     return ExitEffects {
 501       AUnknown,
 502       *stack_below(inst.src(1),
 503                    inst.extra<JmpSwitchDest>()->spOffBCFromIRSP - 1).
 504         precise_union(AMIStateAny)
 505     };
 506   case JmpSSwitchDest:
 507     return ExitEffects {
 508       AUnknown,
 509       *stack_below(inst.src(1),
 510                    inst.extra<JmpSSwitchDest>()->offset - 1).
 511         precise_union(AMIStateAny)
 512     };
 513
 514   //////////////////////////////////////////////////////////////////////
 515   // Unusual instructions
 516
 517   /*
 518    * The ReturnHook sets up the ActRec so the unwinder knows everything is
 519    * already released (i.e. it calls ar->setLocalsDecRefd()).
 520    *
 521    * The eval stack is also dead at this point (the return value is passed to
 522    * ReturnHook as src(1), and the ReturnHook may not access the stack).
 523    */
 524   case ReturnHook:
 525     return may_load_store_kill(
 526       AHeapAny | AActRec {inst.src(0)}, AHeapAny,
 527       *AStackAny.precise_union(ALocalAny)->precise_union(AMIStateAny)
 528     );
 529
 530   // The suspend hooks can load anything (re-entering the VM), but can't write
 531   // to frame locals.
 532   case SuspendHookAwaitEF:
 533   case SuspendHookAwaitEG:
 534   case SuspendHookAwaitR:
 535   case SuspendHookCreateCont:
 536   case SuspendHookYield:
 537     // TODO: may-load here probably doesn't need to include ALocalAny normally.
 538     return may_load_store_kill(AUnknown, AHeapAny, AMIStateAny);
 539
 540   /*
 541    * If we're returning from a function, it's ReturnEffects.  The RetCtrl
 542    * opcode also suspends resumables, which we model as having any possible
 543    * effects.
 544    */
 545   case RetCtrl:
 546     if (inst.extra<RetCtrl>()->suspendingResumed) {
 547       // Suspending can go anywhere, and doesn't even kill locals.
 548       return UnknownEffects {};
 549     }
 550     return ReturnEffects {
 551       AStackAny | ALocalAny | AMIStateAny | AFBasePtr
 552     };
 553
 554   case AsyncFuncRet:
 555   case AsyncFuncRetSlow:
 556     return ReturnEffects { AStackAny | AMIStateAny | livefp(inst.src(1)) };
 557
 558   case AsyncSwitchFast:
 559     // Suspending can go anywhere, and doesn't even kill locals.
 560     return UnknownEffects {};
 561
 562   case GenericRetDecRefs:
 563     /*
 564      * The may-store information here is AUnknown: even though we know it
 565      * doesn't really "store" to the frame locals, the values that used to be
 566      * there are no longer available because they are DecRef'd, which we are
 567      * required to report as may-store information to make it visible to
 568      * reference count optimizations.  It's conceptually the same as if it was
 569      * storing an Uninit over each of the locals, but the stores of uninits
 570      * would be dead so we're not actually doing that.
 571      */
 572     return may_load_store_kill(AUnknown, AUnknown, AMIStateAny);
 573
 574   case EndCatch: {
 575     auto const stack_kills = stack_below(
 576       inst.src(1),
 577       inst.extra<EndCatch>()->offset - 1
 578     );
 579     return ExitEffects {
 580       AUnknown,
 581       stack_kills | AMIStateTempBase | AMIStateBase
 582     };
 583   }
 584
 585   case EnterTCUnwind: {
 586     auto const stack_kills = stack_below(
 587       inst.marker().fp(),
 588       -inst.marker().spOff() - 1
 589     );
 590     return ExitEffects {
 591       AUnknown,
 592       stack_kills | AMIStateTempBase | AMIStateBase
 593     };
 594   }
 595
 596   /*
 597    * BeginInlining must always be the first instruction in the inlined call. It
 598    * defines a new FP for the callee but does not perform any stores or
 599    * otherwise initialize the FP.
 600    */
 601   case BeginInlining: {
 602     /*
 603      * SP relative offset of the firstin the inlined call.
 604      */
 605     auto inlineStackOff =
 606       inst.extra<BeginInlining>()->spOffset + kNumActRecCells - 1;
 607     return may_load_store_kill(
 608       AEmpty,
 609       AEmpty,
 610       /*
 611        * This prevents stack slots from the caller from being sunk into the
 612        * callee. Note that some of these stack slots overlap with the frame
 613        * locals of the callee-- those slots are inacessible in the inlined
 614        * call as frame and stack locations may not alias.
 615        */
 616       stack_below(inst.src(0), inlineStackOff)
 617     );
 618   }
 619
 620   case EndInlining: {
 621     assertx(inst.src(0)->inst()->is(BeginInlining));
 622     auto const fp = inst.src(0);
 623     auto const callee = inst.src(0)->inst()->extra<BeginInlining>()->func;
 624     const AliasClass ar = AActRec { inst.src(0) };
 625     auto const locals = [&] () -> AliasClass {
 626       if (!callee->numLocals()) return AEmpty;
 627       return ALocal {fp, AliasIdSet::IdRange(0, callee->numLocals())};
 628     }();
 629
 630     // NB: It's okay if the AliasIdSet for locals cannot be precise. We want to
 631     //     kill *every* local in the frame so there's nothing else that can
 632     //     accidentally be included in the set.
 633     return may_load_store_kill(AEmpty, AEmpty, ar | locals | AMIStateAny);
 634   }
 635
 636   case InlineCall:
 637     return PureInlineCall {
 638       AFBasePtr,
 639       inst.src(0),
 640
 641       // Right now when we "publish" a frame by storing it in rvmfp() we
 642       // implicitly depend on the AFFunc and AFMeta bits being stored. In the
 643       // future we may want to track this explicitly.
 644       //
 645       // We also need to ensure that all of our parent frames have this stored
 646       // this information. To achieve this we also register a load on AFBasePtr,
 647       // forcing them to also be published. Notice that we doin't actually
 648       // depend on this load to properly initialize m_sfp or rvmfp().
 649       AliasClass(AFFunc { inst.src(0) }) | AFMeta { inst.src(0) } | AFBasePtr
 650     };
 651
 652   case InlineReturn:
 653     // Unlike InlineCall we don't need to explicitly require the frame be
 654     // published. Unlike InlineCall, however, it is not safe to "move" an
 655     // InlineReturn, it may only be killed once it has been made redundant by
 656     // the removal of its associated InlineCall.
 657     return PureInlineReturn { AFBasePtr, inst.src(0), inst.src(1) };
 658
 659   case SyncReturnBC: {
 660     auto const spOffset = inst.extra<SyncReturnBC>()->spOffset;
 661     auto const arStack = actrec(inst.src(0), spOffset);
 662     return may_load_store(AEmpty, arStack);
 663   }
 664
 665   case InterpOne:
 666     return interp_one_effects(inst);
 667   case InterpOneCF:
 668     return ExitEffects {
 669       AUnknown,
 670       stack_below(inst.src(1), -inst.marker().spOff() - 1) | AMIStateAny
 671     };
 672
 673   case NativeImpl:
 674     return UnknownEffects {};
 675
 676   // NB: on the failure path, these C++ helpers do a fixup and read frame
 677   // locals before they throw.  They can also invoke the user error handler and
 678   // go do whatever they want to non-frame locations.
 679   //
 680   // TODO(#5372569): if we combine dv inits into the same regions we could
 681   // possibly avoid storing KindOfUninits if we modify this.
 682   case VerifyParamCallable:
 683   case VerifyParamCls:
 684   case VerifyParamFailHard:
 685   case VerifyParamRecDesc:
 686     return may_load_store(AUnknown, AHeapAny);
 687   // VerifyParamFail might coerce the parameter to the desired type rather than
 688   // throwing.
 689   case VerifyParamFail: {
 690     auto const extra = inst.extra<ParamWithTCData>();
 691     assertx(extra->paramId >= 0);
 692     auto const stores =
 693       AHeapAny |
 694       ALocal{inst.marker().fp(), safe_cast<uint32_t>(extra->paramId)};
 695     return may_load_store(AUnknown, stores);
 696   }
 697   case VerifyReifiedLocalType: {
 698     auto const extra = inst.extra<ParamData>();
 699     assertx(extra->paramId >= 0);
 700     auto const stores =
 701       AHeapAny |
 702       ALocal{inst.marker().fp(), safe_cast<uint32_t>(extra->paramId)};
 703     return may_load_store(AUnknown, stores);
 704   }
 705   // However the following ones can't read locals from our frame on the way
 706   // out, except as a side effect of raising a warning.
 707   case VerifyRetCallable:
 708   case VerifyRetCls:
 709   case VerifyReifiedReturnType:
 710   case VerifyRetRecDesc:
 711     return may_load_store(AHeapAny | livefp(inst), AHeapAny);
 712
 713   case VerifyRetFail:
 714   case VerifyRetFailHard:
 715     return may_load_store(AHeapAny | AStackAny | livefp(inst), AHeapAny);
 716
 717   case VerifyPropCls:
 718   case VerifyPropFail:
 719   case VerifyPropFailHard:
 720   case VerifyProp:
 721   case VerifyPropAll:
 722   case VerifyPropCoerce:
 723   case VerifyPropCoerceAll:
 724   case VerifyPropRecDesc:
 725     return may_load_store(AHeapAny | livefp(inst), AHeapAny);
 726
 727   case CallUnpack:
 728     {
 729       auto const extra = inst.extra<CallUnpack>();
 730       return CallEffects {
 731         // Kills. Everything on the stack below the incoming parameters.
 732         stack_below(inst.src(0), extra->spOffset - 1) | AMIStateAny,
 733         // Input arguments.
 734         extra->numInputs() == 0 ? AEmpty : AStack {
 735           inst.src(0),
 736           extra->spOffset + extra->numInputs() - 1,
 737           static_cast<int32_t>(extra->numInputs())
 738         },
 739         // ActRec.
 740         actrec(inst.src(0), extra->spOffset + extra->numInputs()),
 741         // Inout outputs.
 742         extra->numOut == 0 ? AEmpty : AStack {
 743           inst.src(0),
 744           extra->spOffset + extra->numInputs() + kNumActRecCells +
 745             extra->numOut - 1,
 746           static_cast<int32_t>(extra->numOut)
 747         },
 748         // Locals.
 749         backtrace_locals(inst) | livefp(inst.src(1))
 750       };
 751     }
 752
 753   case ContEnter:
 754     {
 755       auto const extra = inst.extra<ContEnter>();
 756       return CallEffects {
 757         // Kills. Everything on the stack.
 758         stack_below(inst.src(0), extra->spOffset) | AMIStateAny,
 759         // No inputs. The value being sent is passed explicitly.
 760         AEmpty,
 761         // ActRec. It is on the heap and we already implicitly assume that
 762         // CallEffects can perform arbitrary heap operations.
 763         AEmpty,
 764         // No outputs.
 765         AEmpty,
 766         // Locals.
 767         backtrace_locals(inst) | livefp(inst.src(1))
 768       };
 769     }
 770
 771   case Call:
 772     {
 773       // If any frames in the inlined stack have metadata we need to materialize
 774       // all of the frames so that debug_backtrace() can find it.
 775       AliasClass ar = any_frame_has_metadata(inst.src(1))
 776         ? livefp(inst.src(1))
 777         : AliasClass(AActRec {inst.src(1)});
 778       auto const extra = inst.extra<Call>();
 779       return CallEffects {
 780         // Kills. Everything on the stack below the incoming parameters.
 781         stack_below(inst.src(0), extra->spOffset - 1) | AMIStateAny,
 782         // Input arguments.
 783         extra->numInputs() == 0 ? AEmpty : AStack {
 784           inst.src(0),
 785           extra->spOffset + extra->numInputs() - 1,
 786           static_cast<int32_t>(extra->numInputs())
 787         },
 788         // ActRec.
 789         actrec(inst.src(0), extra->spOffset + extra->numInputs()),
 790         // Inout outputs.
 791         extra->numOut == 0 ? AEmpty : AStack {
 792           inst.src(0),
 793           extra->spOffset + extra->numInputs() + kNumActRecCells +
 794             extra->numOut - 1,
 795           static_cast<int32_t>(extra->numOut)
 796         },
 797         // Locals. We intentionally leave off a dependency on AFBasePtr to allow
 798         // store-elim to elide the new frame.
 799         backtrace_locals(inst) | ar
 800       };
 801     }
 802
 803   case CallBuiltin:
 804     {
 805       AliasClass out_stk = AEmpty;
 806       auto const callee = inst.extra<CallBuiltin>()->callee;
 807       auto const stk = [&] () -> AliasClass {
 808         AliasClass ret = AEmpty;
 809         for (auto i = uint32_t{2}; i < inst.numSrcs(); ++i) {
 810           if (inst.src(i)->type() <= TPtrToCell) {
 811             auto const cls = pointee(inst.src(i));
 812             if (cls.maybe(AStackAny)) {
 813               ret = ret | cls;
 814               auto const paramOff = callee->isMethod() ? 3 : 2;
 815               if (i >= paramOff && callee->isInOut(i - paramOff)) {
 816                 out_stk = out_stk | cls;
 817               }
 818             }
 819           }
 820         }
 821         return ret;
 822       }();
 823       if (callee->isFoldable()) {
 824         return may_load_store_kill(
 825           stk | AHeapAny, out_stk | AHeapAny, AMIStateAny
 826         );
 827       } else {
 828         return may_load_store_kill(
 829           stk | AHeapAny | ARdsAny,
 830           out_stk | AHeapAny | ARdsAny,
 831           AMIStateAny
 832         );
 833       }
 834     }
 835
 836   // Resumable suspension takes everything from the frame and moves it into the
 837   // heap.
 838   case CreateGen:
 839   case CreateAGen:
 840   case CreateAFWH:
 841   case CreateAFWHNoVV: {
 842     auto const fp = canonical(inst.src(0));
 843     auto fpInst = fp->inst();
 844     auto const frame = [&] () -> AliasClass {
 845       if (fpInst->is(DefFP, DefFuncEntryFP)) return ALocalAny;
 846       assertx(fpInst->is(BeginInlining));
 847       auto const nlocals = fpInst->extra<BeginInlining>()->func->numLocals();
 848       return nlocals
 849         ? ALocal { fp, AliasIdSet::IdRange(0, nlocals)}
 850         : AEmpty;
 851     }();
 852     return may_load_store_move(
 853       frame | AActRec { fp },
 854       AHeapAny,
 855       frame
 856     );
 857   }
 858
 859   // AGWH construction updates the AsyncGenerator object.
 860   case CreateAGWH:
 861     return may_load_store(AHeapAny | AActRec { inst.src(0) }, AHeapAny);
 862
 863   case CreateAAWH:
 864     {
 865       auto const extra = inst.extra<CreateAAWH>();
 866       auto const frame = ALocal {
 867         inst.src(0),
 868         AliasIdSet {
 869           AliasIdSet::IdRange{ extra->first, extra->first + extra->count }
 870         }
 871       };
 872       return may_load_store(frame, AHeapAny);
 873     }
 874
 875   case CountWHNotDone:
 876     {
 877       auto const extra = inst.extra<CountWHNotDone>();
 878       auto const frame = ALocal {
 879         inst.src(0),
 880         AliasIdSet {
 881           AliasIdSet::IdRange{ extra->first, extra->first + extra->count }
 882         }
 883       };
 884       return may_load_store(frame, AEmpty);
 885     }
 886
 887   // This re-enters to call extension-defined instance constructors.
 888   case ConstructInstance:
 889     return may_load_store(AHeapAny, AHeapAny);
 890
 891   // Closures don't ever throw or reenter on construction
 892   case ConstructClosure:
 893     return IrrelevantEffects{};
 894
 895   case CheckStackOverflow:
 896   case CheckSurpriseFlagsEnter:
 897   case CheckSurpriseAndStack:
 898     return may_load_store(AEmpty, AEmpty);
 899
 900   //////////////////////////////////////////////////////////////////////
 901   // Iterator instructions
 902
 903   case IterInit:
 904   case LIterInit:
 905   case IterNext:
 906   case LIterNext: {
 907     auto const& args = inst.extra<IterData>()->args;
 908     assertx(!args.hasKey());
 909     auto const fp = inst.src(inst.op() == IterNext ? 0 : 1);
 910     AliasClass val = ALocal { fp, safe_cast<uint32_t>(args.valId) };
 911     return iter_effects(inst, fp, val);
 912   }
 913
 914   case IterInitK:
 915   case LIterInitK:
 916   case IterNextK:
 917   case LIterNextK: {
 918     auto const& args = inst.extra<IterData>()->args;
 919     assertx(args.hasKey());
 920     auto const fp = inst.src(inst.op() == IterNextK ? 0 : 1);
 921     AliasClass key = ALocal { fp, safe_cast<uint32_t>(args.keyId) };
 922     AliasClass val = ALocal { fp, safe_cast<uint32_t>(args.valId) };
 923     return iter_effects(inst, fp, key | val);
 924   }
 925
 926   case IterFree: {
 927     auto const base = aiter_base(inst.src(0), iterId(inst));
 928     return may_load_store(AHeapAny | base, AHeapAny);
 929   }
 930
 931   case CheckIter: {
 932     auto const iter = inst.extra<CheckIter>()->iterId;
 933     return may_load_store(aiter_type(inst.src(0), iter), AEmpty);
 934   }
 935
 936   case LdIterBase:
 937     return PureLoad { aiter_base(inst.src(0), iterId(inst)) };
 938
 939   case LdIterPos:
 940     return PureLoad { aiter_pos(inst.src(0), iterId(inst)) };
 941
 942   case LdIterEnd:
 943     return PureLoad { aiter_end(inst.src(0), iterId(inst)) };
 944
 945   case StIterBase:
 946     return PureStore { aiter_base(inst.src(0), iterId(inst)), inst.src(1) };
 947
 948   case StIterType: {
 949     auto const iter = inst.extra<StIterType>()->iterId;
 950     return PureStore { aiter_type(inst.src(0), iter), nullptr };
 951   }
 952
 953   case StIterPos:
 954     return PureStore { aiter_pos(inst.src(0), iterId(inst)), inst.src(1) };
 955
 956   case StIterEnd:
 957     return PureStore { aiter_end(inst.src(0), iterId(inst)), inst.src(1) };
 958
 959   case KillIter: {
 960     auto const iters = aiter_all(inst.src(0), iterId(inst));
 961     return may_load_store_kill(AEmpty, AEmpty, iters);
 962   }
 963
 964   //////////////////////////////////////////////////////////////////////
 965   // Instructions that explicitly manipulate locals
 966
 967   case StLoc:
 968     return PureStore {
 969       ALocal { inst.src(0), inst.extra<StLoc>()->locId },
 970       inst.src(1),
 971       nullptr
 972     };
 973
 974   case StLocRange:
 975     {
 976       auto const extra = inst.extra<StLocRange>();
 977       auto acls = AEmpty;
 978
 979       for (auto locId = extra->start; locId < extra->end; ++locId) {
 980         acls = acls | ALocal { inst.src(0), locId };
 981       }
 982       return PureStore { acls, inst.src(1), nullptr };
 983     }
 984
 985   case LdLoc:
 986     return PureLoad { ALocal { inst.src(0), inst.extra<LocalId>()->locId } };
 987
 988   case CheckLoc:
 989   case LdLocPseudoMain:
 990     // Note: LdLocPseudoMain is both a guard and a load, so it must not be a
 991     // PureLoad.
 992     return may_load_store(
 993       ALocal { inst.src(0), inst.extra<LocalId>()->locId },
 994       AEmpty
 995     );
 996
 997   case StLocPseudoMain:
 998     // This can store to globals or locals, but we don't have globals supported
 999     // in AliasClass yet.
1000     return PureStore { AUnknown, inst.src(1), nullptr };
1001
1002   //////////////////////////////////////////////////////////////////////
1003   // Pointer-based loads and stores
1004
1005   case LdMem:
1006     return PureLoad { pointee(inst.src(0)) };
1007   case StMem:
1008     return PureStore { pointee(inst.src(0)), inst.src(1), inst.src(0) };
1009
1010   case StImplicitContext:
1011     return may_load_store(AEmpty, AEmpty);
1012
1013   case LdClsInitElem:
1014     return PureLoad { AHeapAny };
1015
1016   case StClsInitElem:
1017     return PureStore { AHeapAny };
1018
1019   case LdPairElem:
1020     return PureLoad { AHeapAny };
1021
1022   case LdMBase:
1023     return PureLoad { AMIStateBase };
1024
1025   case StMBase:
1026     return PureStore { AMIStateBase, inst.src(0), nullptr };
1027
1028   case FinishMemberOp:
1029     return may_load_store_kill(AEmpty, AEmpty, AMIStateAny);
1030
1031   case IsNTypeMem:
1032   case IsTypeMem:
1033   case CheckTypeMem:
1034   case CheckInitMem:
1035     return may_load_store(pointee(inst.src(0)), AEmpty);
1036
1037   case CheckRDSInitialized:
1038     return may_load_store(
1039       ARds { inst.extra<CheckRDSInitialized>()->handle },
1040       AEmpty
1041     );
1042   case MarkRDSInitialized:
1043     return may_load_store(
1044       AEmpty,
1045       ARds { inst.extra<MarkRDSInitialized>()->handle }
1046     );
1047
1048   case InitProps:
1049     return may_load_store(
1050       AHeapAny,
1051       AHeapAny | ARds { inst.extra<InitProps>()->cls->propHandle() }
1052     );
1053
1054   case InitSProps:
1055     return may_load_store(
1056       AHeapAny,
1057       AHeapAny | ARds { inst.extra<InitSProps>()->cls->sPropInitHandle() }
1058     );
1059
1060   case LdClsFromClsMeth:
1061   case LdFuncFromClsMeth:
1062   case LdFuncFromRFunc:
1063   case LdGenericsFromRFunc:
1064   case LdClsFromRClsMeth:
1065   case LdFuncFromRClsMeth:
1066   case LdGenericsFromRClsMeth:
1067     return may_load_store(AEmpty, AEmpty);
1068
1069   //////////////////////////////////////////////////////////////////////
1070   // Object/Ref loads/stores
1071
1072   case InitObjProps:
1073     return may_load_store(AEmpty, APropAny);
1074
1075   case InitObjMemoSlots:
1076     // Writes to memo slots, but these are not modeled.
1077     return IrrelevantEffects {};
1078
1079   case LockObj:
1080     // Writes object attributes, but these are not modeled.
1081     return IrrelevantEffects {};
1082
1083   // Loads $obj->trace, stores $obj->file and $obj->line.
1084   case InitThrowableFileAndLine:
1085     return may_load_store(AHeapAny, APropAny);
1086
1087   //////////////////////////////////////////////////////////////////////
1088   // Array loads and stores
1089
1090   case InitPackedLayoutArray: {
1091     auto const arr = inst.src(0);
1092     auto const val = inst.src(1);
1093     auto const idx = inst.extra<InitPackedLayoutArray>()->index;
1094     return PureStore { AElemI { arr, idx }, val, arr };
1095   }
1096
1097   case InitMixedLayoutArray: {
1098     auto const arr = inst.src(0);
1099     auto const val = inst.src(1);
1100     auto const key = inst.extra<InitMixedLayoutArray>()->key;
1101     return PureStore { AElemS { arr, key }, val, arr };
1102   }
1103
1104   case LdVecElem:
1105   case LdPackedElem: {
1106     auto const base = inst.src(0);
1107     auto const key  = inst.src(1);
1108     return PureLoad {
1109       key->hasConstVal() ? AElemI { base, key->intVal() } : AElemIAny
1110     };
1111   }
1112
1113   case InitPackedLayoutArrayLoop:
1114     {
1115       auto const extra = inst.extra<InitPackedLayoutArrayLoop>();
1116       auto const stack_in = AStack {
1117         inst.src(1),
1118         extra->offset + static_cast<int32_t>(extra->size) - 1,
1119         static_cast<int32_t>(extra->size)
1120       };
1121       return may_load_store_move(stack_in, AElemIAny, stack_in);
1122     }
1123
1124   case NewKeysetArray:
1125     {
1126       // NewKeysetArray is reading elements from the stack, but writes to a
1127       // completely new array, so we can treat the store set as empty.
1128       auto const extra = inst.extra<NewKeysetArray>();
1129       auto const stack_in = AStack {
1130         inst.src(0),
1131         extra->offset + static_cast<int32_t>(extra->size) - 1,
1132         static_cast<int32_t>(extra->size)
1133       };
1134       return may_load_store_move(stack_in, AEmpty, stack_in);
1135     }
1136
1137   case NewStructDArray:
1138   case NewStructDict:
1139     {
1140       // NewStructArray is reading elements from the stack, but writes to a
1141       // completely new array, so we can treat the store set as empty.
1142       auto const extra = inst.extra<NewStructData>();
1143       auto const stack_in = AStack {
1144         inst.src(0),
1145         extra->offset + static_cast<int32_t>(extra->numKeys) - 1,
1146         static_cast<int32_t>(extra->numKeys)
1147       };
1148       return may_load_store_move(stack_in, AEmpty, stack_in);
1149     }
1150
1151   case NewRecord:
1152     {
1153       auto const extra = inst.extra<NewStructData>();
1154       auto const stack_in = AStack {
1155         inst.src(1),
1156         extra->offset + static_cast<int32_t>(extra->numKeys) - 1,
1157         static_cast<int32_t>(extra->numKeys)
1158       };
1159       return may_load_store_move(stack_in, AEmpty, stack_in);
1160     }
1161   case MemoGetStaticValue:
1162   case MemoGetLSBValue:
1163   case MemoGetInstanceValue:
1164     // Only reads the memo value (which isn't modeled here).
1165     return may_load_store(AEmpty, AEmpty);
1166
1167   case MemoSetStaticValue:
1168   case MemoSetLSBValue:
1169   case MemoSetInstanceValue:
1170     // Writes to the memo value (which isn't modeled)
1171     return may_load_store(AEmpty, AEmpty);
1172
1173   case MemoGetStaticCache:
1174   case MemoGetLSBCache:
1175   case MemoSetStaticCache:
1176   case MemoSetLSBCache: {
1177     // Reads some (non-zero) set of locals for keys, and reads/writes from the
1178     // memo cache (which isn't modeled).
1179     auto const extra = inst.extra<MemoCacheStaticData>();
1180     auto const frame = ALocal {
1181       inst.src(0),
1182       AliasIdSet{
1183         AliasIdSet::IdRange{
1184           extra->keys.first,
1185           extra->keys.first + extra->keys.count
1186         }
1187       }
1188     };
1189
1190     return may_load_store(frame, AEmpty);
1191   }
1192
1193   case MemoGetInstanceCache:
1194   case MemoSetInstanceCache: {
1195     // Reads some set of locals for keys, and reads/writes from the memo cache
1196     // (which isn't modeled).
1197     auto const extra = inst.extra<MemoCacheInstanceData>();
1198     auto const frame = [&]() -> AliasClass {
1199       // Unlike MemoGet/SetStaticCache, we can have an empty key range here.
1200       if (extra->keys.count == 0) return AEmpty;
1201
1202       return ALocal {
1203         inst.src(0),
1204         AliasIdSet{
1205           AliasIdSet::IdRange{
1206             extra->keys.first,
1207             extra->keys.first + extra->keys.count
1208           }
1209         }
1210       };
1211     }();
1212     return may_load_store(frame, AEmpty);
1213   }
1214
1215   case MixedArrayGetK:
1216   case DictGetK:
1217   case KeysetGetK: {
1218     auto const base = inst.src(0);
1219     auto const key  = inst.src(1);
1220     always_assert(key->isA(TInt | TStr));
1221     if (key->isA(TInt)) {
1222       return PureLoad {
1223         key->hasConstVal() ? AElemI { base, key->intVal() } : AElemIAny
1224       };
1225     }
1226     if (key->isA(TStr)) {
1227       return PureLoad {
1228         key->hasConstVal() ? AElemS { base, key->strVal() } : AElemSAny
1229       };
1230     }
1231     return PureLoad { AElemAny };
1232   }
1233
1234   case LdPtrIterKey:
1235     // Array element keys are not tracked by memory effects right now.
1236     return may_load_store(AEmpty, AEmpty);
1237
1238   case LdPtrIterVal: {
1239     // NOTE: The type param for this op restricts the key, not the value.
1240     if (inst.typeParam() <= TInt) return PureLoad { AElemIAny };
1241     if (inst.typeParam() <= TStr) return PureLoad { AElemSAny };
1242     return PureLoad { AElemAny };
1243   }
1244
1245   case ElemMixedArrayK:
1246   case ElemDictK:
1247   case ElemKeysetK:
1248     return IrrelevantEffects {};
1249
1250   case VecFirst: {
1251     auto const base = inst.src(0);
1252     return may_load_store(AElemI { base, 0 }, AEmpty);
1253   }
1254   case VecLast: {
1255     auto const base = inst.src(0);
1256     if (base->hasConstVal(TArr)) {
1257       return may_load_store(
1258           AElemI { base, static_cast<int64_t>(base->arrVal()->size() - 1) },
1259           AEmpty);
1260     }
1261     return may_load_store(AElemIAny, AEmpty);
1262   }
1263   case DictFirst:
1264   case DictLast:
1265   case KeysetFirst:
1266   case KeysetLast:
1267     return may_load_store(AElemAny, AEmpty);
1268
1269   case DictFirstKey:
1270   case DictLastKey:
1271     return may_load_store(AEmpty, AEmpty);
1272
1273   case CheckMixedArrayKeys:
1274   case CheckMixedArrayOffset:
1275   case CheckDictOffset:
1276   case CheckKeysetOffset:
1277   case CheckMissingKeyInArrLike:
1278   case ProfileMixedArrayAccess:
1279   case ProfileDictAccess:
1280   case ProfileKeysetAccess:
1281   case CheckArrayCOW:
1282     return may_load_store(AHeapAny, AEmpty);
1283
1284   case ArrayIsset:
1285   case AKExistsArr:
1286     return may_load_store(AElemAny, AEmpty);
1287
1288   case ArrayIdx:
1289     return may_load_store(AElemAny, AEmpty);
1290
1291   case SameArr:
1292   case NSameArr:
1293     return may_load_store(AEmpty, AEmpty);
1294
1295   case DictGetQuiet:
1296   case DictIsset:
1297   case DictIdx:
1298   case KeysetGetQuiet:
1299   case KeysetIsset:
1300   case KeysetIdx:
1301   case AKExistsDict:
1302   case AKExistsKeyset:
1303     return may_load_store(AElemAny, AEmpty);
1304
1305   case SameVec:
1306   case NSameVec:
1307   case SameDict:
1308   case NSameDict:
1309   case EqKeyset:
1310   case NeqKeyset:
1311   case SameKeyset:
1312   case NSameKeyset:
1313     return may_load_store(AElemAny, AEmpty);
1314
1315   case AKExistsObj:
1316     return may_load_store(AHeapAny, AHeapAny);
1317
1318   //////////////////////////////////////////////////////////////////////
1319   // Member instructions
1320
1321   case CheckMBase:
1322     return may_load_store(pointee(inst.src(0)), AEmpty);
1323
1324   /*
1325    * Various minstr opcodes that take a PtrToGen in src 0, which may or may not
1326    * point to a frame local or the evaluation stack. Some may read or write to
1327    * that pointer while some only read. They can all re-enter the VM and access
1328    * arbitrary heap locations.
1329    */
1330   case CGetElem:
1331   case IssetElem:
1332   case CGetProp:
1333   case CGetPropQ:
1334   case IssetProp:
1335     return may_load_store(
1336       AHeapAny | all_pointees(inst),
1337       AHeapAny
1338     );
1339
1340   /*
1341    * SetRange behaves like a simpler version of SetElem.
1342    */
1343   case SetRange:
1344   case SetRangeRev:
1345     return may_load_store(
1346       AHeapAny | all_pointees(inst),
1347       AHeapAny | pointee(inst.src(0))
1348     );
1349
1350   case IncDecElem:
1351   case IncDecProp:
1352   case SetElem:
1353   case SetNewElem:
1354   case SetOpElem:
1355   case SetOpProp:
1356   case SetProp:
1357   case SetNewElemArray:
1358   case SetNewElemVec:
1359   case SetNewElemKeyset:
1360   case UnsetElem:
1361   case ElemArrayD:
1362   case ElemArrayU:
1363   case ElemVecD:
1364   case ElemVecU:
1365   case ElemDictD:
1366   case ElemDictU:
1367   case ElemKeysetU:
1368   case ElemX:
1369   case ElemDX:
1370   case ElemUX:
1371   case UnsetProp:
1372     // These member ops will load and store from the base lval which they
1373     // take as their first argument, which may point anywhere in the heap.
1374     return may_load_store(
1375       AHeapAny | all_pointees(inst),
1376       AHeapAny | all_pointees(inst)
1377     );
1378
1379   case ReservePackedArrayDataNewElem:
1380     return may_load_store(AHeapAny, AHeapAny);
1381
1382   /*
1383    * Intermediate minstr operations. In addition to a base pointer like the
1384    * operations above, these may take a pointer to MInstrState::tvRef, which
1385    * they may store to (but not read from).
1386    */
1387   case PropX:
1388   case PropDX:
1389   case PropQ:
1390     return minstr_with_tvref(inst);
1391
1392   /*
1393    * Collection accessors can read from their inner array buffer, but stores
1394    * COW and behave as if they only affect collection memory locations.  We
1395    * don't track those, so it's returning AEmpty for now.
1396    */
1397   case MapIsset:
1398   case PairIsset:
1399   case VectorIsset:
1400     return may_load_store(AHeapAny, AEmpty /* Note */);
1401   case MapGet:
1402   case MapSet:
1403   case VectorSet:
1404     return may_load_store(AHeapAny, AEmpty /* Note */);
1405
1406   case LdInitPropAddr:
1407     return may_load_store(
1408       AProp {
1409         inst.src(0),
1410         safe_cast<uint16_t>(inst.extra<LdInitPropAddr>()->index)
1411       },
1412       AEmpty
1413     );
1414   case LdInitRDSAddr:
1415     return may_load_store(
1416       ARds { inst.extra<LdInitRDSAddr>()->handle },
1417       AEmpty
1418     );
1419
1420   //////////////////////////////////////////////////////////////////////
1421   // Instructions that allocate new objects, without reading any other memory
1422   // at all, so any effects they have on some types of memory locations we
1423   // track are isolated from anything else we care about.
1424
1425   case NewClsMeth:
1426   case NewRClsMeth:
1427   case NewCol:
1428   case NewColFromArray:
1429   case NewPair:
1430   case NewInstanceRaw:
1431   case NewDArray:
1432   case NewDictArray:
1433   case NewRFunc:
1434   case FuncCred:
1435   case AllocVArray:
1436   case AllocVec:
1437   case AllocStructDArray:
1438   case AllocStructDict:
1439   case ConvDblToStr:
1440   case ConvIntToStr:
1441     return IrrelevantEffects {};
1442
1443   case AllocObj:
1444     // AllocObj re-enters to call constructors, but if it weren't for that we
1445     // could ignore its loads and stores since it's a new object.
1446     return may_load_store(AEmpty, AEmpty);
1447   case AllocObjReified:
1448     // Similar to AllocObj but also stores the reification
1449     return may_load_store(AEmpty, AHeapAny);
1450
1451   //////////////////////////////////////////////////////////////////////
1452   // Instructions that explicitly manipulate the stack.
1453
1454   case LdStk:
1455     return PureLoad {
1456       AStack { inst.src(0), inst.extra<LdStk>()->offset, 1 }
1457     };
1458
1459   case StStk:
1460     return PureStore {
1461       AStack { inst.src(0), inst.extra<StStk>()->offset, 1 },
1462       inst.src(1),
1463       nullptr
1464     };
1465
1466   case StOutValue:
1467     // Technically these writes affect the caller's stack, but there is no way
1468     // to actually observe them from within the callee. They can also only
1469     // occur once on any exit path from a function.
1470     return may_load_store(AEmpty, AEmpty);
1471
1472   case LdOutAddr:
1473     return IrrelevantEffects{};
1474
1475   case CheckStk:
1476     return may_load_store(
1477       AStack { inst.src(0), inst.extra<CheckStk>()->offset, 1 },
1478       AEmpty
1479     );
1480
1481   case DbgTraceCall:
1482     return may_load_store(AStackAny | ALocalAny, AEmpty);
1483
1484   case Unreachable:
1485     // Unreachable code kills every memory location.
1486     return may_load_store_kill(AEmpty, AEmpty, AUnknown);
1487
1488   case ResolveTypeStruct: {
1489     auto const extra = inst.extra<ResolveTypeStructData>();
1490     auto const stack_in = AStack {
1491       inst.src(0),
1492       extra->offset + static_cast<int32_t>(extra->size) - 1,
1493       static_cast<int32_t>(extra->size)
1494     };
1495     return may_load_store(AliasClass(stack_in)|AHeapAny, AHeapAny);
1496   }
1497
1498   case DefFP:
1499     return may_load_store(AFBasePtr, AFBasePtr);
1500
1501   case DefFuncEntryFP:
1502     return may_load_store(livefp(inst.src(0)), livefp(inst.dst()));
1503
1504   case LdARNumParams:
1505   case LdARFlags:
1506     return PureLoad { AFMeta { inst.src(0) }};
1507
1508   //////////////////////////////////////////////////////////////////////
1509   // Instructions that never read or write memory locations tracked by this
1510   // module.
1511
1512   case AbsDbl:
1513   case AddDbl:
1514   case AddInt:
1515   case AddIntO:
1516   case AdvanceMixedPtrIter:
1517   case AdvancePackedPtrIter:
1518   case AndInt:
1519   case AssertType:
1520   case AssertLoc:
1521   case AssertStk:
1522   case AssertMBase:
1523   case DefFrameRelSP:
1524   case DefRegSP:
1525   case DefCallFlags:
1526   case DefCallFunc:
1527   case DefCallNumArgs:
1528   case DefCallCtx:
1529   case EndGuards:
1530   case EnterPrologue:
1531   case EqBool:
1532   case EqCls:
1533   case EqRecDesc:
1534   case EqFunc:
1535   case EqStrPtr:
1536   case EqArrayDataPtr:
1537   case EqDbl:
1538   case EqInt:
1539   case EqPtrIter:
1540   case GetMixedPtrIter:
1541   case GetPackedPtrIter:
1542   case GteBool:
1543   case GteInt:
1544   case GtBool:
1545   case GtInt:
1546   case Jmp:
1547   case JmpNZero:
1548   case JmpZero:
1549   case LdPropAddr:
1550   case LdStkAddr:
1551   case LdPackedArrayDataElemAddr:
1552   case LteBool:
1553   case LteDbl:
1554   case LteInt:
1555   case LtBool:
1556   case LtInt:
1557   case GtDbl:
1558   case GteDbl:
1559   case LtDbl:
1560   case DivDbl:
1561   case DivInt:
1562   case MulDbl:
1563   case MulInt:
1564   case MulIntO:
1565   case NeqBool:
1566   case NeqDbl:
1567   case NeqInt:
1568   case SameObj:
1569   case NSameObj:
1570   case EqRes:
1571   case NeqRes:
1572   case CmpBool:
1573   case CmpInt:
1574   case CmpDbl:
1575   case SubDbl:
1576   case SubInt:
1577   case SubIntO:
1578   case XorBool:
1579   case XorInt:
1580   case OrInt:
1581   case AssertNonNull:
1582   case CheckNonNull:
1583   case CheckNullptr:
1584   case CheckImplicitContextNull:
1585   case CheckSmashableClass:
1586   case Ceil:
1587   case Floor:
1588   case DefLabel:
1589   case CheckInit:
1590   case Nop:
1591   case Mod:
1592   case Conjure:
1593   case ConjureUse:
1594   case EndBlock:
1595   case ConvBoolToInt:
1596   case ConvBoolToDbl:
1597   case DefConst:
1598   case LdLocAddr:
1599   case Sqrt:
1600   case Shl:
1601   case Shr:
1602   case Lshr:
1603   case IsNType:
1604   case IsType:
1605   case Mov:
1606   case ConvDblToBool:
1607   case ConvDblToInt:
1608   case DblAsBits:
1609   case LdMIStateAddr:
1610   case LdClsCns:
1611   case LdSubClsCns:
1612   case LdSubClsCnsClsName:
1613   case LdTypeCns:
1614   case CheckSubClsCns:
1615   case LdClsCnsVecLen:
1616   case ProfileSubClsCns:
1617   case FuncHasAttr:
1618   case IsFunReifiedGenericsMatched:
1619   case IsClsDynConstructible:
1620   case JmpPlaceholder:
1621   case LdFuncRxLevel:
1622   case LdSmashable:
1623   case LdSmashableFunc:
1624   case LdRDSAddr:
1625   case CheckRange:
1626   case ProfileType:
1627   case LdIfaceMethod:
1628   case InstanceOfIfaceVtable:
1629   case IsTypeStructCached:
1630   case LdTVAux:
1631   case MethodExists:
1632   case GetTime:
1633   case GetTimeNs:
1634   case ProfileInstanceCheck:
1635   case Select:
1636   case LookupSPropSlot:
1637   case ConvPtrToLval:
1638   case ProfileProp:
1639   case ProfileIsTypeStruct:
1640     return IrrelevantEffects {};
1641
1642   case StClosureArg:
1643     return PureStore {
1644       AProp {
1645         inst.src(0),
1646         safe_cast<uint16_t>(inst.extra<StClosureArg>()->index)
1647       },
1648       inst.src(1),
1649       inst.src(0)
1650     };
1651
1652   case StArResumeAddr:
1653     return PureStore { AFMeta { inst.src(0) }, nullptr };
1654
1655   case StContArKey:
1656   case StContArValue:
1657   case StContArState:
1658   case ContArIncIdx:
1659   case ContArIncKey:
1660   case ContArUpdateIdx:
1661   case LdContArKey:
1662   case LdContArValue:
1663     return may_load_store(AFContext { inst.src(0) }, AEmpty);
1664
1665   case LdFrameThis:
1666   case LdFrameCls:
1667     return PureLoad { AFContext { inst.src(0) }};
1668
1669   case StFrameCtx:
1670     return PureStore { AFContext { inst.src(0) }, inst.src(1) };
1671
1672   case StFrameFunc:
1673     return PureStore { AFFunc { inst.src(0) }, inst.src(1) };
1674
1675   case StFrameMeta:
1676     return PureStore { AFMeta { inst.src(0) }, nullptr };
1677
1678   case EagerSyncVMRegs:
1679     return may_load_store(AEmpty, AEmpty);
1680
1681   //////////////////////////////////////////////////////////////////////
1682   // Instructions that technically do some things w/ memory, but not in any way
1683   // we currently care about.  They however don't return IrrelevantEffects
1684   // because we assume (in refcount-opts) that IrrelevantEffects instructions
1685   // can't even inspect Countable reference count fields, and several of these
1686   // can.  All GeneralEffects instructions are assumed to possibly do so.
1687
1688   case DecRefNZ:
1689   case ProfileDecRef:
1690   case AFWHBlockOn:
1691   case AFWHPushTailFrame:
1692   case IncRef:
1693   case LdClosureCls:
1694   case LdClosureThis:
1695   case LdRetVal:
1696   case ConvStrToInt:
1697   case ConvResToInt:
1698   case OrdStr:
1699   case ChrInt:
1700   case CreateSSWH:
1701   case CheckInOuts:
1702   case BeginCatch:
1703   case CheckSurpriseFlags:
1704   case CheckType:
1705   case ZeroErrorLevel:
1706   case RestoreErrorLevel:
1707   case CheckCold:
1708   case ContValid:
1709   case ContStarted:
1710   case IncProfCounter:
1711   case IncCallCounter:
1712   case IncStat:
1713   case ContPreNext:
1714   case ContStartedCheck:
1715   case ConvArrToDbl:
1716   case CountArray:
1717   case CountVec:
1718   case CountDict:
1719   case CountKeyset:
1720   case HasReifiedGenerics:
1721   case InstanceOf:
1722   case InstanceOfBitmask:
1723   case NInstanceOfBitmask:
1724   case InstanceOfIface:
1725   case InstanceOfRecDesc:
1726   case InterfaceSupportsArr:
1727   case InterfaceSupportsVec:
1728   case InterfaceSupportsDict:
1729   case InterfaceSupportsKeyset:
1730   case InterfaceSupportsDbl:
1731   case InterfaceSupportsInt:
1732   case InterfaceSupportsStr:
1733   case IsWaitHandle:
1734   case IsCol:
1735   case HasToString:
1736   case DbgAssertRefCount:
1737   case DbgCheckLocalsDecRefd:
1738   case GtStr:
1739   case GteStr:
1740   case LtStr:
1741   case LteStr:
1742   case EqStr:
1743   case NeqStr:
1744   case SameStr:
1745   case NSameStr:
1746   case CmpStr:
1747   case GtStrInt:
1748   case GteStrInt:
1749   case LtStrInt:
1750   case LteStrInt:
1751   case EqStrInt:
1752   case NeqStrInt:
1753   case CmpStrInt:
1754   case GtRes:
1755   case GteRes:
1756   case LtRes:
1757   case LteRes:
1758   case CmpRes:
1759   case LdBindAddr:
1760   case LdSSwitchDestFast:
1761   case RBTraceEntry:
1762   case RBTraceMsg:
1763   case ConvIntToBool:
1764   case ConvIntToDbl:
1765   case ConvStrToBool:
1766   case ConvStrToDbl:
1767   case ConvResToDbl:
1768   case ExtendsClass:
1769   case LdUnwinderValue:
1770   case LdClsName:
1771   case LdAFWHActRec:
1772   case LdContActRec:
1773   case LdContField:
1774   case LdContResumeAddr:
1775   case LdClsCachedSafe:
1776   case LdRecDescCachedSafe:
1777   case LdClsInitData:
1778   case UnwindCheckSideExit:
1779   case LdCns:
1780   case LdFuncVecLen:
1781   case LdClsMethod:
1782   case LdClsMethodCacheCls:
1783   case LdClsMethodCacheFunc:
1784   case LdClsMethodFCacheFunc:
1785   case LdClsTypeCns:
1786   case LdClsTypeCnsClsName:
1787   case ProfileSwitchDest:
1788   case LdFuncCls:
1789   case LdFuncNumParams:
1790   case LdFuncName:
1791   case LdMethCallerName:
1792   case LdObjClass:
1793   case LdRecDesc:
1794   case LdObjInvoke:
1795   case LdObjMethodD:
1796   case LdObjMethodS:
1797   case LdStrLen:
1798   case StringIsset:
1799   case LdSwitchDblIndex:
1800   case LdSwitchStrIndex:
1801   case LdWHResult:
1802   case LdWHState:
1803   case LdWHNotDone:
1804   case LookupClsMethod:
1805   case LookupClsRDS:
1806   case StrictlyIntegerConv:
1807   case DbgAssertFunc:
1808   case ProfileCall:
1809   case ProfileMethod:
1810     return may_load_store(AEmpty, AEmpty);
1811
1812   // Some that touch memory we might care about later, but currently don't:
1813   case ColIsEmpty:
1814   case ColIsNEmpty:
1815   case ConvTVToBool:
1816   case ConvObjToBool:
1817   case CountCollection:
1818   case LdVectorSize:
1819   case CheckPackedArrayDataBounds:
1820   case LdColVec:
1821   case LdColDict:
1822     return may_load_store(AEmpty, AEmpty);
1823
1824   //////////////////////////////////////////////////////////////////////
1825   // Instructions that can re-enter the VM and touch most heap things.  They
1826   // also may generally write to the eval stack below an offset (see
1827   // alias-class.h above AStack for more).
1828
1829   case DecRef:
1830     return may_load_store(AHeapAny, AHeapAny);
1831
1832   case GetMemoKey:
1833     return may_load_store(AHeapAny, AHeapAny);
1834
1835   case GetMemoKeyScalar:
1836     return IrrelevantEffects{};
1837
1838   // These opcodes raise notices if we access $GLOBALS['GLOBALS'],
1839   // or, due to case insensitivity, $GLOBALS['gLoBAls'], etc.
1840   case BaseG:
1841   case LdGblAddr:
1842   case LdGblAddrDef: {
1843     auto const base = inst.op() == BaseG
1844       ? may_load_store(AHeapAny, AHeapAny)
1845       : may_load_store(AEmpty, AEmpty);
1846     auto const& key = inst.src(0)->type();
1847     auto const safe = key.hasConstVal() && !s_GLOBALS.equal(key.strVal());
1848     return safe ? base : may_reenter(inst, base);
1849   }
1850
1851   case LdClsCtor:
1852     return may_load_store(AEmpty, AEmpty);
1853
1854   case RaiseRxCallViolation:
1855     return may_load_store(AFFunc{inst.src(0)}, AEmpty);
1856
1857   case LdClsPropAddrOrNull:   // may run 86{s,p}init, which can autoload
1858   case LdClsPropAddrOrRaise:  // raises errors, and 86{s,p}init
1859   case Clone:
1860   case ThrowArrayIndexException:
1861   case ThrowArrayKeyException:
1862   case RaiseClsMethPropConvertNotice:
1863   case RaiseArraySerializeNotice:
1864   case RaiseUninitLoc:
1865   case RaiseUndefProp:
1866   case RaiseTooManyArg:
1867   case RaiseError:
1868   case RaiseNotice:
1869   case RaiseWarning:
1870   case RaiseHackArrCompatNotice:
1871   case RaiseForbiddenDynCall:
1872   case RaiseForbiddenDynConstruct:
1873   case RaiseStrToClassNotice:
1874   case CheckClsMethFunc:
1875   case CheckClsReifiedGenericMismatch:
1876   case CheckFunReifiedGenericMismatch:
1877   case ConvTVToStr:
1878   case ConvObjToStr:
1879   case Count:      // re-enters on CountableClass
1880   case GtObj:
1881   case GteObj:
1882   case LtObj:
1883   case LteObj:
1884   case EqObj:
1885   case NeqObj:
1886   case CmpObj:
1887   case GtArr:
1888   case GteArr:
1889   case LtArr:
1890   case LteArr:
1891   case EqArr:
1892   case NeqArr:
1893   case CmpArr:
1894   case GtVec:
1895   case GteVec:
1896   case LtVec:
1897   case LteVec:
1898   case EqVec:
1899   case NeqVec:
1900   case CmpVec:
1901   case EqDict:
1902   case NeqDict:
1903   case ConvObjToVArr:  // can invoke PHP
1904   case ConvObjToDArr:  // can invoke PHP
1905   case OODeclExists:
1906   case DefCls:         // autoload
1907   case LdCls:          // autoload
1908   case LdClsCached:    // autoload
1909   case LdFunc:         // autoload
1910   case LdFuncCached:   // autoload
1911   case LdRecDescCached:    // autoload
1912   case LdSwitchObjIndex:  // decrefs arg
1913   case InitClsCns:      // autoload
1914   case LookupClsMethodCache:  // autoload
1915   case LookupClsMethodFCache: // autoload
1916   case LookupCnsE:
1917   case LookupFuncCached: // autoload
1918   case StringGet:      // raise_notice
1919   case OrdStrIdx:      // raise_notice
1920   case AddNewElem:         // can re-enter
1921   case AddNewElemKeyset:   // can re-enter
1922   case ArrayGet:       // kVPackedKind warnings
1923   case ArraySet:       // kVPackedKind warnings
1924   case DictGet:
1925   case KeysetGet:
1926   case VecSet:
1927   case DictSet:
1928   case ConcatStrStr:
1929   case PrintStr:
1930   case PrintBool:
1931   case PrintInt:
1932   case ConcatIntStr:
1933   case ConcatStrInt:
1934   case LdSSwitchDestSlow:
1935   case ConvObjToDbl:
1936   case ConvObjToInt:
1937   case ConvTVToInt:
1938   case ConvResToStr:
1939   case ConcatStr3:
1940   case ConcatStr4:
1941   case ConvTVToDbl:
1942   case ConvArrToVec:
1943   case ConvArrToDict:
1944   case ConvObjToVec:
1945   case ConvObjToDict:
1946   case ConvObjToKeyset:
1947   case ThrowOutOfBounds:
1948   case ThrowInvalidArrayKey:
1949   case ThrowInvalidOperation:
1950   case ThrowCallReifiedFunctionWithoutGenerics:
1951   case ThrowDivisionByZeroException:
1952   case ThrowHasThisNeedStatic:
1953   case ThrowLateInitPropError:
1954   case ThrowMissingArg:
1955   case ThrowMissingThis:
1956   case ThrowParameterWrongType:
1957   case ThrowParamInOutMismatch:
1958   case ThrowParamInOutMismatchRange:
1959   case SetLegacyDict:
1960   case SetLegacyVec:
1961   case SetOpTV:
1962   case OutlineSetOp:
1963   case ThrowAsTypeStructException:
1964   case PropTypeRedefineCheck: // Can raise and autoload
1965   case HandleRequestSurprise:
1966     return may_load_store(AHeapAny, AHeapAny);
1967
1968   case AddNewElemVec:
1969   case RaiseErrorOnInvalidIsAsExpressionType:
1970   case IsTypeStruct:
1971   case RecordReifiedGenericsAndGetTSList:
1972     return may_load_store(AElemAny, AEmpty);
1973
1974   case ConvArrToKeyset: // Decrefs input values
1975   case ConvVecToKeyset:
1976   case ConvDictToKeyset:
1977   case ConvDictToDArr: // These 4 may raise Hack array compat notices
1978   case ConvKeysetToDArr:
1979   case ConvClsMethToDArr:
1980   case ConvClsMethToDict:
1981   case ConvClsMethToKeyset:
1982   case ConvClsMethToVArr:
1983   case ConvClsMethToVec:
1984     return may_load_store(AElemAny, AEmpty);
1985
1986   case ConvDictToVec:
1987   case ConvKeysetToVec:
1988   case ConvVecToDict:
1989   case ConvKeysetToDict:
1990   case ConvArrToVArr:
1991   case ConvVecToVArr:
1992   case ConvDictToVArr:
1993   case ConvKeysetToVArr:
1994   case ConvArrToDArr:
1995   case ConvVecToDArr:
1996     return may_load_store(AElemAny, AEmpty);
1997
1998   case ReleaseVVAndSkip:  // can decref VarEnv and Locals
1999     return
2000       may_load_store(AHeapAny|ALocalAny|livefp(inst.src(0)),
2001                      AHeapAny|ALocalAny|livefp(inst.src(0)));
2002
2003   // debug_backtrace() traverses stack and WaitHandles on the heap.
2004   case DebugBacktrace:
2005   case DebugBacktraceFast:
2006     return may_load_store(AHeapAny|ALocalAny|AStackAny, AHeapAny);
2007
2008   // This instruction doesn't touch memory we track, except that it may
2009   // re-enter to construct php Exception objects.  During this re-entry anything
2010   // can happen (e.g. a surprise flag check could cause a php signal handler to
2011   // run arbitrary code).
2012   case AFWHPrepareChild:
2013     return may_load_store(AActRec { inst.src(0) }, AEmpty);
2014
2015   //////////////////////////////////////////////////////////////////////
2016   // The following instructions are used for debugging memory optimizations.
2017   // We can't ignore them, because they can prevent future optimizations;
2018   // eg t1 = LdStk<N>; DbgTrashStk<N>; StStk<N> t1
2019   // If we ignore the DbgTrashStk it looks like the StStk is redundant
2020
2021   case DbgTrashStk:
2022     return GeneralEffects {
2023       AEmpty, AEmpty, AEmpty,
2024       AStack { inst.src(0), inst.extra<DbgTrashStk>()->offset, 1 }
2025     };
2026   case DbgTrashFrame:
2027     return GeneralEffects {
2028       AEmpty, AEmpty, AEmpty,
2029       actrec(inst.src(0), inst.extra<DbgTrashFrame>()->offset)
2030     };
2031   case DbgTrashMem:
2032     return GeneralEffects {
2033       AEmpty, AEmpty, AEmpty,
2034       pointee(inst.src(0))
2035     };
2036   case DbgTrashRetVal:
2037     return IrrelevantEffects {};
2038
2039   //////////////////////////////////////////////////////////////////////
2040
2041   }
2042
2043   not_reached();
2044 }
2045
2046 //////////////////////////////////////////////////////////////////////
2047
2048 DEBUG_ONLY bool check_effects(const IRInstruction& inst, MemEffects me) {
2049   SCOPE_ASSERT_DETAIL("Memory Effects") {
2050     return folly::sformat("  inst: {}\n  effects: {}\n", inst, show(me));
2051   };
2052
2053   auto check_fp = [&] (FPRelOffset base) {
2054     always_assert_flog(
2055       base.offset <= 0,
2056       "frame offset is above base frame"
2057     );
2058   };
2059
2060   auto check_obj = [&] (SSATmp* obj) {
2061     always_assert_flog(
2062       obj->type() <= TObj,
2063       "Non obj pointer in memory effects"
2064     );
2065   };
2066
2067   auto check = [&] (AliasClass a) {
2068     if (auto const fr = a.local()) check_fp(fr->base);
2069     if (auto const pr = a.prop())  check_obj(pr->obj);
2070   };
2071
2072   match<void>(
2073     me,
2074     [&] (GeneralEffects x) {
2075       check(x.loads);
2076       check(x.stores);
2077       check(x.moves);
2078       check(x.kills);
2079
2080       // Locations may-moved always should also count as may-loads.
2081       always_assert(x.moves <= x.loads);
2082
2083       if (inst.mayRaiseErrorWithSources()) {
2084         // Any instruction that can raise an error can run a user error handler
2085         // and have arbitrary effects on the heap.
2086         always_assert(AHeapAny <= x.loads);
2087         always_assert(AHeapAny <= x.stores);
2088         /*
2089          * They also ought to kill /something/ on the stack, because of
2090          * possible re-entry.  It's not incorrect to leave things out of the
2091          * kills set, but this assertion is here because we shouldn't do it on
2092          * purpose, so this is here until we have a reason not to assert it.
2093          *
2094          * The mayRaiseError instructions should all be going through
2095          * may_reenter right now, which will kill the stack below the re-entry
2096          * depth---unless the marker for `inst' doesn't have an fp set.
2097          */
2098         always_assert(inst.marker().fp() == nullptr ||
2099                       AStackAny.maybe(x.kills));
2100       }
2101     },
2102     [&] (PureLoad x)         { check(x.src); },
2103     [&] (PureStore x)        { check(x.dst); },
2104     [&] (ExitEffects x)      { check(x.live); check(x.kills); },
2105     [&] (IrrelevantEffects)  {},
2106     [&] (UnknownEffects)     {},
2107     [&] (CallEffects x)      { check(x.kills);
2108                                check(x.inputs);
2109                                check(x.actrec);
2110                                check(x.outputs);
2111                                check(x.locals); },
2112     [&] (PureInlineCall x)   { check(x.base);
2113                                check(x.actrec); },
2114     [&] (PureInlineReturn x) { check(x.base); },
2115     [&] (ReturnEffects x)    { check(x.kills); }
2116   );
2117
2118   return true;
2119 }
2120
2121 //////////////////////////////////////////////////////////////////////
2122
2123 }
2124
2125 MemEffects memory_effects(const IRInstruction& inst) {
2126   auto const inner = memory_effects_impl(inst);
2127   auto const ret = [&] () -> MemEffects {
2128     if (!inst.mayRaiseErrorWithSources()) return inner;
2129
2130     auto fail = [&] {
2131       always_assert_flog(
2132         false,
2133         "Instruction {} has effects {}, but has been marked as MayRaiseError "
2134         "and must use a UnknownEffects, GeneralEffects, or CallEffects type.",
2135         inst,
2136         show(inner)
2137       );
2138       return may_load_store(AUnknown, AUnknown);
2139     };
2140
2141     // Calls are implicitly MayRaise, all other instructions must use the
2142     // GeneralEffects or UnknownEffects class of memory effects
2143     return match<MemEffects>(
2144       inner,
2145       [&] (GeneralEffects x)   { return may_reenter(inst, x); },
2146       [&] (CallEffects x)      { return x; },
2147       [&] (UnknownEffects x)   { return x; },
2148       [&] (PureLoad)           { return fail(); },
2149       [&] (PureStore)          { return fail(); },
2150       [&] (ExitEffects)        { return fail(); },
2151       [&] (PureInlineCall)     { return fail(); },
2152       [&] (PureInlineReturn)   { return fail(); },
2153       [&] (IrrelevantEffects)  { return fail(); },
2154       [&] (ReturnEffects)      { return fail(); }
2155     );
2156   }();
2157   assertx(check_effects(inst, ret));
2158   return ret;
2159 }
2160
2161 AliasClass pointee(const SSATmp* tmp) {
2162   return pointee(tmp, nullptr);
2163 }
2164
2165 //////////////////////////////////////////////////////////////////////
2166
2167 MemEffects canonicalize(MemEffects me) {
2168   using R = MemEffects;
2169   return match<R>(
2170     me,
2171     [&] (GeneralEffects x) -> R {
2172       return GeneralEffects {
2173         canonicalize(x.loads),
2174         canonicalize(x.stores),
2175         canonicalize(x.moves),
2176         canonicalize(x.kills)
2177       };
2178     },
2179     [&] (PureLoad x) -> R {
2180       return PureLoad { canonicalize(x.src) };
2181     },
2182     [&] (PureStore x) -> R {
2183       return PureStore { canonicalize(x.dst), x.value, x.dep };
2184     },
2185     [&] (ExitEffects x) -> R {
2186       return ExitEffects { canonicalize(x.live), canonicalize(x.kills) };
2187     },
2188     [&] (PureInlineCall x) -> R {
2189       return PureInlineCall {
2190         canonicalize(x.base),
2191         x.fp,
2192         canonicalize(x.actrec)
2193       };
2194     },
2195     [&] (PureInlineReturn x) -> R {
2196       return PureInlineReturn {
2197         canonicalize(x.base),
2198         x.calleeFp,
2199         x.callerFp
2200       };
2201     },
2202     [&] (CallEffects x) -> R {
2203       return CallEffects {
2204         canonicalize(x.kills),
2205         canonicalize(x.inputs),
2206         canonicalize(x.actrec),
2207         canonicalize(x.outputs),
2208         canonicalize(x.locals)
2209       };
2210     },
2211     [&] (ReturnEffects x) -> R {
2212       return ReturnEffects { canonicalize(x.kills) };
2213     },
2214     [&] (IrrelevantEffects x) -> R { return x; },
2215     [&] (UnknownEffects x)    -> R { return x; }
2216   );
2217 }
2218
2219 //////////////////////////////////////////////////////////////////////
2220
2221 std::string show(MemEffects effects) {
2222   using folly::sformat;
2223   return match<std::string>(
2224     effects,
2225     [&] (GeneralEffects x) {
2226       return sformat("mlsmk({} ; {} ; {} ; {})",
2227         show(x.loads),
2228         show(x.stores),
2229         show(x.moves),
2230         show(x.kills)
2231       );
2232     },
2233     [&] (ExitEffects x) {
2234       return sformat("exit({} ; {})", show(x.live), show(x.kills));
2235     },
2236     [&] (PureInlineCall x) {
2237       return sformat("inline_call({} ; {})",
2238         show(x.base),
2239         show(x.actrec)
2240       );
2241     },
2242     [&] (PureInlineReturn x) {
2243       return sformat("inline_return({})", show(x.base));
2244     },
2245     [&] (CallEffects x) {
2246       return sformat("call({} ; {} ; {} ; {} ; {})",
2247         show(x.kills),
2248         show(x.inputs),
2249         show(x.actrec),
2250         show(x.outputs),
2251         show(x.locals)
2252       );
2253     },
2254     [&] (PureLoad x)        { return sformat("ld({})", show(x.src)); },
2255     [&] (PureStore x)       { return sformat("st({})", show(x.dst)); },
2256     [&] (ReturnEffects x)   { return sformat("return({})", show(x.kills)); },
2257     [&] (IrrelevantEffects) { return "IrrelevantEffects"; },
2258     [&] (UnknownEffects)    { return "UnknownEffects"; }
2259   );
2260 }
2261
2262 //////////////////////////////////////////////////////////////////////
2263
2264 }}