path: root/gcc/doc/cfg.texi

@c -*-texinfo-*-
@c Copyright (C) 2001-2021 Free Software Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.

@c ---------------------------------------------------------------------
@c Control Flow Graph
@c ---------------------------------------------------------------------

@node Control Flow
@chapter Control Flow Graph
@cindex CFG, Control Flow Graph
@findex basic-block.h

A control flow graph (CFG) is a data structure built on top of the
intermediate code representation (the RTL or @code{GIMPLE} instruction
stream) abstracting the control flow behavior of a function that is
being compiled.  The CFG is a directed graph where the vertices
represent basic blocks and edges represent possible transfer of
control flow from one basic block to another.  The data structures
used to represent the control flow graph are defined in
@file{basic-block.h}.

In GCC, the representation of control flow is maintained throughout
the compilation process, from constructing the CFG early in 
@code{pass_build_cfg} to @code{pass_free_cfg} (see @file{passes.def}).
The CFG takes various different modes and may undergo extensive
manipulations, but the graph is always valid between its construction
and its release.  This way, transfer of information such as data flow,
a measured profile, or the loop tree, can be propagated through the
passes pipeline, and even from @code{GIMPLE} to @code{RTL}.

Often the CFG may be better viewed as integral part of instruction
chain, than structure built on the top of it.  Updating the compiler's
intermediate representation for instructions cannot be easily done
without proper maintenance of the CFG simultaneously.

@menu
* Basic Blocks::           The definition and representation of basic blocks.
* Edges::                  Types of edges and their representation.
* Profile information::    Representation of frequencies and probabilities.
* Maintaining the CFG::    Keeping the control flow graph and up to date.
* Liveness information::   Using and maintaining liveness information.
@end menu


@node Basic Blocks
@section Basic Blocks

@cindex basic block
@findex basic_block
A basic block is a straight-line sequence of code with only one entry
point and only one exit.  In GCC, basic blocks are represented using
the @code{basic_block} data type.

@findex ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR
Special basic blocks represent possible entry and exit points of a
function.  These blocks are called @code{ENTRY_BLOCK_PTR} and
@code{EXIT_BLOCK_PTR}.  These blocks do not contain any code.

@findex BASIC_BLOCK
The @code{BASIC_BLOCK} array contains all basic blocks in an
unspecified order.  Each @code{basic_block} structure has a field
that holds a unique integer identifier @code{index} that is the
index of the block in the @code{BASIC_BLOCK} array.
The total number of basic blocks in the function is
@code{n_basic_blocks}.  Both the basic block indices and
the total number of basic blocks may vary during the compilation
process, as passes reorder, create, duplicate, and destroy basic
blocks.  The index for any block should never be greater than
@code{last_basic_block}.  The indices 0 and 1 are special codes
reserved for @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}, the
indices of @code{ENTRY_BLOCK_PTR} and @code{EXIT_BLOCK_PTR}.

@findex next_bb, prev_bb, FOR_EACH_BB, FOR_ALL_BB
Two pointer members of the @code{basic_block} structure are the
pointers @code{next_bb} and @code{prev_bb}.  These are used to keep
doubly linked chain of basic blocks in the same order as the
underlying instruction stream.  The chain of basic blocks is updated
transparently by the provided API for manipulating the CFG@.  The macro
@code{FOR_EACH_BB} can be used to visit all the basic blocks in
lexicographical order, except @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}.
The macro @code{FOR_ALL_BB} also visits all basic blocks in
lexicographical order, including @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}.

@findex post_order_compute, inverted_post_order_compute, walk_dominator_tree
The functions @code{post_order_compute} and @code{inverted_post_order_compute}
can be used to compute topological orders of the CFG.  The orders are
stored as vectors of basic block indices.  The @code{BASIC_BLOCK} array
can be used to iterate each basic block by index.
Dominator traversals are also possible using
@code{walk_dominator_tree}.  Given two basic blocks A and B, block A
dominates block B if A is @emph{always} executed before B@.

Each @code{basic_block} also contains pointers to the first
instruction (the @dfn{head}) and the last instruction (the @dfn{tail})
or @dfn{end} of the instruction stream contained in a basic block.  In
fact, since the @code{basic_block} data type is used to represent
blocks in both major intermediate representations of GCC (@code{GIMPLE}
and RTL), there are pointers to the head and end of a basic block for
both representations, stored in intermediate representation specific
data in the @code{il} field of @code{struct basic_block_def}.

