*******************************************
* HipHop Intermediate Representation (HHIR)
*******************************************



Introduction
------------

The HipHop Intermediate Representation (IR) is a typed, in-memory,
static-single-assignment, intermediate-level representation of HHBC
programs used for just in time compilation, with these goals:

  1. Complete.  The IR represents a program or program fragment
     entirely, without reference to HHBC or other upstream forms of
     the program.

  2. Type-Safe.  Since the IR deals directly with refined types and
     internal VM types, all operations are typesafe.  All instruction
     parameters have a parameter type P, and all variables have a type
     S.  Given an instruction with source parameter type P and variable
     type S, S must be equal to or more refined than P (S == P or S <: P).

  3. Machine Independent.  Since this IR is intended to be used in a JIT
     compiler, it will always be used in a machine specific context.
     Nevertheless, we rely on machine independence in order to separate
     concerns and increase portability of the VM.  Passes which manipulate
     IR based on PHP or HHBC semantics should be portable.  Passes which deal
     with machine specifics (such as register allocation) should be self
     contained.  For example, register allocation may insert machine-specific
     loads, stores, or swaps, according to a specific cpu model.  But those
     instructions are still well behaved Instruction classes.  Types are
     machine independent.

The unit of compilation is the Trace, which is a sequence of Blocks of
Instructions that produce and consume Variables.  Blocks are single-entry,
single-exit sequences of instructions (i.e. basic blocks).  Instructions may
be annotated with Type which modifies the instruction's behavior.  Each
Variable has a Type which describes the set of values it may hold at
the point it is defined.  Instructions may have side effects, which occur
in execution order.

The static single assignment form guarantees the following two invariants
for a well-formed Trace:

  1. Each Variable is assigned to by exactly one Instruction.

  2. Definitions dominate uses.  Every path to an Instruction using a Variable
     first executes the Instruction defining the Variable.

Any pass that generates or manipulates IR must preserve these invariants,
however it is possible and expected for the invariants to be temporarily
broken during trace creation or during an optimizer pass.


Control Flow
------------

Traces have one entry block and zero or more exit traces.  Blocks may branch
within a trace or to an exit trace; blocks form a restricted control flow graph.
This control flow may contain join points (two or more branches exiting
at the same point, or two jumps within the trace to a target in the same trace),
but may not form loops.

No Variables are defined on entry to the main Trace.

Blocks which are join points may start with a DefLabel with destination
Variables.  In that case, each predecessor must be a Jmp_ passing a matching
number of source Variables.  In this case the Jmp_ acts as a tail-call, passing
arguments the same way a plain call would.

Together, the sources of the Jmp_ instructions and the destinations of the
DefLabel instructions act as traditional SSA Phi pseudo-functions; The type
of the label's destination is the type-union of the corresponding sources.
Because the Jmp_ sources are at the ends of blocks, they do not violate the
SSA dominator rule (rule 2, above).

Implementation note: The JIT's compilation unit ("Trace" in this spec) actually
consists of one or more instances of the Trace class.  There is exactly one
main trace, and zero or more exit traces which handle side exits.
Instructions in exit traces may use Variables defined on the main trace,
so these exits are not separate compilation units.


Types
-----

Types in the IR are used in several contexts.  In all cases, a Type represents
a set of runtime values, however, a Type's meaning depends on the context
in which it appears.  A type which annotates an instruction (like IsType)
modifies its behavior, extending its opcode.  The type of each source
parameter restricts the type of any variable used by that parameter.
A variable's type describes the set of values it may hold at the point it is
defined.

Since types represent sets of values, we define relations on types in terms of
the sets of values they represent.  Two types S and T are equal (S == T) if they
represent equal sets of values.  S is more refined than T (S <: T), or a
subtype of T, if the set of values represented by S is a subset of the set of
values represented by T.  S and T are not related if neither value set is
a subtype of the other: (S <: T) and (T <: S) are both false.  A type U
is a union of S and T (U = {S|T}) if it represents the union of S and T's
value sets.  In that case, S and T are both subtypes of U (S <: U, T <: U),
even if S and T are not related.

Variables in the IR contain a mix of PHP-visible types and internal types. The
following table describes types representing PHP values. Note that the types
used here are more specific than what can be discriminated by user code (e.g.,
StaticStr and CountedStr both appear as type String at the PHP level).

  Type            HHVM representation
  ----            -------------------
  Uninit          KindOfUninit
  InitNull        KindOfNull
  Null            {Uninit|InitNull}
  Bool            false=0,true=1 (actual bit width varies)
  Int             int64_t (64-bit twos compliment binary integer)
  Dbl             double (IEEE 754 64-bit binary floating point)
  StaticStr       StringData* where isStatic() == true
  CountedStr      StringData* where isStatic() == false
  UncountedInit   TypedValue {Null|Bool|Int|Dbl|StaticStr}
  Uncounted       TypedValue {Unin|Null|Bool|Int|Dbl|StaticStr}
  Str             StringData* {CountedStr|StaticStr}
  StaticArr       ArrayData* where isStatic() == true
  CountedArr      ArrayData* where isStatic() == false
  Arr             ArrayData* {CountedArr|StaticArr}
  Obj             ObjectData*
  Counted         {CountedStr|CountedArr|Obj|BoxedCell}
  Cell            {Null|Bool|Int|Dbl|Str|Arr|Obj}

