third_party/subzero/docs/LOWERING.rst

Target-specific lowering in ICE
===============================

This document discusses several issues around generating target-specific ICE
instructions from high-level ICE instructions.

Meeting register address mode constraints
-----------------------------------------

Target-specific instructions often require specific operands to be in physical
registers.  Sometimes one specific register is required, but usually any
register in a particular register class will suffice, and that register class is
defined by the instruction/operand type.

The challenge is that ``Variable`` represents an operand that is either a stack
location in the current frame, or a physical register.  Register allocation
happens after target-specific lowering, so during lowering we generally don't
know whether a ``Variable`` operand will meet a target instruction's physical
register requirement.

To this end, ICE allows certain directives:

    * ``Variable::setWeightInfinite()`` forces a ``Variable`` to get some
      physical register (without specifying which particular one) from a
      register class.

    * ``Variable::setRegNum()`` forces a ``Variable`` to be assigned a specific
      physical register.

These directives are described below in more detail.  In most cases, though,
they don't need to be explicity used, as the routines that create lowered
instructions have reasonable defaults and simple options that control these
directives.

The recommended ICE lowering strategy is to generate extra assignment
instructions involving extra ``Variable`` temporaries, using the directives to
force suitable register assignments for the temporaries, and then let the
register allocator clean things up.

Note: There is a spectrum of *implementation complexity* versus *translation
speed* versus *code quality*.  This recommended strategy picks a point on the
spectrum representing very low complexity ("splat-isel"), pretty good code
quality in terms of frame size and register shuffling/spilling, but perhaps not
the fastest translation speed since extra instructions and operands are created
up front and cleaned up at the end.

Ensuring a non-specific physical register
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The x86 instruction::

    mov dst, src

needs at least one of its operands in a physical register (ignoring the case
where ``src`` is a constant).  This can be done as follows::

    mov reg, src
    mov dst, reg

so long as ``reg`` is guaranteed to have a physical register assignment.  The
low-level lowering code that accomplishes this looks something like::

    Variable *Reg;
    Reg = Func->makeVariable(Dst->getType());
    Reg->setWeightInfinite();
    NewInst = InstX8632Mov::create(Func, Reg, Src);
    NewInst = InstX8632Mov::create(Func, Dst, Reg);

``Cfg::makeVariable()`` generates a new temporary, and
``Variable::setWeightInfinite()`` gives it infinite weight for the purpose of
register allocation, thus guaranteeing it a physical register (though leaving
the particular physical register to be determined by the register allocator).

The ``_mov(Dest, Src)`` method in the ``TargetX8632`` class is sufficiently
powerful to handle these details in most situations.  Its ``Dest`` argument is
an in/out parameter.  If its input value is ``nullptr``, then a new temporary
variable is created, its type is set to the same type as the ``Src`` operand, it
is given infinite register weight, and the new ``Variable`` is returned through
the in/out parameter.  (This is in addition to the new temporary being the dest
operand of the ``mov`` instruction.)  The simpler version of the above example
is::

    Variable *Reg = nullptr;
    _mov(Reg, Src);
    _mov(Dst, Reg);

Preferring another ``Variable``'s physical register
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

(An older version of ICE allowed the lowering code to provide a register
allocation hint: if a physical register is to be assigned to one ``Variable``,
then prefer a particular ``Variable``'s physical register if available.  This
hint would be used to try to reduce the amount of register shuffling.
Currently, the register allocator does this automatically through the
``FindPreference`` logic.)

Ensuring a specific physical register
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Some instructions require operands in specific physical registers, or produce
results in specific physical registers.  For example, the 32-bit ``ret``
instruction needs its operand in ``eax``.  This can be done with
``Variable::setRegNum()``::

    Variable *Reg;
    Reg = Func->makeVariable(Src->getType());
    Reg->setWeightInfinite();
    Reg->setRegNum(Reg_eax);
    NewInst = InstX8632Mov::create(Func, Reg, Src);
    NewInst = InstX8632Ret::create(Func, Reg);

Precoloring with ``Variable::setRegNum()`` effectively gives it infinite weight
for register allocation, so the call to ``Variable::setWeightInfinite()`` is
technically unnecessary, but perhaps documents the intention a bit more
strongly.

The ``_mov(Dest, Src, RegNum)`` method in the ``TargetX8632`` class has an
optional ``RegNum`` argument to force a specific register assignment when the
input ``Dest`` is ``nullptr``.  As described above, passing in ``Dest=nullptr``
causes a new temporary variable to be created with infinite register weight, and
in addition the specific register is chosen.  The simpler version of the above
example is::

    Variable *Reg = nullptr;
    _mov(Reg, Src, Reg_eax);
    _ret(Reg);

Disabling live-range interference
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

(An older version of ICE allowed an overly strong preference for another
``Variable``'s physical register even if their live ranges interfered.  This was
risky, and currently the register allocator derives this automatically through
the ``AllowOverlap`` logic.)

