\section{Mapping operands to bit-vector slots}
\label{sec-operand-catalogs}

Solvers of bit-vector data-flow problems need to associate an integer
identifier with each item in the universe whose data flow they
calculate.  As mentioned earlier, we call these unique integers
\emph{slots} because that is the term sometimes used for bit-vector
positions.  In the liveness problem, the items of interest are operands,
so the liveness solver needs a map from operands to slots.  The
purpose of an \emph{operand catalog} is to provide this map.

As the program is scanned during analysis, the catalog is used to assign
slots to operands.  Later, as operands are revisited, the catalog provides
efficient lookup of their slot numbers so that data-flow information can be
read out of the slot sets produced by analysis.


\subsection{Class [[RegSymCatalog]]}

The [[machine]] library (see \emph{The SUIF Machine Library} document)
defines class [[OpndCatalog]] which provides a common abstract interface
for operand catalogs.  One very useful concrete subclass of [[OpndCatalog]]
implements a catalog for register and variable-symbol operands.  This
class, called [[RegSymCatalog]] is heavily used in register allocation,
scalar optimization, and instruction scheduling.

<<class [[RegSymCatalog]]>>=

class RegSymCatalog : public OpndCatalog {
  public:
    typedef bool (*filter_f)(Opnd);

    RegSymCatalog(bool record = false, filter_f = NULL,
		  int hash_table_size = 1024);

    virtual int size() const { return _next_slot; }

    virtual bool enroll(Opnd, int *slot = NULL);
    virtual bool lookup(Opnd, int *slot = NULL) const;

<<[[RegSymCatalog]] details>>
};
@

\paragraph{Constructing a [[RegSymCatalog]].}

The constructor for class [[RegSymCatalog]] declared above
takes the following arguments:

\begin{itemize}
\item An optional flag indicating whether operands enrolled should be
      remembered so that the catalog can be printed.
\item An optional filter, a Boolean function taking an operand
      as argument.  If the filter is provided, the catalog ignores any
      operand for which the filter returns [[false]].
\item An optional bucket count for the catalog's hash table.  This must
      be a power of two.  Overriding the default value may affect
      performance, but not the table's capacity.
\end{itemize}



\subsection{Implementation details}

\subsubsection{Class [[RegSymCatalog]]}

The private part of [[RegSymCatalog]] declares the user-provided
operand filter and the running slot count.

<<[[RegSymCatalog]] details>>=
    filter_f _filter;
    int _next_slot;
@

It also records the hash map taking operands to slots:

<<[[RegSymCatalog]] details>>=

    HashMap<unsigned long, int> _hash_map;
@

The function member is simply a subroutine of the public methods.

<<[[RegSymCatalog]] details>>=

    bool get_slot(Opnd, int*, bool);
@


\subsection{Header file for module [[catalog]]}

Classes [[OpndCatalog]] and [[RegSymCatalog]] are defined in module
[[catalog]], which has the following header file:

<<catalog.h>>=
/* file "bvd/catalog.h" -- Maps from operands to slot sets */

<<Machine-SUIF copyright>>

#ifndef BVD_OPND_CATALOG_H
#define BVD_OPND_CATALOG_H

#include <machine/copyright.h>
   
#ifndef SUPPRESS_PRAGMA_INTERFACE
#pragma interface "bvd/catalog.h"
#endif

#include <machine/machine.h>

<<class [[RegSymCatalog]]>>

#endif /* BVD_OPND_CATALOG_H */
@