A PHP reference is implemented as a container object (RefData) which contains
one value.  The contained value cannot be another PHP reference.  For every
type T in the table above, there is a corresponding type BoxedT, which is a
pointer to a RefData struct containing a value of type T.

  Type            HHVM representation
  ----            -------------------
  BoxedInitNull   RefData* containing InitNull
  ...             Everything from the first table above can be boxed
  BoxedCell       RefData* containing Cell (topmost boxed type).

Finally, there is one top-level type representing all possible PHP values:

  Gen             {Cell|BoxedCell}

The VM also manipulates values of various internal types, which are never
visible at the PHP semantic level, and do not have any type relation with the
above PHP-facing types.

  Type            HHVM representation
  ----            -------------------
  PtrToT          Exists for all T in Gen. Represents a TypedValue*
  None            No value, KindOfInvalid
  Bottom          No value, {}. Subtype of every other type
  Cls             Class*
  Func            Func*
  VarEnv          VarEnv*
  NamedEntity     NamedEntity*
  FuncCls         Tuple of (Func*,Cctx)
  FuncObj         Tuple of (Func*,Obj)
  Cctx            A Class* with the lowest bit set (as stored in ActRec.m_cls)
  Ctx             {Obj|Cctx}
  FuncCtx         Tuple of (Func*,{Cctx|Obj})
  RetAddr         Return address
  StkPtr          Pointer into VM execution stack
  TCA             Machine code address

In the instruction descriptions below, we also use a "Const" prefix on
several types loosly, which means the operand must be the requested
type and must be a compile-time constant.  The optimizer relies on
accessing the value of those operands.


Variables
---------

A Variable represents a storage location which takes on various concrete values
at runtime.  Since HHIR uses SSA, a variable may only be assigned to by one
instruction.  A variable's type represents the set of values it may hold at
the point it is defined.  The type is invariant over the lifetime of the
variable (from the definition point to the last use).

Implementation note: this the proposed semantics. The current implementation
is not this strict; during IR generation, we overload instruction type
(IRInstruction::m_type), variable type (SSATmp::getType returns instr->type),
and types known at points *after* definition, due to guards.  e.g.  after
a guard, we change src->instr->type to the refined type, then propagate this
backwards through copies.  This effectively uses IRInstruction::m_type as
a scratch variable, which is only valid at certian times during construction).
This is probably unsound in later passes; after such a refinement,
instructions using the variable before the guard see the refined type.


Instructions
------------

An instruction is an executable operation with zero or more inputs (sources),
zero or one result (destination), and possible side effects such as accessing
memory, doing I/O, and which may branch or throw an exception.  Some
instructions have a Type parameter which modifies its behavior.

Each instruction has a signature which describes its effect, parameter types,
and return type, for example:

  r:Bool = IsType<T> s:Gen

By convention we use infix; destinations on the left, = represents assignment,
then the opcode name, and source parameters.  Types are to the right of the
entities they modify, separated by : for results, sources, and variables,
or delimited by <> for instruction modifiers.

Instruction flags further describe their behavior:

HasDest
NaryDest

  The instruction defines exactly one destination variable (HasDest) or
  a varying number of destination variables (NaryDest).  These flags are
  mutually exclusive.  An instruction with neither of these flags set has
  zero destination variables.

  Note that an instruction's destination variable may sometimes be a
  copy of one of the input variables.  (For example, AddElem returns the
  array it took as an input.)

CanCSE

  The instruction is safe to elide through common subexpression
  elimination.

Essential

  Whether the instruction is essential indicates whether it can be
  elided through certain types of optimizations.

  Currently this is just used to flag whether we are allowed to do
  dead code elimination on it.

MemEffects

  Indicates that the instruction has side effects on memory that
  cannot be rolled back.  If this bit isn't set, it means it is ok to
  redo whatever work the instruction did without changing observable
  program behavior.

  This flag is currently unused, but may be used later to share exit
  traces.

CallsNative

  Indicates that the instruction will call a native helper.

  The register allocator uses this to optimize register spills around
  native calls and to bias register allocation toward arguments and
  return values.

ConsumesRC

  The instruction decrefs its sources.

  TODO: explain better

ProducesRC

  The instruction produces an incref'd value.

  This flag is currently unused.

MayModifyRefs

  The instruction may modify inner cells on KindOfRef values.

Rematerializable

  The instruction is a candidate for rematerialization if the the
  register allocator needs to spill its destination.

MayRaiseError

  The instruction may raise an error, and therefore has an implicit
  exit edge.

Terminal

  The instruction has no next instruction; it either jumps, returns,
  or throws.

Passthrough

  The value of the instruction's dest is the same as one of its inputs; it
  differs only in the refcount of the underlying object, the type of the
  variable, or some other property that doesn't affect the value of the
  variable itself.