Call instructions kill scratch registers
----------------------------------------

A ``call`` instruction kills the values in all scratch registers, so it's
important that the register allocator doesn't allocate a scratch register to a
``Variable`` whose live range spans the ``call`` instruction.  ICE provides the
``InstFakeKill`` pseudo-instruction to compactly mark such register kills.  For
each scratch register, a fake trivial live range is created that begins and ends
in that instruction.  The ``InstFakeKill`` instruction is inserted after the
``call`` instruction.  For example::

    CallInst = InstX8632Call::create(Func, ... );
    NewInst = InstFakeKill::create(Func, CallInst);

The last argument to the ``InstFakeKill`` constructor links it to the previous
call instruction, such that if its linked instruction is dead-code eliminated,
the ``InstFakeKill`` instruction is eliminated as well.  The linked ``call``
instruction could be to a target known to be free of side effects, and therefore
safe to remove if its result is unused.

Instructions producing multiple values
--------------------------------------

ICE instructions allow at most one destination ``Variable``.  Some machine
instructions produce more than one usable result.  For example, the x86-32
``call`` ABI returns a 64-bit integer result in the ``edx:eax`` register pair.
Also, x86-32 has a version of the ``imul`` instruction that produces a 64-bit
result in the ``edx:eax`` register pair.  The x86-32 ``idiv`` instruction
produces the quotient in ``eax`` and the remainder in ``edx``, though generally
only one or the other is needed in the lowering.

To support multi-dest instructions, ICE provides the ``InstFakeDef``
pseudo-instruction, whose destination can be precolored to the appropriate
physical register.  For example, a ``call`` returning a 64-bit result in
``edx:eax``::

    CallInst = InstX8632Call::create(Func, RegLow, ... );
    NewInst = InstFakeKill::create(Func, CallInst);
    Variable *RegHigh = Func->makeVariable(IceType_i32);
    RegHigh->setRegNum(Reg_edx);
    NewInst = InstFakeDef::create(Func, RegHigh);

``RegHigh`` is then assigned into the desired ``Variable``.  If that assignment
ends up being dead-code eliminated, the ``InstFakeDef`` instruction may be
eliminated as well.

Managing dead-code elimination
------------------------------

ICE instructions with a non-nullptr ``Dest`` are subject to dead-code
elimination.  However, some instructions must not be eliminated in order to
preserve side effects.  This applies to most function calls, volatile loads, and
loads and integer divisions where the underlying language and runtime are
relying on hardware exception handling.

ICE facilitates this with the ``InstFakeUse`` pseudo-instruction.  This forces a
use of its source ``Variable`` to keep that variable's definition alive.  Since
the ``InstFakeUse`` instruction has no ``Dest``, it will not be eliminated.

Here is the full example of the x86-32 ``call`` returning a 32-bit integer
result::

    Variable *Reg = Func->makeVariable(IceType_i32);
    Reg->setRegNum(Reg_eax);
    CallInst = InstX8632Call::create(Func, Reg, ... );
    NewInst = InstFakeKill::create(Func, CallInst);
    NewInst = InstFakeUse::create(Func, Reg);
    NewInst = InstX8632Mov::create(Func, Result, Reg);

Without the ``InstFakeUse``, the entire call sequence could be dead-code
eliminated if its result were unused.

One more note on this topic.  These tools can be used to allow a multi-dest
instruction to be dead-code eliminated only when none of its results is live.
The key is to use the optional source parameter of the ``InstFakeDef``
instruction.  Using pseudocode::

    t1:eax = call foo(arg1, ...)
    InstFakeKill  // eax, ecx, edx
    t2:edx = InstFakeDef(t1)
    v_result_low = t1
    v_result_high = t2

If ``v_result_high`` is live but ``v_result_low`` is dead, adding ``t1`` as an
argument to ``InstFakeDef`` suffices to keep the ``call`` instruction live.

Instructions modifying source operands
--------------------------------------

Some native instructions may modify one or more source operands.  For example,
the x86 ``xadd`` and ``xchg`` instructions modify both source operands.  Some
analysis needs to identify every place a ``Variable`` is modified, and it uses
the presence of a ``Dest`` variable for this analysis.  Since ICE instructions
have at most one ``Dest``, the ``xadd`` and ``xchg`` instructions need special
treatment.

A ``Variable`` that is not the ``Dest`` can be marked as modified by adding an
``InstFakeDef``.  However, this is not sufficient, as the ``Variable`` may have
no more live uses, which could result in the ``InstFakeDef`` being dead-code
eliminated.  The solution is to add an ``InstFakeUse`` as well.

To summarize, for every source ``Variable`` that is not equal to the
instruction's ``Dest``, append an ``InstFakeDef`` and ``InstFakeUse``
instruction to provide the necessary analysis information.