\section{Flow functions}
\label{sec-flow-functions}

Muchnick \cite{bibmuchnick} and other authors present the theoretical
basis for data-flow problems in terms of \emph{flow functions} (or
sometimes \emph{transfer functions}).

Here we define the three monotone $\mathit{boolean}\to\mathit{boolean}$
functions, extended pointwise to vectors of booleans, i.e., bit vectors.
As in Section~\ref{sec-class-bvd} we use the slot-set metaphor instead
of talking in terms of bit vectors, and so these flow functions operate
on values of type [[NatSetDense]].  Class [[FlowFun]] has a method
[[apply]] that applies the flow function that it represents to a
[[NatSetDense]] value.  This allows us to encode operations on
[[NatSetDense]]s directly from the theory.

The reason that we get away with using the theory in practice is that
there are only three monotone boolean functions (the identity function,
the function that always returns the constant 
\ifhtml%
\textbf{top} (%
\else%
$\top$ (``top'',
\fi%
\Mit{true}, 1), and the function that always returns the constant
\ifhtml%
\textbf{bottom} (%
\else%
$\bot$ (``bottom'',
\fi%
\Mit{false}, 0).  So we only need two bits to represent a monotone
$\mathit{boolean}\to\mathit{boolean}$ function.  Thus the pointwise
extension of boolean functions to slot sets can be represented in only
twice as much space as the sets that they manipulate.


\subsection{Class [[FlowFun]]}

<<class [[FlowFun]]>>=
class FlowFun {
  public:
    FlowFun(int num_slots_hint = 0);

    FlowFun(const FlowFun&);
    void operator=(const FlowFun&);
    
    void set_to_top();
    void set_to_top(int slot);
    void set_to_bottom();
    void set_to_bottom(int slot);
    void set_to_id();
    void set_to_id(int slot);
    
    void apply(NatSetDense &updated);
    
    void print(int bound, FILE* = stdout);
    
<<[[FlowFun]] details>>
};
@

When you create an instance of [[FlowFun]], it is initialized to the
identity function.  The constructor takes an integer that the
implementation can use as an estimate of slot-set sizes.

\begin{tabular}{l@{\hspace*{2em}}p{.7\linewidth}}
[[set_to_top(n)]]   & Makes [[this]] a function that
		      sets bit [[n]] to 1 ($\top$). \\
[[set_to_top()]]    & Makes [[this]] a function that
		      sets all bits to 1 ($\top$). \\
[[set_to_bottom(n)]]& Makes [[this]] a function that
		      sets bit [[n]] to 0 ($\bot$). \\
[[set_to_bottom()]] & Makes [[this]] a function that
		      sets all bits to 0 ($\bot$). \\
[[set_to_id(n)]]    & Makes [[this]] a function that
		      passes the value of bit [[n]] unchanged. \\
[[set_to_id()]]	    & Makes [[this]] a function that
		      passes the values of all bits unchanged. \\
[[apply(b)]]	    & Applies [[this]] to set [[b]],
		      overwriting [[b]] with the result. \\
\end{tabular}


\subsection{Implementation}

As hinted earlier, we use two slot sets to represent a flow function.

<<[[FlowFun]] details>>=
  private:
    NatSetDense _id;
    NatSetDense _cs;
@

Roughly speaking, the presence or absence of $s$ in set [[_id]]
determines whether the flow function is the identity at slot $s$ or
always produces a constant ($\top$ or $\bot$) at that slot.  In the
latter case, the particular constant is determined by whether or not
[[_cs]] contains $s$.  Here are the precise rules:

\begin{center}
\begin{tabular}{l|cc}
			& $s\ \not\in\ [[_cs]]$	& $s\ \in\ [[_cs]]$	\\
\hline
$s\ \not\in\ [[_id]]$	& $\bot$ at $s$		& $\top$ at $s$		\\
$s\	\in\ [[_id]]$	& \Mit{identity} at $s$	& {\it (disallowed)}
\end{tabular}
\end{center}


\paragraph{Inlined methods.}

For efficiency, we define the methods that compute and apply flow
functions as [[inline]] members.

<<[[FlowFun]] inlines>>=
inline void
FlowFun::set_to_top()
{
    // set function to "constant 1" on all bits
    _id.remove_all();
    _cs.insert_all();
}
@

<<[[FlowFun]] inlines>>=

inline void
FlowFun::set_to_top(int slot)
{
    claim(slot >= 0, "FlowFun::set_to_top - negative slot %d", slot);
    _id.remove(slot);
    _cs.insert(slot);
}
@

<<[[FlowFun]] inlines>>=

inline void
FlowFun::set_to_bottom()
{
    // set function to "constant 0" on all bits
    _id.remove_all();
    _cs.remove_all();
}
@

<<[[FlowFun]] inlines>>=

inline void
FlowFun::set_to_bottom(int slot)
{
    claim(slot >= 0, "FlowFun::set_to_bottom - negative slot %d", slot);
    _id.remove(slot);
    _cs.remove(slot);
}
@

<<[[FlowFun]] inlines>>=

inline void
FlowFun::set_to_id()
{
    // set function to "identity" on all bits
    _id.insert_all();
    _cs.remove_all();
}
@

<<[[FlowFun]] inlines>>=

inline void
FlowFun::set_to_id(int slot)
{
    _id.insert(slot);
    _cs.remove(slot);
}
@

To apply a flow function to a slot set, we subtract away any slots at
which the function is constant and then union in the new constant slots.
We rely on the representation invariant that $[[_cs]] \cap [[_id]] =
\emptyset$.

<<[[FlowFun]] inlines>>=

inline void
FlowFun::apply(NatSetDense &updated)
{
    updated *= _id;
    updated += _cs;
}
@


\subsection{Header file [[flow_fun.h]]}

Class [[FlowFun]] is defined in the following header file.

<<flow\_fun.h>>=
/* file "bvd/flow_fun.h" -- Flow functions */

<<Machine-SUIF copyright>>

#ifndef BVD_FLOW_FUN_H
#define BVD_FLOW_FUN_H

#include <machine/copyright.h>

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

#include <machine/machine.h>

<<class [[FlowFun]]>>

<<[[FlowFun]] inlines>>

#endif /* BVD_FLOW_FUN_H */
@