\section{Global Partitioning}
\label{section:global}
In the previous section, we have seen how to partition basic blocks.
Now, we address the problem of partitioning blocks that contain
conditional expressions and calls to other user defined functions.
We use the term {\em general} blocks to refer to such blocks and
{\em global partitioning} to refer to partitioning such 
blocks. Although our discussion in this section is focussed primarily on 
dealing with calls to user defined functions, the same techniques
can be used to handle conditionals by abstracting them into 
a separate function.


\subsection{Converting General to Basic Blocks}
\label{section:convert-general}
\begin{myfig*}{figure:global}{Figure (a) shows a simple block that calls a function {\tt f}.
Figure (b) shows the basic block obtained by disconnecting the call
to {\tt f}. Figure (c) corresponds to the path $[u,v]$ of {\tt f}.
Figure (d) corresponds to the path $[u]$ and figure (e) corresponds
to the path $\bot_p$.}
\illustration{fig1}[\hsize]
\vspace{-4ex}
\end{myfig*}

Our strategy
in performing global partitioning is to reduce a general block
to a set of basic blocks by using dependence information of
functions called in the general block. In this section, we present our approach using an
example. We formalize these techniques in sections~\ref{section:path}
and ~\ref{section:global-path}.

Consider the simple block shown in figure~\ref{figure:global}(a). The
block has two inputs, two outputs and calls a function
{\tt f}. Suppose the function {\tt f} is not known, but we would
like to partition the block anyway. We can convert the block into
a basic block by assuming ``worst case'' or ``unknown'' behavior
of the function {\tt f}. As shown in figure~\ref{figure:global}(b),
we {\em disconnect} the node calling {\tt f}. Then, we create
new outputs ($z, w$) and a new input ($c$) and use these nodes 
instead of a call to the function $f$. Partitioning this basic block
merges nodes \{3,4\} into a single partition.

Why does this process yield correct partitions? Note
that our basic block algorithm is correct, that is, the 
behavior of the partitioned
block is identical to the behavior of the original block under
any context, regardless of the dependencies between the
inputs and outputs of the block. In particular, the algorithm will generate
safe partitions even when the dependencies between outputs $z,w$ and 
input $c$ 
correspond to the actual dependencies of function {\tt f}. 

Now, suppose that the function {\tt f} being called in figure~\ref{figure:global} is the one given below:
\begin{verbatim}
def f u v = u + v;
\end{verbatim}
It is obvious that {\tt f} acts exactly like the primitive
operator $+$, so the block can be converted to the basic block
in figure~\ref{figure:global}(c) (node 5 is shown shaded as it is
not an actual primitive operator but a ``dummy'' one). We can then
partition the basic block yielding the partitions \{1,2\} and 
\{3,4\}\footnote{In an ordinary basic block, all five nodes would
be in a single partition. As node 5 is a dummy node, we cannot
include it in any partition.}. Thus, we have been able to generate
better partitions than that was possible by disconnecting the call to 
{\tt f}. It is also easy to observe that the same basic block is
also sufficient to model the following function:
\begin{verbatim}
def f u v = 
 {t1 = u * 2;
  t2 = v + 3;
  t3 = t1 - t2
 in 
  t3};
\end{verbatim}
In this case too, {\tt f} acts like a primitive operator on its
two arguments -- the result depends on both the arguments, and the
result is {\em always} available if both the arguments are supplied.
We say that {\tt f} has the {\em path} $[u,v]$ to denote this property.

It may not be possible to specify a single path for every
function. A simple example of such a function is given below:
\begin{verbatim}
def f u v = if u then v else 3;
\end{verbatim}
Here, we do not know (at compile-time) whether {\tt f} depends
on its second argument -- that depends on the value of {\tt u}. We
do know that it can only be one of two possibilities: the
result depends on both the arguments if the {\em then} branch
is selected or just the first argument if the {\em else} branch
is selected. We allow both these possibilities to be represented:
{\tt f} is assigned a {\em set} of paths $\{[u,v], [u]\}$. In this
case, we generate two basic blocks from the block calling {\tt f}:
one for each path of {\tt f}. For our
example, in addition to the basic block in figure~\ref{figure:global}(c),
we generate another basic block; the one shown in figure~\ref{figure:global}(d).

Consider the following recursive function defined below. What are
the paths for this function?
\begin{verbatim}
def f u v =  if (u == 0) then v else f (u-1) v;
\end{verbatim}
If this function terminates, we can argue that the result
depends on both {\tt u} and {\tt v} -- thus the function has the path
$[u,v]$. There is also the possibility that the function
does not terminate. We use the path $\bot_p$ to denote that possibility.
Thus, the paths for the function {\tt f} are $\{[u,v], \bot_p\}$. Using
this definition of $f$ in the example, we generate the graph 
in figure~\ref{figure:global}(e) instead of figure~\ref{figure:global}(d).
The {\em bot} node in the graph denotes that the node is undefined.

