Previous: Maintaining the CFG, Up: Control Flow
13.5 Liveness information
Liveness information is useful to determine whether some register is “live” at given point of program, i.e. that it contains a value that may be used at a later point in the program. This information is used, for instance, during register allocation, as the pseudo registers only need to be assigned to a unique hard register or to a stack slot if they are live. The hard registers and stack slots may be freely reused for other values when a register is dead.
The liveness information is stored partly in the RTL instruction
stream and partly in the flow graph. Local information is stored in
the instruction stream:
Each instruction may contain REG_DEAD notes representing that
the value of a given register is no longer needed, or
REG_UNUSED notes representing that the value computed by the
instruction is never used. The second is useful for instructions
computing multiple values at once.
Global liveness information is stored in the control flow graph.
Each basic block contains two bitmaps, global_live_at_start and
global_live_at_end representing liveness of each register at
the entry and exit of the basic block. The file flow.c
contains functions 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 code modifying passes. This can be easily
accomplished using the flags field of a basic block. Functions
modifying the instruction stream automatically set the BB_DIRTY
flag of a modifies basic block, so the pass may simply
useclear_bb_flags before doing any modifications and then ask
the data flow module to have liveness updated via the
update_life_info_in_dirty_blocks function.
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 analysis may produce invalid results or get into an infinite cycle when the initial solution is not below the desired one. Only simple transformations, like splitting basic blocks or inserting on edges, are safe, as functions to implement them already know how to update liveness information locally.