\section{Class [[Liveness]]}
\label{sec-class-liveness}

As mentioned in Section~\ref{sec-class-bvd} the only elements needed
to build a liveness analyzer on top of class [[Bvd]] are a mechanism for
mapping the ``interesting'' operands of a program to slot numbers, and a
way of enumerating the slots of operands defined and/or used by a
particular instruction.  The map from operands to slots is called an
operand catalog.  It has class [[OpndCatalog]], and it is the
subject of Section~\ref{sec-operand-catalogs}.  The ``def/use'' analyzer
for a single instruction is described later in this section.


\subsection{Class [[Liveness]]}

To perform liveness analysis, you simply construct an instance of class
[[Liveness]], passing a CFG, an operand catalog, and (optionally) a
def/use analyzer as arguments to the constructor.

<<class [[Liveness]]>>=
class Liveness : public Bvd {
  public:
    Liveness(Cfg *graph, OpndCatalog *catalog, DefUseAnalyzer *analyzer)
	: Bvd(graph, backward, any_path)
    {
	_catalog = catalog;

	if (analyzer) {
	    _analyzer_own = NULL; _analyzer = analyzer;
	} else
	    _analyzer_own = _analyzer = new DefUseAnalyzer(catalog);

	solve();
    }

    virtual ~Liveness()			      { delete _analyzer_own; }

    virtual void find_kill_and_gen(Instr *mi)
	{ _analyzer->analyze(mi); }

    virtual const NatSet* kill_set() const    { return _analyzer->defs_set(); }
    virtual const NatSet* gen_set()  const    { return _analyzer->uses_set(); }

    virtual int num_slots() const	      { return _catalog->num_slots(); }

  protected:
    OpndCatalog* catalog()		      { return _catalog; }
    DefUseAnalyzer* analyzer()		      { return _analyzer; }

  private:
    OpndCatalog *_catalog;
    DefUseAnalyzer *_analyzer;
    DefUseAnalyzer *_analyzer_own;	      // default analyzer
};
@

The operand catalog, of type pointer to [[OpndCatalog]], serves two
purposes.  It screens out the uninteresting operands, and it assigns slot
numbers to the interesting one.  You don't need to have enrolled any
operands in the catalog before invoking the [[Liveness]] constructor
(although you are free to do so).  In the course of scanning the CFG,
the solver enrolls interesting operands as needed.  Then, after analysis
is complete, you use the catalog to map operands to slot numbers so that
you can access the data-flow results.

Note that the constructor and destructor and [[num_slots]] are the only
public methods defined by [[Liveness]].  (Recall from
Section~\ref{sec-class-bvd} that [[num_slots]] returns number of slots
in the final catalog after liveness has been computed.)  To get at the
analysis, you use the inherited methods [[in_set]] and [[out_set]].

The protected methods are principally those that any subclass of [[Bvd]]
must supply:

\begin{tabular}{l@{\hspace*{2em}}p{.65\linewidth}}
{\tt find\_kill\_and\_gen($i$)}& Analyzes instruction $i$ prior to use
			      of [[kill_iter]] and [[gen_iter]].  For
			      [[Liveness]], this extracts the slots of
			      operands defined (written) and operands
			      used (read) by $i$. \\
[[kill_iter()]]		    & Produces an iterator over the \Mit{kill}
			      set for the instruction most recently analyzed
			      instruction by [[find_kill_and_gen]].  For
			      [[Liveness]], the \Mit{kill} set holds the
			      slots of operands \emph{defined}. \\
[[gen_iter()]]		    & Produces an iterator over the \Mit{gen}
			      set for the instruction most recently analyzed
			      instruction by [[find_kill_and_gen]].  For
			      [[Liveness]], the \Mit{gen} set holds the
			      slots of operands \emph{used}.
\end{tabular}

Since liveness is a backward data-flow problem, the solver built into
class [[Bvd]] applies [[find_kill_and_gen]] to the instructions in a
basic block by starting at the last one and working backward to the
entry of the block.  It starts with a ``blank'' flow function (one
that would do nothing if applied to a slot set) and accumulates the
block's net effect on liveness (for all slots) as it goes through the
block.  For each instruction, the operands defined are considered first;
their liveness is ``killed'' because just before their
definitions, their old values cannot be useful.  The operands used by
the instruction are considered next; they become live (their liveness is
``generated'') from the point of view of code preceding the current
instruction.  The flow function that results from this one pass over
a node in the CFG captures its effect on liveness.  The solver therefore
has no further need to examine instructions as is solves the liveness
problem for the whole procedure.

The [[catalog]] and [[analyzer]] methods of class [[Liveness]] simply
return pointers to the operand catalog and the instruction def/use analyzer
associated with an instance of the class.

Note that all of the code for [[Liveness]] is given in the above
class declaration.  All that's required to build a [[Bvd]]-based
analyzer is to establish a map from ``interesting data-flow items'' to
bit-vector slots, and to write a \Mit{gen}/\Mit{kill} analyzer for
instructions.


\subsection{Class [[DefUseAnalyzer]]}

The task of identifying the data-flow items defined and used by a
particular instruction is handled by an instance of class
[[DefUseAnalyzer]].  This class handles explicit operands as well as
implicit definitions and uses recorded in [[regs_defd]] and [[regs_uses]]
annotations.  The latter are used, for example, on call and return
instructions for certain architectures to indicate registers used for
argument and result transmission and also registers potentially defined
because they are not protected by a callee-saves convention.

<<class [[DefUseAnalyzer]]>>=
class DefUseAnalyzer {
  public:
    DefUseAnalyzer(OpndCatalog *catalog) : _catalog(catalog) { }
    virtual ~DefUseAnalyzer() { }

    virtual void analyze(Instr *mi);

    NatSetIter defs_iter() const	      { return _defs.iter(); }
    NatSetIter uses_iter() const	      { return _uses.iter(); }

    const NatSet *defs_set() const	      { return &_defs; }
    const NatSet *uses_set() const	      { return &_uses; }

  protected:
    OpndCatalog *catalog()		      { return _catalog; }
    NatSet *defs()			      { return &_defs; }
    NatSet *uses()			      { return &_uses; }

  private:
    OpndCatalog *_catalog;
    NatSetSparse _defs;
    NatSetSparse _uses;
};
@

The only input needed to create a [[DefUseAnalyzer]] is the operand
catalog.  When the [[analyze]] method is applied to an instruction, it
attempts to enroll each operand of the instruction in the catalog.  This
has the effects of excluding uninteresting operands, of enrolling
interesting operands in the catalog, and of providing slot numbers that
can be used to make up def/use sets.  The [[analyze]] method builds
these sets for the instruction.  The the other public methods can be
used to access them, either directly as sets (methods [[defs_set]] and
[[uses_set]]) or as iterations (methods [[defs_iter]] and
[[uses_iter]]).



<<liveness.h>>=
/* file "bvd/liveness.h" -- Liveness analyzer */

<<Machine-SUIF copyright>>

#ifndef BVD_LIVENESS_H
#define BVD_LIVENESS_H

#include <machine/copyright.h>

#ifndef SUPPRESS_PRAGMA_INTERFACE
#pragma interface "bvd/liveness.h"
#endif

#include <machine/machine.h>
#include <cfg/cfg.h>

#include <bvd/solve.h>


<<class [[DefUseAnalyzer]]>>

<<class [[Liveness]]>>

#endif /* BVD_LIVENESS_H */
@