KillsSource

  The instruction might destroy one or more of its sources, so they
  cannot be safely used after it has executed.


Instruction set
---------------


1. Checks and Asserts

D:T = GuardType<T> S0:Gen -> L

  Check that the type of the src S0 is T, and if so copy it to D.  If
  S0 is not type T, branch to the exit trace label L.

GuardLoc<T,localId> S0:StkPtr -> L

  Check that type of the given localId on the frame S0 is T; if not,
  branch to the exit trace label L.

AssertLoc<T,localId> S0:StkPtr

  Asserts that type of the supplied local on the frame S0 is T.  This
  is used as a hint for local type information, and is similar to
  GuardLoc except it doesn't imply a runtime check and cannot cause
  control flow.

D:StkPtr = GuardStk<T> S0:StkPtr S1:ConstInt -> L

  Check that the type of the cell on the stack pointed to by S0 at
  index S1 (in cells) is T; if not, branch to the exit trace label L.
  Returns a new StkPtr that represents the same stack but with the
  knowledge that the slot at the index S1 has type T.

D:StkPtr = AssertStk<T> S0:StkPtr S1:ConstInt

  Returns a new StkPtr that represents the same stack as S0, but with
  the knowledge that the slot at the index S1 (in cells) has type T.
  This is similar to a GuardStk except that it does not imply a
  runtime check and cannot cause control flow.

D:StkPtr = CastStk<T> S0:StkPtr S1:ConstInt

  Returns a new StkPtr that represents the same stack as S0, but with
  the slot at index S1 (in cells) converted to type T.

CheckInit S0:Gen -> L

  If S0's type is Uninit, branch to label L.

CheckInitMem S0:PtrToGen S1:ConstInt -> L

  If the value at S0 + S1 has type Uninit, branch to L.

GuardRefs


2. Arithmetic

D:Int = OpAdd S0:{Int|Bool} S1:{Int|Bool}
D:Int = OpSub S0:{Int|Bool} S1:{Int|Bool}
D:Int = OpAnd S0:{Int|Bool} S1:{Int|Bool}
D:Int = OpOr  S0:{Int|Bool} S1:{Int|Bool}
D:Int = OpXor S0:{Int|Bool} S1:{Int|Bool}
D:Int = OpMul S0:{Int|Bool} S1:{Int|Bool}

  Integer/boolean arithmetic.  Performs the operation described by the
  opcode name on S0 and S1, and puts the result in D.

3. Type conversions

D:T = Conv<T> S0:Gen

  Convert S0 from its current type to type T, according to the PHP
  semantics of such a conversion.


4. Boolean predicates

D:Bool = OpGt    S0:Gen S1:Gen
D:Bool = OpGte   S0:Gen S1:Gen
D:Bool = OpLt    S0:Gen S1:Gen
D:Bool = OpLte   S0:Gen S1:Gen
D:Bool = OpEq    S0:Gen S1:Gen
D:Bool = OpNeq   S0:Gen S1:Gen
D:Bool = OpSame  S0:Gen S1:Gen
D:Bool = OpNSame S0:Gen S1:Gen

  Perform comparisons with PHP semantics on S0 and S1, and put the
  result in D.

D:Bool =  InstanceOf S0:Cls S1:Cls S2:ConstBool
D:Bool = NInstanceOf S0:Cls S1:Cls S2:ConstBool

  Sets D based on whether S0 is a descendant of the class, interface,
  or trait in S1.  (Note that this is always false for a trait).  S1
  may be null at runtime if the class is not defined.  The flag S2 is
  just a hint that is true if we should assume S1 might be an
  interface---the instruction must still handle it correctly if this
  hint is wrong at runtime.

D:Bool = ExtendsClass S0:Cls S1:Cls

  A fast-path for instanceof checks.  Sets D based on whether S0 is a
  descendant of the class in S1, where S1 must be a unique class that
  is not an interface or a trait.

D:Bool =  InstanceOfBitmask S0:Cls S1:ConstStr
D:Bool = NInstanceOfBitmask S0:Cls S1:ConstStr

  A fast-path for instanceof checks.  Sets D based on whether S0 is a
  descendant of the class named by S1, where S1 must have a bit
  allocated for it in the fast instance check bitvector (see class.h).

D:Bool =  IsType<T> S0:Cell
D:Bool = IsNType<T> S0:Cell

  IsType (IsNType) sets D to true iff S0 holds a value that is (not)
  of type T.

D:Bool =  IsTypeMem<T> S0:PtrToGen
D:Bool = IsNTypeMem<T> S0:PtrToGen

  IsTypeMem (IsNTypeMem) sets D to true iff the value referenced by S0
  is (not) of type T.

5. Branches

There is a conditional branch instruction for each predicate above,
to enable generating efficient compare-and-branch instruction sequences.

JmpGt
JmpGte
JmpLt
JmpLte
JmpEq
JmpNeq
JmpSame
JmpNSame
JmpInstanceOf
JmpNInstanceOf
JmpInstanceOfBitmask
JmpNInstanceOfBitmask
JmpIsType
JmpIsNType

  Fused jump instructions.  These all operate exactly as their
  corresponding query op, but also take a label to jump to when the
  condition is true.

