| 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 hints/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. |
| |
| * ``Variable::setPreferredRegister()`` registers a preference for a physical |
| register based on another ``Variable``'s physical register assignment. |
| |
| These hints/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 hints/directives. |
| |
| The recommended ICE lowering strategy is to generate extra assignment |
| instructions involving extra ``Variable`` temporaries, using the |
| hints/directives to force suitable register assignments for the temporaries, and |
| then let the global 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 some 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. |
| |
| 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 ``NULL``, 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 = NULL; |
| _mov(Reg, Src); |
| _mov(Dst, Reg); |
| |
| Preferring another ``Variable``'s physical register |
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| |
| One problem with this example is that the register allocator usually just |
| assigns the first available register to a live range. If this instruction ends |
| the live range of ``src``, this may lead to code like the following:: |
| |
| mov reg:eax, src:esi |
| mov dst:edi, reg:eax |
| |
| Since the first instruction happens to end the live range of ``src:esi``, it |
| would be better to assign ``esi`` to ``reg``:: |
| |
| mov reg:esi, src:esi |
| mov dst:edi, reg:esi |
| |
| The first instruction, ``mov esi, esi``, is a redundant assignment and will |
| ultimately be elided, leaving just ``mov edi, esi``. |
| |
| We can tell the register allocator to prefer the register assigned to a |
| different ``Variable``, using ``Variable::setPreferredRegister()``:: |
| |
| Variable *Reg; |
| Reg = Func->makeVariable(Dst->getType()); |
| Reg->setWeightInfinite(); |
| Reg->setPreferredRegister(Src); |
| NewInst = InstX8632Mov::create(Func, Reg, Src); |
| NewInst = InstX8632Mov::create(Func, Dst, Reg); |
| |
| Or more simply:: |
| |
| Variable *Reg = NULL; |
| _mov(Reg, Src); |
| _mov(Dst, Reg); |
| Reg->setPreferredRegister(llvm::dyn_cast<Variable>(Src)); |
| |
| The usefulness of ``setPreferredRegister()`` is tied into the implementation of |
| the register allocator. ICE uses linear-scan register allocation, which sorts |
| live ranges by starting point and assigns registers in that order. Using |
| ``B->setPreferredRegister(A)`` only helps when ``A`` has already been assigned a |
| register by the time ``B`` is being considered. For an assignment ``B=A``, this |
| is usually a safe assumption because ``B``'s live range begins at this |
| instruction but ``A``'s live range must have started earlier. (There may be |
| exceptions for variables that are no longer in SSA form.) But |
| ``A->setPreferredRegister(B)`` is unlikely to help unless ``B`` has been |
| precolored. In summary, generally the best practice is to use a pattern like:: |
| |
| NewInst = InstX8632Mov::create(Func, Dst, Src); |
| Dst->setPreferredRegister(Src); |
| //Src->setPreferredRegister(Dst); -- unlikely to have any effect |
| |
| 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 ``NULL``. As described above, passing in ``Dest=NULL`` 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 = NULL; |
| _mov(Reg, Src, Reg_eax); |
| _ret(Reg); |
| |
| Disabling live-range interference |
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| |
| Another problem with the "``mov reg,src; mov dst,reg``" example happens when |
| the instructions do *not* end the live range of ``src``. In this case, the live |
| ranges of ``reg`` and ``src`` interfere, so they can't get the same physical |
| register despite the explicit preference. However, ``reg`` is meant to be an |
| alias of ``src`` so they needn't be considered to interfere with each other. |
| This can be expressed via the second (bool) argument of |
| ``setPreferredRegister()``:: |
| |
| Variable *Reg; |
| Reg = Func->makeVariable(Dst->getType()); |
| Reg->setWeightInfinite(); |
| Reg->setPreferredRegister(Src, true); |
| NewInst = InstX8632Mov::create(Func, Reg, Src); |
| NewInst = InstX8632Mov::create(Func, Dst, Reg); |
| |
| This should be used with caution and probably only for these short-live-range |
| temporaries, otherwise the classic "lost copy" or "lost swap" problem may be |
| encountered. |
| |
| Instructions with register side effects |
| --------------------------------------- |
| |
| Some instructions produce unwanted results in other registers, or otherwise kill |
| preexisting values in other registers. For example, a ``call`` kills the |
| scratch registers. Also, the x86-32 ``idiv`` instruction produces the quotient |
| in ``eax`` and the remainder in ``edx``, but generally only one of those is |
| needed in the lowering. It's important that the register allocator doesn't |
| allocate that register to a live range that spans the instruction. |
| |
| ICE provides the ``InstFakeKill`` pseudo-instruction to mark such register |
| kills. For each of the instruction's source variables, 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, ... ); |
| VarList KilledRegs; |
| KilledRegs.push_back(eax); |
| KilledRegs.push_back(ecx); |
| KilledRegs.push_back(edx); |
| NewInst = InstFakeKill::create(Func, KilledRegs, 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 killed register arguments need to be assigned a physical register via |
| ``Variable::setRegNum()`` for this to be effective. To avoid a massive |
| proliferation of ``Variable`` temporaries, the ``TargetLowering`` object caches |
| one precolored ``Variable`` for each physical register:: |
| |
| CallInst = InstX8632Call::create(Func, ... ); |
| VarList KilledRegs; |
| Variable *eax = Func->getTarget()->getPhysicalRegister(Reg_eax); |
| Variable *ecx = Func->getTarget()->getPhysicalRegister(Reg_ecx); |
| Variable *edx = Func->getTarget()->getPhysicalRegister(Reg_edx); |
| KilledRegs.push_back(eax); |
| KilledRegs.push_back(ecx); |
| KilledRegs.push_back(edx); |
| NewInst = InstFakeKill::create(Func, KilledRegs, CallInst); |
| |
| On first glance, it may seem unnecessary to explicitly kill the register that |
| returns the ``call`` return value. However, if for some reason the ``call`` |
| result ends up being unused, dead-code elimination could remove dead assignments |
| and incorrectly expose the return value register to a register allocation |
| assignment spanning the call, which would be incorrect. |
| |
| 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. |
| |
| 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, KilledRegs, 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. |
| |
| Preventing dead-code elimination |
| -------------------------------- |
| |
| ICE instructions with a non-NULL ``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, ... ); |
| VarList KilledRegs; |
| Variable *eax = Func->getTarget()->getPhysicalRegister(Reg_eax); |
| Variable *ecx = Func->getTarget()->getPhysicalRegister(Reg_ecx); |
| Variable *edx = Func->getTarget()->getPhysicalRegister(Reg_edx); |
| KilledRegs.push_back(eax); |
| KilledRegs.push_back(ecx); |
| KilledRegs.push_back(edx); |
| NewInst = InstFakeKill::create(Func, KilledRegs, 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. |