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