D:None = JmpZero S0:{Bool|Int} L:Label
D:None = JmpNZero S0:{Bool|Int} L:Label

  Conditionally jump to L based on S0.

D:None JmpSwitchDest<JmpSwitchData> S0:Int

  Jump to the target of a switch stamement using table metadata
  <JmpSwitchData> and index S0.

ExitWhenSurprised -> L

  Tests the surprise flags and if they are set, jumps to the
  exit-trace label L.

ExitOnVarEnv S0:StkPtr -> L

  Loads the VarEnv slot off the ActRec pointed to by S0.  If it is
  non-zero, jumps to the exit-trace label L.

Marker<bcOff,stackOff,func>

  Record HHBC virtual position information at the position of this
  instruction.  Marker has no executable semantics.  The JIT compiler
  uses this to generate bytecode<->machine code maps.

Jmp_ [S:T ...] -> L

  Unconditional jump to L.  L is the name of a DefLabel instruction.
  Each the sources are copied to the corresponding destinations of the
  target L.  The number of destinations on L must match the number of
  sources of this Jmp_.

DefLabel
D:T ... = DefLabel

  Denote the position of a jump target.  Branch instructions, and
  instructions which implicitly guard, take a Label argument which refers
  to a specific DefLabel instruction.  Additionally, every Trace must begin
  with a DefLabel instruction.

  DefLabel can optionally define one or more destination variables.  In that
  case, the values are passed to it by Jmp_ instruction(s) with the same
  number of sources.  The type of each destination variable is the least common
  supertype of each of the corresponding Jmp_ sources.

  Note that when a label defines destination variables, it is only reachable
  from the Jmp_ instruction.  Other branch instructions cannot pass arguments.


6. Reference manipulation

D:Cell = Unbox S0:Gen

  Unbox S0 if it is boxed, and put the resulting Cell in D.

D:BoxedCell = Box S0:Gen

  Box S0 if it is unboxed, and put the resulting BoxedCell in D.

D:PtrToCell = UnboxPtr S0:PtrToGen

  If S0 points to a cell that is KindOfRef, dereference the pointer in
  the TypedValue and return a pointer to the inner-cell in D.

D:PtrToBoxedCell = BoxPtr S0:PtrToGen

  Boxes the TypeValue that S0 points to if it is not boxed. The result
  D points to the same TypedValue as S0 but has a more refined type.

7. Loads

Some of the load instructions have an optional label parameter that
make the load also perform a runtime type check. A load that has a
label parameter present checks that the value it loads has the type T,
where T is load instruction's type parameter, and branches to its
label if the type check fails.

LdLoc and LdStack have corresponding GuardLoc and GuardStk
instructions that allow the compiler to decouple type checks from the
load operation. The type guards for locals and stacks are generated
eagerly at the start of a tracelet, while other guards (typically
generated due to type prediction) are generated at the point where the
guarded value is loaded. Allowing the checks for locals and stack to
be decoupled gives the compiler the flexibility to avoid partially
dead loads of local and stack values and to avoid unnecessarily long
live ranges due to eagerly loaded values at the start of the tracelet.

D:T = LdStack<T> S0:StkPtr S1:ConstInt

  Loads from S0 at index S1 (in cells), and puts the value in D as
  type T.

D:T = LdLoc<T,localId> S0:StkPtr

  Loads local number localId from the frame S0 and puts the value in D
  as type T.

D:PtrToGen = LdStackAddr S0:StkPtr S1:ConstInt

  Loads the address of the stack slot given by the pointer in S0 and
  the index S1 (in cells).

D:T* = LdLocAddr<T, localId> S0:StkPtr

  Loads the address of the local slot localId from the frame S0 into D.

D:T = LdMem<T> S0:PtrToGen [ -> L ]

  Loads from S0 and puts the value in D. If the optional label L is
  specified and the loaded value's type does not match T, this
  instruction does not load into D and transfers control to L.

D:T = LdProp<T> S0:Obj S1:ConstInt [ -> L ]

  Loads a property from the object referenced by S0 at the offset
  given by S1 and puts the value in D. If the optional label L is
  specified and the loaded value's type does not match T, this
  instruction does not load into D and transfers control to L.

D:T = LdRef<T> S0:Cell& [ -> L ]

  Loads the value held in the box referenced by S0 and puts the value
  in D.  If the optional label L is specified and the loaded value's
  type does not match T, this instruction does not load into D and
  transfers control to L.

D:Obj = LdThis S0:StkPtr [ -> L ]

  Loads the this pointer out of the ActRec pointed to by S0, and puts
  it in D.  If the optional label L is supplied, if the this pointer
  in S0 is not, this instruction does not load it into D and transfers
  control to the exit label L.

D:Ctx = LdCtx S0:StkPtr S1:Func

  Loads into D the value of the m_this/m_cls field out of the frame
  pointer S0 in the function given by S1. The result could be either
  an object representing the this pointer or a class context.