To summarize, in this section we have seen how one can disconnect
function-calls or use the paths of the function being called to 
generate basic blocks. In the next two sections, we formalize these
ideas and design a global partitioning algorithm using them. 

\subsection{Path Semantics}
\begin{myfig}{figure:path}{Path Semantics of SP-TAC}
\centering
$\begin{array}{lcl}
{\cal A}_k\ld +\rd  & = & \lambda s.\{x \cup y | (x,y) \in s\}\\
\\
{\cal A}_s\ld c\rd \:  abve & = & \{[]\}\\
{\cal A}_s\ld x\rd \:  abve & = & abve\ld x\rd\\
\\
{\cal A} \ld se\rd \:  \: abve \: aenv  & = & {\cal A}_s\ld se\rd  \: abve\\
{\cal A}\ld b\rd  \: abve \: aenv  & = & {\cal A}_b\ld b\rd  \: abve \:aenv\\
\multicolumn{3}{l}{{\cal A}\ld p(se_1,se_2,\ldots,se_n)\rd  \: abve \: aenv  = }\\
\multicolumn{3}{l}{\hspace{0.25in}{\cal A}_k\ld p\rd  \: ({\cal A}_s\ld se_1\rd  \: abve \times \cdots \times {\cal A}_s\ld se_n\rd  \: abve )}\\
\multicolumn{3}{l}{{\cal A}\ld f(se_1,se_2,\ldots,se_n)\rd  \: abve \: aenv  = }\\
\multicolumn{3}{l}{\hspace{0.25in}aenv\ld f\rd  \: ({\cal A}_s\ld se_1\rd  \: abve \times \cdots \times {\cal A}_s\ld se_n\rd  \: abve )}\\
\multicolumn{3}{l}{{\cal A}\ld {\bf if} \: se \: {\bf then} \:  b_1 \: {\bf else} \: b_2\rd  \: abve \: aenv  =}\\
\multicolumn{3}{l}{\hspace{0.25in} \{(x \cup y_1,\ldots,x \cup y_n), (x \cup z_1,\ldots,x \cup z_n)\}, \mbox{\bf where}}\\
\multicolumn{3}{l}{\hspace{0.25in} x \in {\cal A}_s\ld se\rd \: abve \: \mbox{\bf and}}\\
\multicolumn{3}{l}{\hspace{0.25in}(y_1,\ldots,y_n) \in {\cal A}_b\ld b_1\rd \: abve \: aenv \: \mbox{\bf and}} \\
\multicolumn{3}{l}{\hspace{0.25in}(z_1,\ldots,z_n) \in {\cal A}_b\ld b_2\rd  \: abve \: aenv}\\
\\
\multicolumn{3}{l}{{\cal A}_b\ld \{\{(y_{i1},\ldots,y_{im})=e_i\}^*\: {\bf in}\: (se_1,\ldots,se_n) \}\rd  \: abve \: aenv = }\\
\multicolumn{3}{l}{\hspace{0.25in} \mbox{\bf letrec}}\\
\multicolumn{3}{l}{\hspace{0.25in} newabve=[y_{ij} \mapsto ({\cal A}\ld e_i \rd \: (newabve.abve) \: aenv)\downarrow j]}\\
\multicolumn{3}{l}{\hspace{0.25in} \mbox{\bf in} \: ({\cal A}_s\ld se_1\rd  \: newbve,\ldots,{\cal A}_s\ld se_n\rd  \: newbve)}\\
\\
\multicolumn{3}{l}{{\cal A}_p\ld \{f_i(x_1,x_2,\ldots,x_n)=b_i\}\rd  = aenv,
\mbox{\bf whererec} \: aenv = }\\
\multicolumn{3}{l}{\hspace{0.25in}[f_i \mapsto (\lambda s.\{{\cal A}_b\ld b_i\rd \:  [x_i \mapsto \{y_i\}] aenv | (y_1,\ldots,y_n) \in s\})]}
\end{array}$
\end{myfig}

\label{section:path}
How do we compute paths for every function in an input program? 
We follow the well known technique of abstract
interpretation \cite{Abramsky87} as used by \cite{Bloss88}. Paths
of a function are derived by using a {\em non-standard} semantics
of SP-TAC (as opposed to the {\em standard} semantics presented
in section~\ref{section:syntax}).

