| 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. |