@findex CODE_LABEL
@findex NOTE_INSN_BASIC_BLOCK
For RTL, these pointers are @code{BB_HEAD} and @code{BB_END}.

@cindex insn notes, notes
@findex NOTE_INSN_BASIC_BLOCK
In the RTL representation of a function, the instruction stream
contains not only the ``real'' instructions, but also @dfn{notes}
or @dfn{insn notes} (to distinguish them from @dfn{reg notes}).
Any function that moves or duplicates the basic blocks needs
to take care of updating of these notes.  Many of these notes expect
that the instruction stream consists of linear regions, so updating
can sometimes be tedious.  All types of insn notes are defined
in @file{insn-notes.def}.

In the RTL function representation, the instructions contained in a
basic block always follow a @code{NOTE_INSN_BASIC_BLOCK}, but zero
or more @code{CODE_LABEL} nodes can precede the block note.
A basic block ends with a control flow instruction or with the last
instruction before the next @code{CODE_LABEL} or
@code{NOTE_INSN_BASIC_BLOCK}.
By definition, a @code{CODE_LABEL} cannot appear in the middle of
the instruction stream of a basic block.

@findex can_fallthru
@cindex table jump
In addition to notes, the jump table vectors are also represented as
``pseudo-instructions'' inside the insn stream.  These vectors never
appear in the basic block and should always be placed just after the
table jump instructions referencing them.  After removing the
table-jump it is often difficult to eliminate the code computing the
address and referencing the vector, so cleaning up these vectors is
postponed until after liveness analysis.   Thus the jump table vectors
may appear in the insn stream unreferenced and without any purpose.
Before any edge is made @dfn{fall-thru}, the existence of such
construct in the way needs to be checked by calling
@code{can_fallthru} function.

@cindex GIMPLE statement iterators
For the @code{GIMPLE} representation, the PHI nodes and statements
contained in a basic block are in a @code{gimple_seq} pointed to by
the basic block intermediate language specific pointers.
Abstract containers and iterators are used to access the PHI nodes
and statements in a basic blocks.  These iterators are called
@dfn{GIMPLE statement iterators} (GSIs).  Grep for @code{^gsi}
in the various @file{gimple-*} and @file{tree-*} files.
There is a @code{gimple_stmt_iterator} type for iterating over
all kinds of statement, and a @code{gphi_iterator} subclass for
iterating over PHI nodes.
The following snippet will pretty-print all PHI nodes the statements
of the current function in the GIMPLE representation.

@smallexample
basic_block bb;

FOR_EACH_BB (bb)
  @{
   gphi_iterator pi;
   gimple_stmt_iterator si;

   for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
     @{
       gphi *phi = pi.phi ();
       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
     @}
   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
     @{
       gimple stmt = gsi_stmt (si);
       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
     @}
  @}
@end smallexample


@node Edges
@section Edges

@cindex edge in the flow graph
@findex edge
Edges represent possible control flow transfers from the end of some
basic block A to the head of another basic block B@.  We say that A is
a predecessor of B, and B is a successor of A@.  Edges are represented
in GCC with the @code{edge} data type.  Each @code{edge} acts as a
link between two basic blocks: The @code{src} member of an edge
points to the predecessor basic block of the @code{dest} basic block.
The members @code{preds} and @code{succs} of the @code{basic_block} data
type point to type-safe vectors of edges to the predecessors and
successors of the block.

@cindex edge iterators
When walking the edges in an edge vector, @dfn{edge iterators} should
be used.  Edge iterators are constructed using the
@code{edge_iterator} data structure and several methods are available
to operate on them:

@ftable @code
@item ei_start
This function initializes an @code{edge_iterator} that points to the
first edge in a vector of edges.

@item ei_last
This function initializes an @code{edge_iterator} that points to the
last edge in a vector of edges.

@item ei_end_p
This predicate is @code{true} if an @code{edge_iterator} represents
the last edge in an edge vector.

@item ei_one_before_end_p
This predicate is @code{true} if an @code{edge_iterator} represents
the second last edge in an edge vector.

@item ei_next
This function takes a pointer to an @code{edge_iterator} and makes it
point to the next edge in the sequence.

@item ei_prev
This function takes a pointer to an @code{edge_iterator} and makes it
point to the previous edge in the sequence.