\begin{definition} [Paths]
A {\em path} is either a set of variables or $\bot_p$. In the $Path$ 
domain $\bot_p$ is the least element.
The {\em paths} for a function $f$ with $N$ arguments and returning $M$ results
is a set\footnote{Actually, it is an element of the Egli-Milner Powerdomain 
of the Paths domain. Though the powerdomain construction is important
in proving properties of our path semantics, we do not go into the details
here.} of M-tuples of paths. An individual path $[u_1,\ldots,u_k]$ denotes
that if the function $f$ takes that path, the value corresponding to
the path depends on all $u_1,\ldots,u_k$ and is always defined if $u_1,\ldots,u_k$ are defined.
\end{definition}
These are similar to the {\em paths} introduced in \cite{Bloss87}, except
that the paths in \cite{Bloss87} also considered different orderings
of the arguments. That is, the path $[u,v]$ was considered
 different from the path $[v,u]$.

Here are the domains used in our non-standard semantics.
\begin{center}
\begin{tabular}{lr}
$Path$ & Domain of Paths \\
$PS$ & Sets of paths \\
$PTS$ & Sets of path-tuples \\
$Pfun$ & Abstract Functions \\
$Aenv$ & Function environment \\
$Abve$ & Variable Environment
\end{tabular}
\end{center}
The semantic functions are:
\begin{center}
\begin{tabular}{lr}
${\cal A}_s : SE \rightarrow Abve \rightarrow PS$ & Simple Exps\\
${\cal A}_k : Pf \rightarrow Pfun$ & Primitive Operators\\
${\cal A}_b : Bo \rightarrow Abve \rightarrow Aenv \rightarrow PTS$ &
Blocks \\
${\cal A} : Exp \rightarrow Abve \rightarrow Aenv \rightarrow PTS$ &
Expressions \\
${\cal A}_p: Pr \rightarrow Aenv$ & Programs
\end{tabular}
\end{center}
We use $p_1 \cup p_2$ to denote
the ordinary set union operation when both $p_1$ and $p_2$ are sets.
If one of $p_1$ or $p_2$ is $\bot_p$, then $p_1 \cup p_2$ is also $\bot_p$.

Consider the various semantic equations given in figure~\ref{figure:path}.
\begin{enumerate}
\item{The semantic function ${\cal A}_s$ (for constants and variables) is
straightforward. In case of a constant, it returns the 
empty path, reflecting the fact that a constant does not have to depend on
any variable for its value. For variables, it returns the paths
of the variable present in the environment.}
\item{For primitive functions, the paths returned reflect the 
strict behavior of primitive functions. 
For the $+$ operator, a union of the variables
of the first operand and the second operand is returned modeling the fact
that $+$ requires both operands to produce a value.}
\item{The semantic function for {\em if} returns two sets, 
one corresponding to the variables needed when the
{\em then} branch is taken and the other corresponding to when the {\em else}
branch is taken.}
\item{The semantic function ${\cal A}$ for expressions 
is very similar to the standard semantic function ${\cal E}$. It recurses appropriately
when the expression is either a primitive function or a user-defined
function.}
\item{The semantic function for blocks and functions are similar
to their standard semantics counterparts. They use recursion in
the environments to model recursion in the blocks and functions.}
\end{enumerate}

It is possible to consider the semantic equations given above
as an algorithm and compute paths for every function using these
equations. The algorithm uses fix-point iteration to compute paths
of recursive functions. Intuitively, this assumes that the paths
of a function are ${\bot_p}$ to begin with 
and computes the paths of the function using the above equations. This process is repeated with the new paths computed for the function until the paths
of every function remain unchanged. The computation of paths
for the recursive function {\tt fact} is shown below:
\begin{verbatim}
def fact n = 
   if (n == 0) then 1 else n * fact (n - 1);
\end{verbatim}

\begin{center}
\begin{tabular}{|l|l|l|}
\hline
Expression & $Paths_0$ & $Paths_1$ \\ \hline
\tt n == 0  \rm &  $[n]$   & $[n]$ \\
\tt 1 \rm  & $[]$ & $[]$ \\
\tt n - 1 \rm & $[n]$ & $[n]$ \\
\tt (fact (n-1)) \rm & $\bot_p$ & $[n], \bot_p$ \\
\tt (fact n) \rm &  $[n], \bot_p$ & $[n], \bot_p$ \\ \hline
\end{tabular}
\end{center}

There are two issues that need to be addressed here:
\begin{itemize}
\item (Correctness) We should show that there is a strong relation
between the standard semantics defined in section~\ref{section:syntax} and the path semantics give here. The proof of this is quite long,
the reader is referred to \cite{Bloss88,Coorg94} for details. Basically,
the safety
of path semantics guarantees that a function always takes one
of the paths computed by the path semantics.
\item (Computability) The algorithm computing paths should terminate
on every possible input program. Informally, this is guaranteed
by the fact that a function can have only a finite number of 
paths ($(2^N+1)^M$ for an N-argument, M-result function) and paths
of a function in an iteration ``increases'' with every iteration.
\end{itemize}
The complexity of the algorithm is $O(2^{MN})$ for a function
with N-arguments and M-results. Though this is exponential, it is 
still practical for ordinary programs if the number of arguments 
of a function is bounded by some small constant. As it subsumes 
strictness analysis \cite{Bloss87}, it is not possible to give
a more efficient algorithm (strictness analysis requires exponential
time \cite{Hudak86}).


