Liveness Information

Liveness information is useful to determine whether register X is ``live'' at given point of program, that means that it contains important value. This information is used, for instance, during register allocation pass, as the pseudo registers need to be assigned to unique hard register or stack slot only when they are live. The hard registers and stack slots may be freely reused for other values when they are dead.

The liveness information is stored partly in the RTL instruction chain and partly in the flow graph. RTL chain stores local information: each instruction may contain REG_DEAD note representing that value of given register is no longer needed or REG_UNUSED note representing that the value computed by instruction is never used. The second is useful for instructions computing multiple values at once.

Each basic block contains bitmaps representing liveness of each register at entry and exit of basic block (global_live_at_start and global_live_at_end). flow.c contains function to compute liveness of each register at any given place in the instruction stream using this information.

Liveness is expensive to compute and thus it is desirable to keep it up to date during optimization passes. This can be easily accomplished using flags field of basic block. The functions modifying instruction stream automatically set BB_DIRTY flag of basic block, so the pass may simply use clear_bb_for_blocks before doing any modifications and then ask dataflow modulule via function update_life_info_in_dirty_blocks to get liveness updated.

This scheme works reliably as long as no control flow graph transformations are done. The task of updating liveness after control flow graph changes is more difficult as normal iterative data flow may produce invalid results or get into cycle when the initial solution is not bellow the desired one. Only simple transformations, like splitting basic blocks or emitting to the edge are safe, as functions to implement them already know how to update liveness locally.