@item ei_edge
This function returns the @code{edge} currently pointed to by an
@code{edge_iterator}.

@item ei_safe_safe
This function returns the @code{edge} currently pointed to by an
@code{edge_iterator}, but returns @code{NULL} if the iterator is
pointing at the end of the sequence.  This function has been provided
for existing code makes the assumption that a @code{NULL} edge
indicates the end of the sequence.

@end ftable

The convenience macro @code{FOR_EACH_EDGE} can be used to visit all of
the edges in a sequence of predecessor or successor edges.  It must
not be used when an element might be removed during the traversal,
otherwise elements will be missed.  Here is an example of how to use
the macro:

@smallexample
edge e;
edge_iterator ei;

FOR_EACH_EDGE (e, ei, bb->succs)
  @{
     if (e->flags & EDGE_FALLTHRU)
       break;
  @}
@end smallexample

@findex fall-thru
There are various reasons why control flow may transfer from one block
to another.  One possibility is that some instruction, for example a
@code{CODE_LABEL}, in a linearized instruction stream just always
starts a new basic block.  In this case a @dfn{fall-thru} edge links
the basic block to the first following basic block.  But there are
several other reasons why edges may be created.  The @code{flags}
field of the @code{edge} data type is used to store information
about the type of edge we are dealing with.  Each edge is of one of
the following types:

@table @emph
@item jump
No type flags are set for edges corresponding to jump instructions.
These edges are used for unconditional or conditional jumps and in
RTL also for table jumps.  They are the easiest to manipulate as they
may be freely redirected when the flow graph is not in SSA form.

@item fall-thru
@findex EDGE_FALLTHRU, force_nonfallthru
Fall-thru edges are present in case where the basic block may continue
execution to the following one without branching.  These edges have
the @code{EDGE_FALLTHRU} flag set.  Unlike other types of edges, these
edges must come into the basic block immediately following in the
instruction stream.  The function @code{force_nonfallthru} is
available to insert an unconditional jump in the case that redirection
is needed.  Note that this may require creation of a new basic block.

@item exception handling
@cindex exception handling
@findex EDGE_ABNORMAL, EDGE_EH
Exception handling edges represent possible control transfers from a
trapping instruction to an exception handler.  The definition of
``trapping'' varies.  In C++, only function calls can throw, but for
Ada exceptions like division by zero or segmentation fault are
defined and thus each instruction possibly throwing this kind of
exception needs to be handled as control flow instruction.  Exception
edges have the @code{EDGE_ABNORMAL} and @code{EDGE_EH} flags set.

@findex purge_dead_edges
When updating the instruction stream it is easy to change possibly
trapping instruction to non-trapping, by simply removing the exception
edge.  The opposite conversion is difficult, but should not happen
anyway.  The edges can be eliminated via @code{purge_dead_edges} call.

@findex REG_EH_REGION, EDGE_ABNORMAL_CALL
In the RTL representation, the destination of an exception edge is
specified by @code{REG_EH_REGION} note attached to the insn.
In case of a trapping call the @code{EDGE_ABNORMAL_CALL} flag is set
too.  In the @code{GIMPLE} representation, this extra flag is not set.

@findex may_trap_p, tree_could_trap_p
In the RTL representation, the predicate @code{may_trap_p} may be used
to check whether instruction still may trap or not.  For the tree
representation, the @code{tree_could_trap_p} predicate is available,
but this predicate only checks for possible memory traps, as in
dereferencing an invalid pointer location.


@item sibling calls
@cindex sibling call
@findex EDGE_ABNORMAL, EDGE_SIBCALL
Sibling calls or tail calls terminate the function in a non-standard
way and thus an edge to the exit must be present.
@code{EDGE_SIBCALL} and @code{EDGE_ABNORMAL} are set in such case.
These edges only exist in the RTL representation.

@item computed jumps
@cindex computed jump
@findex EDGE_ABNORMAL
Computed jumps contain edges to all labels in the function referenced
from the code.  All those edges have @code{EDGE_ABNORMAL} flag set.
The edges used to represent computed jumps often cause compile time
performance problems, since functions consisting of many taken labels
and many computed jumps may have @emph{very} dense flow graphs, so
these edges need to be handled with special care.  During the earlier
stages of the compilation process, GCC tries to avoid such dense flow
graphs by factoring computed jumps.  For example, given the following
series of jumps,