\subsection{Global Partitioning using Paths}
\label{section:global-path}
In this section, we design a global partitioning algorithm using
the path analysis described in the previous section. 
Our algorithm is based on the intuition presented in section~\ref{section:global}, that is, convert general to basic blocks. 

Algorithm 3 (shown in figure~\ref{figure:algorithm-3}) partitions
a general block by propagating information in the paths, one
function at a time\footnote{
It is possible to propagate information for more than
one function at a time. However, this leads to the generation of 
a large number of basic blocks, increasing the complexity of the algorithm.}. The idea is to generate the basic blocks 
corresponding to each path of the function. By the safety of path semantics, 
we are guaranteed that the behavior
of the general block is identical to one of the basic blocks. If
we generate a partitioning that is correct for each of the basic blocks,
we can be assured that the partitioning is correct for the general
block too. 

This is achieved by using any basic block partitioning algorithm
(algorithm 1 or algorithm 2); the difference is the way demand
and tolerance sets are computed for each node in a general block. Instead
of computing them directly, they are computed using the demand
and tolerance sets of the basic blocks $b_1,\ldots,b_P$.

Computing demand and tolerance sets of the basic blocks $b_1,\ldots,b_P$
is done as in section~\ref{section:basic} -- with two minor changes.
First, nodes that are connected to $bot$ may be deleted -- they
never compute any value. Second, we rename the output labels in 
each of the basic blocks $b_1,\ldots,b_P$ to ensure that the
dependence properties of one basic block are not ``mixed up'' with
that of another basic block. Then, the union
of demand (tolerance) sets of a node $n$ in
$b_1,\ldots,b_P$ captures the dependence properties of all the
basic blocks: if any relation between two sets is true in $b$, it
will also be true in $b_1,\ldots,b_P$. In essence, algorithm 3
uses the demand and tolerance sets to simultaneously simulate a basic block
algorithm on each $b_1,\ldots,b_P$, generating partitions safe for all
of them.

\begin{myfig}{figure:algorithm-3}{Algorithm 3 that Partitions General
Blocks}
\noindent{\bf Algorithm 3}\\
Given a block $b$:
\begin{enumerate}
\item{Select a node in $b$ that calls some function (say $f$). 
Disconnect all other nodes that are not primitive operators. Disconnecting
a node involves introducing a new output node corresponding to 
each of the function's arguments and a new input node corresponding
to each of the function's results.}
\item{Let $f$ be an M-result function and have $P$ paths. For each $1 \leq j \leq P$
construct block $b_j$ as follows:
\begin{enumerate}
\item{Let the $j^{th}$ path be $(p_{j1},p_{j2},\ldots,p_{jM})$.}
\item{For each $1 \leq k \leq M$ do
\begin{enumerate}
\item{Let $O$ be the nodes of $b$ connected to the $k^{th}$ output of $f$.}
\item{If $p_{jk} = \bot_p$, connect each node in $O$ to a new input
node called $bot$.}
\item{Otherwise, introduce a new ``dummy'' node ($op$) with inputs connected
to the arguments of $f$ in $p_{jk}$. Connect the output $op$ with
each node in $O$.}
\end{enumerate}}
\end{enumerate}}
\item{For $1 \leq j \leq P$, delete all nodes in $b_j$ that
are (transitively) connected to a {\em bot} node.}
\item{Rename all input and output nodes so 
that there is no conflict of names between blocks.}
\item{Apply any basic block partitioning\footnotemark algorithm with the
demand and tolerance sets of nodes in $b$ computed 
using the demand and tolerance sets of nodes in $b_1,\ldots,b_P$ as 
follows:
\begin{eqnarray*}
Demand_{b}(n) & = & \bigcup_{1\leq j \leq P}Demand_{b_{j}}(n)\\
Tolerance_{b}(n) & = & \bigcup_{1\leq j \leq P}Tolerance_{b_{j}}(n)
\end{eqnarray*}}
\item{Go to step 1 if changes to the partitioning of $b$ occur.}
\end{enumerate}
\end{myfig}
\footnotetext{A small change is needed. We have to make sure the ``dummy'' operators introduced do not fall into any partition.}

The complexity of the algorithm is $O(PN^3)$ where $P$ is the largest
number of paths of a function in the program. 