D:Cctx = LdCctx S0:StkPtr

  Loads into D the value of the m_cls field out of the frame pointer
  S0. The compiler should generate this only if it can prove that the
  frame does not contain a $this pointer.

D:Cls = LdClsCtx S0:Ctx

  Loads into D the class representing the current context. Extracts
  the class from the S0, which can be either the this pointer or the
  context class.

D:Cls = LdClsCctx S0:Cctx

  Loads into D the class representing the current context. Extracts
  the class from the S0, which is a context class.

D:Home = LdHome S0:StkPtr S1:ConstInt

  Logically packages the location of a pointer into the VM stack and
  an offset.  S0 will usually be the output of a DefFP.

D:T = LdConst<T>

D:ConstT = DefConst<T>

D:Cls = LdCls S0:Str S1:Cls

  Loads the class named S0 in the context of the class S1. Invokes
  autoload and may raise an error if the class is not defined. The
  explicit context parameter allows the compiler to optimize this
  instruction by simplifying it to LdClsCached, which uses the target
  cache.

D:Cls = LdClsCached S0:ConstStr

  Loads the class named S0 via the target cache. Invokes autoload and
  may raise an error if the class is not defined.

D:Cls = LdCachedClass S0:ConstStr

  Loads the class whose name is S0 out of the target cache. Returns
  null and has no side effects if the class is not defined.

D:T = LdClsCns<T> S0:ConstStr S1:ConstStr [ -> L ]

  Loads the class constant named S0 from a class named S1 via the
  target cache. This instruction should generally be followed by
  CheckInit, unless we know the class is already loaded.  If the
  optional label L is specified and the loaded value's type does not
  match T, this instruction does not load into D and transfers control
  to L. The result may be uninitialized if the class is not defined.
  Note that no decref of the result is necessary because class
  constants will always be static.