@smallexample
  goto *x;
  [ @dots{} ]

  goto *x;
  [ @dots{} ]

  goto *x;
  [ @dots{} ]
@end smallexample

@noindent
factoring the computed jumps results in the following code sequence
which has a much simpler flow graph:

@smallexample
  goto y;
  [ @dots{} ]

  goto y;
  [ @dots{} ]

  goto y;
  [ @dots{} ]

y:
  goto *x;
@end smallexample

@findex pass_duplicate_computed_gotos
However, the classic problem with this transformation is that it has a
runtime cost in there resulting code: An extra jump.  Therefore, the
computed jumps are un-factored in the later passes of the compiler
(in the pass called @code{pass_duplicate_computed_gotos}).
Be aware of that when you work on passes in that area.  There have
been numerous examples already where the compile time for code with
unfactored computed jumps caused some serious headaches.

@item nonlocal goto handlers
@cindex nonlocal goto handler
@findex EDGE_ABNORMAL, EDGE_ABNORMAL_CALL
GCC allows nested functions to return into caller using a @code{goto}
to a label passed to as an argument to the callee.  The labels passed
to nested functions contain special code to cleanup after function
call.  Such sections of code are referred to as ``nonlocal goto
receivers''.  If a function contains such nonlocal goto receivers, an
edge from the call to the label is created with the
@code{EDGE_ABNORMAL} and @code{EDGE_ABNORMAL_CALL} flags set.

@item function entry points
@cindex function entry point, alternate function entry point
@findex LABEL_ALTERNATE_NAME
By definition, execution of function starts at basic block 0, so there
is always an edge from the @code{ENTRY_BLOCK_PTR} to basic block 0.
There is no @code{GIMPLE} representation for alternate entry points at
this moment.  In RTL, alternate entry points are specified by
@code{CODE_LABEL} with @code{LABEL_ALTERNATE_NAME} defined.  This
feature is currently used for multiple entry point prologues and is
limited to post-reload passes only.  This can be used by back-ends to
emit alternate prologues for functions called from different contexts.
In future full support for multiple entry functions defined by Fortran
90 needs to be implemented.

@item function exits
In the pre-reload representation a function terminates after the last
instruction in the insn chain and no explicit return instructions are
used.  This corresponds to the fall-thru edge into exit block.  After
reload, optimal RTL epilogues are used that use explicit (conditional)
return instructions that are represented by edges with no flags set.

@end table


@node Profile information
@section Profile information

@cindex profile representation
In many cases a compiler must make a choice whether to trade speed in
one part of code for speed in another, or to trade code size for code
speed.  In such cases it is useful to know information about how often
some given block will be executed.  That is the purpose for
maintaining profile within the flow graph.
GCC can handle profile information obtained through @dfn{profile
feedback}, but it can also estimate branch probabilities based on
statics and heuristics.

@cindex profile feedback
The feedback based profile is produced by compiling the program with
instrumentation, executing it on a train run and reading the numbers
of executions of basic blocks and edges back to the compiler while
re-compiling the program to produce the final executable.  This method
provides very accurate information about where a program spends most
of its time on the train run.  Whether it matches the average run of
course depends on the choice of train data set, but several studies
have shown that the behavior of a program usually changes just
marginally over different data sets.

@cindex Static profile estimation
@cindex branch prediction
@findex predict.def
When profile feedback is not available, the compiler may be asked to
attempt to predict the behavior of each branch in the program using a
set of heuristics (see @file{predict.def} for details) and compute
estimated frequencies of each basic block by propagating the
probabilities over the graph.

@findex frequency, count, BB_FREQ_BASE
Each @code{basic_block} contains two integer fields to represent
profile information: @code{frequency} and @code{count}.  The
@code{frequency} is an estimation how often is basic block executed
within a function.  It is represented as an integer scaled in the
range from 0 to @code{BB_FREQ_BASE}.  The most frequently executed
basic block in function is initially set to @code{BB_FREQ_BASE} and
the rest of frequencies are scaled accordingly.  During optimization,
the frequency of the most frequent basic block can both decrease (for
instance by loop unrolling) or grow (for instance by cross-jumping
optimization), so scaling sometimes has to be performed multiple
times.

@findex gcov_type
The @code{count} contains hard-counted numbers of execution measured
during training runs and is nonzero only when profile feedback is
available.  This value is represented as the host's widest integer
(typically a 64 bit integer) of the special type @code{gcov_type}.

