mesa/docs/drivers/amd/live-var-analysis.rst

:orphan:

.. _aco-live-var-analysis:

Description of live variable analysis in ACO
============================================

Operand flags
-------------

Operands can have several different flags which are set by live variable analysis:

* ``isKill``: this operand is not live after the instruction
* ``isFirstKill``: this is the first instance of a temporary in the instruction with ``isKill=true``
* ``isLateKill``: this operand cannot use the same registers as any definition
* ``isClobbered``: this operand will use some of the same registers as a definition
* ``isCopyKill``: this operand must use a different register than earlier instances of the same temporary in the
  instruction's operand list

Note that:

* ``isFirstKill=true`` requires that the operand is also ``isKill=true``.
* If ``isKill=true``, then ``isLateKill=true`` requires that the operand is also ``isFirstKill=true`` or
  ``isCopyKill=true``.
* ``isCopyKill=true`` is incompatible with ``isFirstKill=true`` in the same operand.
* ``isLateKill=true`` cannot be used with ``isClobbered=true`` for the same temporary in an instruction.
* If ``isCopyKill=true``, then the operand will also have ``isKill=true``, even if the temporary is live after the
  instruction.

Operands and definitions can be "tied", indicated by ``get_tied_defs()``, meaning that the must use the same registers:

* Operands tied to definitions have ``isClobbered=true``.
* If a clobbered operand has ``isKill=false``, it will be moved to a different register.
* If two operands of the same temporary are tied to different definitions of the same instruction, the second of those
  operands will have ``isCopyKill=true``.

There also exists the ``isVectorAligned`` flag. This can be used to define a vector of operands, starting with
``isVectorAligned=true`` and ending with ``isVectorAligned=false``, which must be placed in consecutive registers.

To prevent issues with register allocation, an operand being part of a vector means:

* Unless a vector is tied to a definition, it will also have ``isLateKill=true``, so that a partially killed vectors
  are not required to share the same space with definitions.
* If two operands of the same temporary are both part of vectors in the same instruction, the second of those operands
  will have ``isCopyKill=true``.

Register demand calculation
---------------------------

``live_in``
   temporaries live before the instruction

``live_out``
   temporaries live after the instruction

``live_through``
   temporaries live both before and after the instruction

``live_definitions``
   temporaries defined and used later (definitions where ``isKill=false``)

``dead_definitions``
   temporaries defined and not used later (definitions where ``isKill=true``)

``early_kill_operands``
   temporaries killed which are not marked late kill (operands where ``isFirstKill=true && isLateKill=false``)

``late_kill_operands``
   temporaries killed which are marked late kill (operands where ``isFirstKill=true && isLateKill=true``)

``first_kill_operands``
   temporaries killed by the instruction (operands where ``isFirstKill=true``)

   ``early_kill_operands + late_kill_operands``

``copied_operands``
   operands which are either clobbered but not killed, or copy-kill (operands where
   ``isCopyKill=true || (isClobbered=true && isKill=false)``)

``early_kill_copies``
   ``copied_operands`` which are not marked late kill (operands where
   ``(isCopyKill=true && isLateKill=false) || (isClobbered=true && isKill=false)``)

``late_kill_copies``
   ``copied_operands`` which are marked late kill (operands where ``(isCopyKill=true && isLateKill=true)``)

``live_out``
   ``live_through + live_definitions``

   ``live_in - first_kill_operands + live_definitions``

``live_in``
   ``live_out - live_definitions + first_kill_operands``

   ``live_through + first_kill_operands``

``live_through``
   ``live_out - live_definitions``

   ``live_in - first_kill_operands``

Breakdown of register demand stages using ``live_in``:

* stage 0: before instruction: ``live_in``
* stage 1:     setup operands: ``live_in + early_kill_copies + late_kill_copies``
* stage 2: during instruction: ``live_in - early_kill_operands + late_kill_copies``
* stage 3:  write definitions: ``live_in - early_kill_operands + late_kill_copies + live_definitions + dead_definitions``
* stage 4:  after instruction: ``live_in - early_kill_operands - late_kill_operands + live_definitions``

Breakdown of register demand stages using ``live_through``:

* stage 0: before instruction: ``live_through + late_kill_operands + early_kill_operands``
* stage 1:     setup operands: ``live_through + late_kill_operands + early_kill_operands + early_kill_copies + late_kill_copies``
* stage 2: during instruction: ``live_through + late_kill_operands + late_kill_copies``
* stage 3:  write definitions: ``live_through + late_kill_operands + late_kill_copies + live_definitions + dead_definitions``
* stage 4:  after instruction: ``live_through + live_definitions``

Breakdown of register demand stages using ``live_out``:

* stage 0: before instruction: ``live_out - live_definitions + late_kill_operands + early_kill_operands``
* stage 1:     setup operands: ``live_out - live_definitions + late_kill_operands + early_kill_operands + early_kill_copies + late_kill_copies``
* stage 2: during instruction: ``live_out - live_definitions + late_kill_operands + late_kill_copies``
* stage 3:  write definitions: ``live_out + dead_definitions + late_kill_operands + late_kill_copies``
* stage 4:  after instruction: ``live_out``

If instruction B immediately follows instruction A, then stage 0 of instruction B equals stage 4 of instruction A.
``Instruction::register_demand`` is ``max(stage1, stage3)``, which is equal to the maximum of all stages.

There are a few helper functions for examining how an instruction changes register demand:

``get_live_changes()``
   This is the register demand change from killed temporaries and live definitions.

   ``live_definitions - first_kill_operands``

   equal to ``live_out - live_in``

``get_temp_registers()``
   This is the temporary increase in register demand needed for copy-kill operands, late-kill operands, clobbered
   operands, and dead definitions.

   ``max(early_kill_operands + late_kill_operands + early_kill_copies + late_kill_copies - live_definitions, late_kill_operands + late_kill_copies + dead_definitions)``

   equal to ``register_demand - live_out``

``get_temp_reg_changes()``
   Since ``register_demand`` is ``max(stage1, stage3)``, this can be used to know what's the effect of marking an
   operand killed will be.

   ``live_definitions + dead_definitions - early_kill_operands - early_kill_copies``

   equal to ``stage3 - stage1``

They can be used as follows:

* ``register_demand(a) = live_in(a) + live_changes(a) + temp_registers(a)``
* ``register_demand(a) = live_out(a) + temp_registers(a)``

Assuming ``stage4(a)==stage0(b)``:

* ``register_demand(a) = register_demand(b) - temp_registers(b) - live_changes(b) + temp_registers(a)``
* ``register_demand(b) = register_demand(a) - temp_registers(a) + live_changes(b) + temp_registers(b)``

(note that ``max(a + b, a + c) - max(b, c) = a`` and ``a + max(b, c) = max(a + b, a + c)``)