D:FuncCtx = LdClsMethodFCache S0:ConstStr S1:ConstStr
                              S2:{Obj|Cls|Ctx} L:Label

  Loads from the MethodFCache a pointer to the callee function and the
  context (ActRec's m_this/m_cls slot) into D.  S0 and S1 hold the
  names of the callee's class and method, respectively.  S2 is the
  current context.  This instruction loads the corresponding entry in
  the MethodFCache if needed.  In case the given method is not found,
  control is transferred to label L.

D:Ctx = GetCtxFwdCall S0:{Obj|Cls|Ctx} S1:Func

  Loads the context (ActRec's m_this/m_cls slot) for a forwarding call
  into D.  S0 is the current context, and S1 is the method being called.

LdClsMethodCache
LdClsMethod
LdPropAddr

D:PtrToGen = LdGblAddr S0:Str -> L

  Loads a pointer to a global. S0 is the global's name. Branches to L
  if the global is not defined.

D:PtrToGen = LdGblAddrDef S0:Str

  Loads a pointer to a global. S0 is the global's name. Defines the
  global if it is not already defined. Decrements the reference count
  of S0.

D:PtrToGen = LdClsPropAddr S0:Cls S1:Str S2:ConstCls [ -> L ]

  Loads a pointer to a static class property. S0 points to the class,
  S1 is the property name, and S2 is the class representing the
  context of the code accessing the property. If class S0 does not
  have a visible and accessible static property named S1, then this
  instruction will either (1) throw a fatal error if the optional
  label L is not present, or (2) jump to L if it is present.

D:PtrToGen = LdClsPropAddrCached S0:Cls S1:ConstStr S2:ConstStr
                                 S3:ConstCls [ -> L ]

  Loads a pointer to a static class property via the target cache. S0
  points to the class, S1 is the property name, S2 is the class name,
  and S3 is the class representing the context of the code accessing
  the property.  If class S0 does not have a visible and accessible
  static property named S1, then this instruction will either (1)
  throw a fatal error if the optional label L is not present, or (2)
  jump to L if it is present.

D:Func = LdObjMethod S0:ConstInt S1:ConstStr S2:StkPtr

D:Cls = LdObjClass S0:Obj

  Load the class out of the object in S0 and put it in D.

D:Func = LdFunc S0:Str

  Loads the Func whose name is S0.  Fatal if the named function is
  not defined, and the function autoloader fails to define it.

D:Func = LdFixedFunc S0:ConstStr

  Loads the Func whose name is S0.  Fatal if the named function is
  not defined, and the function autoloader fails to define it.

D:Func = LdCurFuncPtr

  ...

D:Func& = LdARFuncPtr S0:StkPtr S1:ConstInt

  Loads the m_func member of an ActRec.  S0 is the base address, and
  S1 is an offset, such that S0 + S1 points to the base of the ActRec.

LdFuncCls

D:PtrToCell = LdContLocalsPtr S0:Obj

  Loads a pointer to the embedded local variables of S0 (a Continuation
  object) into D.

D:T = LdRaw<T> S0:Ptr S1:ConstInt

  "Raw" load from memory.  S0 is the base address, and is an untyped
  pointer.  S1 is a constant from the RawMemSlot::Kind enum, which
  describes the offset from the base, and the size.  The value in D is
  assumed to be of type T.


8. Allocation

NewObj
NewArray
NewTuple


9. Call & Return

D:ActRec = DefActRec S0:StkPtr
                     S1:Func
                     S2:{CtxPtr|ClassPtr|Null}
                     S3:ConstInt
                     S4:{String|Null}

  Operands:

     S0 - callee frame pointer
     S1 - callee Func
     S2 - object (for FPushObjMethod*), class (for FPushClsMethod*), or
          null (for FPushFunc*).
     S3 - number of arguments
     S4 - invName field for magic calls, or null

  Defines the fields for an activation record.  May be passed to a
  SpillStack to store the fields to the stack.

D:StkPtr = FreeActRec S0:StkPtr

  Load the saved frame pointer from the activation record pointed to
  by S0 into D.

D:StkPtr = Call S0:ActRec S1:ConstInt S2:Func S3...

  Invoke the function S2 with ActRec S0 and variadic arguments S3...
  representing values to pass to the function.  S2 is the bytecode
  offset of the next instruction to execute when the call returns.

NativeImpl = S0:ConstFunc S1:StkPtr

  Execute a call to the native builtin specified by the func in S0.

D:T = CallBuiltin<T> S0:FuncPtr S1:ConstInt S2...SN

  Call builtin function. Operands:

    S0: callee Func
    S1: number of arguments to builtin
    S2..SN: arguments to builtin function

D:RetAddr = LdRetAddr S0:StkPtr

  Load the return address off of the activation record pointed to by
  S0.  The return address D is normally provided to a RetCtrl.
  Between a LdRetAddr and a RetCtrl, a FreeActRec is normally emitted
  to free the activation record S0.  This is the reason why LdRetAddr
  is a separate instruction from RetCtrl.

RetCtrl S0:{StkPtr|PtrToGen} S1:StkPtr S2:RetAddr

  Ensure that S0 is stored in rVmSp and S1 is stored in rVmFp and then
  execute a hardware procedure-return using the return address
  specified by S2.

RetVal S0:StkPtr S1:Gen

  Writes the value in S1 to the return value slot on the activation
  record pointed to by S0.

D:StkPtr = RetAdjustStack S0:StkPtr

  Loads the new VM stack pointer into the destination.  S0 is a
  pointer to the current activation record.

ReleaseVVOrExit S0:StkPtr -> L

  Loads the VarEnv slot off the ActRec pointed to by S0.  If it is
  null, does nothing.  If it is an ExtraArgs, deallocates the
  ExtraArgs structure.  Otherwise jumps to the exit-trace label L.

D:StkPtr = GenericRetDecRefs S0:StkPtr S1:Gen S2:ConstInt

  Does decrefs of all the current function's locals, where S0 is a
  pointer to the relevant activation record, and S2 is the number of
  locals in the current function.

  S1 is the return value for the function, which GenericRetDecRefs
  needs access to currently only to ensure it isn't clobbered.

  Returns the adjusted VM stack pointer (pointing at the return value
  location).

  Semantically similar to a series of DecRefLoc followed by
  RetAdjustStack.  Note that this does not store the return value even
  though it takes it as a source.


10. Stores

StMem S0:PtrToGen S1:ConstInt S2:Gen
StMemNT S0:PtrToGen S1:ConstInt S2:Gen
StProp S0:Obj S1:Int S2:Gen
StPropNT S0:Obj S1:Int S2:Gen

StLoc<localId> S0:StkPtr S1:Gen

  Store S1 to local number localId on the frame pointed to by S0.

StLocNT<localId> S0:StkPtr S1:Gen

  Store S1 to local number localId on the frame pointed to by S0,
  without storing the type.

StRef
StRefNT
StRaw

D:StkPtr = SpillStack         S0:StkP S1:ConstInt, S2...

  SpillStack synchronizes the virtual execution stack with the
  physical stack by storing a variadic list of SSATmps to the physical
  stack.

  Operands:

     S0      - current stack pointer

     S1      - stack deficit; indicates the number of elements that
               need to be logically popped before the variadic list
               is pushed

     S2...   - variadic list of elements to spill, with values
               representing cells or ActRecs.  Each temp of type
               ActRec is followed by kSpillStackActRecExtraArgs for
               the contents of the ActRec.


11. Trace exits

ExitTrace S0:ConstFunc S1:ConstInt S2:StkPtr S3:StkPtr
          [S4:TCA]

  Unconditional exit to bytecode offset S1 in function S0.  S2 and
  S3 are the VM stack and frame pointers, respectively.  If given,
  S4 is the address of a jmp instruction to patch later.

  [Implementation note.  S4 refers to a branch instruction, but the
  type is really None.  We access the branch instruction to find
  the TCA to use, at compile time.  In effect, S4 is simply a
  compile-time pointer to the IRInstruction to patch].

ExitTraceCc S0:ConstFunc S1:ConstInt S2:StkPtr S3:StkPtr
            S4:ConstInt [S5:TCA]

  Exit conditionally to bytecode offset S1 or S4 in function S0.
  S4 is bytecode address to exit to if the condition is false.
  S2 and S3 are the VM stack and frame pointer, respectively.

ExitGuardFailure S0:ConstFunc S1:ConstInt S2:StkPtr S3:StkPtr

  A start-of-trace guard failed before the trace began executing.
  Runtime may retranslate the bytecode using HHIR.  S1 is the
  bytecode offset, S2 and S3 are the VM stack and frame pointer.

ExitSlow S0:ConstFunc S1:ConstInt S2:StkPtr S3:StkPtr

  Like ExitTrace, but with a runtime hint to not use HHIR at this func/pc
  position in the future.  Runtime may start a new trace using Tx64 or
  interpreter.

ExitSlowNoProgress S0:ConstFunc, S1:ConstInt, S2:StkPtr, S3:StkPtr

  Like ExitGuardFailure, with the "slow" hint from ExitSlow.
  In this case we can retranslate or interprete the whole tracelet since
  it didn't make any progress.


12. Refcounting and copies

Mov

D:T* = LdAddr S0:T* S1:ConstInt

  Load address. Returns a pointer to (S0 + S1) with the same type as S0.

IncRef

DecRefLoc<localId> S0:StkPtr

  DecRef the local given by localId on the frame S0.

DecRefStack<T> S0:StkPtr S1:ConstInt

  DecRef a value of type T at offset S1 on the stack pointed to by S0.

DecRefThis

DecRef S0:Gen

  Decrease the reference count of S0 by one, and call a destructor for
  types that require it if it goes to zero.

DecRefMem S0:PtrToGen S1:ConstInt

  Decref the value pointed to by S0 at offset S1 (in bytes), calling
  any appropriate destructor if the refcount goes to zero.

DecRefNZ S0:Gen

  Decrease the reference count of S0 by one, do not check if it goes
  to zero.  This instruction can be used for more efficient code when
  it is provable that the reference count cannot go to zero.


13. Misc

D:StkPtr = DefFP

  Creates a temporary D representing the current vm frame pointer.

D:StkPtr = DefSP S0:StkPtr S1:ConstInt

  Creates a temporary D representing the current vm stack pointer.  S0
  is a pointer to the current frame, and S1 is the offset between the
  stack pointer and the frame pointer.  (XXX: this doesn't work
  because of continuations, and is unused.)

Nop

  Does nothing.  It's sometimes useful for the simplifier to insert
  one of these in the instruction stream.


14. Runtime helpers

RaiseUninitLoc<localId>

  Raise a notice for an uninitialized local variable.

DefCns S0:ConstStr S0:Cell

  Defines the constant with name S0 to be the value S1. If S0 has a refcounted
  type, this instruction consumes its refcount.

Print
AddElem
AddNewElem
Concat
ArrayAdd
DefCls
DefFunc
AKExists

D:Int LdSwitchDblIndex S0:Dbl S1:Int S2:Int
D:Int LdSwitchStrIndex S0:Str S1:Int S2:Int
D:Int LdSwitchObjIndex S0:Obj S1:Int S2:Int

  These instructions are used to determine the target of a switch
  statement with target range [S1:S1 + S2), when invoked with the value S0.
  They call helper functions to check whether S0 is an numeric integer
  in the range [S1:S1 + S2), and if so return the value S1 - (Int)S0.
  Else, they return the target of the default target, S2 + 1.

D:StkPtr InterpOne S0:StkPtr S1:StkPtr S2:ConstInt S3:ConstInt
                     S4:ConstInt [ -> L ]

  Call the interpreter implementation function for one opcode.  S0 and
  S1 are the VM frame and stack pointers, respectively.  S2 is the bytecode
  offset.  S3 is the number of cells to adjust the stack pointer before
  running the interpreter function.  S4 is the VM DataType of the return
  type for the opcode.  Returns the updated VM stack pointer.


15. Register allocation

D:T = Spill S0:T

  Stores S0 to a spill location specified by the destination.  The
  destination temporary will not have registers allocated to it.

D:T = Reload S0:T

  Loads from a spilled temporary S0, and stores the result in D.

AllocSpill S0:ConstInt

  Allocates S0 slots of additional spill space on the stack.
  Generated when the preallocated spill space is exhausted.

FreeSpill S0:ConstInt

  Deallocates S0 slots of spill space on the stack.


16. Continuations

CreateCont
FillContLocals
FillContThis

ContEnter S0:StkPtr S1:TCA S2:ConstInt

  Enters a generator body. S0 is the ActRec embedded in the Continuation
  object. S1 is the address to jump to. S2 is the bytecode offset in the
  caller to return to when the generator body yields.

UnlinkContVarEnv
LinkContVarEnv
ContRaiseCheck
ContPreNext
ContStartedCheck


17. Debugging and instrumentation

IncStat S0:ConstInt S1:ConstInt S2:ConstBool

  Increment stat counter. S0 is the implementation defined stat counter index,
  S1 is the amount to increment the counter (may be negative), and S2 is a
  'force' flag. This opcode becomes a noop iff (force == false and runtime
  stats are not enabled) at translation time.

DbgAssertRefCount S0:{Counted|StaticStr|StaticArr}

  Assert that S0 has a valid refcount.  S0 must be a type with a valid
  (counted or static) _count field.  If S0's count is implausible then
  execute a hardware trap instruction (int3 on x64).

DbgAssertPtr S0:PtrToGen

  Assert that S0 points to plausible TypedValue.  If the TypedValue is a
  type with a _count field, check that the count field is plausible using
  the same logic as DbgAssertRefCount.  Internally this uses always_assert();
  failures cause an abort (whatever always_assert does).


18. Iterators

D:Bool = IterInit S0:{Arr|Obj} S1:StkPtr S2:ConstInt S3:ConstInt
D:Bool = IterInitK S0:{Arr|Obj} S1:StkPtr S2:ConstInt S3:ConstInt S4:ConstInt

  Initializes the iterator variable whose index is given by S2. This
  instruction creates the appropriate iterator for the array or object
  that S0 references, and rewinds the new iterator to its start.  S3
  and S4 are local variable indices. S0 points to the stack frame
  containing the iterator and local variables S2, S3, and S4.

  If the new iterator is at its end (i.e., has no elements to iterate
  over), this instruction decrements the refcount of S0 and returns
  false; otheriwse, it stores a reference to S0 in the new iterator
  and returns true. If the iterator is not at its end, then this
  instruction stores the iterator's first value (and key) into the
  local variable S3 (and S4, respectively).

  This instruction has the ConsumesRC property because it either
  decrements the reference count of s0 or stores a reference to S0
  into the new iterator.

D:Bool = IterNext S0:StkPtr S1:ConstInt S2:ConstInt
D:Bool = IterNextK S0:StkPtr S1:ConstInt S2:ConstInt S3:ConstInt

  Advances the iterator variable whose index is given by S1. S2 and S3
  are local variable indices. S0 points to the stack frame containing
  the iterator and local variables S1, S2, and S3.

  If the iterator has reached the end, this instruction frees the
  iterator variable and returns false; otherwise, it returns true.  If
  the iterator has not reached its end, then this instruction stores
  the iterator's next value (and key) into the local variable S3 (and
  S4, respectively).

IterFree S0:StkPtr S1:ConstInt

  Free the iterator variable whose index is given by S1 in the stack
  frame pointed to by S0.

19. Vector instruction support

D:PtrToCell = DefMIStateBase

  Declares a base register for MInstrState. Currently this is always %rsp

All of the remaining opcodes in this section are simple wrappers
around helper functions (specified in S0) to perform the corresponding
vector operation. If S1 is a ConstCls it represents the context class
for the operation. D:Vector indicates that the return value of the
opcode depends on the input types:

SetElem/SetOpElem/IncDecElem:
- If the base is not a subtype of Type::Arr or Type::Obj, the
  operation will fail with a warning and the return value is
  null. Otherwise the return value is the same as the value input.

SetProp/SetOpProp/IncDecProp:
- If the base is not a subtype of Type::Obj, the operation will fail
  with a warning and the return value is null. Otherwise the return
  value is the same as the value input.


D:PtrToGen = PropX S0:ConstTCA S1:ConstCls S2:{Obj|PtrToGen} S3:Gen S4:PtrToCell

  Lookup intermediate property in S2, with key S3. S4 should point to
  an MInstrState struct.

D:Cell = CGetProp S0:ConstTCA S1:ConstCls S2:{Obj|PtrToGen} S3:Gen S4:PtrToCell

  Get property with key S3 from S2. S4 should point to an MInstrState
  struct.

D:Vector = SetProp S0:ConstTCA S1:ConstCls S2:{Obj|PtrToGen} S3:Gen S4:Cell

  Set property with key S3 in S2 to S4.

D:PtrToGen = ElemX S0:ConstTCA S1:PtrToGen S2:Gen S3:PtrToCell

  Get intermediate element with key S2 from base S1. The base will not be
  modified. S3 should point to an MInstrState struct.

D:PtrToGen = ElemDX S0:ConstTCA S1:PtrToGen S2:Gen S3:PtrToCell

  Like ElemX, but used for intermediate element lookups that may
  modify the base.

D:Cell = CGetElem S0:ConstTCA S1:PtrToGen S2:Gen S3:PtrToCell

  Get element with key S2 from S1. S3 should point to an MInstrState
  struct.

D:Vector = SetElem S0:ConstTCA S1:PtrToGen S2:Gen S3:Cell

  Set element with key S2 in S1 to S3.

D:Vector = SetNewElem S0:GenPtr S1:Cell

  Append the value in S1 to S0.

D:Bool = IssetElem S0:ConstTCA S1:PtrToGen S2:Gen S3:PtrToCell

  Returns true iff the element at key S2 in S1 is set.

D:Bool = EmptyElem S0:ConstTCA S1:PtrToGen S2:Gen S3:PtrToCell

  Returns true iff the element at key S2 in S1 is set and not equal
  (as defined by the hhbc Eq instruction) to false.