Most optimization passes can use only the frequency information of a
basic block, but a few passes may want to know hard execution counts.
The frequencies should always match the counts after scaling, however
during updating of the profile information numerical error may
accumulate into quite large errors.

@findex REG_BR_PROB_BASE, EDGE_FREQUENCY
Each edge also contains a branch probability field: an integer in the
range from 0 to @code{REG_BR_PROB_BASE}.  It represents probability of
passing control from the end of the @code{src} basic block to the
@code{dest} basic block, i.e.@: the probability that control will flow
along this edge.  The @code{EDGE_FREQUENCY} macro is available to
compute how frequently a given edge is taken.  There is a @code{count}
field for each edge as well, representing same information as for a
basic block.

The basic block frequencies are not represented in the instruction
stream, but in the RTL representation the edge frequencies are
represented for conditional jumps (via the @code{REG_BR_PROB}
macro) since they are used when instructions are output to the
assembly file and the flow graph is no longer maintained.

@cindex reverse probability
The probability that control flow arrives via a given edge to its
destination basic block is called @dfn{reverse probability} and is not
directly represented, but it may be easily computed from frequencies
of basic blocks.

@findex redirect_edge_and_branch
Updating profile information is a delicate task that can unfortunately
not be easily integrated with the CFG manipulation API@.  Many of the
functions and hooks to modify the CFG, such as
@code{redirect_edge_and_branch}, do not have enough information to
easily update the profile, so updating it is in the majority of cases
left up to the caller.  It is difficult to uncover bugs in the profile
updating code, because they manifest themselves only by producing
worse code, and checking profile consistency is not possible because
of numeric error accumulation.  Hence special attention needs to be
given to this issue in each pass that modifies the CFG@.

@findex REG_BR_PROB_BASE, BB_FREQ_BASE, count
It is important to point out that @code{REG_BR_PROB_BASE} and
@code{BB_FREQ_BASE} are both set low enough to be possible to compute
second power of any frequency or probability in the flow graph, it is
not possible to even square the @code{count} field, as modern CPUs are
fast enough to execute $2^32$ operations quickly.


@node Maintaining the CFG
@section Maintaining the CFG
@findex cfghooks.h

An important task of each compiler pass is to keep both the control
flow graph and all profile information up-to-date.  Reconstruction of
the control flow graph after each pass is not an option, since it may be
very expensive and lost profile information cannot be reconstructed at
all.

GCC has two major intermediate representations, and both use the
@code{basic_block} and @code{edge} data types to represent control
flow.  Both representations share as much of the CFG maintenance code
as possible.  For each representation, a set of @dfn{hooks} is defined
so that each representation can provide its own implementation of CFG
manipulation routines when necessary.  These hooks are defined in
@file{cfghooks.h}.  There are hooks for almost all common CFG
manipulations, including block splitting and merging, edge redirection
and creating and deleting basic blocks.  These hooks should provide
everything you need to maintain and manipulate the CFG in both the RTL
and @code{GIMPLE} representation.

At the moment, the basic block boundaries are maintained transparently
when modifying instructions, so there rarely is a need to move them
manually (such as in case someone wants to output instruction outside
basic block explicitly).

@findex BLOCK_FOR_INSN, gimple_bb
In the RTL representation, each instruction has a
@code{BLOCK_FOR_INSN} value that represents pointer to the basic block
that contains the instruction.  In the @code{GIMPLE} representation, the
function @code{gimple_bb} returns a pointer to the basic block
containing the queried statement.

@cindex GIMPLE statement iterators
When changes need to be applied to a function in its @code{GIMPLE}
representation, @dfn{GIMPLE statement iterators} should be used.  These
iterators provide an integrated abstraction of the flow graph and the
instruction stream.  Block statement iterators are constructed using
the @code{gimple_stmt_iterator} data structure and several modifiers are
available, including the following:

@ftable @code
@item gsi_start
This function initializes a @code{gimple_stmt_iterator} that points to
the first non-empty statement in a basic block.

@item gsi_last
This function initializes a @code{gimple_stmt_iterator} that points to
the last statement in a basic block.

@item gsi_end_p
This predicate is @code{true} if a @code{gimple_stmt_iterator}
represents the end of a basic block.

@item gsi_next
This function takes a @code{gimple_stmt_iterator} and makes it point to
its successor.

