\section{Comparison with Related Work}
\label{section:related}
Strictness analysis \cite{Mycroft80,Burn86,Clack85} has similar
goals to that of partitioning. It tries to determine which
arguments of a function are strict, so that they may 
be evaluated directly --
instead of building a closure/graph for them, which is 
significantly more expensive. Partitioning (as presented in 
this paper) differs from this
technique in several ways: the algorithms given here do not
seek to preserve laziness, the benefit of partitioning is more
explicit -- it results in the creation of larger threads. 

Partitioning techniques could be useful in compiling lazy
functional languages too. The difference is that the choice
for partitioning algorithms is restricted: only demand set partitioning 
preserves laziness \cite{Traub89}. In some cases, demand
set partitioning  can generate
better code than traditional strictness analysis, by making
use of the fact that two arguments are always used ``together''
in a function, even though the function may not be strict in 
them \cite{Traub92}.

Path analysis \cite{Bloss87,Bloss88} identifies the order
in which expressions in a function are evaluated. It has applications
in reusing storage, optimizing representation of thunks \cite{Bloss88}.
Our contribution is to recognize that a restricted definition of 
paths is very useful in capturing dependence information of functions,
and this information can be effectively used in a 
global partitioning algorithm.

Much of the research in partitioning is based on 
the seminal work in \cite{Traub88}. 
It defined the partitioning problem, its relation to dependence
analysis and provided some insight into the partitioning problem by
proving a related problem NP-hard. Our work provides the first
insight into the complexity of the problem -- it shows that finding 
an optimal partitioning
(minimum number of partitions or largest possible partitions) is
NP-hard even for basic blocks.

Developing heuristics to generate safe partitions is the
focus of many papers \cite{Hoch91,Schauser91,Schauser94a}.
These include {\em dependence partitioning} \cite{Ianucci88} based on 
the notion of dependence sets. Dependence sets 
are the natural ``dual'' of demand sets, where 
each node is annotated with the set of {\em inputs} that it depends
on. In dependence set partitioning, nodes with the same dependence
set can be merged together. Tolerance sets defined in this paper subsume the notion of
demand sets: \ie, it is always possible to merge two nodes using their
tolerance sets, if it is possible to do so using dependence sets, but
not vice-versa. Figure~\ref{figure:sets} provides an example of this.
The dependence
sets of nodes $2$ and $5$ are $\{a,b\}$ and $\{b\}$ respectively, but
it is still safe to merge them as they have the same tolerance sets.

Demand sets itself were
introduced in \cite{Schauser91,Hoch91}, and the iterated partitioning
algorithm (similar to algorithm 2) was introduced in \cite{Traub92,Hoch91}.
Most of these papers did not do any global analysis for partitioning,
they used the disconnecting operation used in algorithm 3
to handle conditionals and 
calls to user defined functions. Also, these algorithms did not
produce {\em maximal} partitions, \ie, even after these algorithms
terminated, it was possible that there are two partitions that could
be merged safely.

An inter-procedural algorithm for partitioning was 
first designed in \cite{Traub92}.
This algorithm is based on the idea that the demand/dependence sets
themselves contain some dependence information, and propagating
these sets between the definition of a function to its call-site
yields better partitions. A major limitation of the inter-procedural
algorithm given there is its inability to handle recursive functions. 
Our algorithm has no such limitations, as the paths of recursive
functions are well-defined and our inter-procedural algorithm 
is based {\em only} on a function's paths. For example, in figure~\ref{figure:global}, our inter-procedural algorithm succeeds in merging nodes
$1$ and $2$ when {\tt f} is the recursive function given in Section~\ref{section:convert-general}. Their algorithm has to make a worst case assumption about
the recursive call to {\tt f}, and is unable to merge these two nodes.

Interestingly, our algorithm is more powerful even in the 
non-recursive case.\\
Example 3:
\begin{verbatim}
def f p a b c = 
 {x = a + b;
  y = b * c;
  z = if p then x else y	
 in
   z};
\end{verbatim}
In this example, the algorithm of \cite{Traub92} fails to merge
the input nodes corresponding to {\tt p} and {\tt b}, even though the result
is strict in both of them. This is because the strictness information
is obscured by the presence of non-strict arguments {\tt a} and {\tt c}. Our
inter-prodedural algorithm detects that {\tt p} and {\tt b} can 
be merged in both the basic blocks generated by the two branches of
the conditional, thus merging {\tt p} and {\tt b}.

Independent of this work, the partitioning algorithms in
\cite{Traub92} have been extended in \cite{Schauser94a,Schauser94b} to
generate maximal partitions for basic blocks and to handle
recursive functions. Algorithm 1 for partitioning basic blocks
is equivalent to the one presented in \cite{Schauser94b}, though it is a different
formulation and its complexity is slightly better. Algorithm 2, however,
is a new algorithm that subsumes the algorithm in \cite{Traub92}, but
still retains its structure. The inter-procedural algorithm
given in \cite{Schauser94b} differs from our inter-procedural
algorithm in the following ways.
\begin{itemize}
\item It still uses dependence and demand sets to propagate global 
information, and thus retains some of the limitations of \cite{Traub92}
(\eg, example 3).
\item The extension that detects strictness information is an approximation
to the abstract interpretation algorithm used here.
\end{itemize}
However, the complexity of our inter-procedural 
algorithm is higher than that of the algorithm in \cite{Schauser94b}.