@item gsi_prev
This function takes a @code{gimple_stmt_iterator} and makes it point to
its predecessor.

@item gsi_insert_after
This function inserts a statement after the @code{gimple_stmt_iterator}
passed in.  The final parameter determines whether the statement
iterator is updated to point to the newly inserted statement, or left
pointing to the original statement.

@item gsi_insert_before
This function inserts a statement before the @code{gimple_stmt_iterator}
passed in.  The final parameter determines whether the statement
iterator is updated to point to the newly inserted statement, or left
pointing to the original  statement.

@item gsi_remove
This function removes the @code{gimple_stmt_iterator} passed in and
rechains the remaining statements in a basic block, if any.
@end ftable

@findex BB_HEAD, BB_END
In the RTL representation, the macros @code{BB_HEAD} and @code{BB_END}
may be used to get the head and end @code{rtx} of a basic block.  No
abstract iterators are defined for traversing the insn chain, but you
can just use @code{NEXT_INSN} and @code{PREV_INSN} instead.  @xref{Insns}.

@findex purge_dead_edges
Usually a code manipulating pass simplifies the instruction stream and
the flow of control, possibly eliminating some edges.  This may for
example happen when a conditional jump is replaced with an
unconditional jump.  Updating of edges
is not transparent and each optimization pass is required to do so
manually.  However only few cases occur in practice.  The pass may
call @code{purge_dead_edges} on a given basic block to remove
superfluous edges, if any.

@findex redirect_edge_and_branch, redirect_jump
Another common scenario is redirection of branch instructions, but
this is best modeled as redirection of edges in the control flow graph
and thus use of @code{redirect_edge_and_branch} is preferred over more
low level functions, such as @code{redirect_jump} that operate on RTL
chain only.  The CFG hooks defined in @file{cfghooks.h} should provide
the complete API required for manipulating and maintaining the CFG@.

@findex split_block
It is also possible that a pass has to insert control flow instruction
into the middle of a basic block, thus creating an entry point in the
middle of the basic block, which is impossible by definition: The
block must be split to make sure it only has one entry point, i.e.@: the
head of the basic block.  The CFG hook @code{split_block} may be used
when an instruction in the middle of a basic block has to become the
target of a jump or branch instruction.

@findex insert_insn_on_edge
@findex commit_edge_insertions
@findex gsi_insert_on_edge
@findex gsi_commit_edge_inserts
@cindex edge splitting
For a global optimizer, a common operation is to split edges in the
flow graph and insert instructions on them.  In the RTL
representation, this can be easily done using the
@code{insert_insn_on_edge} function that emits an instruction
``on the edge'', caching it for a later @code{commit_edge_insertions}
call that will take care of moving the inserted instructions off the
edge into the instruction stream contained in a basic block.  This
includes the creation of new basic blocks where needed.  In the
@code{GIMPLE} representation, the equivalent functions are
@code{gsi_insert_on_edge} which inserts a block statement
iterator on an edge, and @code{gsi_commit_edge_inserts} which flushes
the instruction to actual instruction stream.

@findex verify_flow_info
@cindex CFG verification
While debugging the optimization pass, the @code{verify_flow_info}
function may be useful to find bugs in the control flow graph updating
code.


@node Liveness information
@section Liveness information
@cindex Liveness representation
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.

Liveness information is available in the back end starting with
@code{pass_df_initialize} and ending with @code{pass_df_finish}.  Three
flavors of live analysis are available: With @code{LR}, it is possible
to determine at any point @code{P} in the function if the register may be
used on some path from @code{P} to the end of the function.  With
@code{UR}, it is possible to determine if there is a path from the
beginning of the function to @code{P} that defines the variable.
@code{LIVE} is the intersection of the @code{LR} and @code{UR} and a
variable is live at @code{P} if there is both an assignment that reaches
it from the beginning of the function and a use that can be reached on
some path from @code{P} to the end of the function.

In general @code{LIVE} is the most useful of the three.  The macros
@code{DF_[LR,UR,LIVE]_[IN,OUT]} can be used to access this information.
The macros take a basic block number and return a bitmap that is indexed
by the register number.  This information is only guaranteed to be up to
date after calls are made to @code{df_analyze}.  See the file
@code{df-core.c} for details on using the dataflow.


@findex REG_DEAD, REG_UNUSED
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 @code{REG_DEAD} notes
representing that the value of a given register is no longer needed, or
@code{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.